Компонентный Паскаль/Связанный список: различия между версиями

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
Строка 32: Строка 32:


Пример такого списка:
Пример такого списка:
<source lang="oberon2">
TDblList = POINTER TO RECORD (* двусвязный список *)
first : POINTER TO TDblElem; (* первый элемент списка *)
end : POINTER TO TDblElem; (* последний элемент списка *)
len : INTEGER; (* длина списка *)
END;
</source>
Как видно из примера, управляющая структура совсем короткая. Даже короче, чем элемент двусвязного списка. Сам тип TDblList определён через указатель на структуру, поэтому переменную такого типа, можно создать динамически, что позволит сократить объём программы в виде исполняемого файла.

==== Вставка нового элемента ====
Вставку нового элемента в список рационально (но не обязательно) реализовать в форме метода объекта:
<source lang="oberon2">
<source lang="oberon2">



Версия от 13:21, 20 апреля 2015

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

Что такое список -- знают все из повседневной жизни. Это лист бумаги, который содержит пункты, например, того, что нужно купить в магазине. Аналога связанного списка[1] в жизни нет. С большой натяжкой связанным списком в жизни можно назвать алгоритм схемы в виде блок-схем[2]. В блок-схемах каждый последующий блок, связан с предыдущим. но в блок-схемам могут быть побочные связи, а в связанных списках их нет.

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

При использовании односвязного списка надо быть очень внимательным, чтобы цепочка не разорвалась, т. к. информация за разрывом будет потеряна. При двусвязных списках вероятность такого неприятного события сохраняется, но существенно ниже[3].

Пример использования двусвязного списка

Задача создания двусвязного списка разбивается на несколько простых подзадач.

Создание элемента двусвязного списка

Для начала создадим тип данных, соответствующей нашей задаче -- элемент двусвязного списка . Примерный код представлен ниже:

TYPE
	TDblElem = RECORD (* Элемент двусвязного списка *)
		value : INTEGER; (* полезная информация *)
		first : BOOLEAN;  (* признак первого элемента в списке *)
		Last  : BOOLEAN;  (* признак последнего элемента в списке *)
		backward: POINTER TO TDblElem; (* указатель на предыдущий элемент *)
		forward: POINTER TO TDblElem; (* указатель на следующий элемент *)
	END;

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

Элемент двусвязного списка не является указателем на запись, т. к. с применённым подходом нельзя было бы использовать указателя на тип "указатель на запись" (т.е. на самого себя).

Создание двусвязного списка

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

Пример такого списка:

TDblList = POINTER TO RECORD (* двусвязный список *)
	first : POINTER TO TDblElem; (* первый элемент списка *)
	end   : POINTER TO TDblElem; (* последний элемент списка *)
	len   : INTEGER;             (* длина списка *)
END;

Как видно из примера, управляющая структура совсем короткая. Даже короче, чем элемент двусвязного списка. Сам тип TDblList определён через указатель на структуру, поэтому переменную такого типа, можно создать динамически, что позволит сократить объём программы в виде исполняемого файла.

Вставка нового элемента

Вставку нового элемента в список рационально (но не обязательно) реализовать в форме метода объекта:

Примечания

  1. Связный список не единственная структура в подобном роде. Варианты списков можно посмотреть по ссылке в этом пункте примечания. Допустимо использование названий структуры как "Связный список", так и "Связанный список" (от слов "связной" и "связанный").
  2. Блок-схема -- это одна из технологий разработки программного обеспечения (ПО), которая была принята в качестве стандарта на заре компьютерной эпохи. Необходимость в блок-схемах естественно вытекала из-за невыразительности языков программирования. Очень часто в государственных организациях до наших дней можно встретить алгоритмы действий в виде блок-схем на стенах. Блок-схемы несколько архаичны, но например, такой визуальный графический язык, как ДРАКОН ещё не сказал своего слова. Создатели космического корабля "Буран" это подтверждают.
  3. Следует помнить о том, что связанный список для хранения информации может иметь КПД всего 11%: 4 байта на указатель на следующий элемент, 4 байта на предыдущий элемент, и только 1 байт на переменную типа BYTE. Соотношение полезной информации к общей как 1 к 9, что и даёт всего 11%.