CM04 tableau de structure

Télécharger le CM04 tableau de structure en pdf

Pages : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

Page 1 : Informatique IIPointeurs et tableaux de structures

Page 2 : Rappels• Les types de base int, float, char, etc... ne sont pas toujours suffisants pour modéliser des objets/ phénomènes de la réalité.• La construction de ces nouveaux types de variables peut être faite en combinanttous les types de base et les types déjà définis. Ce sont les structures.•Par exemple, on pourra avoir :Un type Date qui contiendra le jour, le mois, l’année, le jour de lasemaine et du mois en lettres.Un type Personne qui contiendra un nom, un prénom, une adresse,une date de naissance avec le type Date car on peut imbriquer lesstructures, un numéro de téléphone, etc…Un type Classe, qui contiendra un tableau de type Matière, un tableau de type Personne qui seront les élèves, un tableau de type Note, etc…Un type PaquetIP qui contiendra tous les champs d’une trame de donnéesdu protocole IP

Page 3 : Rappels• Les types de bases int, float ect. ne sont pas toujours suffisant pour modéliser des objets/ phénomènes de la réalité.• La construction de ces nouveaux types de variables peut être faite en combinanttous les types de base et les types déjà définis. Ce sont les structures.STRUCTURE Etudiantnom : chaîne de caractèresprenom : chaîne de caractèresnum : entiergroupe : entiernoteN : tableau de réélsFIN STRUCTUREChamps ou attributs ou membres de la structure EtudiantToujours une majuscule !

Page 4 : Rappels• Une fois définie, la structure peut être utilisée comme un type : c’est un type structuré.typedef struct float t abscisse;float t ordonnee; Point;Point constructeurPoint... // fonction retournant un Point…int mainPoint x; // declaration d’un Point xPoint y; //declaration d’un Point y…return 0; ;On peut aussi écrire:struct Point float abscisse;float ordonnee;;… struct Point x;typedef permet de redéfinir un type : plus besoin d’écrire "struct Point"Pour déclarer une variable

Page 5 : Rappels• On peut manipuler les différents champs d’une variable de type structuré avec le caractère '.' typedef struct float abscisse;float ordonnee; Point;Point constructeurPoint // fonction retournant un PointPoint z;scanf"f", &z.abscisse ;scanf"f" ,&z.ordonnee ;return z;int mainPoint x; // declaration d’un Point xPoint y; //declaration d’un Point yx.abscisse = 10;x.ordonnee = 2.5;y = constructeurPoint;return 0;

Page 6 : Structures et tableaux• Les tableaux permettent de gérer des données de même type avec une seule variable.• Les types structurés permettent d’avoir des champs différentes différents types dans une seule variable.Structure Etudiantnumetudiantadressechaînenomprénomnoteschaînechaînetableauentier

Page 7 : Structures et tableaux• Les tableaux permettent de gérer des données de même type avec une seule variable.• Les types structurés permettent d’avoir des champs différentes différents types dans une seule variable.notes0notes1notes2notes3…Les champs d’une structure ne prennent pas tous la même place en mémoireStructure Etudiantnumetudiantadressechaînenomprénomnoteschaînechaînetableauentier

Page 8 : Stockage d’une structure Adresse Valeur …11540000 000011550000 000011560000 000011570000 000111580000 000011590000 000011600001 000111611001 0100…x.abscissetypedef struct int abscisse;int ordonnee;Point;int mainPoint x;x.abscisse = 1;x.ordonnee = 4500;return 0;x.ordonneex

Page 9 : Stockage d’une structure Adresse Valeur …&x???&x+sizeofint???…x.abscissex.ordonnee

Page 10 : Stockage d’une structure • Les différents champs d’une structure sont à la suite dans la mémoire comme les éléments d’un tableau. Mais contrairement au tableau, il n’y a pas de pointeur qui pointe sur la première adresse de la structure.• L’accès aux différents champs de la structure se fait automatiquement: le compilateur connait le « saut de mémoire » à effectuer.• Une structure étant un type, on peut connaître sa place en mémoire avec la fonction sizeof.

Page 11 : Stockage d’une structure • Une structure étant un type, on peut connaître sa place en mémoire avec la fonction sizeof.

Page 12 : Stockage d’une structure • Une structure étant un type, on peut connaître sa place en mémoire avec la fonction sizeof.

Page 13 : Stockage d’une structure • Une structure étant un type, on peut connaître sa place en mémoire avec la fonction sizeof.Pourtant un char ne fait qu’un octet !

