Лекція 10.

Динамічні структури даних. Поняття про чергу,стек,список.

Загальні відомості.

В мові Сі визначені такі структури даних:

• одинокі дані (проста змінна);

- масив однотипних даних;

- структура (сукупність різнотипних даних, які відносяться до одного об’єкту).

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

Але не завжди такі засоби для роботи з інформацією є достатніми і зручними. Деякі задачі виключають використання структур даних фіксованого розміру і вимагають введення динамічних структур, які можуть збільшуватись і зменшуватись в розмірах в процесі роботи програми. Кожна структура даних характеризується, по-перше, взаємозв’язком елементів n, по-друге, набором типових операцій над цією структурою. У випадку динамічної структури важливо:

- яким чином може рости і скорочуватись дана структура даних;

- яким чином можна включити в структуру новий і вилучити існуючий елемент;

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

О
днією із простіших і в той же час типових структур даних є черга. Проблема черги виникає, коли є деякий механізм обслуговування, який може виконувати замовлення послідовно одне за одним. Якщо при появі нового замовлення даний пристрій вільний, він відразу приступає до виконання цього замовлення; якщо ж він виконує якесь раніше отримане замовлення, то повне замовлення поступає в кінець черги інших замовлень, які чекають виконання. Коли пристрій вивільняється, він приступає до виконання замовлення з початку черги (це замовлення вилучається із черги, і першим в ній стає наступне замовлення). Якщо замовлення поступають нерегулярно, черга то збільшується, то скорочується, і навіть може стати пустою (див. малюнок).

Чергу часто називають системою організованого і працюючого по принципу FIFO (first in – first out). Основними операціями з чергою є добавлення нового елемента в кінець і вилучення елементу з початку черги.

Розглянемо, як може бути реалізована робота з чергою на Сі з використанням структур, покажчиків на структури і функції допоміжного виділення (звільнення пам’яті).

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

• функція insert( ) відводить пам’ять під черговий елемент, вводе в нього потрібну інформацію і ставить у кінець черги;

• функція take_off( ) вилучає з черги її перший елемент, вивільняє пам’ять із під нього і зміщує покажчик початку черги на наступний елемент. У випадку спроби вилучення елемента з пустої черги, параметр помилки error отримує значення 1.

---

#include <stdio.h>

#include<alloc.h>

#define QUEVE struct queve

QUEVE

{int info; // поле інформації елемента черги

QUEVE *next; // поле посилання на наступний елемент черги

}

void insert (QUEVE **q, int item)

{ QUEVE tek=*q; // покажчик на поточний елемент черги

QUEVE *pred =0; // pred містить адресу останнього елемента

QUEVE * new_n;

While (tek) // проглядаємо чергу до кінця

{ pred=tek; tek->next;}

new_n=( QUEVE*) malloc (sizeof(QUEVE));

new_n-> info=item;

if (pred) // якщо черга була не пустою

{new_n->next=pred->next;

pred->next+new_n;

}

else (*q=new_n; (*q)->next=0;)

}

int take_off (QUEVE **q, int*error)

{int value=0; // значення елемента черги, що повертається

QUEVE*old = *q; // покажчик на стару голову черги

if ( *q ) // якщо черга не пуста

{ value = old -> info; *q=(*q)->next;

free( old ); *error=0; // елемент вилучений із черги

}

else *error = 1;

return value;

}

void main ( )

{ int error, j;

QUEVE *q1, *q2;

for (j=12; j<=15; j++)

insert (&q1, j );

for (j=1; j<=4; j++)

insert (&q2, take_off(&q1, &error));

for (j=1; j<=4; j++)

printf(“\n вилучений з q2:%d”);

take_off(&q2, &error);

}

Друга, яка часто зустрічається структура даних – це стек (магазин) – відрізняється від черги тим, що вона організована по принципу LIFO (last in – first out). Операція введення й вилучення елемента зі стека виконується тільки з одного кінця, який називається вершиною стека. Коли новий елемент поміщається в стек, то попередній верхній елемент ніби

45 45 “проштовхується” вниз і робиться тимчасово недосяж-

н им. Коли ж верхній елемент вилучається з вершини стеку, попередній елемент “виштовхується” уверх і знов

