end;
Рассмотрим процедуру вставки нового элемента в список в позицию, зависящую от значения информационного поля нового элемента. Такой алгоритм наполнения списка повлечет за собой его упорядоченность. Очевидно, что в момент вставки нового элемента нужно рассмотреть четыре ситуации, связанные со следующими состояниями списка:
1. пустой список; в этом случае для вставки первого элемента потребуется лишь скопировать содержимое ссылки на начало списка в связывающее поле записи и после этого скопировать ссылку на запись в область памяти, которая указывает на начало списка;
2. список не пуст, а из сравнения информационных полей элементов списка с соответствующим полем нового элемента следует, что его нужно вставить в начало; в этом случае применяется последовательность действий, описанная в п. 1;
3. список не пуст, а элемент нужно вставить в конец; в этой ситуации необходимо скопировать ссылку на новую запись в связывающее поле записи, стоящей в данный момент в конце списка, затем положить значение связываемого поля новой записи равным nil;
4. список не пуст, а элемент необходимо вставить между двумя элементами списка; здесь необходимо скопировать значение связующего поля того элемента, который должен предшествовать новому в поле связи нового элемента, а затем скопировать ссылку на новый элемент в связующем поле того элемента, который должен предшествовать новому в списке.
Данные четыре операции покроются тремя вариантами вставки: в начало списка, в конец списка и между двумя элементами списка. Общий алгоритм процедуры должен выглядеть следующим образом (ниже Тек_Ссылка означает ссылку на текущий элемент, а Пред_Ссылка √ значение ссылки на предшествующий):
1. Установить значение Тек_Ссылка так, чтобы оно указывало на начало списка, положить значение Пред_Ссылка = nil и установить признак того, что положение вставляемого элемента не определено.
2. Пока в списке остаются еще не просмотренные элементы и положение нового элемента не определено выполнять следующее: - если новый элемент следует за тем, на который указывает Тек_Ссылка, то положить значение Пред_Ссылка равным Тек_Ссылка и изменить значение Тек_Ссылка так, чтобы оно указывало на следующий элемент; - иначе установить признак того, что положение вставляемого элемента не определено.
3. Если Пред_Ссылка= nil, то вставить элемент в начало списка. Если и Пред_Ссылка и Тек_Ссылка не равны nil, то вставить новый элемент между теми элементами, на которые указывают Пред_Ссылка и Тек_Ссылка. Если Пред_Ссылка не равна nil, а Тек_Ссылка= nil, то вставить новый элемент в конец списка.
procedure InclWithSort( NewElem: DynStr; var HeadOfStr: Pointer);
var
CurrAssoc, PredAssoc: DynStr; {соответственно Тек_Ссылка и Пред_Ссылка}
IsFounded: Boolean;
begin
CurrAssoc:= HeadOfStr;
PredAssoc:= nil;
IsFounded:= False;
while ( CurrAssoc <> nil ) and not IsFounded do begin
if NewElem^.Elem > CurrAssoc^.Elem then begin
{перейти к следующему элементу}
PredAssoc:= CurrAssoc;
CurrAssoc:= CurrAssoc^.NextElem
end
else IsFounded:= True
{позиция вставки нового элемента найдена}
if PredAssoc= nil then begin
{вставка нового элемента в начало списка}
NewElem^.NextElem:= HeadOfStr;
HeadOfStr:= NewElem
if ( PredAssoc <> nil ) and ( CurrAssoc <> nil ) then begin
{вставка элемента между элементами, на которые указывают ссылки PredAssoc
CurrAssoc}
NewElem^.NextElem:= PredAssoc^.NextElem;
PredAssoc^.NextElem:= NewElem
if ( PredAssoc <> nil ) and ( CurrAssoc= nil ) then begin
{вставка в конец списка}
PredAssoc^.NextElem:= NewElem;
NewElem^.NextElem:= nil
Линейный список неудобен тем, что при попытке вставить некоторый элемент перед текущим элементом, требуется обойти почти весь список, начиная с заголовка, чтобы изменить значение указателя в предыдущем элементе списка. Чтобы устранить данный недостаток вводится второй указатель в каждом элементе списка. Первый указатель связывает данный элемент со следующим, а второй √ с предыдущим. Такая организация динамической структуры данных получила название линейного двунаправленного списка (двусвязного списка). На рис. 2 приведена графическая интерпретация двунаправленного списка.
Интересным свойством такого списка является то, что для доступа к его элементам вовсе не обязательно хранить указатель на первый элемент. Достаточно иметь указатель на любой элемент списка. Первый элемент всегда можно найти по цепочке указателей на предыдущие элементы, а последний - по цепочке указателей на следующие. Но наличие указателя на заголовок списка в ряде случаев ускоряет работу со списком
Линейные списки характерны тем, что в них можно выделить первый и последний элементы, причем для однонаправленного линейного списка обязательно нужно иметь указатель на первый элемент. Циклические списки также как и линейные бывают однонаправленными и двунаправленными. Основное отличие циклического списка состоит в том, что в списке нет пустых указателей (см. рис 3).
Последний элемент списка содержит указатель, связывающий его с первым элементом. Для полного обхода такого списка достаточно иметь указатель только на текущий элемент.
В двунаправленном циклическом списке система указателей аналогична системе указателей двунаправленного линейного списка (см. рис 4).
Двунаправленный циклический список позволяет достаточно просто осуществлять вставки и удаления элементов слева и справа от текущего элемента. В отличие от линейного списка, элементы являются равноправными и для выделения первого элемента необходимо иметь указатель на заголовок. Однако во многих случаях нет необходимости выделять первый элемент списка и достаточно иметь указатель на текущий элемент.
Разберем решение типичной задачи, связанной с обработкой списков.
Текст задания
С использованием списков, заданный во входном файле текст (за которым следует точка) распечатать в обратном порядке.
Решение
program reverse;
type List= ^Elem;
Elem= record
Info: Char;
Next: List
L, p: List;
c: char;
{ввод литер текста и запись их в обратном порядке в список L (без заглавного звена)}
L:= nil; {ссылка на построенную часть списка}
read( c );
while c <> '.' do begin
{добавить с в начало списка}
new( p );
p^.Info:= c;
p^.Next:= L;
L:= p;
read( c )
{печать литер из L}
while L <> nil do begin
write( L^.Info );
L:= L^.Next
writeln
end.
Очередь и стек представляют собой структуры данных с фиксированными механизмами занесения и выбора элементов. Возможны реализации очереди и стека на базе регулярных или списковых структур данных. Соответственно представлению изменяется реализация механизмов обработки структур. Однако определяющими являются следующие принципы: очередь предполагает занесение нового элемента в конец, а выбор с начала списка (FIFO √ First In First Out); в стек элемент заносится в начало и выбирается также сначала (LIFO √ Last In First Out).
Из механизма FIFO следует, что в очереди доступны два элемента √ первый и последний простая очередь (см. рис. 5).
Структура данных, представляющая очередь, могла бы выглядеть следующим образом:
type
TypeOfElem= {};
Assoc= ^ElementOfQueue;
ElementOfQueue= record
Elem: TypeOfElem;
NextElem: Pointer
Queue= Assoc;
Для создания новой пустой или очистки существующей очереди достаточно присвоить указателям на первый и последний элементы значение nil.
procedure CreateQueue ( var FirstElem, LastElem: Queue);
FirstElem:= nil;
LastElem:= nil
Условием пустоты очереди является значения указателей на первый и последний элементы, равные nil.
function QueueIsClear( var FirstElem, LastElem: Queue ): Boolean;
QueueIsClear:= ( FirstElem= nil ) and ( LastElem= nil )
Для включения элемента в очередь, необходимо создать новый элемент типа очередь, затем инициализировать его информационное поле. В заключение изменить его указатель и указатель на последний элемент очереди так, чтобы последним стал новый элемент.
procedure IncludeInQueue( var FirstElem, LastElem: Queue; NewElem: TypeOfElem);
ServiceVar: Queue;
{создание нового элемента}
new( ServiceVar );
ServiceVar^.Elem:= NewElem;
ServiceVar^.NextElem:= nil;
if ( FirstElem= nil ) and ( LastElem= nil ) then begin
{создать очередь из одного элемента}
FirstElem:= ServiceVar;
LastElem:= ServiceVar
else begin
{созданный элемент поместить в конец очереди}
Страницы: 1, 2, 3, 4, 5