Page 14 : Stockage d’une structure • Une structure étant un type, on peut connaître sa place en mémoire avec la fonction sizeof.Le champs b prends 4 octets malgré le fait qu'il soit de type char !

Page 15 : Notion de mot et alignement• La mémoire est divisée en octets indiqués par des adresses mémoires.• La mémoire communique avec le processeur qui effectue les instructions.adresseinstructionadressevaleur à stockerRAMprocesseur

Page 16 : Notion de mot et alignement• La mémoire est divisée en octets indiqués par des adresses mémoires.• La mémoire communique avec le processeur qui effectue les instructions.• Le processeur ne travaille pas sur des octets mais sur des mots dont la taille varie selon son architecture : 32 bits, 64 bits, 128 bitsadresse 64 bitInstruction 64 bitsadresse 64 bitsvaleur à stocker 64 bitsRAMprocesseur

Page 17 : Notion de mot et alignement• Pour assurer la rétrocompatibilité des programmes, GCC travaille avec des mots de 32 bits 4 octets.• Illustration de la mémoire : 1055A3B6FFE58709125C8977452FBADB04816013numoctetadresse du mot 2mot

Page 18 : Notion de mot et alignement• Pour assurer la rétrocompatibilité des programmes, GCC travaille avec des mots de 32 bits 4 octets.• Illustration de la mémoire : 1055A3B6FFE58709125C8977452FBADB04816numoctetadresse du mot 0132motadresse de 12 ? = 8

Page 19 : Notion de mot et alignement• Pour assurer la rétrocompatibilité des programmes, GCC travaille avec des mots de 32 bits 4 octets.• Illustration de la mémoire : 1055A3B6FFE58709125C8977452FBADB04816numoctetadresse du mot motadresse de 87? = 6 0132

Page 20 : Notion de mot et alignement• Conséquence : un mot est toujours à une adresse multiple de 4.• Une variable ne doit pas être stockée sur deux mots différents:1055A3B6FFE58709125C8977452FBADB04816numoctetadresse du mot mot0132

Page 21 : Notion de mot et alignement• Conséquence : un mot est toujours à une adresse multiple de 4.• Une variable ne doit pas être stockée sur deux mots différents:• Rappel : un int est sur 4 octets: 1055A3B6FFE58709125C8977452FBADB04816numoctetadresse du mot motun int a la taille d’un mot 0132

Page 22 : Notion de mot et alignement• Conséquence : un mot est toujours à une adresse multiple de 4.• Une variable ne doit pas être stockée sur deux mots différents:• Rappel : un double est sur 8 octets: 1055A3B6FFE58709125C8977452FBADB04816numoctetadresse du mot motUn double a la taille dedeux mots0132

Page 23 : Notion de mot et alignement• Conséquence : un mot est toujours à une adresse multiple de 4.• Une variable ne doit pas être stockée sur deux mots différents:• Rappel : un char est sur 1 octets: 1055A3B6FFE58709125C8977452FBADB04816numoctetadresse du mot motUn char est compris dans un mot 0132

Page 24 : Notion de mot et alignement• Conséquence : un mot est toujours à une adresse multiple de 4.• Une variable ne doit pas être stockée sur deux mots différents:• Rappel : un int est sur 4 octets: 1055A3B6FFE58709125C8977452FBADB04816numoctetadresse du mot motUne même variable ne doit pas être à cheval sur deux mots !0132

Page 25 : Notion de mot et alignement1055A3B6FFE58709125C8977452FBADB04816numoctetadresse du mot mottypedef struct float abscisse;float ordonnee; Point;Point x;• Retour sur les structures :0132

Page 26 : Notion de mot et alignement1055A3B6FFE58709125C8977452FBADB04816124numoctetadresse du mot 3mot• Retour sur les structures :x.abscissetypedef struct float abscisse;float ordonnee; Point;Point x;

Page 27 : Notion de mot et alignement1055A3B6FFE58709125C8977452FBADB04816124numoctetadresse du mot 3mot• Retour sur les structures :x.abscissex.ordonneetypedef struct float abscisse;float ordonnee; Point;Point x;

Page 28 : Notion de mot et alignement1055A3B6FFE58709125C8977452FBADB04816124numoctetadresse du mot 3mottypedef struct int a;char b;int c; Test;Test x;• Retour sur les structures :

Page 29 : Notion de mot et alignement1055A3B6FFE58709125C8977452FBADB04816124numoctetadresse du mot 3mot• Retour sur les structures :x.atypedef struct int a;char b;int c; Test;Test x;

