Chapitre 5 : Structures et tableaux des structures A) Le type structure : 1) Domaines d'utilisation : Le type structure se trouve dans les structures de données suivantes : - tableau de structures - liste linéaire chaînée, arbre binaire - fichier non texte - classe (programmation orientée objet) - etc ... 2) Introduction : Le type structure (struct) en C est semblable au type enregistrement (record) dans le langage PASCAL (cours IFT 1140). C'est une collection des champs qui peuvent être de types différents. Exemple : Une personne est une structure avec les champs possibles suivants : - nom et prénom : chaîne de caractères - taille et poids : réels - âge : entier - sexe : caractère - etc ... Grâce à ce type, on peut réduire le nombre de tableaux à traiter dans un programme : Pour la gestion des notes du cours IFT 1160 : 1. Avec les tableaux à un seul indice, on a besoin des tableaux suivants : nomPre : tableau des chaînes de caractères numero : tableau des entiers (numéros d'inscription) intra, final, tp1, tp2, tp3, tps, globale : 7 tableaux des réels code : tableau des chaînes de caractères ("A+", "C-",...) Au total, on a 10 tableaux à déclarer, à écrire sur les en-têtes des fonctions et des appels. De plus, quand on fait l'échange dans le tri, il faut utiliser 3 affectations par tableau. Avec ces 10 tableaux, ces échanges nécessitent 10 x 3 = 30 affectations. C'est long à écrire. 2. Avec les tableaux à deux indices, on peut réduire sensiblement le nombre de tableaux à traiter : nomPre : tableau des chaînes de caractères numero : tableau des entiers (numéros d'inscription) note : un seul tableau à 2 indices code : tableau des chaînes de caractères ("A+", "C-",...) Au total, on a 4 tableaux à déclarer, à manipuler sur les en-têtes des fonctions et des appels. Pour le tri, on a besoin de 12 (4 x 3) affectations afin d'échanger les informations. 3. Avec le type structure, il est possible d'utiliser un seul tableau : tableau des étudiants, chaque élément de ce tableau est une variable de type structure. On a ainsi un seul tableau à déclarer et à manipuler. Plus tard dans le cours, on utilisera le type "struct" dans les listes linéaires chaînées, les arbres binaires, les fichiers non textes, ... 3) Déclaration et terminologie : Supposons qu'on désire déclarer deux variables pers1 et pers2 de type structure et que chaque personne dispose de quatre informations : - numéro : un entier - taille et poids : deux réels - sexe : un caractère. a) Façon 1 : déclaration directe sans le nom du type structure. struct { int numero ; float taille, poids ; char sexe ; } pers1, pers2 ; Le désavantage de cette manière de faire est qu'il n'est pas flexible pour la déclaration de nouvelles variables de même type structure que nous aimerions utiliser ailleurs dans un même programme. Schéma d'une structure : b) Façon 2: déclaration avec le nom du type structure. b.1) on déclare d'abord le type : struct personne { int numero ; float taille, poids ; char sexe ; } ; b.2) on déclare après les variables : struct personne pers1, pers2 ; Si on veut déclarer d'autres informations de ce type, il suffit de se référer au type "struct personne" : Exemples : 1) void Afficher ( struct personne unePers ) /* afficher les informations d' "unePers" qui est de type struct personne */ 2) struct personne tempo ; /* une autre variable de même type */ etc ... c) Façon 3: déclarer en même temps le type et les variables: struct personne { int numero ; float taille, poids ; char sexe ; } pers1, pers2 ; d) Façon 4: déclarer en utilisant "typedef" : typedef struct { int numero ; float taille, poids ; char sexe ; } Personne ; /* personne est le nom du type */ Personne pers1, pers2 ; Remarques : 1. Pour le cours IFT 1160, on vous suggère fortement d'utiliser la 4 ième façon. 2. Avec la déclaration selon la 4 ième façon : a) Personne est le nom du type structure qui dispose de 4 champs d'information. b) numero est le nom d'un champ de type entier. taille et poids sont deux champs de type réels. sexe est un champ de type caractère. c) pers1 et pers2 sont deux variables de type structure dont le nom est Personne. 3. Le C++ permet de simplifier les déclarations : struct Personne { int numero ; float taille, poids ; char sexe ; }; Personne pers1, pers2 ; Exemple : Écrire les déclarations d'une variable "unEtud" de type "Etudiant" pour la gestion de ses notes. Solution : #define LONG_NP 30 /* 30 caractères pour le nom et le prénom */ #define NB_NOTES 7 /* 7 notes */ #define LONG_CODE 2 /* 2 caractères pour le code littéral "B+" ...*/ typedef struct { char nomPre [LONG_NP +1] ; int numIns ; float note[NB_NOTES] ; char code[LONG_CODE+1] ; } Etudiant ; Etudiant unEtud ; Exercice : Écrire les déclarations d'une variable "unEmp" de type "Employe" qui comporte les champs d'informations suivantes : - nom et prénom - numéro d'employé - numéro d'assurance sociale - âge - salaire hebdomadaire - poste de travail (parmi les postes : analyste, programmeur, opérateur, secrétaire) 4) Manipulation du type structure : 4.1) Accès à un champ d'une structure : Comme en langage PASCAL, le C utilise aussi le point "." pour accéder à un champ d'une variable de type structure : variable_de_type_structure . champ Exemples : 1. Écrire les instructions pour donner à la "pers1" les informations suivantes : C'est un homme qui mesure 1.67 mètre et pèse 67.8 kgs. Son numéro d'identification est le 7234. pers1.numero = 7234 ; pers1.sexe = 'M' ; pers1.taille = 1.67 ; pers1.poids = 67.8 ; 2. Écrire les instructions pour afficher les informations de "pers1" à l'écran : printf("Son numéro : %6d\n", pers1.numero); printf("Son sexe : %6c\n", pers1.sexe); printf("Son poids : %6.2f kgs\n", pers1.poids); printf("Sa taille : %6.2f m\n", pers1.taille); Cas spécial : Pointeur vers le type structure : Avec la déclaration : Personne * P ; P est un pointeur vers le type Personne. *P est une variable de type Personne. On peut accéder à n'importe quel champ de *P : (*P).taille, (*P).poids, etc .... Le C permet de simplifier l'écriture en utilisant l'opérateur -> (*P).champ <======> P->champ 4.2) Affectation entre deux variables de type structure : Avec Personne pers1, pers2 ; on peut affecter l'une à l'autre : pers1 = pers2 ; /* pers1 contiendra toutes les informations de pers2. */ Exemple : Écrire une fonction permettant d'échanger les informations de deux personnes (de type Personne) : Solution : void echanger ( Personne * P1, Personne * P2) { Personne Temporaire ; temporaire = *P1 ; *P1 = *P2 ; *P2 = temporaire ; } 4.3) Comparaison entre deux variables de type structure : La comparaison directe de deux informations de type structure if ( pers1 == pers2 ) printf("C'est pareil") ; n'est pas permise. Cependant, le C permet de comparer octet par octet (comparaison en mémoire) : #include <mem.h> /* pour memcmp : memory comparison */ ....... if ( memcmp(&pers1, &pers2, sizeof(Personne)) == 0) printf("Elles sont identiques\n"); else printf("Elles sont différentes\n"); Exemple : Écrire une fonction permettant d'afficher l'heure courante sous la forme, exemple : 18:25:17:78 Solution : #include <dos.h> /* pour la fonction gettime(...) dans la fonction afficherHeure */ .... void afficherHeure () { /* struct time est un type "structure" prédéfinie dans le fichier d'en-tête <dos.h> struct time { unsigned char ti_min ; unsigned char ti_hour; unsigned char ti_hund; unsigned char ti_sec ; } où unsigned char : entier de 0 à 255 ti_min : minute, ti_hour : heure, ti_hund : pourcent seconde, ti_sec : seconde. */ struct time Temps ; gettime(&Temps); printf("%2d:%2d:%2d:%2d\n", Temps.ti_hour, Temps.ti_min, Temps.ti_sec, Temps.ti_hund); } Exercices : Exercice 1 : Écrire un programme permettant de : - saisir les informations d'une personne (type Personne) en utilisant une fonction dont l'argument est transmis par pointeur : void saisir ( Personne * P ) - appeler la fonction "saisir" 2 fois pour obtenir les informations de deux personnes différentes ; - afficher les informations de ces deux personnes avec une fonction du genre : void afficher ( Personne unePers ) - échanger (permuter) les informations de ces deux personnes en utilisant une fonction ; - réafficher de nouveau les informations de ces deux personnes après l'échange. Notes : La lecture suivante est parfaitement valide : void saisir ( Personne * P ) { ...... printf("Entrez la taille "); scanf("%f", &(P->taille)); ...... } Le compilateur TURBO C réagit souvent mal à la lecture d'un réel avec l'opérateur ->. Si c'est le cas, il suffit de contourner le problème comme suit : float t ; ...... printf("Entrez la taille "); scanf("%f", &t) ; P->taille = t ; /* c'est la même chose */ ...... Exercice 2 : Écrire un programme en mode interactif permettant de gérer les notes d'un seul étudiant (type structure) du cours IFT 1160. Les champs prévus sont : nomPre : une chaîne de 30 caractères numIns : un entier note : un tableau de 7 notes code : le code littéral "A-", "B+", ... B) Tableau de structures : 1) Domaines d'utilisation : Supposons qu'on a besoin de manipuler les informations "structurées" (des personnes, des étudiants, des employés, etc ...) dont les traitements prévus sont : - le tri, la recherche d'un élément - l'affichage - les statistiques - la création de nouveaux fichiers Si le nombre de données est raisonnable (exemple : 500 à 600 personnes à traiter, 400 étudiants à calculer les notes , etc ... ), on peut utiliser un tableau des structures. 2) Déclaration : Écrire les déclarations d'un tableau de personnes. Chaque élément du tableau est de type structure nommé "personne" qui comporte les champs suivants : sexe : 1 seul caractère taille et poids : 2 réels On a 100 personnes ou moins à traiter. Solution : #define MAX_PERS 100 typedef struct { char sexe ; float taille, poids ; } Personne ; Personne pers[MAX_PERS] ; int nbPers ; /* le nombre effectif de personnes*/ 3) Schéma d'un tableau des structures : 4) Compréhension de base : Avec ces déclarations : 1) pers est un tableau des personnes ; 2) pers[0], pers[1], ..., pers[99] sont 100 éléments du tableau pers. Chacun est une variable de type structure nommé "Personne" ; 3) pers[15].sexe est le sexe de la 16 ième personne ; 4) La déclaration : Personne * P ; rend valide l'affectation suivante : P = pers ; Cette affectation est équivalente à : P = &pers[0] ; De plus, *(P + i) est équivalent à pers. Ainsi : *(P + i). taille est pers.taille Donc, (P + i) -> taille est pers.taille 5) Exemples sur les tableaux des structures : Exemple 1 : On dispose du fichier texte "Metrique.Dta" : ROY CHANTAL F 1.63 54.88 MOLAISON CLAUDE M 1.57 56.25 BEDARD MARC-ANDRE M 1.43 42.50 etc .... Écrire un programme en C permettant de lire le fichier et de : 1. créer un tableau de personnes 2. afficher la liste des 10 premières personnes 3. compter et afficher le nombre de personnes dont : - la taille dépasse 1.80 mètre - le poids dépasse 56.78 kgs Solution : /* Fichier Struct1.A95: exemple sur le type "struct" en C */ #include <stdio.h> #include <string.h> #define MAX_PERS 25 #define LONG_NP 30 typedef struct { char nomPre[LONG_NP+1] ; char sexe ; float taille, poids ; } Personne ; Personne pers[MAX_PERS] ; int nbPers ; void continuer() { printf("Appuyez sur Entrée "); fflush(stdin); getchar(); } void lireCreer (Personne pers[], int * P) { FILE * donnees ; int n = 0 ; float t, p ; donnees = fopen("Metrique.Dta", "r"); while (!feof(donnees)) { /* On lit 30 caractères pour un nom et prénom et on fait déposer le caractère '\0' à la fin */ fgets(pers[N].nomPre, LONG_NP+1, donnees); fscanf(donnees,"%c%f%f\n", &pers[N].sexe, &t, &p); pers[n].taille = t ; pers[n].poids = p ; n++; } fclose(donnees); *P = n ; } int nombre (Personne pers[], int nbPers, int code, float borne) { int k = 0 , i ; for (i = 0 ; i < nbPers ; i++) if ( (code == 1 && pers.taille > borne) || (code == 2 && pers.poids > borne) ) k++; return k ; } /* démonstration du pointeur vers le type structure */ void Afficher ( Personne * P, int nombre ) { int i ; printf("Liste des %d premières personnes :\n\n", nombre); for (i = 0 ; i < nombre ; i++) printf("%3d) %s %6.2f m %8.1f kgs %s\n", i+1, (P+i)->nomPre, (P+i)->taille, (P+i)->poids, (P+i)->sexe == 'F' ? "Féminin" : "Masculin"); Continuer(); } void main() { lireCreer (Pers, &nbPers); afficher(Pers, nbPers); printf("\n\n"); printf("Le nombre de personnes dont la taille dépasse" " 1.80 mètre :%3d\n", nombre(Pers, nbPers, 1, 1.80)); printf("Le nombre de personnes dont le poids dépasse" " 56.78 kgs :%3d\n", nombre(Pers, nbPers, 2, 56.78)); continuer(); } Exécution : Liste des 10 premières personnes : 1) ROY CHANTAL 1.63 m 54.9 kgs Féminin 2) MOLAISON CLAUDE 1.57 m 56.2 kgs Masculin 3) BEDARD MARC-ANDRE 1.43 m 42.5 kgs Masculin 4) MONAST STEPHANE 1.65 m 61.7 kgs Masculin 5) JALBERT LYNE 1.63 m 47.6 kgs Féminin 6) DUBE FRANCOISE 1.63 m 53.5 kgs Féminin 7) LABELLE LISE 1.73 m 63.0 kgs Féminin 8) RIVERIN HELENE 1.70 m 60.8 kgs Féminin 9) MICHAUD NORMAND 1.73 m 71.7 kgs Masculin 10) RICHER AGATHE 1.65 m 53.1 kgs Féminin Appuyez sur Entrée Le nombre de personnes dont la taille dépasse 1.80 mètre : 1 Le nombre de personnes dont le poids dépasse 56.78 kgs : 10 Appuyez sur Entrée Exemple 2 : Adapter le programme de l'exemple 1 afin qu'il permette aussi de 1. trier le tableau selon le nom et prénom 2. afficher la liste des 10 premières personnes avant et après le tri 3. chercher et afficher les informations d'une personne 4. créer un fichier texte nommé "Hommes.Gra" qui contient les informations des hommes dont la taille dépasse 1.75 mètre. Solution : /* Fichier Struct2.A95: Suite de Struct1.A95 */ #include <stdio.h> #include <ctype.h> #include <string.h> #define MAX_PERS 25 #define LONG_NP 30 typedef struct { char nomPre[LONG_NP+1] ; char sexe ; float taille, poids ; } Personne ; Personne pers[MAX_PERS] ; int nbPers ; void continuer() { printf("\n\nAppuyez sur Entrée "); fflush(stdin); getchar(); } void lireCreer (Personne pers[], int * P) { FILE * donnees ; int n = 0 ; float taille, poids; donnees = fopen("Metrique.Dta", "r"); while (!feof(donnees)) { fgets(Pers[n].nomPre, LONG_NP+1, donnees); fscanf(donnees,"%c%f%f\n", &Pers[n].sexe, &taille, &poids); pers[n].taille = taille ; pers[n].poids = poids ; n++; } fclose(donnees); *P = n ; } void afficher ( Personne * P, int nombre, char * quand ) /* note : (*P).champ <===> P->champ */ { int i ; printf("Liste des %d premières personnes %s le tri:\n\n", nombre, quand); for (i = 0 ; i < nombre ; i++) printf("%3d) %s %6.2f m %8.1f kgs %s\n", i+1, (P+i)->nomPre, (P+i)->taille, (P+i)->poids, (P+i)->sexe == 'F' ? "Féminin" : "Masculin"); continuer(); } /* Tri par sélection */ void Trier (Personne pers[], int nbPers) { int i, j, indMin ; /* pour le tri par sélection */ Personne tempo ; /* pour échanger 2 personnes */ for (i = 0 ; i < nbPers-1 ; i++) { indMin = i ; /* par défaut */ for ( j = i+1 ; j < nbPers ; j++ ) if ( strcmp(pers[j].nomPre , pers[indMin].nomPre) < 0 ) indMin = j ; if (indMin != i) { /* faire des échanges*/ tempo = pers ; pers = pers[indMin]; pers[indMin] = tempo ; } /* fin de if (commentaire pédagogique) */ } /* fin de for (commentaire pédagogique) */ } void creer(Personne pers[], int nbPers, char sexeVoulu, float borne, char * nomFichier) { FILE * aCreer = fopen(nomFichier, "w" ) ; /* w => for writing */ for (int i = 0 ; /* cas spécial de C++, déclaration "flexible" */ i < nbPers ; i++) if (pers.sexe == sexeVoulu && pers. taille > borne) fprintf(aCreer,"%s %c %6.2f %7.1f\n", pers.nomPre, pers.sexe, pers.taille, pers.poids); fclose(aCreer); } /* Recherche dichotomique dans un tableau trié */ void Chercher(Personne pers[], int nbPers) { char aChercher[LONG_NP+1] ; int mini, maxi, milieu, trouve ; int compare, longueur ; #define VRAI 1 #define FAUX 0 do { printf("RECHERCHE DICHOTOMIQUE\n"); printf("Quelques noms existants :\n"); printf("Dube Francoise, Labelle Lise, ... "); printf("\n\nEntrez le nom et prénom de la " "personne recherchée "); gets(aChercher); /* get string = lire une chaîne */ longueur = strlen(aChercher) ; mini = 0 ; maxi = nbPers - 1 ; trouve = FAUX ; /* on ne trouve pas encore */ while (!trouve && mini <= maxi) { milieu = (mini + maxi) / 2 ; compare = strnicmp(aChercher, pers[milieu].nomPre, longueur); if ( compare < 0 ) maxi = milieu - 1 ; else if (compare > 0) mini = milieu + 1 ; else trouve = VRAI ; } if (!trouve) printf("Désolé, on ne trouve pas %s\n", aChercher); else { printf("Yahou!, voici ses informations :\n\n"); printf("Nom et prénom : %s\n", pers[milieu].nomPre); printf("taille : %6.2f mètre\n", pers[milieu].taille); printf("poids : %6.2f kgs \n", pers[milieu].poids); printf("sexe : %s\n", pers[milieu].sexe == 'F' ? "Féminin": "Masculin"); } printf("\n\n"); printf("Avez-vous une autre personne à traiter ? (O/N) "); fflush(stdin); } while (toupper(getchar()) == 'O'); } void main() { lireCreer (pers, &nbPers); afficher(pers, 10, "avant"); trier (pers, nbPers) ; afficher(pers, 10, "après"); chercher(pers, nbPers); /* Créer un fichier texte nommé "Hommes.Gra" qui ne contient que les informations des hommes dont la taille est supérieure à 1.75 mètre */ creer(Pers, nbPers, 'M', 1.75, "Hommes.Gra"); printf("\n\nFin de la création du nouveau fichier Hommes.Gra\n"); continuer(); } Exécution : Liste des 10 premières personnes avant le tri: 1) ROY CHANTAL 1.63 m 54.9 kgs Féminin 2) MOLAISON CLAUDE 1.57 m 56.2 kgs Masculin 3) BEDARD MARC-ANDRE 1.43 m 42.5 kgs Masculin 4) MONAST STEPHANE 1.65 m 61.7 kgs Masculin 5) JALBERT LYNE 1.63 m 47.6 kgs Féminin 6) DUBE FRANCOISE 1.63 m 53.5 kgs Féminin 7) LABELLE LISE 1.73 m 63.0 kgs Féminin 8) RIVERIN HELENE 1.70 m 60.8 kgs Féminin 9) MICHAUD NORMAND 1.73 m 71.7 kgs Masculin 10) RICHER AGATHE 1.65 m 53.1 kgs Féminin Appuyez sur Entrée Liste des 10 premières personnes après le tri: 1) BEDARD MARC-ANDRE 1.43 m 42.5 kgs Masculin 2) BEGIN MARIE-LUCE 1.60 m 49.0 kgs Féminin 3) DESMARAIS DENISE 1.75 m 64.0 kgs Féminin 4) DUBE FRANCOISE 1.63 m 53.5 kgs Féminin 5) DUMITRU PIERRE 1.80 m 79.4 kgs Masculin 6) FILLION ERIC 1.78 m 75.8 kgs Masculin 7) JALBERT LYNE 1.63 m 47.6 kgs Féminin 8) LABELLE LISE 1.73 m 63.0 kgs Féminin 9) MICHAUD NORMAND 1.73 m 71.7 kgs Masculin 10) MOLAISON CLAUDE 1.57 m 56.2 kgs Masculin Appuyez sur Entrée RECHERCHE DICHOTOMIQUE Quelques noms existants : Dube Francoise, Labelle Lise, Michaud Normand ... Entrez le nom et prénom de la personne recherchée dube francoise Yahou!, voici ses informations : nom et prénom : DUBE FRANCOISE taille : 1.63 mètre poids : 53.52 kgs sexe : Féminin Avez-vous une autre personne à traiter ? (O/N) o RECHERCHE DICHOTOMIQUE Quelques noms existants : Dube Francoise, Labelle Lise, Michaud Normand ... Entrez le nom et prénom de la personne recherchée ali baba Désolé, on ne trouve pas ali baba Avez-vous une autre personne à traiter ? (O/N) N Fin de la création du nouveau fichier Hommes.Gra Appuyez sur Entrée Contenu du fichier "Hommes.Gra" : DUMITRU PIERRE M 1.80 79.4 FILLION ERIC M 1.78 75.8 TREMBLAY SYLVAIN M 1.83 86.2
