CM03 tableaux dynamiques

Télécharger le CM03 tableaux dynamiques 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

Page 1 : Informatique IIPointeurs et tableaux dynamiques

Page 2 : Rappel•Les valeurs d’un tableau sont à la suite dans la mémoire.•Lorsqu’un tableau est déclaré:•Un espace mémoire de la bonne taille est réservé•Un pointeur constant lecture seule portant le nom du tableau est créé. Il pointe sur la première case du tableau.Adresse Valeur 115413000…………22 2221154tab0tab1tab2tab3tab4tab

Page 3 : Un petit test •Que devrait afficher le code suivant ?// Programme d'exemple int mainint tab10=0; // déclaration du tableau printf"&tab0 =p \n", &tab0;printf"&tab1 =p \n", &tab1;printf"&tab2 =p \n", &tab2; return 0;

Page 4 : Un petit test •Que devrait afficher le code suivant ?// Programme d'exemple int mainint tab10=0; // déclaration du tableau printf"&tab0 =p \n", &tab0;printf"&tab1 =p \n", &tab1;printf"&tab2 =p \n", &tab2; return 0;4 numéros d’adresse d’écart entre chaque case !

Page 5 : Un petit test •Que devrait afficher le code suivant ?// Programme d'exemple int mainchar tab10=0; // déclaration du tableau printf"&tab0 =p \n", &tab0;printf"&tab1 =p \n", &tab1;printf"&tab2 =p \n", &tab2;return 0;1 numéro d’adresse d’écart entre chaque case !

Page 6 : Un petit test •Que devrait afficher le code suivant ?// Programme d'exemple int maindouble tab10=0; // déclaration du tableau printf"&tab0 =p \n", &tab0;printf"&tab1 =p \n", &tab1;printf"&tab2 =p \n", &tab2;return 0;8 numéros d’adresse d’écart entre chaque case !

Page 7 : Stockage des variable •Une variable peut – être stockée sur plusieurs cases mémoire selon son type.•Une adresse mémoire contient 1 octet. Type Taille octetchar1short entier2int/ float4long/double8……•Rmq: ces valeurs sont valables pour des processeur 64 bits. En fonction de la cible certaines de ces valeurs peuvent varier.

Page 8 : Stockage des variable •Une variable peut – être stockée sur plusieurs cases mémoire selon son type.•Une adresse mémoire contient 1 octet. Type Taille octetchar1short entier2int/ float4long/double8……•La fonction sizeof donne le nombre d’octet sdu type passé en argument:Exemple : sizeofint retourne 4

Page 9 : Stockage des variable •Une variable peut – être stockée sur plusieurs cases mémoire selon son type.•Une adresse mémoire contient 1 octet. inta = 1000;char b = ‘b’; //98

Page 10 : Stockage des variable •Une variable peut – être stockée sur plusieurs cases mémoire selon son type.•Une adresse mémoire contient 1 octet. inta = 1000;char b = ‘b’; //98AdresseValeur11540000 000011550000 000011560000 001111571110 1000…10 0280110 0010ab

Page 11 : Stockage des variable •Un tableau en mémoire:int tab5=1,2,3,4,5;Adresse Valeur 11540000 000011550000 000011560000 000011570000 000111580000 000011590000 000011600000 000011610000 001011620000 000011630000 000011640000 000011650000 0011….….tab0tab1tab2

Page 12 : Stockage des variable •Un tableau en mémoire:int tab5=1,2,3,4,5;Adresse Valeur 11540000 000011550000 000011560000 000011570000 000111580000 000011590000 000011600000 000011610000 001011620000 000011630000 000011640000 000011650000 0011….….tab1554tab0tab1tab2

Page 13 : Gestion des pointeurs•Nous avons vu que:tabi = tab+iAdresse Valeur 11540000 000011550000 000011560000 000011570000 000111580000 000011590000 000011600000 000011610000 001011620000 000011630000 000011640000 000011650000 0011….….tab1554tab0tab1tab2•&tab0+1 = tab+1 ici 1155 n’est pas l’adresse de tab1 !!!•Il y a une opération cachée derrière l'arithmétique des pointeurs