Page 30 : Notion de mot et alignement1055A3B6FFE58709125C8977452FBADB04816124numoctetadresse du mot 3mot• Retour sur les structures :x.ax.btypedef struct int a;char b;int c; Test;Test x;

Page 31 : Notion de mot et alignement1055A3B6FFE58709125C8977452FBADB04816124numoctetadresse du mot 3mot• Retour sur les structures :x.ax.bx.cx.c est sur deux mots différents!typedef struct int a;char b;int c; Test;Test x;

Page 32 : Notion de mot et alignement• Pour éviter le problème de champs d’une occurrence d’une structure qui peut être sur plusieurs mots différents, les compilateurs ajoutent du bourrage padding: des octets non utilisés.1055A3B6FFE58709125C8977452FBADB04816124adresse du mot 3mottypedef struct int a;char b;int c;Test;Test x;x.ax.bx.cbourrage

Page 33 : Notion de mot et alignement• Pour éviter le problème de champs d’une occurrence d’une structure qui peut être sur plusieurs mots différents, les compilateurs ajoutent du bourrage padding: des octets non utilisés.• Le compilateur sait combien d’octets de bourrage il doit rajouter car il est nécessaire que l’adresse mémoire d’un type de variable soit multiple de sa taille. Ex; l’adresse d’un int doit être un multiple de 4.• C’est la contrainte d’alignement. • Il est possible de connaître les contraintes d’alignement d’un type avec Alignof• Les valeurs d’alignement dépendent de la machine.

Page 34 : Notion de mot et alignement

Page 35 : Notion de mot et alignement• Autre exemple : taille de la structure suivante? aaaab/ccccdbourrageLa structure fait 13 octets

Page 36 : Notion de mot et alignement• Autre exemple : taille de la structure suivante? aaaab0b1b2/ccccbourrageLa structure fait 12 octets

Page 37 : Pointeur sur structure•Il est possible de définir un pointeur vers l’occurrence d’une structure: le pointeur aura donc le type de cette structure et indiquera l’adresse de la première case de l’occurrence.Typestructure nomPointeur;

Page 38 : Pointeur sur structure•Il est possible de définir un pointeur vers l’occurrence d’une structure: le pointeur aura donc le type de cette structure et indiquera l’adresse de la première case de l’occurrence.•ExempleTypestructure nomPointeur;typedef struct float abscisse;float ordonnee; Point;int mainPointx;Point px;px = &x;

Page 39 : Pointeur sur structure•ExempleAdresseValeur…11540000 000011550000 000011560000 000011570000 000111580000 000011590000 000011600001 000111611001 0100…20 0001154x.abscissex.ordonneexpxtypedef struct float abscisse;float ordonnee; Point;int mainPointx;Point px;px = &x;

Page 40 : Pointeur sur structure•Il est possible de définir un pointeur vers l’occurrence d’une structure: le pointeur aura donc le type de cette structure et indiquera l’adresse de la première case de l’occurrence.•Pour accéder aux différents champs :•On peut également écrire :Typestructure nomPointeur;nomPointeur.nomchampnomPointeur-nomchamp

Page 41 : Pointeur sur structure•Exempletypedef struct float abscisse;float ordonnee; Point;int mainPoint x;Point px;px = &x;x.abscisse = 5,5;px-ordonnee = 2;px-abscisse = px-abscisse + x.ordonnee;return 0;Adresse Valeur …11541155115611571158115911601161…20 0001154x.abscissex.ordonneexpx

Page 42 : typedef struct float abscisse;float ordonnee; Point;int mainPoint x;Point px;px = &x;x.abscisse = 5,5;px-ordonnee = 2;px-abscisse = px-abscisse + x.ordonnee;return 0;Pointeur sur structure•ExempleAdresse Valeur …11545,51155115611571158115911601161…20 0001154x.abscissex.ordonneexpx

Page 43 : typedef struct float abscisse;float ordonnee; Point;int mainPoint x;Point px;px = &x;x.abscisse = 5,5;px-ordonnee = 2;px-abscisse = px-abscisse + x.ordonnee;return 0;Pointeur sur structure•ExempleAdresse Valeur …11545,511551156115711582115911601161…20 0001154x.abscissex.ordonneexpx

Page 44 : Pointeur sur structure•ExempleAdresse Valeur …11547,511551156115711582115911601161…20 0001154x.abscissex.ordonneexpxtypedef struct float abscisse;float ordonnee; Point;int mainPoint x;Point px;px = &x;x.abscisse = 5,5;px-ordonnee = 2;px-abscisse = px-abscisse + x.ordonnee;return 0;

