Зв‘язок між елементами динамічної структури

Порядок роботи з динамічними структурами

Приклад 1. struct Node { int key;//інформаційне поле Node*next;//адресне поле }; Приклад 2. (Інформаційних полів може бути

Схематичне зображення двозв’язного списку

784.00K

Category:

programming

8_Динамічні структури

1. Динамічні структури даних

2. Динамічні структури даних

Динамічні структури даних – це структури даних, пам'ять
під які виділяється та звільняється по мірі необхідності.
Динамічні структури даних характеризуються тим що:
• вони не мають імені;
• їм виділяється пам'ять в процесі виконання програми;
• кількість елементів структури може не фіксуватися;
• розмірність структури може змінюватися в процесі
виконання програми;
• в процесі виконання програми може змінюватися
характер взаємозв'язку між елементами структури.
2

3. Використання динамічних структур даних

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

4. Зв‘язок між елементами динамічної структури

Для встановлення зв'язку між елементами динамічної структури
використовуються вказівники, через які встановлюються явні зв'язки
між елементами. Таке представлення даних в пам'яті називається
зв'язним.
Переваги :
• розмір структури обмежується тільки доступним об'ємом машинної
пам'яті;
• при зміні логічної послідовності елементів структури потрібно не
переміщення даних в пам'яті, а тільки корекція вказівників;
• велика гнучкість структури.
Недоліки:
• на поля, що містять вказівники для зв'язування елементів один з
одним, виділяється додаткова пам'ять;
• доступ до елементів зв'язної структури може бути менш ефективним
за часом.
4

5. Порядок роботи з динамічними структурами

Порядок роботи з
динамічними структурами
1.
2.
3.
Створити (відвести місце в динамічній пам'яті);
Працювати за допомогою вказівника;
Видалити (звільнити зайняте структурою місце).
Класифікація
односпрямовані (однозв'язні) списки;
двонаправлені (двозв'язні) списки;
циклічні списки;
стек;
дек;
черга;
бінарні дерева.
5

6. Оголошення динамічних структур даних

struct ім’я_типу {
інформаційне поле;
адресне поле;
};
Схематичне представлення
динамічної структури
Наприклад,
struct TNode {
int Data;// інформаційне поле
TNode *Next;// адресне поле
};
Інформаційних і адресних полів
може бути як одне, так і декілька.
6

7. Доступ до даних в динамічних структурах

Доступ до динамічних даних виконується спеціальним чином за
допомогою вказівників.
Вказівник містить адресу певного об'єкта в динамічній пам'яті.
Адреса формується з двох слів: адреса сегмента і зміщення. Сам
вказівник є статичним об'єктом і розташований в сегменті даних.
Зв’язок вказівника з об’єктом
7

8. Робота з пам'яттю

Робота з пам'яттю
Формат доступу до даних в динамічних структурах.
ВказівникНаСтруктуру-> Ім’яЕлементу
Операція "стрілка" (->) двомісна. Застосовується для доступу до
елементу, що задається правим операндом, тієї структури, яку
адресує лівий операнд. Лівий операнд повинен бути вказівником
на структуру, а в якості правого виступає ім'я елемента цієї
структури.
Наприклад,
p->Data;
p->Next;
Виділення динамічної пам'яті проводиться за допомогою операції
new або за допомогою бібліотечної функції malloc (calloc).
Звільнення динамічної пам'яті здійснюється операцією delete або
функцією free.
8

9. Робота з пам'яттю

Робота з пам'яттю
struct Node {char *Name;
int Value;
Node *Next
};
Node *PNode; //оголошується вказівник
PNode = new Node; //виділяється пам’ять
PNode->Name = "STO"; //присвоюється значення
PNode->Value = 28;
PNode->Next = NULL;
delete PNode; // звільнення пам’яті
9

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

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

11. Односпрямовані списки

Односпрямований (однозв'язний) список - це структура даних, що
представляє собою послідовність елементів, в кожному з яких
зберігається і значення, і вказівник на наступний елемент списку.
В останньому елементі вказівник на наступний елемент дорівнює
NULL.
Опис найпростішого елементу списку.
struct ім’я_типу { інформаційне поле; адресне поле; };
де інформаційне поле – це поле будь-якого, раніше оголошеного або
стандартного типу;
адресне поле – це вказівник на об’єкт того ж типу, що і дана
структура, в нього записують адресу наступного елемента списку.
11

12. Приклад 1. struct Node { int key;//інформаційне поле Node*next;//адресне поле }; Приклад 2. (Інформаційних полів може бути

кілька)
struct point {
char*name;// інформаційне поле
int age;// інформаційне поле
point*next;//адресне поле
};
12

13. Основні операції

• створення списку;
• друк (перегляд) списку;
• вставка елемента в список;
• видалення елемента зі списку;
• пошук елемента в списку
• перевірка порожнечі списку;
• видалення списку.
13

14. Оголошення односпрямованих списків

struct Single_List {//структура даних
int Data; //інформаційне поле
Single_List *Next; //адресне поле
};
..........
Single_List *Head; //вказівник на перший елемент списку
..........
Single_List *Current; //вказівник на поточний елемент списку (при
необхідності)
14

15. Двонаправлені списки

Двонаправлений (двозв’язний) список - це структура
даних, що складається з послідовності елементів,
кожен з яких містить інформаційну частину і два
вказівника на сусідні елементи. При цьому два сусідні
елементи повинні містити взаємні посилання один на
один.
Кожен елемент двонаправленого списку має два поля з
вказівниками: одне поле містить посилання на
наступний елемент, інше поле - посилання на
попередній елемент і третє поле - інформаційне.
15

16. Схематичне зображення двозв’язного списку

17. Опис найпростішого елемента

struct ім'я типу {
інформаційне поле;
адресне поле 1;
адресне поле 2;
};
де інформаційне поле - це поле будьякого, раніше оголошеного або
стандартного, типу;
адресне поле 1 - це вказівник на об'єкт
того ж типу, що й структура, в нього
записується адреса наступного
елемента списку;
адресне поле 2 - це вказівник на об'єкт
того ж типу, що й структура, в нього
записується адреса попереднього
елемента списку.
Приклад 1.
struct list {
type elem ;
list *next, *pred ;
}
list *headlist, *taillist ;
де type - тип інформаційного поля
елемента списку;
* Next, * pred - вказівники на
наступний і попередній елементи
цієї структури відповідно.
17

18. Приклади операцій

1. Створення першого елемента
2. Створення другого елемента
List *t = new List;
t->next = new List;
t->elem = 3;
List *p = t;
t->prev = NULL;
t = t->next;
t->next = NULL;
t->prev = p;
Begin = t;
t->elem = 5;
End = t;
t->next = NULL;
End = t;
18

19. Приклади операцій

3. Створення третього елемента
t->next = new List;
p = t;
t = t->next;
t->prev = p;
t->elem = 1;
t->next = NULL;
End = t;
19

20. Обхід списку і вивід

1. Прямий напрям
void print_forward(List *Begin)
2. Зворотній напрям
void print_back(List *End)
{
{
List *p = End;
List *p = Begin;
cout << "List2:" << endl;
cout << "List1:" << endl;
while(p)
while(p)
{
{
cout << p->elem << endl;
p = p->prev;
cout << p->elem << endl;
}
p = p->next;
}
}
}
20

21. Стек

Стеком називається динамічна структура даних, додавання компоненти в яку і
виключення компоненти з якої відбувається з одного кінця, який називають
вершиною стеку.
Стек працює за принципом LIFO (Last-In, First-Out) – поступив останнім,
обслуговується першим.
Використання стеку в програмуванні.
1.
Стек використовується для тимчасового збереження стану не
виконаного до кінця завдання.
2.
Використовуються при розборі (parsing) граматик (від простих виразів
алгебри до мов програмування).
3.
Як засіб моделювання рекурсії.
4.
Як модель виконання інструкцій.
21

22. Стек

Додавання елемента, або проштовхування
(push), можливе тільки в вершину стека
(доданий елемент стає першим зверху),
виштовхування (pop) - також тільки з
вершини стеку, при цьому другий зверху
елемент стає верхнім.
22

23. Стек

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

24. Опис стеку

struct ім'я типу {
інформаційне поле;
адресне поле;
};
де інформаційне поле - це поле будь-якого раніше оголошеного або
стандартного типу;
адресне поле - це вказівник на об'єкт того ж типу, що й структура, в нього
записується адреса наступного елемента стеку.
Наприклад,
Struct StackItem {
int Info;
StackItem *Next;
};
24

25. Стек

Для підтримки роботи стека необхідно знати адресу
елемента, що знаходиться на вершині стека, тобто
поміщеного в стек останнім:
StackItem *Sp=NULL;
Конструкція Sp-> Info представляє інформаційну частину, а
конструкція Sp-> Next - адреса попереднього елемента, який
був поміщений в стек безпосередньо перед поточним.
25

26. Стек

Для проходу по стеку від верхнього елемента до найпершого елементу
необхідна допоміжна змінна-посилання (наприклад - з іменем Current).
Вона на кожному кроці проходу по стеку повинна визначати адресу
поточного елемента. На самому початку проходу треба встановити
значення Current = Top, а потім циклічно змінювати його на значення
Current-> Next до тих пір, поки не буде досягнутий перший елемент
стека.
StackItem *Current = Sp;
while(Current != NULL)
{
cout << Current->Info << " ";
Current = Current->Next;
}
26

27. Стек

Для проходу треба використовувати цикл з невідомим
числом повторень, а ознакою його завершення повинно бути
отримання в полі Current-> Next порожнього посилання
NULL.
27

28. Стек

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

29. Приклад

struct Stack {
Single_List *Top; //вершина стека
};
..........
Stack *Top_Stack; //вказівник на вершину стека
//створення стеку
void Make_Stack(int n, Stack* Top_Stack){
if (n > 0) {
int tmp;//допоміжна змінна
cout << "Введіть значення ";
cin >> tmp; //вводимо значення інформаційного поля
Push_Stack(tmp, Top_Stack);
Make_Stack(n-1,Top_Stack);
}
}
29

30. Стек

Для видалення елемента с вершини стека необхідно виконати
наступні дії:
За допомогою допоміжної змінної Tmp адресувати елемент,
що видаляється: Tmp = Sp;
Змінити значення змінної Sp на адресу нової вершини стека;
Обробити видалений з вершини елемент:
Звільнити пам'ять, яку він займає.
30

31. Приклад роботи зі стеком

#include <iostream>
using namespace std;
/*НАША СТРУКТУРА*/
struct List
{
int x; //інформаціний елемент
List *Next,*Head; //Голова стека і вказівник на
наступний елемент
};
/*ФУНКЦІЯ ВІДОБРАЖЕННЯ СТЕКА*/
void Show(List *MyList) //Потрібен тільки сам стек
{
List *temp=MyList->Head; //Оголошуємо вказівник і
вказуємо йому, що його позиція в голові стеку
//за допомогою циклу проходимо по всьому стеку
/*ФУНКЦІЯ ДОДАВАННЯ ЕЛЕМЕНТА В СТЕК
while (temp!=NULL) //вихід, якщо поле пусте
(в список LIFO)*/
void Add(int x, List *&MyList) //Приймаємо
{
елемент стека і вказівник на стек, при цьому
говоримо, що вказівник, який приймає, буде сам
по собі вказівником
cout<<temp->x<<" "; //Виводимо на екран е-т стеку
{
temp=temp->Next; //Переходимо до наступного е-ту
List *temp=new List; //Виділяємо память для
нового елемента
temp->x=x; //Записуємо в поле x елемент x
}
temp->Next=MyList->Head; //Вказуємо, що
наступний елемент це попередній
}
MyList->Head=temp; //Зсуваємо голову на
позицію вперед
}
int main()
{
31

32. Черга

Черга - це структура даних, що представляє собою
послідовність елементів, яка утворена в порядку їх
надходження. Кожен новий елемент розміщується в кінці
черги; елемент, що стоїть на початку черги, вибирається з
неї першим. У черзі використовується принцип доступу до
елементів FIFO (First Input - First Output, "перший прийшов
- першим вийшов").
У черзі доступні два елементи (дві позиції): початок черги і
кінець черги. Помістити елемент можна тільки в кінець
черги, а взяти елемент тільки з її початку.
32

33. Черга

Для реалізації черги можна вибрати двонаправлений
список.
Для доступу до списку використовується не одна
змінна-вказівник, а дві – посилання на «голову» списку
(Head) і на «хвіст» - останній елемент (Tail)
33

34. Черга

Типові операції над чергою і її елементами:
• додавання елемента в хвіст черги;
видалення елемента з голови черги;
перевірка, чи порожня черга;
очищення черги.
34

35. Черга

Для програмної реалізації елемент черги треба оголосити як
структуру, яка містить три поля - інформаційне і два адресних.
Наприклад,
struct QueueElem {
double Elem;
QueueElem *nextElement;
QueueElem *prevElement;
};
35

36. Черга

Для підтримки роботи черги необхідно знати адресу елемента,
що знаходиться в голові черги QueueElem * head, і адреса
елемента, що знаходиться в хвості черги QueueElem * tail.
Для того щоб створити чергу треба створити голову списку.
Для створення нового елементу треба виділити під нього
пам'ять (наприклад, оператором new) і зв'язати з основним
списком - створити вказівники на наступний і попередній
елементи рівні 0. Для першого елемента вказівник на
попередній елемент завжди дорівнює 0.
36

37. Черга. Додавання елемента

• Виділити пам'ять для розміщення нового елемента за
допомогою допоміжної змінної-посилання Tmp;
• Заповнити інформаційну частину нового елемента;
• Встановити адресну частину нового елемента таким чином,
щоб вона визначала адресу колишнього останнього елемента
черги;
• Встановити адресну частину колишнього останнього
елемента черги таким чином, щоб вона визначала адресу
нового елемента;
• Створити новому елементу вказівник на наступний елемент
рівний Null;
• Змінити адресу хвоста черги так, щоб він визначав як кінець
черги новий елемент.
37

38. Черга. Додавання елемента

39. Черга. Вилучення елемента

Вилучити інформаційну частину першого елемента черги
За допомогою допоміжної змінної Tmp адресувати елемент,
що видаляється : Tmp = Head;
Змінити вказівник другого елементу черги на попередній
елемент рівний Null;
Змінити значення змінної Head на адресу другого елементу
черги;
Звільнити пам'ять, яку займає Tmp.
39

40. Очистка черги

За допомогою допоміжної змінної Tmp адресувати
елемент, що видаляється : Tmp = Head;
Змінити вказівник елемента, наступного за тим, що
видаляється, на попередній елемент рівний Null;
Змінити значення змінної Head на адресу наступного
елемента затим, що видаляється;
Звільнити пам'ять, яку займає Tmp;
Якщо в черзі є ще елементи, перехід до п.1;
Голові і хвосту черги присвоїти NULL.
40

41. Черга

Кільцева черга
Черга з пріоритетним
включенням
Кільцева черга, коли частина
елементів зайнята
Черга з пріоритетним
виключенням
41

42. Дек

Дек є симбіозом стека і черги - це та ж структура, але на
цей раз з нею можна працювати з обох кінців. Таким
чином, якщо ми будемо працювати з деком тільки з
лівого краю, то фактично виходить стек. Аналогічно ми
отримаємо стек, якщо будемо працювати тільки з
правого краю (кінця дека).
Користуючись приписами "додати в кінець" та "взяти з
початку", ми зможемо отримати чергу, елементи якої
будуть просуватися справа наліво.
Назва дека походить від скорочення англійських слів
Double Ended Queue - черга з двома кінцями.
42

43. Граф

Граф - це сукупність двох кінцевих множин: множини точок і
множини ліній, які попарно з'єднують деякі з цих точок.
Множина точок називається вершинами (вузлами) графа.
множина ліній, що з'єднують вершини графа, називається
ребрами (дугами) графа.
43

44. Дерева

Деревом називають кінцевий зв’язний граф з
виділеною вершиною (коренем), який не має
циклів
44

45. Бінарні дерева

Дерева, в яких кожен вузол або є листом, або утворює
два піддерева: ліве і праве, називаються бінарними
деревами і використовуються при поділі множини на
дві взаємовиключних підмножини за деякою ознакою
(дихотомічне ділення).
45

46.

Висота вузла дерева - це довжина самого довгого шляху з цього вузла
до будь-якого листа.
Висота дерева співпадає з висотою кореня.
Глибина вузла – це довжина шляху від кореня до цього вузла.
Степінь вузла – це кількість дуг, що з нього виходить.
Степінь дерева дорівнює максимальному степеню вузла, що входить у
дерево.
Листя в дереві - це вузли, що мають степінь нуль.
Бінарне дерево – це дерево степінь якого дорівнює два .
Дерева, степінь яких більше двох, називаються розгалуженими.
46

47.

Повне бінарне дерево - це дерево для якого на всіх рівнях менше
чим n вузли мають степінь 2, а на рівні n – степінь 0.
а) неповне
бінарне дерево
б) повне бінарне
дерево
47

48.

Строго бінарне дерево складається тільки з вузлів, що мають степінь
2 або 0.
Нестрого бінарне дерево містить вузли зі степенем 1.
а) строго
бінарне дерево
б) нестрого
бінарне дерево
48

