10 Зв’язані списки

Зв’язаний список – одна з найважливіших структур даних, у якій елементи лінійно впорядковані, але порядок визначається не номерами елементів, як у масивах, а вказівниками, що входять до складу елементів списку. Список має “голову” – перший та “хвіст” – останній елемент. Зв’язаний список – не новий тип, а спосіб організації даних відомих типів. Для побудови зв’язаного списку найкраще підходять структури, тоді кожна з них є одним елементом списку, крім власне даних, вони містять один або більше вказівників для запам’ятовування адрес сусідніх структур. Ці вказівники мусять мати тип тієї структури, на яку вони вказують. Нагадаємо, що вказівник – це змінна, призначена для запам’ятовування адреси, а його тип визначає крок розміщення даних у пам’яті. Таким чином, одержуємо ніби ланцюжок певної кількості структур, зв’язаних між собою за допомогою адрес.

Існують такі різновиди зв’язаних списків: однобічно зв’язаний, двобічно зв’язаний та кільцевий, розглянемо їх.

Однобічно зв’язаний список є найпростішим, кожний його елемент (структура) містить один вказівник, який запам’ятовує адресу, назвемо її next, наступного елемента. Якщо вказівник не вказує на інший елемент, тобто next = NULL, то вважається, що даний елемент є останнім у списку. Крім вказівника next, програма має мати ще й вказівник на перший елемент списку, назвемо його head, який служить для заходу в список. Якщо список порожній, то цьому вказівнику теж присвоюють значення NULL. Однобічно зв’язаний список забезпечує послідовний доступ до своїх елементів у одну сторону – від початку до кінця. Під час гортання списку (наприклад, під час пошуку потрібного елемента) ні вказівник head, ні кожний із вказівників next не змінюють своїх значень (адрес), тому для запам’ятовування адреси поточного елемента теж використовується вказівник, назвемо його curr. Гортання списку відбувається в циклі, умовою завершення якого є curr == NULL.

Двобічно зв’язаний список подібно до вищерозгляненого однобічно зв’язаного теж забезпечує послідовний доступ до своїх елементів, але, на відміну від нього, дозволяє гортати список як від початку до кінця, так і навпаки. Кожний його елемент містить два вказівники: один next, який вказує на наступний елемент, а другий, назвемо його prev, який вказує на попередній. Якщо prev=NULL, то в елемента немає попередника, тобто він є “головою” списку, якщо next=NULL, то в нього немає наступника –“хвіст” списку.

Кільцевий список може бути як однобічно, так і двобічно зв’язаним. У ньому зв’язується перший елемент з останнім. Тобто, в однобічно зв’язаному списку вказівник next “хвоста” дорівнює head. У двобічно зв’язаному вказівник prev “голови” списку вказує на “хвіст”, а вказівник next “хвоста” вказує на “голову” списку.

Застосування списків. Списки інтенсивно застосовуються в програмуванні як самостійні структури. Також на їх основі можна будувати більш складні структури даних, такі як дерева (зокрема двійкові), стеки та черги.

Списки мають деякі переваги над масивами. Вони більш ефективні при додаванні або вилученні елемента в довільному місці списку, бо виконують ці операції за постійний час, тоді як у масивах час зростає з ростом кількості елементів масиву. В списках не існує проблеми “розширення”, яка рано чи пізно виникає в масивах фіксованого розміру, коли виникає необхідність включити в нього додаткові елементи. Також масив фіксованого розміру, з якого було вилучено багато елементів (або вони просто не використовуються) є дуже неефективним з погляду на використання пам’яті. Функціонування списків можливе в ситуації, коли пам’ять комп’ютера фрагментована, тоді як масиви переважно потребують неперервної області.

З іншого боку, масиви забезпечують безпосередній (прямий) доступ до будь-якого елемента, тоді як списки (особливо однобічно зв’язані), потребують проходження усіх попередніх елементів. Це ускладнює пошук елемента списку, наприклад, в алгоритмах сортування. Іншим недоліком списків є додаткові затрати пам’яті на збереження вказівників, що позначається на ефективності її використання.

