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
Page 1 : INFORMATIQUE 2Eva ANSERMIN & Romuald GRIGNON1I I I . P O I N T E U R S&TA B L E A U X D Y N A M I Q U E S
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 2221154tab0tab1tab2tab3tab4tab2
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;4 numéros d’adresse d’écart entre chaque case !3
Page 4 : 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 !4
Page 5 : 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 !5
Page 6 : •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.Stockage des variables6
Page 7 : •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 du type passé en argument :•Exemple : sizeofint retourne 4.Stockage des variables7
Page 8 : •Une variable peut être stockée sur plusieurs cases mémoire selon son type.•Une adresse mémoire contient 1 octet. Stockage des variablesinta = 1000;char b = ‘b’; //98AdresseValeur11540000 000011550000 000011560000 001111571110 1000…10 0280110 0010ab8
Page 9 : •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….….tab0tab1tab2Stockage des variables9
Page 10 : •Nous avons vu que :Gestion des pointeurstabi = 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 pointeurs10
Page 11 : •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 bArithmétique du pointeur11
Page 12 : •Les pointeurs sont des variables entières adresses mémoire.•On peut donc lui appliquer un certain nombre d’opérateurs arithmétiques classiques : Arithmétique du pointeur1.L’addition + d’un entier à un pointeur. Le résultat est un pointeur de mêmetype que le pointeur de départ.2.lLa soustraction - d’un entier à un pointeur. Le résultat est un pointeur demême type que le pointeur de départ.3.La différence - de deux pointeurs pointant tous deux vers des données demême type. Le résultat est un entier.4.Les opérateurs de comparaison.12
Page 13 : •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 •Le décalage du bon nombre d’adresse s’effectue automatiquement.Arithmétique du pointeur : addition13
Page 14 : •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 : Arithmétique du pointeur : additioninta = 1;int p = NULL;p = &a;p = p+1;p = p+2;p= 10;Adresse Valeur 1100………10 028…15 000…22 22214
Page 15 : Arithmétique du pointeur : additioninta = 1;int p = NULL;p = &a;p = p+1;p = p+2;p= 10;Adresse Valeur 11001………10 028…15 000…22 222a•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 : 15
Page 16 : Arithmétique du pointeur : additioninta = 1;int p = NULL;p = &a;p = p+1;p = p+2;p= 10;Adresse Valeur 11001………10 028…15 000…22 2221100ap•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 : 16
Page 17 : Arithmétique du pointeur : additioninta = 1;int p = NULL;p = &a;p = p+1;p = p+2;p= 10;Adresse Valeur 11001………10 028…15 000…22 2221104ap•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 : 17
Page 18 : Arithmétique du pointeur : additioninta = 1;int p = NULL;p = &a;p = p+1;p = p+2;p= 10;Adresse Valeur 11001………10 028…15 000…22 2221112ap•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 : 18
Page 19 : Arithmétique du pointeur : additioninta = 1;int p = NULL;p = &a;p = p+1;p = p+2;p= 10; 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 : 19
Page 20 : 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+i•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 •Application au tableaux :20
Page 21 : •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 •Application au tableaux : Arithmétique du pointeur : additionOn a donc bien :tabi = tab+iint tab10; // tableau d’entierint p = NULL;forp=&tab0; p&tab10; p++ //parcours du tableaup=0;21
Page 22 : Arithmétique du pointeur : soustractionint tab10; // tableau d’entierint p; p = &tab6; // adresse 5eme casep = p-1;// adresse 4eme casep = p-3;// adresse 1ere case•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 : 22
Page 23 : •La différence de deux pointeurs portant tous deux vers des objets de même type. Le résultat estun entier.•Pertinent que si les pointeurs pointent sur des éléments d’un même tableau.•La différences indique p1-p2 nombre d’éléments du tableau entre p1 et p2•Exempleint tab10; // tableau d’entierint p1,p2;p1=&tab2;p2=&tab4;p2-p1= p1-p2= p1-p1= p2+3-p1= Arithmétique du pointeur : différence23
Page 24 : int tab10; // tableau d’entierint p1,p2;p1=&tab2;p2=&tab4;p2-p1= 2 p1-p2= -2 p1-p1= 0 p2+3-p1= 5 Arithmétique du pointeur : différence•La différence de deux pointeurs portant tous deux vers des objets de même type. Le résultat estun entier.•Pertinent que si les pointeurs pointent sur des éléments d’un même tableau.•La différences indique p1-p2 nombre d’éléments du tableau entre p1 et p2•Exemple24
Page 25 : •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.Arithmétique du pointeur : comparaison•Question : quelle différence entre p1 == p2 et p1==p225
Page 26 : •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.Arithmétique du pointeur : comparaison•La comparaison de deux pointeurs qui pointent dans le même tableau est équivalente à la comparaison des indices correspondants.•On peut utiliser =!, ==, , , =, = 26
Page 27 : 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.Allocation dynamique27
Page 28 : •Il est possible d’allouer réserver un espace mémoire d’un nombre souhaité d’octets grâce à la fonction malloc. C’est l’allocation dynamique.•Exemple :mallocnombred’octetsmalloc3; //alloue l’espace mémoire de 3 octetsAdresse Valeur 110011011102…10 028Espace alloué !Allocation dynamique : malloc28
Page 29 : •Il est possible d’allouer réserver un espace mémoire d’un nombre souhaité d’octets grâce à la fonction malloc. C’est l’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’octetsAllocation dynamique : mallocvoid mallocnombred’octetsfloat p2;p2=malloc…;int p1;p1=malloc…;char p3;p3=malloc…;29
Page 30 : •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 programmeAllocation dynamique : test30
Page 31 : •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…?….….tab1554Allocation dynamique : tableau31
Page 32 : •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;Allocation dynamique : tableauAdresse Valeur 1154tab01155tab01156tab01157tab01158tab11159tab11160tab11161tab1…1154+nbsizeofin….….tab1554Ici tab +1 = 1158, plus généralement &tab1 Ici tab +2 = ici 1562, plus généralement &tab2 32
Page 33 : •On peut allouer dynamiquement l’espace pour un tableau de type type et 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 = malloctaillesizeoftypeAllocation dynamique : tableau•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 !33
Page 34 : •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;Allocation dynamique : calloc34
Page 35 : •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, tailleelementAllocation dynamique : calloc35
Page 36 : •Une bonne pratique pour éviter une utilisation inutile de l’espace mémoire est de libérerla 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.•Exemple :float p;// allocation de l’espace mémoire.p=malloc10sizeoffloat;…freep; // restitution de l’espace mémoire.Allocation dynamique : free36
Page 37 : •Une bonne pratique pour éviter une utilisation inutile de l’espace mémoire est de libérer 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.Allocation dynamique : free37
Page 38 : •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&a 1100………22 222&pa 10 028apappapa= &a ppa= &pappa= &a=5pa= 5 ppa= &aLes doubles pointeurs38
Page 39 : •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&a 1100………22 222&pa 10 028apappapa= ppa= ppa= pa= ppa= Les doubles pointeurs39
Page 40 : •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 000001111122222Les doubles pointeurs : applications40
Page 41 : •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.Les doubles pointeurs : applications41
Page 42 : •Les doubles pointeurs permettent de créer des tableau de tableau.•Illustration : int tab15, tab210, tab33;int t2t3;t2t0=tab1;t2t1=tab2;t2t2=tab3;Adresse Valeur 1000tab101004tab11……1016tab14150010001700tab20…tab21700A quoi sont équivalentes les commandes suivantes?t2t= tab10t2t+2+1= tab3 +1 = tab31t2t19= tab29Adresse Valeur 2500tab30…30002500370010001700250040003700tab1tab10tab20tab30tab3t2t0t2t1t2t2t2tLes doubles pointeurs : applications42
Page 43 : •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;Les doubles pointeurs : applications43
Page 44 : •Révélation : la fonction main peux prendre des arguments!•On peut communiquer au programme des arguments lors de l’exécution.•Exemples :Les doubles pointeurs : applications44
Page 45 : •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 argvLes doubles pointeurs : applications45
Page 46 : •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 argvLes doubles pointeurs : applications46
Page 47 : •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 argvLes doubles pointeurs : applications./prog zoro sanji 4247
Page 48 : •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 argvLes doubles pointeurs : applications./prog zoro sanji 42nomexecutableargument 1argument 2 argument 348
Page 49 : •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 argvLes doubles pointeurs : applications./prog zoro sanji 42argv0 = "./prog"argv1 = "zoro"argv2 = "sanji"argv3 = "42"argc= 449
Page 50 : •Exemple d’application :Les doubles pointeurs : applicationsinclude 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;50
Page 51 : •Exemple d’application :Les doubles pointeurs : applicationsinclude 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; Il y a 3 argumentsLe premier argument est coucouSomme des deux arguments = 35./prog coucou 15 2051
Page 52 : •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.Conclusion52
Page 53 : •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 f loa t•…•La fonction sprintf fait l’inverse : elle peut convertir n’importe quel type en chaîne de caractères comme le ferait printf.Bonus : conversion d’une chaîne vers un nombre53
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