TP7 question 4
| /* TP7 question:4 - 31/12/02-10/01/02 http://www.Software-DS.com */ #include <stdio.h> #include <stdlib.h> typedef int Element; /* Graphe */ typedef struct Noeud { Element Sommet; struct Noeud * Suivant; }; typedef struct Noeud * Liste; typedef Liste Graphe[10]; Graphe t; int couleur[5]={0,0,0,0,0}; /* valeur=0 -> non visiter ; valeur=1 -> deja visiter */ /* j'utilise ici un tableau pour memoriser les couleurs des noeuds, en vrai il faudrait utiliser */ /* une liste chainée ou une pile, mais pour gagner du temps, j'ai préféré utiliser un tableau :p */ /* Prototypes pour le graphe */ void Creer_Liste(Liste *L); void Ajouter(Liste *P, Element x); void Afficher(Liste L); void creer_graphe(Graphe t){ Element s,n; int i=0; do{ Liste L; printf("\nSommet = ?"); scanf("%d",&s); if (s>0) { Creer_Liste(&L); Ajouter(&L,s); /* on va maitenant ajouter ses voisins */ do{ printf("voisin= ?"); scanf("%d",&n); if (n>0) Ajouter(&L,n); } while (n>0); t[i]=L; i++; } } while (s>0); t[i]=NULL; } /* ©2002-2003 All Rights Reserved to Didier STRAUS http://www.Software-DS.com */ /* Question 4 Parcours en profondeur recursif */ void PPR(Element x){ int i; Liste Q; /* on recherche la position du Sommet x */ i=-1; do { i++; } while (t[i]->Sommet!=x); Q=t[i]; if (Q!=NULL) { couleur[Q->Sommet]=1; printf("%d,",Q->Sommet); Q=Q->Suivant; /* on saute le sommet pour passer à ces voisins */ } /* pour chaque voisin immediat : PPR */ while((Q)!=NULL) { /* on verifie qu'on a pas deja visiter le sommet ? */ if (couleur[Q->Sommet]==0) PPR(Q->Sommet); /* Appel recursif */ Q=Q->Suivant; } } int main(void) { creer_graphe(t); printf("Parcours en profondeur recursif:\n"); PPR(t[0]->Sommet); printf("\n\n©2002-2003 All Rights Reserved to http://www.Software-DS.com\n"); return 0; /* ©2002-2003 All Rights Reserved to Didier STRAUS http://www.Software-DS.com */ } /* Cree une Liste */ void Creer_Liste(Liste *L) { *L=NULL; } /* Ajout d'un nouvel Element dans la Liste: */ void Ajouter(Liste *P, Element x) { Liste Q,R; int j; Q=(Liste)malloc(sizeof(Q)); Q->Sommet=x; Q->Suivant=NULL; if (*P==NULL) *P=Q; else { R=*P; while(R->Suivant!=NULL) { R=R->Suivant; } R->Suivant=Q; } } /* ©2002-2003 All Rights Reserved to Didier STRAUS http://www.Software-DS.com */ |
Haut de la page - Page générée en 0.00135 sec.
|
||||||
