(* Структура данных - способ организации (однотипных) элементов *) (* данных, удобный для решения конкретной задачи. *) (* *) (* Обычно структура данных должна поддерживать след.операции: *) (* -1- включить в структуру новый элемент; *) (* -2- выбрать из структуры элемент (с последующим удалением); *) (* -3- найти в структуре элемент с заданными характеристиками; *) (* +4+ породить (пустую) структуру; *) (* +5+ проверить наличие элементов в структуре. *) (* *) (* Типичные структуры: очереди, стеки, деревья поиска и т.д. *) (* Строительный материал: массивы, ссылки+записи *) Основные понятия |
(* Множество вершин - конечное множество некоторых элементов: *) (* точек плоскости, записей в памяти и т.п. *) |
(* Ориентированное ребро (дуга; ребро) *) (* - упорядоченная пара вершин *) (* *) (* Если (a,b) - ребро, то говорят, что *) (* "ребро (a,b) соединяет вершины a и b", *) (* "ребро (a,b) исходит из вершины a", *) (* "ребро (a,b) входит в вершину b". *) (* *) (* Множество ребер - конечное множество ориентированных ребер. *) |
(* Ориентированный граф - пара множеств: *) (* множество вершин и множество ребер. *) |
(* Пример графа. Мн-во вершин = {a, b, c, d} *)
(* Мн-во ребер = {(a,b), (b,c), (c,d), (d,b)} *)
(* В этом графе: из вершины a исходит 1 ребро (a,b); *)
(* в вершину a не входит ни одно ребро; *)
(* из вершины b исходит 1 ребро (b,c); *)
(* в вершину b входят 2 ребра: (a,b) и (d,b); *)
(* из вершины c исходит 1 ребро (c,d); *)
(* в вершину c входит 1 ребро (b,c); *)
(* из вершины d исходит 1 ребро (d,b); *)
(* в вершину d входит 1 ребро (c,d). *)
(* Конец примера. *)
|
(* Дерево - граф в котором: *) (* -1- существует ровно 1 вершина (корень дерева), *) (* в которую не входит ни одно ребро; *) (* -2- во все остальные вершины *) (* входит ровно одно ребро. *) |
(* Лист дерева - вершина дерева, из которой не исходят ребра. *) (* *) (* Внутренняя вершина дерева - вершина дерева, отличная от *) (* корня и листьев. *) (* *) (* Если (p,q) - вершина дерева, то говорят, что: *) (* "вершина p - непосредственный предок вершины q" и *) (* "вершина q - непосредственный потомок вершины p". *) (* *) (* Листья дерева не имеют непосредственных потомков. *) (* Все вершины (за исключением корня) имеют ровно *) (* одного предка. *) (* *) (* Пусть p - вершина некоторого дерева. *) (* Потомки вершины p - непосредственные потомки p, а также *) (* потомки непосредственных потомков p. *) |
(* Пример дерева. Мн-во вершин = {a, b, c, d, e, f} *)
(* Мн-во ребер = {(b,a), (b,d), (b,f), *)
(* (f,c), (f,e) }. *)
(* Корень: b *)
(* Листья: a, d, c, e *)
(* Внутренняя: f *)
(* Вершина b - непосредственный предок вершин a, d, f. *)
(* Вершина f - непосредственный предок вершин c, e. *)
(* Непосредственные потомки вершины b: a, d, f. *)
(* Непосредственные потомки вершины f: c, e. *)
(* Потомки вершины b: a, d, f, c, e. *)
(* Потомки вершины f: c, e. *)
(* Конец примера. *)
|
(* Если (p,q) - ребро дерева, то *) (* глубина(q) ::= глубина(p)+1, при этом считаем, *) (* что глубина(корень) ::= 0 *) (* *) (* Высота дерева (Глубина дерева) - *) (* максимальная глубина его вершин = *) (* максимальная глубина его листьев. *) |
(* Пусть p - вершина некоторого дерева. *) (* Поддерево с корнем p ::= дерево, *) (* вершинами которого (мн-вом M) являются сама p и ее потомки, *) (* ребрами которого являются все ребра исходного дерева, *) (* соединяющие вершины из M. *) |
(* Пример. Мн-во вершин = {a, b, c, d, e, f, g, h} *)
(* Мн-во ребер = {(a,b), (a,c), (a,d), *)
(* (d,e), (d,f), *)
(* (e,g), (e,h)} *)
(* глубина(a) = 0; *)
(* глубина(b) = 1; глубина(с) = 1; глубина(d) = 1; *)
(* глубина(e) = 2; глубина(f) = 2; *)
(* глубина(g) = 3; глубина(h) = 3; *)
(* Высота дерева = Глубина дерева = 3. *)
(* Поддерево с корнем d. Мн-во вершин = {d, e, f, g, h} *)
(* Мн-во ребер = {(d,e), (d,f), *)
(* (e,g), (e,h)} *)
(* Высота поддерева с корнем d = 2. *)
(* Поддерево с корнем e. Мн-во вершин = {e, g, h} *)
(* Мн-во ребер = {(e,g), (e,h)} *)
(* Высота поддерева с корнем e = 1. *)
(* Конец примера. *)
|
(* Двоичное дерево (Бинарное дерево) - дерево, в котором *) (* каждая вершина имеет 0, 1 или 2 непосредственных потомков. *) (* *) (* Представление деревьев на языке Паскаль >> goto *) |