 |
Вывод содержимого информационных полей списка
|
|
|
|
(прямая и обратная печать)
Вывод содержимого информационных полей списка (или печать списка) является частным случаем алгоритма обхода списка, основная идея которого заключается в переходе от узла к узлу списка согласно ссылкам, записанным в узлах. Для этой цели в процедуре прямой печати (от “головы” списка) PrintFirst организован цикл для переме-щения указателя current по узлам списка, начиная с первого. Внутри этого цикла присут-ствует оператор (mem.Add) для вывода содержимого информационных полей текущего узла в окно компонента memo1 через свойство lines:
procedure PrintFirst(mem:TStrings);
Begin
current:=L.first; {ставим служебный указатель current
на первый узел списка}
if L.count<>0 then
Repeat
mem.Add(current^.down.M+' '+current^.down.N+'
'+current^.down.W);
current:=current^.next; {перемещаем указатель current
с текущего узла на следующий}
until current=nil
Else
end;
Процедура обратной печати PrintLast аналогична по-своему алгоритму процедуре прямой печати PrintFirst с той лишь разницей, что начальное положение указателя current находится на последнем узле списка и он перемещается в перед к началу списка.
procedure PrintLast(mem:TStrings);
Begin
current:=L.Last; {ставим служебный указатель current
на последний узел списка}
if L.count<>0 then
Repeat
mem.Add(current^.down.M+' '+current^.down.N+
' '+current^.down.W);
current:=current^.prev; {перемещаем указатель
current с текущего узла на предыдущий}
until current=nil
Else
end;
Включение и удаление узлов списка
Выделяют две основные операции, которые используются, как правило, при моди-фикации структуры списка. Это включение и исключение узлов. Наиболее просто эти операции реализуются для узлов с левой и правой стороны списка, т. к. всегда известно их местоположение: адреса первого и последнего узлов находятся в заголовке списка. Для включения узла в середину списка и исключения узла из середины списка необходимо предварительно выполнить обход части списка.
|
|
|
Включение узла в список заключается в размещении нового узла в подходящем месте списка. Порядок узлов при выполнении операции включения обычно не нарушается. Включение узла в середину списка всегда требует ссылку на узел, после которого будет размещен новый. Часто адрес этого узла неизвестен, и для его обнаружения необходим обход списка. Ниже приведена процедура включения нового узла в список после узла с заданным номером.
Алгоритм процедуры AddAfterNode (добавление узла после заданного) также состоит из двух основных действий: первое-это создание узла, а второе-это его включение(привязка) в заданное место цепочки линейного списка, используя при этом поля указателей prev и next:
procedure AddAfterNode;
var i:integer; temp:PTElem;
Begin
current:=L.first; {ставим служебный указатель current
на первый узел списка}
if L.count<>0 then begin
for i:=1 to t-1 do current:=current^.next; { цикл
прохода по списку }
{Оператор цикла for do предназначен для перемещения
текущего указателя current в заданное место списка, на
узел после которого добавляется новый. Цикл работает
до тех пор пока номер заданного узла(переменная t) не
совпадет со значением счетчика i }
{1} New(temp); {выделена память под новый узел списка,
а его адрес записан в указатель temp }
{2} temp^.Prev:=current; {устанавливаем связь между
новым узлом и узлом перед которым он вставляется(связь
по полю указателя prev справа-налево)}
{3} temp^.Next:=current^.next; {устанавливаем связь
между новым узлом и узлом после которого он
вставляется(связь по полю указателя next слева-направо)}
temp^.down.M:=a[ind].M; { заполним три
информационных поля }
temp^.down.N:=a[ind].N; { нового узла,}
temp^.down.W:=a[ind].W;
{4} current^.next^.prev:=temp; {устанавливаем связь
между новым узлом и узлом перед которым он
вставляется(связь по полю указателя prev справа-налево)}
|
|
|
{5} current^.next:=temp; {устанавливаем связь между
новым узлом и узлом после которого он вставляется(связь
по полю указателя next слева-направо)}
Inc(L.count); { узлов в списке стало на один больше}
end;
end;
На рис.15 графически интерпретированы действия пронумерованных операторов процедуры AddAfterNode.
 |
Рис.15. Графическая интерпретация действий
Для исключения узла из середины списка всегда необходима ссылка на удаляемый узел. Часто адрес этого узла неизвестен, и для его обнаружения необходим обход списка. Ниже приведена процедура DeleteNode (исключения узла из списка по заданному номеру).Алгоритм этой процедуры состоит из трех основных действий: первое-это перемещение служебного указателя current в заданное место списка на удаляемый узел, второе-это установление связей по указателям prev и next между узлом предшествующим удаляемому и узлом следующим за ним и наконец удаления выбранного узла.
procedure DeleteNode;
var i:integer;
Begin
current:=L.first; {ставим служебный указатель current на
первый узел списка}
if L.count<>0 then begin
for i:=1 to t-1 do current:=current^.next; {цикл прохода
по списку }
current^.prev^.next:=current^.next; { устанавливаем
связъ по указателю next между узлом
предшествующим удаляемому и
узлом следующим за ним (слева-направо).}
current^.next^.prev:=current^.prev;{ устанавливаем
связъ по указателю prev между узлом
следующим за удаляемым и узлом
предшествующим ему (справа-налево).}
dispose(current); {удаления выбранного узла}
current:=nil;
L.Count:=L.count-1;{ узлов в списке стало на один
меньше}
end;
end;
End.
Поиск узла по номеру
Алгоритм процедуры SearchNode (поиск узла по заданному номеру) пол-ностью аналогичен алгоритму процедуры прямой печати PrintFirst. В процедуре SearchNode также организован цикл для перемещения указателя current по узлам списка, начиная с первого. Однако такой цикл завершит свою работу, как только текущий указатель current “ встанет” на заданный узел. За циклом следует оператор (mem.Add) для вывода содержимого информационных полей текущего узла в окно компонента memo1 через свойство lines:
procedure SearchNode (mem:TStrings);
var i:integer;
Begin
current:=L.first;
if L.count<>0 then begin
for i:=1 to t-1 do
current:=current^.next;
mem.Add(current^.down.M+' '+current^.down.N+
' '+current^.down.W);
end;
end;
Литература
1. Просуков Е.А., Пащенко О.Б. Работа с динамическими структурами данных.Ч.1. Ссылки, структуры, списки записей: Учебно-методическое пособие по курсу «Вычислительная техника и информационная технология» М.:Изд-во МГТУ им. Н.Э.Баумана, 2003г. 37с.
|
|
|
2. Иванова Г.С., Ничушкина Т.Н., Пугачев Е.К. «Объектно-ориентированное программирование»: Учеб. для вузов/Под ред. Г.С. Ивановой. – М.:Изд.-во МГТУ им. Н.Э. Баумана, 2001..
3. Пащенко О.Б. Объектно-ориентированное программирование. Статические, динамические и виртуальные методы: Учебное пособие по курсу «Вычислительная техника и информационная технология» М.:Изд-во МГТУ им. Н.Э.Баумана, 2004г. 23с.
4.Глушаков С.В., Клевцов А.Л., Теребилов С.А. Программирование на DELPHI 5.0 – Харьков:Фолио,2002.
|
|
|
