Графи P
ГЛАВА 7
ДИНАМІЧНІ СТРУКТУРИ ДАНИХ R
Особливості динамічних структурP
Лінійні зв'язні списки P
Нелінійні розгалужені списки P
Керування динамічною пам'яттю P
Графи P
Дерева P
ДИНАМІЧНІ СТРУКТУРИ ДАНИХ
Динамічні структури даних по визначенню характеризуються:
Ø відсутністю фізичної суміжності елементів структури в пам'яті,
Ø мінливістю і непередбачуваністю розміру (числа елементів) та структури в процесі її обробки.
Лінійні зв'язні списки
МАШИННЕ ПРЕДСТАВЛЕННЯ ЗВ'ЯЗНИХ ЛІНІЙНИХ СПИСКІВ.
У пам'яті зв’язний список (linked list) являє собою сукупність дескриптора й… Розрізняють лінійні і кільцеві однозв'язні та двозв'язні списки.
Лінійні списки знаходять широке застосування в додатках, де непередбачені вимоги на розмір пам'яті, необхідної для збереження даних; велике число… На базі лінійних списків можуть будуватися стеки, черги, деки. Представлення… Лінійні зв'язні списки іноді використовуються також для представлення таблиць – у тих випадках, коли розмір таблиці…
Нелінійні розгалужені списки
Нелінійним розгалуженим списком є список, елементами якого можуть бути теж списки. Якщо один з покажчиків кожного елемента списку задає порядок… Якщо ж один з покажчиків задає порядок довільного виду, що не є зворотним… ОПИС СПИСКІВ. Якщо списки узяти в круглі дужки, а елементи списків розділити комами, то як списки можна вважати такі…
У відповідності зі схематичним зображенням розгалужених списків типова структура елемента розгалуженого списку повинна мати такі поля: data – дані… Поле рtype містить ознаку атом/вузол, вона може бути 1 – бітовою. Такий формат… У цьому випадку покажчик down указує на дані або на підсписок. Оскільки списки можуть складатися з даних різних типів,…
Найбільше впровадження списки знайшли у мові програмування LISP. LISP – це мова обробки списків. Усі дані в LISP представляються у вигляді списків,… Як правило, уся програма на LISP являє собою єдине звертання до функції з… Інші мови обробки списків, наприклад IPL-V, COMMIT більше орієнтовані на рішення прикладних задач, а не на обробку…
Динамічні структури по визначенню характеризується мінливістю і непередбачуваністю розміру. Тому пам'ять під окремі елементи таких структур… У сучасних обчислювальних середовищах велика частина питань, зв'язаних з… У загальному випадку при розподілі пам'яті повинні бути вирішені наступні питання:
Графи
Граф - це складна нелінійна багатозв’язна динамічна структура, що відображає властивості і зв'язки складного об'єкта і має наступні властивості:
- на кожен елемент (вузол, вершину) може бути довільна кількість посилань;
- кожен елемент може мати зв'язок з будь-якою кількістю інших елементів;
Існують два основних методи представлення графів у пам'яті ЕОМ: матричний, тобто масивами, і зв'язними нелінійними списками. Вибір методу… МАТРИЧНЕ ПРЕДСТАВЛЕННЯ ОРГРАФІВ. При використанні матриць суміжності їхні… Наприклад, для простого орієнтованого графа, зображеного на рис. 7.5 масив визначається як:
Алгоритми обробки графів аналогічні алгоритмам обробки нелінійних списків, до яких можуть бути віднесені графи. Як приклад приведемо програму, що… АЛГОРИМ ДЕЙКСТРИ.Нехай дана частина карти дорожньої мережі і потрібно знайти… Така задача виглядає досить просто, але "найкращий" маршрут можуть визначати багато факторів. Наприклад:…
Дерева
Дерево - це граф, що характеризується наступними властивостями:
- існує єдиний елемент (вузол, вершина), на який не посилається ніякий інший… - починаючи з кореня і переміщаючись по визначеній послідовності покажчиків, що зберігаються в елементах, можна…
Мається ряд способів графічного зображення дерев (див. рис. 7.17).
1). Використання діаграм Венна, що наочно показують вкладеність піддерев.
2). Спосіб, застосовуваний при складанні змісту книги; має просту програмну реалізацію.
LPTR
DATA
RPTR
Рис. 7.19. Структура вузла дерева
Відрізняють m-арні дерева, тобто такі дерева в яких напівступінь виходу кожної вершини менше або дорівнює m (де m може дорівнювати 0,1,2,3 і т.д.).…
ІДЕАЛЬНО ЗБАЛАНСОВАНІ ДЕРЕВА.Дерево називається ідеально збалансованим, якщо число вершин у його лівих і правих піддеревах відрізняється не більше…
- обхід дерева у визначеному порядку,
- пошук вузла з заданим ключем,
- додавання нового вузла,
КОДИ ХАФФМАНА.Це приклад, коли двійкові дерева використовуються в якості структур даних. Нехай маємо сповіщення, в якому символи незалежні і… А чи можна винайти інший код з меншою середньою довжиною? Дійсно, є код з…
ВПРАВИ
1. Постройте зв’язаний список суміжності для графа на рис. 7.11.
2. Для графа, поданого на рис. 7.11 використайте
а) алгоритм Дейкстри для знаходження самих коротких шляхів від вершини 2 до всіх інших;
б) алгоритм Флойда для знаходження самих коротких шляхів між всіма парами вершин.
3. Коренем ациклічного орграфа зветься така вершина, із якої можна дістатися до всіх інших. Напишіть програму, що визначає, чи має даний ациклічний орграф корінь.
4. Розробіть алгоритм і програму для читання арифметичного виразу, що представлений у вигляді розгалуженого списку.
5. Мається зв’язний лінійний список з ключовим полем цілого типу. Напишіть програму для сортування списку за спаданням ключа.
6. В кільцевий (циклічний) список часто вводять так званий заголовок списку. Навіщо такі заголовки? Напишіть процедури для
а) додавання,
б) видалення,
в) пошуку елемента по заданому ключу. Зробіть це для списку із заголовком та без нього.
7. Завдання 6 виконайте для двозв’язного списку.
8. Напишіть структуру m-арного дерева за своїм розсудом. Поретворіть його в бінарне.
9. Запишіть арифметичний вираз за своїм розсудом. Створіть відповідне для нього дерево. Виконавши обход дерева, запишіть префіксну, інфіксну та посфіксну форми запису заданого виразу.
10. Напишіть програму, що для бінарного дерева визначає:
а) кількість вузлів,
б) кількість віток ,
в) глибину цього дерева.
11. Мається двійкове дерево пошуку. Напишіть програму, що знаходить усі листи і видає їх ключі.
12. Розробити програму для визначення глибини мінімального, максимального елемента двійкового дерева.
13. Для двійкового дерева напишіть програму, що визначає кількість:
а) листів в дереві,
б) внутрішніх вузлів в дереві,
в) вузлів, що мають тільки лівого сина,
г) вузлів, що мають тільки правого сина.
14. Напишить фразу. Визначте ймовірність появи символів в рядку. Закодуйте символи, що входять в рядок
а) кодами однакової довжини,
б). кодами Хаффмана.
Визначте середню довжину коду в обох випадках, зробіть висновки.