TP C4 2526v1
(à faire en séance du TP C4, 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)
- Créez un nouveau programme C qui ne contiendra qu’un programme principal qui devra :
- Déclarer un pointeur de réel (
double) et allouer dynamiquement un réel
(avec vérification !),
- y stocker la valeur calculée de quatre tiers, la multiplier par 2, puis l’afficher,
- afficher le pointeur (grâce au format
%p), puis le désallouer, puis le réafficher,
- 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)
- Recopiez le fichier
III-2.c du TP C3 dans le répertoire TpC4 en
l’appelant II-2.c .
- 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 !).
- 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.
- 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)
- Dupliquez le fichier
II-2.c en II-3.c .
- 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 !
- 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 recopier les champs du groupe !
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.
- 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.
- 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 beaucoup 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
- Créez un nouveau programme qui commencera par créer un nouveau type
TabDyn
pour pouvoir créer des tableaux dynamiques de réels.
- 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 !).
- Remplissez chaque case par la racine carrée de l’indice de la case.
- Affichez toutes les cases du tableau sur une ligne.
- Calculez et affichez la moyenne de toutes les valeurs du tableau.
- 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)
- Dupliquez le fichier III-2.c en III-3.c .
- 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.
Sa valeur est donc NULL si la liste est vide.
| Exemples : |
 |
