Вы, возможно, заметили, что при рассмотрении связанных списков большин-
ство операций было определено на основе каких-либо действий после указанной
ячейки в списке. Если задана определенная ячейка, очень просто добавить или
удалить ячейку после нее или перечислить идущие за ней. Но не так легко удалить
саму ячейку, вставить новую перед ней или перечислить находящиеся перед ней
ячейки. Однако небольшое изменение "кода позволит выполнить и эти операции.
Добавьте к каждой ячейке новое поле указателя, ссылающегося на предыду-
щую ячейку в списке. С помощью этих новых полей вы можете создать двусвязный
список, который позволит исследовать элементы в обратном порядке (см. рис. 2.8).
Теперь не составит труда удалить или вставить новую ячейку перед заданной и пе-
речислить ячейки в любом направлении.
Рис. 2.8. Двусвязный список
Тип записи TDoubleListCell, используемый для подобных списков, может
быть определен следующим кодом: ,
type
PDoubleListCell = ^TDoubleListCell;
TDoubleListCell = record
Value : String[20];
NextCell : PDoubleListCell;
PrevCell : PDoubleListCell;
end;
Часто бывает полезно сохранять указатели на начало и конец двусвязного
списка. Тогда вы сможете легко добавлять элементы с обеих сторон списка. Могут
пригодиться метки в начале и конце списка. Тогда вам не нужно будет заботиться
о том, работаете ли вы с его началом, серединой или концом.
На рис. 2.9 показан двусвязный список с метками. На этом рисунке неисполь-
зуемые указатели меток NextCell и PrevCell установлены в нуль. Поскольку
программа опознает концы списка, сравнивая указатели ячейки с метками, а не
отыскивая значение nil, устанавливать эти значения в нуль не обязательно. Тем
не менее это признак хорошего стиля программирования.
Рис. 2.9. Двусвязный список с метками
Код для вставки и удаления элементов из двусвязного списка подобен коду,
представленному ранее для односвязных списков. Необходимо лишь немного из-
менить процедуры, чтобы они могли обрабатывать указатели PrevCell.
Теперь вы можете написать новые процедуры для вставки элемента до или
после данного и его удаления. Например, следующие процедуры добавляют и уда-
ляют ячейки из двусвязного списка. Обратите внимание, что эти процедуры не
нуждаются в доступе ни к одной из меток списка. Им нужны только указатели на
узел, который будет добавлен или удален, и узел, расположенный рядом с точкой
вставки.
procedure Remove(t arget:PDoubleListCell);
var
after_target, before_target:PDoubleListCell;
begin
after_target := target^.NextCell;
before_target := target^.PrevCell;
before_targetA.NextCell := after_target;
after_targetA.PrevCell := before_target;
end;
procedure AddAfter(new_cell, after_me: PDoubleListCell);
var
before_me : PDoubleListCell;
begin
before_me := after_me^.NextCell;
after_me^.NextCell := new_cell;
new.cell^.NextCell := before_me;
before_me^.PrevCell := new_cell;
new_cell^.prevCell := after_me;
end;
procedure AddBefore(new_cell, before_me : PDoubleListCell);
var
after_me : PDoubleListCell;
begin
after_me := before_me^.PrevCell;
after_me^.NextCell := new_cell;
new_cell/4.NextCell := before_me;
before_me^.PrevCell := new_cell;
new_cel^.PrevCell := after_me;
end;
Программа DblLiSt работает с двусвязным списком. Она позволяет добавлять
элементы до или после выбранного, а также удалять его. |
Главная
Каталог файлов
