Компонентный Паскаль/Связанный список

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

Что такое список -- знают все из повседневной жизни. Это лист бумаги, который содержит пункты, например, того, что нужно купить в магазине. Аналога связного списка^[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 определён через указатель на структуру, поэтому переменную такого типа, можно создать динамически, что позволит сократить объём программы в виде исполняемого файла.

Инициализация списка

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

PROCEDURE (l: TDblList)Init, NEW;
VAR
BEGIN
	l.len := 0;     (* пустой список *)
	l.first := NIL; (* первый элемент *)
	l.end := NIL;   (* последний элемент *)
END Init;

В этом методе используется ссылки на пользовательский тип "TDblList". Происходит принудительное обнуление длины списка, и присвоение указателям значения "NIL" ("НИЧЕГО"). Это специальная переменная, для указания того, что здесь "пустота"^[4].

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

Вставку нового элемента в список рационально (но не обязательно) реализовать в форме метода объекта. Представленный вариант ниже вставляет новый элемент только в конец списка. Для включения элемента в произвольное место, необходимо в объект TDblList свойство "cur"("current", "текущий"). Оно как раз и будет указателем на то место, куда вставлять. Предлагается такой вариант списка выполнить самостоятельно.

	PROCEDURE (l: TDblList)Insert(v:INTEGER), NEW;
		VAR
			el, el1 : POINTER TO TDblElem;
	BEGIN
		NEW(el);
		IF l.len=0 THEN (* если список пустой *)
			l.first:=el;  (* назначить первый элемент *)
			l.end:=el;    (* назначить его же последним *)
			el.forward:=NIL; (* ссылки никда не показывают *)
			el.backward:=NIL;
			el.value:=v;  (* присвоить значение из параметров *)
			el.first:=TRUE; (* установить флаги элемента *)
			el.last:=TRUE
		ELSE
			el1:=l.end; (* сохранение бывшего последнего элемента *)
			el1.forward:=el; (* создание перекрёстных ссылок *)
			el1.last:=FALSE; (* больше не последний *)
			
			l.end:=el;  (* присвоение нового оследнего элемента *)
			el.backward:=el1; (* показать на предыдущий *)
			el.forward:=NIL;  (* впереди ничего нет *)
			el.value:=v;      (* присвоить значение из параметра *)
			el.first:=FALSE;  (* выставить флаги *)
			el.last:=TRUE;
		END;
		INC(l.len);
		Log.String('Элемент: '); Log.Int(el.value); Log.Ln	
	END Insert;

Работа с указателями в Компонентном Паскале упрощена до предела^[5]. Если в предыдущих вариантах Паскаля (или даже во вполне современном FreePascal) использовалась специальная семантика для работы с указателями, то сейчас она изъята из языка, как излишняя. Ведь тип переменной известен точно^[6]. Во входных параметрах метода указана переменная "v". Она вместе с созданием нового элемента присваивает значение новому элементу. В конце метода выводится контрольная строка, что элемент действительно вставлен.

Удаление элемента

Удаление элемента из списка опасно тем, что может разорвать цепочку, и если её не срастить -- указатель будет висеть в никуда.

	PROCEDURE (l: TDblList)Remove, NEW;
		VAR
			el, el1 : POINTER TO TDblElem;
	BEGIN
		IF l.len>1 THEN (* если в списке более двух элементов *)
				el:=l.end;       (* найти последний элемент *)
				el1:=el.backward;(* найти предпоследний элемент *)
				el:=NIL;   (* последний элемент удалить *)
				l.end:=el1; (* последним сделать предпоследний *)
				el1.forward:=NIL; (* больше никуда не показывает *)
				el1.last:=TRUE; (* выставить правильный флаг *)
				DEC(l.len); (* уменьшить длину *)
		ELSE    (* остался последний элемент *)
				el:=l.end;
				el:=NIL;
				l.end:=NIL;
				l.first:=NIL;
				l.len:=0;
		END;
		INC(l.len);	
	END Remove;

Удалять элементы проще, чем вставлять, так как не приходится думать об удалённом элементе. Но в любом случае, надо контролировать ссылки.

Заполнение списка

Метод будет реализован с помощью цикла FOR. Необходим только для первоначального заполнения списка.

PROCEDURE (l: TDblList) FillList, NEW;
VAR
	i: INTEGER;
BEGIN
	FOR i:=1 TO 15 DO
		l.Insert(i*10);
	END;	
END FillList;

В приведённом методе происходит заполнение списка 15 элементами.

Удаление последних пяти элементов

Удаление будет производиться с конца списка, так как это заложено в алгоритме работы списка. После удаления, будет выведен список оставшихся элементов.

PROCEDURE (l: TDblList) DelElem, NEW;
VAR
	i: INTEGER;
	el : POINTER TO TDblElem;
BEGIN
	FOR i:=1 TO 5 DO
		l.Remove;
	END;
	el:=l.first;
	FOR i:=1 TO l.len DO
		Log.String('Элемент: '); Log.Int(el.value); Log.Ln;
		el:=el.forward;
	END;
END DelElem;

Внутри метода первый цикл можно заменить на REPEAT...UNTIL. А вот со вторым использовать не получится, так как последний элемент имеющий признак "el.last" не будет выведен на экран.

Процедура Start

Это процедура является завершающей, и включает в себя всю последовательность вызовов методов.

PROCEDURE Start*;
	VAR
BEGIN
	NEW(lst);
	lst.Init;
	lst.FillList;
	lst.DelElem
END Start;

Последовательные вызовы приводят к созданию списка, его заполнению, затем удалению пяти элементов.

Полный листинг

Текст модуля достаточно разобран выше, текст приводится без комментариев. Рекомендуется самостоятельно разобраться в деталях реализации.

Hello14.odc

MODULE TestHello14;
	(* Этот пример показывает как
	создать и использовать двусвязный список *)

	IMPORT In, Log, Math;

	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;

	VAR
		lst: TDblList;

	PROCEDURE (l: TDblList)Init, NEW;
		VAR
	BEGIN
		l.len := 0; (* пустой список *)
		l.first := NIL; (* первый элемент *)
		l.end := NIL; (* последний элемент *)
	END Init;

	PROCEDURE (l: TDblList)Insert (v: INTEGER), NEW;
		VAR
			el, el1: POINTER TO TDblElem;
	BEGIN
		NEW(el);
		IF l.len = 0 THEN (* если список пустой *)
			l.first := el; (* назначить первый элемент *)
			l.end := el; (* назначить его же последним *)
			el.forward := NIL; (* ссылки никда не показывают *)
			el.backward := NIL;
			el.value := v; (* присвоить значение из параметров *)
			el.first := TRUE; (* установить флаги элемента *)
			el.last := TRUE
		ELSE
			el1 := l.end; (* сохранение бывшего последнего элемента *)
			el1.forward := el; (* создание перекрёстных ссылок *)
			el1.last := FALSE; (* больше не последний *)

			l.end := el; (* присвоение нового оследнего элемента *)
			el.backward := el1; (* показать на предыдущий *)
			el.forward := NIL; (* впереди ничего нет *)
			el.value := v; (* присвоить значение из параметра *)
			el.first := FALSE; (* выставить флаги *)
			el.last := TRUE;
		END;
		INC(l.len);
		Log.String('Элемент: '); Log.Int(el.value); Log.Ln
	END Insert;

	PROCEDURE (l: TDblList)Remove, NEW;
		VAR
			el, el1: POINTER TO TDblElem;
	BEGIN
		IF l.len > 1 THEN (* если в списке более двух элементов *)
			el := l.end; (* найти последний элемент *)
			el1 := el.backward; (* найти предпоследний элемент *)
			el := NIL; (* последний элемент удалить *)
			l.end := el1; (* последним сделать предпоследний *)
			el1.forward := NIL; (* больше никуда не показывает *)
			el1.last := TRUE; (* выставить правильный флаг *)
			DEC(l.len); (* уменьшить длину *)
		ELSE (* остался последний элемент *)
			el := l.end;
			el := NIL;
			l.end := NIL;
			l.first := NIL;
			l.len := 0;
		END;
	END Remove;

	PROCEDURE (l: TDblList) FillList, NEW;
		VAR
			i: INTEGER;
	BEGIN
		FOR i := 1 TO 15 DO
			l.Insert(i * 10);
		END;
	END FillList;


	PROCEDURE (l: TDblList) DelElem, NEW;
		VAR
			i: INTEGER;
			el: POINTER TO TDblElem;
	BEGIN
		FOR i := 1 TO 5 DO
			l.Remove;
		END;
		el := l.first;
		FOR i := 1 TO l.len DO
			Log.String('Элемент: '); Log.Int(el.value); Log.Ln;
			el := el.forward;
		END;
	END DelElem;

	PROCEDURE Start*;
		VAR
	BEGIN
		NEW(lst);
		lst.Init;
		lst.FillList;
		lst.DelElem
	END Start;


BEGIN
END TestHello14.

Вывод программы

Если программа набрана правильно, то должен быть получен следующий вывод:

компилируется "TestHello14"   616   4
старый модуль TestHello14 выгружен
Элемент:  10
Элемент:  20
Элемент:  30
Элемент:  40
Элемент:  50
Элемент:  60
Элемент:  70
Элемент:  80
Элемент:  90
Элемент:  100
Элемент:  110
Элемент:  120
Элемент:  130
Элемент:  140
Элемент:  150
Элемент:  10
Элемент:  20
Элемент:  30
Элемент:  40
Элемент:  50
Элемент:  60
Элемент:  70
Элемент:  80
Элемент:  90
Элемент:  100

Заключение

Приведённый пример является простейшим. В нём не хватает нескольких методов для доступа к произвольному элементу (на самом деле, здесь бы хватило и фиксированного массива указателей). Кроме того, нельзя удалять элементы из середины списка. Но данный учебный пример позволяет понять как это сделать, и пример можно взять за основу для своих решений. Ещё раз хотелось бы остановиться на эффективности использования памяти в приведённом примере -- очень не эффективно. Структуры данных надо проектировать тщательно, особенно когда дело касается большого массива данных.

Примечания

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

[спис-1] Связный список не единственная структура в подобном роде. Варианты списков можно посмотреть по ссылке в этом пункте примечания. Допустимо использование названий структуры как "связный список", так и "связанный список" (от слов "связной" и "связанный").

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

[кпд-3] Следует помнить о том, что связный список для хранения информации может иметь КПД всего 11%: 4 байта на указатель на следующий элемент, 4 байта на предыдущий элемент, и только 1 байт на переменную типа BYTE. Соотношение полезной информации к общей как 1 к 9, что и даёт всего 11%.

[nil-4] По указателям действие присвоения NIL излишне в соответствии с документацией, встроенной в КП: "Любой указатель может принимать значение NIL, которое не указывает ни на какую переменную вообще. Все поля и элементы вновь размещенной записи или массива очищаются; в частности, значения все содержащиеся в них указательные и процедурные переменные устанавливаются в NIL." Но мы будем приучаться к методически правильному промышленному программированию. В разных реализациях КП вполне могут встретиться отклонения от эталонного КП. С представленным подходим, в случае необходимости сменить компилятор проблем точно не возникнет.

[указ-5] Традиционно считается, что работа с указателями сложна. На самом деле это не так сложно, если работать со строго типизированными данными. См. Указатель (тип данных).

[питон-6] Кроме Компонентного Паскаля, такая же простая работа с указателями присутствует в python. Но python -- язык динамический, а значит более медленный чем КП (примерно в 25-28 раз).

[1]

[2]

[3]

[4]

[5]

[6]