TP7 questions 1-2-3

 /*
TP7 26/12/02 - 27/12/02
http://www.Software-DS.com
*/

#include <stdio.h>
#include <Carbon.h> /* Sur Mac Seulement , sur PC: stlib.h*/

typedef int Element;
/* Graphe */
typedef struct Noeud {
Element Sommet;
struct Noeud * Suivant;
};
typedef struct Noeud * Liste;
typedef Liste Graphe[10];

/* file d'attente */
typedef struct Cellule {
Element Valeur;
struct Cellule * Suivant;
}Cellule;
typedef struct Cellule * file;Graphe t;

/* Prototypes pour le graphe */
void Creer_Liste(Liste *L);
void Ajouter(Liste *P, Element x);
void Afficher(Liste L);

/* prototypes pour la file */
file creer_file(file p);
file emfiler(file p, Element x);
file defiler(file p);
Element sommet(file p);
int file_vide(file p);
int Appartient(file p,Element x);

/* ©2002-2003 All Rights Reserved to Didier STRAUS http://www.Software-DS.com */
/* Question 1 */
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;
}

/* Question 2 */
void affiche_voisin(Graphe t,Element s){
/* Je considere qu'on va trouver ce que l'on cherche ! */
int i=-1;

do{
i++;
} while (t[i]->Sommet!=s);
Afficher(t[i]);
}

/* Question 3 Parcours en Largeur */
void PL(Graphe t){
/* pour tester cette fonction il est essentiel de la tester avec un vrai graphe */
/* si vous saisissez n'importe quelle valeurs pour votre graphe */
/* la fonction recherche du sommet ne fonctionnera pas et cela va planter ! */
/* Exemple de graphe: 1,2,3 / 2,1,4 / 3,1,4 / 4,2,3 */
file a_voir,deja_vue;
Element k;

a_voir=creer_file(a_voir);
deja_vue=creer_file(deja_vue);
k=t[0]->Sommet;
a_voir=emfiler(a_voir,k);
printf("%d,",k);

while(file_vide(a_voir)==0) { /* tant que la file n'est pas vide */
int i;
Liste Q;
Element e;

e=sommet(a_voir);
a_voir=defiler(a_voir);
deja_vue=emfiler(deja_vue,e);

/* on cherche le sommet */
i=-1;
do{
i++;
} while (t[i]->Sommet!=e);

/* on enfile tous ces voisins */
Q=t[i];
if (Q!=NULL)
Q=Q->Suivant; /* on saute le sommet pour passer à ces voisins */
while((Q)!=NULL) {
if (Appartient(deja_vue,Q->Sommet)==1) {
printf("%d,",Q->Sommet);
a_voir=emfiler(a_voir,Q->Sommet); /* on enfile les voisins si cela n'est pas deja fait */
}
Q=Q->Suivant;
}
}
}

int main(void) {
int i;

creer_graphe(t);
printf("Affichage des voisins du sommet ?");
scanf("%d",&k);
affiche_voisin(t,k);

printf("\nParcours en largeur:\n");
PL(t);


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 */
}

/* ©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) {
/* Attention cette fonction est différente de celle du prof mais au moins elle fonctionne ! ! ! */
Liste Q,R;

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;
}
}

/* Affichage de la Liste L */
void Afficher(Liste L) {
Liste Q;

Q=L;
if (Q!=NULL) {
printf("Les voisins de %d sont : ",Q->Sommet);
Q=Q->Suivant;
}
while((Q)!=NULL) {
printf("%d,",Q->Sommet);
Q=Q->Suivant;
}
}

/* file d'attente */

/* Cree une file */
file creer_file(file p){
return(NULL);
}

/* Ajout d'un nouvel Element au sommet de la file: */
file emfiler(file p, Element x){
file Q,R;

Q=(file)malloc(sizeof(Q));
Q->Valeur=x;
Q->Suivant=NULL;

if (p==NULL)
p=Q;
else {
R=p;
while(R->Suivant!=NULL) {
R=R->Suivant;
}
R->Suivant=Q;
}
return(p);
}

/* Suppression de l'Element du sommet de la file */
file defiler(file p){
file Q;

Q=p;
p=p->Suivant;
/* free(Q);*/
return(p);
}

/* Consultation du sommet de la file p */
Element sommet(file p){
return(p->Valeur);
}

/* Test de l'etat d'une file, renvoie 1 si la file est vide */
int file_vide(file p){
if (p==NULL)
return(1);
else
return(0);
}

int Appartient(file p,Element x){
/* x appartient à p => 0 sinon 1 */
file Q;

Q=p;
while(p!=NULL){
if (p->Valeur==x)
return 0;
p=p->Suivant;
}
return 1;
}
/* ©2002-2003 All Rights Reserved to Didier STRAUS http://www.Software-DS.com */