Page 14 : Arithmétique du pointeur•Un pointeur n’indique pas simplement une adresse mais un espace mémoire. •Le type donné au pointeur indique la taille de l’espace sur lequel il pointe.•Exemple :Adresse Valeur 1154…………10 028…15 000…22 222inta;charb;intp1; // pointeur sur intcharp2; // pointeur sur chara= 5;p1 = &a;// prend l'adresse de ab= A;//65p2 = &b;// prend l'adresse de b

Page 15 : Arithmétique du pointeur•Les pointeurs sont des variables entières adresses mémoire.•On peut donc lui appliquer un certain nombre d’opérateurs arithmétiques classiques: 1. l’addition + d’un entier à un pointeur. Le résultat estun pointeur de même type que lepointeur de départ.2. la soustraction - d’un entier à un pointeur. Le résultatest un pointeur de même type que le pointeur dedépart.3. la différence - de deux pointeurs pointant tous deuxvers des données de même type. Le résultat est un entier.4. Les opérateurs de comparaison.

Page 16 : Arithmétique du pointeur : additionSi i est un entier et p est un pointeur sur un objet de type type, l’expression p+i désigne un pointeur de valeur:p + i = p + i sizeoftype •Le décalage du bon nombre d’adresses mémoire se fait automatiquement.

Page 17 : Arithmétique du pointeur : additionSi i est un entier et p est un pointeur sur un objet de type type, l’expression p+i désigne un pointeur de valeur:p + i = p + i sizeoftype Exemple inta = 1;int p = NULL;p = &a;p = p+1;p = p+2;p= 10;Adresse Valeur 1100………10 028…15 000…22 222

Page 18 : Arithmétique du pointeur : additionAdresse Valeur 11001………10 028…15 000…22 222aSi i est un entier et p est un pointeur sur un objet de type type, l’expression p+i désigne un pointeur de valeur:p + i = p + i sizeoftype Exemple inta = 1;int p = NULL;p = &a;p = p+1;p = p+2;p= 10;

Page 19 : Arithmétique du pointeur : additionAdresse Valeur 11001………10 028…15 000…22 222NULLapSi i est un entier et p est un pointeur sur un objet de type type, l’expression p+i désigne un pointeur de valeur:p + i = p + i sizeoftype Exemple inta = 1;int p = NULL;p = &a;p = p+1;p = p+2;p= 10;

Page 20 : Arithmétique du pointeur : additionAdresse Valeur 11001………10 028…15 000…22 2221100apSi i est un entier et p est un pointeur sur un objet de type type, l’expression p+i désigne un pointeur de valeur:p + i = p + i sizeoftype Exemple inta = 1;int p = NULL;p = &a;p = p+1;p = p+2;p= 10;

Page 21 : Arithmétique du pointeur : additionAdresse Valeur 11001………10 028…15 000…22 2221104apSi i est un entier et p est un pointeur sur un objet de type type, l’expression p+i désigne un pointeur de valeur:p + i = p + i sizeoftype Exemple inta = 1;int p = NULL;p = &a;p = p+1;p = p+2;p= 10;

Page 22 : Arithmétique du pointeur : additionAdresse Valeur 11001………10 028…15 000…22 2221112apSi i est un entier et p est un pointeur sur un objet de type type, l’expression p+i désigne un pointeur de valeur:p + i = p + i sizeoftype Exemple inta = 1;int p = NULL;p = &a;p = p+1;p = p+2;p= 10;

