TP C4   2425v4
(à faire même si le TP C3 n'est pas terminé)

I.          L’allocation dynamique en C

 

I.1. Idée

Toutes les données que nous avons manipulées jusqu’à présent ont toujours été allouées « statiquement » par le compilateur, et on ne pouvait ni en ajouter ni en supprimer pendant l’exécution.

Nous allons voir qu’il est possible de les allouer « dynamiquement » et également de libérer cette mémoire lorsqu’on n’en a plus besoin.

 

I.2. Un type simple

Si on souhaite allouer dynamiquement un int, il nous faut prévoir un pointeur pour stocker l’adresse de la zone mémoire allouée pour cet int : int * ptrEntier;      


Pour effectivement allouer la mémoire, on écrira : ptrEntier = (int*)malloc( sizeof(int) );
La fonction malloc trouvera un emplacement suffisamment grand dans la mémoire pour contenir le nombre d’octets qu’on lui passe en paramètre et nous le réservera. Il nous faut donc calculer le nombre d’octets nécessaires en fonction du type avec sizeof .
Enfin, elle nous retournera l’adresse de début de cet emplacement mémoire, sous forme de pointeur générique (void*) puisque malloc ne sait pas quel type de pointeur on veut. Il faut donc convertir ce pointeur dans le type pointeur souhaité.
Il est intéressant de noter pour la suite (*) que le système d'exploitation maintient une table des allocations qui à chaque adresse retournée par malloc associe la taille de la zone allouée.


Que se passe-t-il s’il n’y a plus assez de place ou si l’allocation échoue pour une autre raison ? Dans ce cas, malloc retourne NULL (aussi appelé nil ou pointeur nul), qui est une valeur particulière qu’on peut tester.

Attention ! Pour utiliser la fonction malloc, il faut avoir inclus le fichier stdlib.h.

 

Une fois cette allocation faite, on peut utiliser la zone mémoire comme si on avait déclaré un entier comme habituellement ; donc, au lieu d’écrire :      
1.   int* ptrEntier;
2.   int i;  ptrEntier = &i; // ne peut pas etre NULL
3.   *ptrEntier = 5;
4.   *ptrEntier = *ptrEntier + 1;
5.   printf( "%d\n", *ptrEntier );

on peut écrire :          

 1.   int* ptrEntier;
2a.   ptrEntier = (int*)malloc( sizeof(int) ); // peut etre NULL
2b.   if ( ptrEntier != NULL) {
 3.     *ptrEntier = 5;
 4.     *ptrEntier = *ptrEntier + 1;
 5.     printf( "%d\n", *ptrEntier );
2c.   }

Attention ! En 2a., la zone mémoire ainsi allouée n’a pas été initialisée et peut contenir autre chose que des 0 (tout comme en 2., la variable i n'a pas été initialisée et peut contenir autre chose que des 0).
Il est toutefois possible d’utiliser la fonction calloc au lieu de malloc pour initialiser à 0 toute la zone mémoire au moment de l’allocation (juste avant de retourner l’adresse à stocker dans un pointeur).

 

I.3. Il faut toujours rendre ce que l’on a emprunté

Ce qui manque jusqu’à présent est la libération de l’espace mémoire réservé quand on n’en a plus besoin.      
Jusqu’ici, on ne s’en préoccupait pas et la mémoire était simplement libérée à la fin du programme, même si de nombreuses variables n’étaient plus utiles depuis peu après le début du programme.

Avec l’allocation dynamique, on peut faire beaucoup mieux puisqu’on peut rendre la mémoire au système dès qu’on n’en a plus besoin, ce qui lui permettra de la réutiliser tout de suite pour autre chose.

Pour rendre au système la mémoire réservée pour notre entier, il suffit d’écrire free(ptrEntier);
Il est intéressant de noter que le système d'exploitation se souvient (*) de la taille de la zone à libérer associée au pointeur qu'on passe à free.

 

Attention ! free ne doit être appelée sur un pointeur que si celui-ci contient bien l’adresse d’une zone mémoire allouée par malloc ou calloc.

Le problème est qu’ensuite, ptrEntier pointe toujours sur cette zone mémoire et qu’un mauvais programmeur pourrait continuer de l’utiliser alors que la mémoire a été rendue au système.

Il est donc d’usage de faire suivre la désallocation d’une instruction ptrEntier = NULL; pour qu’il ne soit plus possible d’accéder à la zone mémoire qui n’est plus réservée pour notre programme.
Remarque : certaines implémentations de free mettent à 0 les 16 premiers octets de la zone ainsi libérée.

 

Il est donc conseillé de définir une macro. (optionnel pour l'instant, mais obligatoire si vous avez le temps à la fin du TP)


I.4. Exercice I-4.c (à faire très vite, tout est donné ci-dessus)

1.      Créez un nouveau programme C qui ne contiendra qu’un programme principal qui devra :

2.      Déclarer un pointeur de réel (double) et allouer dynamiquement un réel (avec vérification !),

3.      y stocker la valeur de quatre tiers, la multiplier par 2, puis l’afficher,

4.      afficher le pointeur (grâce au format %p), puis le désallouer, puis le réafficher,

5.      réafficher la valeur pointée (juste par curiosité, car c’est interdit !), passer le pointeur à NULL, puis la réafficher ;           
peut-on toujours aller chercher la valeur se trouvant à l’adresse désignée par notre pointeur ?

 

II.        Une structure

 

II.1. On peut aussi allouer dynamiquement une structure (d’ailleurs on y reviendra plus loin)

 

II.2. Exercice II-2.c (à faire vite, peu de modifications)

1.      Recopiez le fichier III-2.c du TP C3 dans le répertoire TpC4 en l’appelant II-2.c

2.      Remplacez dans le programme principal la déclaration des 2 groupes par la déclaration de 2 pointeurs de Groupe avec l’allocation dynamique de 2 groupes (avec vérification !).

3.      Modifiez ce qu’il faut dans les 3 instructions suivantes pour tenir compte de ce changement, tout en conservant l'objectif de ne saisir qu'un Groupe et de le recopier dans le 2ème.

4.      Compilez/testez : tout doit fonctionner comme avant. Au fait, avez-vous pensé à désallouer ?


II.3. Exercice II-3.c (à faire assez vite, les mêmes principes sont à l’œuvre)

1.      Dupliquez le fichier II-2.c en II-3.c

2.      Dans cet exercice du TP précédent, nous n’avions pas pu aller au bout de la démarche : afficheGroupe pouvait ne pas recopier son paramètre puisqu’on lui passait l’adresse de la structure, mais on devait recopier le résultat de saisitGroupe, car si on avait retourné l’adresse de la variable déclarée dans saisitGroupe, nous aurions retourné l’adresse d’une variable qui a automatiquement disparu à la fin de l’exécution de cette fonction !

3.      Maintenant que nous savons faire de l’allocation dynamique, modifiez saisitGroupe pour qu’elle alloue dynamiquement un Groupe et qu’elle retourne juste l’adresse du Groupe, sans recopie !

Que devrait-elle retourner en cas d’échec d’allocation ?  Pensez à utiliser des ->
Remarque : Il est légitime de s'interroger sur la responsabilité de la désallocation ; le pointeur étant retourné au programme principal, ce sera à lui de le faire, s'il n'en a plus besoin avant la fin du programme.

4.      N’oubliez pas la modification indispensable dans le programme principal, tout en conservant l'objectif de ne saisir qu'un Groupe et de le recopier dans le 2ème.

5.      Compilez/testez : tout doit fonctionner comme avant.

 

III.      Les tableaux

 

III.1. Il est encore plus intéressant d’allouer dynamiquement des tableaux (qui prennent bcp de place).

Pour manipuler des tableaux dynamiques d’entiers, il nous suffira de déclarer un simple type Pointeur d’entier : typedef int * TabDyn;

Maintenant, si nous voulons allouer dynamiquement un tableau de 100 entiers, il faudra écrire :

TabDyn vTab = (TabDyn)malloc( 100 * sizeof(int) );

Avec l’équivalence pointeur/tableau que nous avons déjà étudiée, on pourra se servir de ce tableau « dynamique » avec la syntaxe habituelle des tableaux « statiques » :

vTab[0] = 10;  vTab[1] = vTab[0]*2;  vTab[2] = vTab[0]+vTab[1];

exactement comme si on avait déclaré int vTab[100];

Mais la différence, c’est qu’on peut libérer la mémoire prise par ce tableau bien avant la fin du programme, et surtout, qu’on peut choisir la taille du tableau à l’exécution, et non forcément à la compilation !


Comme ci-dessus, on peut aussi définir une macro. (optionnel pour l'instant, mais obligatoire si vous avez le temps à la fin du TP)

 

III.2. Exercice III-2.c

1.      Créez un nouveau programme qui commencera par créer un nouveau type TabDyn pour pouvoir créer des tableaux dynamiques de réels.

2.      Dans le programme principal, demandez à l’utilisateur quelle taille de tableau il désire et allouez dynamiquement un tableau d’autant de réels que souhaité (avec vérification !).

3.      Remplissez chaque case par la racine carrée de l’indice de la case.

4.      Affichez toutes les cases du tableau sur une ligne.

5.      Calculez et affichez la moyenne de toutes les valeurs du tableau.

6.      Désallouez le tableau et réaffichez toutes les valeurs (juste pour braver l’interdit).

 

III.3. Exercice III-3.c (optionnel pour l'instant, mais obligatoire si vous avez le temps à la fin du TP)

1.      Dupliquez le fichier III-2.c en III-3.c

2.      Si vous avez tout programmé dans le programme principal au III.2, rendez-le plus lisible et mieux conçu en créant les deux procédures initTab et afficheTab, ainsi que la fonction moyenne. Les trois devront avoir chacune deux paramètres (voyez-vous pourquoi ?), et les trois ne s'appliquent qu'à un tableau déjà créé.

 

IV.      Les listes chaînées dynamiques

IV.1. Idée

Les tableaux dynamiques, c’est bien, mais si on veut supprimer ou ajouter des éléments, c’est très coûteux :

- Pour supprimer un élément à la 10ème place d’un tableau de 100 éléments, il faut décaler vers la gauche (donc recopier) les 90 éléments de droite.

- Pour insérer un élément à la 10ème place d’un tableau de 100 éléments qui ne contenait que 50 valeurs utiles, il faut décaler vers la droite (donc recopier) les 40 éléments de droite.

- Mais le pire arrive si on veut ajouter un élément alors que le tableau est déjà plein : il faut en réallouer un autre plus grand et recopier toutes les valeurs !
  Même s’il existe une fonction realloc pour cela, le coût en temps devient vite déraisonnable si on le fait souvent, surtout sur des tableaux de grande taille.

Heureusement, on a inventé les listes chaînées dynamiques !       
Il s’agit d’enchaîner des maillons, chaque maillon contenant une valeur et un pointeur vers le prochain maillon. Un pointeur valant NULL indique la fin de la liste. Une liste est désignée par son pointeur de tête.

https://tdinfo.phelma.grenoble-inp.fr/2Aproj/ressources_soutien/FichesHTML/images/02_Listes/TADListeDynIm-0.png Crédits à N.Castagné, F.Cayre, M.Desvignes, E.Moisan, F. Portet

L’inconvénient, c’est qu’on ne peut accéder directement et rapidement qu’au premier élément de la liste et que pour accéder au 10ème élément, il faut parcourir les 10 chaînages précédents.         
Mais l’avantage, c’est qu’on peut en seulement 2 copies de pointeurs (et aucune recopie d’éléments), donc très rapidement, supprimer ou ajouter un élément au milieu d’une liste de milliers d’éléments.

IV.2. La technique

Il faut commencer par définir le type Maillon :

typedef struct {                      Attention !
  int contenu;                           ça ne fonctionne pas !
  Maillon* suivant;     Car ici, le compilateur ne connaît
} Maillon;              pas encore le type Maillon

Pour résoudre ce problème de définition récursive, on va utiliser un type temporaire :

typedef struct tmp_maillon {
  int contenu;
  struct tmp_maillon * suivant;  
} Maillon;

Ensuite, nous pouvons facilement définir le type pointeur de Maillon :    
typedef Maillon* PtrMaillon;

Et enfin le type Liste, représentée par le pointeur de tête de liste, donc un simple pointeur de Maillon :
typedef PtrMaillon Liste;
Bien qu'on constate ci-dessus que PtrMaillon et Liste sont strictement équivalents, essayez dans les exercices ci-dessous de toujours réfléchir pour savoir quel est le nom le plus approprié à utiliser selon la situation :
est-ce une tête de liste, ou bien un simple pointeur qui parcoure la liste ?

IV.3. Un premier exercice sur les listes : IV-3.c

1.      Créez un nouveau programme qui commencera par créer les trois types ci-dessus, mais avec des contenus non pas entiers, mais réels (double).

2.      Créez la fonction listeVide qui retourne 1 quand son paramètre est une liste vide, 0 sinon.

3.      Dans le programme principal, déclarez une liste vide et affichez le résultat de la fonction listeVide.

4.      Créez la procédure afficheListe qui affichera son paramètre Liste sous la forme    
6.0->4.0->5.0->NULL ou simplement NULL si la liste est vide. L’appeler dans le main.       
Conseil : Pour parcourir une liste, il est souvent intéressant d’utiliser une boucle for, dont les 3 parties seront : déclaration/initialisation du pointeur de maillon, vérification que le pointeur n’est pas NULL, puis passage au pointeur suivant.

5.      Créez la fonction creeMaillon qui retournera un pointeur vers le maillon qu’elle aura alloué dynamiquement et qu’elle aura auparavant initialisé avec ses deux paramètres (réel et pointeur de Maillon).
Elle retournera NULL en cas d’échec de l’allocation, ce qui pourra donc être testé dans le main.  
Appelez-la dans le main en lui passant un réel et NULL (avec vérification !).

6.      Appelez à nouveau listeVide et afficheListe pour surveiller l’évolution.

IV.4. Une multitude de fonctions possibles (à commencer pendant le TP et à terminer en travail personnel)

On peut inventer beaucoup de fonctions de manipulation de listes chaînées pour les rendre plus faciles et agréables à utiliser. Il est fortement conseillé de s’entraîner à les programmer. Et pour qu’elles fonctionnent sans trop de bug même en cas de liste vide ou de manipulation du premier ou du dernier élément, il est quasi-obligatoire de faire des dessins au brouillon avec toutes les flèches nécessaires …

 

1.      Dupliquez le fichier IV-3.c en IV-4.c

2.      Ajoutez une fonction ajouteDebut qui prend 2 paramètres : une Liste et un pointeur de Maillon supposé avoir été alloué (au pire NULL). Elle ajoutera le Maillon au début de la Liste et la retournera.

3.      A la fin du programme principal, créez un Maillon (avec vérification !), ajoutez-le au début de la Liste, puis affichez-la pour surveiller l’évolution.

4.      Ajoutez une fonction ajouteFin qui prend 2 paramètres : une Liste et un pointeur de Maillon supposé avoir été alloué (au pire NULL). Elle ajoutera le Maillon à la fin de la Liste et la retournera.

5.      A la fin du programme principal, créez un Maillon (avec vérification !), ajoutez-le à la fin de la Liste, puis affichez-la pour surveiller l’évolution.        
Conseil : Comme dans le parcours de liste nécessaire ici, il n’y a rien à faire d’autre que de faire avancer le pointeur, une boucle while semble plus appropriée.

6.      Ajoutez une fonction contient qui prend en paramètre une Liste et un réel, et qui retourne 1 si ce réel a été trouvé dans l’un des maillons de la liste ou 0 sinon.

7.      Comme vous avez dû mettre 3 réels différents dans les 3 maillons de la Liste, affichez le résultat de l’appel de la fonction contient avec chacune de ces 3 valeurs + une valeur qui n’est pas dans la liste.

8.      Ajoutez la fonction supprimeDebut qui retourne la liste passée en paramètre amputée de son premier élément (qui aura donc été désalloué).

9.      Ajoutez à la fin du programme principal un appel à supprimeDebut suivi d’un affichage de la Liste. Recommencez 3 fois pour tester la fonction dans tous les cas possibles.

10.  Ajoutez la fonction supprimeFin qui retourne la liste passée en paramètre amputée de son dernier élément (qui aura donc été désalloué). Attention aux cas particuliers !

11.  Remplacez à la fin du programme principal les 4 appels à supprimeDebut par 4 appels à supprimeFin.

12.  On peut encore penser à bien d’autres fonctions comme supprimer la première occurrence ou toutes les occurrences d’une valeur, insérer ou supprimer un maillon à une position précise, compter le nb de maillons, etc.

 

V.        Fin du TP

V.1. Si ce n’est pas déjà fait, programmer la partie optionnelle dans le III.3.

V.2. Si ce n’est pas déjà fait, utiliser les macros dans les exercices II.3, III.2, III.3, IV.3 et IV.4.

V.3. Si ce n’est pas déjà fait, terminez les TP précédents.