2. Абстрактные типы данных. Примеры и варианты реализации.
Абстрактный тип данных - это мат. модель задачи или её фрагмента с совокупностью операторов, определенных в рамках этой модели.
Реализация АТД включает:
- выбор необходимых структур данных, построенных на основе стандартных типов данных, используемого языка программирования.
- разработка процедур и функций для выполнения необходимых операций над объектами АТД.
АТД Список - последовательность однотипных элементов, упорядоченных определённым образом, который может содержать повторные элементы. Количество элементов (n) – длина списка. Важным свойством списка является линейная упорядоченность его элементов в соответствии с их позициями в списке. Чтобы определить АТД на основе мат. понятия списка надо задать операторы, выполняемые над данными типа «список». В зависимости от реализации списка позиция элемента может быть задана целым числом, показывающим номер элемента или указателем на элемент списка при использовании динамической памяти.
Реализация списка с использованием массива.
Недостатки: ограниченная длина списка; необходимость перемещения элементов части списка при вставке или удаления элемента. Элементы списка располагаются в смежных ячейках массива, что позволяет легко просматривать список и вставлять элемент в его конец. Но вставка или удаление элемента в середине списка требует перемещение всех последующих элементов в 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;
Удалить элемент списка L из позиции p
Procedure DEL( p:position; var L:List);
Var q:position;
Begin
If (p<1) or(p>L.Last) then ERROR(“Недопустимая позиция”);
If (p<L.Last) then
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, которая обозначает «пустой адрес». Переменная типа «указатель» определяет адрес динамической переменной. Для описания указателей в программах на Pascal используется след-я конструкция:
Type
mas=array[1..10] of integer;
Var
pi:^integer;
pr:^real;
pm:^mas;
Значение пустого адреса можно присвоить любому указателю. Выделение памяти для динамической переменной производится процедурой NEW(указатель). Эта процедура резервирует необходимый объем памяти, адрес которого сохраняется в указателе. Освобождение памяти после использования –процедура Dispose(указатель).
Список организованной динамической памяти можно представить:
Head
next
a1
next
a2
next
an
NIL
….
Описание абстрактного типа данных «список» имеет вид:
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.
Рассматриваемый тип данных список показывает пример реализации однонаправленного списка, в котором указатель позволяет определить только следующий элемент, но не предыдущий. Недостатком применения указателей является то, что они затрудняют обращение к элементам списка по их номеру и их не рекомендуется использовать при частых вставках и удалениях элементов.
АТД Стек
Стек – специальный тип списка, в котором все вставки и удаления элемента выполняются с одного конца списка, называемого вершиной стека. Обозначается LIFO(Last int –First out). Для работы с типом данных стек обычно используют следующие операторы:
MAKENULL(S) - Создать пустой стек S.
PUSH(x,S) - Вставить элемент x в вершину стека S.
ELEM(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.
В отличии от стека реализация очереди в динамической памяти с помощью типа данных «список» не отличается высокой эффективностью. Выделяют 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;