Списки, соновные виды (список, стек, очередь), реализация

В математике список представляет собой последовательность однотипных элементов, упорядоченных определённым образом, который может содержать повторные элементы. Количество элементов (n) – длина списка. При n=0 список называется пустым. Важным свойством списка является линейная упорядоченность его элементов в соответствии с их позициями в списке.
Чтобы определить АТД на основе мат. понятия списка надо задать операторы, выполняемые над данными типа «список».
L - список объектов некоторого типа.
el _type – тип элементов списка.
X – переменная или объект из списка
p – позиция элемента в списке
В зависимости от реализации списка позиция элемента может быть задана целым числом, показывающим номер элемента или указателем на элемент списка при использовании динамической памяти.
Часто над объектами типа «список» определяются следующие операторы:
1. INS(X,p,L) – Вставить Х в позицию р списка L.
2. DEL(p,L) - Удалить элемент из позиции р списка L.
3. LOCATE(X,L) - Возвратить позицию элемента Х в списке L.
4. NEXT(p,L) PREV(p,L) - Возвратить следующую и предыдущую позицию в списке L
5. FIRST(L) - Возвратить первую позицию в списке L.
6. MAKENULL(L) –Создать пустой список
7. RET(p,L) – Возвратить элемент из позиции p списка L.

Абстрактные типы данных. Реализация списка с использованием массива
Недостатки: ограниченная длина списка; необходимость перемещения элементов части списка при вставке или удаления элемента.
Элементы списка располагаются в смежных ячейках массива, что позволяет легко просматривать список и вставлять элемент в его конец. Но вставка или удаление элемента в середине списка требует перемещение всех последующих элементов в 1 позицию к концу или началу списка.
Определим тип данных «список».
List как запись включает 2 поля:
1 поле содержит массив для хранения элементов. 2 поле – переменную, для хранения позиции последнего элемента списка.
const
maxlen=100;
type
List=record;
element: array[1..maxlen] of el_type;
last: integer;
end;
position = integer;


Приведём примеры реализации нек-х операторов для типа данных список:
1) Оператор- сделать список пустым.
Function MAKENULL( var L:List):position;
begin
L.last:=0
MAKENULL:=0
end;

2) Удалить элемент списка L из позиции p
Procedure DEL( p:position; var L:List);
Var q:position;
Begin
If (pL.Last) then ERROR("Недопустимая позиция”);
If (p for q:=p to last-1 do
L.element[q]=L.element[q+1]
L.Last:=L.Last-1;
End;

Абстрактные типы данных. Реализация списка с использованием указателей (в динамической памяти)
Чтобы исключить недостатки реализации списка с использованием массивов каждый элемент списка размещается в динамической памяти и дополняется указателем на следующий элемент. При этом требуется дополнительная память.
Все переменные массивов, описываемые в разделе var, размещаются в памяти перед выполнением программы и находятся там постоянно, они называются статическими. Но во время выполнения программы в памяти могут размещать новые переменные и после их использования - удалять, освобождая память. Такие переменные динамические. Они не имеют имен и обращение к ним производится по их адресам в памяти. Для хранения адресов используются переменные особого типа – указатели. Различают указатели на целые(pi), вещественные(pr) переменные, на массивы(pm), записи и на любые типы данных. Существует 1 константа типа указатель: NIL, которая обозначает «пустой адрес». Переменная типа «указатель» определяет адрес динамической переменной. Для описания указателей в программах на Objet Pascal используется следующая конструкция:
Type
mas=array[1..10] of integer;
Var
pi:^integer;
pr:^real;
pm:^mas;

Значение пустого адреса можно присвоить любому указателю. Выделение памяти для динамической переменной производится процедурой NEW(указатель). Эта процедура резервирует необходимый объем памяти, адрес которого сохраняется в указателе. Освобождение памяти после использования –процедура Dispose(указатель).
Список организованной динамической памяти можно представить:

Каждый элемент списка размещается в ячейке, которая содержит 2 поля.
1 поле: элемент. 2 поле: указатель на следующий элемент.
Первая ячейка определяет заголовок списка, элемента не содержит, но содержит указатель на 1 элемент. Позиция при такой организации списка отличается от номера элемента. Под позицией элемента понимается указатель на предыдущую ячейку списка, которая содержит указатель на заданный элемент.
Описание абстрактного типа данных «список» имеет вид:
type
LIST=^cell;
cell=record;
element: el_type;
next: List;
end;
position=List;

Покажем реализацию некоторых операторов для переменных типа список:
1) Создать пустой список:
Function MAKENULL (var L:List): position;
begin
New (L);
L^.next:= NIL;
MAKENULL:=L;
end;

2) Вставить элемент x в позицию p списка L.
Procedure INS(x:el_type, p:position var L:List);
Var
temp: position;
begin
temp:=p^.next;
New (p^.next); // Выделение памяти под ячейку
p^.next^.element:=x; // В нее записывается x
p^.next^.next:=temp;
End.

Рассматриваемый тип данных список показывает пример реализации однонаправленного списка, в котором указатель позволяет определить только следующий элемент, но не предыдущий. Существуют двунаправленные списки, в которых ячейка содержит 2 указателя, на следующий и на предыдущий элемент. При такой организации проще просматривать список в двух направлениях: прямом и обратном. Здесь в качестве позиции элемента может использоваться указатель на ячейку, содержащую данный элемент.
Недостатком применения указателей является то, что они затрудняют обращение к элементам списка по их номеру и их не рекомендуется использовать при частых вставках и удалениях элементов.

