- •Тема 1. Стеки, очереди, деки 7
- •Тема 2. Односвязные и двусвязные линейные списки 21
- •Тема 3. Бинарные деревья 40
- •Тема 4. Графы 65
- •Введение
- •Терминология
- •Классификация структур данных по различным признакам
- •Типовые операции над структурами данных
- •Эффективность алгоритмов. O-обозначения
- •Тема 1. Стеки, очереди, деки
- •Операции над стеком
- •Реализация стека
- •Реализация основных операций над стеком
- •Использование стека для преобразования форм записи выражений.
- •Очередь
- •Операции над очередью
- •Операции над деком
- •Реализация очереди и дека
- •Реализация основных операций над очередью и деком
- •Итератор
- •Лабораторная работа 1. Стеки, очереди, деки
- •Тема 2. Односвязные и двусвязные линейные списки
- •Линейный список
- •Операции над линейным списком
- •Реализация линейного списка в виде односвязной динамической структуры
- •Реализация основных операций над односвязным списком
- •Циклический список
- •Операции над циклическим списком
- •Односвязная реализация циклического списка
- •Реализация основных операций над односвязным циклическим списком
- •Реализация линейного списка в виде двусвязной динамической структуры
- •Реализация основных операций над двусвязным списком
- •Циклический двусвязный список
- •Реализация основных операций над двусвязным циклическим списком
- •Лабораторная работа 2. Односвязные и двусвязные линейные списки
- •Тема 3. Бинарные деревья
- •Основные понятия и определения
- •Построение бинарного дерева
- •Операции над бинарным деревом
- •Реализация бинарного дерева
- •Реализация основных операций над бинарным деревом
- •Дерево выражения
- •Дерево поиска
- •Операции над деревом поиска
- •Реализация дерева поиска
- •Реализация операций над деревом поиска
- •Сбалансированные деревья
- •Включение в сбалансированное дерево
- •Лабораторная работа 3. Бинарные деревья
- •Тема 4. Графы
- •Основные понятия и определения
- •Граф g7
- •Операции над графом
- •Реализация графа
- •Реализация основных операций над ориентированным графом
- •Обход ориентированного графа
- •Вычисление расстояния между узлами ориентированного графа
- •Лабораторная работа 4. Ориентированные графы
- •Библиографический список
-
Реализация основных операций над односвязным циклическим списком
Включение элемента в начало циклического списка:
procedure tCircleList.InsertHead(v:tValue);
var
NewItem: pItem;
begin
NewItem:= New(pItem); // выделение памяти под новый элемент списка
NewItem^.Value:= v;
if Empty
then begin // включение в пустой список
NewItem^.Next:= NewItem;
fHead:= NewItem; end
else begin // включение в непустой список
NewItem^.Next:= fHead^.Next;
fHead^.Next:=NewItem
end;
Inc(fSize); // увеличение числа элементов списка на 1
end; // procedure tCircleList.InsertHead
Включение элемента в конец циклического списка. При реализации метода можно использовать следующий прием – включить элемент в начало списка, а затем перенести указатель последнего элемента на включенный (следующий за ним) элемент:
procedure tCircleList.InsertRear(v: tValue);
begin
InsertHead(v); // включение элемента в начало
// Перенос указателя последнего элемента на следующий элемент:
fHead:= fHead^.Next;
end; // procedure tCircleList.InsertRear
Исключение элемента из начала циклического списка выполняется по той же схеме, что и исключение элемента из стека или очереди. Если исключается единственный элемент списка, то после исключения список должен стать пустым.
function tCircleList.DeleteHead: tValue;
var
DisItem: pItem;
begin
DisItem:= fHead^.Next; // исключаемый элемент - первый
DeleteHead:= DisItem^.Value; // чтение первого элемента списка
if fHead=DisItem // если в списке был один элемент,
then fHead:=nil // то после исключения список пуст,
else fHead^.Next:= DisItem^.Next; // иначе первым становится второй эл-т.
Dispose(DisItem); // удаление из памяти исключаемого элемента
Dec(fSize); // уменьшение числа элементов списка на 1
end; // function tCircleList.DeleteHead
Исключение элемента из конца циклического списка. Поскольку список является циклическим, то можно применить следующий прием. Сначала передвинуть указатель последнего элемента списка fHead на предшествующий ему элемент (предварительно определив указатель на этот элемент). При этом бывший последний элемент (который и нужно исключить) становится первым. Этот элемент можно исключить из списка с использованием метода исключения из начала DeleteHead.
function tCircleList.DeleteRear: tValue;
var
Item: pItem;
begin
// Перемещение указателя Item на предпоследний элемент списка
Item:= fHead;
while Item^.Next<>fHead do Item:=Item^.Next;
fHead:= Item; // сдвиг fHead на предпоследний элемент
DeleteRear:= DeleteHead;
end; // function tCircleList.DeleteRear
Операции исключения элементов из списка tCircleList.DeleteHead и tCircleList.DeleteRear неприменимы к пустому списку, поэтому перед их выполнением необходимо анализировать признак «список пуст».
Сцепление циклического списка с другим циклическим списком CList2 (подключение списка CList2 справа).
При реализации этой операции в виде метода класса tCircleList в метод Concat циклического списка необходимо передавать не указатель на первый элемент второго списка, а указатель на сам подсоединяемый список (CList2). При этом в методе нужно избежать прямого обращения к полям fHead и fSize класса CList2. Для обеспечения доступа к этим полям по чтению и записи в классе tCircleList свойства Head и Size должны быть доступны не только по чтению, но и по записи.
Метод класса tCircleList, реализующий сцепление описываемого списка с другим списком, реализуется следующим образом:
procedure tCircleList.Concat(var CList2: tCircleList);
var
Head2, // указатель на начало второго списка
Item: pItem; // указатель на элемент списка
begin
Head2:=CList2.Head; // получение указателя на начало второго списка
Item:= fHead^.Next; // сохранение указателя на начало общего списка
fHead^.Next:= Head2^.Next; // включение списка с указ. Head2 справа
fHead:= Head2; // перемещение fHead на последний элемент
fHead^.Next:= Item; // восстановление связи с первым элементом
fSize:=fSize + CList2.Size; // вычисление размера общего списка
CList2.Head := nil; CList2.Size := 0; // список CList2 становится пустым
end;//tCircleList.Concat
Если в приведенном выше методе исключить операцию перемещения указателя fHead на последний элемент включенного списка (fHead:= Head2), то список CList2 будет включен в список tCircleList слева.