Відображення АСД на СДХ

Отображение АСД на СДХ.

Наша завдання :

1.Найти відображення АСД -> СДХ;

2.Оценить складність алгоритмів операцій вставки, заміни, пошуку миру і видалення що за різних засобах отображениях.

1. Відображення на вектор.

Будемо припускати що ми маємо працювати з неотсортированными структурами. Докладно що означає умова сортированности ми розглянемо розділ IV «Сортування. «.

1.1. Строка

Відображення рядки на вектор будується так:

1. Візьмемо антитранзитиное ставлення R «таке що його транзитивное замикання дає R (на те дуже розглянути ставлення лінійного порядку R без умови 2 — умови транзитивності :

якщо (a, b) і (b, з) належать R, то (a, з) теж належить R;

Ясно що R «задає ставлення сусідства, тобто. (a, b) принадл. R «як і лише если.

Не істот. з: з принадл. 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² /4 чи N² на великих N.

Проте за оперции видалення потрібно зрушувати все елементи, як у випадку з рядком. Проте, операція вставки трубет зміни розмірності матриці суміжності в кожному виміру з N на N+1. І тому доведеться виконати (N+1) операцій присвоювання, для заповнення нову рядок в векторі, плюс N+1 зрушень рядків, щоб додати кожної старої рядку у новій елементу, відповідному N+1 стовпцю. Кількість операцій зсуву визначається наступним соотношением:

.

Таким чином складність операції вставки буде равна.

N²/4 + N³/2 = N²(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². Звідси, при умови равновстречаемости елементів в дереві, потрібно переглянути загалом половину шляхів (їх кількість одно чмслу листя в дереві) довжини 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) Î R {a £ a}.

2) транзитивность: a £ b, b £ з Þ a £ c.

3) антисимметричность: a £ b, b £ a Þ a = b.

якщо ставлення не має здатність 3), то R — предпорядок Отношение суворого порядку, тоді як п. 3) (a, b) Î R Þ (b, a) Ï R.

R — лінійний порядок, якщо R визначено для «a і b і R є суворим порядком.

Некоторое безліч частково упорядковано, якби ньому зафіксовано певний порядок, тобто. на безлічі існують незрівнянні величины.

Структура G на безлічі M — пара (R, M), де R ставлення порядку на безлічі M.

Примеры: безліч натуральних чисел — структура,.

безліч слів — структура Индексация I — відображення M на відрізок [ 1.½M1/2].

Абстрактные структури данных

Рядок Граф Дерево Стік Черга Таблица.

Строка

Строка — кінцеве безліч символів зі ставленням лінійного порядку. Отже кожному за символу знаємо попередній і подальший символы.

Примеры рядків: текст, формули без індексів і др.

Свойства рядків:

— змінна длина,.

— звернення до елементам рядки іде у відповідність до ставленням лінійного порядку, а чи не в відповідність до індексацією у цьому безлічі.

(L, M) I: M Þ [1.ôMô].

— часто рядок має додаткову структуру — синтаксис.

Операции:

— пошук символа,.

— вставка символа,.

— видалення символа,.

— заміна символа.

Граф

Графом гама називаються пари (X, U), де X — безліч, Uставлення порядку на X (X — частково упорядкований множество).

Если U — просто порядок, то граф — орієнтований, з властивості антисимметричности.

Если U — предпорядок, то граф неориентированный.

Пару (a, b) з'єднують дугою, якщо пара (a, b) Î безлічі U.

.

Граф гама називається взвешанным, якщо кожної дузі ми зіставляємо деяке речовинне число, зване вагою даної дуги.

m: UÞR.

Граф гама — розмічений, якщо поставлено деяке відображення.

h: X Þ A, де A — безліч меток.

.

ПРИМЕРЫ: 1) мережу доріг (вагу — відстань, мітка — назва населеного пункту). Знайти найкоротшого шляху з п. A в п.B.

2) Знайти електричні характеристики у різних ділянках електричної цепи.

Способы завдання графа:

— графический,.

— застосування матриці смежности.

½×½ = n; X… X.

.

X.

ì 1, (X, X) Î U.

P.S = í.

î 0, (X, X) Ï U.

— застосування матриці инцедентности.

U…U (дуги).

X.

.

X.

(Вершины).

ì 1, якщо X инцендентно U і Xявляется кінцем дуги U.

p.s = í -1, якщо X инцендентно U і Xявляется початком дуги U.

î 0, у протилежному случае.

Степень вершини — число дуг вхідних (у і виходять (з) даної вершини (инцендентных даної вершине).

Степень заходу (результату) — число дуг вхідних (виходять) в (з) цю вершину.

Граф називається регулярним, якщо ступінь його вершин постоянна.

Последовательность вершин графа X… Xназывается ланцюгом, для.

" (X, X) Î U, тобто. існують дуги якими можна вийти з X до X, від X до X і т.д.

Последовательность вершин графа називається шляхом, якщо для.

" (X, X) Î U чи (X, X) Î U.

Всякая ланцюг — шлях, але кожен шлях — цепь.

Если у ланцюги X=X, така ланцюг називається цикл.

Граф називається слабосвязанным, якщо для «його двох вершин існує шлях їх який би з'єднав, без щодо їх ориентации.

Граф називається сильносвязанным, для «його двох вершин існує шлях їх який би з'єднав, з урахуванням їхньої ориентации.

Вес шляху X … X — сума терезів дуг цього пути.

m (X … X) =m (x, x).

Операции:

— вставити вершину,.

— видалити вершину,.

— вставити дугу,.

— видалити дугу і т.д.

С погляду графа рядок це цепь.

Дерево

Дерево — зв’язний ациклический граф.

Одна вершина в дереві обов’язково має ступінь заходу 0. Ця вершина — корінь дерева. Листя дерева — вершини, мають ступінь результату рівну 0.

Для будь-який вершини дерева (крім кореня) ступінь заходу дорівнює 1.

.

Деревья може бути орієнтовані і неориентированные.

Высота дерева (H) — найдовший шлях з кореня до листу.

Рекурсивное визначення: Безліч з однієї вершини — дерево.

Если T … T — дерева, то.

.

Дерево називається k-ичным, коли всі вершини мають ступінь результату k.

Дерево називається лінійним, ступінь результату дорівнює 1.

ЗАДАЧА. Підрахувати кількість дерев, мають n вершин.

РЕШЕНИЕ. B — число дерев з і вершин. Дотримуючись рекурсивному визначенню дерева:

Þ.

.

Дерево досконале, якщо будь-який шлях від кореня до аркушу відрізняється лише на 1 від самої довгого пути.

Совершенное дерево з n вершин має мінімальну высоту.

Свойства скоєних деревьев:

— становлять мінімальну частина всіх деревьев,.

— всі дороги від кореня до аркушу равноправны.

Список литературы

Для підготовки даної праці були використані матеріали із російського сайту internet.