Page 23 : Arithmétique du pointeur : additionAdresse Valeur 11001………10 028…15 000…22 2221112ap On ne modifie pas a ! mais une donnée plus loin! Une Erreur de segmentation est possible, et c'estd'ailleurs la meilleure chose qu'il puisse arriver. Si l'instruction p=10; n'échoue pas, il serapeut-être difficile de trouver d'où vient le problème lorsque le symptôme se manifestera.Si i est un entier et p est un pointeur sur un objet de type type, l’expression p+i désigne un pointeur de valeur:p + i = p + i sizeoftype Exemple inta = 1;int p = NULL;p = &a;p = p+1;p = p+2;p= 10;

Page 24 : Arithmétique du pointeur : additionint tab10; // tableau d’entierint p; p = tab;// &tab0 adresse première casep = p+1;// ajoute sizeofint - 2eme case du tableau.p = p+2;// adresse de la quatrième case.On a donc bien :tabi = tab+iSi i est un entier et p est un pointeur sur un objet de type type, l’expression p+i désigne un pointeur de valeur:p + i = p + i sizeoftype Application aux tableaux

Page 25 : Arithmétique du pointeur : additionint tab10; // tableau d’entierint p = NULL;forp=&tab0; p&tab10; p++ //parcours du tableaup=0;On a donc bien :tabi = tab+iSi i est un entier et p est un pointeur sur un objet de type type, l’expression p+i désigne un pointeur de valeur:p + i = p + i sizeoftype Application aux tableaux

Page 26 : Arithmétique du pointeur : soustractionint tab10; // tableau d’entierint p; p = &tab6; // adresse 5eme casep = p-1;// adresse 4eme casep = p-3;// adresse 1ere caseSi i est un entier et p est un pointeur sur un objet de type type,l’expression p-i désigne un pointeur de valeur:p - i = p - i sizeoftype Exemple

Page 27 : Arithmétique du pointeur : différence•La différence de deux pointeurs portant tous deux vers des objets demême type. Le résultat est un entier.•Pertinent que si les pointeurs pointent sur des éléments d’un même tableau.•La différences indique p1-p2 nombre d’élements du tableau entre p1 et p2Exempleint tab10; // tableau d’entierint p1,p2;p1=&tab2;p2=&tab4;p2-p1= p1-p2= p1-p1= p2+3-p1=

Page 28 : •La comparaison entre deux pointeurs équivaut à comparer les adresses contenues par ces pointeurs.p1==p2 indiquent si les pointeurs pointent sur la même adresse mémoire.Algorithme du pointeur : comparaison

Page 29 : •La comparaison entre deux pointeurs équivaut à comparer les adresses contenues par ces pointeurs.p1==p2 indiquent si les pointeurs pointent sur la même adresse mémoire.Question : quelle différence entre p1==p2 et p1==p2?Adresse Valeur 1100………10 028…15 000…Algorithme du pointeur : comparaison

Page 30 : Algorithme du pointeur : comparaison•La comparaison entre deux pointeurs équivaut à comparer les adresses contenues par ces pointeurs.p1==p2 indiquent si les pointeurs pointent sur la même adresse mémoire.•La comparaison de deux pointeurs qui pointent dans le même tableau est équivalente à la comparaison des indices correspondants.•On peut utiliser =!, ==, , , =, =

Page 31 : Allocation dynamique Rappel:•La taille d’un tableau doit être connue lors de sa déclaration. On peut écrire :•int tab10 : directement le nombre de cases•int tabCONST : utiliser une constanteMais:•La taille d’un tableau n’est pas forcement connue lors de la compilation.•La taille peut-être passée en paramètre ou donnée par l’utilisateur.•La taille d’une chaîne de caractère dépend de son contenu.Jusqu’à maintenant : On déclare des tableaux très trop grands.

Page 32 : Allocation dynamique : malloc•Il est possible d’allouer réserver un espace mémoire d’un nombre souhaité d’octets grâce à la fonction malloc. C’estl’allocation dynamique.Exemple: mallocnombred’octetsmalloc3; //alloue l’espace mémoire de 3 octetsAdresse Valeur 110011011102…10 028Espace alloué !

