Полустатические структуры данных

 

Полустатические структуры данных

Характерные особенности полустатических структур

признаками: - они имеют переменную длину и простые процедуры ее изменения; - изменение длины структуры происходит в определенных пределах,

Стеки

Логическая структура стека

включение и исключение элементов из которого выполняются только с одной стороны списка, называемого вершиной стека. Применяются и другие названия стека - магазин и очередь, функционирующая по

Машинное представление стека и реализация операций

ляется память, как для вектора. В дескрипторе этого вектора кроме обычных для вектора параметров должен находиться также указатель стека - адрес вершины стека. Указатель стека может указывать либо

Стеки в вычислительных системах

многих задач вычислительной техники. Наиболее типичной из таких задач является обеспечение вложенных вызовов процедур. Предположим, имеется процедура A, которая вызывает процедуру

Очереди FIFO

Логическая структура очереди

первым исключается"). называется такой последовательный список с переменной длиной, в котором включение элементов выполняется только с одной стороны списка (эту сторону часто называют концом

Машинное представление очереди FIFO и реализация

Операций

дополнение к обычным для дескриптора вектора параметрам в нем должны находиться два указателя: на начало очереди (на первый элемент в очереди) и на ее конец (первый свободный элемент в оче-

Очереди с приоритетами

ровании очередей, отличных от FIFO или LIFO. Порядок выборки элементов из таких очередей определяется приоритетами элементов. Приоритет в общем случае может быть представлен числовым значени-

Очереди в вычислительных системах

мы является буфер клавиатуры в Базовой Системе Ввода-Вывода ПЭВМ IBM PC. Буфер клавиатуры занимает последовательность байтов памя- ти по адресам от 40:1E до 40:2D включительно. По адресам 40:1A и

Деки

Логическая структура дека

queue,т.е очередь с двумя концами) - это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Частный случай де-

Деки в вычислительных системах

ной технике и программировании гораздо реже, чем задачи, реализу- емые на структуре стека или очереди. Как правило, вся организация дека выполняется программистом без каких-либо специальных средств

Строки

Логическая структура строки

лов, принадлежащих конечному множеству символов, называемому ал- фавитом. Строки обладают следующими важными свойствами:

Операции над строками

Базовыми операциями над строками являются:

- определение длины строки;

- присваивание строк;

- конкатенация (сцепление) строк;

- выделение подстроки;

- поиск вхождения.

Операция определения длины строки имеет вид функции, возвра-

щаемое значение которой - целое число - текущее число символов в

строке.

Операция присваивания имеет тот же смысл, что и для других

типов данных.

Операция сравнения строк имеет тот же смысл, что и для дру-

гих типов данных. Сравнение строк производится по следующим пра-

вилам. Сравниваются первые символы двух строк. Если символы не

равны, то строка, содержащая символ, место которого в алфавите

ближе к началу, считается меньшей. Если символы равны, сравнива-

ются вторые, третьи и т.д. символы. При достижении одной конца

одной из строк строка меньшей длины считается меньшей. При ра-

венстве длин строк и попарном равенстве всех символов в них стро-

ки считаются равными.

Результатом операции сцепления двух строк является строка,

длина которой равна суммарной длине строк-операндов, а значение

соответствует значению первого операнда, за которым непосредс-

твенно следует значение второго операнда. Операция сцепления дает

результат, длина которого в общем случае больше длин операндов.

Как и во всех операциях над строками, которые могут увеличивать

длину строки (присваивание, сцепление, сложные операции), возмо-

жен случай, когда длина результата окажется большей, чем отведен-

ный для него объем памяти. Естественно, эта проблема возникает

только в тех языках, где длина строки ограничивается. Возможны

три варианта решения этой проблемы, определяемые правилами языка

или режимами компиляции:

- никак не контролировать такое превышение, возникновение

такой ситуации неминуемо приводит к труднолокализуемой ошибке при

выполнении программы;

- завершать программу аварийно с локализацией и диагностикой

ошибки;

- ограничивать длину результата в соответствии с объемом от-

веденной памяти;

Операция выделения подстроки выделяет из исходной строки

последовательность символов, начиная с заданной позиции n, с за-

данной длиной l. В языке PASCAL соответствующая функция называет-

ся COPY. В языках PL/1, REXX соответствующая функция - SUBSTR -

обладает интересным свойством, отсутствующим в PASCAL. Функция

SUBSTR может употребляться в левой части оператора присваивания.

Например, если исходное значение некоторой строки S - 'ABCDEFG',

то выполнение оператора: SUBSTR(S,3,3)='012'; изменит значение

строки S на - 'AB012FG'.

При реализации операции выделения подстроки в языке програм-

мирования и в пользовательской процедуре обязательно должно быть

определено правило получения результата для случая, когда началь-

ная позиция n задана такой, что оставшаяся за ней часть исходной

строки имеет длину, меньшую заданной длины l, или даже n превыша-

ет длину исходной строки. Возможные варианты такого правила:

- аварийное завершение программы с диагностикой ошибки;

- формирование результата меньшей длины, чем задано, возможно да-

же - пустой строки.

Операция поиска вхождения находит место первого вхождения

подстроки-эталона в исходную строку. Результатом операции может

быть номер позиции в исходной строке, с которой начинается вхож-

дение эталона или указатель на начало вхождения. В случае отсутс-

твия вхождения результатом операции должно быть некоторое специ-

альное значение, например, нулевой номер позиции или пустой

указатель.

На основе базовых операций могут быть реализованы и любые

другие, даже сложные операции над строками. Например, операция

удаления из строки символов с номерами от n1 включительно n2 мо-

жет быть реализована как последовательность следующих шагов:

- выделение из исходной строки подстроки, начиная с позиции

1, длиной n1-1;

- выделение из исходной строки подстроки, начиная с позиции

n2+1, длиной длина исходной строки - n2;

- сцепление подстрок, полученных на предыдущих шагах.

Впрочем, в целях повышения эффективности некоторые вторичные

операции также могут быть реализованы как базовые - по собствен-

ным алгоритмам, с непосредственным доступом к физической структу-

ре строки.

Представление строк в памяти.

менчивыми являются строки в каждой конкретной задаче, и средства такого представления варьируются от абсолютно статического до динамического. Универсальные языки программирования в основном

ПРЕДСТАВЛЕНИЕ СТРОК ВЕКТОРОМ ПЕРЕМЕННОЙ ДЛИНЫ С ПРИЗНАКОМ

длину строк. Признак конца - это особый символ, принадлежащий ал- фавиту (таким образом, полезный алфавит оказывается меньше на один символ), и занимает то же количество разрядов, что и все ос-

ПРЕДСТАВЛЕНИЕ СТРОК ВЕКТОРОМ ПЕРЕМЕННОЙ ДЛИНЫ СО СЧЕТЧИКОМ.

точное количество битов, чтобы их с избытком хватало для предс- тавления длины самой длинной строки,какую только можно предста- вить в данной машине. Обычно для счетчика отводят от 8 до 16