русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Кольцевые списки


Дата добавления: 2013-12-23; просмотров: 5123; Нарушение авторских прав


 

Если значение указателя последнего звена линейного односвязного списка заменить с nil (или NULL) на адрес ведущего звена, то линейный список превратится в односвязный кольцевой список.

 

Для двусвязного списка, кроме того, нужно заменить с nil на адрес последнего звена значение второго указателя в ведущем звене. Получится двусвязный кольцевой (циклический) список.

 

В односвязном кольцевом списке можно переходить от последнего звена к заглавному, а в двусвязном - еще и от заглавного к последнему.

 

Двусвязный кольцевой список выглядит так:

Кольцевой список, как и линейный, идентифицируется как единый программный объект указателем, например L2, значением которого является адрес заглавного звена.

 

 

Возможен другой вариант организации кольцевого списка:

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

 

Рассмотрим операции с кольцевыми списками.

 

Отсутствие "последнего" звена приводит к ещё большему упрощению операций добавления и удаления, по сравнению с 1- и 2-связным линейным списком. Например, для 1-связного кольцевого списка в процедуре удаления отсутствует оператор if - проверка на существование звена, следующего за заданным (в кольцевом списке такое звено всегда есть). Такие же операторы отсутствуют в процедурах добавления и удаления звеньев для 2-связного кольцевого списка.

 

При циклической обработке кольцевого списка нужно учесть, что формально последнего звена нет.



Программа работы с двусвязным кольцевым списком на языке Паскаль

Type

rel2=^elem2;

elem2=record

next:rel1;

prev:rel2;

data:<Тип хранимых данных>

end;

list2=rel2;

 

procedure insert2(pred:rel2; info:<Тип>);

var

q:rel2;

begin

new(q); (* Создание нового звена *)

q^.data:=info;

q^.next:=pred^.next;

q^.prev:=pred^.next^.prev;

pred^.next.prev:=q;

pred^.next:=q

end;

 

При вставке в начало списка (после заглавного звена) нужно указать в качестве аргумента pred адрес заглавного звена, то есть указатель на список L2.

 

procedure delete2(del:rel2);

begin

del^.next^.prev:=del^.prev;

del^.prev^.next:=del^.next;

dispose(del);

end;

 

function search2(list:rel2; info:<Тип>; var point:rel2):boolean;

var

p,q:rel2;

b:boolean;

begin

b:=false;

point:=nil;

p:=list;

q:=p^.next;

while (p<>q) and (not b) do

begin

if q^.data=info then

begin

b:=true;

point:=q

end;

q:=q^.next

end;

search2:=b

end;

 

...

...

 

var

l2:list2;

r:rel2;

begin (* Создание заглавного звена *)

new(r);

r^.next:=r;

r^.pred:=r;

l2:=r;

 

...

...

 

end.

 

Процедуры работы с двусвязным кольцевым списком на языке Си++

 

Тип данных для кольцевого 2-связного списка такой же, как и для 2-связного линейного. То же самое справедливо для 1-связных списков. По типу звена списка нельзя судить о его архитектуре, можно - только о числе связей.

Добавление звена в произвольную позицию за ведущим звеном

void Insert(Link2* Pred,int data)

{

Link2* Loc=new Link2; // 1

Loc->Value=data; // 2

Loc->next=Pred->next; // 3

Loc->prev=Pred; // 4

Pred->next=Loc; // 5

Loc->next->prev=Loc; // 6

}

Удаление звена из любого места списка за ведущим звеном

void Delete2(Link2* Del)

{

Del->prev->next=Del->next; // 1

Del->next->prev=Del->prev; // 2

delete Del; // 3

}

Поиск

int Search(Link2* Start,Link2*& Find,int Key)

{

Link2* Cur=Start->next;

int Success=0;

while(Cur!=Start && !Success)

{

if(Cur->Value==Key)

{

Find=Cur;

Success=1;

break;

}

Cur=Cur->next;

}

return Success;

}

 

Прекращение поиска в случае неудачи происходит при достижении "текущим" указателем Cur точки начала поиска Start, т.е. при невыполнении условия в операторе while:

while(Cur!=Start ... )

 

Ведущее звено кольцевого 2-связного списка создаётся набором операторов:

 

Link2 *L2 = new Link2;

L2->next = L2;

L2->prev = L2;

 

Графически состояние списка после создания этого звена может быть представлено таким образом:



<== предыдущая лекция | следующая лекция ==>
Линейный двусвязный список | Двоичные деревья


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.006 сек.