Page 33 : Allocation dynamique : malloc•Il est possible d’allouer réserver un espace mémoire d’un nombre souhaité d’octets grâce à la fonction malloc. C’estl’allocation dynamique.•La fonction retourne l’adresse de la première case mémoire de l’espace alloué donc un pointeur.•Le pointeur retourné n’a pas de type. C’est un pointeur universel. •Le prototype de la fonction malloc s’écrit :•On peut donc attribuer au retour de la fonction un pointeur de n’import quel type:mallocnombred’octetsvoid mallocnombred’octetsfloat p2;p2=malloc…;int p1;p1=malloc…;char p3;p3=malloc…;

Page 34 : Allocation dynamique : test •Il est possible que l’allocation échoue. Il y a deux possibilités:•1. Si l'allocation a marché, le pointeur retourné contient une adresse.•2. Si l’allocation a échoué le pointeur retourné contient NULL.•Il faut donc toujours vérifier que l’allocation a fonctionné avant d’utiliser la mémoire allouée:includesdtlib.h // malloc et exitint mainint p1;p=mallocnmboctetsouhaites;\\testifp==NULLprintf"Allocation échouée !"exit1; // On quitte le programme

Page 35 : Allocation dynamique : tableau •On peut allouer dynamiquement l’espace pour un tableau:Exemple :int tab=NULL;int nb;//on demande la tailleprintf"Taille du tableau ? ";//on récupère la taillescanf"d",&nb;//on alloue la place pour nb inttab = mallocnbsizeofint;Adresse Valeur 11541155115611571158115911601161…?….….tab1554

Page 36 : Allocation dynamique : tableau •On peut allouer dynamiquement l’espace pour un tableau:Exemple :Adresse Valeur 11541155115611571158115911601161…?….….tab1554tab +1 = tab +2 = int tab=NULL;int nb;//on demande la tailleprintf"Taille du tableau ? ";//on récupère la taillescanf"d",&nb;//on alloue la place pour nb inttab = mallocnbsizeofint;

Page 37 : Allocation dynamique : tableau •On peut allouer dynamiquement l’espace pour un tableau de type typeet de taille taille. C’est l’allocation dynamqiue.•Le pointeur obtenu pointe sur la première case du tableau. Le tableau peut être géré comme un tableau à déclaration statique. tab = malloctaillesizeoftype

Page 38 : Allocation dynamique : tableau •On peut allouer dynamiquement l’espace pour un tableau de type typeet de taille taille. C’est l’allocation dynamqiue.•Le pointeur obtenu pointe sur la première case du tableau. Le tableau peut être géré comme un tableau à déclaration statique. •Points importants:•Le type du pointeur doit être du même type que les éléments du tableau.•Toujours vérifier que l’allocation mémoire a été réalisée•Une fois l’allocation faite, la taille de la mémoire allouée est fixée : on ne peut pas modifier la taille du tableau à postériori. •malloc appartient à la bibliothèque stdlib !type tab = NULL;tab = malloctaillesizeoftype;

Page 39 : Allocation dynamique : calloc•La fonction calloc permet également d’allouer un espace mémoire et de retourner un pointeur sur la première adresse de cet espace.•Contrairement à malloc, la fonction calloc demande le nombre d’élément et la taille de chaque élément à allouer:•Exemple callocnombreelements, tailleelementfloat p;//allocation mémoire pour 10 réelsp = calloc10, sizeoffloat;

Page 40 : Allocation dynamique : calloc•La fonction calloc permet également d’allouer un espace mémoire et de retourner un pointeur sur la première adresse de cet espace.•Contrairement à malloc, la fonction calloc demande le nombre d’élément et la taille de chaque élément à allouer:•En plus d’allouer l’espace mémoire, la fonction calloc initialise tous les elements de cet espace à 0. peut prendre du temps!•calloc appartient également à stdlib.callocnombreelements, tailleelement

