INFO517-cours7

Séance 7 du Cours-TD de Programmation C.

Structures récursives

Quand on veut déclarer un type récursif (ou auto-référentiel), la syntaxe suivante est rejetée: <source lang="C"> typedef struct { int data ; bloc_t *suivant ; } bloc_t ; </source> Le problème est que le type bloc_t n'est pas encore défini au moment où on écrit la structure.

Il faut utiliser la syntaxe plus précise: <source lang="C"> typedef struct bloc_rec_t { int data ; struct bloc_rec_t *suivant ; } bloc_t ; </source>

L'idée est que <source lang="C"> struct bloc_rec_t { int data ; struct bloc_rec_t *suivant ; } </source> Déclare un nouveau nom de structure bloc_rec_t. Et alors struct bloc_rec_t est un type.

La version précédente revient à: <source lang="C"> struct bloc_rec_t { int data ; struct bloc_rec_t *suivant ; } ; typedef struct bloc_rec_t bloc_t ; </source>

Pour fixer les idées, on peut revenir au type des vecteurs vu plus haut, en utilisant la syntaxe de déclaration des structures: <source lang="C">

1. include <stdio.h>

struct vect_t { double x ; double y ; } ;

int main () { struct vect_t v = { 1, 2 } ; printf("(%4.2f,%4.2f)\n",v.x,v.y) ; return 0 ; } </source>

La déclaration struct vect_t v dit que v est une variable de type struct vect_t.

La définition struct vect_t v = { 1, 2 } ; initialise v avec 1 dans le premier champ (x) et 2 dans le second (y).

On utilisera souvent des pointeurs vers des structures. Si type_t est le type d'une structure qui comporte un champ x, alors on voudra souvent considérer un pointeur <source lang="C"> type_t *p; </source> et faire référence au champ x de la structure pointée par p: (*p).x. C'est tellement courant qu'il existe une notation abrégée pour cette opération: p->x. On pourra ainsi écrire le programme suivant: <source lang="C">

1. include <stdio.h>

struct vect_t { double x ; double y ; } ;

int main () { struct vect_t v = { 1, 2 } ; struct vect_t *p = &v ; printf("(%4.2f,%4.2f)\n",p->x,p->y) ; return 0 ; } </source> qui fait la même chose que le précédent.