49. Структура бінарного дерева

50. Бінарні дерева

Опис бінарного дерева має вигляд:
struct ім’я_типу {
інформаційне поле;
адреса лівого піддерева;
адреса правого піддерева;
};
де інформаційне поле – це поле любого раніше
оголошеного або стандартного типу;
адреса лівого (правого) піддерева – це вказівник на
об’єкт того ж типу, що і задана структура, в нього
записується адреса наступного елемента лівого
(правого) піддерева.
50

51. Бінарні дерева

Наприклад,
struct BinaryTree{
int Data; //поле даних
BinaryTree* Left; //вказівник на лівий нащадок
BinaryTree* Right; //вказівник на правий нащадок
};
Корінь дерева:
BinaryTree* BTree = NULL;
51

52. Бінарні дерева

Основні операції з бінарними деревами:
• створення бінарного дерева;
• друк бінарного дерева;
• обхід бінарного дерева;
• вставка елемента в бінарне дерево;
• видалення елемента з бінарного дерева;
• перевірка бінарного дерева на пустоту;
• видалення бінарного дерева.
52

53. Обхід дерев

Під обходом бінарного дерева розуміють
визначений порядок проходження всіх вершин
дерева. Розрізняють: прямий, зворотній та
симетричний порядки обходу.
Прямий порядок обходу:
1.почати з кореня R
2.пройти в прямому порядку ліве
піддерево A
3.пройти в прямому порядку праве
піддерево B
R
А
В
53