Структури даних (реферат)

Реферат на тему:

Структури даних

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

Найпоширеними складними об’єктами є множини та послідовності
(впорядковані множини).

Списком називається впорядкована послідовність елементів a1, a2, …,
an. Розмір або довжина цього списку дорівнює n. Список розміру 0
називається порожнім. Список можна реалізувати або за допомогою масиву
або за допомогою зв’язування його елементів вказівниками (зв’язаний
список). У зв’язаному списку елементи лінійно впорядковані, їх порядок
визначається вказівниками, що входять у склад елементів списка. Елемент
двостороннього зв’язаного списка містить три поля: ключ та два
вказівника – наступний та попередній. В односторонньому зв’язаному
списку відсутнє поле ‘попередній’. У впорядкованому списку елементи
розташовані в порядку зростання ключів на відміну від невпорядкованого
списка.

Стеки та черги – це динамічні множини (або спеціальні типи списків), в
яких елемент що додається, визначається структурою множини. Стек працює
за принципом “останній прийшов – перший пішов (LIFO)”, а черга – за
принципом “перший прийшов – перший пішов (FIFO)”.

Нехай PList – вказівник на однозв’язний список.

PList = ^List;

List = object

val: integer; /* значення */

next: PList; /* вказівник на наступний елемент списку */

end;

Стек має наступні методи:

PUSH – покласти елемент до стеку;

POP – взяти верхній елемент зі стеку;

TOP – повернути верхній елемент стеку без його вилучення;

IsEmpty – перевірити, чи є стек порожнім;

PRINT – надрукувати елементи стеку.

Pstack – вказівник на об’єкт стек.

PStack = ^Stack;

Stack = object

lst: PList;

procedure Push (Value: integer);

function Pop :integer;

function Top :integer;

function IsEmpty :boolean;

procedure Print;

end;

procedure Stack.Push (Value:integer);

var temp: PList;

begin

New (temp);

temp^.val := Value;

temp^.next := lst;

lst := temp;

end;

function Stack.Pop: integer;

begin

if (lst = NIL) then Pop := -1 else

begin

Pop := lst^.val;

lst := lst^.next;

end;

function Stack.Top: integer;

begin

Top := lst^.val;

end;

function Stack.IsEmpty: boolean;

begin

if (lst = NIL) then IsEmpty := TRUE

else IsEmpty := FALSE;

end;

procedure Stack.Print;

var tmp: PList;

begin

tmp := lst;

while (tmp NIL) do

begin

write(tmp^.val); write(‘ ‘);

tmp := tmp^.next;

end;

writeln;

end;

Орієнтованим графом називається структура G = (V, E), де V – скінченна
множина вершин, E – множина ребер, що задається як бінарне відношення на
V, тобто E ??V ??V. Орієнтований граф називається орграфом. Граф може
містити ребра – цикли, які сполучають вершину саму з собою. Про ребро
(u, v) говорять, що воно виходить із вершини u та входить у вершину v.

В неорієнтованому графі множина ребер E складається із невпорядкованих
пар вершин. Про ребро (u, v) неорієнтованого графу говорять, що воно
інцидентно вершинам u та v. Якщо в графі G є ребро (u, v), то говорять,
що вершина u суміжна з вершиною v. Для неорієнтованого графу відношення
суміжності є симетричним.

Степенем вершини в неорієнтованому графі називається кількість
інцидентних їй ребер. Для орієнтовних графів розрізняють вхідну та
вихідну вершини; сума вхідних та вихідних степеней називається степенем
вершини.

Деревом називається зв’язаний граф без циклів. Дерево являє собою
скінченну множину елементів Т, які називаються вершинами. Якщо множина
вершин Т порожня, то дерево називається порожнім; інакше в дереві
повинна бути виділена одна вершина, яка називається коренем (якщо
виділеної вершини не існує, то така структура називається деревом без
виділеного кореня). Якщо (y, x) є останнім ребром на шляху з кореня до
х, то y називається батьком, а x – сином. Корінь є єдиною вершиною, яка
не має батька. Вершини, які мають одного спільного батька, називаються
братами. Якщо кожна вершина T (батько) сполучається не більше ніж з k
іншими вершинами T1, T2, …, Tk (синами), то таке дерево називається k
– арним. Якщо вершина не має синів, то вона називається листом; інакше
вершина називається внутрішньою. Кількість синів у вершини дерева
називається її степенем. Глибиною вершини називається довжина шляху від
кореня до цієї вершини. Висотою дерева називається найбільша довжина від
кореня до листа. Повним k – арним деревом називається k – арне дерево, в
якому усі листи мають однакову глибину та усі внутрішні вершини мають
однаковий степінь.

Властивість дерев. Нехай G = (V, E) – неорієнтований граф. Тоді наступні
твердження еквівалентні:

G є деревом без виділеного кореня;

для довільних двох вершин G існує єдиний простий шлях, що їх сполучає;

граф G є зв’язним, але не залишається таким при вилученні хоча б одного
ребра;

