Remerciez-le!

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

Les structures Les structures de données de données illustrées avec illustrées

Les structures Les structures de données de données illustrées avec illustrées avec WPF et C#4 WPF et C#4 Programmer les piles, les files, les listes chaînées, les arbres et les tables Utilisation de Visual Studio 2010 et .NET Framework 4.0 Conception, test et déploiement d’application Les structures de données illustrées avec WPF et C#4 Patrice REY Toutes les marques citées ont été déposées par leurs propriétaires respectifs. La loi du 11 Mars 1957 n’autorisant aux termes des alinéas 2 et 3 de l’article 41, d’une part, que les «copies ou reproductions strictement réservées à l’usage privé du copiste et non destinées à une utilisation collective», et, d’autre part, que les analyses et les courtes citations dans un but d’exemple et d’illustration, «toute représentation ou reproduction intégrale, ou partielle, faite sans le consentement de l’auteur ou de ses ayants droit ou ayant cause, est illicite» (alinéa 1er de l’article 40). Cette représentation ou reproduction, par quelque procédé que ce soit, constituerait donc une contre-façon sanctionnée par les articles 425 et suivants du Code Pénal. Titres déjà parus Initiation au jeu 2D avec Silverlight 4 (ISBN : 978-2-8106-1168-3) Éditeur Books on Demand GmbH, 12/14 rond point des Champs Élysées, 75008 Paris, France Impression : Books on Demand GmbH, Norderstedt, Allemagne ISBN : 978-2-8106-1387-8 Dépôt légal : Avril 2011 Auteur Patrice REY 85 rue de vincennes App 23 B 33000 BORDEAUX e-mail : reypatrice@orange.fr Table des matières Avant-propos .......................................................................................... 7 Chapitre 1 - La récursivité 1. La notion de récursion ...................................................................... 16 2. La fonction factorielle ....................................................................... 17 3. La puissance de N .............................................................................. 18 4. La suite de Fibonacci ......................................................................... 20 5. Algorithme d’Euclide et PGCD .......................................................... 23 6. Les tours de Hanoï ............................................................................. 27 7. Un coloriage récursif ......................................................................... 33 Chapitre 2 - Les piles 1. Une pile contenant des entiers ......................................................... 38 2. Une pile générique ............................................................................ 46 2.1 - Créer une classe générique ...................................................... 47 2.2 - Le contrôle utilisateur FicheEmploye ..................................... 49 2.3 - Une pile générique contenant des fiches ................................ 51 3. Les expressions arithmétiques ......................................................... 53 3.1 - De la notation infixée à la notation suffixée .......................... 55 3.2 - Evaluation de la notation suffixée ........................................... 57 4. Inverser des chaînes de caractères ..................................................... 60 Chapitre 3 - Les files 1. Une file contenant des chaînes de caractère ..................................... 64 2. Une file générique .............................................................................. 72 Table des matières 4 2.1 - Créer une file générique ........................................................... 73 2.2 - Le contrôle utilisateur Voiture ................................................... 75 2.3 - Une file générique contenant des voitures ............................... 77 Chapitre 4 - Les listes chainées 1. La liste chaînée ................................................................................. 82 1.1 - Les primitives de gestion des listes ......................................... 83 1.2 - Implémentation d’un élément de type entier ......................... 84 1.3 - Implémentation d’une liste contenant des entiers ................... 86 1.4 - Utilisation de la liste ListeChaineeAvecEntiers ........................ 92 2. Une liste générique contenant des wagons ....................................... 94 2.1 - Rendre générique le type Element ............................................. 95 2.2 - Rendre générique le type Liste ................................................... 96 2.3 - Utiliser la liste générique ............................................................ 99 3. Inversion de l’ordre et tri par insertion d’une liste ........................... 105 3.1 - Inversion de l’ordre d’une liste de boules ..................................... 107 3.2 - Tri par insertion d’une liste de pions ............................................. 112 4. La liste chaînée circulaire ................................................................... 119 4.1 - La liste chaînée circulaire générique ............................................ 122 4.2 - Une liste circulaire contenant des chevaux .................................. 126 5. Le problème de Flavius Josèphe ....................................................... 131 6. Les polynômes .................................................................................. 140 Chapitre 5 - Les arbres 1. Définition et terminologie ............................................................... 152 1.1 - Vocabulaire employé pour les arbres ....................................... 153 1.2 - Les types d’arbres .................................................................... 156 2. Le parcours d’un arbre multibranche .............................................. 156 2.1 - Une liste d’adjacence ................................................................. 158 2.2 - Un nœud générique .................................................................. 161 2.3 - Parcours d’un arbre .................................................................... 163 Table des matières 5 3. L’arbre binaire ................................................................................... 166 4. Un arbre binaire d’expression arithmétique ..................................... 168 4.1 - Principe de construction ............................................................ 168 4.2 - Parcours d’un arbre binaire ........................................................ 169 4.3 - Implémentation ......................................................................... 173 5. Arbre binaire de recherche ................................................................ 181 5.1 - Construction d’un arbre de recherche ...................................... 181 5.2 - Mise en application ................................................................... 182 5.3 - Implémentation de l’arbre de recherche .................................. 183 Chapitre 6 - Les méthodes de tri 1. Le tri par sélection (selection sort) ........................................................ 192 1.1 - Principe de la méthode ............................................................... 192 1.2 - Un exemple illustré .................................................................... 194 2. Le tri par insertion (insertion sort) ......................................................... 199 2.1 - Principe de la méthode .............................................................. 199 2.2 - Un exemple illustré .................................................................... 201 3. Le tri à bulles (bubble sort) .................................................................... 203 3.1 - Principe de la méthode ............................................................... 203 3.2 - Un exemple illustré .................................................................... 203 4. Le tri Shell (Shell sort) ........................................................................... 206 4.1 - Principe de la méthode .............................................................. 206 4.2 - Un exemple illustré .................................................................... 209 5. Le tri rapide (quick sort) ....................................................................... 211 5.1 - Principe de la méthode .............................................................. 211 5.2 - Un exemple illustré .................................................................... 213 Chapitre 7 - Les recherches 1. La recherche séquentielle ................................................................. 216 1.1 - Un fichier de données au format XML ....................................... 216 1.2 - La construction de l’exemple .................................................... 218 Table des matières 6 1.3 - Charger un fichier XML ........................................................... 220 1.4 - Un parcours séquentiel ............................................................ 225 2. La recherche dichotomique ........................................................... 228 2.1 - Construction de l’application ................................................... 228 2.2 - La version récursive .................................................................. 230 2.3 - La version itérative .................................................................... 233 Chapitre 8 - Les tables 1. Définition et principe ........................................................................ 236 2. Implémentation de la clé et du contenu ............................................ 237 2.1 - Une clé de type TCle<T> ............................................................ 237 2.2 - Un contenu de type TInfos<T> .................................................. 239 3. Une table indexant des mots du dictionnaire .................................... 239 4. Un dictionnaire des acteurs du cinéma ............................................ 251 4.1 - Une clé générique à deux types .................................................. 251 4.2 - Un dictionnaire comme application .......................................... 251 5. La concordance ................................................................................. 263 6. La table de hachage ........................................................................... 272 6.1 - Définition du hachage ................................................................. 272 6.2 - Les fonctions de hachage ............................................................ 274 6.3 - Mise en pratique des fonctions de hachage ................................ 279 Index ....................................................................................................... 295 Avant-propos La programmation des logiciels est très complexe de nos jours et elle ne peut se faire qu’avec beaucoup de pratique. L’apprentissage des concepts par la théorie représente une phase obligatoire. Néanmoins, si ces concepts ne sont pas exploités en pratique, quelque soit le langage informatique employé, la progression en programmation s’en trouve alors fortement ralentie. L’informatique étant à la fois une science, une technologie et un ensemble d’outils, ces trois composantes permettent l’apprentissage de la programmation logicielle. Les structures de données sont un des piliers fondamentaux sur lesquels repose l’enseignement de l’informatique. Les structures de données modélisent au mieux les informations à traiter pour en faciliter le traitement par l’algorithme considéré. S’il est important d’apprendre et de comprendre les structures de données de façon théorique, il est très important de mettre en oeuvre ces structures de données par des exemples pratiques. En effet, la pratique apporte souvent une compréhension objective et pragmatique de la théorie acquise. La visualisation d’une notion par un exemple pratique montre très souvent ses points forts et ses faiblesses, obligeant le programmeur à contourner le problème pour arriver à une solution acceptable et performante. C’est la meilleure façon de progresser rapidement et sûrement dans l’apprentissage des notions et concepts. Les structures de données Les informaticiens, ou les simples usagers de l’outil informatique, utilisent des systèmes informatiques pour concevoir ou exécuter généralement des programmes d’application. Pour modéliser au mieux les informations à traiter, l’emploi des structures de données s’avère nécessaire. Les structures de données spécifient la façon de représenter les données d’un problème considéré. Cela est nécessaire en particulier pour un traitement par un algorithme à l’aide d’un ordinateur. De nos jours, les ordinateurs sont très puissants, capables d’effectuer de nombreux calculs simultanément, et ils sont dotés d’une quantité de mémoire Avant-propos 8 assez importante. Malgré cela, deux préoccupations principales interviendront dans le choix des structures de données: la place qu’elles consomment dans la mémoire de l’ordinateur et la facilité qu’elles offrent quand on cherche à accéder à une certaine donnée. Même si les structures de données sont définies indépendamment du langage de programmation, leur mise en pratique avec un langage de programmation évolué (C#, C++, Java) permettra de mieux les comprendre, de mieux les appréhender, de mieux les utiliser, et de mieux en apprécier leur utilité et leur performance. Les structures de données classiques appartiennent le plus souvent aux familles suivantes: • les structures linéaires qui sont essentiellement des structures représentables par des listes linéaires, c’est-à-dire des tableaux ou des listes chaînées unidimensionnelles; on y trouve en particulier les piles (pour lesquelles les données sont ajoutées ou supprimées à partir d’une même extrémité) et les files (pour lesquelles les données sont ajoutées à une extrémité tandis qu’elles sont supprimées à l’autre extrémité). • les structures arborescentes avec notamment la sous-famille importante des arbres binaires. • les structures relationnelles qui prennent en compte des uploads/Ingenierie_Lourd/ bod-02-structures-donnees-wpf-csharp4.pdf