Page 45 : Tableaux statiques de structures•On peut définir des tableaux de structures :•Comme pour les tableaux classiques, les différents éléments ici des occurrences d’une structure seront à la suite dans la mémoire.•Un pointeur constant est créé et initialisé avec l'adresse de la première case du tableau. Ce pointeur pointe donc sur la première occurrence du type structuré.Typestructure nomTableautaille;

Page 46 : Pointeur sur structure•ExempleAdresse Valeur …1154……tabtest1154pxtabtest0tabtest1tabtest2typedef struct int a;char b;float c; Test;int main// tableau de 10 structures TestTest tabtest10; return 0;

Page 47 : Pointeur sur structure•ExempleAdresse Valeur …1154……tabtest1154pxtabtest0tabtest1tabtest2Question :Comment accéder au champ b du 3 ème élément du tableau?tabtest2.bEn format pointeur ? tabtest+2.b tabtest+2-btypedef struct int a;char b;float c; Test;int main// tableau de 10 structures TestTest tabtest10; return 0;

Page 48 : Pointeur sur structure•ExempleAdresse Valeur …1154……tabtest1154pxtabtest0tabtest1tabtest2Question :De combien d'octets se déplace-t-on en mémoire lorsque l’on fait tabtest+4 ?On se déplace de 4sizeofTest, soit de 412=48 octets. typedef struct int a;char b;float c; Test;int main// tableau de 10 structures TestTest tabtest10; return 0;

Page 49 : Tableaux statiques de structures•On peut définir des tableaux de structures :•Comme pour les tableaux classiques, les différents éléments ici des occurrences d’une structure seront à la suite dans la mémoire.•Un pointeur constant est créé et initialisé avec l'adresse de la première case du tableau. Ce pointeur pointe donc sur la première occurrence du type structuré.•Pour accéder aux différents champs :Typestructure nomTableautaille;nomTableauind.nomchampnomtableau+ind.nomchampnomtableau+ind-nomchamp

Page 50 : Tableaux dynamiques de structures•Pour allouer en mémoire un tableau de structures il faut connaître la taille totale de ce tableau. Il faut donc connaître:•1. Le nombre d’elements à stocker•2. La taille de la structure•Les commandes pour allour dynamiquement un tableau de structure est donc : •Le tableau peut ensuite être utilisé comme un tableau statique•Toujours vérifier que l’allocation mémoire a bien eu lieu.•Ne pas oublier de libérer free l’espace mémoire alloué !Typestructure tab = NULL;int nbelements = 7;tab = malloc nbelements sizeofTypestructure ;

Page 51 : Tableaux dynamiques de structure•Exempleincludestdio.hincludestdlib.htypedef structchar nom50;char prenom50;int num;int groupe;int note10; Etudiant;int mainint nbetu, i;Etudiant tabetu = NULL;printf"Nb étudiants dans la classe?\n";scanf"d", &nbetu;tabetu = malloc nbetusizeofEtudiant ;iftabetu == NULLprintf"Problème allocation mémoire! \n ";exit 1;printf"Quel est le nom du : \n";for i=0; inbetu; i++printf" d ieme eleve?\n", i+1;scanf"s", tabetui.nom;return 0;Comment modifier la 4eme note du 5eme étudiant?tabetu4.note3 tabetu+4-note3 tabetu+4-note+3

Page 52 : Recherche et parcours d’un tableau de structures•La recherche dans un tableau de structure se fait généralement en recherchant des valeurs de champs ex: quels étudiants sont dans le groupe 4?.•Si l’on souhaite faire des opérations sur les éléments recherchés, il existe plusieurs approches :•1. On sauvegarde chaque occurrences recherchées puis on leur applique des opérations•2. On effectue des opérations sur les occurrences recherchées à mesure que l’on parcours le tableau

Page 53 : Recherche et parcours d’un tableau de structures•La recherche et le traitement de donnée se bases donc sur ces deux principe. On va choisir la méthode selon notre priorité:•1.On parcours une fois le tableau et on sauvegarde les occurrences recherchée. - Un seul parcours = rapidité- sauvegarde de donnée = utilisation d’espaceOn peut optimiser le parcours et l’espace utilisé en travaillant sur un tableau trié, mais le tri prend beaucoup de temps !•2. On parcourt une fois l'ensemble des données pour chaque information à récupérer. Celles‐ci n'ont donc pas besoin d'être retenues, mais le temps d'exécution peut être beaucoup plus long.-pas de sauvegarde : minimum d’espace utilisé- plusieurs parcours : algorithme lent

