Реализация АТД (Абстрактный тип данных). Линейный список

Согласно определению реализация должна обеспечивать упорядоченность элементов (упорядоченного следования одного c другим). Либо тоже самое по порядковому номер, а не в смысле возрастания или убывания. Что может быть реализовано двумя способами:

1. Последовательное распределение элементов в памяти, когда элементы располагаются физически друг за другом без пропусков, тем самым очередность следования определяется местом в памяти. Пример – массив.
2. Связанные распределение - элементы в памяти располагаются в произвольном (определенном) порядке, однако каждый элемент кроме значения имеет специальное поле. Поле - поле связи, в значение которого есть физический адрес в порядке обхода элемента. ИЗ определения следует, что и первый элемент может располагаться в произвольном порядке. Поэтому необходимо специальная ячейка, которая называется головой списка, содержащая адрес первого элемента линейного связанного списка (ЛСС).

Таким образом, структура элемента линейного связанного списка, в общем, состоит из двух частей: информационной и поля связи.

информацион. поля связи

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

1. Однонаправленный линейный связанный список

Tuzel = record { неверно }

Info: anytype

Next: ^tuzel;

End;

Prev INFO Next

1. Двунаправленный список, 2 поля связи.

Tuzell = record

Info1,...., infomLanytype;

Next,prev:^tuzel { неверно }

End;

2

Xk-1 Xk Xk+1

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

1. Var head, tail:^tuzee;

head

1

teal

2

Множественными связками, если дан линейный список данных студентов группы с Ф.И.О., то тогда первое поле связи может обеспечивать получения списка в порядке зачисления студентов в группу. Такую очередность обхода, чтобы список оказался отсортированным по фамилиям, третье форма связи аналогично по имени, а четвертое поле может включать в себя только отличников.

По структуре организации линейного связанного списка списки делятся на:

- концевые, в таких списках последний элемент специальным образом обозначается, а точнее обычно в поле связи записывается

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

В кольцевой структуре: в отличие от признака конца (null), в кольцевом списке признаком завершения обхода является совпадение адресов начала обхода. Одиночный обход завершается, если адрес текущего элемента совпадает с адресом начала обхода.