Линейные списки
Наиболее простой способ связать некоторое множество элементов - это организовать линейный список. При такой организации элементы некоторого типа образуют цепочку. Для связывания элементов в списке используют систему указателей. В рассматриваемом случае любой элемент линейного списка имеет один указатель, который указывает на следующий элемент в списке или является пустым указателем, что означает конец списка.
Рис. 1.1. Линейный список (связанный список)
В языке Turbo Pascal предусмотрены два типа указателей v типизированные и не типизированные указатели. В случае линейного списка описание данных может выглядеть следующим образом.
type
element = record
data:string;
next: pointer;
end;
var
head: pointer;
current, last : ^element;
В данном примере элемент списка описан как запись, содержащая два поля. Поле data строкового типа служит для размещения данных в элементе списка. Другое поле next представляет собой не типизированный указатель, который служит для организации списковой структуры.
В описании переменных описаны три указателя head, last и current. Head является не типизированным указателем. Указатель current является типизированным указателем, что позволяет через него организовать доступ к полям внутри элемента, имеющего тип element. Для объявления типизированного указателя обычно используется символ ^, размещаемый непосредственно перед соответствующим типом данных. Однако описание типизированного указателя еще не означает создание элемента списка. Рассмотрим, как можно осуществить создание элементов и их объединение в список.
В системе программирования Turbo Pascal для размещения динамических переменных используется специальная область памяти heap-область¦.
Heap-область размещается в памяти компьютера следом за областью памяти, которую занимает программа и статические данные, и может рассматриваться как сплошной массив, состоящий из байтов.
Попробуем создать первый элемент списка. Это можно осуществить при помощи процедуры New
New(Current);
После выполнения данной процедуры в динамической области памяти создается динамическая переменная, тип которой определяется типом указателя. Сам указатель можно рассматривать как адрес переменной в динамической памяти. Доступ к переменной может быть осуществлен через указатель. Заполним поля элемента списка.
Current^.data:= -данные в первом элементе списка - ;
Сurrent^.next:=nil;
Значение указателя nil означает пустой указатель. Обратим внимание на разницу между присвоением значения указателю и данным, на которые он указывает. Для указателей допустимы только операции присваивания и сравнения. Указателю можно присваивать значение указателя того же типа или константу nil. Данным можно присвоить значения, соответствующие декларируемым типам данных. Для того чтобы присвоить значение данным, после указателя используется символ ^. Поле Сurrent^.next само является указателем, доступ к его содержимому осуществляется через указатель Current.
В результате выполнения описанных действий мы получили список из одного элемента. Создадим еще один элемент и свяжем его с первым элементом.
Head:=Current;
New(last);
Last^.data:= -данные во втором элементе списка - ;
Last^.next:=nil;
Сurrent^.next:=nil;
Непосредственно перед созданием первого элемента мы присвоили указателю Head значение указателя Current. Это связано с тем, что линейный список должен иметь заголовок. Другими словами, первый элемент списка должен быть отмечен указателем. В противном случае, если значение указателя Current в дальнейшем будет переопределено, то мы навсегда потеряем возможность доступа к данным, хранящимся в первом элементе списка.
Динамическая структура данных предусматривает не только добавление элементов в список, но и их удаление по мере надобности.
Самым простым способом удаления элемента из списка является переопределение указателей, связанных с данным элементом (указывающих на него). Однако сам элемент данных при этом продолжает занимать память, хотя доступ к нему будет навсегда утерян. Для корректной работы с динамическими структурами следует освобождать память при удалении элемента структуры. В языке TurboPascal для этого можно использовать функцию Dispose. Покажем, как следует корректно удалить первый элемент нашего списка.
Head:=last;
Dispose(current);
Рассмотрим пример более сложной организации списка. Линейный список неудобен тем, что при попытке вставить некоторый элемент перед текущим элементом требуется обойти почти весь список, начиная с заголовка, чтобы изменить значение указателя в предыдущем элементе списка. Чтобы устранить данный недостаток введем второй указатель в каждом элементе списка. Первый указатель связывает данный элемент со следующим, а второй v с предыдущим. Такая организация динамической структуры данных получила название линейного двунаправленного списка (двусвязанного списка).
Рис.1.2. Двунаправленный список
Интересным свойством такого списка является то, что для доступа к его элементам вовсе не обязательно хранить указатель на первый элемент. Достаточно иметь указатель на любой элемент списка. Первый элемент всегда можно найти по цепочке указателей на предыдущие элементы, а последний - по цепочке указателей на следующие. Но наличие указателя на заголовок списка в ряде случаев ускоряет работу со списком.
Приведем пример программы, которая выполняет следующие операции с двунаправленным линейным списком:
добавление (справа и слева от текущего);
удаление (справа и слева от текущего);
поиск;
вывод списка.
program;
type element = record
data:string;
last, next: pointer;
end;
var
i,n: integer;
head: pointer;
current, pnt, pnt2: ^element;
s:string;
begin
new(current);
head:=current;
current^.data:=head;
current^.next:=nil;
current^.last:=nil;
repeat
writeln(-1 v сделать текущим-);
writeln(-2 v список элементов-);
writeln(-3 v добавить справа-);
writeln(-4 v добавить слева-);
writeln(-5 v удалить текущий-);
writeln(-6 v удалить справа от текущего-);
writeln(-7 v удалить слева от текущего-);
writeln(-0 v выход-);
writeln(-текущий элемент: -, current^.data);
readln(n);
if n=1 then
{Выбор нового текущего элемента}
begin
writeln(--); readln(s);
pnt:=head;
repeat
if pnt^.data=s then current:=pnt;
pnt:=pnt^.next;
until pnt=nil;
end;
if n=2 then
{Вывод всех элементов}
begin
pnt:=head; i:=1
repeat
writeln(i, - v -, pnt^.data);
pnt:=pnt^.next;
i:=i+1;
until pnt=nil;
end;
if n=3 then
{ Добавление нового элемента справа от текущего}
begin
writeln(-элемент-); readln(s);
new(pnt);
pnt^.data:=s;
pnt^.last:=current;
pnt^.next:=current^.next;
pnt2:=current^.next;
if not(pnt2=nil) then pnt2^.last:=pnt;
end;
if n=4 then
{Добавление нового элемента слева от текущего}
begin
writeln(-элемент-); readln(s);
new(pnt);
pnt^.data:=s;
pnt^.last:=current^.last;
pnt^.next:=current;
pnt2:=current^.last;
if not(pnt2=nil) then pnt2^.next:=pnt;
end;
if n=5 and not(current=head) then
{Удаление текущего элемента}
begin
pnt:=current^.last;
pnt^.next:=current^next;
pnt2:=current^.next;
if not(pnt2=nil) then pnt2^.last:=current^.last;
dispose(current);
end;
if n=6 and not(current^.next=nil) then
{ Удаление элемента справа от текущего}
begin
pnt:=current^.next;
current^.next:=pnt^next;
pnt2:=pnt^.next;
if not(pnt2=nil) then pnt2^.last:=current;
dispose(pnt);
end;
if n=7 and not(current^.last=head) and not(current^.last=nil) then
{Удаление элемента слева от текущего}
begin
pnt:=current^.last;
current^.last:=pnt^.last;
pnt2:=pnt^.last;
if not(pnt2=nil) then pnt2^.next:=current;
dispose(pnt);
end;
until n=0;
end.
В данной программе реализован алгоритм поиска элемента в списке (сделать текущим). В процессе поиска происходит обход с начала списка. Наличие указателя на заголовок списка ускоряет процесс поиска, так как не требуется сначала найти первый элемент, а затем - сделать обход списка.