Discussion :

[raphio000]

Voila, j'ai un petit problème.
Je fais un petit programme qui créé un graphe, qui ajoute des arcs à ce graphe et qui en supprime.
La crétion du graphe et des arcs fonctionnent mais la suppression d'un arc ne marche pas.
En effet lorsque je free un des pointeurs de la liste d'arc, au lieu d'etre supprimé le sommet est remplacé par 0 ?????
Voila le code ce sera plus simple à comprendre.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <stdio.h>
#include<stdlib.h>
#define N 5
struct element{
	int numSommet;
	struct element *suivant;
};
 
typedef struct element * liste;
 
void creerSommet(liste ls[]){
	liste tmp;
	int i;
	for (i=0;i<N;i++){
		tmp=malloc(sizeof(struct element));
 
		tmp->numSommet=i;
		tmp->suivant=NULL;
		ls[i]=tmp;
 
	}
}
 
void ajouterArc(liste ls[],int ori,int desti){
	liste tmp,ptr;
	tmp=ls[ori];
	ptr=malloc(sizeof(struct element));
	ptr->numSommet=desti;
	ptr->suivant=tmp->suivant;
	tmp->suivant=ptr;
}
 
void supprimerArc(liste ls[],int ori,int desti){
	liste tmp,tmp2;
	tmp=ls[ori];
	if (tmp->suivant!=NULL){
 
		while(tmp->numSommet!=desti){
			tmp=tmp->suivant;
		}
		tmp2=tmp;
		tmp=tmp->suivant;
		free(tmp2);
	}
}
 
void afficherGraphe(liste ls[]){
	int i;
	liste tmp;
	for(i=0;i<N;i++){
		tmp=ls[i];
		while(tmp!=NULL){
			printf("%d ",tmp->numSommet);
			tmp=tmp->suivant;
		}
		printf("\n");
	}
}
 
int main(){
	liste ls[N];
 
	creerSommet(ls);
	ajouterArc(ls,1,2);
	ajouterArc(ls,1,3);
	ajouterArc(ls,2,4);
	ajouterArc(ls,4,1);
	ajouterArc(ls,4,0);
	ajouterArc(ls,0,0);
	ajouterArc(ls,0,3);
	afficherGraphe(ls);
	printf("--------------------\n");
	supprimerArc(ls,1,3);
	afficherGraphe(ls);
	return 1;
}

MErci d'avance !!

[acx01b]

salut

tu as quelques petits problèmes avec les listes chainées, et aussi avec les moyens de représenter un graphe en mémoire !!

si tu commençais par changer ta fonction d'initialisation ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
void creerSommet(liste *graphe){	
             int i;
	for (i=0;i<N;i++){
	      graphe[i]=NULL;
	}
}

(au départ il n'y a pas d'arc dans ton graphe)

ensuite pour supprimer un élément d'une liste chainée (c'est une des façons de faire):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
liste supprimer(liste l, int numSommet) {
     liste l2,l3;
     if (l == NULL) return NULL;
     if (l->numSommet == numSommet) {
          l2 = l->suivant;
          free(l);
          return l2;
     }
     l3 = l2 = l;
     l = l->suivant;
     while(l) {
        if (l->numSommet == numSommet) {
            l2->suivant = l->suivant;
            free(l);
            return l3;
        }
        l2 = l;
        l = l->suivant;
     }
     return l3;
}