Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

ALGORITHMES ET STRUCTURES DE DONNÉES GÉNÉRIQUES Cours et exercices corrigés en

ALGORITHMES ET STRUCTURES DE DONNÉES GÉNÉRIQUES Cours et exercices corrigés en langage C Michel Divay Professeur à l’université Rennes 1 2e édition Illustration de couverture : Lionel Auvergne © Dunod, Paris, 1999, 2004 ISBN 2 10 007450 4 Ce pictogramme mérite une explication. Son objet est d’alerter le lecteur sur la menace que représente pour l’avenir de l’écrit, particulièrement dans le domaine de l’édition tech- nique et universitaire, le dévelop- pement massif du photo- copillage. Le Code de la propriété intellectuelle du 1er juillet 1992 interdit en effet expressément la photocopie à usage collectif sans autorisation des ayants droit. Or, cette pratique s’est généralisée dans les établissements d’enseignement supérieur, provoquant une baisse brutale des achats de livres et de revues, au point que la possibilité même pour les auteurs de créer des œuvres nouvelles et de les faire éditer correctement est aujourd’hui menacée. Nous rappelons donc que toute reproduction, partielle ou totale, de la présente publication est interdite sans autorisation du Centre français d’exploitation du droit de copie (CFC, 20 rue des Grands- Augustins, 75006 Paris). Toute reprsentation ou reproduction intgrale ou partielle faite sans le consentement de lÕauteur ou de ses ayants droit ou ayants cause est illicite selon le Code de la proprit intellectuelle (Art L 122-4) et constitue une contrefaon rprime par le Code pnal. ¥ Seules sont autorises (Art L 122-5) les copies ou reproductions strictement rserves lÕusage priv du copiste et non destines une utilisation collective, ainsi que les analyses et courtes citations justifies par le caractre critique, pdagogique ou dÕinformation de lÕÏuvre laquelle elles sont incorpores, sous rserve, toutefois, du respect des dispositions des articles L 122-10 L 122-12 du mme Code, relatives la reproduction par reprographie. © Dunod – La photocopie non autorisée est un délit. Table des matières AVANT-PROPOS IX CHAPITRE 1 • RÉCURSIVITÉ, POINTEURS, MODULES 1 1.1 Récursivité des procédures : définition 1 1.2 Exemples de fonctions récursives 2 1.2.1 Exemple 1 : factorielle 2 1.2.2 Exemple 2 : nombres de Fibonacci 4 1.2.3 Exemple 3 : boucles récursives 7 1.2.4 Exemple 4 : numération 8 1.2.5 Exemple 5 : puissance nième d’un nombre 10 1.2.6 Exemple 6 : Tours de Hanoi 11 1.2.7 Exemple 7 : tracés récursifs de cercles 15 1.2.8 Exemple 8 : tracé d’un arbre 17 1.2.9 Conclusions sur la récursivité des procédures 19 1.3 Récursivité des objets 19 1.3.1 Rappel sur les structures 19 1.3.2 Exemple de déclaration incorrecte 20 1.3.3 Structures et pointeurs 20 1.3.4 Opérations sur les pointeurs 23 1.4 Modules 24 1.4.1 Notion de module et de type abstrait de données (TAD) 24 1.4.2 Exemple : module de simulation d’écran graphique 25 1.5 Pointeurs de fonctions 33 1.6 Résumé 34 IV Table des matières CHAPITRE 2 • LES LISTES 36 2.1 Listes simples : définition 36 2.2 Représentation en mémoire des listes 37 2.3 Module de gestion des listes 38 2.3.1 Création d’un élément de liste (fonction locale au module sur les listes) 41 2.3.2 Ajout d’un objet 41 2.3.3 Les fonctions de parcours de liste 43 2.3.4 Retrait d’un objet 44 2.3.5 Destruction de listes 47 2.3.6 Recopie de listes 47 2.3.7 Insertion dans une liste ordonnée 47 2.3.8 Le module de gestion de listes 48 2.4 Exemples d’application 51 2.4.1 Le type Personne 51 2.4.2 Liste de personnes 52 2.4.3 Les polynômes 55 2.4.4 Les systèmes experts 61 2.4.5 Les piles 66 2.4.6 Les ﬁles d’attente (gérée à l’aide d’une liste) 72 2.5 Avantages et inconvénients des listes 75 2.6 Le type abstrait de données (TAD) liste 75 2.7 Les listes circulaires 75 2.7.1 Le ﬁchier d’en-tête des listes circulaires 76 2.7.2 Insertion en tête de liste circulaire 77 2.7.3 Insertion en ﬁn de liste circulaire 78 2.7.4 Parcours de listes circulaires 78 2.7.5 Le module des listes circulaires 79 2.7.6 Utilisation du module des listes circulaires 79 2.8 Les listes symétriques 80 2.8.1 Le ﬁchier d’en-tête des listes symétriques 80 2.8.2 Le module des listes symétriques 81 2.8.3 Utilisation du module des listes symétriques 84 2.9 Allocation contiguë 86 2.9.1 Allocation - désallocation en cas d’allocation contiguë 86 2.9.2 Exemple des polynômes en allocation contiguë avec liste libre 87 2.9.3 Exemple de la gestion des commandes en attente 89 2.10 Résumé 100 Table des matières V © Dunod – La photocopie non autorisée est un délit. CHAPITRE 3 • LES ARBRES 102 3.1 Les arbres n-aires 102 3.1.1 Déﬁnitions 102 3.1.2 Exemples d’applications utilisant les arbres 103 3.1.3 Représentation en mémoire des arbres n-aires 106 3.2 Les arbres binaires 108 3.2.1 Déﬁnition d’un arbre binaire 108 3.2.2 Transformation d’un arbre n-aire en un arbre binaire 108 3.2.3 Mémorisation d’un arbre binaire 109 3.2.4 Parcours d’un arbre binaire 114 3.2.5 Propriétés de l’arbre binaire 122 3.2.6 Duplication, destruction d’un arbre binaire 125 3.2.7 Égalité de deux arbres 127 3.2.8 Dessin d’un arbre binaire 127 3.2.9 Arbre binaire et questions de l’arbre n-aire 130 3.2.10 Le module des arbres binaires 137 3.2.11 Les arbres de chaînes de caractères 140 3.2.12 Arbre binaire et tableau 149 3.2.13 Arbre binaire et ﬁchier 153 3.2.14 Arbre binaire complet 154 3.3 Les arbres binaires ordonnés 156 3.3.1 Déﬁnitions 156 3.3.2 Arbres ordonnés : recherche, ajout, retrait 157 3.3.3 Menu de test des arbres ordonnés de chaînes de caractères 163 3.4 Les arbres binaires ordonnés équilibrés 167 3.4.1 Déﬁnitions 167 3.4.2 Ajout dans un arbre ordonné équilibré 168 3.4.3 Exemple de test pour les arbres équilibrés 179 3.5 Arbres n-aires ordonnés équilibrés : les b-arbres 182 3.5.1 Déﬁnitions et exemples 182 3.5.2 Insertion dans un B-arbre 183 3.5.3 Recherche, parcours, destruction 185 3.6 Résumé 196 CHAPITRE 4 • LES TABLES 197 4.1 Cas général 197 4.1.1 Déﬁnition 197 4.1.2 Exemples d’utilisation de tables 198 4.1.3 Création, initialisation de tables 200 4.1.4 Accès séquentiel 201 4.1.5 Accès dichotomique (recherche binaire) 203 4.1.6 Le module des tables 206 4.1.7 Exemples d’application des tables 210 VI Table des matières 4.2 Variantes des tables 213 4.2.1 Rangement partitionné ou indexé 213 4.2.2 Adressage calculé 215 4.3 Adressage dispersé, hachage, hash-coding 217 4.3.1 Déﬁnition du hachage 217 4.3.2 Exemples de fonction de hachage 218 4.3.3 Analyse de la répartition des valeurs générées par les fonctions de hachage 220 4.3.4 Résolution des collisions 221 4.3.5 Résolution à l’aide d’une nouvelle fonction 222 4.3.6 Le ﬁchier d’en-tête des fonctions de hachage et de résolution 227 4.3.7 Le corps du module sur les fonctions de hahscode et de résolution 227 4.3.8 Le type TableHC (table de hachage) 228 4.3.9 Exemple simple de mise en œuvre du module sur les tables de hash-code 233 4.3.10 Programme de test des fonctions de hachage 235 4.3.11 Résolution par chaînage avec zone de débordement 237 4.3.12 Résolution par chaînage avec une seule table 238 4.3.13 Retrait d’un élément 244 4.3.14 Parcours séquentiel 244 4.3.15 Évaluation du hachage 244 4.3.16 Exemple 1 : arbre n-aire de la Terre (en mémoire centrale) 245 4.3.17 Exemple 2 : arbre n-aire du corps humain (ﬁchier) 249 4.4 Résumé 253 CHAPITRE 5 • LES GRAPHES 254 5.1 Définitions 254 5.1.1 Graphes non orientés (ou symétriques) 254 5.1.2 Graphes orientés 255 5.1.3 Graphes orientés ou non orientés 256 5.2 Exemples de graphes 257 5.3 Mémorisation des graphes 259 5.3.1 Mémorisation sous forme de matrices d’adjacence 259 5.3.2 Mémorisation en table de listes d’adjacence 260 5.3.3 Liste des sommets et listes d’adjacence : allocation dynamique 260 5.4 Parcours d’un graphe 261 5.4.1 Principe du parcours en profondeur d’un graphe 262 5.4.2 Principe du parcours en largeur d’un graphe 262 5.5 Mémorisation 263 5.5.1 Le type Graphe 264 5.5.2 Le ﬁchier d’en-tête des graphes 264 5.5.3 Création et destruction d’un graphe 265 5.5.4 Insertion d’un sommet ou d’un arc dans un graphe 267 5.5.5 Écriture d’un graphe (listes d’adjacence) 267 5.5.6 Parcours en profondeur (listes d’adjacence) 268 5.5.7 Parcours en largeur (listes d’adjacence) 268 Table des matières VII © Dunod – La photocopie non autorisée est un délit. 5.5.8 Plus court chemin en partant d’un sommet 269 5.5.9 Création d’un graphe à partir d’un ﬁchier 274 5.5.10 Menu de test des graphes (listes d’adjacence et matrices) 276 5.6 Mémorisation sous forme de matrices 281 5.6.1 Le ﬁchier d’en-tête du module des graphes (matrices) 281 5.6.2 Création et destruction d’un graphe (matrices) 282 5.6.3 Insertion d’un sommet ou d’un arc dans un graphe (matrices) 283 5.6.4 Lecture d’un graphe (à partir d’un ﬁchier) 284 5.6.5 Écriture d’un graphe 284 5.6.6 Parcours en profondeur (matrices) 285 5.6.7 Parcours en largeur (matrices) 285 5.6.8 Plus courts chemins entre tous les sommets (Floyd) 286 5.6.9 Algorithme de Floyd 288 5.6.10 Algorithme de calcul de la fermeture transitive 290 5.6.11 Menu de test des graphes (matrices) 293 5.7 Résumé 293 5.8 Conclusion générale 294 CORRIGÉS DES EXERCICES 295 BIBLIOGRAPHIE 337 INDEX 339 Avant-propos 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 ﬁchiers et de découpage en fonctions d’un programme. Il présente des notions plus complexes très utilisées en conception uploads/S4/ cours-c-avancee-et-structures-de-donnes.pdf