Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Симметричный двунаправленный список



 

Наиболее удобной в двунаправленном списке является та организация ссылок, при которой движение, перебор элементов в обратном направлении является строго противоположным перебору элементов в прямом направлении. Такой двунаправленный список называется симметричным.Например, в прямом направлении элементы линейного списка пронумерованы и выбираются так: 1, 2, 3, 4, 5. Строго говоря, перебирать элементы в обратном направлении можно по-разному, соответствующим способом организуя ссылки, например: 4, 1, 5, 3, 2. Симметричным же будет называться список, реализующий перебор элементов в таком порядке: 5, 4, 3, 2, 1.

 

Следует заметить, что «обратный» список, так же, как и прямой, является просто линейным однонаправленным списком, который заканчивается элементом со ссылкой, имеющей значение nil. Для удобства работы со списком в обратном направлении и в соответствии с идеологией однонаправленного списка нужен доступ к первому в обратном направлении элементу. Такой доступ осуществляется с помощью указателя LAST («говорящее» имя) на этот первый в обратном направлении элемент.Структура линейного двунаправленного симметричного списка дана на рис. 19 .

 

Как указывалось ранее, замкнутый, циклический, кольцевой список организован таким образом, что в адресную часть конечного элемента вместо константы nil помещается адрес начального элемента (список замыкается сам на себя). В симметричном кольцевом списке такое положение характерно для обоих - прямого и обратного - списков, следовательно, можно построить циклический двунаправленный список (см. рис. 20 ) .


 


Описание элементов списков

Элементоднонаправленного списка

 

Описать структуру условного элемента однонаправленного списка (см. рис 1) можно следующим образом:

Type

point=^zap;

zap=record

nf1 : integer; { первое информационное поле }

inf2 : string; { второе информационное поле }

next : point; {ссылочное поле }

end;

 

Из этого описания видно, что имеет место рекурсивная ссылка: для описания типа point используется тип zap, а при описании типа zapиспользуется тип point. По соглашениям Паскаля в этом случае сначала описывается тип «указатель», а затем уже тип связанной с ним переменной. Правила Паскаля только при описании ссылок допускают использование идентификатора (zap) до его описания. Во всех остальных случаях, прежде чем упомянуть идентификатор, необходимо его определить.

 

Элементдвунаправленного списка

 

В случае двунаправленного списка в описании должно появиться еще одно ссылочное поле того же типа, например,

 

Type

point=^zap;

zap=record

inf1 : integer; { первое информационное поле }

inf2 : string; { второе информационное поле }

next:point; {ссылочное поле на следующий элемент}

prev:point; {ссылочное поле на предыдущий элемент}

end;

 

 

Как уже отмечалось, последовательность обработки элементов списка задается системой ссылок. Отсюда следует важный факт: все действия над элементами списка, приводящие к изменению порядка обработки элементов списка - вставка, удаление, перестановка - сводятся к действиям со ссылками.Сами же элементы не меняют своего физического положения в памяти.

При работе со списками любых видов нельзя обойтись без указателя на первый элемент. Не менее полезными, хотя и не всегда обязательными, могут стать адрес последнего элемента списка и количество элементов. Эти данные могут существовать по отдельности, однако их можно объединить в единую структуру типа «запись» (из-за разнотипности полей: два поля указателей на элементы и числовое поле - для количества элементов). Эта структура и будет представлять так называемый головной элемент списка.

 

Type

hd_el =^ head_elem;

head_elem=record

First:el; {ссылочное поле на первый элемент списка}

prev: el; {ссылочное поле на последний элемент списка}

n : integer; { количество элементов списка }

inf : string; { необязательное поле

с произвольной информацией }

end;

Var

hd : hd_el;

Следуя идеологии динамических структур данных, головной элемент списка также необходимо сделать динамическим, выделяя под него память при создании списка и освобождая после окончания работы. Тем не менее, стоит отметить, что головной элемент может быть и статического типа. Тогда он описывается в разделе VAR как обычная переменная типа RECORD соответствующей структуры.

 

hd := nil;

. . .

new ( hd );

. . .

 

 

Использование данных головного элемента делает работу со списком более удобной, но требует определенных действий по его обслуживанию.

 

Рассмотрим основные процедуры работы с линейным однонаправленным списком без головного элемента. Действия оформлены в виде процедур или функций в соответствии с основными требованиями модульного программирования (см. соответствующий раздел пособия).

 

Приведем фрагменты разделов Type и Var, необходимые для дальнейшей работы с линейным однонаправленным списком без головного элемента.

 

 

Type

el = ^zap;

zap=record

inf1 : integer;{ первое информационное поле }

inf2 : string; { второе информационное поле }

next : el; {ссылочное поле }

end;

Var

first, { указатель на первый элемент списка }

p, q , t : el; { рабочие указатели, с помощью которых

будет выполняться работа с элементами списка }

 

 


 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.