10

[ЗМІСТ] [Далі] [Назад] [Початок розділу]

10.4.3 Кільцевий список

Кільцевий список відрізняється від списку з поточним елементом тим, що для кільцевого списку не визначають перший та останній елемент. Всі елементи зв’язані у кільце та відомий лише порядок слідування. Визначимо кільцевий список:

1. Порожній список.

2. Список; поточний елемент; список.

Набір дій над кільцевими списками:

1. Почати роботу.

2. Довжина списку.

3. Перейти до наступного елемента.

4. Поточний елемент.

5. Вставити елемент.

6. Видалити елемент.

Дії 1, 3, 5, 6 – інструкції; 2, 4 - операції.

Інструкція “Почати роботу” повертає порожній список.

Операція “ Довжина списку” повертає кількість елементів у списку.

“Перейти до наступного елемента” – зробити поточним наступний елемент списку. Якщо список порожній, то нічого не робити.

“Поточний елемент” повертає значення поточного елемента. Список при цьому не змінюється. Якщо список порожній, ця операція повинна давати відмову.

“Вставити елемент” – вставити новий елемент у список перед поточним.

“Видалити елемент” – видалити поточний елемент. Поточним стає наступний елемент або список стає порожнім. Якщо список порожній, інструкція повинна давати відмову.

Можлива реалізація кільцевого списку з використанням вказівників зображена на Рис. 10.12. Елементи списку – це записи з двох полів: поле даних та вказівник на наступний елемент. За допомогою вказівника елементи списку з’єднані у кільце. Сам список – це вказівник на поточний елемент. Якщо список порожній, то елементів немає, а вказівник дорівнює nil.

Рис. 10.23 – Реалізація кільцевого списку

Для списку з поточним елементом ми розглянемо реалізацію у мові Паскаль. Для Сі обмежимось файлом заголовку. Підпрограми Init, Next, Current нескладні і тому залишаються для самостійної роботи. Функція Len обчислює довжину списку за допомогою додаткового вказівника p. Поступово проходимо всі елементи списку до того момента, коли p стане знову рівним r, вказівнику на поточний елемент.

unit IntRList;

interface

type

rlist = ^relem; {Список}

relem = record {Елемент списку}

d: integer;

next: rlist

end;

procedure Init(var r: rlist); { Почати роботу }

function Len(r: rlist): integer; { Довжина списку }

procedure Next(var r: rlist); { Перейти до наступного елемента }

function Current(r: rlist): integer; { Поточний елемент }

procedure Insert(var r: rlist; n: integer);{ Вставити елемент }

procedure Delete(var r: rlist); { Видалити елемент }

implementation

.................

function Len;

var i: word;

p: rlist;

begin

i:=0; p:=r;

if p<>nil then

repeat

p:=p^.next;

i:=i+1

until p=r;

Len:=i

end;

.................

procedure Insert;

var p: rlist;

begin

new(p);

if r=nil then

begin

p^.d:=n; p^.next:=p; {Рис. 10.24 а), б)}

end

else

begin

p^:=r^; r^.d:=n; r^.next:=p; {Рис. 10.24 в), г)}

end;

r:=p;

end;

procedure Delete;

var p: rlist;

begin

if r=nil then begin

writeln('Delete: Список порожній');

halt

end;

if r^.next=r then

begin

p:=r; r:=nil {Рис. 10.25 а), б)}

end

else

begin

p:=r^.next; r^:=p^ {Рис. 10.25 в), г)}

end;

dispose(p)

end;

end.

Вставка елемента у список зображена на Рис. 10.24. Треба розглянути 2 випадки: коли список порожній та непорожній. Перший випадок зображено на Рис 10.24 а), б), а другий - на Рис 10.24 в), г). Якщо список не порожній, то для вставки елемента у нього ми робимо певний трюк. А саме: у динамічній пам’яті ми вставляємо елемент не перед, а після поточного. Це дає нам змогу не проходити весь список для зв’язування елементів у ньому (як це було, наприклад, у списках з поточним елементом). Після виділення пам’яті під новий елемент ми переносимо дані, які були у поточному елементі, у новий елемент (Рис. 10.24 в) ). Дані нового елемента натомість заносимо у той елемент, який був поточним у списку. Нарешті, зв’язуємо поточний елемент з новим, пересуваємо вказівник на поточний елемент, щоб він вказував на новий елемент (Рис. 10.24 г) ). З точки зору кільцевого списку, ми вставили елемент перед поточним.