Attention au fait que la structure récursive utilise un pointeur vers elle-même. En effet, on ne peut pas faire directement: <source lang="C"> struct bloc_rec_t { int data ; struct bloc_rec_t suivant ; } ; </source> Un champ dans une structure ne peut-être du même type (souvenez-vous que la taille d'un struct est la somme des tailles de ses champs).

Un exemple complet avec une pile

On construit un programme qui lit des lignes sur son entrée, et les affiches de la dernière à la première.

D'abord, on rappelle la fonction lit_ligne déjà vu plus haut, qu'on met dans une bibliothèque minimaliste:

En-têtes liste.h: <source lang="C">

1. ifndef LIGNE_H
2. define LIGNE_H

/* On alloue par blocs de taille LIGNE_MORCEAU. */

1. define LIGNE_MORCEAU 1024

/* Lit une ligne en entrée _quelle que soit sa taille_

* et la stocke dans *p (p est un pointeur sur une chaîne).
* Renvoie le nombre de caractère lus (-1 en cas d'erreur). */

int lit_ligne (char **p) ;

1. endif /* #ifndef LIGNE_H */

</source>

Code ligne.c: <source lang="C">

1. include <stdlib.h>
2. include <stdio.h>
3. include "ligne.h"

int lit_ligne (char **p) { char c ; char *s ; int pos, blocs, i ;

/* La position courante dans la chaîne est i+LIGNE_MORCEAU*blocs. */ pos = blocs = i = 0 ;

/* On alloue le premier morceau. */ s = malloc ((++blocs)*LIGNE_MORCEAU*sizeof(char)) ; if (s == NULL) return -1 ;

while ((c=getchar())!=EOF && c!='\n') { s[pos] = c ; if (i==LIGNE_MORCEAU-1) { /* on déborderait en faisant ++i, donc on alloue plus de mémoire */ if ((s=realloc(s,(++blocs)*LIGNE_MORCEAU*sizeof(char))) == NULL) { return -1 ; /* plus de mémoire disponible: on quitte */ } i=0 ; } else { ++i; } ++pos ; }

/* si c == '\n' il faut l'ajouter */

if (c=='\n') { s[pos] = c ; /* on pourrait déborder en ajoutant le '\0': on gère ça */ if (i==LIGNE_MORCEAU-1) { if ((s=realloc(s,(pos+1)*sizeof(char))) == NULL) return -1 ; /* plus de mémoire disponible: on quitte */ } ++pos ; }

s[pos]='\0' ; *p=s ; return pos ;

} </source>

Ensuite, on donne un type pour les piles de chaînes de caractères, et les fonctions usuelles.

En-têtes pile.h: <source lang="C">

1. ifndef PILE_H
2. define PILE_H

typedef char data_t ;

typedef struct bloc_rec_t { data_t *data ; struct bloc_rec_t *suivant ; } bloc_t ;

typedef bloc_t *pile_t ;

/* Renvoie une pile vide */ pile_t pile_cree () ;

/* Teste si une pile est vide (1 si vide, 0 sinon) */ int pile_vide (pile_t p) ;

/* Empile la donnée d sur la pile *p.

* En cas de succès, renvoie la nouvelle valeur de *p. 
* Sinon, renvoie NULL (et alors *p est inchangé). */

pile_t pile_empile (pile_t *p, data_t *d) ;

/* Dépile la donnée au sommet de la pile.

* Renvoie NULL en cas d'échec (pile vide). */

data_t *pile_depile (pile_t *p) ;

1. endif

</source>

Code pile.c: <source lang="C">

1. include <stdlib.h>
2. include "pile.h"

pile_t pile_cree () { return NULL ; }

int pile_vide (pile_t p) { return (p == NULL) ; }

pile_t pile_empile (pile_t *p, data_t *d) { pile_t q = malloc (sizeof(bloc_t)) ; if (q != NULL) { q->data = d ; q->suivant = *p ; *p = q ; } return q ; }

data_t *pile_depile (pile_t *p) { pile_t q = *p ; data_t *d = NULL ; if (!pile_vide(q)) { d=q->data ; *p=q->suivant ; free(q) ; } return d ; } </source>

Le programme principal test_pile.c: <source lang="C">

1. include <stdio.h>
2. include <stdlib.h>
3. include "ligne.h"
4. include "pile.h"

/* Lit des lignes, puis les affiche de la dernière à la première */ int main () { char *l ; pile_t p = pile_cree() ; int ret ;

printf("Tapez des lignes\n") ; while ((ret=lit_ligne(&l))>0) { pile_empile(&p,l) ; } if (ret<0) return -1 ; while(!pile_vide(p)) { l=pile_depile(&p) ; printf("%s",l) ; free(l) ; } return 0 ; } </source>

Makefile

Pour compiler le tout (avec les options usuelles), il faudrait écrire

 $ gcc -Wall -pedantic -o test_pile test_pile.c pile.c ligne.c 

et même, de manière plus modulaire:

 $ gcc -Wall -pedantic -o pile.o -c pile.c
 $ gcc -Wall -pedantic -o ligne.o -c ligne.c
 $ gcc -Wall -pedantic -o test_pile.o -c test_pile.c
 $ gcc -Wall -pedantic -o test_pile test_pile.o pile.o ligne.o

Ça devient fastidieux. L'outil make a été conçu pour ce genre de situation.

On peut écrire le fichier Makefile:

 CC=gcc
 CFLAGS=-Wall -pedantic
 all: test_pile
 test_pile: pile.o ligne.o test_pile.o
 	$(CC) $(CFLAGS) -o test_pile $^
 clean:
 	rm -f pile.o ligne.o test_pile.o test_pile 

et alors la commande make fait le nécessaire:

 $ make
 gcc -Wall -pedantic   -c -o pile.o pile.c
 gcc -Wall -pedantic   -c -o ligne.o ligne.c
 gcc -Wall -pedantic   -c -o test_pile.o test_pile.c
 gcc -Wall -pedantic -o test_pile test_pile.o pile.o ligne.o

La syntaxe des Makefile décrit des dépendances sous la forme:

 cible: dependance_1 dependance_2 ... dependance_n
   commande

c'est-à-dire: pour fabriquer cible j'ai besoin des fichiers dependance_? et j'appelle la commande commande.

On peut définir des variables (première ligne) et il existe des cibles spéciales (all et clean) qui ne produisent pas de fichier au nom de la cible.

Notez que la conversion des *.o aux *.c est faite automatiquement (et utilise les variables CC et CFLAGS): ceci correspond à des règles par défaut de make. De la même manière, la commande après la ligne test_pile: ... est facultative: quelque chose de similaire serait fait automatiquement par make.

La syntaxe des Makefiles est assez riche et puissante: la lecture de la documentation est conseillée. On utilisera tout ça en TP.

Exercices en TD

Feuille 2.