Après avoir géré au TP4 un tableau de lignes de texte, on va gérer des textes reliés par des pointeurs.
soient :
typedef char texte[80];
typedef struct boite
{
texte nom;
struct boite * pp;
struct boite * pg;
}boite;
boite * racine;
J'explique ce qu'il y a dans une boite (un nom et deux adresses, pp pointe sur UN plus petit (dans l'ordre alphabétique) mais pas nécéssairement le plus petit ni le "juste plus petit", pg vers un plus grand). A partir de 6 boites, je dessine un graphe avec plein de liens.
Maintenant je demande de créer 3 boites, sous forme d'un arbre : jacques fred max
Remarque : ne pas oublier les fichiers entêtes en début du fichier !
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void main (void)
{
boite a,b,c;
racine=&a;
strcpy(a.nom,"jacques");
a.pp=&b;
a.pg=&c;
strcpy(b.nom,"fred");
b.pp=b.pg=NULL;
strcpy(c.nom,"max");
c.pp=c.pg=NULL;
}
évidement, c'est bien beau mais on ne peut rien vérifier. Créons donc une fonction affiche1 à qui l'on donne l'adresse d'une boite, et qui en affiche le nom, ainis que le nom du pp (s'il existe) et du pg (s'il existe).
Donc en rajoutant au bout de main :
affiche1(racine); affiche1(racine->pp); affiche1(racine->pg);
j'aimerai qu'il m'affiche :
nom : jacques, plus petit : fred, plus grand : max nom : fred, pas de plus petit, pas de plus grand nom : max, pas de plus petit, pas de plus grand
void affiche1(boite *p)
{
printf("nom : %s, ",p->nom);
if(p->pp) printf("plus petit : %s, ",p->pp->nom);
else printf("pas de plus petit, ");
if(p->pg) printf("plus grand : %s\n",p->pg->nom);
else printf("pas de plus grand\n");
}
Pour que plus tard je puisse créer un graphe avec un nombre non imposé de boites, je ne veux plus déclarer a,b,c mais créer les boites par malloc. Le problème sera qu'on ne connait plus le nom des boites (a,b,c) mais on connaîtra quand même leur adresse.
void creation(void)
{
boite * nouv;
racine=(boite*)malloc(sizeof(boite));
strcpy(racine->nom,"jacques");
nouv=(boite*)malloc(sizeof(boite));
strcpy(nouv->nom,"fred");
nouv->pp=nouv->pg=NULL;
racine->pp=nouv;
nouv=(boite*)malloc(sizeof(boite));
strcpy(nouv->nom,"max");
nouv->pp=nouv->pg=NULL;
racine->pg=nouv;
}
void main(void)
{
creation();
affiche1(racine);
affiche1(racine->pp);
affiche1(racine->pg);
}
Maintenant je veux créer un graphe pour n'importe quel nombre de noms (mais plus d'1).
Proposition : on crée la racine comme avant. Puis les autres sont créés dans une boucle.
Je coupe le programme en deux sous-problèmes : créer une nouvelle boite, la placer parmi les autres. Pour placer, j'utilise un algorithme simple : je me place à la racine. supposons que le nouveau est plus petit. Alors soit pp est vide (NULL), j'y mets l'adresse du nouveau, soit elle est occupée, je vais à ce plus petit et je recommence (j'essaie de placer le nouveau sous celui-là, s'il y a une place je le mets sinon je redescend encore d'un cran).
void creation(void)
{
boite * nouv;
texte t;
racine=(boite*)malloc(sizeof(boite));
printf("nom du premier ?");
gets(racine->nom);
racine->pp=racine->pg=NULL;
do
{
printf("nom (Entrée pour finir)");
gets(t);
if (*t) /* premier caractère différent de \0 */
{
nouv=(boite*)malloc(sizeof(boite));
strcpy(nouv->nom,t);
nouv->pp=nouv->pg=NULL;
placer(nouv);
}
}
while(*t);
}
void placer(boite * v)
{
boite * w;
w=racine;
do
{
if(strcmp(v->nom,w->nom)<0)
if(w->pp) w=w->pp;
else
{w->pp=v;v=NULL;}
else
if(w->pg) w=w->pg;
else
{w->pg=v;v=NULL;}
}
while(v);
}
et maintenant il reste à afficher tous les noms contenus dans l'arbre (dans un premier temps dans n'importe quel ordre).
Proposition : afficher le sommet de l'arbre, puis son sous-arbre gauche, puis son sous-arbre droit.
void affiche(boite * x)
{
printf(" %s,",x->nom);
if(x->pp)affiche(x->pp);
if(x->pg)affiche(x->pg);
}
Remarque : si j'inverse les lignes de cette fonction, les noms sont toujours triés dans l'ordre alphabétique quel que soit leur ordre de saisie !
void affiche(boite * x)
{
if(x->pp)affiche(x->pp);
printf(" %s,",x->nom);
if(x->pg)affiche(x->pg);
}
retour au sommaire des travaux pratiques d'informatique.