Рис. 10.24 – Вставка елемента у список

Видалення елемента списку зображено на Рис. 10.25. Якщо список порожній (r=nil), то процедура Delete дає відмову. Інакше, як і для вставки елемента, розглядаємо 2 випадки: коли список складається з 1 елемента, та більше, ніж з 1 елемента. Перший випадок зображено на Рис 10.25 а), б), а другий - на Рис 10.25 в), г). У другому випадку діємо аналогічно діям при вставці елемента. Тобто, видаляємо у динамічній пам’яті не поточний, а наступний елемент, спочатку перенісши дані з нього у поточний елемент.

Рис. 10.25 – Видалення елемента списку

Як приклад використання кільцевих списків розглянемо ту ж задачу, які ми розв’язували для деків. Тобто, вводиться послідовність натуральних чисел. Треба впорядкувати її та показати результат. Підпрограма PutToList, аналогічно put_to_deque з розділу 10.3.2, вставляє число на своє місце у впорядкованій послідовності. Ми вважаємо, що поточний елемент кільцевого списку є найменшим, а далі елементи йдуть у порядку зростання. Процедура WriteList показує кільцевий список, починаючи з поточного елемента. Основна програма вводить послідовність та показує результат впорядкування.

Program TstRList;

uses IntRList;

procedure PutToList(var r: rlist; n: integer);

var l,i,j: word;

b: boolean;

begin

l:=Len(r);

i:=0; b:=false;

while (i<l) and not b do begin

b:=n<Current(r);

if not b then begin

Next(r);

i:=i+1;

end

end;

Insert(r,n);

for j:=i+1 to l do

Next(r);

end;

procedure WriteList(r: rlist);

var i: word;

begin

for i:=1 to Len(r) do begin

write(Current(r),' ');

Next(r)

end;

writeln;

end;

var r: rlist;

i: word;

n: integer;

begin

Init(r);

writeln('Введіть послідовність до першого від”ємного числа');

readln(n);

while n>0 do begin

PutToList(r,n);

readln(n)

end;

writeln('Впорядкована послідовність');

WriteList(r)

end.

Файл заголовку модуля кільцевого списку у мові Сі наведено нижче.

/* rlist.h */

typedef struct relem *rlist; /* Список */

struct relem { /* Елемент списку */

int d;

rlist next;

};

extern void init(rlist *pr); /* Почати роботу */

extern int len(rlist r); /* Довжина списку*/

extern void next(rlist *pr); /* Перейти до наступного елемента */

extern int current(rlist r); /* Поточний елемент */

extern void insert(rlist *pr, int n);/* Вставити елемент */

extern void delete(rlist *pr); /* Видалити елемент */

10.4.4 Двозв’язний список

Двозв’язний список схожий на список з поточним елементом. Але, на відміну від останнього, двозв’язний список дозволяє однаково легко переходити як до наступного, так і до попереднього елемента списка. Визначимо двозв’язний список:

1. Порожній список.

2. Список; поточний елемент; список.

Набір дій над двозв’язними списками:

1. Почати роботу.

2. Чи порожній список?

3. Чи порожній початок списку?

4. Чи порожній кінець списку?

5. Встати до початку списку.

6. Встати до кінця списку.

7. Перейти до наступного елемента.

8. Перейти до попереднього елемента.

9. Поточний елемент.

10. Вставити елемент перед поточним.

11. Вставити елемент після поточного.

12. Видалити елемент.

Дії 1, 5, 6, 7, 8, 10, 11, 12 – інструкції; 2, 3, 4 – відношення; 9 - операція.

Інструкція “Почати роботу” повертає порожній список.

Відношення “Чи порожній початок списку?” перевіряє, чи є елементи у списку перед поточним.

Відношення “Чи порожній кінець списку?” перевіряє, чи є елементи у списку після поточного.

“Встати до початку списку” – зробити поточним перший елемент списку.

“Встати до кінця списку” – зробити поточним останній елемент списку.

“Перейти до наступного елемента” – зробити поточним наступний елемент списку. Якщо кінець списку порожній, то нічого не робити.

“Перейти до попереднього елемента” – зробити поточним попередній елемент списку. Якщо початок списку порожній, то нічого не робити.

“Вставити елемент перед поточним” – вставити новий елемент у список перед поточним. Якщо список був порожнім, то новий елемент стає поточним у списку.

