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

Содержимое удалено Содержимое добавлено
Строка 132:
Удаление будет производиться с конца списка, так как это заложено в алгоритме работы списка. После удаления, будет выведен список оставшихся элементов.
<source lang="oberon2">
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;
</source>
Внутри метода первый цикл можно заменить на REPEAT...UNTIL. А вот со вторым использовать не получится, так как последний элемент имеющий признак "el.last" не будет выведен на экран.
 
==== Процедура Start ====
Это процедура является завершающей, и включает в себя всю последовательность вызовов методов.
<source lang="oberon2">
PROCEDURE Start*;
VAR
BEGIN
NEW(lst);
lst.Init;
lst.FillList;
lst.DelElem
END Start;
</source>
Последовательные вызовы приводят к созданию списка, его заполнению, затем удалению пяти элементов.
 
=== Полный листинг ===
Текст модуля достаточно разобран выше, текст приводится без комментариев. Рекомендуется самостоятельно разобраться в деталях реализации.
 
Hello14.odc
<source lang="oberon2">
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.
</source>
 
== Заключение ==
Приведённый пример является простейшим. В нём не хватает нескольких методов для доступа к произвольному элементу (на самом деле, здесь бы хватило и фиксированного массива указателей). Кроме того, нельзя удалять элементы из середины списка. Но данный учебный пример позволяет понять как это сделать, и пример можно взять за основу для своих решений. Ещё раз хотелось бы остановиться на эффективности использования памяти в приведённом примере -- очень не эффективно. Структуры данных надо проектировать тщательно, особенно когда дело касается большого массива данных.
 
== Примечания ==