Remerciez-le!

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

Guide de programmation HAKXWTZS4598264THKWX Structures de Données expliquées et

Guide de programmation HAKXWTZS4598264THKWX Structures de Données expliquées et illustrées avec C#5 et WPF Patrice REY Tous les noms de produits ou marques cités dans ce livre sont des marques déposées par leurs propriétaires respectifs. Titres disponibles en librairie Initiation au jeu 2D avec SILVERLIGHT 4 Les structures de données illustrées avec WPF et C#4 La programmation graphique 2D de WPF 4 La programmation graphique 3D de WPF 4 Guide pratique de la modélisation 3D avec WPF 4 La modélisation 3D avec C# et WPF 4 Développez des applications internet avec SILVERLIGHT 5 La 3D avec SILVERLIGHT 5 Le traitement d’images avec SILVERLIGHT 5 Programmez des jeux vidéo 3D avec C#5 et WPF XML expliqué et illustré avec C#5, WPF et LINQ Développement des applications web 3D avec WebGL Traitement des images avec C#5 et WPF Formation 3D par la pratique - Modéliser des molécules Modélisation 3D et Animation avec C#5 et WPF Techniques créatives avec CANVAS 2D de HTML 5 LINQ To XML avec C#5 et WPF Filtrage des images avec CANVAS 2D de HTML 5 Editeur Auteur Books on Demand GmbH, 12/14 rond point des Champs Élysées, 75008 Paris, France Impression : Books on Demand GmbH, Norderstedt, Allemagne ISBN : 9782322017300 Dépôt légal : MAI 2015 Patrice REY 85 rue de vincennes App 23 B 33000 BORDEAUX email : reypatrice@orange.fr site web : www.reypatrice.fr Table des matières Avant-propos ................................................................................ 9 Etape 1 - La notion de récursivité 1. Une fonction récursive ............................................................. 17 2. La fonction factorielle .............................................................. 21 3. La puissance N ......................................................................... 24 4. La suite de Fibonacci .............................................................. 27 5. Algorithme d’Euclide et PGCD ............................................... 31 6. Les tours de Hanoï ..................................................................... 36 7. Applications pratiques de la récursivité ............................... 45 7.1 - Un coloriage récursif ......................................................... 45 7.2 - Une image récursive ........................................................ 50 7.3 - Arborescence de données hiérarchiques XML ........... 53 Etape 2 - La pile 1. Mécanisme de la pile .............................................................. 67 2. Application avec une pile gérant des nombres entiers ....... 75 3. Réaliser une pile générique ...................................................... 79 3.1 - Créer une classe générique pour la pile ......................... 80 3.2 - Un contrôle utilisateur UcFicheVerbe ............................. 83 3.3 - Une pile gérant des éléments UcFicheVerbe .............. 84 4. Les expressions arithmétiques ................................................. 89 4.1 - De la notation infixée à la notation suffixée .................... 94 4.2 - Evaluation d’une expression suffixée ............................. 97 Le code source de programmation est téléchargeable gratuitement à l’adresse internet http://www.reypatrice.fr Table des matières 6 4.3 - Inverser une chaîne de caractères ................................. 102 Etape 3 - La file 1. Mécanisme de la file .............................................................. 105 2. Application avec une file gérant des nombres entiers ......... 113 3. Réaliser une file générique ....................................................... 117 3.1 - Créer une classe générique pour la file ............................ 118 3.2 - Un contrôle utilisateur UcEtiquetteVoiture ...................... 121 3.3 - Une file gérant des éléments UcEtiquetteVoiture .......... 123 Etape 4 - Les listes chaînées 1. Mécanisme de la liste chaînée ................................................ 127 1.1 - Les primitives de manipulation ........................................ 128 1.2 - Un maillon de type MaillonTypeEntier ........................... 131 1.3 - Une liste chaînée avec des maillons de type entier .... 134 2. Réaliser une liste chaînée générique ...................................... 158 3. Inverser une liste chaînée ........................................................ 170 4. Tri par insertion avec une liste .................................................. 175 5. La liste chaînée circulaire ........................................................ 184 5.1 - Réaliser une liste chaînée circulaire générique .............. 184 5.2 - Application pratique de la liste circulaire ......................... 191 5.3 - Le problème de Flavius Josèphe ..................................... 204 6. Gérer les polynômes avec une liste chaînée ......................... 216 Etape 5 - Les arbres 1. Définition et terminologie ......................................................... 233 2. Mécanisme de l’arbre multibranche générique .................. 240 3. Arbre binaire ............................................................................. 255 3.1 - Définition ............................................................................ 255 3.2 - Arbre binaire d’expression arithmétique ........................ 258 Table des matières 7 4. Mécanisme de l’arbre binaire de recherche ..................... 278 4.1 - Construction de l’arbre ..................................................... 279 4.2 - Implémentation de l’arbre .............................................. 283 5. Rendu graphique d’un arbre binaire de recherche .............. 293 Etape 6 - Trier et rechercher les données 1. La méthode du tri par sélection ............................................. 309 1.1 - Principe du tri par sélection ............................................... 310 1.2 - Mise en pratique du tri par sélection .............................. 312 2. La méthode du tri par insertion ............................................. 317 2.1 - Principe du tri par insertion ............................................. 318 2.2 - Mise en pratique du tri par insertion ............................ 321 3. La méthode du tri à bulles ....................................................... 325 3.1 - Principe du tri à bulles .................................................... 325 3.2 - Mise en pratique du tri à bulles .................................... 328 4. La méthode du tri Shell ............................................................ 332 5. La méthode du tri rapide ...................................................... 337 6. La recherche séquentielle ..................................................... 343 6.1 - Exécuter un processus en arrière-plan ........................... 345 6.2 - Estimation horaire d’une recherche séquentielle ........ 356 7. La recherche par dichotomie ............................................... 364 Etape 7 - Les tables 1. Mécanisme d’une table générique ....................................... 373 2. Clé générique gérant deux types différents ........................ 389 3. Application pratique avec la concordance ........................ 400 4. La table de hachage ............................................................. 419 4.1 - Principe de fonctionnement ........................................... 419 4.2 - Clé de type numérique ................................................... 427 Table des matières 8 4.3 - Clé de type chaîne de caractères ................................. 440 Etape 8 - Les graphes 1. Définition et terminologie ....................................................... 451 2. La mémorisation des graphes ............................................... 456 3. Application avec un graphe orienté et évalué .................... 459 3.1 - Mémorisation par une table de listes d’adjacences .... 459 3.2 - Parcours du graphe en largeur ...................................... 471 3.3 - Parcours du graphe en profondeur .............................. 477 4. Algorithme de Dijkstra .............................................................. 483 4.1 - Principe du plus court chemin ....................................... 483 4.2 - Mise en pratique de l’algorithme de Dijkstra .............. 490 Index ................................................................................................. 507 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 (notamment en BTS, en DUT et en Licence). 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 œuvre ces structures de données par des exemples pratiques lors de l’apprentissage de la programmation logicielle. 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 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 assez importante. Malgré cela, deux préoccupations principales interviendront dans le Avant-propos 10 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 relations existant ou n’existant pas entre les entités qu’elles décrivent; les relations binaires sont représentables généralement sous forme de graphes (orientés ou non). Une structure de données définit une abstraction des données et cache les détails de leur implémentation. L’important est de connaître les opérations que l’on peut effectuer sur les données. uploads/Marketing/ bod-19-structures-de-donnees.pdf