Data Structures and Algorithms in C Téléchargement - Data Structures and Algorithms in C Téléchargement du code source

Data Structures and Algorithms in C

Autre code source

1.0.0

Télécharger

Sticartes et algorithmes de données implémentés en C

Ici, vous trouverez certaines structures de données et algorithmes implémentés dans C. Ces algorithmes sont principalement basés sur l' introduction du livre aux algorithmes de Thomas H. Cormen .

Instructions

Chaque module se compose d'au moins d'un fichier d'en-tête (.h) et d'un fichier source qui contient le CODE CORPUS (.C). Afin d'utiliser l'un de ces modules, je vous suggère de suivre ces étapes:

Trouvez la structure de données ou l'algorithme dont vous avez besoin à partir de /modules
Téléchargez le répertoire du module (par exemple /modules/List ) qui contient le fichier de code source .c (par exemple List.c )
Allez dans /include/ dossier, trouvez le fichier d'en-tête (.h) que vous souhaitez (par exemple List.h ) et téléchargez-le.
❕ Pas encore terminé ❕, allez maintenant vérifier le fichier d'en-tête (.h) et télécharger ce qui est inclus (commandes #include "foo.h" ). La plupart des modules incluent par exemple HashFunctions ou Comparators ou même d'autres structures de données. Repérez ce qui est nécessaire et téléchargez tous les fichiers.
Corrigez les chemins de #include "foo.h" si vous modifiez la structure du dossier actuel.
Tout est prêt, j'espère que cela vous a aidé!

Compiler et exécuter

Si vous clonez l'ensemble du dossier, vous pouvez exécuter:

make : qui complique chaque module
make run-tests : qui compile chaque module et exécute tous les tests
make valgind-tests : qui compile chaque module et exécute tous les tests à l'aide de Valgrind

Appendice

Structure de données	Définition
Filtre à floraison	Le filtre Bloom est une structure de données probabilistes économe en espace, conçue par Burton Howard Bloom en 1970, qui est utilisée pour tester si un élément est membre d'un ensemble. Des correspondances faussement positives sont possibles, mais les faux négatifs ne sont pas - en d'autres termes, une requête renvoie "éventuellement dans le jeu" ou "certainement pas dans le jeu". Des éléments peuvent être ajoutés à l'ensemble, mais non supprimés (bien que cela puisse être traité avec la variante du filtre de floraison de comptage); Plus les éléments sont ajoutés, plus la probabilité de faux positifs est grande.
Arbre noir	L'arbre rouge-noir est une sorte d'arbre de recherche binaire auto-équilibré. Chaque nœud stocke un bit supplémentaire représentant "couleur" ("rouge" ou "noir"), utilisé pour s'assurer que l'arbre reste équilibré pendant les insertions et les suppressions. Lorsque l'arbre est modifié, le nouvel arbre est réarrangé et "repeint" pour restaurer les propriétés de coloration qui contraignent à quel point l'arbre peut devenir déséquilibré dans le pire des cas. Les propriétés sont conçues de telle sorte que ce réarrangement et cette recoloration puissent être effectués efficacement. Le rééquilibrage n'est pas parfait, mais garantit la recherche en temps o (logn) , où n est le nombre de nœuds de l'arbre. Les opérations d'insertion et de suppression, ainsi que le réarrangement et la recoloration de l'arbre, sont également effectuées en temps d' O (Log) .
Liste liée	La liste liée est une collecte linéaire d'éléments de données dont l'ordre n'est pas donné par leur placement physique en mémoire. Au lieu de cela, chaque élément pointe vers le suivant. Il s'agit d'une structure de données composée d'une collection de nœuds qui représentent ensemble une séquence.
File d'attente	La file d'attente prioritaire est un type de données abstrait similaire à une structure de données de file d'attente ou de pile régulière dans laquelle chaque élément a en outre une "priorité" associée. Dans une file d'attente de priorité, un élément avec une priorité élevée est servi devant un élément avec une faible priorité.
Hashtable avec liste	Mise en œuvre générique d'un hachage très simple avec des clés et des chaînes. Aucune reconstruction fournie.
Hachage avec un arbre rouge-noir	Consistait en une table, dans laquelle chaque ligne a un pointeur vers un arbre rouge-noir de cette façon, nous obtenons les meilleures complexités ci-dessus et en évitant en même temps trop de collisions.
Hashtable avec seaux à l'arbre rouge-noir	Le hashtable était composé de seaux de pointeurs vers des arbres noirs rouges
Maxheap	Un maximum de max est un arbre binaire complet dans lequel la valeur dans chaque nœud interne est supérieure ou égale aux valeurs chez les enfants de ce nœud. Le mappage des éléments d'un tas dans un tableau est trivial: si un nœud est stocké un index k, alors son enfant gauche est stocké à l'index 2k + 1 et son enfant droit à l'index 2k + 2.
Disjoint	La structure de données disjointes, également appelée structure de données Union-Find ou Ensemble de fusion-lit, est une structure de données qui stocke une collection d'ensembles disjoints (non-chevauchement). De manière équivalente, il stocke une partition d'un ensemble en sous-ensembles disjoints. Il fournit des opérations pour ajouter de nouveaux ensembles, fusionner (les remplacer par leur syndicat) et trouver un membre représentatif d'un ensemble. La dernière opération permet de découvrir efficacement si deux éléments se trouvent dans les mêmes ensembles ou différents.
Planificateur d'emploi avec fils	Planificateur de travaux multi-thread Using Unix Pthreads.

Algorithme	Définition
Sort	Heapsort est un algorithme de tri basé sur une comparaison. Heapsort peut être considéré comme un type de sélection amélioré: comme le tri de sélection, Heapsort divise son entrée en une région triée et non triée, et il rétrécit itérativement la région non triée en en extrait le plus grand élément et en l'insertant dans la région triée. Contrairement au tri de sélection, Heapsort ne perd pas de temps avec un balayage linéaire de la région non triée; Au contraire, le tri de tas maintient la région non triée dans une structure de données de tas pour trouver plus rapidement le plus grand élément de chaque étape.
Quicksort	Quicksort est un algorithme de tri efficace. Développé par l'informatique britannique Tony Hoare en 1959 et publié en 1961, il s'agit toujours d'un algorithme couramment utilisé pour le tri. Lorsqu'il est bien implémenté, il peut être un peu plus rapide que le tri de fusion et environ deux ou trois fois plus rapide que Heapsort.

Algorithme

Définition

Sort

Heapsort est un algorithme de tri basé sur une comparaison. Heapsort peut être considéré comme un type de sélection amélioré: comme le tri de sélection, Heapsort divise son entrée en une région triée et non triée, et il rétrécit itérativement la région non triée en en extrait le plus grand élément et en l'insertant dans la région triée. Contrairement au tri de sélection, Heapsort ne perd pas de temps avec un balayage linéaire de la région non triée; Au contraire, le tri de tas maintient la région non triée dans une structure de données de tas pour trouver plus rapidement le plus grand élément de chaque étape.

Quicksort

Quicksort est un algorithme de tri efficace. Développé par l'informatique britannique Tony Hoare en 1959 et publié en 1961, il s'agit toujours d'un algorithme couramment utilisé pour le tri. Lorsqu'il est bien implémenté, il peut être un peu plus rapide que le tri de fusion et environ deux ou trois fois plus rapide que Heapsort.