Remerciez-le!

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

- 1 - ENSMA Département I & A (Informatique & Automatique) Cours METHODES AVANC

- 1 - ENSMA Département I & A (Informatique & Automatique) Cours METHODES AVANCEES DE PROGRAMMATION Chapitre STRUCTURES DE DONNEES DYNAMIQUES & LANGAGE C Adresse sur le réseau interne de l'ENSMA : \\S-applis-ens\DATAPROFS\Informatique\guittet\A3\cours\Sdd.doc L. GUITTET email : guittet@ensma.fr 09/2010 - 2 - Table des matières 1 Introduction........................................................................................................................ 3 1.1 Pourquoi modéliser des données ? ............................................................................. 3 1.2 Pourquoi des structures de données dynamiques ? .................................................... 3 1.3 Quel langage ?............................................................................................................ 3 1.4 Quel programme (du cours☺) ? ................................................................................. 3 2. Le langage C ...................................................................................................................... 4 2.1 Introduction................................................................................................................ 4 2.2 Bonjour....................................................................................................................... 4 2.2.1 Avec le compilateur « gcc » de cygwin ............................................................. 4 2.2.2 Avec l’environnement « Visual C++ 2008 Express Edition »........................... 5 2.3 Calcul de factorielle ................................................................................................... 6 2.4 Trier un tableau .......................................................................................................... 7 2.5 Échanger deux variables............................................................................................. 8 2.6 Concaténer deux chaines............................................................................................ 9 2.7 Les nombres complexes ........................................................................................... 10 3. Structure de Donnée Abstraite ......................................................................................... 11 3.1 C’est quoi une SDA ?............................................................................................... 11 3.2 Spécification et implémentation d’une SDA............................................................ 11 3.3 La liste linéaire......................................................................................................... 12 3.3.1 Spécifications ................................................................................................... 12 3.3.1.1 Le Vecteur.................................................................................................... 12 3.3.1.2 Le Tirage ...................................................................................................... 13 3.3.2 Implémentations............................................................................................... 13 3.3.2.1 Le Vecteur.................................................................................................... 14 3.3.2.2 Le Tirage ...................................................................................................... 14 3.3.3 Spécifications algébriques................................................................................ 16 4. Structures Classiques ....................................................................................................... 17 4.1 Structures dérivées des listes.................................................................................... 17 4.1.1 La pile............................................................................................................... 17 4.1.1.1 Spécification, implémentation et test en C................................................... 18 4.1.1.2 Les tours de Hanoï : « des tours » récursif ☺............................................... 19 4.1.2 La file ............................................................................................................... 21 4.1.3 Autres structures ensemblistes linéaires........................................................... 23 4.2 Arbres....................................................................................................................... 25 4.2.1 Principe, forme générale .................................................................................. 25 4.2.2 Arbres binaires ................................................................................................. 27 4.2.2.1 Spécification algébrique............................................................................... 27 4.2.2.2 Spécification et implémentation en C .......................................................... 28 4.2.2.3 Fonctions simples sur l’arbre ....................................................................... 29 4.2.2.4 Parcours en profondeur ................................................................................ 29 4.2.2.5 Parcours en largeur....................................................................................... 30 4.3 Autres formes d'arbres.............................................................................................. 32 4.3.1 Arbres généralisés ............................................................................................ 32 4.3.2 Structures dérivées ........................................................................................... 32 4.4 Les graphes............................................................................................................... 32 4.4.1 Intérêt ............................................................................................................... 33 4.4.2 Modélisation d’un graphe................................................................................. 33 - 3 - 1 Introduction 1.1 Pourquoi modéliser des données ? Programme = algorithme + données • Pour réaliser un « bon » programme (i.e. rapide et faible en mémoire), le choix de la structure de données est aussi important que celui de l’algorithme. • La structure de données doit modéliser au mieux les informations à traiter pour en faciliter le traitement. • L’utilisation de structures de données abstraites (S.D.A.) associées à des fonctions de manipulation facilite la conception d’un algorithme. 1.2 Pourquoi des structures de données dynamiques ? • La spécification d’une S.D.A. permet de décrire des objets au niveau fonctionnel / logique tout en cachant leur implémentation. • L’implémentation (ou réalisation physique) peut-être statique (taille fixée) ou dynamique (taille variable) pour optimiser certaines fonctions (par ex : insérer une donnée) • Pour pouvoir faire varier la taille des données, le langage doit permettre la création / destruction de zone mémoire : les pointeurs. 1.3 Quel langage ? • Le langage C est très utilisé, possède de nombreux environnements de développement (MS Visual C++) et est à la base de C++ et JAVA. Il oblige le concepteur à maîtriser les allocations dynamiques de mémoire. 1.4 Quel programme (du cours☺) ? • Nous allons d’abord nous familiariser avec le langage C • Nous verrons dans le chapitre Structure de Donnée Abstraite comment spécifier puis réaliser une SDA grâce à un exemple simple : la liste • Nous étudierons alors au chapitre Structures Classiques les structures suivantes : o Linéaires (piles, files, listes ordonnées, chaînées, ensemble, dictionnaire) o Hiérarchiques (arbres binaires, arbres de recherche, arbre n-aires) o Graphes (notions générales) Une bibliographie sur le WEB est en dernière page du polycopié ainsi que la table des figures. - 4 - 2.Le langage C 2.1 Introduction C est un langage impératif, normalisé et à typage fort, mais dangereux ! Sa syntaxe très souple permet l’écriture de programmes corrects du point de vue du langage mais dont l’exécution ne fourni pas le résultat attendu. Par exemple, if (a=0) printf("oui") ; n’affichera jamais oui !!! Nous aborderons le langage au travers d’exemples de programmes commentés. Chacun d’eux montre des notions nouvelles listées en fin de paragraphe. 2.2 Bonjour Le programme suivant affiche « bonjour » à l’écran et passe à la ligne. Programme Explications #include <stdio.h> Insertion du fichier bibliothèque stdio. Il contient les E/S standard (ici printf) /*fin des include*/ Le texte entre /* et */ est un commentaire int main(void) Entête de la fonction principale. Elle n’a aucun paramètre d’entrée (void) et rend un entier (int). Son nom doit être « main » { Corps du programme entre { et } printf("bonjour\n"); Ecriture de « bonjour » suivi d’un passage à la ligne « \n » à l’écran. Le ; est séparateur d’instructions return 0; Retour de la valeur 0 au système (tout est OK) } Notions vues : include, bibliothèque stdio, commentaires, main, fonction, paramètre void, printf,\n, valeur de retour, int, {}, ; Ce programme, édité et sauvé sous forme de fichier texte « bonjour.c » nécessite certaines manipulations pour voir le résultat d’exécution. Deux moyens s’offrent à nous : 2.2.1 Avec le compilateur « gcc » de cygwin Cygwin est un logiciel installé sur Windows qui simule le système d’exploitation « Linux ». Le texte doit être compilé dans la fenêtre cygwin par la commande : > gcc bonjour.c Ceci génère un fichier « a.exe » qui est l’équivalent exécutable de bonjour.c >a.exe bonjour La commande suivante permet de nommer différemment l’exécutable (au lieu de a.exe) > gcc bonjour.c –o bonjour La production de l’exécutable se réalise en 2 étapes : 1. Compilation : source.c -------> objet.o 2. Edition de liens : objet.o + bibliothèques --------> exécutable Dans notre cas, nous avons : bonjour.c ------> bonjour.o bonjour.o + stdiolib.a -------> bonjour (ou a.exe) - 5 - L’aide de gcc est fournie par l’option suivante : >gcc --help 2.2.2 Avec l’environnement « Visual C++ 2008 Express Edition » La Figure 1 montre la fenêtre principale de l’environnement. Le programme est édité dans la zone de droite (onglet « bonjour.c »), et le compte-rendu de fabrication de l’exécutable est en bas (fenêtre « sortie »). Le fichier appartient à un projet appelé « bonjour » (en gras dans la fenêtre de gauche), qu’il faut créer avant par la commande « Fichier/Nouveau/Projet … ». Le bouton encerclé de rouge permet de « faire tourner » le programme jusqu’au point d’arrêt (avant return 0;), ou de faire l’exécution en « pas à pas ». Figure 1 : écran de l'environnement Visual C++ 2008 Express - 6 - 2.3 Calcul de factorielle Le programme suivant (re)demande à l’utilisateur un nombre entre 0 et 7 jusqu’à ce qu’il soit effectivement entre 0 et 7, puis affiche la factorielle du nombre saisi. #include <stdio.h> int main (){ char n; /*le type « char » est un 'petit' entier de 0 à 255*/ int i , fact = 1; /*initialisation possible lors de la déclaration*/ /*Lecture au clavier d’un décimal mis dans n (à son adresse)*/ printf("entrez 0<=n<=7 : "); scanf("%d",&n); /*While effectue le bloc {} tant que la condition entre () est vraie*/ while((n<=0)||(n>7)) { /*|| est le « ou » logique*/ if (n<=0) printf("0>n! "); else printf("n>7! "); printf("entrez 0<=n<=7 : "); scanf("%d",&n); } /*Pour i de 2 « i=2 » à n « i<=n » par pas de 1 « i++ »*/ for(i=2;i<=n;i++) fact*=i; /*fact*=i <=> fact=fact*i;*/ /*Le 1er %d affiche n en décimal, le 2ème fact. Ex : écrit 5!=120 si n=5.*/ printf("%d! = %d\n",n,fact); return 0; } Notions vues : char, déclaration de variable,=, initialisation, scanf, &variable, while, ||, condition, if, for,i++, *= Notions approfondies :printf avec format, %d - 7 - 2.4 Trier un tableau Le programme suivant trie et affiche un tableau de valeurs entières. /*Ce programme comporte plusieurs fonctions*/ #include <stdio.h> enum {MAX = 5}; /*MAX est une constante entière globale*/ int tab[MAX] = {3,10,-5,8,2 } ; /*le tableau tab[0..4] est global*/ /* prototype des fonctions : type rendu nom ( paramètres ) */ /* trie le tableau global tab de taille MAX (pas de paramètres) */ void trier(void); /*affiche le tableau t de taille éléments */ void afficher(int taille,int t[]); void main(void) { /* main a pour rôle d'appeler trier et afficher */ trier(); afficher(MAX,tab); } void trier(void) { int i, j, cle; for (i = 1; i < MAX; i++) { cle = tab[i]; for (j = i-1; (j >= 0) && (cle<tab[j]); j--) tab[j+1] = tab[j]; tab[j+1] = cle; } } void afficher(int taille,int t[]) { int i; printf("\nvoici le tableau trié\n"); for(i = 0; i < taille; i++) printf("%5d",t[i]); printf("\n"); } Notions vues : structure de programme, type énuméré, type tableau, initialisation de tableau, variable globale, prototype Notions approfondies : paramètres, for Fonctionnement : Passage de paramètres Exercices : • Ajouter une fonction permettant de lire les MAX entiers • Modifier le programme pour autoriser d’en lire moins que MAX - 8 - 2.5 Échanger deux variables Le programme échange deux valeurs réelles saisies au clavier. #include <stdio.h> void echanger(float * ad_f1, float * ad_f2) { /* ad_f1 est un pointeur uploads/Ingenierie_Lourd/ coursinformatique-id2748.pdf