Dados de dados
Esta biblioteca fornece implementações de algoritmos e dados de dados clássicos.
Organização
O projeto é dividido em dois pacotes, algoritmos e estrutura. O pacote de algoritmos contém implementações de algoritmos principalmente independentes, enquanto o pacote de estrutura contém estruturas e algoritmos de dados que opera exclusivamente neles.
Algoritmos
Aqui está uma lista de algoritmos no pacote de algoritmos:
Em binarySearch.py:
- Pesquisa binária padrão: a pesquisa binária padrão. https://en.wikipedia.org/wiki/binary_search_algorithm
- PRIMEIRA Pesquisa binária de ocorrência: a pesquisa binária padrão, exceto que encontra o primeiro elemento que corresponde à chave de pesquisa.
Em expressão.py:
Algoritmo de pátio de desvio: o algoritmo de Dijkstra para converter o Infix em notação pós -fixo. https://en.wikipedia.org/wiki/shunting-yard_algorithm
O algoritmo de dois pilhas de Dijkstra: o algoritmo de Dijkstra para interpretar expressões pós -fix.
Em Problemolver.py:
- A* algoritmo: um algoritmo de encontro de caminho. https://en.wikipedia.org/wiki/a*_search_algorithm
- A* algoritmo adaptado ao problema de 8 puzzle: https://www.cs.princeton.edu/courses/archive/spr10/cos226/assignments/8puzzle.html
Em Sort.py:
- Centro de seleção: https://en.wikipedia.org/wiki/selection_sort
- Classificação de inserção: https://en.wikipedia.org/wiki/insertion_sort
- Classificação de shell: https://en.wikipedia.org/wiki/shellsort
- Variações de Merge Sort: https://en.wikipedia.org/wiki/merge_sort
- Contagem de inversão: conte o número de inversões com classificação de mesclagem modificada
- Variações de classificação rápida: incluindo classificação rápida padrão, classificação rápida de 3 vias e amostragem rápida. https://en.wikipedia.org/wiki/quicksort
- HEAP CLEM: https://en.wikipedia.org/wiki/heapsort
- Selecione KTH: selecione o elemento KTH em ordem. Com base na partição rápida de classificação.
Estrutura
Aqui está uma lista de estruturas e algoritmos de dados implementados que opera neles:
Em linkedlist.py:
- Lista vinculada: https://en.wikipedia.org/wiki/linked_list
- Pilha vinculada: pilha implementada com uma lista vinculada.
- Fila vinculada: fila implementada com uma lista vinculada.
Em Unionfind.py: https://en.wikipedia.org/wiki/Disjoint-Set_Data_Structure
- Localização rápida: Conjunto Discart implementado com a estrutura da matriz. O (1) Encontre.
- União rápida: o conjunto disjunto implementado com a árvore de link dos pais.
- União rápida equilibrada: o conjunto disjunto implementado com a árvore de links para pais e o equilíbrio na união. O (log (n)) eficiência para encontrar e união.
- Compressão do caminho União rápida: o conjunto disjunto implementado com a árvore de link dos pais e aumentado com a compressão do caminho.
- Compressão do caminho equilibrado União rápida: conjunto Disjunt implementado com a árvore de link dos pais com o equilíbrio e a compressão do caminho. eficiência quase amortizada (1) em Find e Union.
Em simboltable.py:
- Árvore de pesquisa binária: BST padrão. https://en.wikipedia.org/wiki/binary_search_tree
- Árvore vermelha e preta: BST equilibrado usando 2-3 representação. https://en.wikipedia.org/wiki/red%E2%80%93black_tree
- Tabela de hash de encadeamento separada: tabela de hash que resolvem a colisão encadeando -as em uma lista. https://en.wikipedia.org/wiki/hash_table#separate_cheing
- Tabela de hash de endereço aberto: tabela de hash que resolvem colisão com sondagem linear. https://en.wikipedia.org/wiki/hash_table#open_addressing
Em heap.py:
- Pilha binária: uma implementação de uma fila de prioridade com pilha binária. https://en.wikipedia.org/wiki/binary_heap
Em graf.py:
- Gráfico não direcionado: https://en.wikipedia.org/wiki/graph_(discrete_mathematics)#undirected_graph
- Gráfico direcionado: https://en.wikipedia.org/wiki/graph_(discrete_mathematics)#directed_graph
- Gráfico pesado não direcionado: https://en.wikipedia.org/wiki/graph_(discrete_mathematics)#weighted_graph
- Gráfico ponderado direcionado: https://en.wikipedia.org/wiki/graph_(discrete_mathematics)#weighted_graph
- Profundidade Primeira pesquisa: https://en.wikipedia.org/wiki/depth-first_search
- Primeira pesquisa em largura: https://en.wikipedia.org/wiki/Breadth-First_Search
- Componentes conectados não direcionados: https://en.wikipedia.org/wiki/component_(graph_theory)
- Detecção de ciclo não direcionada: https://en.wikipedia.org/wiki/cycle_(graph_theory)
- Detecção de ciclo direcionado: https://en.wikipedia.org/wiki/cycle_(graph_theory)
- Detecção de Bipart: https://en.wikipedia.org/wiki/bipartite_graph
- Ordem topológica: https://en.wikipedia.org/wiki/topological_sorting
- Componentes fortemente conectados (algoritmo de Kosaraju): https://en.wikipedia.org/wiki/kosaraju%27s_algorithm
- Algoritmo de Prim (Lazy): https://en.wikipedia.org/wiki/prim%27s_algorithm
- Algoritmo de Kruskal: https://en.wikipedia.org/wiki/kruskal%27s_algorithm
- Caminho mais curto de Dijkstra: https://en.wikipedia.org/wiki/dijkstra%27s_algorithm
- Caminho mais curto acíclico topológico: https://en.wikipedia.org/wiki/topological_sorting#application_to_shortest_path_finding
- Bellman Ford mais curto caminho: https://en.wikipedia.org/wiki/bellman%E2%80%93ford_algorithm
Uso
Todos os componentes são testados. No entanto, eles não são testados com rigorosos padrões de produção. Estruturas de dados, como a lista vinculada e os simboltáveis, possuem interfaces como a lista Python padrão e o dicionário.
