Итак сегодня мы займёмся рассмотрением классического примера: связанный список. Для начала самый простой вариант - односвязный. Что же такое связаный список ? Давайте представим, что у нас есть запись.... для простоты введём только одно поле :)
tlist = record
data : integer;
end;И пускай нам нужно создать массив из N таких записей, причём N задаётся пользователем и может изменяться во время работы программы, как в сторону увеличения, так и в сторону уменьшения. Конечно можно создать массив таким образом:
list : array [1 .. N] of tlist;где N будет максимально возможное число для того, что бы массив поместился в сегменте данных. Однако это не есть гуд. Гораздо проще такая задача решается с использованием указателей. Чем мы сейчас и займёмся. Идея связанного списка проста как бит: в каждом элементе содержится указатель на следующий. Т.е. запись выглядит так:
type
plist = ^tlist;
tlist = record
data : integer;
next : plist
end;Давайте рассмотрим организацию такого списка. Проще всего это дело нарисовать, к сожалению к рассылке нельзя приаттачить картинку, поэтому я нарисую её тут с использованием текстовых символов (не судите за убогость):
+------+ |---->+------+ |---->+------+ | data | | | data | | | data | +------+ | +------+ | +------+ | next | | | next | | | next | | ----------- | ----------- | -------------> nil +------+ +------+ +------+
итак как мы видим в указателе next находится адрес следующего элемента в памяти. Последний же указатель указывает в никуда (т.е. в nil). Поэтому для организации списка нам потребуются 2 указателя на tlist. Один из них будет постоянно хранить адрес начала (т.е. первого элемента) списка, второй будет "суетится" по списку, т.е. бегать по нему из начала в конец. Можно было бы ввести ещё и указатель на последний элемент (т.е. 3-й указатель на tlist) , но в нём нет надобности, т.к. узнать кончился ли список мы можем, сравнив next с nil. Т.е. у нас будет 2 глобальных переменных:
var
list, start : plist;Start - будет указывать на начало списка, а list будет нашей рабочей лошадкой. Как видите наш список занимает в памяти всего 8 байт (под один указатель отводится 4). Для начала напишем процедуру, которая добавляет элемент в список. Замечу, что добавляем мы всегда в конец списка! Параметр d - это то, что нам нужно добавить. list у нас указывает на последний элемент списка.
procedure Add (d : integer);
var
l : plist;
begin
New (l); { выделяем память под структуру }
l^.data := d; { инициализируем данные }
l^.next := nil; { т.к. добавляем в конец, то указатель на следующий равен nil }
{ если start не равен nil, значит список не пуст}
if start <> nil then
begin
list := start;
{ "перематываем" список, что бы list стал последним элементом }
while list^.next <> nil do
list := list^.next;
list^.next := l { устанавливаем указатель на следующий элемент, а это у нас l }
end
else
start := l; { если список был пуст, тогда делаем l первым элементом }
list := l { теперь меняем текущий элемент, присваивая ему значение l }
end;Обратите внимание, что мы не освобождаем память, которую занимает l. Почему мы так делаем ? Опять "нарисую" картинку:
+------+ |---->...->+------+ +------+ | data | | ... | data | | data | +------+ | ... +------+ +------+ | next | | ... | next | | next | | ----------- ... | -------->nil | -------------> nil +------+ ... +------+ +------+ ^ ^ ^ | - это start | - это list | - это lВыполняя присваивание list^.next := l мы переходим к такому виду:
+------+ |---->...->+------+ |---->+------+ | data | | ... | data | | | data | +------+ | ... +------+ | +------+ | next | | ... | next | | | next | | ----------- ... | ------------ | -------------> nil +------+ ... +------+ +------+ ^ ^ ^ | - это start | - это list | - это lи после list := l мы получаем такую картину:
+------+ |---->...->+------+ |---->+------+ | data | | ... | data | | | data | +------+ | ... +------+ | +------+ | next | | ... | next | | | next | | ----------- ... | ------------ | -------------> nil +------+ ... +------+ +------+ ^ ^ | - это start | - это list и l
Если же мы добавляем первай элемнт, то в начале start = nil. В конце и list и start и l будут указывать на одно и тоже. Если же освободить память, которую занимает l, то последний (или первый) элемент списка отрежется и мы ничего не добавим. Теперь напишем процедуру, которая выводит результаты нашей деятельности, т.е. список на экран:
procedure Display;
begin
if start = nil then
begin
writeLn ('Список пуст.');
exit
end;
list := start;
while list <> nil do
begin
write (#32, list^.data);
list := list^.next
end
end;Итак тут мы устанавливам указтель list на начало списка (list := start), а потом "прокручиваем" его, пока он не равен nil (т.е. пока он существует). Обратите внимание, что мы переходим к следующему элементу таким образом: list := list^.next После выполнения программы было бы неплохо (я сказал даже очень замечательно) освободить память, которую занимает список. Это кстати может понадобится и в процессе выполнения самой программы. Процедура осовобождения очень похожа на процедуру вывода - мы так же последовательно перебираем список, только вместо вывода на экран мы освобождаем память.
procedure Clean;
var
l : plist;
begin
if start = nil then
exit; { список пуст, удалять нечего }
list := start; { переходим на начала списка }
while list <> nil do
begin
l := list; { теперь l - это текущий элемент }
list := list^.next; { list переходит на следующий }
Dispose (l) { освобождаем память }
end;
start := nil { обнуляем указатель начала }
end;Естественно, что нам может понадобится найти чего-то в списке. Для этого предназаначена следующая процедура. Мы ищем элемент с data = d. Указатель на него останется в list после завершения работы процедуры, если же элемент не найден, то list = nil. Сама она не представляет из себя что-то сверх выдающееся. Тот же перебор от начала до конца (или же до той поры пока не найдём).
procedure Search (d : integer);
var
flag : boolean;
begin
list := start;
flag := false;
while (list <> nil) and (not flag) do
begin
if d = list^.data then
flag := true
else
list := list^.next
end
end;Ну и напоследок напишем процедуру для удаления произвольного элемента из списка. Тут сразу же возникает 3 случая: удаляется первый, удалется последний и удаляется средний (т.е. не первый и не последний) элемент. Для начала рассмотрим третий случай. Список в данный момент представляет из себя что-то такое:
...->+------+ |---->+------+ |---->+------+
| data | | | data | | | data |
+------+ | +------+ | +------+
| next | | | next | | | next |
| ----------- | ------------ | ------------...
+------+ +------+ +------+
prev cur nxt
Я назвал условными именами элементы: cur - элемент, который удаляем; prev - элемент, который идёт перед удаляемым; nxt - элемент, идущий за удаляемым. Что бы удалить cur мы должны сделать следующие действия: prev.next = nxt (т.е. предыдущий должен указать на последующий за удаляемым):
...->+------+ +------+ |--|---->+------+
| data | | data | | | | data |
+------+ +------+ | | +------+
| next | | next | | | | next |
| -----------| | ---------+--- | ------------...
+------+ | +------+ | +------+
prev | cur | nxt
| |
|--------------|
Таким образом мы исключили из списка элемент cur, теперь просто освободим память и список преобразуется в такой:
...->+------+ |------>+------+
| data | | | data |
+------+ | +------+
| next | | | next |
| -----------| | | ------------...
+------+ | | +------+
prev | | nxt
| |
|------|
Случай удаления последнего элемента, является частным от удаления среднего, если предположить, что nxt = nil. А случай для удаления первого, если prev = nil. Процедура, которая выполняет всё описанное выше написана ниже :) При этом обратите внимание, что в момент входа в процедуру list указывает на элемент, который предшествует удаляемому (т.е. условно list = prev)
procedure Delete;
var
l : plist;
begin
if start = nil then
exit; { список пуст - удалять нечего }
l := list^.next; { теперь l указыват на удаляемый элемент l = cur}
if list <> nil then
begin{ если удаляется не первый элемент }
list^.next := l^.next; { prev.next = nxt (или же prev.next = cur.next) }
Dispose (l){ Освобождаем память }
end
else
begin { удаляем первый элемент }
list := start^.next;
Dispose (start); { освобождаем память }
start := list { устанавляваем новое начало списка }
end
end;Теперь у нас есть довольно мощный арсенал для работы со списком. Мы можем заполнить список с помощью Add, очистить его Clean, найти нужный элемент Search и удалить его .... или нет удалить его сразу мы не можем. Ведь после выполнения Search list указывает на найденный элемент, а для выполнения Delete нам в list нужен указатель на предыдущий. Надо бы написать ещё процедуру, которая бы находила элемент предшествующий данному. Это и будет домашним заданием. Написать процедуру findPrior, которая ищет элемент списка, предшествующий list.... после её выполнения именно list и должен указывать на этот элемент (что бы потом проще было вызывать Delete). Так же было бы не плохо (а вернее очень хорошо) написать процедуру для добавления элемента в начало списка. Ниже я привёл пример работы со связанным списком. Это просто все процедуры описанные выше + маленькая менюшка. Естественно не хватает процедуры findPrior. Поэтому не пытайтесь что-то удалять пока не напишите её. colspan
