Использование указателей для обработки списков
Указатели оказываются незаменимыми в задачах, связанных с добавлением и корректировкой данных в структурно организованных системах данных. Дело в том, что хранение данных в массивах наталкивается на серьезные технические трудности. Добавление данных возможно только вконец массива. Если играет роль порядок данных, то при вставке элемента в середину массива необходимо сдвинуть все остальные элементы. Это очень неудобно или даже невозможно, если номера данных по одному массиву используются в других массивах.
Существует другая возможность описывать упорядоченную последовательность данных - списком. В наборе технологических средств программирования списком называется совокупность однотипных упорядоченнных данных, снабженных средствами, позволяющими переходить от предыдущего значения к последующему. Наиболее естественно обеспечивается переход с помощью указателей. Именно, элемент списка будет состоять из двух частей: первая часть состоит из содержательных данных списка, а вторая часть представляет собой указатель, ссылающийся на следующий элемент списка. Указатель на первый элемент списка хранится в фиксированной переменной. Если он неопределенный (равен Nil), то список пуст. Указатель следующего элемента в последнем элементе списка равен Nil. Общая схема списка такова:
Описание элемента списка в Паскале имеет одну особенность, которую мы поясним на примере. Пусть сами данные описываются как запись типа rec. Тогда элемент списка будет записью из двух полей: одно типа rec и другое типа указатель на элемент списка.
type
rec = record <поля данных> end; {запись данных}
plist = ^list; {тип указателя на элемент списка }
list = record {тип элемента списка}
d: rec; {данные списка}
p: plist {ссылка на следующий элемент}
end;
var p0: plist; {ссылка на первый элемент списка}
Особенность вышеприведенного описания в том, что при определении типа указателя с именем plist
испоьзуется тип list, определяемый ниже в тексте программы, а не выше, как того требует фундаментальное правило Паскаля. Разобранный случай - это единственное исключение из этого правила.
Список, устроенный так, как это было описано выше, называется линейным однонаправленным (или односвязным) списком. При работе с таким списком можно выделить три основные функции:
- поиск элемента списка по критерию;
- добавление элемента внутрь списка;
- удаление элемента из списка.
Пусть функция: {function order (r1,r2: rec): integer;} возвращает -1, 0 или +1 в зависимости от того, предшествует, совпадает или следует запись r1 за записью r2
(порядок следования зависит от полей записи). Тогда поиск в линейном списке записи r заключается в последовательном переборе элементов списка и сравнении записи r с полем d элемента списка. Перебор начинается с элемента p0^ и заканчивается тогда, когда order(r,d)=0 (запись найдена), либо order(r,d)=1 (нужной записи не существует), либо указатель на следующую запись равен Nil (список кончился).
function find_in_list (r: rec): plist; {возвращает указатель на элемент, Nil - неудача}
var next: plist;
begin
find_in_list := Nil;
next := po; {Первый элемент списка}
while (next<>Nil) and (order (r, next^.d) >= 0) do
{Cписок не кончился и исходная запись больше текущей}
if order (r, next^.d) = 0
then begin find_in_list := next; break end {Записи совпадают}
else next := next.p; {исходная больше текущей; продолжить поиск}
end;
Для того, чтобы добавить элемент в список, необходимо вначале определить его местоположение в списке (найти элемент до и элемент после).
В модифицированном списке элемент до должен указывать на вставленный элемент, а вставленный - на элемент после. Алгоритм обязан правильно обрабатывать случаи, когда элемент вставляется в начало или конец списка. Обратите внимание, что в процедуре вставки используется указатель на указатель, что совершенно законно.
procedure include_in_list (r: rec);
var next,curr: plist; prev: ^plist;
begin
next := po; {Первый элемент списка}
prev := @p0; {Сcылка на указатель первого элемента}
while (next<>Nil) and (order (r, next^.d) >= 0) do begin
prev := @(next.p); {Сcылка на указатель в предыдущем элементе}
next := next.p {Переход к следующему элементу}
end; {Cписок кончился или последняя запись предшествует текущей}
new (curr); {Создание копии элемента списка}
curr^.d := r; {Заполнение элемента}
curr^.p := prev^; {Ссылка последующий элемент списка}
prev^ := curr; {Ссылка в прдыдущем элементе на новый}
end;
Для того, чтобы удалить элемент из списка, необходимо вначале определить его местоположение в списке (найти элемент до и элемент после). В модифицированном списке элемент до должен указывать на элемент после. Здесь тавже надо следить за правильностью удаления первого и последнего элемента.
function exclude_from_list (r: rec): boolean;
var next: plist; prev: ^plist;
begin
exclude_from_list := false;
next := po; {Первый элемент списка}
prev := @p0; {Сcылка на указатель первого элемента}
while (next<>Nil) and (order (r, next^.d) <= 0) do
if order (r, next^.d) = 0 {Уничтожить элемент списка}
then begin prev^ := next.p; {Ссылка в прдыдущем элементе на последующий}
dispose (next); {Освободить ненужную память}
exclude_from_list := true; {Элемент удален}
break
end
else begin prev := @(next.p); {Сcылка на указатель в предыдущем элементе}
next := next.p {Переход к следующему элементу}
end
end;
Кольцевой список отличается от линейного тем, что в нем указатель в последнем элементе не равен Nil, а указывает на первый элемент, то есть ссылки замыкают список в кольцо. Кольцевой список позволяет производить поиск не только с первого, но и с любого элемента. Процедуры поиска, добавления и уничтожения в кольцевом списке несколько отличаются за счет проверки условия окончания поиска (next <> p0 вместо next <> Nil).
Если в задаче необходимо двигаться по списку в обоих направлениях, используются двунаправленные (двусвязные) списки. Элемент линейного двунаправленного списка кроме ссылки на последующий элемент содержит ссылку на предыдущий элемент. Двунаправленный список также можно замкнуть в двунаправленное кольцо. Процедуры поиска, добавления и уничтожения для двунаправленного списка в основных чертах повторяют процедуры для обычного списка.
