Реализация бинарных деревьев на Си - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Реализация бинарных деревьев на Си, слайд №1

Реализация бинарных деревьев на Си, слайд №2

Реализация бинарных деревьев на Си, слайд №3

Реализация бинарных деревьев на Си, слайд №4

Реализация бинарных деревьев на Си, слайд №5

Реализация бинарных деревьев на Си, слайд №6

Реализация бинарных деревьев на Си, слайд №7

Реализация бинарных деревьев на Си, слайд №8

Реализация бинарных деревьев на Си, слайд №9

Реализация бинарных деревьев на Си, слайд №10

Реализация бинарных деревьев на Си, слайд №11

Реализация бинарных деревьев на Си, слайд №12

Реализация бинарных деревьев на Си, слайд №13

Реализация бинарных деревьев на Си, слайд №14

Реализация бинарных деревьев на Си, слайд №15

Реализация бинарных деревьев на Си, слайд №16

Реализация бинарных деревьев на Си, слайд №17

Реализация бинарных деревьев на Си, слайд №18

Реализация бинарных деревьев на Си, слайд №19

Реализация бинарных деревьев на Си, слайд №20

Реализация бинарных деревьев на Си, слайд №21

Реализация бинарных деревьев на Си, слайд №22

Реализация бинарных деревьев на Си, слайд №23

Реализация бинарных деревьев на Си, слайд №24

Реализация бинарных деревьев на Си, слайд №25

Реализация бинарных деревьев на Си, слайд №26

Реализация бинарных деревьев на Си, слайд №27

Реализация бинарных деревьев на Си, слайд №28

Реализация бинарных деревьев на Си, слайд №29

Реализация бинарных деревьев на Си, слайд №30

Реализация бинарных деревьев на Си, слайд №31

Реализация бинарных деревьев на Си, слайд №32

Реализация бинарных деревьев на Си, слайд №33

Реализация бинарных деревьев на Си, слайд №34

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Реализация бинарных деревьев на Си. Доклад-сообщение содержит 34 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

ПРОГРАММИРОВАНИЕ Семинар 12. Деревья, графы

Слайд 2

