Материал: Лабораторная работа №10 Односвязные списки, Поиск, Сортировка
Лабораторные работы по информатике для специальности «Моделирование и исследование операций в организационно-технических системах»
Лабораторная работа №10 Динамические структуры данных. Односвязные списки.
Введение
В данной лабораторной работе рассмотрены односвязные списки. Дана структура для описания узлов односвязных списков. Рассмотрены основные алгоритмы работы со списками, такие как вставка и удаление узлов, поиск узлов, сортировка и др. Рассмотрен пример создания модуля для работы с односвязными списками. Рассмотрены некоторые примеры применения односвязных списков.
Динамические структуры данных
Динамическими структурами данных называют структуры данных размер и количество элементов которых может изменяться во время работы программы. Существует большое количество динамических структур данных. Примером таких структур могут служить списки и деревья. Рассмотрим одну из наиболее распространенных структур данных – списки.
Односвязные списки
Односвязный список представляет собой цепочку элементов, называемых узлами. При этом каждый элемент содержит указатель, указывающий на следующий элемент в этом списке.
n
Рисунок 1 – Узел односвязного списка
Для получения доступа ко всем элементам списка достаточно знать первый узел списка, от которого, путем переходов по ссылкам можно обойти все остальные узлы.
|
n |
|
|
|
n |
|
|
|
|
n |
|
|
nil |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рисунок 2 – Односвязный список |
|
|
|
|
|||||||
В отличие от массива узлы списка могут располагаться в различных участках памяти, а их порядок определяется ссылками. Таким образом размер списка ограничен лишь свободным объемом памяти. Недостатками списка является большое количество обращений к памяти при переборе элементов списка, как следствие, меньшее быстродействие при чтении списка. Достоинством списка является простота и высокая скорость вставки или удаления элемента из списка.
Конец списка обычно помечается пустым указателем nil или ссылка последнего узла указывает на первый узел, в этом случае список называется кольцевым.
n |
n |
n |
Рисунок 3 – Кольцевой односвязный список
Узлы связного списка
Описание узлов односвязного списка приведено ниже
Лабораторные работы по информатике для специальности «Моделирование и исследование операций в организационно-технических системах»
//Описание структуры узла
type PNode=^TNode; //указатель на узел TNode=record
next:PNode; //указатель на следующий узел data:pointer;//указатель на данные узла end;
Узел может либо непосредственно содержать данные, либо содержать указатель на данные.
Для перехода по ссылке можно использовать примерно следующий код
var NextNode, CurrentNode:PNode; begin
...
NextNode:=CurrentNode^.next;
Создание односвязного списка
В самом простом случае первый узел в связном списке описывает весь список. Первый узел называют головой списка.
var HeadNode:PNode;
Если HeadNode содержит nil значит списка еще нет. Таким образом список создается следующим образом
var HeadNode:Pnode=nil;
Вставка и удаление элементов в односвязном списке
Для односвязного списка существует только один вариант вставки нового узла в список – вставкам после указанного узла списка. Пошаговый алгоритм вставки нового элемента в список приведен на рисунке 4
Лабораторные работы по информатике для специальности «Моделирование и исследование операций в организационно-технических системах»
1) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
n |
|
|
nil |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
|
|
|
nil |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
|
n |
|
|
|
nil |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n
3)
|
n |
|
|
|
n |
|
|
n |
|
nil |
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
n
Рисунок 4 – Вставка нового узла в односвязный список
Подпрограмма реализующая данный алгоритм может выглядеть следующим образом.
function InsertBefore(var ANode:PNode; InsNode:PNode):PNode; begin
//если список не содержит узлов if ANode=nil then ANode:=InsNode
else //если вставляемый узел не пустой if InsNode<>nil then
begin InsNode^.next:=ANode^.next; ANode^.next:=InsNode;
end;{if InsNode} Result:=InsNode;
end;{InsertBefore}
Обратите что существует особый случай – это вставка перед первым узлом списка. В этом случае первым элементом в списке становится вставляемый элемент. Так как односвязный список задается своим первым элементом, то код для этого случая надо писать отдельно, например
var MyList:PNode=nil; //список InsNode:PNode
begin
...
MyList:=InsertBefore(InsNode, MyList);
...
Лабораторные работы по информатике для специальности «Моделирование и исследование операций в организационно-технических системах»
end.
Пошаговый алгоритм удаления узла из односвязного списка приведен на рисунке 5
1)
|
n |
|
|
|
n |
|
|
|
n |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
2)
|
n |
|
|
|
n |
|
|
|
|
n |
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3)
|
n |
|
|
|
n |
|
|
|
|
n |
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
nil
nil
nil
Рисунок 5 – Удаление узла из односвязного списка
Код удаления узла из списка может выглядеть следующим образом
function DeleteBefore(ANode:PNode):PNode; begin
if ANode<>nil then
if ANode^.next<>nil then //если удаляемый узел существует begin
Result:=ANode^.next;
ANode^.next:=ANode^.next^.next;
Result^.next:=nil; end{if ANode^.next}
else Result:=nil else Result:=nil; end;{DeleteBefore}
Здесь также существует особый случай, если удаляется первый элемент, он должен обрабатываться отдельно (не существует узел перед которым стоит первый узел), например так
var MyList:PNode=nil; //список Node:PNode
begin
...
Node:=MyList;
MyList:=MyList^.next;
Dispose(Node);
...
end.
Прохождение односвязного списка
Прохождение односвязного списка реализуется с помощью очень простого алгоритма: − вводится текущий узел;
Лабораторные работы по информатике для специальности «Моделирование и исследование операций в организационно-технических системах»
−текущему узлу присваивается первый узел списка;
−далее производится переход от узла к узлу с помощью указателей next. При этом для каждого узла может вызываться некоторая подпрограмма обрабатывающая данные содержащиеся в узле;
−процесс останавливается при достижении указателя nil.
Код реализующий данный алгоритм может выглядеть следующим образом
procedure ProcessList(AHead:PNode; ANodeProc:TProcessNode); begin
//обход списка начиная с первого узла while AHead<>nil do
begin
ANodeProc(AHead^.data); //процедура обработки данных узла
AHead:=Next(AHead); end;{while}
end;{ProcessList}
Поиск предшествующего узла в односвязном списке
Часто необходимо найти в списке узел, стоящий перед заданным узлом. Алгоритм поиска такого узла прост, необходимо осуществлять проход списка, начиная с первого элемента до тех пор, пока не будет найден узел указатель next которого, указывает на заданный узел. Пример реализации кода реализующего этот алгоритм приведен ниже.
function Prev(AHead, ANode:PNode):PNode; begin
Result:=nil;
//поиск узла указатель next которого равен ANode while AHead<>nil do
begin
if AHead^.next=ANode then begin
Result:=AHead;
break; end;{if}
AHead:=Next(AHead); end;{while}
end;{Prev}
Вставка перед заданным узлом
Для осуществления вставки элемента перед заданным узлом списка необходимо найти узел предшествующий заданному узлу списка, а затем выполнить вставку после этого узла. Обратите внимание, что здесь также существует особый случай, а именно вставка перед первым узлом.
Сортировка вставками
Продолжим рассматривать алгоритмы сортировки. Следующий алгоритм сортировки называется алгоритм сортировки вставками. Алгоритм сортировки заключается в следующем:
1.создаем пустой список, который будет содержать отсортированный список;
2.поиск «минимального» узла в исходном списке;
3.найденный узел удаляется из исходного списка и вставляется в отсортированный список;