Разновидности связанных списков

В оставшейся части методических указаний рассматриваются только связанные списки. Связанный список (или цепной список) - список данных, в котором рорядок элементов задан посредством указателей включенных в элементы списка. Самой простой разновидностью связанных списков является линейный связанный список. Линейный связанный список - это конечный набор пар, каждая из которых состоит из информацион-ной части и указывающей части. Каждая пара называется узлом (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.

tail: =nil;

 

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 графически интерпретированы действия операторов программы.

		current

current

{1} {3}

 

 

 

current

{5}

 

 

 

Рис.3.2

Процедуру построения списка следует дополнить процедурой инициали-зации указателей начала и конца списка и счетчика узлов.

procedure init_list;

begin

list0.head: =nil; list0.tail: =nil; list0.count: =0;

end;

⇐ Предыдущая123

Поделиться:

Популярное:

1. Авторитарный режим неоднороден по своему характеру. В литературе выделяют деспотический, тиранический, военный и иные разновидности авторитарного режима.
2. Алгоритм списков в динамической памяти
3. Договор ренты и его разновидности.
4. Исполнительные органы. Передаточные функции исполнительных органов. Клапаны, их разновидности. Позиционеры и их назначение
5. Использование стихотворного текста в качестве опорных списков
6. Криминологическая характеристика преступлений, связанных с незаконной торговлей оружия.
7. Объекты маркетинга: виды и разновидности потребностей и спроса
8. Понятие криминалистической характеристики преступлений, связанных с незаконным оборотом наркотических средств и её элементы
9. Правовое регулирование -определенная форма воздействия права на общественные отношения с целью их урегулирования (упорядочения) с помощью взаимосвязанных юридических средств.
10. Предтечи, разновидности, последователи
11. Проект — комплекс взаимосвязанных целенаправленных мероприятий, проводимых при ограниченных временных, финансовых, трудовых и материальных ресурсах.
12. Процессуальный порядок разрешения вопросов, связанных с исполнением приговора