Переменные типа «указатель» обычно используют при реализации динамических структур данных. Динамические структуры данных могут быть организованы линейно, в виде дерева и в виде сети.
Линейная динамическая структура представляет собой изменяемую последовательность элементов. Частными случаями таких структур являются:
· стеки, в которых разрешено добавлять элементы только в конец и удалять только последние элементы (рис. 7а);
· очереди, в которых добавление элементов осуществляется в конец, а удаление – из начала (рис. 7б);
· деки, которые допускают добавление и удаление элементов и с начала и с конца (рис. 7в);
В древовидной структуре каждый элемент (вершина) ссылается на один и более элементов следующего уровня (рис.7г). В сетевой структуре никаких ограничений на связи элементов не накладывается (рис. 7д).
Рис. 7
Линейные динамические структуры, такие как стеки, очереди и деки, при известном максимальном количестве элементов можно реализовать в виде динамических или статических одномерных массивов. В противном случае, а также для представления остальных структур (древовидной и сетевой) используют списки.
Списком называют структуру, в которой помимо данных хранятся также адреса элементов. Элемент списка состоит из двух частей: информационной, содержащей данные, и адресной, где хранятся указатели на следующие элементы. В зависимости от количества полей в адресной части и порядка связывания элементов различают линейные односвязные списки и линейные двусвязные списки.
Линейные односвязные списки – единственное адресное поле содержит адрес следующего элемента, если следующий элемент отсутствует, то в адресное поле заносят константу nil. Ниже приведена структура односвязного списка (рис.8), т.е. связь идет от одного элемента списка к другому в одном направлении. Здесь поле D – это информационное поле, в котором находятся данные (любой допустимый в языке Паскаль тип), поле N (Next) – указатель на следующий элемент списка.
Каждый список должен иметь следующие указатели: Head – голова списка, Cur – текущий элемент списка, иногда в односвязных списках также используется указатель Tail – хвост списка (в двусвязных списках он используется всегда). Поле указателя последнего элемента списка является пустым, в нем находится специальный признак nil, свидетельствующий о конце списка и обозначается перечеркнутым квадратом.
Для описания элементов списка используют записи, например, элемент односвязного списка с двумя информационными полями и одним адресным полем может быть описан следующим образом:
Type pe=^element; {тип указатель}
element=record
name:string[16]; {информационное поле 1}
telefon:string[15]; {информационное поле 2}
p:pe; {адресное поле}
end;
Односвязный список отличается тем, что пройти по нему можно только в одном направлении — от начала в конец списка. Это оказывается достаточно неудобно, поэтому гораздо большее распространение получили двусвязные списки.
Линейные двусвязные списки – каждый элемент содержит адреса предыдущего и последующего элементов, соответственно, первый элемент в качестве адреса предыдущего, а последний – в качестве адреса следующего элемента содержит nil (рис. 9).
Элемент двусвязного списка описывается двумя адресными полями, например:
Type pe=^element; {тип указатель}
element=record
name:string[16]; {информационное поле 1}
telefon:string[15]; {информационное поле 2}
back:pe; {адресное поле «предыдущий»}
next:pe; {адресное поле «следующий»}
end;
У любого списка имеется хотя бы один указатель, размещенный в статической памяти, который содержит адрес первого элемента списка или константу nil, если список пуст. Достаточно часто используют дополнительные указатели, в которых хранят адреса других элементов, например, адрес текущего элемента, адрес последнего элемента и т.п. Эти указатели также описываются как «указатели на элемент», например:
Var first, last, q:pe;
В процессе выполнения программы динамические структуры создаются, обрабатываются и уничтожаются.
Линейные списки в отличие от одномерных массивов позволяют:
· работать с произвольным количеством элементов, добавляя и удаляя их по мере необходимости;
· осуществлять вставку и удаление записей, не перемещая остальные элементы последовательности.
Операции вставки и удаления требуют модификации указателей максимум у трех узлов: узла, над которым выполняется операция, и двух окружающих узлов. Схематично эти операции и изменения значений указателей показаны на рис. 10.
 |
Рис.10
Недостатком этих структур является то, что при поиске элемента по номеру приходится просматривать все ранее расположенные элементы, в то время как в одномерном массиве возможен прямой доступ к элементу по индексу.
При работе с линейными списками используются основные операции:
· создание списка;
· добавление нового элемента в список: в голову списка, в хвост списка, после текущего элемента списка, перед текущим элементом списка;
· удаление элемента из списка;
· обход списка с целью его обработки;
· поиск узла в списке;
· переход на узел в списке по номеру от начала и другие операции.
Рассмотрим некоторые из этих операций для линейного двусвязного списка, содержащего следующую информацию: фамилия студента, группа, стипендия.
Описание:
Type
tstud=record
fam:string[30];
group:string[10];
stip:real;
end;
Node=^List; //узел списка – это есть указатель на список
List=record
Info:tstud;
Back:Node; //Указатель на предыдущий элемент списка
Next:Node; //Указатель на следующий элемент списка
end;
Var
t, h,cur:node; st:tstud;
Создание списка. При создании списка нужно выполнить следующие действия (рис.11):
· выделить память;
· «обнулить» указатели на предыдущий и последующий элементы;
· определить указатели на голову, хвост и текущий элемент списка;
· внести в информационную часть списка данные.
 |
Рис. 11
Function CreateList(st:tstud; Var H,T,C: Node): Node;
Var p: Node;
Begin
New(p);
p^.next:=nil;p^.back:=nil;
H:=p;T:=p;C:=p;
p^.Info.fio:=st.fio;
p^.Info.group:=st.group;
p^.Info.stip:=st.stip;
CreateList:=p;
End;
В результате выполнения этой функции будет создан список, содержащий одну запись.