Удаление двунаправленного списка

Операция удаления двунаправленного списка реализуется аналогично удалению однонаправленного списка.

4.Кольцевой список: структура, машинное представление , операции.

Под кольцевым (циклическим) списком понимается список, в котором указатель из некоторой ячейки направлен на такое место в списке, откуда данная ячейка может быть достигнута снова [1]. Очевидно, что теперь мы можем из любого звена списка, "перемещаясь" по указателям достичь любого другого звена.

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

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

Рис.1. Кольцо с удаленным заглавным звеном

Такой кольцевой список будем называть кольцевым списком с удаленным заглавным звеном.

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

Рис.2. Пустое кольцо с удаленным заглавным звеном

Рис.3. Кольцо с включенным заглавным звеном

А этот кольцевой список назовем кольцевым списком с включенным заглавным звеном.

Пустой кольцевой список с включенным заглавным звеном представим так:

Рассмотрим способ построения кольцевого списка. Построение выполняется так же, как и в случае линейного однонаправленного списка с заглавным звеном, только после окончания ввода элементов кольцевого списка, в поле указателя последнего звена списка помещается адрес звена, следующего за заглавным.

Сказанное легко формализуется:

void POSTROENIE (node **phead)

//*phead - указатель на заглавное звено.

{

int el;

struct node *t;

// Вначале сформируем заглавное звено.

*phead = new (node);

t = *phead; (*t).sled = NULL;

cout<<"Вводите элементы кольца: "; cin>>el;

while (el!=0)

{ (*t).sled = new (node); t = (*t).sled; (*t).elem = el;

cin>>el;

}

(*t).sled = (*(*phead)).sled;

}

Вывод на экран дисплея содержимого информационных полей кольцевого списка производится до тех пор, пока рабочий указатель, перемещающийся по кольцу, не совпадет с указателем на звено, расположенное после заглавного:

void VYVOD (node **phead)

{

struct node *t;

t = (**phead).sled; cout<< "Кольцо: ";

if (t!=NULL)

{ cout<<(*t).elem; t = (*t).sled;

while (t!=(**phead).sled)

{

cout<<(*t).elem;

t = (*t).sled; }

}

else cout<<"пусто!\n";

}

Дата добавления: 2015-07-26; просмотров: 145; Нарушение авторских прав

Мы поможем в написании ваших работ!