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 précédente - Page générée en 0.00173 sec.

Recherche personnalisée
1840207 visiteurs. ©2001-2023 All Rights Reserved to Software-DS.com		Confidentialité