1. INSERT(x, p, L). Этот оператор вставляет объект х в позицию р и далее в следующую, более высокую позицию. Таким образом, если список L состоит из элементов а1, a2, …,an, то после выполнения этого оператора он будет иметь вид а1, a2, …, ap-1, x, ap, …, an. Если р принимает значение END(L), то будем иметь a1, a2, …, an, x. Если в списке L нет позиции р, то результат выполнения этого оператора не определён.

2. LOCATE(x, L). Эта функция возвращает позицию объекта х в списке L.если в списке объект х встречается несколько раз, то возвращается позиция первого от начала списка объекта х. Если объекта х нет в списке L, то возвращается END(L).

3. RETRIEVE(p, L). Эта функция возвращает элемент, который стоит в позиции р в списке L. Результат не определён, если p = END(L) или в списке L нет позиции p. Элементы должны быть одного типа, который в принципе может возвращать функция. Однако на практике мы всегда можем изменить эту функцию так, что она будет возвращать указатель на объект типа elementtype.

4. DELETE(p, L). этот оператор удаляет элемент в позиции p списка L. Так, если список L состоит из элементов a1, a2, …, an, то после выполнения этого оператора он будет иметь вид a1, a2, …, ap-1, ap+1, …, an. Результат не определён, если в списке L нет позиции p или p = END(L).

5. NEXT(p, L) и PREVIOUS(p, L). Эти функции возвращают соответственно следующую и предыдущую позиции от позиции p в списке L.если р – последняя позиция в списке L, то NEXT(p, L) = END(L). Функция NEXT не определена, когда p = END(L). Функция PREVIOUS не определена, если p = 1. Обе функции не определены, если в списке L нет позиции p.

6. MAKENULL(L). Эта функция делает список L пустым и возвращает позицию END(L).

7. FIRST(L). Эта функция возвращает первую позицию в списке L. Если список пустой, то возвращается позиция END(L).

8. PRINTLIST(L). Печатает элементы списка L в порядке их расположения.

Стеки.

Стек – это специальный тип списка, в котором все вставки и удаления выполняются только на одном конце, называемом вершиной (top). Стеки также иногда называют «магазинами», а в английской литературе для обозначения стеков ещё используется аббревиатура LIFO (last-in-first-out – последний вошел – первый вышел). Интуитивными моделями стека могут служить колода карт на столе при игре в покер, книги, сложенные в стопку, или стопка тарелок на полке буфета; во всех этих моделях взять можно только верхний предмет, а добавить новый объект можно, только положив его на верхний. Абстрактные типы данных семейства STAK (Стек) обычно используют следующие пять операторов.

1. MAKENULL(S). Делает стек S пустым.

2. TOP(S). Возвращает элемент из вершины стека S. Обычно вершина стека идентифицируется позицией 1, тогда TOP(S) можно записать в терминах общих операторов списка как RETRIEVE(FIRST(S), S).

3. POP(S). Удаляет из вершины стека (выталкивает из стека), в терминах операторов списка этот оператор можно записать как DELETE(FIRST(S), S). Иногда этот оператор реализуется в виде функции, возвращающей удаляемый элемент.

4. PUSH(x, S). Вставляет элемент x в вершину стека S (заталкивает элемент в стек). Элемент, ранее находившийся в вершине стека, становится элементом, следующим за вершиной, и т.д. В терминах общих операторов списка данный оператор можно записать как INSERT(x, FIRST(S), S).

5. EMPTY(S). Эта функция возвращает значение true (истина), если стек S пустой, и значение false (ложь) в противном случае.

Очереди.

Другой специальный тип списка – очередь (queue), где элементы вставляются с одного конца, называемого задним (rear), а удаляются с другого, переднего (front). Очереди также называют «списками типа FIFO» (аббревиатура FIFO расшифровывается как first-in-first-out: первым вошел – первым вышел). Операторы, выполняемые над очередями, аналогичны операторам стеков. Существенное отличие между ними состоит в том, что вставка новых элементов осуществляется в конец списка, а не в начало, как в стеках. Кроме того, различна устоявшаяся терминология для стеков и очередей. Для работы с очередями будут использоваться следующие операторы.

1. MAKENULL(Q) очищает очередь Q, делая её пустой.

2. FRONT(Q) – функция, возвращающая первый элемент очереди Q. Можно реализовать эту функцию с помощью операторов списка как RETRIEVE(FIRST(Q), Q).

3. ENQUEUE(x, Q) вставляет элемент x в конец очереди Q. С помощью операторов списка этот оператор можно выполнить следующим образом: INSERT(x, END(Q), Q).

4. DEQUEUE(x, Q) удаляет первый элемент очереди Q. Также реализуем с помощью операторов списка как DELETE(FIRST(Q), Q).

5. EMPTY(Q) возвращает значение true тогда и только тогда, когда Q является пустой очередью.

Отображения.

Отображение – это функция, определённая на множестве элементов (области определения) одного типа (будет обозначаться domaintype – тип области определения функции) и принимающая значения из множества элементов (области значений) другого типа, этот тип будет обозначаться rangetype – тип области значений (конечно, типы domaintype и rangetype могут совпадать). Тот факт, что отображение М ставит в соответствие элемент d типа domaintype из области определения элементу r типа rangetype из области значений, будет записываться как M(d) = r.

Некоторые отображения, подобные square(i) = i2, легко реализовать с помощью функций и арифметических выражений языка Pascal. Но для многих отображений нет очевидных способов реализации, кроме хранения для каждого d значения M(d). Например, для реализации функции, ставящей в соответствие работникам их недельную зарплату, требуется хранить текущий заработок каждого работника.

Рассмотрим операторы, которые можно выполнить над отображением М. Например, по заданному элементу d типа domaintype мы хотим получить M(d) или узнать, определено ли M(d) (т.е. узнать, принадлежит ли элемент d области определения М). Или хотим добавить новые элементы в текущую область определения М и поставить им в соответствие элементы из области значений. Очевидна также необходимость иметь оператор, который изменял бы значение M(d). Кроме того, нужно средство «обнуления» отображения, переводящее любое отображение в пустое отображение, т.е. такое, у которого область определения пуста. Всё это можно обобщить в следующие три команды.

1. MAKENULL(M). Делает отображение М пустым.

2. ASSIGN(M, d, r). Делает М(d) равным r независимо от того, как M(d) определено ранее.

3. COMPUTE(M, d, r). Возвращает значение true и присваивает переменной r значение M(d), если последнее определено, и возвращает false в противном случае.

Структуры данных и алгоритмы для внешней памяти.

В алгоритмах, которые обсуждались до сих пор, предполагалось, что объем входных данных позволяет обходиться исключительно основной (оперативной) памятью. Но как быть, если нужно, например, отсортировать всех государственных служащих по продолжительности их рабочего стажа или хранить информацию из налоговых деклараций всех граждан страны? Когда возникает необходимость решать подобные задачи, объём обрабатываемых данных намного превышает возможности основной памяти. В большинстве компьютерных систем предусмотрены устройства внешней памяти, такие как жесткие диски, или запоминающие устройства большой ёмкости, на которых можно хранить огромные объёмы данных. Однако характеристики доступа к таким устройствам внешней памяти существенно отличаются от характеристик доступа к основной памяти. Чтобы повысить эффективность использования этих устройств был разработан ряд структур данных и алгоритмов.