Как выбрать структуру данных

Если вы наперёд не знаете количество элементов, которые вы должны будете принять например, посредством ввода данных пользователем, то используйте связный список (linked list).

Если нужно обработать много элементов, среди которых некоторые важнее других то используйте очередь с приоритетом (priority queue). Например, сетевой трафик имеет разный приоритет. Некоторые данные важнее, например, голосовые коммуникации в режиме реального времени требуют более высокого уровня QoS чем резервное копирование данных в фоновом режиме. Если ваш компьютер посылает пакеты для VoIP телефоного соединения и в тоже время загружает ваши фотки с отпуска на Facebook, то вы естественно захотите чтобы в первую очередь передавался голос, потому что он более time-sensitive.

Если вам нужно брать данные с накопителя у которого медленный доступ, например стримера или диска, то нужно использовать B-tree. Древовидная иерархия позволяет хранить данные таким способом, что можно эффективно искать нужные данные загружая только необходимые для этого части дерева с накопителя в оперативную память.

Бинарные кучи (пирамиды)

Лекция 7: Бинарные кучи (пирамиды) from Mikhail Kurnosov

d-кучи и их применение

D-кучи и их применение from DEVTYPE

С++11/14 в STL

Бинарные деревья

Бинарное дерево представляет собой структуру, в которой каждый узел (или вершина) имеет не более двух узлов-потомков и в точности одного родителя. Самый верхний узел дерева является единственным узлом без родителей; он называется корневым узлом, или корнем.

Бинарное дерево с N узлами имеет не меньше ⌊log₂N + 1⌋ уровней (при максимально плотной упаковке узлов). 

Например, у полного бинарного дерева с 15 узлами один корень, два узла на втором уровне, четыре узла на третьем уровне и восемь узлов на четвертом уровне; наше равенство также дает ⌊log₂15⌋ + 1 = ⌊3,9⌋ + 1 = 4 уровня.

Заметим, что добавление еще одного узла к дереву приведет к необходимости появления нового уровня, и их число станет равным ⌊log₂16⌋ + 1 = ⌊4⌋ + 1 = 5.

В самом большом бинарном дереве с N узлами N уровней: у каждого узла этого дерева в точности один потомок (и само дерево представляет собой просто список) .

Если уровни дерева занумеровать, считая что корень лежит на уровне 1, то на уровне с номером k лежит не более чем 2^k-1 узла.

У полного бинарного дерева с j уровнями (занумерованными от 1 до j) все листья (узлы без потомков) лежат на уровне с номером j, и у каждого узла на уровнях с первого по j - 1 в точности два непосредственных потомка.

В полном бинарном дереве с j уровнями 2^j - 1 узел. 

Заметки о тестировании программ

Основная идея — не пытаться программировать сразу. Пошаговая детализация автоматически заставляет формировать понятную структуру программы. При этом требуется отслеживать правильность детализации, создавая набор контрольных точек и просчитывая значения данных в них. Выбор представления данных — один из фундаментальных аспектов разработки программы. Н. Вирт так определял критерии этого действия: естественность, структуры данных обязаны «вытекать» из специфики задачи; привычность, структуры данных выбираются так, чтобы программирование приближалось к утверждению «как говорю, так и пишу программу, ничего лишнего»; оптимальность, структуры данных выбираются так, чтобы была возможность построения эффективного алгоритма.

Следует придерживаться правила о том, что любой фрагмент программного кода (логики) должен иметь одну точку входа и одну точку выхода (пусть даже в ущерб эффективности использования памяти).

Временная сложность(t). Обычно на время решения задачи накладываются определенные ограничения. Размерность задачи опишем величиной N. Временная сложность алгоритма является линейной при t~O(N), полиномиальной при t~O(N^q), где q равно обычно 2 или 3, и экспоненциальной при t~O(q^N).

---

OZON.ru - Книги | Программирование в алгоритмах | С. Окулов | Купить книги: интернет-магазин / ISBN 978-5-94774-689-1