Пов’язані списки, черги, стеки, кільця

Лабораторна робота №10

Список– це набір елементів (найчастіше структурних змінних) розміщених у динамічній пам'яті і пов'язаних між собою з використанням покажчиків на ці елементи. Спосіб зв'язування елементів, що застосовується, визначає тип списку.

Списки буваютьлінійними та кільцевими, однозв'язковими та двозв'язковими.Елемент однозв'язкового списку містить крім безпосередньо «корисної» інформації також інформацію про наступний або попередній елемент списку. Відповідно елемент двозв'язкового списку містить інформацію як про наступний, так і про попередні елементи. Останній елементкільцевого спискумістить покажчик на перший елемент списку.

Графічний зображення списків показано на рис. 1.1.

Однозв'язний лінійний списокДвозв'язковий лінійний списокОднозв'язний кільцевий список
язані

Мал. 1.1. Графічне зображення списків

Найпоширенішими випадками лінійного однозв'язкового списку єстекічерга.

Черга –це список з таким способом зв'язку між елементами, при якому нові елементи додаються суворо до кінця списку, а витягуються для обробки строго з початку.

Стек- це список з таким способом зв'язку між елементами, при якому нові елементи додаються строго на початок списку і витягуються для обробки строго з початку списку, тобто. перший занесений у стек елемент буде оброблений останнім).

Кільце –це перелік, елементи якого утворюють замкнуту кругову систему, тобто. останній створений елемент повинен містити покажчик першого елемент.

Списки можуть бутидвонаправленими, що дає можливість обходу списків у двохнапрямках. У лінійних списків у перших елементах покажчик на попередній елемент, як правило, дорівнює нулю. У двонаправленого кільця перший елемент свідчить про останній, а останній – перший.

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

struct node

int data;

struct node *nextPtr;

описує тип struct node. Структура типу struct node і двох елементів — цілого data і покажчика nextPtr. Елемент nextPtr вказує на структуру типу struct node - структуру того самого типу, що і щойно оголошена, звідси і термін «структура, що посилається на себе». Елемент nextPtr іноді називаютьзв'язкою,тобто. nextPtr можна використовувати для того, щоб зв'язати структуру типу struct node з іншою структурою того ж типу. Структури, що посилаються на себе, можуть зв'язуватися разом для утворення інших структур даних, таких як списки, черги, стеки та дерева.

Мал. 1.2. Графічна ілюстрація двох структур, що посилаються на себе, пов'язаних один з одним

Графічна ілюстрація двох структур, що посилаються на себе, пов'язані один з одним і утворюють список наведена на рис. 3.20. На рис. 1.2 у сполучному елементі другої структури намальована, що представляє покажчикNULL, коса риса, щоб показати, що цей елемент не вказує на іншу структуру. Коса риса використовується виключно для ілюстрації і не має жодного відношення до символу зворотної дрібної риси мови Сі. ПокажчикNULL зазвичай позначає кінець структури даних, як символNULL позначає кінець рядка.

Пов'язаний список— це лінійний набір структур, що посилаються на себе, званих вузлами,та об'єднаних покажчиком-зв'язкою, звідси й назва – «пов'язаний» список. Доступ до зв'язаного списку забезпечується покажчиком першого вузол списку. Доступ до наступних вузлів здійснюється через зв'язуючий покажчик, що зберігається у кожному вузлі. За загальною угодою зв'язуючий покажчик в останньому вузлі списку встановлюєтьсяNULL, позначаючи кінець списку. Дані зберігаються у зв'язаному списку динамічно - кожен вузол створюється за необхідності. Вузол може містити будь-які дані, включаючи інші структури. Стеки та черги також належать до лінійних структур даних, і є спеціальними варіантами пов'язаних списків. Дерева ж є нелінійними структурами даних.

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

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

Вузли пов'язаних списків, як правило, не розташовуються в пам'яті у вигляді суцільної області. Логічно пов'язаний список є безперервним. Графічна ілюстрація ілюструє пов'язаний список з кількома вузлами наведено на рис. 1.3.

черги

Мал. 1.3. Графічна ілюстрація пов'язаного списку з кількома вузлами.

Стек- це спрощений варіант пов'язаного списку. Нові вузли можуть додаватися до стек і видалятися зі стека тільки зверху. З цієї причини, стек часто називають структурою видуостаннім прийшов-першим обслужився(LIFO). На стек посилаються через покажчик верхній елемент стека. Зв'язуючий елемент в останньому вузлі стека встановленийNULL, щоб позначити межу стека.

