[ЗМІСТ] [Далі] [Назад] [Початок розділу]
10.4. Списки
Стеки, черги та деки призначені для
тимчасового збереження та почергової обробки даних. Дійсно, ми не можемо
отримати, наприклад, другий елемент черги, не змінивши її (для цього потрібно спочатку
взяти перший елемент). В той же час, у багатьох задачах дані, маючи динамічний
розмір, повинні багаторазово переглядатись та певним чином оброблятись. Для
таких цілей використовують списки. Ми розглянемо декілька видів списків, які
мають спільні властивості, але відрізняються способами реалізації та складом
допустимих дій.
10.4.1 Класичний
список
Класичний
список визначимо так:
1.
Порожній
список.
2.
Перший
елемент; список.
Це означення схоже на означення черг та стеків.
Але список відрізняється від стекуабо черги набором дій.
1.
Почати
роботу.
2.
Чи
порожній список?
3.
Додати
елемент.
4.
Голова
списку.
5.
Хвіст
списку.
Дії 1,
3, 4, 5 – операції; 2 – відношення.
Операція
“Почати роботу” повертає порожній список.
“Додати
елемент” – додати до списку один елемент, який стає першим у списку.
“Голова
списку” повертає значення першого елемента. Список при цьому не змінюється. Для
порожнього списку ця операція повинна давати відмову.
“Хвіст
списку” повертає залишок списку без першого елемента. Хвіст порожнього списку
за означенням – порожній список.
Можлива
реалізація класичного списку з використанням вказівників зображена на Рис.
10.17. Елементи списку – це записи з двох полів: поле даних та вказівник на
наступний елемент. За допомогою вказівника елементи списку з’єднані у ланцюг. У
останньому елементі вказівник на наступний елемент дорівнює nil. Сам список – це вказівник на початок.
Якщо список порожній, то елементів немає, а вказівник дорівнює nil.
Рис. 10.17 – Реалізація класичного списку
Розглянемо
модуль реалізації класичних списків у Паскалі. Треба зазначити, що всі дії
реалізовані за допомогою функцій. Функції Init, Empty, Head залишаються для
самостійної роботи. Функція Add (Рис. 10.18) схожа на підпрограму вштовхування елемента у стек. Але, на відміну
від останньої, Add повертає,
взагалі кажучи, новий список, а не модифікує існуючий. Функція Tail повертає nil для порожнього списку або вказівник на другий
елемент для непорожнього.
unit ListClassic;
interface
type list = ^lelem; {Список}
lelem = record {Елемент списку}
d: integer;
next: list
end;
function Init: list; { Почати роботу }
function Empty(l: list): boolean; { Чи порожній список?}
function Add(l: list; n: integer): list; { Додати елемент }
function Head(l: list): integer; { Голова списку }
function Tail(l: list): list; { Хвіст списку }
implementation
.................
function Add(l: list; n: integer): list;
var p:
list;
begin
new(p);
p^.d:=n; p^.next:=l;
Add:=p
end;
.................
function Tail(l: list): list;
begin
if l=nil
then Tail:=nil
else
Tail:=l^.next
end;
end.
Рис. 10.18 – Додавання елемента до списку
Оцінимо
тепер докладніше, як класичні списки розташовані у динамічній пам’яті. Зверніть
увагу на те, що функція Tail
не вміщує жодного виклику dispose. Немає таких викликів і в інших функціях. Отже одного разу виділена
динамічна пам’ять ніколи не звільняється. Розташування списків у динамічній
пам’яті зображене на Рис. 10.19. З нього можна побачити, що декілька списків
ділять спільну пам’ять. Дійсно, після виконання ланцюга
l2:=Tail(l1); l2:=Add(l2,x); l2:=Add(l2,y)
списки l1 та l2 будуть мати спільні елементи (завершення списків). Оскільки пам’ять ніколи
не звільняється, існує небезпека переповнення пам’яті. Якщо багато разів у
циклі повторювати ланцюг l:=Add(l,x); l:=Tail(l), то, незважаючи на незмінний розмір списку l, можна отримати аварійне повідомлення про вичерпання
динамічної пам’яті. Таким чином, хоч реалізація класичних списків дуже проста,
вони використовують динамічну пам’ять неоптимально.
Рис. 10.19 – Розміщення списків у динамічній пам’яті
Як
приклад використання класичних списків розв’яжемо задачу порівняння двох
списків. Функція CmpLists перевіряє, чи співпадають два списки l1 та l2. Основна програма вводить 2 списки та показує
результат порівняння.
Program ListClassTst;
uses ListClassic;
function CmpLists(l1,l2: list): boolean;
var b:
boolean;
begin
b:=true;
while
not Empty(l1) and not Empty(l2) and b do
begin
b:=Head(l1)=Head(l2);
l1:=Tail(l1); l2:=Tail(l2)
end;
CmpLists:=b and Empty(l1) and Empty(l2)
end;
var l1,l2: list;
i,n,m,k:
word;
begin
l1:=Init;
write('Кількість елементів 1-го списку: '); readln(n);
for i:=1
to n do begin
write('l1(',i,')'); readln(k);
l1:=Add(l1,k)
end;
l2:=Init;
write('Кількість елементів 2-го списку: '); readln(m);
for i:=1
to m do begin
write('l2(',i,')'); readln(k);
l2:=Add(l2,k)
end;
write('Списки ');
if not
CmpLists(l1,l2) then write('не ');
writeln('співпадають')
end.
На
завершення розгляду класичних списків наведемо файл заголовку модуля класичного
списку.
/* Класичний список classlst.h */
typedef struct lelem *list; /*
Список */
struct
lelem { /* Елемент списку */
int d;
list next;
};
extern
list init(); /* Почати роботу */
extern
int empty(list l); /* Чи порожній список? */
extern list
add(list l, int n); /* Додати елемент */
extern
int head(list l); /* Голова списку */
extern
list tail(list l); /* Хвіст списку */
10.4.2 Список
з поточним елементом
Список
з поточним елементом краще використовує динамічну пам’ять, ніж класичний список,
завдяки іншому набору команд. Визначимо список з поточним елементом:
1.
Порожній
список.
2.
Список;
поточний елемент; список.
3.
Список.
Набір дій над списками з поточним елементом:
1.
Почати
роботу.
2.
Чи
порожній залишок списку?
3.
Встати
до початку списку.
4.
Перейти
до наступного елемента.
5.
Поточний
елемент.
6.
Вставити
елемент.
7.
Видалити
елемент.
Дії 1,
3, 4, 6, 7 – інструкції; 2 – відношення; 5 - операція.
Інструкція
“Почати роботу” повертає порожній список.
Відношення
“Чи порожній залишок списку?”
перевіряє, чи є елементи у списку, починаючи від поточного.
“Встати до початку списку” – зробити поточним перший елемент списку.
“Перейти до наступного елемента” – зробити поточним наступний елемент списку. Якщо залишок списку порожній,
то нічого не робити.
“Поточний елемент” повертає значення поточного елемента. Список при цьому не змінюється. Якщо залишок списку порожній, ця
операція повинна давати відмову.
“Вставити елемент” – вставити новий елемент у список перед поточним.
“Видалити елемент” – видалити поточний елемент. Поточним стає наступний елемент. Якщо залишок списку порожній, інструкція
повинна давати відмову.
Можлива
реалізація списку з поточним елементом з використанням вказівників зображена на
Рис. 10.20. Елементи списку – це записи з двох полів: поле даних та вказівник
на наступний елемент. За допомогою вказівника елементи списку з’єднані у
ланцюг. У останньому елементі вказівник на наступний елемент дорівнює nil. Сам список – це запис з двох
вказівників: вказівник на початок списку та вказівник на поточний елемент. Якщо
список порожній, то елементів немає, а обидва вказівники дорівнюють nil. Будемо вважати, що коли залишок списку
порожній, вказівник на поточний елемент вказує за останній елемент списку (його
значення при цьому дорівнює nil). Це нам потрібно, щоб можна було вставити новий елемент у будь-яке місце
списку.
Рис. 10.20 – Реалізація списку з поточним елементом
Для
списку з поточним елементом ми розглянемо реалізацію у мові Сі. Для Паскаля
обмежимось інтерфейсною частиною модуля.
unit ListCurrent;
interface
type lref = ^lelem; {Вказівник
на елемент списку}
lelem =
record {Елемент
списку}
d: integer;
next: lref
end;
list = record {Список}
beg, cur: lref
end;
procedure Init(var l: list); { Почати роботу }
function EmpEnd(l: list): boolean; { Чи порожній залишок списку?}
procedure First(var l: list); { Встати до початку списку }
procedure Next(var l: list); { Перейти до наступного елемента }
function Current(l: list): integer; { Поточний
елемент }
procedure Insert(var l: list; n: integer);{ Вставити елемент }
procedure Delete(var l: list); { Видалити елемент }
implementation
.................
end.
Модуль
роботи із списком з поточним елементом у Сі складається з 2 файлів: listcur.h
та listcur.c. Функції init, emp_end, first, next, current залишаються на самостійну роботу.
/* listcur.h */
typedef struct lelem *lref; /* Вказівник на елемент списку */
struct lelem { /*
Елемент списку */
int d;
lref next;
};
typedef struct { /*
Список */
lref beg, cur;
} list;
extern void init(list *pl); /* Почати роботу */
extern int emp_end(list l); /* Чи порожній залишок списку?*/
extern void first(list *pl); /* Встати до початку списку */
extern void next(list *pl); /* Перейти до наступного елемента */
extern int current(list l); /* Поточний елемент */
extern void insert(list *pl, int n);/* Вставити елемент */
extern void delete(list *pl); /* Видалити елемент */
/* listcur.c */
#include <stdio.h>
#include <stdlib.h>
#include "listcur.h"
lref find_prev(list l)
{
lref p;
if (l.beg
== l.cur) p=NULL;
else
{
p =
l.beg;
while
(p -> next != l.cur)
p =
p ->next;
}
return p;
}
.................
void insert(list *pl, int n)
{
lref p;
p =
(lref) malloc(sizeof(struct lelem));
p -> d
= n;
p ->
next = pl -> cur;
/* Рис. 10.21 а), в) */
if(pl
-> beg == pl -> cur) pl -> beg = p; /* Рис. 10.21 б)
*/
else
find_prev(*pl) -> next = p; /*
Рис. 10.21 г) */
}
void delete(list *pl)
{
lref p;
if(pl
-> cur == NULL)
{
printf("delete: список порожній\n");
exit(1);
}
p = pl
-> cur;
if(pl
-> beg == p) pl -> beg = pl -> cur -> next; /* Рис.
10.22 а) */
else
find_prev(*pl) -> next = pl -> cur -> next; /* Рис. 10.22 в)
*/
pl ->
cur = pl -> cur -> next;
free(p);
/* Рис. 10.22 б), г) */
}
Вставка
елемента у список зображена на Рис. 10.21. Треба розглянути 2 випадки: коли
вказівник на поточний елемент вказує на початок списку (перший елемент списку)
та у середину списку. Перший випадок зображено на Рис 10.21 а), б), а другий -
на Рис 10.21 в), г). Для вставки елемента та видалення елемента функції insert та delete використовують допоміжну внутрішню функцію модуля
find_prev. Вона повертає вказівник на попередній
елемент списку (p1 на Рис.
10.21).
Рис. 10.21 – Вставка елемента у список
Видалення
елемента списку зображено на Рис. 10.22. Якщо залишок списку порожній (pl ->
cur == NULL), то функція delete дає відмову. Інакше, як і для вставки елемента, розглядаємо 2 випадки:
коли вказівник на поточний елемент вказує на початок списку (перший елемент
списку) та у середину списку. Перший випадок зображено на Рис 10.22 а), б), а
другий - на Рис 10.22 в), г).
Рис. 10.22 – Видалення елемента списку
Як
приклад використання списків з поточним елементом розв’яжемо задачу порівняння
двох списків. Функція cmp_list перевіряє, чи співпадають два списки l1 та l2. Функція input_list вводить список. Основна програма вводить
2 списки та показує результат порівняння.
/* listcurt.c */
#include <stdio.h>
#include "listcur.h"
#define TRUE 1
int cmp_list(list l1, list l2)
{
int b;
first(&l1); first(&l2); b = TRUE;
while(!emp_end(l1) && !emp_end(l2)
&& b)
{
b
= current(l1)==current(l2);
next(&l1);
next(&l2);
}
return b && emp_end(l1) &&
emp_end(l2);
}
void input_list(list *pl)
{
unsigned n, i;
int k;
init(pl);
printf("Введіть кількість елементів:
");
scanf("%u", &n);
for(i=1; i<=n; i++)
{
printf("Елемент
%u= ", i);
scanf("%d",
&k);
insert(pl,
k);
}
}
main()
{
list l1, l2;
printf("\nВведіть перший список\n");
input_list(&l1);
printf("\nВведіть другий список
\n");
input_list(&l2);
printf("Списки ");
if (!cmp_list(l1,l2)) printf("не ");
printf("співпадають\n");
}
[ЗМІСТ] [Далі] [Назад] [Початок розділу]