Var
prt: ^ТипЯчейки
Постфикс в виде символа «^», в Pascal используется как оператор разыменования, т.е. выражение prt ^ обозначает значение (типа ТипЯчейки) в ячейке, указанной prt.
7. АТД Список.
В математике список представляет собой последовательность однотипных элементов, упорядоченных определённым образом, который может содержать повторные элементы. Количество элементов (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.
8. Реализация списков посредством массивов.
Недостатки: ограниченная длина списка; необходимость перемещения элементов части списка при вставке или удаления элемента.
Элементы списка располагаются в смежных ячейках массива, что позволяет легко просматривать список и вставлять элемент в его конец. Но вставка или удаление элемента в середине списка требует перемещение всех последующих элементов в 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 (p<1) or(p>L.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;
9. Реализация списков посредством указателей
Чтобы исключить недостатки реализации списка с использованием массивов каждый элемент списка размещается в динамической памяти и дополняется указателем на следующий элемент. При этом требуется дополнительная память.
Все переменные массивов, описываемые в разделе 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;
Рассматриваемый тип данных список показывает пример реализации однонаправленного списка, в котором указатель позволяет определить только следующий элемент, но не предыдущий.
10. Дважды связанные списки.
Существуют двунаправленные списки, в которых ячейка содержит 2 указателя, на следующий и на предыдущий элемент. При такой организации проще просматривать список в двух направлениях: прямом и обратном. Здесь в качестве позиции элемента может использоваться указатель на ячейку, содержащую данный элемент.
Недостатком применения указателей является то, что они затрудняют обращение к элементам списка по их номеру и их не рекомендуется использовать при частых вставках и удалениях элементов.
11. Циклические списки.
Линейные списки характерны тем, что в них можно выделить первый и последний элементы, причем для однонаправленного линейного списка обязательно нужно иметь указатель на первый элемент.
Циклические списки также как и линейные бывают однонаправленными и двунаправленными. Основное отличие циклического списка состоит в том, что в списке нет пустых указателей.
Рис.1.3. Однонаправленный циклический список
Последний элемент списка содержит указатель, связывающий его с первым элементом. Для полного обхода такого списка достаточно иметь указатель только на текущий элемент.
В двунаправленном циклическом списке система указателей аналогична системе указателей двунаправленного линейного списка.
Рис.1.4. Двунаправленный циклический список
Двунаправленный циклический список позволяет достаточно просто осуществлять вставки и удаления элементов слева и справа от текущего элемента. В отличие от линейного списка, элементы являются равноправными и для выделения первого элемента необходимо иметь указатель на заголовок. Однако во многих случаях нет необходимости выделять первый элемент списка и достаточно иметь указатель на текущий элемент.
12. АТД Стек.
Стек – специальный тип списка, в котором все вставки и удаления элемента выполняются с одного конца списка, называемого вершиной стека. Обозначается LIFO (Last int –First out).
Стек может быть реализован, как частный случай списка. Для этого надо объявить переменную S как переменную типа «список». Тогда первый оператор будет реализован одноимённой функцией для списка.
13. Реализация стеков посредством указателей.
14. Реализация стеков посредством массивов.
Используется подход, в котором изменяется расположение первого (верхнего) элемента стека. Элемент вершины стека обозначается специальной переменной top. Реализацию стека с помощью массива можно представить след-м образом:
const
maxlen=100;
type
Stack=record;
element:array[1..maxlen] of el_type;
top:integer;
end;
15. АТД Очередь.
Очередь вляется особым видом списка, в который элементы добавляются с одного конца, а выбираются с другого конца. Обозначается: FIFO.
16. Реализация очередей посредством указателей.
17. Реализация очередей посредством циклических массивов.
Предполагается подход, где массив рассматривается как циклическая структура данных, в которой за последним элементом идет первый элемент массива.
Пусть имеется некоторый массив: 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;
18. АТД Дек.
Рассмотрим структуры данных, напоминающие очереди, но в которых добавление и удаление элементов может осуществляться как в начало, так и в конец. Подобный усовершенствованный вариант очереди называется двунаправленной очередью, или деком (deque — double-ended queue — очередь с двумя концами).
19. Деревья – основная терминология.
Дерево — одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Является связанным графом, не содержащим циклы. Большинство источников также добавляют условие на то, что рёбра графа не должны быть ориентированными. В дополнение к этим трём ограничениям, в некоторых источниках указываются, что рёбра графа не должны быть взвешенными.
· Корневой узел — самый верхний узел дерева.
· Корень — одна из вершин, по желанию наблюдателя.
· Лист, листовой или терминальный узел — узел, не имеющий дочерних элементов.
· Внутренний узел — любой узел дерева, имеющий потомков, и таким образом, не являющийся листовым узлом.
20. АТД Дерево.
Дерево — это абстрактный тип данных (АТД) для иерархического хранения элементов. За исключением элемента во главе дерева, каждый элемент структуры имеет родителя {parent element) и ноль или более дочерних элементов {children element). Для придания древовидной структуре большей наглядности ее элементы изображаются в виде овалов или прямоугольников, а связи между ними — в виде прямых линий (рис. 6.2). Обычно головной элемент дерева называется корнем (root% хотя он является самым верхним элементом структуры, а остальные расположены под ним (в отличие от обычного, биологического дерева).
21. Обходы деревьев
Существует достаточно много алгоритмов работы с древовидными структурами, в которых часто встречается понятие обхода (traversing) дерева или "прохода" по дереву. При таком методе исследования дерева каждый узел посещается только один раз, а полный обход задает линейное упорядочивание узлов, что позволяет упростить алгоритм, так как при этом можно использовать понятие "следующий" узел. т.е. узел стоящий после данного при выбранном порядке обхода.
Существует несколько принципиально разных способов обхода дерева:
Обход в прямом порядке
Каждый узел посещается до того, как посещены его потомки.
Для корня дерева рекурсивно вызывается следующая процедура:
Посетить узел Обойти левое поддерево Обойти правое поддеревоПримеры использования обхода:
· решение задачи методом деления на части
· разузлование сверху
· стратегия "разделяй и властвуй" (Сортировка Фон Hеймана, быстрая сортировка, одновременное нахождение максимума и минимума последовательности чисел, умножение длинных чисел).
Симметричный обход
Посещаем сначало левое поддерево, затем узел, затем - правое поддерево.
Для корня дерева рекурсивно вызывается следующая процедура:
Обойти левое поддерево Посетить узел Обойти правое поддерево