ou |
|
ou |
|
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 {
int contenu;
Maillon* suivant;
} Maillon;
|
Attention !
ça ne fonctionne pas !
Car ici, le compilateur ne connaît
pas encore le type Maillon
|
Pour résoudre ce problème de définition récursive, on va utiliser un type temporaire,
qui désigne le type struct en cours de définition :
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
- 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).
- Créez la fonction
listeVide qui retourne 1 quand son paramètre est une liste vide,
0 sinon.
- Dans le programme principal, déclarez une liste vide et affichez le résultat
de la fonction
listeVide.
- Créez la procédure
afficheListe qui affichera son paramètre Liste
sous la forme
6.0->4.0->5.0->NULL si la liste est :
|
|
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.
- 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 !).
- Appelez à nouveau
listeVide et afficheListe pour surveiller l’évolution.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
2ème partie
IV.4. Une multitude de fonctions possibles (à commencer pendant le TP et à terminer en travail personnel)
Ne pas commencer ces exercices sans avoir terminé le IV.3 ci-dessus.
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 …
- Dupliquez le fichier IV-3.c en IV-4.c .
- 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.
- A la fin du
main, créez un Maillon (avec vérification !),
ajoutez-le au début de la liste, puis affichez-la pour surveiller l’évolution.
- 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.
- A la fin du
main, 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.
- 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.
- 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.
- 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é).
- Ajoutez à la fin du
main un appel à supprimeDebut suivi d’un affichage
de la liste. Recommencez 3 fois pour tester la fonction dans tous les cas possibles.
- 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 !
- Remplacez à la fin du
main les 4 appels à supprimeDebut
par 4 appels à supprimeFin.
- Ajoutez la fonction
nbMaillons qui retourne le nombre de maillons de la liste
passée en paramètre.
- Ajoutez au début de
afficheListe un affichage du nb de maillons,
sous la forme
(3) 6.0->4.0->5.0->NULL si la liste est :
|
|
IV.5. Fin de la 2ème partie
- 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, etc.
- Si ce n’est pas déjà fait, programmer la partie optionnelle dans le III.3.
- 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.
- Si ce n’est pas déjà fait, terminez les TP précédents.
Ne pas tenir compte des parties V. à VIII. ci-dessous pour A3P 2025/2026.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
3ème partie
V. Automatisation de la compilation/édition de liens
V.1. Compilation séparée
(questions possibles au contrôle)
- Comme nous l'avons vu lors du TP C1
(peut-être afficher dans un autre onglet la partie sur la compilation séparée...),
nous pouvons découper notre programme en plusieurs fichiers,
notamment pour pouvoir ne recompiler que les parties qui ont été modifiées.
- Terminez le IV.4. ci-dessus, pour l'instant jusqu'au IV.4.5.
- Créez un sous-répertoire cs et changez de répertoire courant pour y travailler.
- Dupliquez IV-4.c de l'exercice précédent en main.c .
- Extrayez les 3 typedef dans un fichier MesTypes.h que vous n'oublierez pas
d'inclure au début de main.c, mais après les include système.
- Extrayez toutes les fonctions dans un fichier MesFonctions.c
(qui ne doit contenir aucun include inutile),
et vérifiez qu'ajouteFin appelle bien listeVide.
- Recopiez les prototypes de ces fonctions (en n'oubliant pas d'ajouter le point-virgule final)
dans un fichier MesFonctions.h qui devra bien sûr inclure MesTypes.h .
- N'oubliez pas d'inclure ce fichier d'une part au début de main.c (au bon endroit !),
d'autre part au début de MesFonctions.c puis triez les fonctions par ordre alphabétique.
- Compilez séparément le fichiers MesFonctions.c .
Auriez-vous un problème de déclaration implicite ?
C'est bien normal si on réfléchit un peu :
la fonction ajouteFin a besoin de la fonction listeVide
qui apparaît après dans l'ordre alphabétique.
La solution naïve qui consisterait à rechanger l'ordre des fonctions n'est pas la bonne,
d'autant qu'une fonction f1 pourrait appeler une fonction f2
qui elle-même pourrait appeler la fonction f1 !
On prend donc comme convention d'inclure systématiquement le fichier .h des prototypes dans
MesFonctions.c .
- Recompilez séparément MesFonctions.c puis main.c .
Auriez-vous des problèmes de définition multiple ?
C'est bien normal si on réfléchit un peu :
Lorsque main.c inclut MesFonctions.h après MesTypes.h,
il inclut une deuxième fois MesTypes.h puisque celui-ci est inclus par
MesFonctions.h, et on tente de définir une deuxième fois des types avec les mêmes noms !
La solution naïve qui consisterait à ne pas inclure MesTypes.h
dans main.c n'est pas la bonne,
d'une part, car c'est logique de vouloir inclure MesTypes.h puisqu'on utilise
ces types dans le main, mais d'autre part, car il y aura forcément des situations
où l'on aura besoin d'inclure fonc1.h et fonc2.h alors que chacun inclut
le même MesTypes.h.
Pour cela, on prend donc comme convention d'inclure systématiquement ces deux lignes
au début de chaque .h :
#ifndef FICHIER_H
#define FICHIER_H
ainsi que cette ligne à la fin :
#endif
où FICHIER est le vrai nom (en majuscules) du fichier .h
(sans l'extension puisqu'on ajoute _H).
Ainsi, la constante FICHIER_H est définie lors de la première inclusion,
et détectée par le #ifdef lors de la deuxième inclusion pour justement l'empêcher.
- Recompilez séparément les 2 fichiers .c puis générez l'exécutable.
Testez, tout devrait fonctionner comme avant.
- Modifiez la fonction afficheListe pour qu'elle ajoute une barre verticale
juste avant et juste après l'affichage de la valeur réelle.
- Quel fichier devez-vous uniquement recompiler ?
Si vous aviez l'habitude de lancer systématiquement les deux commandes de compilation
plus l'édition de liens, vous lanciez des tâches inutiles puisque main.c n'a pas changé.
Par contre, si nous décidions de changer le type Liste en TeteDeListe
dans MesTypes.h, il faudrait bien recompiler les deux fichiers .c .
Il nous faudrait donc un système qui s'aperçoive automatiquement des fichiers qui ont changé,
et qui lance uniquement les commandes nécessaires pour reconstruire l'exécutable.
V.2. La commande make
(pas de questions au contrôle)
- Ce système existe ! C'est la fameuse commande make.
Tapez-la pour voir. Elle vous dit qu'elle ne trouve pas le fichier makefile
qui devrait lui expliquer ce qu'elle doit faire.
- Créez ce fichier en le laissant vide, et retapez la commande.
Elle trouve bien le makefile mais celui-ci ne contient aucune cible (target)
à construire.
Ajoutez juste ces deux lignes dans le fichier, en utilisant une tabulation
(⟶) pour indenter la 2ème ligne :
listes.exe: *.o
⟶ gcc *.o -o $@
Ceci est une règle qui dit que pour construire la cible listes.exe
lorsqu'au moins un des *.o est modifié, il faut lancer la commande
de la 2ème ligne, $@ désignant simplement la cible.
- Tapez make une première fois, la commande gcc... devrait être lancée.
Tapez make une deuxième fois, elle devrait s'apercevoir qu'il n'y a plus rien à faire.
- Si maintenant nous simulons une petite modification dans main.c
en tapant touch main.c pour mettre à jour la date (et surtout l'heure)
de dernière modification du fichier, mais sans le recompiler.
Pour simuler une situation ou make ne saurait pas comment compiler comme on veut,
tapez make -r : rien ne se passe, car nous ne lui avons pas expliqué comment
fabriquer un .o à partir d'un .c, donc le .o n'a pas été modifié,
donc notre règle ne se déclenche pas.
- Ajoutez au makefile en sautant une ligne la règle suivante :
%.o: %.c
⟶ gcc -c $< -o $@
La première ligne dit qu'on va expliquer comment transformer tout .c en .o,
et $< désigne la première chose après le :, donc ici le fichier .c
à compiler, la cible étant le fichier .o à générer.
- Après avoir tapé touch main.c, tapez make une première fois,
les commandes de compilation séparée puis d'édition de liens devraient être lancées.
Tapez make une deuxième fois, elle devrait s'apercevoir qu'il n'y a plus rien à faire.
- Jusqu'à présent, nous n'avons pas pensé aux .h, mais que se passe-t-il si nous
simulons avec touch une modification par exemple de MesTypes.h ?
Tapez make et constatez qu'il ne se passe rien, alors qu'il aurait dû recompiler
les deux .c qui incluent ce .h !
- Ajoutez au makefile après %.c un espace suivi de *.h
pour signifier que toute modification de .h doit aussi déclencher cette règle.
- Après avoir tapé touch MesTypes.h, tapez make une première fois,
les commandes de compilation séparée puis d'édition de liens devraient être lancées.
Tapez make une deuxième fois, elle devrait s'apercevoir qu'il n'y a plus rien à faire.
- Il nous reste maintenant un dernier détail à régler : nous avons utilisé gcc
au lieu de mycc qui spécifiait certaines options de compilation.
La solution naïve qui consisterait à remplacer gcc par mycc n'est pas la bonne,
car mycc n'est pas une commande standard.
On va donc par convention créer une variable CCFLAGS et l'utiliser dans la commande
de compilation.
Pour cela, ajoutez au début du makefile (puis sautez une ligne) :
CCFLAGS=-std=c99 -Wall -Wextra
puis ajoutez $(CCFLAGS) entre gcc et -c
- Après avoir utilisé touch sur un des fichiers .c ou .h,
tapez make une première fois,
les commandes de compilation séparée (avec les bonnes options !)
puis d'édition de liens devraient être lancées.
Tapez make une deuxième fois, elle devrait s'apercevoir qu'il n'y a plus rien à faire.
-
De la même manière, n'oublions pas l'option -lm pour l'édition de liens.
La convention ici est de définir une variable nommée LDFLAGS.
Saurez-vous effectuer les deux modifications nécessaires pour la mettre en place ?
- Après avoir utilisé touch sur un des fichiers .c ou .h,
tapez make une première fois, les commandes de compilation séparée
puis d'édition de liens (avec la bonne option !) devraient être lancées.
Tapez make une deuxième fois, elle devrait s'apercevoir qu'il n'y a plus rien à faire.
- Bien que nous n'ayons fait qu'effleurer les nombreuses possibilités de la commande
make et du makefile,
à partir de maintenant, à chaque fois que vous ferez une modification dans un fichier,
tapez simplement make pour générer l'exécutable, et le minimum de commandes gcc
seront lancées.
VI. Traitements récursifs
(questions probables au contrôle)
- Si vous avez utilisé une boucle dans les fonctions
afficheListe, ajouteFin, supprimeFin, contient, nbMaillons
vous allez les reprogrammer en récursif, donc sans aucune boucle :
c'est un raisonnement très utilisé avec les listes chaînées
puisque la structure est elle-même récursive.
- Pour ne pas perdre les versions itératives, dupliquez ces 5 fonctions
et renommez le 2ème exemplaire de chacune en ajoutant un I
(comme Itératif ou comme version I) à la fin du nom,
avant de reprogrammer en récursif le corps du premier exemplaire :
vous constaterez que c'est beaucoup plus simple et court.
- Si vous aviez déjà programmé ces 5 fonctions en récursif, alors faites le contraire !
Dupliquez-les en ajoutant un R à la fin du nom et reprogrammez-les sans récursivité,
donc en utilisant une boucle (for ou while, selon ce qui vous paraît
le plus approprié).
- Reconstruisez l'exécutable grâce à make et vérifiez que tout fonctionne comme avant.
- Vérifiez que vous désallouez bien le maillon supprimé dans supprimeDebut et
supprimeFin, et si ce n'est pas le cas, rectifiez ces deux fonctions.
- Reconstruisez l'exécutable grâce à make et vérifiez que tout fonctionne comme avant.
VII. Fin de la 3ème partie
- Si ce n’est pas déjà fait, terminez les fonctions du IV.4., puis complétez le VI.
- Si ce n’est pas déjà fait, terminez les TP précédents.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
4ème partie
VIII. Révisions
VIII.1. TP précédents
À faire dans cet ordre : (et à terminer en travail personnel)
- Si ce n'est pas déjà le cas, terminez intégralement les deux parties du TP C2.
- Si ce n'est pas déjà le cas, terminez intégralement le TP C3.1.
Ne cherchez pas à terminer le TP C3.2 s'il ne l'est pas déjà.
- Si ce n'est pas déjà le cas, terminez intégralement le TP C4.1.
- Si ce n'est pas déjà le cas, terminez intégralement le TP C4.2.
- Si ce n'est pas déjà le cas, terminez l'exercice VI. du TP C4.3.
- Si tous les points précédents sont terminés, terminez l'exercice V. du TP C4.3.
- Si tous les points précédents sont terminés, passez à l'exercice suivant.
VIII.2. Nouvel exercice (Polynômes)
- Cet exercice ne doit être entamé que si TOUS les TP précédents sont terminés,
et si les 3 premières parties de ce TP sont entièrement terminées.
- 🎯 Objectif :
Implémenter un programme en C permettant de représenter et manipuler un polynôme,
en utilisant une liste chaînée de monômes triés par exposant décroissant.
L'intérêt par rapport à un simple tableau de monômes est de ne pas avoir à créer
des tas de monômes pour rien (à chaque fois qu'une puissance n'est pas représentée,
c'est-à-dire quand son coefficient est nul).
- 🗂️ Organisation attendue des fichiers dans un sous-répertoire
Poly :
- MesTypes.h : définition des types utilisés.
- MesFonctions .h et .c : fonctions de gestion du polynôme.
- main.c : programme principal de test.
et utilisation de la commande make.
- 🛠️ Travail détaillé dans les points suivants :
définir les types, créer 3 fonctions, puis le programme principal.
- Les types : vous devez définir une structure
Monome
permettant de représenter un monôme de la forme a·x^n, avec :
- un coefficient (entier),
- un exposant (entier ≥ 0),
- un pointeur vers le monôme suivant.
puis le type PtrMonome et enfin le type Polynome
qui est identique, mais pointe toujours en tête de liste pour désignr un polynôme.
N'oubliez pas d'empêcher l'inclusion multiple de votre fichier .h.
- Écrivez la procédure
afficherPolynome
qui comme son nom l'indique affiche le Polynome qu'on lui passe en paramètre,
sous la forme, par exemple : 7x^5-3x^2+6x-1, si les monômes sont
(7,5) (-3,2) (6,1) (-1,0).
Compilez/corrigez jusqu'à ce qu'il n'y ait plus d'erreurs.
- Écrivez la procédure
insererDansPolynome qui devra insérer dans le
Polynome qu'on lui passe en premier paramètre, le monôme qu'on lui passe
dans les deux derniers paramètres : le coefficient puis l'exposant.
Aide :
Les deux derniers paramètres n'ont aucune raison d'être modifiés dans la procédure...
Les monômes doivent rester triés par exposant décroissant,
si un monôme avec le même exposant existe, les coefficients s'additionnent,
et si le coefficient résultant est nul, le monôme doit être supprimé.
Donc ne pas tenter d'insérer un monôme dont le coefficient est nul.
Compilez/corrigez jusqu'à ce qu'il n'y ait plus d'erreurs.
- Écrivez la procédure
libererPolynome
qui comme son nom l'indique libère la mémoire du Polynome qu'on lui passe en paramètre
(tous les maillons !)
Compilez/corrigez jusqu'à ce qu'il n'y ait plus d'erreurs.
- Écrivez le programme principal qui commencera par créer un polynôme vide, puis insèrera
successivement les monômes :
(1,3) (4,1) (-1,0) (7,5) (-3,2) (2,1) (-1,3).
Terminez en affichant puis libérant le polynôme.
- Compilez/corrigez jusqu'à ce qu'il n'y ait plus d'erreurs, puis générez l'exécutable.
Testez pour vérifier que cela affiche bien
7x^5-3x^2+6x-1.
VIII.3. Fin du TP
- Si vous avez terminé l'exercice précédent, montrez-le à l'intervenant, et vous pouvez partir
s'il ne vous a rien demandé de modifier.
- Si vous n'avez pas terminé l'exercice VI. du TP C4.3, terminez-le en travail personnel.
- Si vous n'avez pas terminé intégralement le TP C4.2, terminez-le en travail personnel,
et si vous avez le temps, faites aussi l'exercice VI. du TP C4.3.
-
N'oubliez pas qu'il y a une séance Résa et une séance PostA avant le contrôle final !
IX. Indices
- IV.4.2. (rien à voir avec le foot ;-) :
Après avoir réussi le cas général, pensez au cas particulier :
Et si la liste était vide au départ ?
Testez les deux cas.
- IV.4.4. :
Après avoir réussi le cas général, pensez au cas particulier :
Et si la liste était vide au départ ?
Testez les deux cas.
- IV.4.8. :
Après avoir réussi le cas général, pensez au cas particulier :
Et si la liste n'avait qu'un seul maillon ?
Testez les deux cas.
- IV.4.10. :
Après avoir réussi le cas général, pensez au cas particulier :
Et si la liste n'avait qu'un seul maillon ?
Testez les deux cas.