Page 41 : Allocation dynamique : free•Une bonne pratique pour éviter une utilisation inutile de l’espace mémoire est de librerer la mémoire allouée lorsqu’on en a plus besoin. •La procédure free permet de libérer l’espace alloué: il peut donc être utilisé à nouveau pour stocker d’autres données. Elle prend en paramètre le pointeur pointant sur la zone allouée.•Exemplefloat p;// allocation de l’espace mémoire.p=malloc10sizeoffloat;…freep; // restitution de l’espace mémoire.

Page 42 : Allocation dynamique : free•Une bonne pratique pour éviter une utilisation inutile de l’espace mémoire est de librerer la mémoire allouée lorsqu’on en a plus besoin. •La procédure free permet de libérer l’espace alloué: il peut donc être utilisé à nouveau pour stocker d’autres données. Elle prend en paramètre le pointeur pointant sur la zone allouée.•Points importants:•On ne peut libérer qu’un espace qui a, au préalable, été alloué dynamiquement avec malloc ou calloc.•Ne pas libérer l’espace mémoire c’est risquer une fuite mémoire.

Page 43 : Les doubles pointeurs•Il est possible de déclarer un pointeur qui pointe sur un autre pointeur. La déclaration se fait avec le double caractère •Exemple:Type nomPointeur; int a = 5;int pa;int ppa;pa= &a;ppa = &pa;Adresse Valeur 11005………10 028………22 222apappapa= ppa= ppa= pa= ppa=

Page 44 : Les doubles pointeurs•Il est possible de déclarer un pointeur qui pointe sur un autre pointeur. La déclaration se fait avec le double caractère •Exemple: qu’affiche le code suivant ? Type nomPointeur; int a=5, b=10;int pa = &a;// raccourcit !int ppa;ppa= &pa;pa= 1;ppa = &b;pa= b + pa;printf"a=d b=d ",a,b;Adresse Valeur 11005…1500…10 028…20 000…22 222

Page 45 : Les doubles pointeurs: application•Les doubles pointeurs permettent de créer des tableaux de tableaux.•Rappel: •Les tableaux à 2 ou plus dimensions peuvent être vu comme des tableaux contenant des sous-tableaux:Exemple : int tab35 peut être visualisé comme un tableau contenant 3 sous tableau de 5 cases. 0,0,0,0,0,1,1,1,1,1,2,2,2,2,2 000001111122222

Page 46 : Les doubles pointeurs: application•Les doubles pointeurs permettent de créer des tableaux de tableaux.•Rappel: •Les tableaux à 2 ou plus dimensions peuvent être vu comme des tableaux contenant des sous-tableau. •En pratique, tous les éléments sont à la suite dans la mémoire.•On ne peux pas construire des sous-tableaux qui auraient des tailles différentes. ex: un tableau de chaîne de caractère de différentes tailles. •La solution est de créer différents tableau et d’indiquer leur emplacement leur adresse dans un tableau de pointeur.•Le pointeur sur la première case d’un tableau de pointeur sera un double pointeur un pointeur sur pointeur.

Page 47 : Les doubles pointeurs: application•Les doubles pointeurs permettent de créer des tableau de tableau.•Illustration: int tab15, tab210, tab33;int tab2tab3;tab2tab0=tab1;tab2tab1=tab2;tab2tab2=tab3;Adresse Valeur A quoi sont équivalentes les commandes suivantes?tab2tab=1;tab2tab+2+1=3;tab2tab19=4;

Page 48 : Les doubles pointeurs: application•Les doubles pointeurs permettent de créer des tableau de tableau.•remarque: int tab15, tab210, tab33;int tab2tab3;=int tab15, tab210, tab33;int tab2tab;tab2tab=malloc3sizeofint;

Page 49 : Les doubles pointeurs: application•Révélation : la fonction main peux prendre des arguments!•On peut communiquer au programme des arguments lors de l’exécution.Exemples