Утворення зв’язаного списку та звертання до його елементів (вивід на екран) показано в програмі Spysok. На її початку оголошено тег структури kadry, яка містить три таких елементи: масив літер s, змінну k цілого типу та адресу *dali типу структури kadry. Ця адреса служить для зберігання наступної структури списку після поточної. Масив s та змінна k – просто якісь елементи структури, зрозуміло, що в реальних умовах виробництва їх буде набагато більше.

Всередині блока програми оголошений та ініціалізований масив структур dano типу kadry. У програмі він служить як хранилище структур для демонстрації робіт у зв’язаному списку, під час утворення списку використаємо перші чотири з них. Змінна i – допоміжна, вона служить у якості лічильника структур у списку. Для маніпуляції структурами списку служать п’ять вказівників типу структури kadry, вони мають таке призначення:

• *head – адреса початку списку, вона не змінюється в ході виконання програми, спочатку вона приймає значення NULL, оскільки список ще порожній;

• *prev – адреса попередньої структури відносно поточної;

• *curr – адреса поточної структури;

• *vstv – допоміжна адреса для вставки структури в список;

• *sort – допоміжна адреса для сортування структур списку.

Створення списку відбувається в циклі, де його параметр i змінюється від 0 до 3. На його початку відводиться пам’ять під чергову структуру типу kadry, вона одержує адресу *curr. Якщо список ще порожній, то цю адресу приймає вказівник head, інакше – вказівник на адресу попередньої структури prev->dali, тобто відбувається її прив’язування до попередніх структур списку. Виділення пам’яті під чергову структуру виконується відомим з розділу 6 способом за допомогою функції malloc().

Після цього відбувається ініціалізація елементів новоутвореної структури. Масив s та змінна забирають свої значення з масиву dano, а адреса curr->dali приймає значення NULL, це означає, що тут список закінчується, адже кожна поточна структура є останньою в списку до тих пір, поки не буде додана наступна. Значення змінної k передається в структуру шляхом присвоєння curr->k=dano[i].k;. Рядок s копіюється за допомогою функції strcpy(curr->s,dano[i].s);, тут не можна застосувати операцію присвоєння, бо, оскільки ім’я масиву s є його адресою, то відбудеться переприсвоєння адрес, а не значень.

Наприкінці циклу відбувається підготовка до додачі в список наступної структури, щойно утворена структура стає попередньою шляхом присвоєння: prev=curr. Якщо вона є першою в списку, то це присвоєння означає й prev=head, бо на початку циклу було head=curr.

Читання списку відбувається в циклі типу while, поки curr!=NULL, тобто поки адреса попередньої структури curr->dali не дорівнює нулю. Звертання до елементів структур списку відбувається подібно до вже розгляненого в програмі mas_stru розділу 6. Гортання структур у списку відбувається за допомогою оператора curr=curr->dali;.Звернемо увагу на те, що, на відміну від програми mas_stru, в цьому прикладі під час гортання списку не відбувається нарощення адреси curr++;. Структури в списку не обов’язково будуть розміщені послідовно одна за другою і їхні адреси не будуть відрізнятися з заданим кроком. Особливо це стосується багатокористувацьких систем, коли одночасно працює декілька програм, які виділяють пам’ять, кожна під свої дані.

#include<stdio.h> /* Spysok */

#include<stdlib.h>

#include<string.h> /* Для функції strcpy() */

struct kadry{char s[12];

int k;

struct kadry *dali;};

int main(void)

