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

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

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.

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

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

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

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