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;


Информация о работе «Ссылочные типы. Динамические переменные»
Раздел: Информатика, программирование
Количество знаков с пробелами: 37264
Количество таблиц: 2
Количество изображений: 8

Похожие работы

Скачать
10828
0
0

... ссылочного типа:  <задание ссылочного типа>::= ^<имя типа> ^ - признак ссылочного типа; <имя типа> - имя стандартного либо описанного ранее типа. Это тип динамических объектов, которые может представлять переменная ссылочного типа. Надо подчеркнуть , что здесь может быть только имя типа.  Сами переменные ссылочного типа вводятся обычным образом. type массив = array ...

Скачать
274963
85
0

... ячейка, а имя переменной превращается в адрес ячейки. Появление этого адреса происходит в результате работы специального оператора языка (NEW), однако его значение в большинстве случаев не используется при программировании на алгоритмических языках типа Паскаль. Условимся считать, что адрес ячейки, которая будет хранить переменную А, есть А. Или, другими словами, А - это общее имя переменной и ...

Скачать
94620
8
0

... Закрыть программу можно нажатием на кнопку «Закрыть» или F10. Заключение В квалификационной работе мы попытались раскрыть более полно и наглядно понятие линейного списка, однонаправленного и двунаправленного списков, стека, дека и очереди. Сформировать и закрепить познавательный интерес к данной теме у учащихся. Выявлять и развивать творческие способности в использовании полученного навыка при ...

Скачать
19204
5
5

... "nсреднее целое равно " << MidInt / double(NMax) << "n"; cout << "среднее вещественное равно: " << MidReal / n << "n"; fclose(t); } Списки Обсудим вопрос о том, как в динамической памяти можно создать структуру данных переменного размера. Разберем следующий пример. В процессе физического эксперимента многократно снимаются показания прибора (допустим, термометра) ...

0 комментариев


Наверх