визначений тип необхідно ознайомитися з механізмом розширення масиву при його переповненні, що забезпечить можливість зберігання більшого числа елементів списку, ніж заздалегідь задано розміром масиву, при його створенні.
3. Дослідження існуючих методів організації динамічних структур даних
Статична розподіл пам'яті вимагає резервування обсягу пам'яті для статичних даних у тексті програми ще до її виконання. Динамічний розподіл пам'яті передбачає визначення необхідного обсягу пам'яті в процесі виконання програми. Необхідну простір пам'яті вибирається з вільного адресного простору ОЗУ.
Покажчики динамічної пам'яті використовуються для адресації (посилання) на окремий динамічний об'єкт або сукупність певним чином організованих однотипних динамічних об'єктів (змінних). І в кожен конкретний момент дозволяє звернутися тільки до одного об'єкту. Міняючи значення покажчика, ми можемо звернутися до іншого динамічному об'єкту того ж типу.
При цьому ми повинні організувати певну динамічну структуру даних, яка дозволить нам без особливих зусиль здійснювати необхідні маніпуляції з тими даними, які вводить користувач. Один із способів побудови списків, що набули поширення, полягає в тому, що елементи списку безпосередньо не пов'язані між собою, а замість цього покажчики на ці елементи групуються в деякому одновимірному масиві, який відображає структуру списку. Послідовність розташування покажчиків у такому масиві визначає послідовність розташування елементів у списку. Відповідно, переміщення елементів у списку зводитися до переміщення покажчиків в масиві.
Отже, для розміщення представленого таким чином списку в пам'яті, в ній повинні розташовуватися як самі елементи списку, так і масив покажчиків на ці елементи. Масив покажчиків може мати фіксований розмір і постійне місце проживання у пам'яті, або змінний розмір, а внаслідок цього, і динамічно мінливий його місце в пам'яті. Відповідно, розрізняються статичні і динамічні масиви покажчиків.
Для розміщення даних мультіспісковой структури більш раціонально використовувати саме динамічні масиви покажчиків, оскільки заздалегідь невідомо, скільки елементів списку буде розміщено користувачем на тому чи іншому рівні ієрархії. Використання такої динамічної структури дозволить по необхідності розмістити в пам'яті масив більшого розміру, що дозволить додавати дані, навіть після того, як первісний розмір масиву буде перевищений.
На відміну від динамічних, статичні масиви мають заздалегідь заданий розмір і не змінюють його в ході роботи програми. Це є істотним недоліком, з яким потрібно рахуватися при виборі структури для зберігання даних. Головна проблема полягає в тому, що при розміщенні в пам'яті масиву занадто малого розміру, додавання нових елементів у масив буде неможливим. З іншого боку, при виділенні масиву занадто великого розміру з'являється ймовірність нераціонального використання системних ресурсів (оперативної пам'яті), оскільки не завжди буде використовуватися хоча б половина з виділеної пам'яті.
Проаналізувавши переваги та недоліки кожного з методів, було прийнято рішення про вибір динамічного масиву покажчиків в якості структури для зберігання даних. Даний метод реалізації мультіспіска дозволить виробляти раніше описані операції з обробки ієрархічної структури даних, заданої відповідно до варіанту дипломного проекту.
4. Визначення шляхів і рішення задачі
. 1 Побудова мультіспіскових структур
Для обробки даної структури, тобто для реалізації завдання введення, видалення, додавання даних про кожному структурному елементі необхідні функції відповідні даним операціям. Особливостями побудови мультіспіска буде те, що для обробки мультіспісковой структури використовуються інваріантні функції пошуку елементів в ієрархічній структурі. Для цього необхідно в функцію пошуку передавати покажчик на функцію порівняння, яка буде повертати ознака рівності ключових полів структур, які знаходяться на одному рівні ієрархії.
Особливістю побудови мультіспіскових структур є також те, що для знаходження якого-небудь елемента, за його ключовому полю, в якому-небудь рівні або підрівні не потрібно виконувати перегляд всіх елементів на цьому рівні, оскільки кожен рівень мультіспісковой структури відсортований, тобто елементи в масиві розташовані в алфавітному порядку.
. 2 Методи реалізації мультіспіскових структур використовуючи особливості мови C ++
Як вже було зазначено раніше, використання покажчиків на функції порівняння, для передачі їх в якості параметрів функції дозволяє реалізувати інваріантні функції пошуку (як методом перебору, так і методом бінарного (д...
