Как вы могли заметить односвязные списки имеют один большой недостаток, который препятствует их широкому применению: такой список нельзя просматривать в обратном направлении. Для этих целей используются списки с двойной связью. Такой список представляет из себя ту же структуру, только теперь добавляется указатель на предыдущий элемент. Т.е. вот так:
+------+<---| |---->+------+<---| |---->+------+
| data | | | | data | | | | data |
+------+ | | +------+ | | +------+
| next | | | | next | | | | next |
| ---------+--- | ---------+--- | -------------> nil
+------+ | +------+ | +------+
| prev | | | prev | | | prev |
nil<--------- | |------------- | |------------- |
+------+ +------+ +------+
Соответственно наша структура преобразуется к следующей:
type
plist = ^tlist;
tlist = record
data : integer;
next, prev : plist;
end;Работа с двусвязным списком не на много сложнее работы с односвязным. А в некоторых местах даже легче. Кроме двусвязных списков я бы хотел обратить внимание на ещё одну деталь. Давайте создадим указатель на указатель :) звучит не очень, но всё таки. Для нашего примера тип указателя на указатель на tlist опишется так:
p2list = ^plist;Что же это такое указатель на указатель ? Давайте вспомним что такое указатель. Указатель - это адрес. Значит указатель на указатель - это адрес указателя. Т.е. это адрес той ячейки памяти, где содержится адрес ячейки памяти, где содержится tlist. Помните: "...синица, которая ворует пшеницу, которая в чёрном чулане хранится, в доме который построил Джек." :) Мы можем создать и указатель на указатель на указатель и так далее. Но сегодня мы не будем так изощрятся и кроме двусвязных списков научимся использовать указатели на указатель. Для начала откажемся от глобальных переменных. Давайте представим, что мы будем писать функции и процедуры для кого другого, т.е. у нас не будет глобальных переменных - всё, что нам нужно мы будем получать из параметров. Начнём с добавления нового элемента в конец списка. Это очень просто :)
procedure AddToEnd (list : p2list; d : integer);
var
prior : plist;
begin
prior := nil;
{ перематываем список до конца }
while list^ <> nil do
begin
prior := list^;
list := @list^^.next
end;
{ добавляем новый элемент }
New (list^);
with list^^ do
begin
data := d;
next := nil;
prev := prior
end
end;Итак наша процедура получает 2 параметра: указатель на указатель на tlist и число, которое добавим в конец списка. Давайте обратимся к самой "страшной" строчке и попробуем разобраться: list := @list^^.next. Итак list указывает на plist, т.е. если разыменовать(получить значение по его адресу) указатель, то list^ - это указатель на tlist. Тогда, что бы обратиться к какому либо полю мы должны провести операцию разыменования ещё раз, т.е. list^^ - это уже структура tlist и мы можем спокойно обращаться с её полями. Теперь давайте разберём зачем мы здесь использовали @. Опять обратимся к определению указателя: указтель - это адрес. Значит в list у нас должен содержаться адрес указателя на tlist. Такой указтель у нас есть - list^^.next - указывает на tlist. Значит мы должны присвоить list адрес list^^.next, что мы благополучно и делаем. В остальном эта процедура ничем замечательным не обладает. Итак элемент добавлен, после работы его надо удалить.
procedure DelFromEnd (list : p2list);
var
old : plist;
begin
if list^ = nil then
exit; { список пуст, удалять нечего }
{ перемотка в конец }
while list^^.next <> nil do
list := @list^^.next;
{ list^ указывает на последний элемент }
old := list^;
{ удаляем этот элемент логически ....}
list^ := nil;
{ ... и физически - освобождаем память }
Dispose (old)
end;Так же необходимо написать процедуру для очиски списка. Это можно сделать 2 способами.
- Преобразовать DelFromEnd в функцию, возвращающую значение false, если список пуст, тогда что бы его очистить можно создать пустой цикл, пока функцию не вернёт false
- Воспользоваться специальной процедурой, текст которой приведён ниже.
procedure Clear (list : p2list);
var
old : plist;
begin
if list^ = nil then
exit;
{ перемотка в начало }
while list^^.prev <> nil do
list^ := list^^.prev;
{ перемотка в конец с уничтожением текущего элемента }
while list^ <> nil do
begin
old := list^;
list^ := list^^.next;
Dispose (old)
end
end;Естественно, что нам может понадобится функция для поиска элемента. Поиск осуществляется тем же перебором от начала до конца, если поиск успешен, то функция вернёт значение true, а list будет указывать на найденный элемент. В противном случае функция вернёт false.
function FindData (list : p2list; data : integer): boolean;
var
l : plist;
begin
if list^ = nil then
begin
FindData := false;
exit
end;
while list^^.prev <> nil do
list^ := list^^.prev;
l := list^;
while l <> nil do
begin
if l^.data = data then
begin
FindData := true;
list^ := l;
exit
end;
l := l^.next
end;
FindData := false
end;Внимательный читатель должен был бы уже призадуматься, а почему это мы передаём параметры обычным способом и ожидаем, что в конце что-то изменится ? (Если этот вопрос вас не гложет или вы понимаете почему произойдёт изменение переходите сразу дальше). Ведь после выполнения такого кода a и b остануться равными 0 !
procedure bla (c,d : integer);
begin
c := 2;
d := 3
end;
var
a, b : integer;
begin
a := 0;
b := 0;
bla (a, b)
end.Однако, то что истинно для простых переменных не всегда правда для указателей. Давайте немного изменим код:
type
pint = ^integer;
procedure bla (c,d : pint);
begin
c^ := 2;
d^ := 3
end;
var
a, b : integer;
begin
a := 0;
b := 0;
bla (@a, @b)
end.В результате a и b изменятся ! Давайте разберём почему. Мы передаём в bla указатели (читай адреса) c и d. Потом меняем значения по этим адресам (c^ := 2). При вызове в bla передадутся адреса a и b - bla (@a, @b). Когда процедура изменит значения по этим адресам, то изменятся значения a и b. Всё это конечно хорошо, но зачем тогда мы передаём в процедуры для работы со списком указатель на указатель, а не просто указатель! Тут всё дело в организации списка. Для односвязного списка мы использовали 2 указателя: начала и рабочий. Для двусвязного списка необходимость в указателе на начало отпадает, поэтому у нас будет один единственный указатель. С ним надо быть осторожнее! Не дай бог обратить его где-нибудь в nil! Односвязный список мы могли бы востановить по указателю начала. Поэтому например в функции поиска для перемотки используется дополнительная переменная. Однако я отвлёкся. Главная часть нашей программы будет выглядеть так:
var
list : plist; { это и есть наш список }
begin
.....
AddTolistEnd (@list, d);
.....Т.е. что бы изменить list, а значит и наш список нам надо в процедуры передавать указатель на plist, т.е. указатель на указатель на tlist. Но вернёмся к нашим баранам. Продолжим пополнять арсенал процедур и функций для работы со списком. Теперь, когда мы можем найти элемент в списке, то нужно с ним что-то делать. Например удалить или вставить новый после него. Начнём со вставки. Что бы вставить элемент нам надо соответствующим образом изменить указатели next у предшествующего и prev у следующего. Т.е. если вначале у нас был такой список:
...---->+------+<---| |---->+------+
| data | | | | data |
+------+ | | +------+
| next | | | | next |
| ---------+--- | ------------->....
+------+ | +------+
| prev | | | prev |
...<--------- | |------------- |
+------+ +------+
тогда, изменив указтели мы получаем такую картинку:
...---->+------+ +------+
| data | | data |
+------+ +------+
| next | | next |
| ------| | ------------->...
+------+ | +------+
| prev | | | prev |
...<--------- | | |---------- |
+------+ | | +------+
^ | \ / ^
| |->+------+ |
| | data | |
| +------+ |
| | next | |
| | ----------|
| +------+
| | prev |
|----------- |
+------+
Текст процедуры, которая описывает это приведён ниже:
procedure Add (list : p2list; d : integer);
var
l : plist;
begin
if list^ = nil then
begin
AddToEnd (list, d);
exit
end;
New (l);
l^.data := d;
l^.prev := list^;
l^.next := list^^.next;
list^^.next := l
end;procedure AddToBegin (list : p2list; d : integer);
var
l : plist;
begin
if list^ = nil then
begin
AddToEnd (list, d);
exit
end;
while list^^.prev <> nil do
list := @list^^.prev;
New (l);
l^.data := d;
l^.prev := nil;
l^.next := list^;
list^^.prev := l
end;
procedure DelFromBegin (list : p2list);
var
old : plist;
begin
if list^ = nil then
exit;
while list^^.prev <> nil do
list^ := list^^.prev;
old := list^;
list^ := list^^.next;
list^^.prev := nil;
Dispose (old)
end;
Вот так слово за слово мы и подошли к процедуре вывода списка на экран. Тут я хочу остановится подробнее. Вспомним примерную структуру нашей будующей программы для работы со списком:
var
list : plist; { это и есть наш список }
begin
.....
AddTolistEnd (@list, d);
.....*123добавим элемент в начало:
321 *123добавим элемент в конец:
321 *123 456теперь добавим после текущего:
321 *123 0 456. Теперь найдём элемент 456:
321 123 0 *456Как вы видите list путешествует по списку (хотя особо не расходится :) и было бы неплохо добавить в процедуру вывода на экран именно указывать где сейчас list с помощью такой же звёздочки, что мы сейчас благополучно и сделаем:
procedure Display (list : plist);
var
p : plist;
begin
if list = nil then
writeLn ('Список пуст')
else
begin
p := list;
while p^.prev <> nil do
p := p^.prev;
while p <> nil do
begin
if p = list then
write ('*');
write (p^.data, #32);
p := p^.next
end
end
end;именно для указания текущего положения мы и вводим дополнительную переменную p с помощь которой осуществляем перемотку. И когда p = list значит это текущий элемент и поэтому мы выводим звёздочку. Ну и наконец я привожу текст программы, работающей с двусвзяным списком. Как и в прошлый раз процедуры, которые я дал вам на домашнее рассмотрение не приведены.
