🗊Презентация Реализация бинарных деревьев на Си

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Реализация бинарных деревьев на Си, слайд №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. Деревья, графы
Описание слайда:
ПРОГРАММИРОВАНИЕ Семинар 12. Деревья, графы

Слайд 2


Реализация бинарных деревьев на Си 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); }
Описание слайда:
Реализация бинарных деревьев на Си 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 г.)
Описание слайда:
Сбалансированные деревья Дерево называется сбалансированным, если высоты двух поддеревьев каждой из его вершин отличаются не более, чем на единицу. АВЛ-дерево — сбалансированное двоичное дерево поиска. (Адельсон-Вельский, Ландис, 1962 г.)

Слайд 4


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

Слайд 5


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

Слайд 6


Вставка в левое поддерево
Описание слайда:
Вставка в левое поддерево

Слайд 7


Вставка в правое поддерево
Описание слайда:
Вставка в правое поддерево

Слайд 8


Представление графов
Описание слайда:
Представление графов

Слайд 9


Матрица смежностей 1 2 3 4
Описание слайда:
Матрица смежностей 1 2 3 4

Слайд 10


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

Слайд 11


Списки смежностей 1
Описание слайда:
Списки смежностей 1

Слайд 12


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

Слайд 13


Частичный порядок Отношение R на множестве A: ∀a∈ A ¬aRa; ∀a, b, c∈ A aRb & bRc⇒ aRc. Следствие: ∀a, b∈ A aRb⇒ ¬bRa.
Описание слайда:
Частичный порядок Отношение 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.
Описание слайда:
Линейный порядок ∀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.
Описание слайда:
Алгоритм топологической сортировки Вход: частичный порядок 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. Пока не перебрали все вершины, повторять сначала.
Описание слайда:
Алгоритм топологической сортировки Реализация на матрице смежности: 1. Найти вершину, в которую не входит ни одна дуга (нулевой столбец). 2. Удалить все исходящие из неё дуги (обнулить соответствующую строку). 3. Пока не перебрали все вершины, повторять сначала.

Слайд 21


Пути в графах
Описание слайда:
Пути в графах

Слайд 22


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

Слайд 23


Нахождение кратчайшего пути из одного источника Идея: строится множество S, содержащее вершины графа, кратчайшие расстояния до которых от источника известны. На каждом шаге добавляется тот из оставшихся узлов, кратчайшее расстояние до которого меньше всех других оставшихся узлов (т. н. "жадный" алгоритм).
Описание слайда:
Нахождение кратчайшего пути из одного источника Идея: строится множество 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.
Описание слайда:
Алгоритм Дейкстры Вход: ориентированный граф 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.
Описание слайда:
Алгоритм Дейкстры Метод: строим такое множество 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, для которого D[w] принимает наименьшее значение; S = S∪ {w}; для всех v∈ V \ S выполнить D[v] = min(D[v], D[w] + c(w, v)); } }
Описание слайда:
Алгоритм Дейкстры { 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.
Описание слайда:
Нахождение кратчайших путей между всеми парами вершин Строим матрицу стоимостей: 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) содержит искомое решение.
Описание слайда:
Алгоритм Флойда-Уоршелла Обозначим через 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); }
Описание слайда:
Алгоритм Флойда-Уоршелла 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.
Описание слайда:
Транзитивное замыкание графа Транзитивное замыкание орграфа 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) содержит искомое решение.
Описание слайда:
Построение транзитивного замыкания графа Обозначим через 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 - 1)∨ (tik(k - 1) & tkj(k - 1)); return T(n); }
Описание слайда:
Построение транзитивного замыкания графа 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); }

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию