Язык С++ и программирование на нем. Рейзлин В.И. - 144 стр.

UptoLike

Составители:

Рубрика:

146

list

h data data data

. . .

Заглавный эл.

Рис. 7. Первый вариант двунаправленного кольцевого списка

list

h data data data

. . .

З. эл.

Рис. 8. Второй вариант двунаправленного кольцевого списка

Здесь список замыкается в кольцо, поэтому списки такого вида

называют двунаправленными кольцевыми.

В первом варианте (рис. 7) очень просто реализуется вставка но-

вого звена как в начало списка (после заглавного звена) так и в его ко-

нец, так как вставка звена в конец списка эквивалентна его вставке пе-

ред заглавным элементом. Но здесь при циклической обработке элемен-

тов придётся каждый раз проверять, не является ли очередное звено за-

главным. Этого недостатка лишён второй вариант списка (рис. 8), но в

этом случае труднее реализуется добавление в конец списка.

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

списками в первом варианте (рис. 7).

24.3. Операции над кольцевыми списками

Вставка элемента

Пусть h, p, q – переменные типа elem*, а k – переменная типа int.

Значение k нужно занести в информационную часть элемента, который

должен быть вставлен после звена, на которое указывает указатель p.

Эту вставку можно осуществить так:

q = new elem (k, p->next, p);

p->next->pred=q; p->next=q; // В таком порядке!