Лекция № 23. Динамические объекты – линейные списки

Фундаментальной структурой в ОП следует считать массивы, но они имеют недостаток – память под массив выделяется в полном объеме от начала и до конца выполнения программы, размеры памяти, как известно, ограничены. Файлы предоставляют уникальные возможности обработки больших объемов информации, но работа с файлом выполняется медленно.

В поисках решения этих проблем были предложены динамические структуры данных. Они характеризуются следующими особенностями:

- Для отдельных элементов структуры память выделяется в тот момент, когда в них появляется необходимость (а не всем элементам сразу);

- Число элементов динамической структуры заранее не объявляется и может изменяться от нуля до некоторого значения, определяемого объемом памяти или спецификой задачи;

- Память, занимаемая структурой, не представляет непрерывную область, т.е. элементы структуры могут быть разбросаны в памяти хаотически;

- Логическая последовательность элементов задается в явном виде с помощью указателей, хранящихся в самих элементах. Каждый элемент, кроме своего значения, хранит указатель на следующий элемент или на два соседних элемента.

Рассмотрим наиболее распространенную динамическую структуру – связанный список.

Связанный список – это такая структура данных, элементами которой служат записи одного и того же формата, связанные друг с другом с помощью указателей, расположенных в самих элементах. Элементы списка называют узлами.

Каждый элемент списка состоит из двух различных по назначению частей: содержательной (информационной) и указующей. В содержательной части хранятся данные. Если указующая часть хранит адрес одного соседнего элемента, то такой список называется односвязным, или однонаправленным. Поле указателя последнего элемента содержит специальный признак NIL (признак конца списка). Для каждого элемента (кроме последнего) имеется единственный следующий элемент, поэтому связанные списки иногда называют линейными. В случае, когда в указующей части хранятся адреса и предыдущего, и следующего элементов, список называется двусвязным или двунаправленным.

 

Сегмент данных   Указатель на первый элемент

Динамически распределяемая память .... инфор- указующ- мацион- ая часть ная часть

nil

 

 

Структура односвязного списка

 

С линейными списками можно выполнять те же действия, что и с одномерными массивами. Типовые действия со списками:

1. добавить новый узел перед заданным узлом;

2. удалить заданный узел;

3. объединить два или более линейных списка в один список;

4. разбить линейный список на два или более списка;

5. сделать копию списка;

6. выполнить сортировку узлов списка в возрастающем порядке по некоторым полям в узлах;

7. найти в списке узел с заданным значением в некотором поле;

очень часто встречаются линейные списки, в которых добавление и удаление производится только в первом и последнем узлах. Это следующие списки:

1. стек – линейный список, в котором все добавления и удаления делаются в одном конце списка;

2. очередь – линейный список, в котором все добавления производятся на одном конце списка, а все удаления делаются на его другом конце;

3. дек – линейный список, в котором все добавления и все удаления делаются на обоих концах списка.

Действия со связанными списками

 

Прежде, чем рассматривать действия над связанными списками, введем обозначения переменных, которыми будем пользоваться при описании соответствующих алгоритмов и структур данных.

· item, pitem – тип для одного элемента списка и указатель на него;

· data – поле данных (информационная часть списка);

· next, prev – указатели следующего, предыдущего элементов (указующая часть);

· head, top – указатели на первый и последний элемент списка;

· p1, p2 – рабочие указатели.

Опишем тип одного элемента односвязного линейного списка и указателя на этот элемент:

Type

pitem = ^item;

item = record

data:... { простой или определяемый пользователем тип }

next: pitem; { или prev: pitem}

end;

Наиболее просто реализуются действия со стеком. Все действия со стеком реализуются на одном конце, который называется вершиной стека. Стеки как структуры данных имеют широкое применение в системном программировании, например, при разработке компиляторов. Область памяти, в которую помещаются локальные переменные и параметры подпрограмм, имеет структуру стека. Благодаря устройству стека возможны такие приемы программирования, как вложенные подпрограммы и рекурсия.

Начало списка

Добавление

элемента

 

Удаление

элемента

 

Схема списка – стека.

Стек представляет собой частный случай списка, доступ к которому возможен только в корневой точке. Добавление или удаление элемента производится вначале списка. Стек иногда обозначают аббревиатурой LIFO – Last In First Out – "последний вошел – первый вышел". Это сокращение правильно передает механизм работы стека.

Очередь, как и стек, является частным случаем списка. Доступ возможен только к первому и к последнему элементам очереди. Данные могут быть добавлены в конец очереди и удалены из ее начала. Элемент, который был добавлен в очередь первым, первым достигнет ее начала. Английское обозначение такой структуры данных – FIFO, т.е. First In First Out – "первым вошел – первым вышел".

Начало списка

 

Добавление элемента Удаление элемента

 

 

Схема списка – очереди.

 

Как и для стека, для очереди определены операции добавления элемента в список и удаление из очереди.

type

pitem = ^item;

item = record

data: integer;

prev: pitem;

end;

var

top, p: pitem;

n, k: integer;

procedure add(x:integer); {процедура добавления элемента на вершину стека}

begin

new(p); {выделение памяти; создаем произвольный элемент p}

p^.data:= x; {присвоение полям записи значений, т.е. в адрес полей записи}

p^.prev:= top; { засылаются значения.}

top:= p; {устанавливаем р вершиной стека}

end;

procedure deltop; {процедура удаления узла с вершины стека}

begin

if top <> nil then {если стек не пустой}

begin

p:= top^.prev; {запоминаем предшествующей вершине элемент}

dispose(top);

top:= p; {устанавливаем р вершиной стека}

end;

end;

procedure writestack; {процедура вывода содержимого стека на экран}

begin

writeln('содержимое стека, начиная с вершины: ');

p:= top;

while p <> nil do

begin

write(p^.data,' ');

p:= p^.prev;

end;

writeln;

end;

begin {начало программы}

top:= nil;

for k:= 1 to 10 do

add(k); {заполняем стек числами от 1 до 10}

writestack;

writeln('введите значение элемента для добавления в стек');

readln(n); add(n);

writestack;

writeln('сколько элементов стека нужно удалить?');

readln(n);

for k:= 1 to n do deltop;

writestack;

readln;

end.

Лекция № 24. Динамические объекты сложной структуры. Деревья: основные понятия.

Дерево представляет собой совокупность элементов с иерархической структурой. Дерево состоит из узлов, причем один начальный узел играет особую роль. Он называется корнем или корневым узлом. Узлы дерева связаны между собой отношениями. У каждого узла есть узел-предок и некоторое число узлов-потомков. Корень представляет собой особый случай. Такие структуры данных встречаются в повседневной жизни (например, генеалогическое дерево). Используются деревья и в компьютерной науке. Например, при компиляции программы строится дерево синтаксического анализа. Существуют разные способы реализации деревьев. Часто при реализации деревьев каждый узел имеет несколько указателей на несколько узлов. Если указателей два (правый и левый), то такое дерево называется бинарным. Один из указателей может быть равен NIL.

У корневого узла нет входящих в него ветвей, а есть только исходящие. Вершина, на которую имеется указатель из другой вершины, называется потомком этой вершины, а значит вершина, имеющая указатель на вершину-потомка, называется вершиной предком. Если вершина не имеет потомков, она называется терминальной вершиной.

 

 

nil

nil

nil

nil

 

 

Схема бинарного дерева.

В бинарном дереве целочисленных значений обычно во всех левых вершинах должны находиться меньшие числа, а в правых – большие.

Основные операции над деревьями – это занесение элемента в дерево, удаление элемента из дерева и обход дерева.