Data Structures and Algorithms in C download - Data Structures and Algorithms in C download de código fonte

Data Structures and Algorithms in C

Outro código-fonte

1.0.0

Baixar

Estruturas de dados e algoritmos implementados em C

Aqui você encontrará algumas estruturas de dados e algoritmos implementados em C. Esses algoritmos são baseados principalmente na introdução do livro aos algoritmos de Thomas H. Cormen .

Instruções

Cada módulo consiste em pelo menos um arquivo de cabeçalho (.h) e um arquivo de origem que contém o código de código (.c). Para usar um desses módulos, sugiro que você siga estas etapas:

Encontre a estrutura ou algoritmo de dados que você precisa de /modules
Faça o download do diretório do módulo (por exemplo /modules/List ) que contém o código -fonte .c (por exemplo, List.c )
Vá para /include/ pasta, encontre o arquivo (.h) que deseja (por exemplo, List.h ) e faça o download.
❕ Ainda não terminado ❕, agora vá e verifique o arquivo de cabeçalho (.h) e baixe o que está incluído (comandos #include "foo.h" ). A maioria dos módulos inclui, por exemplo, HashFunctions ou Comparators ou até outras estruturas de dados. Spot o que é necessário e baixe todos os arquivos.
Corrija os caminhos para o #include "foo.h" se você alterar a estrutura atual da pasta.
Tudo está pronto, espero que te ajude!

Compilar e executar

Se você clonar toda a pasta que poderá executar:

make : isso com ques
make run-tests : que compila todos os módulos e executa todos os testes
make valgind-tests : que compila todos os módulos e executa todos os testes usando Valgrind

Apêndice

Estrutura de dados	Definição
Filtro de flor	O Bloom Filter é uma estrutura de dados probabilísticos com eficiência espacial, concebida por Burton Howard Bloom em 1970, que é usada para testar se um elemento é um membro de um conjunto. As correspondências positivas falsas são possíveis, mas os falsos negativos não são - em outras palavras, uma consulta retorna "possivelmente no conjunto" ou "definitivamente não no set". Os elementos podem ser adicionados ao conjunto, mas não removidos (embora isso possa ser abordado com a variante do filtro Bloom de contagem); Quanto mais itens adicionados, maior a probabilidade de falsos positivos.
Árvore-vermelha-preta	A árvore vermelha-preta é uma espécie de árvore de busca binária auto-equilibrada. Cada nó armazena um bit extra representando "cor" ("vermelho" ou "preto"), usado para garantir que a árvore permaneça equilibrada durante inserções e deleções. Quando a árvore é modificada, a nova árvore é reorganizada e "repintada" para restaurar as propriedades para colorir que restringem o quão desequilibrado a árvore pode se tornar no pior caso. As propriedades são projetadas de modo que essa reorganização e recoloração possam ser executadas com eficiência. O re-balanceamento não é perfeito, mas garante pesquisar no tempo de O (logn) , onde n é o número de nós da árvore. As operações de inserção e exclusão, juntamente com o rearranjo e a recolução de árvores, também são realizadas no tempo O (logn) .
Lista vinculada	Lista vinculada é uma coleção linear de elementos de dados cuja ordem não é fornecida por sua colocação física na memória. Em vez disso, cada elemento aponta para o próximo. É uma estrutura de dados que consiste em uma coleção de nós que juntos representam uma sequência.
Fila	A fila de prioridade é um tipo de dados abstrato semelhante a uma estrutura de dados regular ou pilha, na qual cada elemento possui uma "prioridade" associada a ela. Em uma fila de prioridade, um elemento com alta prioridade é servido antes de um elemento com baixa prioridade.
Hashtable with List	Implementação genérica de uma hashtable muito simples com chaves e correntes. Nenhuma reconstrução fornecida.
Hashtable com árvore vermelha-preta	Consistia em uma mesa, na qual todas as fileiras têm um ponteiro para uma árvore vermelha-preta dessa maneira, obtemos as melhores complexidades acima e, ao mesmo tempo, evitando muitas colisões.
Hashtable com baldes para árvore vermelha-preta	A hashtable consistia em baldes de ponteiros para árvores negras vermelhas
MaxHeap	Um max-heap é uma árvore binária completa na qual o valor em cada nó interno é maior ou igual aos valores nos filhos desse nó. O mapeamento dos elementos de uma pilha em uma matriz é trivial: se um nó for armazenado um índice k, seu filho esquerdo será armazenado no índice 2k+1 e seu filho direito no índice 2k+2.
DiscartSet	A estrutura de dados descontraída, também chamada de estrutura de dados sindicais-base ou conjunto de dados de mesclagem, é uma estrutura de dados que armazena uma coleção de conjuntos de discoint (sem sobreposição). Equivalentemente, ele armazena uma partição de um conjunto em subconjuntos disjuntos. Ele fornece operações para adicionar novos conjuntos, mesclar conjuntos (substituindo -os por seu sindicato) e encontrar um membro representativo de um conjunto. A última operação permite descobrir com eficiência se houver dois elementos no mesmo ou em conjuntos diferentes.
Agendador de empregos com tópicos	Agendador de trabalho com vários thread usando o Unix Pthreads.

Algoritmo	Definição
Heapsort	Heapsort é um algoritmo de classificação baseado em comparação. O HEAPSORT pode ser pensado como um tipo de seleção aprimorado: como o tipo de seleção, o HeapSort divide sua entrada em uma região classificada e não classificada, e reduz iterativamente a região não classificada, extraindo o maior elemento dele e inserindo -o na região classificada. Diferentemente da classificação da seleção, o Heapsort não perde tempo com uma varredura linear da região não classificada; Em vez disso, a classificação de heap mantém a região não classificada em uma estrutura de dados de heap para encontrar mais rapidamente o maior elemento em cada etapa.
Quicksort	O Quicksort é um algoritmo de classificação eficiente. Desenvolvido pelo cientista da computação britânico Tony Hoare em 1959 e publicado em 1961, ainda é um algoritmo comumente usado para classificar. Quando implementado bem, ele pode ser um pouco mais rápido que a classificação da mesclagem e cerca de duas ou três vezes mais rápido que o HeapSort.

Algoritmo

Definição

Heapsort

Heapsort é um algoritmo de classificação baseado em comparação. O HEAPSORT pode ser pensado como um tipo de seleção aprimorado: como o tipo de seleção, o HeapSort divide sua entrada em uma região classificada e não classificada, e reduz iterativamente a região não classificada, extraindo o maior elemento dele e inserindo -o na região classificada. Diferentemente da classificação da seleção, o Heapsort não perde tempo com uma varredura linear da região não classificada; Em vez disso, a classificação de heap mantém a região não classificada em uma estrutura de dados de heap para encontrar mais rapidamente o maior elemento em cada etapa.

Quicksort

O Quicksort é um algoritmo de classificação eficiente. Desenvolvido pelo cientista da computação britânico Tony Hoare em 1959 e publicado em 1961, ainda é um algoritmo comumente usado para classificar. Quando implementado bem, ele pode ser um pouco mais rápido que a classificação da mesclagem e cerca de duas ou três vezes mais rápido que o HeapSort.