{

int i;

struct kadry dano[5]={{"Селіна С.С.", 321, NULL},

{"Сакура С.С.", 789, NULL},

{"Дорока Д.Д.", 123, NULL},

{"Хадлер Х.Х.", 369, NULL},

{"Тензор Т.Т.", 123, NULL}

};

struct kadry *head=NULL, *prev, *curr,*vstv,*sort;

puts("Створення списку:");

for(i=0; i<4; i++)

{

curr=malloc(sizeof(struct kadry));

if(head==NULL)head=curr; else prev->dali=curr;

strcpy(curr->s, dano[i].s);

curr->k=dano[i].k;

curr->dali=NULL;

prev=curr;

}

curr=head; i=0; /* Вивід списку */

while(curr!=NULL)

{

printf("i=%d adr=%p s=%s k=%d dali=%p\n", i++, curr,curr->s, curr->k, curr->dali);

curr=curr->dali;

}

getch();

return 0;

}

Створення списку:

i=0 adr=09F6 s=Селiна С.С. k=321 dali=0A0E

i=1 adr=0A0E s=Сакура С.С. k=789 dali=0A26

i=2 adr=0A26 s=Дорока Д.Д. k=123 dali=0A3E

i=3 adr=0A3E s=Хадлер Х.Х. k=369 dali=0000

Редагування структур списку виконується порівняно нескладно, потрібно лише знайти потрібну структуру, вона ж буде й поточною, та виконати потрібні зміни. Зауважимо, що пошук структури відбувається послідовно, тобто приходиться переглядати всі попередні структури. Як правило, пошук відбувається за наперед заданою умовою.

Під час пошуку структур відбувається їх послідовне гортання подібно до того, як це було зроблено під час їх виводу. Нижче подано приклад пошуку структури, де k=321 і його заміна на k=456. Операції редагування не потребують зміни адрес структур у списку. Цей та всі решта фрагменти слід додати до програми Spysok, тоді він запрацює.

puts("Ред. списку, якщо k=321, то замінити на k=456:");

curr=head; i=0;

while(curr!=NULL)

{

if(curr->k==321)curr->k=456;

curr=curr->dali;

}

Ред. списку, якщо k=321, то замінити на k=456:

i=0 adr=09F6 s=Селiна С.С. k=456 dali=0A0E

i=1 adr=0A0E s=Сакура С.С. k=789 dali=0A26

i=2 adr=0A26 s=Дорока Д.Д. k=123 dali=0A3E

i=3 adr=0A3E s=Хадлер Х.Х. k=369 dali=0000

Вилучення структури зі списку спричиняє зміну адрес сусідніх структур. Пошук потрібної структури виконується подібно до вже вищерозгляненого прикладу. Коли структура знайдена, то вона стає поточною, для її вилучення спочатку необхідно з’єднати попередню структуру з наступною, тобто попередню зробити поточною. Оскільки поточна структура не містить своєї адреси, то подібно до того, як відбувалося створення списку, паралельно з нею змінюється й адреса попередньої структури prev. Зв’язування попередньої структури з наступною, обминаючи поточну, відбувається шляхом присвоєння prev->dali=curr->dali. Зауважимо, що адреса наступної структури міститься в поточній. Після цього треба звільнити ще зайняту вже непотрібною структурою пам’ять і повернути в загальний пул за допомогою відомої з розділу 6 функції free(curr).

Нижче показано приклад вилучення структури зі значенням k=123.

puts("Вилуч. стр-ри при k=123:");

curr=head; i=0; prev=curr;

while(curr!=NULL)

{

if(curr->k==123)

{

if(head==curr)head=head->dali; else prev->dali=curr->dali;

free(curr); curr=prev;

}

prev=curr; curr=curr->dali;

}

Вилуч. стр-ри при k=123:

i=0 adr=09F6 s=Селiна С.С. k=456 dali=0A0E

i=1 adr=0A0E s=Сакура С.С. k=789 dali=0A3E

i=2 adr=0A3E s=Хадлер Х.Х. k=369 dali=0000

Вставка структури в список – порівняно рідкісна дія, частіше приходиться доповнювати список новими структурами, тобто додавати їх у кінець списку. Вона виконується в такій послідовності: спочатку створюють нову структуру за допомогою функції malloc, після чого вона дістає адресу; її елементам присвоюють значення. Потім знаходять поточну структуру в списку, перед якою потрібно вставити нову. Зв’язок між попередньою і поточною структурами розривається, поточною стає нова структура, в яку записують адресу наступної, тобто бувшої тільки що поточною.

