Лабораторная работа № 3 «Реализация абстрактных типов данных».

В качестве основных представителей абстрактных типов данных (АТД ) рассматриваются:

Список (L), представляющий собой последовательность элементов a₁, a ₂, … , a _n , где n ≥ 0 и все его элементы a_i относятся к определённому типу данных datatype.

Стек (S) − это специальный тип списка, в котором все вставки и удаления выполняются только на одном конце, называемом вершиной (top).

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

Для АТД типа список L определено следующее множество операторов:

End (L). Возвращает позицию, следующую за последней позицией n в n – элементном списке L. Позиция End (L), рассматриваемая как расстояние от начала списка, которое может изменяться при увеличении или уменьшении списка, в то время как другие позиции имеют неизменное расстояние от начала списка.

Insert (x, p, L). Этот оператор вставляет элемент x в позицию p в списке L, перемещая элементы от позиции p и далее в следующую, долее высокую позицию. Таким образом , если список L состоит из элементов a₁, a ₂, … , a _n , то после выполнения данного оператора он будет иметь вид a₁, a ₂, …, 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 состоит из элементов a₁, a ₂, … , a _n , то после выполнения данного оператора он будет иметь вид a₁, a ₂, …, a _p-1, a _p+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).

Таблица 1. Список

№	Варианты Операторы	1	2	3	4	5	6	7	8
	Insert (x, p, L)	+		+				+
	Locate (х, L)		+			+		+
	Retrive (p, L)	+			+				+
	Delete (p, L)			+			+
	Next (p, L)				+
	Previous (p, L)		+
	First (L)			+			+		+
	Makenull (L)	+				+
	Printlist (L)		+				+		+
	Double (L)				+
	Purge (L)					+		+

Таблица 2. Стек

№	Варианты Операторы	1	2	3	4	5	6	7	8
	Makenull (S)		+		+
	Top (S)	+							+
	Pop (S)	+			+			+
	Push (x, S)		+			+	+		+
	Empty (S)			+				+
	Printlist (S)							+
	Locate (х, S)			+			+		+
	Retrive (p, S)	+			+	+
	Double (S)		+				+
	Purge (S)			+		+

Таблица 3. Очередь

№	Варианты Операторы	1	2	3	4	5	6	7	8
	Makenull (L)		+		+
	Front (Q)	+							+
	EnQueue (x, Q)	+			+			+
	DeQueue (Q)		+			+	+
	Empty (Q)							+
	Printlist (Q)			+				+
	Locate (х, Q)			+		+	+		+
	Retrive (p, Q)	+			+	+
	Double (Q)			+			+
	Purge (Q)		+						+

10