Абстрактные типы данных. Стек
Стек – специальный тип списка, в котором все вставки и удаления элемента выполняются с одного конца списка, называемого вершиной стека. Обозначается LIFO(Last int –First out). Для работы с типом данных стек обычно используют следующие операторы:
1) MAKENULL(S) - Создать пустой стек S.
2) PUSH(x,S) - Вставить элемент x в вершину стека S.
3) ELEM(S) – Возвратить значение элемента из вершины стека.
4) EMPTY(S) - Проверить, является ли стек S пустым.
5) POP(S) – Возвратить значение элемента из вершины стека и удалить его оттуда.
Стек может быть реализован, как частный случай списка. Для этого надо объявить переменную S как переменную типа «список». Тогда первый оператор будет реализован одноимённой функцией для списка.
Реализация стека с помощью массива.
Используется подход, в котором изменяется расположение первого (верхнего) элемента стека. Элемент вершины стека обозначается специальной переменной top. Реализацию стека с помощью массива можно представить след-м образом:
const
maxlen=100;
type
Stack=record;
element:array[1..maxlen] of el_type;
top:integer;
end;

Покажем реализацию некоторых операторов для переменных типа стек:
1) Создать пустой стек
procedure MAKENULL(var S: Stack);
begin
S.top:=0
еnd;

2) Запись элемента в стек
procedure PUSH(x:el_type; var S:Stack);
begin
if S.top=maxlen then ERROR(«Стек заполнен»)
else
begin
S.top:=S.top+1;
S.element[S.top]:=x;
end;
end;

3)Выбор элементов из стека
Function POP(var S:Stack):el_type;
Begin
If S.top=0 then ERROR("Стек пустой”);
Else
Begin
POP:=S.element[S.top];
S.top:=S.top-1;
End;
End;

Абстрактные типы данных. Очередь
Очередь вляется особым видом списка, в который элементы добавляются с одного конца, а выбираются с другого конца. Обозначается: FIFO. Для работы с очередью в основном используют операторы:
1) MAKENULL(Q) – Создать пустую очередь.
2) BACK(x,Q) - Поместить элемент x в конец очереди Q.
3) ELEM(Q) - Возвратить значение элемента из начала очереди Q.
4) FRONT(Q) - Выбрать элемент из начала очереди Q.
5) EMPTY(Q) - Проверить, является ли очередь Q пустой.
Если для реализации очереди используется тип данных «список», то перечисленные операторы можно реализовать следующим образом:
1) Реализация одноименной функцией.
2)
INS (x, LAST(Q))
, где LAST(Q) – оператор определения последней позиции списка Q.

3)
x:=RET(FIRST(Q),Q);

4)
x:=RET(FIRST(Q),Q); DEL(FIRST(Q),Q);

5)
if Q^.next=NIL then EMPTY:=true
Else EMPTY:=false;

В отличии от стека реализация очереди в динамической памяти с помощью типа данных «список» не отличается высокой эффективностью. Существует еще один вариант построения очереди в виде однонаправленного списка в динамической памяти. Выделяют 2 специальные ячейки для определения позиций начала и конца очереди.
First – начало очереди. Last – конец очереди.
Тип элемента очереди определяется как указатель на ячейку, состоящий из 2 полей: информационного и указателя на следующий элемент. Очередь определяется как запись, состоящая из 2 ячеек.
type
QUEUE=record;
first, last:^cell;
end;

Для первой ячейки очереди, на которую указывает First, информационное поле никогда не используется. Для последней ячейки, на которую указывает Last поле NEXT всегда определяет пустой указатель.
Покажем примеры реализации операторов:
1) Создать пустую очередь
Procedure MAKENULL ( var Q:QUEUE);
begin
New(Q.first);
Q.first^.next:=NIL;
Q.last:=Q.first;
end;

2)Добавить элемент в конец очереди
Procedure BACK(x:el_type; var Q:QUEUE);
Begin
NEW(Q.Last^.next);
Q.Last:=Q.Last^.next;
Q.Last^.element:=x;
Q.Last^.next:=NIL;
End;

Предполагается подход, где массив рассматривается как циклическая структура данных, в которой за последним элементом идет первый элемент массива.
Пусть имеется некоторый массив: x[1..maxlen]
Для организации циклического просмотра элементов используется:
Function NEXT (i:integer):integer;
begin
if i=maxlen then NEXT:=1;
else i:=i+1;
end;

Абстрактные типы данных. Реализация очереди с помощью циклического массива.

Реализация очереди позволяет добавлять и выбирать элементы без перемещения оставшихся. Начало и конец текущего состояния очереди будет фиксироваться с помощью first и last. Тогда, при включении очередного элемента в очередь будет изменяться индекс последнего элемента. А при выборке элемента из очереди будет изменяться индекс первого элемента. Вводится дополнительная переменная для корректной организации очереди на основе циклического массива: len – текущая длина очереди.
Описание очереди:
type
QUEUE=record
element:=array[1..maxlen]of el_type;
first, last, len: integer;
end;

1) Создать пустую очередь
Procedure MAKENULL ( var Q:QUEUE);
begin
Q.first=1;
Q.last=maxlen;
Q.len:=0;
end;

2) Выборка элемента из начала очереди.
function FRONT(var Q:QUEUE): el_type;
begin
if EMPTY(Q) then ERROR («Очередь пуста»)
else
begin
FRONT:=Q.element[Q.first];
Q.first:=NEXT[Q.first];
Q.len:=Q.len-1;
end;
end;