Dijkstra算法分割故障 [英] Dijkstra algorithm segmentation fault
问题描述
我使用邻接列表创建Dijkstra算法程序。我的老师给我这个结构。
参数`nom`是顶点，`poids`是重量，`som_a`和`som_b`是顶点，`nbSommets `是顶点数，`nbArcs`是边数，`NB_SOM_MAX`是顶点数MAX。
我没有编译错误，当我执行时我的程序我有分段错误。
我尝试过：
I create a Dijkstra algorithm program using an adjacency list. My teacher give me this struct.
Where the argument `nom` is vertices, `poids` is weight, `som_a` and `som_b` are vertices, `nbSommets` is number of vertices, `nbArcs` is number of edges, `NB_SOM_MAX` is number of vertices MAX.
I don't have compilation errors and when I execute my program I have a segmentation fault.
What I have tried:
//list of couples (sommet,poids)
typedef struct maillon{
struct maillon *suiv;
int nom;
int poids;
} MAILLON, *LISTE;
//graph structure
typedef struct graphe{
int nbSommets;
LISTE Adj[NB_SOM_MAX]; //liste d'adjacence
} GRAPHE;
//insert (som_b, poids) At the top of the adjacency list Adj[som_a]
void insere(int som_a, int som_b, int poids, LISTE Adj[]){
LISTE prem=malloc(sizeof(LISTE));
prem->nom = som_b;
prem->poids = poids;
prem->suiv = Adj[som_a];
Adj[som_a] = prem;
}
//Initialization of the adjacency table: all lists are empty
void initAdjGraphe(GRAPHE *G){
int i;
for(i = 0; i < G->nbSommets; i++){
G->Adj[i] = NULL;
}
}
//Load a graph from a file
void litGraphe(char *adr, GRAPHE *G){
FILE *f;
int sa,sb,pds,nbArcs;
f=fopen(adr,"r");
fscanf(f,"%d",&(G->nbSommets));
initAdjGraphe(G);
fscanf(f,"%d",&nbArcs);
while(nbArcs){
fscanf(f,"%d %d %d",&sa,&sb,&pds);
insere(sa,sb,pds, G->Adj);
nbArcs--;
}
fclose(f);
}
//Displaying a graph
void afficheGraphe(GRAPHE G){
int j;
printf("%d\n", G.nbSommets);
for(j = 0; j < G.nbSommets; j++){
while(G.Adj[j]->suiv != NULL){
printf("%d %d %d\n",j, G.Adj[j]->nom, G.Adj[j]->poids);
G.Adj[j] = G.Adj[j]->suiv;
}
}
}
//Dijkstra algorithm: displays the shortest path between s and all vertices of G
void dijsktra(int s, GRAPHE G){
int i,j,dist[NB_SOM_MAX], INT_MAX, pred[NB_SOM_MAX], min, nb=0,nbmin=0;
LISTE S,F = G.Adj;
for(i = 0; i<g.nbsommets; i++){="" dist[i]="INT_MAX;" pred[i]="NULL;" }="" dist[0]="0;" s="NULL;" while(f="" !="NULL){" min="G.Adj[0]-">poids;
for(i = 1; i<g.nbsommets; i++){="" if(min=""> G.Adj[i]->poids){
min = G.Adj[i]->poids;
nbmin = i;
}
}
insere(nb, nbmin, min, &S);
nb++;
if(nbmin == 0){
F = F->suiv;
}
else{ // F[nbmin-1]->suiv = F[nbmin+1];
F[nbmin-1] = F[nbmin+1];
}
for(i = G.Adj[nbmin]->nom; i<g.nbsommets; i++){="" if(dist[i]=""> dist[nbmin] + G.Adj[nbmin]->poids){
dist[i] = dist[nbmin] + G.Adj[nbmin]->poids;
pred[i] = nbmin;
}
}
}
for(i = 0; i < G.nbSommets; i++){
printf("Chemin optimal de %d à %d : ", i, s);
printf("%d-", i);
j=i;
while(pred[j] != s || pred[j] != NULL){
printf("%d-", pred[j]);
j=pred[j];
}
printf("\n");
}
}
int main(void){
GRAPHE G;
litGraphe("./graphe.txt", &G);
afficheGraphe(G);
dijsktra(0, G);
return 0;
}
推荐答案
您应该学习尽快使用调试器。而不是猜测你的代码在做什么，现在是时候看到你的代码执行并确保它完成你期望的。
调试器允许你跟踪执行逐行检查变量，你会看到它有一个停止做你期望的点。
调试器 - 维基百科，免费的百科全书 [ ^ ]
掌握Visual Studio 2010中的调试 - A初学者指南 [ ^ ]
调试器在这里向您展示您的代码正在做什么，您的任务是与它应该做什么进行比较。 />
调试器中没有魔法，它没有发现错误，它只是帮助你。当代码没有达到预期效果时，你就接近了一个bug。
[Français]
1）Ton code n 'est pas autonome，donc personne（ici）ne peut le compiler pour voir ce qui ce passe。
2）
You should learn to use the debugger as soon as possible. Rather than guessing what your code is doing, It is time to see your code executing and ensuring that it does what you expect.
The debugger allow you to follow the execution line by line, inspect variables and you will see that there is a point where it stop doing what you expect.
Debugger - Wikipedia, the free encyclopedia[^]
Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't find bugs, it just help you to. When the code don't do what is expected, you are close to a bug.
[Français]
1) Ton code n'est pas autonome, donc personne (ici) ne peut le compiler pour voir ce qui ce passe.
2)
我有分段错误。
Ca veux dire que ton program essaie d'écrireàunendroit qui ne lui appartient pas。 Soittuécrisaprèslafin d'un tableau，soit tu利用un pointeur qui n'stpasinitialisé。
3）利用le debugger，enexécutanttonprogram pas àpas，tu pourra localiser l'endroitouçaplatte。 Avec le debugger，tu pourras inspecter les variables pendant l'éxécution。
Ca veux dire que ton programme essaie d'écrire à un endroit qui ne lui appartient pas. Soit tu écris après la fin d'un tableau, soit tu utilise un pointeur qui n'est pas initialisé.
3) Utilise le debugger, en exécutant ton programme pas à pas, tu pourra localiser l'endroit ou ça plante. Avec le debugger, tu pourras inspecter les variables pendant l'éxécution.
通过阅读代码（我试过）通常很难找到源代码。甚至可以通过从文件加载无效值来获取它。这看起来很可疑，因为您正在从文件中读取索引（第一个弧线值）。当这个超出范围或没有所有索引的行时，您的代码将在以后崩溃（缺少索引，结构中将有NULL条目）。
所以我建议添加检查以验证参数和变量是否有效。
快速的第一种方法可能是使用 assert - C ++ Reference [ ^ ]。
代码的一些示例：
It is often difficult to find the sources by just reading the code (I tried it). It may be even sourced by loading invalid values from the file. This looks suspicious because you are reading the index from the file (first arc line value). When this out of range or there are not lines for all indexes, your code will crash later (with missing indexes there will be NULL entries in your struct).
So I suggest to add checks to verify that parameters and variables are valid.
A quick first approach might be using assert - C++ Reference[^].
Some examples for your code:
#include <assert.h>
void insere(int som_a, int som_b, int poids, LISTE Adj[]){
assert(som_a >= 0 && som_a < NB_SOM_MAX);
/* EDIT: Must be off course Adj
assert(LISTE != 0);
*/
assert(Adj != 0);
LISTE prem=malloc(sizeof(LISTE));
prem->nom = som_b;
prem->poids = poids;
prem->suiv = Adj[som_a];
Adj[som_a] = prem;
}
void initAdjGraphe(GRAPHE *G){
assert(G);
assert(G->nbSommets < NB_SOM_MAX);
int i;
for(i = 0; i < G->nbSommets; i++){
G->Adj[i] = NULL;
}
}
对于 initAdjGraphe（）设置所有内容会更好项目到 NULL 。
最终实现将返回错误代码和/或打印错误消息：
For initAdjGraphe() it would be even better to set all items to NULL.
A final implementation would return an error code and/or print an error message:
int insere(int som_a, int som_b, int poids, LISTE Adj[]){
if (som_a < 0 || som_a >= NB_SOM_MAX)
{
printf("som_a value %d is invalid\n", som_a);
return -1;
}
/* EDIT: Again it must be Adj
if (LISTE == 0)
*/
if (Adj == 0)
{
printf("Adj is NULL\n");
return -1;
}
/* ... */
return 0;
}
这篇关于Dijkstra算法分割故障的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