У поданому нижче фрагменті ставилася задача вставити останню (з індексом 4) структуру масиву dano[] перед структурою, де k=789. Нова структура одержала адресу vstv. Під час гортання списку відомим уже з попередніх прикладів способом була знайдена поточна структура з адресою curr, де curr->k==789. Зрозуміло, що під час виконання операції вставки подібно до вилучення структури мусить бути відомою й адреса prev. Зв’язування нової структури відбувається шляхом переприсвоєння адрес: prev->dali=vstv, а vstv->dali=curr.

Аналізуючи одержані результати, зауважимо, що нова структура дістала адресу 0A26, тобто ту ж адресу, яку мала щойно вилучена структура. Вилучення структури спричинило наявність прогалини в пам’яті (вона стала фрагментованою), а компілятор ощадливо її використав і відвів під нові дані першу ж прогалину, яка підходила за розмірами.

puts(" Вставка стр-ри в список перед k=789:");

vstv=malloc(sizeof(struct kadry));

strcpy(vstv->s, dano[4].s); vstv->k=dano[4].k;

curr=prev=head;

while(curr!=NULL)

{

if(curr->k==789)

{

if(curr==head)head=vstv; else prev->dali=vstv;

vstv->dali=curr;

}

prev=curr; curr=curr->dali;

}

Вставка стр-ри в список перед k=789:

i=0 adr=09F6 s=Селiна С.С. k=456 dali=0A26

i=1 adr=0A26 s=Тензор Т.Т. k=123 dali=0A0E

i=2 adr=0A0E s=Сакура С.С. k=789 dali=0A3E

i=3 adr=0A3E s=Хадлер Х.Х. k=369 dali=0000

Додавання структури до списку виконується подібно до вставки, різниця полягає лише в тому, що додана структура стає останньою, тому має посилатися на нульову адресу, тобто vstv->dali=NULL.

puts("Додати стр-ру до списку:");

curr=prev=head;

vstv=malloc(sizeof(struct kadry));

strcpy(vstv->s, dano[2].s); vstv->k=dano[2].k;

while(curr!=NULL)

{

prev=curr; curr=curr->dali;

}

if(curr==head)head=vstv; else prev->dali=vstv;

vstv->dali=NULL;

Додати стр-ру до списку:

i=0 adr=09F6 s=Селiна С.С. k=456 dali=0A26

i=1 adr=0A26 s=Тензор Т.Т. k=123 dali=0A0E

i=2 adr=0A0E s=Сакура С.С. k=789 dali=0A3E

i=3 adr=0A3E s=Хадлер Х.Х. k=369 dali=0A56

i=4 adr=0A56 s=Дорока Д.Д. k=123 dali=0000

Прямий доступ до структури списку можна виконати, знаючи її адресу. Нехай потрібно знайти ту структуру, де k=789. Тоді під час гортання списку слід запам’ятати її адресу, наприклад, у змінній prev за допомогою такого фрагмента:

if(curr->k==789)prev=curr;.

Елементи знайденої структури можна використовувати в виразах поза списком, наприклад, вивести за допомогою функції:

printf("adr=%p s=%s k=%d dali=%p\n", prev, prev->s, prev->k, prev->dali);.

Тоді одержимо:

adr=0A0E s=Сакура С.С. k=789 dali=0A3E

Сортування списку спричиняє переставляння структур у списку, його можна виконувати двома способами. При першому будуть змінюватися адреси даних, тобто дані будуть залишатися на місці, в тих же комірках пам’яті, а змінюватися будуть лише посилання на них у списку. За другим способом адреси слід залишати на місці, а змінювати дані. Перший спосіб можна реалізувати, застосувавши відомі вже з попередніх прикладів операції вилучення та вставки структур. Він буде вигідним у тому випадку, коли програма має посилання за допомогою адрес на конкретні структури списку без його гортання, тобто при прямому доступі до структур. Тоді в тих посиланнях не треба буде змінювати адреси пересортованого списку, вони завжди будуть однаковими, постійними.