стає доступним (див. малюнок).

Необхідність в організації стеку виникає, наприк-

лад, при вирішенні такої задачі. Нехай є текст, збалан-

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

17. координати відповідних пар дужок, тобто для тексту

( …… (……….. ) ……(……….. ) ……….)

2 5 0 17 42 61 84 95

таблиця повинна бути такою:

17. 42

61. 84

0. 95

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

Розглянемо програму, в якій реалізована робота із стеком. В ній використовуються функції:

push( ) – покласти елемент на вершину стеку;

pop( ) – виштовхнути верхній елемент із стеку;

peek( ) – прочитати значення верхнього елемента, не вилучаючи сам елемент із стеку.

#include<stdio.h>

#include<alloc.h>

#define STACK struct stack

STACK

{ int info // поле значення елементу стека

STACK *next; // після посилання на наступний елемент стека

};

void push (STACK **s, int item)

{ STACK *new_n;

new_n=( STACK*) malloc (sizeof(stack)); // запросили пам’ять під новий елемент

---

new_n->info=item; // занесли значення в новий елемент

new_n->next=*s; // новий елемент став головою стеку

*s=new_n; // покажчику *s присвоїли адресу голови стеку

}

int pop (STACK **s, int *error)

{ STACK *old=*s;

int info=0;

if (*s) // стек не пустий

{ info =old->info; *s=(*s)->next;

free(old); // вивільняємо пам’ять з-під вибраного елемента

*error=0; // елемент вилучений успішно

}

else *error=1;

return (info);

}

int peek (STACK **s, int *error)

{ if (*s) { *error=0; return (*s)->info; }

else { *error =1; return 0; }

}

void main( )

{int error, i;

STACK *s1, s2;

push(&s1, 42);

printf(“\n peek (s1)=%d”, peek(&s1, &error));

push(&s1, 53);

printf(“\n peek (s1)=%d”, peek(&s1, &error));

push(&s1, 72);

printf(“\n peek (s1)=%d”, peek(&s1, &error));

push(&s1, 86);

printf(“\n peek (s1)=%d”, peek(&s1, &error));

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

push(&s2, pop(&s1, &error));

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

printf(“\n pop(&s2)=%d”, pop(&s2,&error));

}

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

Ел-т 1

Ел-т 2

Ел-т N

NULL

…

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

Ел-т 1

NULL

Ел-т 2

Ел-т N

NULL

…

При роботі зі списком можуть бути корисними наступні базові функції:

insert() – добавити новий елемент в список так, щоб список залишився впорядкованим по збільшенню значення одного із полів;

take out() – вилучити елемент із заданим полем (якщо він є в списку);

is_present() – визначити, чи є в списку заданий елемент;

display( ) – роздрукувати значення всіх елементів у списку;

destroy_list – вивільнити пам’ять, яку займає список;

Достатньо часто при роботі з даними буває зручно використовувати структури з неієрархічним зображенням, які добре відображаються за допомогою дерева

Дерево складається з елементів, які називаються вузлами (вершинами). Вузли з’єднуються між собою направленими дугами. У випадку Х->Y вершина Х називається попередником (родичем, батьком), а Y – спадкоємцем (сином). Дерево має один вузол – корінь, у якого немає попередника. Будь-який інший вузол має рівно одного попередника. Вузол, який не має спадкоємця, називається листом.

Розглянемо роботу з бінарним деревом (в якому у кожного вузла може бути тільки два спадкоємця – лівий і правий син).

---

Необхідно вміти: - побудувати дерево;

• виконати пошук елемента з указаним значенням у вузлі;

• вилучити заданий елемент;

• обійти всі елементи дерева (наприклад, щоб над кожним із них провести деяку операцію).

Зазвичай бінарне дерево будується одразу впорядкованим, тобто вузол лівого сина має значення менше, ніж значення батька, а вузол правого сина – більше. Наприклад, якщо надходять числа 17, 18, 6, 5, 9, 23, 12, 7,8, то побудоване по ним дерево буде мати такий вигляд:

1 7

6. 1 8

5. 9 23

6. 1 2

8