Page 54 : Recherche et parcours d’un tableau de structures•Exemple:On stocke dans une structure les chiffres d’affaires de commerciaux d’une entreprise.STRUCTURE Commercial nom : chaine de caractèreregion : Entier// 0=Est ; 1=Nord ; 2=Ouest ; 3=Sud ca : Entier// chiffre d’affairesFIN STRUCTURETcom : Tableau de taille n de Commercial•Objectif: afficher le chiffre d’affaire par région.

Page 55 : Recherche et parcours d’un tableau de structures•Exemple:IndiceNomRégionChiffre d’Affaires0NéoNord5001YodaSud25002CobbEst10003RipleyOuest40004McFlyNord9005SpockSud6006LilouEst20007AtréideOuest15008NeytiriNord30009ConnorSud800CA de la région Est: 3000CA de la région Nord: 4400CA de la région Ouest : 5500CA de la région Sud: 3900

Page 56 : Recherche et parcours d’un tableau de structures•Algorithme 1:•On trie au préalable le tableau selon le champs recherchée ici la région•On parcourt le tableau et on affiche le résultat à chaque changement de région.•Avantage: 1 seul parcours, pas d’espace mémoire supplémentaire•Inconvénient : il faut trier le tableau•Complexite : On+nlognPROCEDURE ALGO1Tcom: tableau de taille n de CommercialVARIABLEsomme, reg, i: ENTIERDEBUTTriTcom, region // On trie le tableau avant par rapport à la régionsomme - Tcom0.ca // On initialise la somme et la région à la valeur de la 1ere casereg - Tcom0.region //1 ere regionPOUR i DE 1 A N FAIRESI Tcomi.region = reg ALORSsomme - somme + Tcomi.caSINON// Changement de région on affiche la précédenteECRIRE "CA de la Région" + reg + " : " +sommesomme - Tcomi.ca // On réinitialise la somme et la régionreg - Tcomi.regionFIN SIFIN POURECRIRE "CA de la Région" + reg + " : " +somme// pour la dernière régionFIN

Page 57 : Recherche et parcours d’un tableau de structures•Algorithme 2:•On fait un parcours du tableau par régions•Avantage: pas d’espace mémoire supplémentaire•Inconvénient : Temps dépendant du nombre de région.•Complexité : OnNBREGION PROCEDURE ALGO2Tcom: tableau de taille n de CommercialVARIABLEsomme, reg, i: ENTIERDEBUTPOUR reg DE 0 A NBREGION FAIRE// parcours d’une régionsomme - 0POUR i DE 0 A n FAIRE // parcours du tableau entierSI Tcomi.region = reg ALORS // somme si c’est la bonne régionsomme - somme + Tcomi.caFIN SIFIN POURECRIRE "CA de la Région" + reg + " : " +sommeFIN POURFIN

Page 58 : Recherche et parcours d’un tableau de structures•Algorithme 3:•Un compromis: on sauvegarde les différentes sommes dans un tableau - un seul parcours.•Avantage: Un seul parcours de tableau•Inconvénient : 1 tableau supplémentaire •Complexité : On+2NBREGION PROCEDURE ALGO3Tcom: tableau de taille n de CommercialVARIABLEreg, i: ENTIERsomme : tableau de taille NBREGION d’ENTIERDEBUTPOUR i DE 0 A NBREGION FAIRE// initialiser le tableau resultatsommei-0-0FIN POURPOUR i DE 0 A n FAIRE E // parcours du tableau entiersommeTcomi.region = sommeTcomi.region + Tcomi.caFIN POURPOUR i DE 0 A NBREGION FAIRE// Affichage des resultatsECRIRE "CA de la Région" + i + " : " +sommeiFIN POURFIN

Page 59 : Conclusion et résumé • Les structures permettent de créer de nouveaux types en combinant des types existants.• Les différents champs d’une structure sont à la suite dans la mémoire. Le compilateur peut ajouter du bourrage dans la mémoire afin de conserver un alignement correct en mémoire. Un ordre des champs défini par l'utilisateur avec la connaissance de l'alignement mémoire permet de gagner de l'espace mémoire.• On peut créer des pointeurs sur structures: l’accès aux différents champs se faite avec l’opérateur -• La gestion d’un tableau de structures se fait de la même façon que pour les tableaux de types classiques. L'arithmétique des pointeurs est la même.• Les opérations de recherches et d’opérations sur ces tableaux nécessitent de trouver un compromis entre rapidité et espace mémoire selon la situation mais ce compromis existe dans tous les aspects du développement logiciel.

Pages : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59