Відображення АСД на СДХ.
Наше завдання:
1.Найті відображення АСД
-> СДХ;
2.Оценіть складність
алгоритмів операцій вставки, заміни, пошуку і
видалення при різних способах відображеннях.
1. Відображення на вектор.
Будемо припускати що ми
маємо справу з несортованими структурами. Детально що означає умова
сортування ми розглянемо в розділі IV "Сортування."
1.1. Рядок
Відображення рядка на
вектор будується так:
1. Візьмемо антітранзітіное відношення R 'таке що його Транзитивне
замикання дає R (для цього достатньо розглянути відношення лінійного порядку
R без умови 2 - умови транзитивності:
якщо (a, b) і (b, c)
належать R, то (a, c) теж належить R;
Ясно що R 'задає відношення сусідства, тобто (a, b) принале. R '
якщо і тільки якщо
Не істот. c: c принале.
M, (a, c) прінадл.R 'і (c, b) прінадл.R'
2.Возьмем мінімальний елемент у рядку (він існує в силу
властивості відношення лінійного порядку R), і нехай це a;
3.Елементи a зіставимо перший компонент вектора: I (a) = 1;
4.Паре (b, c) прінадл.R 'зіставимо I (c) = I (b) 1.
В одному векторі можна
зберігати декілька рядків. Для цього існує два принципово різних способи:
рядки розділяються спеціальним ознакою - ознакою кінця, якого немає серед
символів строк; інший спосіб - на початку кожного рядка вказується її довжина.
Останній спосіб
краще коли ми маємо справу з рядками змінної довжини, а першу
хороший коли рядки фіксованої довжини.
Розглянемо складність операцій пошуку, вставки, видалення і заміни.
Операції вставки, видалення і заміни містять операцію пошуку як складову
частину.
Припускаємо що частота
зустрічальності всіх елементів у рядку одна й та ж. Тоді в середньому (коли ми
маємо справу з безліччю рядків, а не з однією, двома) нам доведеться просомтреть
половину рядки, щоб знайти потрібний символ:
(1/N) + (1/N) 2 + (1/N) 3 +...+( 1/N) N = (N +1)/2 = ~ N/2
Звідси випливає складність пошуку (кількість операцій порівняння)
пропорційна половині довжини рядка.
Для операції вставки
складність проворціональна довжині рядка. Дійсно, нам треба N/2 порівнянь,
щоб знайти місце для вставки, а потім N/2 зрушень вправо, щоб звільнити
місце для нового елемента.
Складність операції
видалення дорівнює складності операції вставки. Міркування тут аналогічно
попереднім.
Неважко підрахувати
складність операції заміни - N/2 1.
Основний висновок полягає в тому, що при відображенні рядка на вектор
всі операції з рядком мають лінійну складність, пропорційну довжині
рядка.
1.2. Граф (дерево)
Відображення графа на
вектор будується через метріцу суміжності або матрицю інцідентностей. У Pascal,
де є двовимірні масиви таке подання графа очевидно. (Див.
подання лабіринту в задачі про Аріадні і Тезея.) При відображенні на вектор
можливо два підходи: відображення по рядках або по стовпцях.
Тут ми розглянемо випадок
відображення по рядках. Випадок відображення по стовпцях повністю аналогічний.
При відображенні за рядками елементу матриці A [i, j] зіставляється елемент
вектора V [k], де
k = (i-1) n + j, де n --
довжина рядка.
Тепер оцінимо складність операції пошуку. Нам доведеться переглянути
в середньому половину рядків - N/2, і половину елементів у кожному рядку - N/2 при
умови, що часто зустрічальності всіх елементів однакова. Таким чином складність
операції пошуку пропорційна N ^ 2/4 або N ^ 2 при великих N.
Однак при оперції
видалення нам не треба зрушувати всі елементи як у випадку з рядком. Однак,
операція вставки трубет зміни розмірності матриці суміжності по кожному
вимірюванню з N на N +1. Для цього нам доведеться виконати (N +1) операцій
привласнення, щоб заповнити новий рядок у векторі, плюс N 1 зрушень рядків,
щоб додати до кожної старої рядку по новому елементу, що відповідає N 1
колонку. Кількість операцій зсуву визначається таким співвідношенням:
Таким чином складність операції вставки буде дорівнює
N ^ 2/4 + N ^ 3/2 = N ^ 2 (N +2)/2.
Слід звернути увагу що як і раніше значний внесок у
складність операцій з графами становить операція пошуку.
Для k-ічного дерева можна
запропонувати спеціальний спосіб відображення на вектор. Компоненту V [0]
співставляємо кореня дерева; компоненти V [1] ... V [k] співставляємо нащадкам кореня,
потім з V [k +1] з V [2k] розміщуємо нащадків V [1], з V [2k +1] - V [3k] - нащадків
V [2] і т.д. У загальному випадку нащадки i-ї вершини, розташованої на j ярусі,
буде розміщатися в компонентах вектора
з V [k (k ^ j -1)/(k-1) +
(i-1) k] компоненту
з V [k (k ^ j -1)/(k-1) + ik]
компонент.
Оцінимо складність операції пошуку при такому відображенні дерева на
вектор. Враховуючи, що висота k-ічного дерева з N вершин дорівнює
H = log (N (k-1) +1) - 1 ~ log (k) N
отримуємо що кількість листя в такому дереві ~ N ^ 2. Звідси, при
умови равновстречаемості елементів у лісі, нам треба переглянути в середньому
половину шляхів (їх число дорівнює чмслу листя в дереві) довжини H кожен. Ці
міркування дають нам величину
~ Nlog (k) N.
Порівнюючи цю оцінку з попередньою для векторного представлення
графа N, можна побачити що це подання багато ефективніше.
1.3. Стек
Оскільки стек є мо
суті одиничне дерево всі операції з якими здійснюються через корінь,
то відображення на стека на вектор цілком зрозуміло. З вектором свзиваем
вказівник p, який вказує на той компонент вектора, де в даний момент
розміщується корінь дерева. Спочатку p = 0. Операція вставки суть
p: = p +1; V [p]: =. Операція видалення: p: = p-1.
Найважливіший висновок полягає
в тому, що операції над стеком при векторному поданні не залежать від довжини
стека.
1.4. Черга
Для векторного
подання черги нам будуть потрібні дві покажчика t і h для хвоста і голови
черзі відповідно. Нагадаємо, що видалення елемента з черги можливо
тільки з голови черги, а вставка - тільки з хвоста.
Одне з можливих відображень
черги на вектор полягає в тому, що вважаємо спочатку h: = N; t: = N. Тоді
вилучення елемента - h: = h-1; а вставка - t: = t-1.
Таке відображення володіє тим недоліком, що якщо загальне число
елементів, які пройшли через чергу - M>> N, за умови, що довжина черги
не більше N, то після вставки N елементів ми вичерпаємо довжину вектора в покажчику
t.
Можна модифіковані цей метод - зафіксувати положення
покажчика h: = N. Тоді при вилученні елемента з черги нам треба буде переміщувати
всі елементи на одиницю вправо і коректувати значення покажчика t. Чим
більше середня довжина черги, тим менш вигідно таке подання (довжина
зсуву збільшується).
Третій спосіб
подання черги через вектор полягає в тому, що ми "загинаємо"
вектор в кільце. Для цього достатньо виконувати всі операції в покажчиками по
модулю N. При такому поданні черги складність операцій вставки та вилучення
стають абсолютно не залежними від розміру черги.
1.5. Таблиці
Відображення таблиць на
векторну пам'ять буде розглянуто пізніше в розділі "Таблиці".
Основним недоліком
векторного подання АСД - обмеженість довжини вектора. Її ми повинні знати
заздалегідь. Крім цього, як ми бачили досить часто нам доводиться рухати
компоненти вектора при вставці і видалення елементів у векторі.
2. Представлення АСД в списковому пам'яті
2.1. Поняття списку
Списком називається
безліч ланок виду
|------------------------------------|
| тіло ... | Вказівник на
ланка |
|------------------------------------|
ув'язаних в ланцюжок за допомогою покажчиків один на одного.
Поле тіло предназнаяено
для зберігання власне даних, поле покажчик на ланка - для посилання на
сусіднє ланка. В одній ланці може бути кілька полів покажчик на ланка.
Значення цього поля - посилання на ланка.
Кожне посилання відповідає
орієнтованої, впорядкованої парі щодо деякої структури даних.
Уздовж покажчика можна рухатися тільки в одному напрямку.
Ланки можна використовувати
як для представлення елементів безлічі структури, так і для представлення
елементів відносини. Ланки можна використовувати для нарощування довжини поля тіло,
для зв'язку ланок між собою.
Основний недолік списку
- Витрати пам'яті на зберігання покажчиків. Чим складніша структура - тим більше
покажчиків треба для її подання, тим більше пам'яті витрачається під
покажчики.
Основна перевага --
необмеженість за розміром, динамічність у керуванні й організації.
2.2. Представлення рядків
Для подання рядків
можна використовувати ланки з наступними видами поля тіло:
- односімвольние ланки;
- многосімвольние ланки;
- ланки змінної довжини
(в Pascal де динамічні структури змінної довжини не підтримуються цього
виду ланки не ефективні);
По організації поля вказівник на інше ланка:
-односпрямовані;
-двонаправлені;
-мультіссилочние (коли
один елемент структури пов'язаний з декількома іншими елементами).
Зауважимо, що у разі
мультіссилочного ланки по деяких напрямках ми можемо мати двонаправлену
зв'язок між ланками, а за деякими - однонапрвленную.
2.3. Представлення графів
При поданні графів можна використовувати кілька підходів:
- використовувати ланки
тільки для представлення вершин, а дуги відображати через покажчики; недоліком
тут є те, що ніде відобразити інформацію, наприклад, про вагу дуги, а
так само - у разі неорієнтованого графа одній дузі буде відповідати два
покажчика.
- використовувати ланки для
дуг, а вершини відображати як посилання між дугами інцідентнимі однієї і тієї ж
вершині; в цьому підході утруднене подання орінетірованних дуг, а так само
інфомація про вершини;
- нарешті можна ввести дві
виду ланок один для представлення дуг, інший для подання вершин;
ланки-дуги погоджуються в список, ланки-вершини також погоджуються в список з
перехресними посиланнями між списками.
Особливий випадок представляють
нерегулярні графи, тобто графи у яких ступінь вершин - величина змінна.
У цьому випадку використовуються спеціальні службові ланки з двох
полів-покажчиків. Одне поле служить для посилання на двругое аналогічне ланка, а
друге поле - для посилання на соотвествующий елемент структури.
2.4. Уявлення стека і черги
Стек представляється
однонапрвленним списком з ланок, що складаються з двох полів: тіла та посилання.
Нижче наводяться процедури, що реалізують операції в завантаження і вивантаження з стека.
type
ланка = record тіло: char; наступний: зв'язок end;
зв'язок = Iзвено;
var тіло: char;
стек: зв'язок;
procedure завантажити (тіло: char; var стек: зв'язок);
var елемент: зв'язок;
begin new (елемент); елементI.тело: = тіло; елементI.следующій: = стек;
стек: = елемент
end (завантажити)
procedure вивантажити (var тіло: char; var стек: зв'язок);
var спожитий: зв'язок;
begin ifnot (стек = nil) then
begin тіло
: = СтекI.тело; спожитий: = стек;
стек: = стекI.следующій;
dispose (використаний) end
else write ( 'стек порожній')
end (завантажити)
Зверніть увагу на значення оператора dispose.
Усі міркування про
поданні черги в списковому пам'яті аналогічні тим, що були приведені в
розділі векторного подання черги. Зауважимо що кільцеву чергу легше
організувати через список. черги.
Структури даних
АСД (абстрактні структури даних) - математична структура, з
допомогою якої ми представляємо прикладні дані програми.
АЛГОРИТМ ------> МОВА ПРОГРАМУВАННЯ
У кожній мові програмування існує своя концепція даних.
Назвемо структури даних конкретного ЯП структурою даних зберігання
(СДХ).
ПРОБЛЕМА: як відобразити АСД алгоритму на СДХ ЯП?
Над "АСД
визначені деякі операції (видалити, замінити елемент і т.д.)
Критерієм вибору СДХ є складність. Слід вибирати як
можна більш прості СДХ.
ЗАВДАННЯ. Дано: АСД і
набір СДХ.
Потрібно: побудувати АСД -----> СДХ так, щоб складність
Пераціму з СДХ (аналогічних операцій з АСД) була мінімальною.
Визначення: стосовно порядку R на множині M називають
безліч пар, які мають такі властивості:
1) рефлексивність: (a, a)