Звичайно, що при першому способі адреси списку не будуть розташованими в якомусь порядку, а будуть розкиданими по всьому списку, тому зростуть витрати часу на його гортання. Оскільки другий спосіб передбачає переставляння, тобто переприсвоєння даних, то він не буде вигідним у списку великих, громіздких структур.

Можна назвати ще один недолік. В реальних умовах часто використовують по-різному посортовані структури – за різними умовами. Наприклад, у нашому прикладі можна сортувати список за зростанням або спаданням значень змінної k, за розташуванням прізвищ у алфавітному порядку та ін. Отже, прийдеться або мати декілька копій зв’язаного списку, або кожного разу його пересортовувати. В цьому випадку вигідніше мати один еталоннний список, а паралельно зробити потрібну кількість (за числом умов) копій, які міститимуть лише дві адреси: постійну еталонного і змінену за даною умовою посортованого.

Таким чином, другий спосіб має перевагу лише у випадку наявності негромізких структур у списку, посортованому за одним критерієм. Приклад його застосування показано в фрагменті нижче. В ньому ставиться задача посортувати одержаний вище список у порядку зростання змінної k, а для її реалізації застосовується метод пошуку мінімального елемента.

Алгоритм сортування являє собою два вкладені цикли типу while. Внутрішній цикл служить для пошуку адреси структури з мінімальним значенням змінної k і присвоєння цієї адреси змінній адресного типу vstv. Гортання структур відбувається адресою curr від наступної за мінімальною, знайденою на попередньому кроці пошуку, тобто від prev->dali до останньої. Кількість його виконань зменшується на одиницю при кожному виконанні зовнішнього циклу. У зовнішньому відбувається гортання списку адресою prev і присвоєння черговій структурі, починаючи від head, структури з мінімальним k. Для цього переприсвоєння служить допоміжна адреса sort.

puts("Сортування списку:");

sort=malloc(sizeof(struct kadry));

prev=head;

while(prev->dali != NULL)

{

curr=prev->dali; vstv=prev;

while(curr != NULL)

{if(curr->k < vstv->k)vstv=curr;

curr=curr->dali;

}

strcpy(sort->s, prev->s); sort->k=prev->k;

strcpy(prev->s, vstv->s); prev->k=vstv->k;

strcpy(vstv->s, sort->s); vstv->k=sort->k;

prev=prev->dali;

}

Сортування списку:

i=0 adr=09F6 s=Тензор Т.Т. k=123 dali=0A26

i=1 adr=0A26 s=Дорока Д.Д. k=123 dali=0A0E

i=2 adr=0A0E s=Хадлер Х.Х. k=369 dali=0A3E

i=3 adr=0A3E s=Селiна С.С. k=456 dali=0A56

i=4 adr=0A56 s=Сакура С.С. k=789 dali=0000

Знищення списку виконується спочатку від адреси head, оскільки маємо послідовний доступ до його структур, тоді, коли він уже непотрібний, а програма ще працює з іншими даними. Нижче подано фрагмент програми, де для знищення списку застосовується вже відома з розділу 6 функція free().

puts("Знищення списку:");

curr=head; i=0;

while(curr!=NULL)

{

printf("i=%d adr=%p\n", i++, curr);

free(curr);

curr=curr->dali;

}

Знищення списку:

i=0 adr=09F6

i=1 adr=0A26

i=2 adr=0A0E

i=3 adr=0A3E

i=4 adr=0A56

Зауважимо, що запропонована вище програма має учбовий характер і може бути вдосконалена. Наприклад, у ній слід передбачити обробку виняткової ситуації при відсутності пам’яті під час додавання чергового елемента зв’язаного списку.

Запитання для перевірки

