Algorithmes et structure des donnée génériques

Ce livre suppose acquis les concepts de base de la programmation tels que les
notions de constantes, de types, de variables, de tableaux, de structures, de fichiers et
de découpage en fonctions d’un programme. Il présente des notions plus complexes
très utilisées en conception de programmes performants sur ordinateur.
Le chapitre 1 introduit la notion de récursivité des procédures et de récursivité des
données conduisant à la notion d’allocation dynamique et de pointeurs. Il introduit
ensuite la notion de découpage d’une application en modules communiquant grâce à
des interfaces basées sur des appels de fonction. Le module devient un nouveau type
de données : l’utilisateur du module n’accède pas directement aux données du
module qui sont masquées et internes au module. On parle alors d’encapsulation des
données qui sont invisibles de l’extérieur du module. Le type ainsi défini est un type
abstrait de données (TAD) pour l’utilisateur qui communique uniquement par un jeu
de fonctions de l’interface du module. Cette notion est constamment mise en application
dans les programmes de ce livre.
Le chapitre 2 présente la notion de listes, très utilisée en informatique dès lors que
l’information à gérer est sujette à ajouts ou retraits en cours de traitement. Un module
est défini avec des opérations de base sur les listes indépendantes des applications. Des
exemples de mise en oeuvre sont présentés, ainsi que des variantes des listes (circulaires,
symétriques) et des mémorisations en mémoire centrale ou secondaire (fichiers).
Le chapitre 3 définit la notion d’arbres (informations arborescentes). La plupart
des algorithmes utilisent la récursivité qui s’impose pleinement pour le traitement. Les algorithmes présentés sont écrits en C et souvent de manière complète, ce qui
permet au lecteur de tester personnellement les programmes et de
jouer avec
pour en
comprendre toutes les finesses. Jouer avec le programme signifie être en mesure de le
comprendre, de faire des sorties intermédiaires pour vérifier ou expliciter certains
points et éventuellement être en mesure de l’améliorer en fonction de l’application
envisagée. Les programmes présentés font un minimum de contrôles de validité de
façon à bien mettre en évidence l’essentiel des algorithmes. Les algorithmes pourraient
facilement être réécrits dans tout autre langage autorisant la modularité, la récursivité et
l’allocation dynamique. Le codage est secondaire ; par contre la définition des fonctions
de base pour chaque type de structures de données est fondamentale. Chaque
structure de données se traduit par la création d’un nouveau type (Liste, Noeud, Table,
Graphe) et de son interface sous la forme d’un jeu de fonctions d’initialisation, d’ajout,
de retrait, de parcours de la structure ou de fonctions plus spécifiques de la structure de
données. Des menus de tests et de visualisation permettent de voir évoluer la structure.
Ils donnent de plus des exemples de mise en oeuvre des nouveaux types créés.