“Вставити елемент після поточного” – вставити новий елемент у список після поточного. Якщо список був порожнім, то новий елемент стає поточним у списку.

“Видалити елемент” – видалити поточний елемент. Якщо це не останній елемент, то поточним стає наступний елемент. Якщо це останній елемент, поточним стає попередній елемент. Якщо список складається з оодного елемента, список стає порожнім. Якщо список порожній, інструкція повинна давати відмову.

Двозв’язний список є найбільш загальною з розглянутих рекурсивних структур даних. На базі двозв’язного списку можна легко реалізувати будь-яку з раніше розглянутих структур, окрім класичних списків.

Можлива реалізація двозв’язного списку з використанням вказівників зображена на Рис. 10.26. Елементи списку – це записи з трьох полів: поле даних та вказівники на наступний та попередній елементи. За допомогою вказівників елементи списку з’єднані у ланцюг. У останньому елементі вказівник на наступний елемент дорівнює nil. У першому елементі вказівник на попередній елемент дорівнює nil. Сам список – це запис з трьох вказівників: вказівник на початок списку, вказівник на кінець списку та вказівник на поточний елемент. Якщо список порожній, то елементів немає, а три вказівники дорівнюють nil. На відміну від списків з поточним елементом, у двозв’язних списках вказівник на поточний елемент завжди знаходиться у межах списку і може дорівнювати nil тільки тоді, коли список порожній.

Рис. 10.26 – Реалізація списку з поточним елементом

Для двозв’язного списку ми розглянемо реалізацію у мові Сі. Для Паскаля обмежимось інтерфейсною частиною модуля.

unit IntDList;

interface

type dlref = ^dlelem; {Вказівник на елемент списку}

dlelem = record {Елемент списку}

d: integer;

next: dlref

end;

dlist = record {Список}

bg, cur, en: dlref

end;

procedure Init(var dl: dlist); { Почати роботу }

function Empty(dl: dlist): boolean; { Чи порожній список?}

function EmpBeg(dl: dlist): boolean; { Чи порожній початок списку?}

function EmpEnd(dl: dlist): boolean; { Чи порожній кінець списку?}

procedure First(var dl: dlist); { Встати до початку списку }

procedure Last(var dl: dlist); { Встати до кінця списку }

procedure Next(var dl: dlist); { Перейти до наступного елемента }

procedure Previous(var dl: dlist); { Перейти до попереднього елемента }

function Current(dl: dlist): integer; { Поточний елемент }

procedure InsBefore(var dl: dlist; n: integer);{Вставити елемент перед поточним}

procedure InsAfter(var dl: dlist; n: integer);{Вставити елемент після поточного}

procedure Delete(var dl: dlist); { Видалити елемент }

implementation

.................

end.

Модуль роботи із двозв’язним списком у Сі складається з 2 файлів: dlist.h та dlist.c. Функції init, emp_beg, emp_end, first, last, next, previous, current, ins_after залишаються на самостійну роботу. Усі ці функції, окрім ins_after, дуже прості. Що ж стосується ins_after, то її можна формально отримати з ins_before паралельною та одночасною заміною у тексті ins_before next на prev, prev на next, bg на en та en на bg. Докладніше розглянемо функції ins_before та delete.

/* dlist.h */

typedef struct dlelem *dlref; /* Вказівник на елемент списку */

struct dlelem { /* Елемент списку */

int d;

dlref next, prev;

};

typedef struct { /* Список */

dlref bg, cur, en;

} dlist;

extern void init(dlist *pdl); /* Почати роботу */

extern int empty(dlist dl); /* Чи порожній список?*/

extern int emp_beg(dlist dl); /* Чи порожній початок списку?*/

extern int emp_end(dlist dl); /* Чи порожній кінець списку?*/

extern void first(dlist *pdl); /* Встати до початку списку */

extern void last(dlist *pdl); /* Встати до кінця списку */

extern void next(dlist *pdl); /* Перейти до наступного елемента */

extern void previous(dlist *pdl); /* Перейти до попереднього елемента */

extern int current(dlist dl); /* Поточний елемент */

extern void ins_before(dlist *pdl, int n);/* Вставити елемент перед поточним */

extern void ins_after(dlist *pdl, int n); /* Вставити елемент після поточного */

extern void delete(dlist *pdl); /* Видалити елемент */

/* dlist.c*/

#include <stdio.h>

