Навигация
2.2 Двунаправленные списки
Линейный список неудобен тем, что при попытке вставить некоторый элемент перед текущим элементом, требуется обойти почти весь список, начиная с заголовка, чтобы изменить значение указателя в предыдущем элементе списка. Чтобы устранить данный недостаток вводится второй указатель в каждом элементе списка. Первый указатель связывает данный элемент со следующим, а второй √ с предыдущим. Такая организация динамической структуры данных получила название линейного двунаправленного списка (двусвязного списка). На рис. 2 приведена графическая интерпретация двунаправленного списка.
Интересным свойством такого списка является то, что для доступа к его элементам вовсе не обязательно хранить указатель на первый элемент. Достаточно иметь указатель на любой элемент списка. Первый элемент всегда можно найти по цепочке указателей на предыдущие элементы, а последний - по цепочке указателей на следующие. Но наличие указателя на заголовок списка в ряде случаев ускоряет работу со списком
2.3 Циклические списки
Линейные списки характерны тем, что в них можно выделить первый и последний элементы, причем для однонаправленного линейного списка обязательно нужно иметь указатель на первый элемент. Циклические списки также как и линейные бывают однонаправленными и двунаправленными. Основное отличие циклического списка состоит в том, что в списке нет пустых указателей (см. рис 3).
Последний элемент списка содержит указатель, связывающий его с первым элементом. Для полного обхода такого списка достаточно иметь указатель только на текущий элемент.
В двунаправленном циклическом списке система указателей аналогична системе указателей двунаправленного линейного списка (см. рис 4).
Двунаправленный циклический список позволяет достаточно просто осуществлять вставки и удаления элементов слева и справа от текущего элемента. В отличие от линейного списка, элементы являются равноправными и для выделения первого элемента необходимо иметь указатель на заголовок. Однако во многих случаях нет необходимости выделять первый элемент списка и достаточно иметь указатель на текущий элемент.
Разберем решение типичной задачи, связанной с обработкой списков.
Текст задания
С использованием списков, заданный во входном файле текст (за которым следует точка) распечатать в обратном порядке.
Решение
program reverse;
type List= ^Elem;
Elem= record
Info: Char;
Next: List
end;
var
L, p: List;
c: char;
begin
{ввод литер текста и запись их в обратном порядке в список L (без заглавного звена)}
L:= nil; {ссылка на построенную часть списка}
read( c );
while c <> '.' do begin
{добавить с в начало списка}
new( p );
p^.Info:= c;
p^.Next:= L;
L:= p;
read( c )
end;
{печать литер из L}
while L <> nil do begin
write( L^.Info );
L:= L^.Next
end;
writeln
end.
3. Очереди и стеки
Очередь и стек представляют собой структуры данных с фиксированными механизмами занесения и выбора элементов. Возможны реализации очереди и стека на базе регулярных или списковых структур данных. Соответственно представлению изменяется реализация механизмов обработки структур. Однако определяющими являются следующие принципы: очередь предполагает занесение нового элемента в конец, а выбор с начала списка (FIFO √ First In First Out); в стек элемент заносится в начало и выбирается также сначала (LIFO √ Last In First Out).
3.1 Очередь на базе списка
Из механизма FIFO следует, что в очереди доступны два элемента √ первый и последний простая очередь (см. рис. 5).
Структура данных, представляющая очередь, могла бы выглядеть следующим образом:
type
TypeOfElem= {};
Assoc= ^ElementOfQueue;
ElementOfQueue= record
Elem: TypeOfElem;
NextElem: Pointer
end;
Queue= Assoc;
3.2 Создание (очистка) очереди
Для создания новой пустой или очистки существующей очереди достаточно присвоить указателям на первый и последний элементы значение nil.
procedure CreateQueue ( var FirstElem, LastElem: Queue);
begin
FirstElem:= nil;
LastElem:= nil
end;
3.3 Проверка очереди на пустоту
Условием пустоты очереди является значения указателей на первый и последний элементы, равные nil.
function QueueIsClear( var FirstElem, LastElem: Queue ): Boolean;
begin
QueueIsClear:= ( FirstElem= nil ) and ( LastElem= nil )
end;
3.4 Включение элемента в очередь
Для включения элемента в очередь, необходимо создать новый элемент типа очередь, затем инициализировать его информационное поле. В заключение изменить его указатель и указатель на последний элемент очереди так, чтобы последним стал новый элемент.
procedure IncludeInQueue( var FirstElem, LastElem: Queue; NewElem: TypeOfElem);
var
ServiceVar: Queue;
begin
{создание нового элемента}
new( ServiceVar );
ServiceVar^.Elem:= NewElem;
ServiceVar^.NextElem:= nil;
if ( FirstElem= nil ) and ( LastElem= nil ) then begin
{создать очередь из одного элемента}
FirstElem:= ServiceVar;
LastElem:= ServiceVar
end
else begin
{созданный элемент поместить в конец очереди}
LastElem^.NextElem:= ServiceVar;
LastElem:= ServiceVar
end
end;
Похожие работы
... ссылочного типа: <задание ссылочного типа>::= ^<имя типа> ^ - признак ссылочного типа; <имя типа> - имя стандартного либо описанного ранее типа. Это тип динамических объектов, которые может представлять переменная ссылочного типа. Надо подчеркнуть , что здесь может быть только имя типа. Сами переменные ссылочного типа вводятся обычным образом. type массив = array ...
... ячейка, а имя переменной превращается в адрес ячейки. Появление этого адреса происходит в результате работы специального оператора языка (NEW), однако его значение в большинстве случаев не используется при программировании на алгоритмических языках типа Паскаль. Условимся считать, что адрес ячейки, которая будет хранить переменную А, есть А. Или, другими словами, А - это общее имя переменной и ...
... Закрыть программу можно нажатием на кнопку «Закрыть» или F10. Заключение В квалификационной работе мы попытались раскрыть более полно и наглядно понятие линейного списка, однонаправленного и двунаправленного списков, стека, дека и очереди. Сформировать и закрепить познавательный интерес к данной теме у учащихся. Выявлять и развивать творческие способности в использовании полученного навыка при ...
... "nсреднее целое равно " << MidInt / double(NMax) << "n"; cout << "среднее вещественное равно: " << MidReal / n << "n"; fclose(t); } Списки Обсудим вопрос о том, как в динамической памяти можно создать структуру данных переменного размера. Разберем следующий пример. В процессе физического эксперимента многократно снимаются показания прибора (допустим, термометра) ...
0 комментариев