Графічне уявлення стека з кількома вузлами показано на рис. 1.4. Слід зазначити, що стеки та пов'язані списки подаються ідентично. Різниця між стеком та зв'язаними списками в тому, що вставку та видалення у зв'язаних списках можна виконувати в будь-якому місці, а в стеку лише зверху.

Мал. 1.4. Графічна ілюстрація стека

Приклади.Програма працює з простим стеком цілих чисел. Програма виконує три дії на вибір: 1) поміщає значення у стек (функція push); 2) витягує значення зі стека (функція pop); 3) завершує роботу.

struct stackNode *nextPrt;

typedef struct stackNode STACKNODE;

typedef STACKNODE * STACKNODEPTR;

void push(STACKNODEPTR*, int);

STACKNODEPTR stackPtr = NULL;

int choice, value;

printf("Enter an integer >> ");

printf("the popped value is %d \n", pop(&stackPtr));

void push(STACKNODEPTR *topPtr, int info)

newPtr = new STACKNODE;

if (newPtr != NULL)

newPtr ->data = info;

newPtr ->nextPrt = * topPtr;

printf("%d Error not memori\n", info);

int pop(STACKNODEPTR *topPtr)

popValue = (*topPtr) ->data;

*topPtr = (*topPtr) ->nextPrt;

void printStack(STACKNODEPTR currentPtr)

if (currentPtr == NULL)

printf("Error not stack\n\n");

printf("Stack is :>> \n");

while (currentPtr != NULL )

printf("%d -> ", currentPtr ->data);

currentPtr = currentPtr ->nextPrt;

int isEmpty (STACKNODEPTR topPtr)

return topPtr == NULL;

У цьому прикладі основні функції, що використовуються під час роботи зі стеками - push і pop. Функція push створює новий вузол та поміщає його на вершину стека. Функція pop видаляє верхній вузол стека, звільняє пам'ять, виділену вилученому вузлу, і повертає вилучене значення.

Програма працює з простим стеком цілих чисел. Програма виконує три дії на вибір: 1) поміщає значення у стек (функція push); 2) вилучає значення зі стека (функція pop); 3) завершує роботу.

Функція push розміщує новий вузол на вершину стека. У виконанні функції можна виділити три етапи:

2. Покажчику newPtr->nextPtr присвоюється *topPtr (покажчик на вершину стека); зв'язуючий елемент newPtr тепер свідчить про вузол, який був верхнім до цього.

3. *topPtr надається значення newPtr; *topPtr тепер вказує на нову вершину стека. Операції, що включають*topPtr, змінюють значенняstackPtr в main.

а)
б)
списки

Мал. 1.5. Графічна ілюстрація виконання функції push

Наочне уявлення у тому, як відбувається виконання функції push показано на рис. 1.5. На рис. 1.5 а зображений стек і новий вузол перед виконанням функції push. Пунктирні лінії на рис. 1.5 б ілюструють кроки 2 і 3 виконання функції push, в результаті яких вузол, що містить 12, стає новою вершиною стека.

Функція pop видаляє верхній вузол стека. Зазначимо, що перед тим як викликати функцію pop, функція main визначає,чи порожній стек. У виконанні функції pop можна виділити п'ять основних етапів:

1. Вказівнику tempPtr присвоюється *topPtr (tempPtr буде використаний для звільнення непотрібної пам'яті).

2. Змінній popValue надається значення (*topPtr)->data (зберігається значення, що знаходилося у верхньому вузлі).

4. Звільняється пам'ять, яку вказує tempPtr.

5. Функції, що викликає, повертається значення popValue (у прикладі програми це функція — main).

Виконання функції pop проілюстровано на рис. 1.6. На рис. 1.6, а показано стан стека після попередньої операції push. На рис. 1.6 б виділені покажчики tempPtr, що вказує на перший вузол стека, і *topPtr, що вказує на другий вузол. Для звільнення зазначеної tempPtr пам'яті викликається функція free.

а)
б)
язані

Мал. 1.6. Графічна ілюстрація виконання функції pop

На стеку виділяється простір для автоматичних змінних під час кожного виклику функції. Коли відбувається повернення від викликаної функції до зухвалої, простір автоматичних змінних функції видаляється зі стека, і ці змінні стають для програми невідомими.

Компілятори використовують стеки в процесі обчислення виразів та створення коду машинної мови.