Для того, щоб вставити новий елемент в дерево, потрібно знайти для нього місце. Для цього, починаючи з кореня, будемо порівнювати значення вузлів (Y) зі значенням нового елемента (NEW). Якщо NEW >Y, то підемо по лівій гілці; в противному випадку – по правій. Коли дойдемо до вузла, з якого не виходить потрібна гілка для поданого пошуку, це означає, що місце під новий елемент знайдено.

Шлях пошуку місця для числа 11 в побудованому вище дереві показаний на малюнку.

1 7

6 18

5 9 23

6. 12

11

При вилученні елемента з дерева, можливі три ситуації:

а) вузол, що вилучається – лист (в цьому випадку потрібно просто вилучити посилання на цей вузол);

б) із вузла, що вилучається виходить тільки одна гілка;

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

Наприклад, побудоване раніше дерево після вилучення вузла 6 може стати таким (див. малюнок):

1 7

7 1 8

5 9 23

8 12

11

Розглянемо задачу обходу дерева. Використовують три способи обходу дерева:

1. Обхід зліва направо: А,R,B (спочатку відвідуємо ліве піддерево, а потім – корінь і, під кінець, праве піддерево;

2. Обхід зверху вниз: R,A,B (відвідуємо корінь до піддерев);

3. Обхід знизу вверх: A,B,R (відвідуємо корінь після піддерев).

Цікаво прослідкувати результати цих трьох обходів на прикладі запису формул у вигляді дерева.

Наприклад, формула

(a+b/c)*(d-e*f)

буде виглядати так:

Дерево формується по принципу: операція – вузол, оператори –піддерева.

Обхід 1 дає звичайний інфіксний запис виразу (правда, без дужок).

Обхід 2 – префіксний запис +*a/b*c-d*c*f

Обхід 3 – постфіксний запис (ПОЛИЗ – польська інверсний запис):

fbc/+dcf*-*.

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

Вводяться прізвища абітурїєнтів; необхідно роздрукувати їх в алфавітному порядку з вказанням кількості повторів кожного прізвища.

В програмі буде використана рекурсивна функція der(), яка будує дерево прізвищ, а також рекурсивна функція для друку дерева print_der(), в якій реалізований перший спосіб обходу дерева

---

#include <alloc.h>

#include<stdio.h>

#define TREE struct der

TREE

{char *w;

int c;

TREE *l;

TREE *r;

}

TREE *der (TREE *kr, char *word)

{ int sr;

if (kr==NULL)

{ kr =(TREE *) malloc (sizeof(TREE));

kr->w=word; kr ->c=1;

kr->=kr->r=NULL;

}

else if ((sr=strcmp(word, kr->w))==) kr->c++;

else if (sr<0) kr->l =der (kr->l, word);

else kr->r=der(kr->r, word);

return kr;

}

void print_der(TREE*kr)

{

if(kr)

{print_der (kr->l);

printf(“слово =%-20s\t количество повторов - %d\n”,kr->w,kr->c);

print_der(kr->r);

}

}

void main()

{ int i;

TREE *kr;

static char word[40][21];

kr=NULL; i=0;

puts (“введите <40 файлы длиной <20 “);

scanf (“%s”, word[i]);

while (word[i][0]!=’\0’)

{ kr=der(kr,word[i]);

scanf (“%s”, word[++i]);

}

print_der(kr);

}

Питання для самоконтролю

1. Поясніть різницю між даними статичної і динамічної структури.

2. Що таке стек, черга, список?

3. Яке призначення стеку, черги, списку?

4. Як створити стек, чергу, список?

5. Назвіть базові операції над стеком, чергою і списком.

6. Що таке гілка, дерево, піддерево?

7. Яке призначення дерев?

8. Що таке бінарне дерево?

9. Назвіть основні операції роботи з деревом.

10. Як сформувати дерево?

11. Поясніть засоби вилучення запису з дерева.

12. Що таке лист? Приклади.

13. Що таке корінь дерева? Приклади.

14. Як називаються зв’язки в деревах?

15. Які бувають списки?

16. Які ви знаєте функції для роботи з чергою?

17. Що таке заголовок списку?

---

Смотрите также файлы

• lexs_1_vstup.doc

• Lexs_7_klaccy_pamjt.doc

• lexs_6_Riadki2.doc

• lexs_3_Mas.doc

• pr_s1_lab3.doc