$Реализация бинарных деревьев на Си typedef struct node { char *word; struct node *left; struct node * right; } tree; void print_tree(tree *t) { if...$

Описание слайда:

Реализация бинарных деревьев на Си typedef struct node { char *word; struct node *left; struct node * right; } tree; void print_tree(tree *t) { if (!t) return; print_tree(t -> left); printf("%s\n", t -> word); print_tree(t -> right); }

Слайд 3

Описание слайда:

Сбалансированные деревья Дерево называется сбалансированным, если высоты двух поддеревьев каждой из его вершин отличаются не более, чем на единицу. АВЛ-дерево — сбалансированное двоичное дерево поиска. (Адельсон-Вельский, Ландис, 1962 г.)

Слайд 4

Описание слайда:

Теорема Среднее число сравнений, необходимых для вставки n случайных элементов в дерево двоичного поиска, пустое в начале, равно O(n log2 n) для n ≥ 1. Максимальное число сравнений — O(n2).

Слайд 5

Описание слайда:

Вставка элемента в сбалансированное дерево 1. hL = hR 2. hL < hR 3. hL > hR

Слайд 6

Описание слайда:

Вставка в левое поддерево

Слайд 7

Описание слайда:

Вставка в правое поддерево

Слайд 8

Описание слайда:

Представление графов

Слайд 9

Описание слайда:

Матрица смежностей 1 2 3 4

Слайд 10

Описание слайда:

Матрица инцидентностей 1 2 3 4 5 6 7

Слайд 11

Описание слайда:

Списки смежностей 1

Слайд 12

Описание слайда:

Частичный порядок Определение?

Слайд 13

Описание слайда:

Частичный порядок Отношение R на множестве A: ∀a∈ A ¬aRa; ∀a, b, c∈ A aRb & bRc⇒ aRc. Следствие: ∀a, b∈ A aRb⇒ ¬bRa.

Слайд 14

Описание слайда:

Частичный порядок: примеры решение большой задачи разбивается на ряд подзадач; последовательность чтения тем в учебном курсе; выполнение работ: одну следует выполнить раньше другой; и т. п.

Слайд 15

Описание слайда:

Пример

Слайд 16

Описание слайда:

Линейный порядок Определение?

Слайд 17

Описание слайда:

Линейный порядок ∀a, b∈ A aRb либо bRa либо a = b.

Слайд 18

Описание слайда:

Пример

Слайд 19

Описание слайда:

Алгоритм топологической сортировки Вход: частичный порядок R на конечном множестве A = {a1, a2, …, an}. Выход: линейный порядок R' на A: R⊆ R'. Метод: представить R' в виде списка Ln = a1, a2, …, an, для которого aiR'aj при i < j. Шаг 1: положить i = 1, A1 = A, R1 = R. Шаг 2: если Ai пусто, то остановиться и выдать Li = a1, a2, …, ai в качестве R'. Иначе выбрать в Ai такой ai + 1, что ∀a'∈ A ¬a'Rai + 1. Шаг 3: положить Ai + 1 = Ai \ {ai + 1}, Ri + 1 = Ri \ ({ai + 1}× Ai + 1), i++, на шаг 2.

Слайд 20

Описание слайда:

Алгоритм топологической сортировки Реализация на матрице смежности: 1. Найти вершину, в которую не входит ни одна дуга (нулевой столбец). 2. Удалить все исходящие из неё дуги (обнулить соответствующую строку). 3. Пока не перебрали все вершины, повторять сначала.

Слайд 21

Описание слайда:

Пути в графах

Слайд 22

Описание слайда:

Определения Пусть G = (V, E) — ориентированный граф. Поставим в соответствие каждой дуге e∈ E в графе G неотрицательную стоимость c(e). c: E→ R+ — функция стоимости. Стоимость пути определяется как сумма стоимостей образующих его дуг. Задача о нахождении кратчайшего пути состоит в нахождении для каждой пары узлов (v, w) пути наименьшей стоимости.

Слайд 23

Описание слайда:

Нахождение кратчайшего пути из одного источника Идея: строится множество S, содержащее вершины графа, кратчайшие расстояния до которых от источника известны. На каждом шаге добавляется тот из оставшихся узлов, кратчайшее расстояние до которого меньше всех других оставшихся узлов (т. н. "жадный" алгоритм).

Слайд 24

Описание слайда:

Алгоритм Дейкстры Вход: ориентированный граф G = (V, E), источник v0∈ V, функция стоимости c: E→ R+. Полагаем, что c(vi, vj) = +∞, если (vi, vj)∉ E; c(v, v) = 0. Выход: для всех вершин v∈ V наименьшая сумма стоимостей дуг из E, взятая по всем путям, идущим из v0 в v.

Слайд 25

Описание слайда:

Алгоритм Дейкстры Метод: строим такое множество S⊆ V, что кратчайший путь из источника в каждый узел v∈ S целиком лежит в S. Массив D[v] содержит стоимость текущего кратчайшего пути из v0 в v.

Слайд 26

$Алгоритм Дейкстры { S = {v0}; D[v0] = 0; для всех v∈ V \ {v0} выполнить: D[v] = c(v0, v); пока S ≠ V выполнять: { выбрать узел w∈ V \ S, для которого...$

Описание слайда:

Алгоритм Дейкстры { S = {v0}; D[v0] = 0; для всех v∈ V \ {v0} выполнить: D[v] = c(v0, v); пока S ≠ V выполнять: { выбрать узел w∈ V \ S, для которого D[w] принимает наименьшее значение; S = S∪ {w}; для всех v∈ V \ S выполнить D[v] = min(D[v], D[w] + c(w, v)); } }

Слайд 27

Описание слайда:

Пример

Слайд 28

Описание слайда:

Нахождение кратчайших путей между всеми парами вершин Строим матрицу стоимостей: c(i, j), если дуга (i, j)∈ E; M[i, j] = +∞ , если дуга (i, j)∉ E; 0, если i = j. Обозначим через d[i, j] матрицу кратчайших путей между всеми вершинами. Вершины занумеруем числами от 1 до n.

Слайд 29

Описание слайда:

Алгоритм Флойда-Уоршелла Обозначим через dij(k) стоимость кратчайшего пути из вершины с номером i в вершину с номером j с промежуточными вершинами из множества {1, 2, …, k}. M[i, j], если k = 0, dij(k) = min(dij(k - 1), dik(k - 1) + dkj(k - 1)), если k ≥ 1. D(n) содержит искомое решение.

Слайд 30

Описание слайда:

Алгоритм Флойда-Уоршелла Floyd-Warshall(M, n) { D(0) = M; for k = 1 to n do for i = 1 to n do for j = 1 to n do dij(k) = min(dij(k - 1), dik(k - 1) + dkj(k - 1)); return D(n); }

Слайд 31

Описание слайда:

Транзитивное замыкание графа Транзитивное замыкание орграфа G = (V, E) — орграф G' = (V, E'), в котором (v, w)∈ E' ⇔ существует путь (длины 0 или больше) из v в w в G.

Слайд 32

Описание слайда:

Пример

Слайд 33

Описание слайда:

Построение транзитивного замыкания графа Обозначим через tij(k) наличие пути из вершины с номером i в вершину с номером j с промежуточными вершинами из множества {1, 2, …, k}. M — матрица смежностей G. M[i, j], если k = 0, tij(k) = tij(k - 1)∨ (tik(k - 1) & tkj(k - 1)), если k ≥ 1. T(n) содержит искомое решение.

Слайд 34

$Построение транзитивного замыкания графа Transitive_Closure(M, n) { T(0) = M; for k = 1 to n do for i = 1 to n do for j = 1 to n do tij(k) = tij(k -...$

Описание слайда:

Построение транзитивного замыкания графа Transitive_Closure(M, n) { T(0) = M; for k = 1 to n do for i = 1 to n do for j = 1 to n do tij(k) = tij(k - 1)∨ (tik(k - 1) & tkj(k - 1)); return T(n); }