 |
Разновидности связанных списков
|
|
|
|
В оставшейся части методических указаний рассматриваются только связанные списки. Связанный список (или цепной список) - список данных, в котором рорядок элементов задан посредством указателей включенных в элементы списка. Самой простой разновидностью связанных списков является линейный связанный список. Линейный связанный список - это конечный набор пар, каждая из которых состоит из информацион-ной части и указывающей части. Каждая пара называется узлом (Node) списка. По числу связей различают списки с одной связью и списки с двумя связями.
Список с одной связью (или однонаправленный список) состоит из узлов, каждый из которых имеет один указатель: ссылку на следующий узел. Объявление узла одно-направленного списка должно следовать следующей схеме:
TYPE{ Должен быть объявлен Некоторый_тип }
Указатель_на_узел = ^ Узел;
Узел = RECORD
Информация: Некоторый_тип;
Следующий: Указатель_на_узел;
END;
VAR Заголовок: Указатель_на_узел;
Здесь Узел представляет собой запись с двумя полями: поле Информация предназначено для хранения данных, тип которых определяет пользователь, а поле Следующий содержит ссылку на запись типа Узел. Последний узел должен содержать nil в поле Следующий. По этому признаку определяется конец списка. Последовательность объявлений типов существенна. Объявление типа Узел должно следовать за объявлением типа Указатель_на_узел. Переменная Заголовок содержит либо ссылку на первый эле-мент списка, либо nil, если список пуст.
К характерным особенностям обработки списков с одной связью относятся следующие:
- обход списка наиболее просто выполняется в порядке от первого узла к последнему;
- для посещения каждого узла используется переменная Текущий типа
|
|
|
- Указатель_на_узел;
- вставка нового узла и удаление узла наиболее просто выполняется со стороны головы списка;
- вставка нового узла в середину списка всегда требует ссылку на узел, после которого буде размещен новый. Аналогично для удаления узла из середины списка всегда необходима ссылка на узел, предшествующий удаляемому.
В качестве примера приводятся объявления для работы с однонаправленным списком, содержащим некоторые сведения о студенте.
type Student = record
Name: string [20]; Age: Integer; Group: string [10];
end;
NodePtr = ^Node;
Node = record
Info: Student;
Next: NodePtr;
end;
var List: NodePtr; { Заголовок определяет список }
Чтобы упростить доступ к узлам однонаправленного списка и унифицировать алгоритмы обработки узлов списка вводят изменения в объявления узла списка и заголовка в соответствии со схемой:
TYPE Указатель_на_некоторый_тип = Некоторый_тип;
{ Должен быть объявлен Некоторый_тип }
Указатель_на_узел = ^ Узел;
Узел = RECORD
Информация: Указатель_на_некоторый_тип;
Следующий: Указатель_на_узел;
END;
Заголовок = RECORD
Первый: Указатель_на_узел;
Последний: Указатель_на_узел;
Длина_списка: Longint; { Счетчик числа узлов списка }
END;
Здесь поле Информация содержит ссылку на хранимые данные, тип которых определяет пользователь, что делает узел слабо зависимым от данных. В результате этого унифицируются основные алгоритмы обработки списков. Объединение указателей на первый узел и последний узел в тип данных запись и включение в нее текущей длины списка позволяет передавать весь агрегат в качестве параметра процедурам и функциям обработки списков. Пример объявлений для для работы с однонаправленным списком, содержащим некоторые сведения о студенте может принять вид
type StudentPtr = ^Student;
Student = record
Name: string [20]; Age: Integer; Group: string [10];
end;
NodePtr = ^Node;
Node = record
Next: NodePtr;
Down: StudentPtr; { Раньше здесь хранились данные о студенте }
|
|
|
end;
ListPtr = ^List;
List = record { Заголовок определяет список }
First, Last: NodePtr;
Count: Longint;
end;
Для рассматриваемого примера предикат Null и функция Length имеют такой простой вид
function Null(L: List): Boolean;
Begin
Null:= L.Count=0;
end;
function Length(L: List): Longint;
Begin
Length:= L.Count;
end;
Незначительные изменения способа связывания узлов списка, заключающиеся в том, что поле Следующий последнего узла содержит ссылку на первый узел списка, а поле Предыдущий первого узла содержит ссылку на последний узел списка, дают важ-ную разновидность связанных списков - циклические или кольцевые списки. Узлы кольцевого списка объявляются точно так же, как узлы линейного списка.
В кольцевых списках эффективно реализуются некоторые важные операции, такие, как "очистка" списка и "расщепление" списка на подсписки.
Приемы программирования по работе со списком.
Создание пустого списка.
Под пустым списком следует понимать служебную структуру данных типа запись, содержащую поля указателей на начало и конец линейного списка, а также поле-счетчик узлов этого списка. При этом поля указателей еще не содержат конкретный адрес узла начала и узла конца списка, а лишь проинициализированы безадресным значением nil. В свою очередь поле-счетчик содержит значение 0.
type List= record
head:PtrNode; { указатель начала списка }
tail:PtrNode; { указатель конца списка }
count:integer;
end;
Графически это можно представить как показано на рис.3.1.
 |
|
 |
nil nil
Рис.3.1
Как следует из раздела 2, каждый узел однонаправленного линейного списка содержит один указатель на следующий узел. В последнем узле списка указатель на следующий узел содержит значение nil. Для реализации этих целей используем следующие структурные построения данных:
type PtrStud=^student;
student= record { информационная запись }
name: string [20]; age:integer; group: string [10]
end;
PtrNode=^node;
node= record
info:student;
next:PtrNode; и на последующие узлы списка }
end;
List= record
head:PtrNode;
tail:PtrNode;
count:integer;
end;
Proc= procedure(x:ptrnode);
Для построения списка следует выполнить итерационную процедуру связывания структурированных узлов, посредством инициализации поля next:
var current:ptrnode; {указатель на текущий узел}
listfile:file of student;
list0:list;
file_name:string;
procedure create_list;
|
|
|
begin
reset(listfile);
{1} new(current); {выделена память под первый узел списка}
read(listfile,current^.info); {чтение из файла информации
по первому студенту в узел 1}
list0.count:=1;
list0.head:=current; {указатель начала списка поставлен на
текущий первый узел}
while not eof(listfile) do
begin
{3} new(current^.next);{выделить память для следующего узла
по адресу, записанному в поле next текущего узла}
read(listfile,current^.next^.info);
inc(list0.count);
{5} current:=current^.next;{сделать следующий(второй) узел текущим (перемещаем указатель current на следующий узел)}
end;
list0.tail:=current;{указатель конца списка ставим на
последний узел}
current^.next:=nil;{поле next последнего узла списка
принимает значение nil}
close(listfile);
readln;
end;
На рис.3.2 графически интерпретированы действия операторов программы.
| |||||
 | |||||
 | |||||
|
{3}
 |  |
|
{5}
 |  |
 |
Рис.3.2
Процедуру построения списка следует дополнить процедурой инициали-зации указателей начала и конца списка и счетчика узлов.
procedure init_list;
begin
list0.head:=nil; list0.tail:=nil; list0.count:=0;
end;
|
|
|