граф G є зв’язним і |E| = |V| – 1;

граф G є ациклічним і |E| = |V| – 1;

граф G є ациклічним, але додання довільного ребра породжує цикл.

У двійковому дереві кожна вершина може мати не більше двох синів (лівий
та правий сини). Кожна вершина окрім кореня, має батька. При
представленні двійкового дерева за допомогою вказівників кожна вершина
містить ключ Val, вказівники на лівого Left та правого Right синів, а
також на батька Up. Якщо сина або батька (для кореня) не існує, то
відповідний вказівник містить NIL.

Ключі у двійковому дереві містяться у відповідності до властивості
впорядкованості:

Нехай x – довільна вершина двійкового дерева. Якщо вершина y
знаходиться в лівому піддереві вершини x, то x.Val > y.Val. Якщо
вершина y знаходиться в правому піддереві вершини x, то x.Val Tree^.Val) then

if Tree^.Right = NIL then

begin

New (Tree^.Right);

Tree^.Right^.val := Value;

Tree^.Right^.Left := NIL;

Tree^.Right^.Right := NIL;

Tree^.Right^.Up := Tree;

end

else InsElem (Tree^.Right, Value)

else

if Tree^.Left = NIL then

begin

New (Tree^.Left);

Tree^.Left^.val := Value;

Tree^.Left^.Left := NIL;

Tree^.Left^.Right := NIL;

Tree^.Left^.Up := Tree;

end

else InsElem (Tree^.Left, Value);

end;

procedure TreeStr.Insert (Value:integer);

var Tmp: PTree;

begin

InsElem (TTree, Value);

end;

При видаленні вершини х з бінарного дерева можливі три випадки:

х не має синів – тоді достатньо розташувати NIL у відповідне поле його
батька (замість х);

х має одного сина – тоді його можна вирізати, поєднавши його батька
напряму з цим сином;

х має двох синів – необхідно знайти наступний за х елемент y (який вже
не має лівого сина), скопіювати його ключ та певні дані з вершини y до
вершини x, а саму вершину y видалити вище описаним способом.

procedure DelElem (var Tree: PTree; Value: integer);

var tmp, Repl: PTree;

begin

if (Tree = NIL) then Exit;

if (Value Tree^.Val) then DelElem (Tree^.Right, Value)

else if ((Tree^.Left NIL) and (Tree^.Right NIL)) then

begin

Repl := Fmin (Tree^.Right);

Tree^.Val := Repl^.Val;

DelElem (Tree^.Right, Repl^.Val);

end

else

begin

tmp := Tree;

if (Tree^.Left = NIL)
then???????????††????????????????????????††????????†????????????????????
??????????????????†???????????????

Дерева з довільним розгалудженням можна перетворити у двійкове дерево за
принципом “ліва дитина – правий сусід”. Кожна вершина містить три
вказівники:

вказівник p на батька;

вказівник left-child[x] на саму ліву дитину вершини х;

вказівник right-child[x] на найближчого сусіда вершини х;

Вершина х не має дітей тоді і тільки тоді коли left-child[x] = NIL.
Вершина х є крайньою правою дитиною свого батька якщо right-child[x] =
NIL.

AVL – деревом (Adelson-Velskii and Landis) називається бінарне дерево,
яке має наступні властивості:

висоти піддерев кожного батька відрізняються не більше ніж на 1:

кожне піддерево батька є AVL – деревом.

AVL – дерева належать до класу збалансованих бінарних дерев.

Ліве дерево є AVL – деревом, оскільки у нього висота кожного лівого сина
на 1 більша за висоту відповідного правого сина. Дерево, яке зображене
справа, не є AVL – деревом, оскільки лівий син вершини 12 (дерево з
коренем 8) має висоту 4, а правий син вершини 12 (дерево з коренем 18)
має висоту 2.

Дерево відрізків – це структура даних, яка створена для роботи з такими
інтервалами на числовій осі, кінці яких належать фіксованій множині з N
абсцис (далі цими абсцисами будемо вважати цілі числа в інтервалі [1,
N]). Оскільки множина абсцис фіксована, то дерево відрізків являє собою
статичну структуру по відношенню до цих абсцис.

Дерево відрізків – це двійкове дерево з коренем. Для заданих цілих чисел
l та r (l 1, то воно складається з лівого піддерева
T(l, [(B[v] + E[v])/2]) та правого піддерева T([(B[v] + E[v])/2], r).

Інтервали, що належать множині {[B[v], E[v]]: v – вузел T(l, r)},
називаються стандартними інтервалами дерева T(l, r). Стандартні
інтервали, які належать листам T(l, r), називаються елементарними
інтервалами. T(l, r) збалансоване та має глибину ?log2(r – l)?.

Дерево відрізків призначено для динамічного запам’ятання інтервалів,
кінці яких належать множині {l, l + 1, …, r}. Якщо r – l > 3, то
інтервал [b, e] з цілими b 2