Однонаправленные циклические списки

Операции над списком

1. Размещение произвольного элемента в начало списка [11]

p=getnode();	Выделение места под узел.
	Запись в переменную р адреса узла.
info(p)=x;	Запись значения х
	в информационную часть узла.
ptrn(p)=lst;	Подключение узла к началу списка.
lst=p;	Установка указателя
	1st на новый узел.

2. Удаление первого элемента списка [11]

p=lst;	Установка указателя р
	на начало списка.
lst=ptrn(p);	Установка 1st
	на второй элемент списка.
x=infо(р);	Сохранение данных
	из удаляемого узла в переменной х.
freenode(p);	Освобождение памяти,
	занятой под первый узел.

3. Размещение элемента после узла с адресом р [11]. Новый элемент вследствие однонаправленности списка может помещаться только после узла, адрес которого известен. Поэтому для вставки узла необходимо поступить следующим образом: новый элемент размещаем после старого, затем меняем указатели. Пусть операция insafter(p, x) означает операцию вставки элемента со значением х после/?.

Операция insafter(p, x)

g=getnode();	Выделяем память под узел.
info(g)=x;	Записываем в новый узел значение х.
ptrn(g)=ptrn(p);	Записываем в адресную часть
	нового узла указатель
	на элемент, следующий за р.
ptrn(p)=g;	Записываем в адресную часть
	узла р указатель д.

4. Удаление элемента после узла с адресом р [11]. В однонаправленном связанном списке можно удалить только элемент, следующий за данным узлом. Пусть default(/?, x) — операция удаления элемента со значением х, следующего за узлом с адресом/?.

Операция default(p, x)

g=ptrn(p); Установка указателя р на адрес

элемента, следующего за р.

x=info(g);	Сохранение данных из
	удаляемого узла в переменной х.
ptrn(p)=ptrn (g);	Подключение узла р к узлу,
	следующему за удаляемым.
freenode(g);	Освобождение участка
	оперативной памяти, занятой
	под узел д.

Примеры

1. Из списка 1st удаляются все элементы, равные 4. Имеем два указателя: р — для просмотра списка; q — указатель на элемент перед р. Используем операции удаления: pop — из начала списка; default — из середины списка.

q=NULL; /^инициализация указателя*/

p=lst; /^текущий указатель на начало списка*/

while (p!=NULL)

{

if (info(p) == 4) if (q==NULL)

{

/*удалить первый элемент*/ x=pop(1st); freenode(p); p=lst;

} else

{

/^передвинуть р и удалить элемент,*/ /*следующим за node(q)*/ p=ptrn(p); default(q, x);

} else

{

/^продолжить просмотр, передвинуть р и q*/ q=p;

p=ptrn(p); } }

2. Список 1st упорядочен по возрастанию. Вставить х, не нарушая упорядоченность. Используем операции push для добавления элемента к началу списка, insafter — внутрь списка.

q=NULL;

p=lst;

while((p!=NULL) && (x>info(p))

{

q=p; p=ptrn(p);

}

/^размещаем х*/

if(q == NULL)

push(1st, x); /^поместить в начало списка*/ else

insafter(q, x);

Одним из недостатков линейных списков является то, что имея указатель р на элемент, мы не можем получить доступа к предшествующим элементам.

Циклический связанный список — это список, в котором последний узел связан с первым узлом [11]. Чтобы превратить линейный список в циклический необходимо в поле адреса последнего элемента записать не NULL, а адрес первого элемента списка 1st (рис. 2.2).

1st -----------------------------------»■					jiiutiT	1st
info	pirn	—*■	info	ptrn	----- и-... —и-	mfo	ptrn
	.

Рис. 2.2. Графическое представление циклического списка

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

Простейшие операции над циклическим списком [11]:

1) размещение нового узла после элемента с известным адресом/?;

2) удаление узла после элемента с известным адресом/?.

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

1) список нельзя просматривать в обратном направлении;

2) располагая только значением указателя на элемент, его невозможно удалить.

Для преодоления этих недостатков используются двунаправленные связанные списки.

Дата добавления: 2014-11-29