Page 50 : Les doubles pointeurs: application•Révélation : la fonction main peux prendre des arguments!•On peut communiquer au programme des arguments lors de l’exécution.•Ces arguments seront traités comme des chaînes de caractères.•Le prototype de la fonction main:•argc est le nombre d’argument +1 •argv est un tableau de chaines de caractères contenant les différents argument. int mainint argc, char argv

Page 51 : Les doubles pointeurs: application•Le prototype de la fonction main:•argc est le nombre d’arguments +1•argv est un tableau de chaines de caractères contenant les différents arguments.•On peut donc récupérer les différents arguments grâce au tableau argv.•Attention:•Les nombres passés en arguments sont considérés comme des chaînes de caractères!•argv0 est la commande d’exécution.int mainint argc, char argv

Page 52 : Les doubles pointeurs: application•Le prototype de la fonction main:•argc est le nombre d’arguments +1•argv est un tableau de chaines de caractères contenant les différents arguments.•Exemple :int mainint argc, char argv./prog zoro sanji 42

Page 53 : Les doubles pointeurs: application•Le prototype de la fonction main:•argc est le nombre d’argument +1•argv est un tableau de chaines de caractères contenant les différents argument. •Exemple :int mainint argc, char argv./prog zoro sanji 42nomexecutableargument 1argument 2argument 3

Page 54 : Les doubles pointeurs: application•Le prototype de la fonction main:•argc est le nombre d’argument +1•argv est un tableau de chaines de caractères contenant les différents argument.•Exemple :•argv0 = "./prog"•argv1 = "zoro"•argv2 = "sanji"•argv3 = "42"•argc= 4int mainint argc, char argv./prog zoro sanji 42

Page 55 : Les doubles pointeurs: application•Exemple d’application:include stdio.hinclude stdlib.hint mainint argc, char argv // obligatoire int a,b;printf"Il y a d arguments \n", argc-1;printf"Le premier argument est s\n", argv0;a = atoiargv2;//converti une chaîne en entierb = atoiargv3;printf"Somme des deux arguments = d \n", a+b;return 0;

Page 56 : Les doubles pointeurs: application•Exemple d’application:./prog coucou 15 20include stdio.hinclude stdlib.hint mainint argc, char argv // obligatoire int a,b;printf"Il y a d arguments \n", argc-1;printf"Le premier argument est s\n", argv1;a = atoiargv2;//converti une chaîne en entierb = atoiargv3;printf"Somme des deux arguments = d \n", a+b;return 0; Il y a 3 argumentsLe premier argument est coucouSomme des deux arguments = 35

Page 57 : Conclusion / résumé•Les pointeurs sont très utiles et leurs applications nombreuses•Le type de pointeur indique l’espace mémoire total sur lequel il pointe. Il permet d’effectuer le bon « saut » de mémoire pour passer d’une variable à l’autre. •Il est possible de réserver manuellement un espace mémoire dont la première case sera indiquée par un pointeur : c’est l’allocation dynamique. Cela permet entre autres de créer des tableaux dont la taille n’est pas connue à l’avance.•On peut utiliser des pointeurs de pointeurs. Cela offre une plus grande liberté de gestion de tableau, notamment pour des tableaux de chaînes de caractères. Ce concept est à la base de l’exploitation des arguments de la fonction main.

Page 58 : Bonus : conversion d’une chaîne vers un nombre•La fonction atoi dans stdlib permet de convertir une chaîne de caractère en int. Cependant si la chaîne est vide, elle ne renvoie pas une erreur mais 0. Il faut donc faire attention lors de son utilisation.•Certaines fonctions permettent de gérer les erreurs et peuvent traduire une chaîne en d’autre types :•strtol : permet de convertir une chaîne vers un long•strtod : permet de convertir une chaîne vers un double•strtof : permet de convertir une chaîne vers un fl oa t•…•La fonction sprintf fait l’inverse : elle peut convertir n’importe quel type en chaîne de caractères comme le ferait printf

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