データストラクチャ
このライブラリは、古典的なアルゴリズムとデータストラクチャの実装を提供します。
組織
このプロジェクトは、アルゴリズムと構造の2つのパッケージに分かれています。アルゴリズムパッケージには、ほとんどスタンドアロンアルゴリズムの実装が含まれていますが、構造パッケージにはそれらを独占的に動作するデータ構造とアルゴリズムが含まれています。
アルゴリズム
アルゴリズムパッケージの下にあるアルゴリズムのリストは次のとおりです。
binarysearch.py：
- 標準バイナリ検索：標準バイナリ検索。 https://en.wikipedia.org/wiki/binary_search_algorithm
- 最初の発生バイナリ検索：検索キーに一致する最初の要素を見つけることを除いて、標準バイナリ検索。
In Expression.py：
infollenceolver.py：
- *アルゴリズム：パス検索アルゴリズム。 https://en.wikipedia.org/wiki/a*_search_algorithm
- 8パズルの問題に適合した*アルゴリズム：https：//www.cs.princeton.edu/courses/archive/spr10/cos226/assignments/8puzzle.html
sort.py：
- 選択ソート：https：//en.wikipedia.org/wiki/selection_sort
- 挿入ソート：https：//en.wikipedia.org/wiki/insertion_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
- リンクスタック：リンクリストで実装されたスタック。
- リンクされたキュー：リンクリストで実装されたキュー。
in unionfind.py：https：//en.wikipedia.org/wiki/disjoint-set_data_structure
- クイック検索：データ構造のような配列で実装されたDijoint Set。 o（1）検索。
- クイックユニオン：親リンクツリーで実装されたDijoint Set。
- バランスの取れたクイックユニオン：親リンクツリーとユニオンでのバランスをとることで実装された分離セット。 O（log（n））発見と結合の効率。
- パス圧縮クイックユニオン：親リンクツリーで実装され、パス圧縮で拡張された分離セット。
- バランスパス圧縮クイックユニオン：バランスとパス圧縮を備えた親リンクツリーで実装された分離セット。ほぼ償却されたO（1）発見と結合の効率。
in symboltable.py：
- バイナリ検索ツリー：標準BST。 https://en.wikipedia.org/wiki/binary_search_tree
- 赤と黒の木：2-3表現を使用したバランスの取れたBST。 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）#undired_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）
- Biparte検出：https：//en.wikipedia.org/wiki/bipartite_graph
- トポロジー順序：https：//en.wikipedia.org/wiki/topological_sorting
- 強く接続されたコンポーネント（Kosarajuのアルゴリズム）：https：//en.wikipedia.org/wiki/kosaraju%27s_algorithm
- Prim's Algorithm（Lazy）：https：//en.wikipedia.org/wiki/prim%27s_algorithm
- Kruskalのアルゴリズム：https：//en.wikipedia.org/wiki/kruskal%27S_algorithm
- Dijkstraの最短経路：https：//en.wikipedia.org/wiki/dijkstra%27s_algorithm
- トポロジー的な環状最短経路：https：//en.wikipedia.org/wiki/topological_sorting#application_to_shortest_path_finding
- ベルマンフォード最短パス：https：//en.wikipedia.org/wiki/bellman%e2%80%93ford_algorithm
使用法
すべてのコンポーネントがテストされています。ただし、厳格な生産基準にはテストされていません。リンクリストやシンボルテーブルなどのデータ構造には、標準のPythonリストや辞書などのインターフェイスがあります。
