Focus C : Structure autoréférentielle
Je vous propose un focus sur l'utilisation du type struct au travers d'un problème général consistant à compter le nombre d'occurrences de tous les mots lus en entrée et de les trier simultanément.
Puisque la liste de mots n'est pas connue à l'avance, il n'est pas pratique de la trier et d'utiliser une recherche dichotomique.
Cependant, nous ne pouvons pas non plus effectuer une recherche séquentielle à l'arrivée de chaque mot pour vérifier si on l'a déjà rencontré ; le temps d'exécution du programme serait trop long.
Comment pouvons-nous organiser les données pour faire face efficacement à liste de mots arbitraires ?
Nous allons utiliser une structure appelée arbre binaire.
Pour ceux qui sont peu familier avec la notion de structure, vous pouvez retrouver dans l'aide-mémoire les explications qui vous permettrons de mieux appréhender ce concept.
Vous pouvez retrouver toutes les explications sur le développement de ce programme dans la bibliothèque thématique de programme C.
Le programme Structures autoréférentielles - Implémentation d'un arbre binaire détaille toute la problématique, les fonctions implémentées et un exemple d'utilisation.
Le code source du programme btree est aussi librement téléchargeable.