Связанные структуры.. Реализация связанных структур данных с использованием массивов.. Простой связанный список (List).

20. Связанные структуры.

В Паскале все типы данных являются статическими. Простые типы данных занимают отдельные ячейки памяти, структурированные типы – группы ячеек. Число ячеек памяти отведенных под структуру определенного типа данных заранее фиксировано, мы не можем управлять размерностью этих структур. Примером динамического типа данных являются файлы, так как мы можем управлять размером файла.

Многие задачи будут решаться более эффективно, а некоторые – единственно возможно при динамическом управлении памятью.

20.1. Реализация связанных структур данных с использованием массивов.

Массив – структура данных, которая позволяет произвольный доступ к своим ячейкам. Мы не можем управлять размещением элементов массива, но можем организовать варианты обхода массива в произвольном порядке и использовать эту возможность, например, для задач сортировки.

В задачах сортировки приходится выполнять следующие действия (или/или):

Переставлять записи в памяти

Присваивать записям номера

Организовывать записи связанные в списки

Последний способ является наиболее эффективным в том случае, если число записей достаточно большое, а поля ключей (ключ – то, что определяет порядок записи в сортировке) составляют малую часть от всей длины записи.

20.1.1 Простой связанный список (List).

CONST

NameLen = 7;

AddrLen = 25;

Max = 4;

TYPE

Month = (Jan, Feb, Mar, Apr, May, un, Jul, Aug, Sep, Oct, Nov, Dec);

Sex = (Male, Female);

Date = RECORD

Mo: Month;

Day: 1 .. 31;

Year: INTEGER;

END;

Person = RECORD

Name: STRING[NameLen];

Addr: STRING[Addrlen];

Birth: Date;

VSex: Sex;

Next: 0 .. Max;

END;

VAR

PRecs: ARRAY [1 .. Max] OF Person;

First: 0 .. Max;

Переменная First указывает на индекс записи, которая считается первой.

В поле Next каждой записи заносится индекс следующей записи.

В поле Next последней записи заносится значение 0;

Index	PRecs[Index].Next	PRecs[Index].Name	Номер в списке
		Miller
		Smith
	2	Plane
		Jones

Итерация по списку.

Index := First;

WHILE Index <> 0

BEGIN {Обход массива в алфавитном порядке с помощью Index}

...

Index := PRecs[Index].Next;

END;

Порядок обхода массива с помощью поля Next визуализирован на следующем рисунке.

Таким образом мы можем рассматривать массив как упорядоченную структуру, где порядок задается указателями обхода First и Next.

Структуры, в которых каждая запись содержит указатель на следующую называется связанным списком. Последовательность записей в связанном списке может быть изменена с помощью указателей без физического перемещения элементов списка. Элементы могут быть добавлены к списку без изменения связей для большинства из существующих записей.

Добавляется новая запись

Index	PRecs[Index].Next	PRecs[Index].Name	Номер в списке
		Miller
		Smith
		Plane
		Jones
		Rush

PRecs[5].Next = PRecs[3].Next

PRecs[3].Next = 5

Любая запись в связанном списке может быть удалена с помощью одного присвоения.

12 3 4 Следующая ⇒