В качестве основных представителей абстрактных типов данных (АТД ) рассматриваются:
Список (L), представляющий собой последовательность элементов a1, a 2, … , a n , где n ≥ 0 и все его элементы ai относятся к определённому типу данных datatype.
Стек (S) − это специальный тип списка, в котором все вставки и удаления выполняются только на одном конце, называемом вершиной (top).
Очередь (Q) − другой специальный тип списка, где элементы вставляются с одного конца, называемым задним (rear), а удаляются с другого, переднего (front).
Для АТД типа список L определено следующее множество операторов:
End (L). Возвращает позицию, следующую за последней позицией n в n – элементном списке L. Позиция End (L), рассматриваемая как расстояние от начала списка, которое может изменяться при увеличении или уменьшении списка, в то время как другие позиции имеют неизменное расстояние от начала списка.
Insert(x, p, L). Этот оператор вставляет элемент x в позицию p в списке L, перемещая элементы от позиции p и далее в следующую, долее высокую позицию. Таким образом , если список L состоит из элементов a1, a 2, … , a n , то после выполнения данного оператора он будет иметь вид a1, a 2, …, a p-1, x, a p ,…, a n . Если в списке L нет позиции p, то результат выполнения данного оператора не определён.
Locate (х, L). Эта функция возвращает позицию объекта x в списке L. Если в списке объект x встречается несколько раз, то возвращается позиция первого от начала списка объекта x. Если объекта x нет в списке L, то возвращается END(L).
Retrive (p, L) Эта функция возвращает элемент, который стоит в позиции p в списке L. Результат не определён, если p = END(L) или в списке нет позиции р.
Delete (p, L). Этот оператор удаляет элемент в позиции p списка L. Так если список L состоит из элементов a1, a 2, … , a n , то после выполнения данного оператора он будет иметь вид a1, a 2, …, a p-1, ap+1 ,…, a n. Результат не определён, если в списке L нет позиции p или p = END (L).
Next (p, L) и Previous (p, L). Эти функции возвращают соответственно следующую и предыдущую позиции от позиции p в списке L. Если p − последняя позиция в списке L, то Next (p, L) = END(L). Функция Next не определена, когда p = END (L). Функция Previous не определена, если p = 1. Обе функции не определены, если в списке L нет позиции p.
Makenull (L). Эта функция делает список L пустым и возвращает позицию END(L).
First (L). Эта функция возвращает первую позицию в списке L. Если список пустой, то возвращается позиция END (L).
Printlist (L). Печатает элементы списка L в порядке их расположения.
Double (L). Возвращает список D, состоящий из элементов, которые имеют пару в списке L.
Purge (L). Процедура вычищает из списка L повторяющиеся элементы.
Для АТД семейства стек S свойственны следующие пять операторов:
Makenull (S). Делает стек S пустым.
Top (S).Возвращает элемент из вершины стека.
Pop (S). Удаляет элемент из вершины стека.
Push (x, S). Вставляет элемент x в вершину стека S, элемент находившийся ранее в вершине стека, становится элементом, следующим за вершиной, и т.д.
Empty (S). Эта функция возвращает значение true (истина), если стек S пустой, и значение false (ложь) в противном случае.
Для работы с АТД семейства очередь Q распространены следующие операторы:
Makenull (Q). Очищает очередь Q, делая её пустой.
Front (Q). Функция возвращает первый элемент очереди Q.
EnQueue (x, Q). Вставляет элемент x в конец очереди Q.
DeQueue (Q). Удаляет первый элемент очереди Q.
Empty (Q) возвращает значение true тогда и только тогда, когда Q является пустой очередью.
Задание: Реализовать на языке высокого уровня (С++) один из 3-х указанных АТД (список, стек, очередь) и 3 оператора для работы с ним (см. табл.1-3).