1. Що таке зв’язаний список? Чи можна назвати його типом даних?

2. Які переваги має зв’язаний список перед масивом?

3. Яким чином зв’язуються між собою дані у зв’язаному списку?

4. Що таке прямий та послідовний доступи до даних у зв’язаному списку?

5. Поясніть виконані вище в програмах операції над даними зв’язаного списку.

6. Чи можна додати до зв’язаного списку за один раз (за один сеанс виділення пам’яті) декілька різних структур? Як можна тоді їх використовувати в програмах та звертатися до кожної з них?

7. Чи можна прочитати зв’язаний список не від початку до кінця, як це було зроблено у вищенаведених прикладах, а навпаки – від кінця до початку?

8. Чи обов’язково потрібно звільняти пам’ять, зайняту зв’язанним списком? Що станеться, якщо цього не робити?

9. Запропонуйте алгоритм вставки в список структури не перед поточною, як це зроблено в вищенаведеному прикладі, а за нею.

10. Складіть алгоритм сортування зв’заного списку бульбашковим методом. Чи буде цей метод ефективнішим за застосований вище в програмі прикладу?

11. Запропонуйте алгоритм сортування зв’язаного списку за декількома умовами, у якому замість багаторазового копіювання всього списку, який залишиться незмінним, буде декілька копій зв’язаних списків з усього двома адресами: еталонного і посортованого списків. Додайте до алгоритму читання посортованих списків за допомогою цих копій. Чи буде тоді досягнена економія пам’яті та часу виконання програми? Наскільки складнішою чи простішою стане програма? Проведіть аналогію між сортуванням зв’язаних списків запропонованим тут способом та виготовленням індексних таблиць бази даних.

12. Обґрунтуйте перевагу посортованого зв’язаного списку перед непосортованим під час виконання пошукових операцій.

ПЕРЕЛІК ВИКОРИСТАНИХ ДЖЕРЕЛ

1. Бек Л. Введение в системное программирование: Пер. с англ. – М.: Мир, 1988.

2. Бочков С.О., Субботин Д.М. Язык программирования Си для персонального компютера. – М.: Радио и связь, 1990.

3. Горбійчук М.І., Семенцов Г.Н. Оптимізація процесу буріння глибоких свердловин. – Івано-Франківськ: Факел, 2003.

4. Довгаль С.И., Сбитнев А.И. Интерфейс современной программной системы. – К.: Информсистема-сервис, 1994.

5. Клим Б.В. Практикум з програмування мовою Сі. – Івано-Франківськ, Факел, 1989.

6. Кочкодан Я.М. Технологія буріння нафтових і газових свердловин. – Івано-Франківськ, Факел, 1999.

7. Кузнецов С.Д. Турбо Сi. – М.: Малип, 1992.

8. Мислюк М.А., Зарубін М.О. Моделювання явищ і процесів у нафтогазопромисловій справі: Навчальний підручник. – Івано-Франківськ: Екор, 1999.

9. Прата С. Язык программирования С. Лекции и упражнения, 5-е издание.: Пер. с англ. – М.: Издательский дом “Вильямс”, 2006.

10. Проценко В.С. i iн. Технiка програмування мовою Сi. – К.: Либiдь, 1993.

11. Середюк М.Д., Якимів Й.В., Лісафін В.П. Трубопровідний транспорт нафти і нафтопродуктів: Підручник. – Івано-Франківськ, 2001.

12. Стариков Ю.А. Мобильность программ и особенности реализаций языка Си. -М.: МП Память, 1992.

13. Трой Д. Программирование на языке Си для персонального компютера IBM PC. – М.: Радио и связь, 1991.

14. Хэзфилд Р., Кирби Л. и др. Искусство программирования на С. Фундаментальные алгоритмы, структуры данных и примеры приложений. Энциклопедия программиста: Пер. с англ./ Ричард Хэзфилд, Лоуренс Кирби и др. – К.: Издательство “ДиаСофт”, 2001.

136