#include <stdlib.h>

#include "dlist.h"

.................

void ins_before(dlist *pdl, int n)

{

dlref p;

p = (dlref) malloc(sizeof(struct dlelem));

p -> d = n;

p -> next = pdl -> cur;

/* Рис. 10.27 а), в), д) */

if (pdl -> cur == NULL) /*порожній список*/

{

p -> prev = NULL;

pdl -> bg = pdl -> en = pdl -> cur = p; /* Рис. 10.27 б) */

}

else

{

if (pdl -> cur == pdl -> bg) /*вставка перед першим елементом*/

{

p -> prev = NULL;

pdl -> bg = p;

}

else /*вставка всередині списку*/

{

p -> prev = pdl -> cur -> prev;

pdl -> cur -> prev -> next = p;

}

pdl -> cur -> prev = p;

/* Рис. 10.27 г), е) */

}

.................

void delete(dlist *pdl)

{

dlref p;

if(pdl -> cur == NULL)

{

printf("delete: список порожній\n");

exit(1);

}

p = pdl -> cur;

if (pdl -> cur==pdl -> bg && pdl -> cur==pdl -> en) /*список з одного елемента*/

{

pdl -> bg = pdl -> cur = pdl -> en = NULL;

}

else if (pdl -> cur != pdl -> en) /*поточний елемент не останній*/

{

pdl -> cur = pdl -> cur -> next;

pdl -> cur -> prev = p -> prev;

if (p == pdl -> bg) pdl -> bg = pdl -> cur; /*поточний елемент перший*/

else p -> prev -> next = pdl -> cur; /*поточний елемент не перший*/

}

else /*поточний елемент останній*/

{

pdl -> cur = pdl -> cur -> prev;

pdl -> cur -> next = NULL;

pdl -> en = pdl -> cur;

}

free(p);

}

Вставка елемента у список зображена на Рис. 10.27. Треба розглянути 3 випадки: коли список порожній, коли вказівник на поточний елемент вказує на перший елемент списку та коли цей вказівник вказує у середину списку. Перший випадок зображено на Рис 10.27 а), б), другий - на Рис 10.27 в), г), третій - на Рис 10.27 д), е).

Рис. 10.27 – Вставка елемента у двозв’язний список перед поточним

Видалення елемента списку зображено на Рис. 10.28. Якщо список порожній (pdl -> cur == NULL), то функція delete дає відмову. Інакше розглядаємо 4 випадки: коли список складається з 1 елемента, коли вказівник на поточний елемент вказує на перший елемент списку, коли цей вказівник вказує у середину списку та на останній елемент списку. Перший випадок зображено на Рис 10.28 а), б), другий - на Рис 10.28 в), г) ), третій - на Рис 10.28 д), е), четвертий - на Рис 10.28 є), ж).

Рис. 10.28 – Видалення елемента двозв’язного списку

Як приклад використання двозв’язних списків розв’яжемо задачу перевірки списку на симетричність. Функція is_symm перевіряє, чи симетричний список dl. Оскільки в одному списку ми не можемо одночасно мати 2 поточних елементи, використовуємо допоміжну змінну dl2, якій присвоюємо значення dl. Ми можемо виконати таке присвоєння, тому що область дії dl2 обмежена тілом функції is_symm та сам список у цій функції не змінюється. Функція input_list вводить список. Основна програма організує введення списку та показує результат перевірки.

/* dlisttst.c */

#include <stdio.h>

#include "dlist.h"

#define TRUE 1

int is_symm(dlist dl)

{

int b;

dlist dl2;

b = TRUE;

if (!empty(dl))

{

dl2 = dl;

first(&dl); last(&dl2);

while(1)

{

b = current(dl)==current(dl2);

if (!b || emp_end(dl)) break;

next(&dl); previous(&dl2);

}

return b;

}

void input_list(dlist *pdl)

{

unsigned n, i;

int k;

init(pdl);

printf("Введіть кількість елементів: ");

scanf("%u", &n);

for(i=1; i<=n; i++)

{

printf("Елемент %u= ", i);

scanf("%d", &k);

ins_after(pdl, k);

next(pdl);

}

main()

{

dlist dl;

printf("\nВведіть список\n");

input_list(&dl);

printf("Список ");

if (!is_symm(dl)) printf("не ");

printf("симетричний\n");

}

[ЗМІСТ] [Далі] [Назад] [Початок розділу]