Datastructures
Эта библиотека предоставляет реализации классических алгоритмов и данных данных.
Организация
Проект разделен на два пакета, алгоритмы и структуру. Пакет алгоритмов содержит реализации в основном автономных алгоритмов, в то время как структура содержит структуры данных и алгоритмы, которые работают исключительно на них.
Алгоритмы
Вот список алгоритмов в пакете алгоритмов:
В BinarySearch.py:
- Стандартный бинарный поиск: стандартный бинарный поиск. https://en.wikipedia.org/wiki/binary_search_algorithm
- Сначала бинарный поиск: стандартный двоичный поиск, за исключением того, что он находит первый элемент, который соответствует клавишу поиска.
В выражении.py:
Алгоритм шунтирующего двора: алгоритм Дейкстры для преобразования инфикс в постфикс. https://en.wikipedia.org/wiki/shunting-yard_algorithm
Два стека алгоритма Dijkstra: алгоритм Dijkstra для интерпретации выражений Postfix.
В проблемах older.py:
- Алгоритм*: алгоритм поиска пути. https://en.wikipedia.org/wiki/a*_search_algorithm
- Алгоритм* адаптирован к проблеме 8-й пузырь: https://www.cs.princeton.edu/courses/archive/spr10/cos226/assignments/8puzzle.html
In sort.py:
- Сортировка выбора: https://en.wikipedia.org/wiki/selection_sort
- Вставка сортировки: https://en.wikipedia.org/wiki/insertion_sort
- Shell Sort: https://en.wikipedia.org/wiki/shellsort
- Вариации слияния сортировки: https://en.wikipedia.org/wiki/merge_sort
- Подсчет инверсии: подсчитайте количество инверсий с модифицированной сортировкой слияния
- Варианты быстрого сортировки: включая стандартное быстрое сортирование, 3-градусную быструю сортировку и быстрое сортирование. https://en.wikipedia.org/wiki/quicksort
- Сорта кучи: https://en.wikipedia.org/wiki/Heapsort
- Выберите KTH: выберите элемент KTH в порядке. На основании быстрого раздела.
Структура
Вот список реализованных структур данных и алгоритмов, которые работают на них:
В linkedlist.py:
- Связанный список: https://en.wikipedia.org/wiki/linked_list
- Связанный стек: стек реализован с помощью связанного списка.
- Связанная очередь: очередь, реализованная в связанном списке.
В UnionFind.py: https://en.wikipedia.org/wiki/disjoint-set_data_structure
- Быстрое находки: Discoint Set, реализованный с помощью массива, такой как структура данных. O (1) Найти.
- Quick Union: Discoint Set, реализованный с родительским деревом ссылок.
- Сбалансированный Quick Union: Desoyoint Set, реализованный с помощью родительского дерева ссылок и уравновешивания на Union. O (log (n)) эффективность для поиска и союза.
- Сжатие пути быстрое союз: непересекающийся набор, реализованный с помощью родительского дерева связей и дополнен сжатием пути.
- Сбалансированное сжатие пути быстрое союз: непересекающийся набор, реализованный с деревом родительских связей с балансировкой и сжатием пути. Почти амортизированная эффективность O (1) на поиске и союзе.
В symboltable.py:
- Дерево бинарного поиска: стандартный BST. https://en.wikipedia.org/wiki/binary_search_tree
- Красное и черное дерево: сбалансированное BST с использованием 2-3 представления. https://en.wikipedia.org/wiki/red%E2%80%93black_tree
- Отдельная таблица хеш -хеш -цепочки: хэш -таблица, которая разрешает столкновение, цепляя их в списке. https://en.wikipedia.org/wiki/hash_table#separate_chaining
- Таблица с открытым адресом: хэш -таблица, которая разрешает столкновение с линейным зондированием. https://en.wikipedia.org/wiki/hash_table#open_addressing
В Heap.py:
- Двоичная куча: реализация очереди приоритетной кучи с бинарной кучей. https://en.wikipedia.org/wiki/binary_heap
В graph.py:
- Недоставленный график: https://en.wikipedia.org/wiki/graph_(discrete_mathematics)#undirected_graph
- Направленный график: https://en.wikipedia.org/wiki/graph_(discrete_mathematics)#directed_graph
- Недовой взвешенный график: https://en.wikipedia.org/wiki/graph_(discrete_mathematics)#weighted_graph
- Направленный взвешенный график: https://en.wikipedia.org/wiki/graph_(discrete_mathematics)#weighted_graph
- Глубина первый поиск: https://en.wikipedia.org/wiki/depth-first_search
- Ширория первого поиска: https://en.wikipedia.org/wiki/breadth-first_search
- Недопроизводные подключенные компоненты: https://en.wikipedia.org/wiki/component_(graph_theory)
- Недостороннее обнаружение цикла: https://en.wikipedia.org/wiki/cycle_(graph_theory)
- Направленное обнаружение цикла: https://en.wikipedia.org/wiki/cycle_(graph_theory)
- Обнаружение двухпарта: https://en.wikipedia.org/wiki/bipartite_graph
- Топологическое упорядочение: https://en.wikipedia.org/wiki/topological_sorting
- Сильно связанные компоненты (алгоритм Косараджу): https://en.wikipedia.org/wiki/kosaraju%27s_algorithm
- Алгоритм Прим (ленивый): https://en.wikipedia.org/wiki/prim%27s_algorithm
- Алгоритм Крускала: https://en.wikipedia.org/wiki/kruskal%27s_algorithm
- Самый короткий путь Дейкстры: https://en.wikipedia.org/wiki/dijkstra%27s_algorithm
- Топологический ациклический кратчайший путь: https://en.wikipedia.org/wiki/topological_sorting#application_to_shortest_path_finding
- Bellman Ford Short Path: https://en.wikipedia.org/wiki/bellman%E2%80%93Ford_algorithm
Использование
Все компоненты протестированы. Тем не менее, они не испытываются в строгих стандартах производства. Структуры данных, такие как связанный список и символические, имеют интерфейсы, такие как стандартный список Python и словарь.
