 |
Модуль построения и редактирования списка
|
|
|
|
Согласно шаблону описанному в предыдущем разделе структуру двунапраленного линейного списка из трех узлов можно представить графически, как это показано на рис.13.
 | |||
 | |||
Рис.13. Структура двунаправленного линейного списка
Каждый из трех узлов(они пронумерованы) содержит три поля:
- указатель на предыдущий узел (поле Prev);
- указатель на последующий узел (поле Next);
- информационное поле (поле Down).
Информационное поле с именем Down описано типом данных запись (record TA).
Содержание полей этой записи представлено ниже под каждым узлом списка.
В поле Prev первого узла, как и в поле Next последнего записан адрес Nil (дословно в никуда). Зарезервированное слово nil является признаком конца списка и это действительно так, поскольку ни перед первым узлом, ни после последнего других узлов нет и указывать не на что. Запись TList содержит:
- указатель на первый узел списка (поле First);
- указатель на последний узел списка (поле Last);
- поле счетчика числа узлов в списке (поле Count).
Указатели First и Last предназначены и используются для процедуры построения и процедуры редактирования списка. Они предоставляют определенные удобства в работе со списком, поскольку по указателю First легко попасть в начало списка, а по указателю Last в его конец.
В соответствии с представленной структурой перейдем к описанию модуля Unit2.
Интерфейсная часть модуля Unit2 имеет следующий вид:
unit Unit2;
Interface
uses Classes;
Type
TA=record { Автомобиль }
M: String[15]; { Ф.И.О. владельца }
N: String[10]; { Марка }
W: String[14]; { Номер }
end;
PTElem=^TElem;
TElem=record
Prev,Next: PTElem;
Down: TA;
end;
TList=record
First,Last: PTElem;
Count: Longint;
end;
Var
L: Tlist; { переменная для работы с указателями First
|
|
|
и Last и счетчиком Count }
Current: PTElem; { служебный указатель для
перемещения по узлам списка }
A: array[1..10] of TA; { информационный массив-буфер
описан в разделе 1.1}
ind,key1,t:integer; {ind - счетчикзаполненных
элементов массива «а» или иначе
заданное число узлов будущего
списка, key1 – служебный ключ-
признак и t – номер заданного узла }
procedure TList_Init; { процедура инициализации
указателей First, Last и счетчика Count }
procedure CreateList; { процедура построения списка}
procedure PrintFirst(mem:TStrings); { процедура
прямой печати списка}
procedure PrintLast (mem:TStrings); { процедура
обратно печати списка}
procedure SearchNode (mem:TStrings); { процедура
поиска узла по номеру}
procedure DisposeList; { процедура удаления списка}
procedure DeleteNode;{ процедура удаления узла списка}
procedure AddAfterNode; { процедура добавления узла в
список после заданного номера}
Implementation
Содержимое процедур приведено в разделе реализации модуля.
Создание (построение) и опустошение списка
Под пустым списком следует понимать служебную структуру данных типа запись, содержащую поля указателей на начало и конец линейного списка, а также поле-счетчик узлов этого списка. При этом поля указателей еще не содержат конкретный адрес узла начала и узла конца списка, а лишь проинициализированы безадресным значением nil. В свою очередь поле-счетчик содержит значение 0. Поэтому на начальном этапе построения списка используется процедура TList_Init она инициализирует указатели First, Last и счетчик Count, присваивая им начальные значения, и используется в процедурах как построения так и удаления списка.
procedure TList_Init;
Begin
L.First:=nil;
L.Last:=nil;
L.Count:=0;
end;
Затем следует ключевая процедура построения списка CreateList. Построение непустого списка можно осуществить посредством вставки новых узлов либо со стороны “головы” (начала) списка, либо со стороны “хвоста” (конца) списка. Возьмем в качестве примера процедуру вставки узла со стороны “головы” списка, и пусть эта процедура имеет вид:
|
|
|
procedure CreateList;
var i:integer;
Begin
Tlist_Init; { вызвана процедура инициализации указателей
First, Last и счетчика Count }
{1} new(current); {выделена память под первый узел
списка, а его адрес записан в указатель current }
Inc(L.Count); { узлов в списке стало на один больше}
current^.down.M:=a[L.Count].M; { заполним три
информационных поля первого узла,}
current^.down.N:=a[L.Count].N; { иначе говоря введем
данные по первому владельцу}
current^.down.W:=a[L.Count].W;{ автомобиля, используя
операцию разименовывания «^» для работы с полем down }
{2} current^.prev:=nil;;{поле prev первого узла принимает
значение nil }
L.first:=current; {указатель начала списка поставлен на
текущий первый узел (куда указывает current туда же
будет указывать и first, адреса уравнены) }
while L.Count<>ind do { цикл работает до тех пор
пока не будет создано заданное число узлов «ind»}
Begin
{3} new(current^.next); {выделить память для следующего
узла по адресу, записанному в поле next текущего}
Inc(L.Count); { узлов в списке стало на один больше}
current^.next^.down.M:=a[L.Count].M; { заполним три
информационных поля }
current^.next^.down.N:=a[L.Count].N; { следующего узла,}
current^.next^.down.W:=a[L.Count].W;
{4} current^.next^.Prev:=current; {инициализируем
поле prev следующего(второго) узла, записывая в него
адреспредыдущего(первого) узла (связывание второго
узла с первым по полю prev)}
{5} current:=current^.Next; {сделать следующий(второй)
узел текущим (перемещаем указатель current на
следующий узел)}
end;
L.Last:=current; {указатель конца списка
поставлен на текущий последний узел (куда
указывает current туда же будет указывать и Last,
адреса уравнены)}
current^.Next:=nil; {поле next последнего узла
списка принимает значение nil }
end;
Таким образом, для построения списка следует выполнить итерационную процедуру связывания структурированных узлов, посредством инициализации их полей prev и next. На рис.14 графически интерпретированы действия пронумерованных операторов программы.
 |
 |
Рис.14. Графическая интерпретация действий
Чтобы опустошить, т. е. уничтожить список, надо организовать итерационный процесс удаления узлов либо со стороны “головы” списка, либо со стороны “хвоста” списка до тех пор, пока список не станет пустым. Возьмем в качестве примера процедуру DisposeList (удаления узла со стороны головы списка) и пусть эта процедура имеет вид:
|
|
|
procedure DisposeList;
Var temp:PTelem;
Begin
current:=L.first; {ставим служебный указатель current
на первый узел списка}
if L.count<>0 then {если число узлов списка не равно
нулю, тогда начинаем итерационный
процесс удаления этих узлов}
Repeat
temp:=current; {ставим вспомогательный указатель
temp на текущий (первый) узел,
заимствуя адрес у указателя current }
current:=current^.next; {перемещаем указатель current
с текущего (первого) узла на следующий (второй) узел}
temp^.Next:=nil; {обрываем связь между текущим
(первым) и следующим (вторым) узлом по указателю next }
temp^.prev:=nil; {обрываем связь между текущим
(первым) и предыдущим узлом по указателю prev
(при удалении первого узла списка этот оператор можно
не выполнять) }
dispose(temp); {удаляем узел на который указывает
указатель temp (первый узел)}
until current=nil; {цикл работает до тех пор пока,
перемещаясь по списку, указатель current не достигнет
последнего узла, который не удаляется}
dispose(current); {удаляем последний узел спика}
Tlist_Init; { инициализируем (освобождаем) указатели
First, Last и счетчик Count }
end;
|
|
|
