De données
Cette bibliothèque fournit des implémentations d'algorithmes classiques et de données.
Organisation
Le projet est divisé en deux packages, algorithmes et structure. Le package des algorithmes contient des implémentations d'algorithmes principalement autonomes tandis que le package de structure contient des structures de données et des algorithmes qui fonctionnent exclusivement sur eux.
Algorithmes
Voici une liste d'algorithmes sous le package des algorithmes:
Dans binarysearch.py:
- Recherche binaire standard: la recherche binaire standard. https://en.wikipedia.org/wiki/binary_search_algorithme
- Première recherche binaire: la recherche binaire standard, sauf qu'il trouve le premier élément qui correspond à la clé de recherche.
Dans expression.py:
Algorithme de cour shunting: algorithme de Dijkstra pour convertir l'infixation en notation post-fixe. https://en.wikipedia.org/wiki/shunting-yard_algorithme
L'algorithme à deux piles de Dijkstra: l'algorithme de Dijkstra pour interpréter les expressions postfix.
Dans Problemsolver.py:
- A * Algorithme: un algorithme de recherche de chemin. https://en.wikipedia.org/wiki/a*_search_algorithme
- A * Algorithme adapté au problème 8-puzzle: https://www.cs.princeton.edu/Courses/archive/spr10/cos226/assignments/8puzzle.html
Dans SORT.PY:
- Tri de sélection: https://en.wikipedia.org/wiki/Selection_sort
- Tri d'insertion: https://en.wikipedia.org/wiki/insertion_sort
- SORT SOCH: https://en.wikipedia.org/wiki/Shellsort
- Variations du tri de fusion: https://en.wikipedia.org/wiki/merge_sort
- Nombre d'inversion: compter le nombre d'inversions avec un tri de fusion modifié
- Variations du tri rapide: y compris le tri rapide standard, le tri rapide à 3 voies et l'échantillonnage rapide. https://en.wikipedia.org/wiki/quicksort
- Toi de tas: https://en.wikipedia.org/wiki/heapsort
- Sélectionnez KTH: Sélectionnez l'élément Kth dans l'ordre. Basé sur la partition de tri rapide.
Structure
Voici une liste des structures et algorithmes de données implémentés qui les opèrent:
Dans linkedList.py:
- Liste liée: https://en.wikipedia.org/wiki/Linked_list
- Stack lié: pile implémentée avec une liste liée.
- Fitre liée: file d'attente implémentée avec une liste liée.
Dans Unionfind.py: https://en.wikipedia.org/wiki/disjoint-set_data_structure
- Renseignante rapide: ensemble disjoint implémenté avec la structure de données comme un tableau. O (1) trouver.
- Union rapide: ensemble disjoint implémenté avec l'arbre de lien parent.
- Équilibré Quick Union: Set Disjoint Implémenté avec un arbre de lien parent et équilibrer l'union. O (log (n)) Efficacité pour trouver et union.
- Path Compression Quick Union: ensemble disjoint implémenté avec l'arbre de liaison parent et augmenté avec la compression de chemin.
- Compression de chemin équilibré Union rapide: ensemble disjoint implémenté avec l'arborescence de liaison parent avec l'équilibrage et la compression de chemin. Presque amorti O (1) Efficacité sur la recherche et l'union.
Dans symboltable.py:
- Arbre de recherche binaire: BST standard. https://en.wikipedia.org/wiki/binary_search_tree
- Arbre rouge et noir: BST équilibré en utilisant la représentation 2-3. https://en.wikipedia.org/wiki/Red%E2%80%93BLACK_TREE
- Table de hachage de chaînage séparé: Tableau de hachage qui résolve la collision en les enchaînant dans une liste. https://en.wikipedia.org/wiki/hash_table#separate_chaining
- Adresse ouverte Tableau de hachage: Tableau de hachage qui résout la collision avec le sondage linéaire. https://en.wikipedia.org/wiki/hash_table#open_addressing
Dans heap.py:
- Tas binaire: mise en œuvre d'une file d'attente prioritaire avec un tas binaire. https://en.wikipedia.org/wiki/binary_heap
Dans graph.py:
- Graphique non dirigée: https://en.wikipedia.org/wiki/graph_(discrete_mathematics)#undirected_graph
- Graphique réalisé: https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)#directed_graph
- Graphique pondéré non dirigée: https://en.wikipedia.org/wiki/graph_(discrete_mathematics)#weaspeyled_graph
- Graphique pondéré réalisé: https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)#weleasy_graph
- Profondeur Première recherche: https://en.wikipedia.org/wiki/depth-first_search
- Étendue première recherche: https://en.wikipedia.org/wiki/Breadth-First_Search
- Composants connectés non dirigés: https://en.wikipedia.org/wiki/Component_(graph_theory)
- Détection du cycle non dirigé: https://en.wikipedia.org/wiki/Cycle_(graph_theory)
- Détection du cycle réalisé: https://en.wikipedia.org/wiki/Cycle_(graph_theory)
- Détection de biparte: https://en.wikipedia.org/wiki/Bubartite_graph
- Ordonnance topologique: https://en.wikipedia.org/wiki/topological_sortting
- Composants fortement connectés (algorithme de Kosaraju): https://en.wikipedia.org/wiki/Kosaraju%27S_Algorithme
- Algorithme de Prim (paresseux): https://en.wikipedia.org/wiki/prim%27s_algorithme
- Algorithme de Kruskal: https://en.wikipedia.org/wiki/kruskal%27s_algorithme
- Le chemin le plus court de Dijkstra: https://en.wikipedia.org/wiki/dijkstra%27s_algorithm
- Chemin le plus court acyclique topologique: https://en.wikipedia.org/wiki/topological_sortting#application_to_shortest_path_finding
- Bellman Ford Path le plus court: https://en.wikipedia.org/wiki/Bellman%E2%80%93ford_algorithm
Usage
Tous les composants sont testés. Cependant, ils ne sont pas testés selon des normes de production rigoureuses. Les structures de données telles que la liste liée et les symboltables ont des interfaces comme la liste et le dictionnaire Python standard.
