WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Структури даних - Реферат

Структури даних - Реферат

приписаний вершині l. Кожна вершина v, яка не є листом, містить два додаткові елементи: L[v] та M[v] найбільший елемент множини даних S у піддереві, коренем якого є відповідно лівий та середній син вершини v.
Вставка в 2 - 3 дерево. Для вставки нового елемента а необхідно знайти місце для нового листа l. Для цього шукають елемент а в дереві. Пошук закінчується у вузлі f, який має двох чи трьох синів що є листами.
Якщо з вузла f виходить лише два вузла l1 та l2, то l стає сином f. Якщо a < E[l1], то l стає самим лівим сином вузла f і покладаємо L[f] = a, M[f] = E[l1]. Якщо E[l1] < a < E[l2], то l стає середнім сином вузла f і покладаємо M[f] = a. Якщо E[l2] < a, то l стає третім сином вузла f. В останньому випадку може виникнути необхідність змінити значення L та M на деяких предках вузла f.
Нехай вузел вже має три листа l1, l2 та l3. L робимо відповідним сином вузла f, після чого f має чотирьох синів. Для збереження 2 - 3 властивості утворимо новий вузел g. Два лівих сина залишаємо синами вузла f, а два правих робимо синами g. Потім робимо g братом f, зробивши його сином батька f. Якщо батько вузла мав двох синів, то зупиняємося. Якщо трьох, то рекурсивно повторюємо вказану процедуру до тих пір, поки в дереві не залишиться більше трьох синів. Якщо корінь матиме чотири сина, утворимо новий корінь з двома новими синами, кожний з яких буде мати в якості двох своїх синів двох із чотирьох синів старого кореня.
Формула Ейлера. Позначимо через V, E, F кількість вершин, ребер та граней планарного графу G (включаючи необмежену область). Тоді справедлива формула:
V - E + F = 2
Малюнок Х. Граф. V = 4, E = 6, F = 4: V - E + F = 4 - 6 + 4 = 2
Якщо граф G незв'язний, а С - кількість компонент зв'язності, то має місце формула:
V - E + F - C = 1
Теорема. Планарний граф з V вершинами має не більше 3(V - 2) ребер та не більше 2(V - 2) граней.
Доведення. Припустимо, що граф не має подвійних ребер та циклів. Побудуємо триангуояцію графу.
Реберний список з подвійними зв'язками (РСПЗ) використовується для представлення планарного графа. Плоске укладання планарного графа - це відображення кожної вершини у точку на площині, а кожного ребра - в просту лінію, яка сполучає пару образів кінцевих вершин цього ребра так, щоб образи ребер перетиналися лише у своїх кінцевих точках.
Головною компонентою РСПЗ для планарного графа (V, E) є реберний вузел. Між ребрами та реберними вузлами існує взаємно однозначна відповідність. Реберний вузел містить чотири інформаційні поля (V1, V2, F1, F2) та два поля вказівників (P1, P2). Поле V1 містить початок ребра, а поле V2 містить його кінець (ребро таким чином має орієнтацію). Поля F1 та F2 містять імена граней. Вказівник P1 (відповідно P2) задає реберний вузел, який містить перше ребро, що зустрічається за ребром (V1, V2) при повороті від нього проти годинникової стрілки навколо V1 (відповідно V2). Імена граней та вершин задаються цілими числами.
V1 V2 F1 F2 P1 P2
a1 1 2 5 1 5 3
a2 2 3 5 4 1 10
a3 2 4 4 1 2 8
a4 1 5 1 3 1 7
a5 1 6 3 5 4 6
a6 6 7 3 5 5 10
a7 5 7 2 3 8 6
a8 5 4 1 2 4 9
a9 4 7 4 2 3 7
a10 3 7 5 4 2 9
Якщо граф має N вершин та F граней, то введемо два масива HV[1:N] та HF[1:F], які містять номер ребра, що виходить з відповідної вершини (обмежує грань). Процедура Fill заповнює ці масиви переглядаючи V1 та F1 за час O(N).
Fill
for i 1 to N do
begin
if (HV[V1[i]] = 0) then HV[V1[i]] i;
if (HV[V2[i]] = 0) then HV[V2[i]] i;
if (HF[F1[i]] = 0) then HF[F1[i]] i;
if (HF[F2[i]] = 0) then HF[F2[i]] i;
end;
Після виконання процедури Fill для наведеного прикладу масиви HV та HF приймуть наступні значення:
HV = [1,1,2,3,4,5,6];
HF = [1,7,4,2,1].
Процедура vertex ( i ) будує послідовність ребер, інцидентних vi як послідовність адрес, занесених в масив An.
Vertex ( j )
i 1;
a HV[j];
a0 a;
An[i] a;
i i + 1;
if (V1[a] = j) then a P1[a]
else a P2[a];
while (a a0) do
begin
An[i] a; i i + 1;
if (V1[a] = j) then a P1[a]
else a P2[a];
end;
Час роботи процедури Vertex ( j ) пропоційна числу ребер, інцидентних vj. Аналогічно можна створити процедуру Facet ( j ), за допомогою якої можна отримати послідовність ребер, які обмежують грань fj, замінивши в попередній процедурі HV та V1 на HF та F1.
Процедури Vertex ( j ) перелічує ребра в порядку обхода навколо вершини проти годинникової стрілки, а Facet ( j ) перелічує їх в порядку обхода за годинниковою стрілкою навколо грані.
Хеш таблиці. Нехай дано n елементів, ключами яких є цілі числа в межах від 1 до m, m n. У найпростішому випадку задані n елементів можна зберігати у таблиці T[m] з прямою адресацією: T[i] або порожнє, або містить один елемент. Пошук в такій таблиці відбувається за час O(1). При такому зберіганні даних повинні виконуватись дві умови:
* всі ключі повинні бути унікальними;
* значення ключів повинні знаходитися у певних межах.
Якщо ключі не унікальні, то можна утворити m списків, кожен з який містить елементи з однаковими ключами. Час пошуку елемента із заданим ключем залишається рівним O(1). Але якщо елементи з одного списку мають різні характеристики (незважаючи на спільний ключ), і кількість елементів у списку дорівнює d, то час пошуку такого елемента складатиме O(d).
Система неперитинаючих множин - це набір непорожніх множин, які не перетинаються, в кожній з яких зафіксовано один із елементів (представник). На системі неперетинаючих множин підтримуються наступні операції:
* Make-Set (x). Утворення множини. Процедурі передається вказівник на вже існуючий об'єкт х. Процедура утворює нову множину, єдиний елемент якої задається вказівником х. Оскільки множини не повинні перетинатися, елемент х повинен вказувати на новий об'єкт (який не лежить в жодній із існуючих множин).
* Find-Set (x). Знайти множину. Повертає вказівник на представника (єдиного) множини, який містить елемент, на який вказує х.
* Union (x, y). Об'єднання. Процедура застосовується, якщо елементи x та y містяться у різних множинах Sx та Sy і замінює ці множини на об'єднання Sx Sy; при цьому обирається деякий представник для Sx Sy. Самі множини Sx та Sy при цьому знищуються.
Реалізація системи непертинаючихмножин за допомогою списків. Кожна множина зберігається у вигляді списку. Представником множини вважається перший елемент списку, а кожний елемент містить вказівники на наступний та перший елементи. Для кожного списку зберігаються вказівники на перший та останній (він потрібний для додавання елементів в кінець списку) елементи.
При такій реалізації операції Make-Set утворює список із одного елемента, а Find-Set повертає вказівник на початок списку і обидві вимагають часу O(1). Для виконання операції Union (x, y) необхідно додати список, який містить x, до кінця списку, що містить y. При цьому треба також встановити правильні вказівники на початок списку для усіх бувших елементів множини, що містила х; час вказаної операції лінійно залежить від розміру вказаної множини.
Loading...

 
 

Цікаве