lektsii_OP / T15
.pdfПЛАН |
|
ДИНАМІЧНІ МОДЕЛІ СТРУКТУР ДАНИХ .................................................................................. |
1 |
Статичні і динамічні змінні ......................................................................................................... |
1 |
Управління динамічною пам’яттю........................................................................................... |
3 |
Поняття динамічної структури даних ..................................................................................... |
8 |
Динамічні масиви........................................................................................................................... |
9 |
Списки.............................................................................................................................................. |
20 |
Поняття списку ............................................................................................................................. |
20 |
Однозв’язні лінійні списки .......................................................................................................... |
23 |
Стеки .............................................................................................................................................. |
29 |
Черги .............................................................................................................................................. |
29 |
Двозв’язні лінійні списки............................................................................................................. |
33 |
Кільцеві списки ............................................................................................................................. |
35 |
Дерева.............................................................................................................................................. |
46 |
Основні визначення ...................................................................................................................... |
46 |
Класифікація дерев ....................................................................................................................... |
47 |
Бінарні дерева ............................................................................................................................... |
49 |
Бінарні дерева пошуку ................................................................................................................. |
57 |
Збалансовані дерева...................................................................................................................... |
59 |
ДИНАМІЧНІ МОДЕЛІ СТРУКТУР ДАНИХ
Статичні і динамічні змінні
Усі розглянуті дотепер елементи даних мали дещо спільне:
пам’ять під них виділялася на етапі компіляції програми, тобто перед виконанням програми (для локальних змінних мається на увазі виділення пам'яті під стек);
існували вони протягом всього часу виконання програми (підпрограми);
їх розмір визначався при оголошенні і був незмінним протягом усього часу роботи програми (підпрограми);
знищувалися вони після завершення програми (підпрограми).
Такі програмні об'єкти вважаються в програмуванні статичними (постійно розміщеними в ОП).
Особливістю статичних об'єктів є те, що звертання до них у програмі може здійснюватися за допомогою імені (ідентифікатора) відповідної змінної. Наприклад, у мові С/С++ опис змінної m виду
int m[20];
свідчить про те, що в програмі породжується статичний масив m із двадцяти цілих чисел.
Статичні змінні характеризуються тим, що їх значення зберігаються в ділянках оперативної пам'яті, які визначаються на етапі компіляції програми і не змінюються в процесі її виконання. Статичними є усі глобальні та локальні змінні програми.
1
Глобальні змінні розміщуються компілятором в одній неперервній області оперативної пам'яті, яку називають сегментом даних (або областю глобальних даних); локальні змінні - у сегменті стека, який очищається після завершення виклику підпрограми.
Використання при програмуванні лише статичних об'єктів не завжди дозволяє отримувати ефективні програми, що буває надзвичайно важливим при вирішенні ряду задач. Справа у тому, що іноді на етапі написання програми не тільки не відомий розмір конкретного програмного об’єкта, але й те чи буде він існувати взагалі. Наприклад, із вхідної послідовності чисел треба сформувати масив від'ємних чисел. Розмір такого масиву залежить від кількості від'ємних чисел. Однак, якщо від'ємних чисел у вхідній послідовності немає, то такого масиву взагалі не буде існувати.
Окрім того, обсяг сегмента даних, що служить для розміщення статичних змінних, обмежений (зазвичай 64 Кб). При необхідності роботи з великими масивами інформації цього може виявитися недостатньо, особливо коли відомо, що вони потрібні не на увесь час виконання програми, а тільки на якусь незначну його частину.
Тому у мовах програмування існує і інший спосіб виділення пам'яті під дані, який називають динамічним. Він передбачає, що виділення та звільнення пам'яті під дані відбувається у міру необхідності в процесі виконання програми. Програмні об'єкти, створені таким чином, називають динамічними. Отже, динамічні змінні характеризуються тим, що створюються і знищуються у процесі виконання програми.
Значення динамічних об'єктів розміщуються у спеціальній області оперативної пам'яті, яку називають динамічною пам’яттю (купою, Heap).
У загальному випадку, під час виконання програми оперативна пам'ять необхідна для розміщення наступних програмних одиниць і даних:
самої програми користувача;
системних програм часу виконання, які здійснюють допоміжні дії при роботі програми користувача;
визначених користувачем структур даних і констант;
точок повернення для програм;
тимчасової пам'яті при передачі параметрів;
буферів вводу-виводу, що використовуються як тимчасові області пам'яті, в яких зберігаються дані між моментом їх реальної фізичної передачі з зовнішнього пристрою або на нього і моментом ініціалізації в програмі операції введення або виведення;
різних системних даних (інформації про статус пристроїв введеннявиведення та ін.) тощо.
Уся інша вільна оперативна пам'ять комп'ютера і є динамічною пам’яттю, що надається програмі при її роботі. Обсяг Heap і її місце розташування залежать від моделі пам'яті, яка визначає логічну структуру пам'яті програми. Зазвичай,
2
розміщується динамічна пам’ять за старшими адресами відразу за стеком даних (рис. 1). Адреса початку Heap зберігається в стандартному покажчику HeapOrg, кінець - у покажчику HeapEnd, поточний блок незайнятої динамічної пам'яті - у
HeapPtr.
|
Вільна (не розподілена) пам'ять |
HeapEnd |
|
Динамічна пам'ять |
HeapPtr |
|
(росте нагору ) |
HeapOrg |
16 Кб |
Сегмент стека |
|
|
(росте вниз ) |
Sseg:SPtr (SP) |
|
Вільна пам'ять стека |
Sseg:0000 (SS) |
64 Кб |
Сегмент даних програми |
DSeg:0000(DS) |
64 Кб |
Сегмент коду програми |
|
Рис. 1. Схема розподілу оперативної пам'яті при роботі програми
Використання динамічних об'єктів надає програмісту ряд додаткових можливостей. По-перше, використання динамічної пам'яті дозволяє суттєво збільшити обсяг оброблюваної інформації. По-друге, якщо потреба у якихось даних відпала до закінчення програми, то зайняту ними пам'ять можна звільнити для іншої інформації. По-третє, використання динамічної пам'яті дозволяє створювати структури даних змінного розміру.
Управління динамічною пам’яттю
Використання динамічних об'єктів спричиняє певні труднощі, які полягають, зокрема, у тому, що виникають об'єкти динамічно, у процесі виконання програми, а дії над ними необхідно задавати статично при написанні програми. Окрім того, за замовчуванням, пошук усіх даних здійснюється тільки в сегменті даних.
У мовах програмування зазначена проблема вирішується шляхом використання спеціального посилального типу даних. Посилальний тип - це особливий статичний тип даних, значеннями якого є не конкретні дані (числа, символи, рядки і т.ін.), а покажчики на які-небудь програмні об'єкти, за якими здійснюється безпосередній доступ до цих об'єктів.
Для опису дій над динамічними об'єктами кожному такому об'єкту в програмі ставиться у відповідність свій статичний покажчик у термінах якого і описуються дії над відповідними динамічними об'єктами. Сам же динамічний об'єкт за необхідності створюється пізніше, під час виконання програми. Зв'язок покажчика з об'єктом схематично можна представити так:
3
статична |
динамічна |
пам'ять |
пам'ять |
* |
5 |
11 |
9 |
24 |
3 |
|
Таким чином, доступ до динамічних даних виконується за допомогою покажчиків. Покажчик містить адресу певного об'єкта в динамічній пам'яті. Сам покажчик є статичним об'єктом і розташований в сегменті даних.
Створення (породження) динамічних об'єктів здійснюється спеціальними засобами (функціями, операторами) розподілу динамічної пам'яті. При цьому в Heap-області виділяється блок пам'яті необхідного розміру (в залежності від типу об'єкта) і адреса його початку стає значенням змінної-покажчика на динамічний об'єкт.
Подальша робота з таким об'єктом здійснюється через відповідну змінну-покажчик. Сам же динамічний об'єкт (динамічна змінна) залишається безіменним.
Породження динамічних об'єктів (виділенням під них динамічної пам’яті) у мовах програмування здійснюється різними програмними засобами. Зокрема, у мові С для цього використовуються функції malloc() і calloc().
Функція malloc() (від англ. “memory allocation” – виділення пам’яті) робить запит щодо виділення ділянки пам’яті заданої кількості байтів. Її прототип:
void *malloc(size_t size);
Єдиний аргумент цієї функции size − кількість байтів, яку треба виділити. Функція повертає покажчик на початок виділеної пам’яті. Якщо для розміщення заданої кількості байтів пам’яті недостатньо, функція повертає NULL. Наприклад, виділення пам’яті під 10 дійсних чисел
float *р = (float*) malloc(sizeof(float)*10);
Адреса початку цієї ділянки пам’яті записується у покажчик р.
Функція calloc() виділяє блок пам’яті заданого розміру і повертає покажчик на виділений блок. Її прототип:
void * calloc(size_t num, size_t size);
Функцією calloc() виділяється блок пам’яті розміром num*size (під num елементів по size байтів кожен). Функція повертає NULL, якщо не вистачає пам’яті для виділення нового блока, або якщо значення num чи size дорівнюють 0.
Особливістю calloc() є те, що кожен елемент виділеного блока ініціалізується нульовим значенням (на відміну від функції malloc()).
Наприклад, виділення пам’яті під 10 дійсних чисел за допомогою функції calloc():
float *р = (float*) calloc(10, sizeof(float));
Функція realloc() змінює розмір виділеної раніше пам'яті. Звертаються до неї так:
char *realloc (void *p, size);
4
Тут p - покажчик на область пам'яті, розмір якої потрібно змінити на size. Якщо в результаті роботи функції змінюється адреса області пам'яті, то нова адреса повернеться в якості результату. Якщо фактичне значення першого параметра NULL, то функція realloc() працює так же, як і функція malloc(), тобто виділяє ділянку пам'яті розміром size байт.
Пам’ять, виділену за допомогою функцій malloc() або сalloc(), звільнюють за допомогою функції free():
void free(*p);
де *p – адреса початку виділеної раніше пам’яті, наприклад,
free(р);
В С++-програмах, окрім функцій malloc() і calloc(), які перейшли до С++ з С, передбачені власні засоби виділення динамічної пам’яті - оператори new і delete.
Оператор new дозволяє виділити і зробити доступною ділянку динамічної пам'яті, яка відповідає заданому типу даних. Його формат:
new тип; new (тип);
Наприклад,
int *p= new int; float *r=new (float);
Тут оператор int *p=new int виконує дві дії: оголошує змінну типу покажчик і далі присвоює їй адресу виділеної області пам’яті у відповідності із заданим типом об’єкта. Аналогічно оголошує покажчик на динамічне дійсне число оператор float *r=new (float).
Ініціалізація значення, що знаходиться за адресою покажчика, виконується схожим чином, тільки в кінці ставляться круглі дужки з потрібним значенням:
new тип (значення).
Наприклад,
int *р = new int (5);
Подальша робота з динамічними змінними відбувається так само, як і з статичними змінними відповідних типів.
Змінні-покажчики (саме вони синтаксично виконують роль динамічних змінних) можна використовувати в будь-яких конструкціях мови програмування, де допускається використання статичних змінних того ж типу. Їм можна присвоювати значення, їх можна використовувати в якості операндів у виразах і параметрів підпрограм тощо. До них можна застосовувати всі ті операції, які допустимі у відповідності із базовим типом.
Наприклад,
int i; int *р;
5
i = 2;
*р = *р*6 + i;
Хоча Heap-область велика, але і її можна вичерпати, якщо не піклуватися про звільнення пам'яті, коли ті чи інші динамічні дані стають непотрібними. Окрім того, якщо динамічний об'єкт втрачає свій покажчик, то він стає "сміттям", тобто інформацією, яка займає пам'ять, але вже не потрібна. Тому, якщо в процесі виконання програми деякий динамічний об'єкт стає непотрібним, то його можна знищити (відмовитися від виділеного для нього місця в пам'яті). Особливо істотним ефект економії пам'яті стає при видаленні великих масивів.
Для звільнення пам’яті, виділеної оператором new, використовується оператор delete наступного формату:
delete покажчик;
Після цього відповідна область пам'яті повертається в пул вільної пам’яті і стає доступною для розподілу під інші динамічні змінні; значення ж змінної-покажчика стає невизначеним. Застосування delete до покажчика, отриманого не за допомогою new, не визначено.
Слід відзначити, що оператором delete знищується лише сам динамічний об'єкт, але не покажчик на нього.
Розглянемо приклад. Нехай у програмі створені наступні динамічні об'єкти:
int *p= new int; int * w= new int;
Прослідкуємо зміни їх значень і значень відповідних покажчиків в результаті послідовного виконання наступних операторів присвоєння:
*p = 3; *w = 58; p = w;
w = NULL;
Для наочності отримані при цьому результати представимо у вигляді наступної схеми (рис. 2).
*p=3; *w= 58; |
p |
|
|
|
|
|
|
|
|
|
|
3 |
w |
|
|
|
|
|
|
|
|
|
58 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
p = w; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
w = NULL; |
p |
|
|
|
|
|
|
|
|
|
|
3 |
w |
|
|
|
|
|
|
|
|
|
58 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
p |
|
|
|
|
|
|
|
|
|
|
3 |
w |
|
|
|
|
|
|
|
|
|
58 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 2. Зміна значень покажчиків
Слід звернути увагу, що в даному прикладі після виконання оператора присвоєння р = w на динамічний об'єкт із значенням 3 не вказує жоден покажчик, тобто він став недоступним для програми. З іншого боку, в результаті виконання цього ж оператора присвоєння не утворюється новий динамічний об'єкт із значенням 58, а
6
покажчик р посилатиметься на вже існуючий динамічний об'єкт (на який посилається і покажчик w).
Важливо чітко розуміти різницю між покажчиком і значенням динамічного об'єкту. Якщо замість оператора р = w у попередньому прикладі виконати оператор *р=*w, то отримаємо наступний результат:
*p=3; *w=58; |
p |
|
|
|
|
|
|
|
|
3 |
w |
|
|
|
|
|
|
|
|
58 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
*p=*w; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
p |
|
|
|
|
|
|
|
|
58 |
w |
|
|
|
|
|
|
|
|
58 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
З урахуванням вищезазначеного, послідовність операторів, схема виконання яких представлена на рис. 1, слід було б модифікувати таким чином:
*p = 3; *w = 58; delete (р);
p= w; w= null;
В результаті виконання оператора р = w динамічний об'єкт, на який раніше посилався покажчик р, стане недоступним для використання в програмі, тому цей об'єкт можна заздалегідь знищити (за допомогою оператора delete) і звільнити займане ним місце у пам'яті.
Схематично результати виконання окремих етапів цього програмного фрагмента представлені на рис. 3.
*p=3; *w=58; |
p |
|
|
|
|
|
|
|
|
|
3 |
w |
|
|
|
|
|
|
|
|
58 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
delete(p); p=w; |
p |
|
|
|
|
|
|
|
|
|
|
w |
|
|
|
|
|
|
|
|
58 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
w=null; |
p |
|
|
|
|
|
|
w |
|
|
|
|
|
|
|
|
58 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 3. Використання функції Delete
На відміну від рис. 2, на рис. 3 динамічний об'єкт із значенням 3 зник, тобто пам’ять, що була ним зайнята, приєдналась до вільної пам’яті комп’ютера.
Здатність визначати розмір об'єкта і виділяти для його зберігання відповідну область пам'яті в процесі виконання програми називають управлінням динамічною пам'яттю. Управління розміщенням об'єкта в Heap-області здійснюється за допомогою стандартного покажчика HeapPtr (поточної адреси в Heap-області). Щораз при створенні динамічного об'єкта цей покажчик зміщується на число байт, яке відповідає розміру відповідного динамічного об'єкта.
Самі динамічні величини не вимагають опису в програмі, оскільки під час компіляції пам'ять під них не виділяється. Під час компіляції пам'ять виділяється тільки під статичні величини. Покажчики - це статичні величини, тому вони вимагають опису.
7
Поняття динамічної структури даних
Особливостями статичних структур даних, які розглядалися раніше, є те, що їх розмір (обсяг виділеної пам'яті), взаєморозташування і взаємозв’язки елементів завжди залишаються постійними.
На відміну від них, динамічні структури даних – це дані складної структури, розмір яких (кількість елементів), взаєморозташування і взаємозв’язки можуть змінюватися в процесі виконання програми.
Така особливість динамічних структур, як непостійність їх розміру та характеру відносин між елементами, призводить до того, що на етапі створення машинного коду програма-компілятор не може виділити для всієї структури в цілому ділянку пам'яті фіксованого розміру, а також не може зіставити з окремими компонентами структури конкретні адреси.
Вирішенням проблеми адресації динамічних структур даних є використання методу динамічного розподілу пам'яті, який передбачає, що пам'ять під окремі елементи виділяється в момент, коли вони "починають існувати" в процесі виконання програми, а не під час компіляції. Компілятор в цьому випадку виділяє фіксований обсяг пам'яті для зберігання адреси динамічного елемента, а не самого елемента. Тобто, для організації динамічних структур даних використовують динамічні змінні.
Отже, динамічна структура даних характеризується тим, що:
вона не має імені;
пам'ять під неї виділяється і звільняється в міру необхідності в процесі виконання програми;
у неї відсутністя фізична суміжність елементів структури в пам'яті;
кількість її елементів може змінюватися в процесі виконання програми;
в процесі виконання програми може змінюватися взаєморозташування і характер взаємозв'язку між її елементами.
Необхідність у динамічних структурах даних, зазвичай, виникає в наступних випадках:
використовуються змінні, що мають досить великий розмір (наприклад, масиви великої розмірності), необхідні в одних частинах програми і абсолютно не потрібні в інших;
в процесі роботи програми потрібен масив, список чи інша структура, розмір якої змінюється в широких межах і є важко передбачуваним;
коли розмір даних, що обробляються в програмі, перевищує обсяг сегмента даних.
Основними різновидами динамічних структур даних є динамічні масиви, списки та дерева. Вони відрізняються способом зв'язування окремих елементів і / або допустимими операціями.
8
Динамічні масиви
Під час роботи довільної програми значення деякої статичної змінної може змінюватися, але власне кількість оголошених статичних змінних не змінюється. Це не завжди зручно. Наприклад, якщо програма призначена для введення та обробки даних про учнів класу, а для збереження цих даних використовується звичайний масив, то визначаючи розмір масиву, приходиться орієнтуватися на деяке, як здається програмісту, граничне значення учнів в класі. При цьому якщо реально учнів в класі менше цього граничного значення, то пам’ять ПК використовується неефективно. Якщо ж учнів більше – то таку програму використовувати взагалі не можна.
В таких задачах зручно використовувати так звані динамічні масиви.
Динамічним називають масив, розмір якого може визначатися під час виконання програми. Динамічні масиви роблять роботу з даними більш гнучкою, оскільки не вимагають попереднього визначення збережених обсягів даних, а дозволяють регулювати розмір масиву відповідно до реальних потреб.
Для розміщення в пам'яті динамічних масивів застосовується традиційні засоби породження динамічних об'єктів. Зокрема, у С++ для цього служить оператор new[]1 наступного формату:
new тип[розмір].
Оператор new[] виділяє для розміщення масиву ділянку динамічної пам'яті відповідного розміру і повертає покажчик, значенням якого є адреса першого елемента масиву. Наприклад,
float *р = new float [20].
Динамічні масиви при створенні не можна визначати (ініціалізувати) і вони не заповнюються нулями.
Доступ до елементів динамічного масиву здійснюється так само, як і до елементів статичного. Наприклад, p[5] або *(p+5).
Для звільненні пам'яті, виділеної оператором new [] під масив, використовується оператор delete []:
delete [ ]покажчик.
Тут квадратні дужки вказують компілятору на те, що звільняти слід ту кількість комірок пам'яті, яка була захоплена в останній операції new в застосуванні до покажчика. Явно вказувати це число не потрібно.
Наприклад,
float *р;
р = new float[10]; // виділення 10 блоків розміром типу float
...
delete [ ]р.
1 У С++ існують дві форми операторів new і delete: для одиночної змінної і масиву значень
9
Розмір динамічного масиву може задаватися через змінну. Наприклад,
int n;
cout<<"size of array ="; cin>>n;
int *p= new int[n]; |
|
for (int i=0; i<n; i++) |
|
{ p[i] = i*4; |
// *(pi+i) |
printf("adres -%p, content -%d\n", &p[i], p[i]);
}
delete[]p;
Іноді при програмуванні виникає необхідність створення багатовимірних динамічних масивів. У більшості мов програмування, зокрема, і у C++, багатовимірний динамічний масив є за своєю суттю одновимірним. При розміщенні елементи таких масивів розташовуються в пам’яті підряд один за одним у послідовно зростаючих адресах пам’яті. Наприклад, масив 3×5 зберігається у пам’яті в такий спосіб:
У такому масиві перші п’ять елементів належать до першого рядка, наступні п’ять – до другого і останні п’ять – до третього. Якщо р – покажчик на початок масиву, тобто на елемент р[0][0], то щоб звернутися, наприклад, до елемента р[1][3], слід “перестрибнути” від початку масиву через 5 елементів нульового рядка і 3 елементи першого рядка, тобто написати: *(р+1*5+3). У загальному випадку до елемента р[i][j] можна звернутися в такий спосіб: *(р+i*5+j).
Оголошення такого масиву як одновимірного динамічного масиву з 15-ти елементів може мати вид:
int *р= new int[3*5];
Його ініціалізація може здійснюватися у такий спосіб:
int *p = new int[3*5]; for (int i=0; i<3*5; i++)
{p[i] = i*5; printf("%d\n", p[i]);
}
Пам’ять від створеного в такий спосіб масиву очищується за допомогою операції delete [], наприклад,
delete []р;
Однак є і інший спосіб роботи з динамічним двовимірним масивом, характерний для представлення двовимірних масивів у мовах С/С++. Він передбачає окреме розміщення в пам’яті кожного рядка матриці як окремого одновимірного масиву, а також допоміжного масиву, де зберігатимуться адреси нульових елементів цих масивів (рис. 4).
10