c - 尝试实现 Dijkstra，但存在毫无意义的段错误

Question

在函数 Dijkstra 中，我初始化了一个优先级队列 nperm，它有一个信息字段；它告诉节点是否是集合 notpermanent 的成员。然后我有一个“i”字段，它实际上存储指针(数组索引)到该图节点和下一个指针。最初，每个节点都是非永久集的成员。这是初始化的完成方式:

for (i = graph; hnode[i].next >= 0;) 
{
    insertnperm(&nperm, 1, i);
    distance[i] = 500000;
    i = hnode[i].next;
}

Distance[i] 基本上是迄今为止已知的节点 i 与根节点的距离，因此随着算法的进行，距离会更新，因此基于距离的优先级队列 nperm 的顺序也应该更新。现在按照函数顺序，我将一个指针传递给优先级队列的指针，并将该指针的值存储在另一个相同类型的变量中，notperm p; p = *pq;，由于优先级队列中的每个节点都有一个字段“i”，其中包含图节点的索引，因此我遍历列表直到最近更新了距离的节点，然后删除并放置该节点节点在优先级升序队列中的正确位置。

我使用语句while ((p->i) != s)来遍历节点，但是出现了段错误，我不知道。当我使用 p->i 访问“i”时，似乎发生了段错误。

谁能给我解释一下为什么会发生这种情况？

这是完整的代码:

#include<stdio.h>
#include<conio.h>
#define MAXNODES 50

struct header 
{   
    int info;     
    int epoint;     
    int tpoint;     
    int next;     
};

struct header hnode[MAXNODES];     
int i = 0;

struct arcs 
{     
    int info;     
    int epoint;     
    int tpoint;     
    int enext;     
    int tnext;     
};     
int j = 0;     
struct arcs anode[MAXNODES]; 

struct node 
{     
    int info;     
    int i;     
    struct node *next;     
};     
typedef struct node *notperm;     

notperm npgetnode(void)
{     
    notperm p;     
    p = (notperm) (malloc(sizeof(struct node)));     
    return p;     
}          

int hgetnode()
{     
    int k;     
    k = i++;     
    return k;     
}   

int agetnode()
{     
    int k;     
    k = j++;     
    return k;     
}  

void hfreenode(int r)
{     
    --i;     
}     
void afreenode(int r)
{     
    --j;     
}

int addnode(int *pgraph, int x)
{     
    int p;     
    p = hgetnode();     
    hnode[p].info = x;     
    hnode[p].epoint = -1;     
    hnode[p].tpoint = -1;     
    hnode[p].next = *pgraph;     
    *pgraph = p;     
    return p;     
} 

void joinwt(int p, int q, int wt)
{    
    int r, r2;     
    int t, t2;     
    r2 = -1;     
    r = hnode[p].epoint; 

    while (r >= 0 && anode[r].epoint != q) 
    {     
        r2 = r;     
        r = anode[r].enext;     
    }        
    if (r >= 0) 
    {     
        anode[r].info = wt;     
    }         
    if (r < 0) 
    {    
        r = agetnode();     
        anode[r].epoint = q;     
        anode[r].tpoint = -1;     
        anode[r].enext = -1;     
        anode[r].tnext = -1;     
        anode[r].info = wt;     
        (r2 < 0) ? (hnode[p].epoint = r) : (anode[r2].enext = r);   
    }

    /*updation to q */

    t = hnode[q].tpoint;     
    t2 = -1;     
    while (t >= 0 && anode[r].tpoint != p) 
    {     
        t2 = t;     
        t = anode[t].tnext;     
    }     
    if (t >= 0) 
    {     
        anode[t].info = wt;     
    }   
    if (t < 0) 
    {     
        t = agetnode();     
        anode[t].tpoint = p;     
        anode[t].epoint = -1;   
        anode[t].tnext = -1;     
        anode[t].enext = -1;     
        anode[t].info = wt;     
        (t2 < 0) ? (hnode[q].tpoint = t) : (anode[t2].tnext = t);     
    }   
}

void insertnperm(notperm * pq, int x, int currep)
{     
    notperm p;     
    if (*pq == NULL)     
    {     
        *pq = (notperm) (malloc(sizeof(struct node)));     
        (*pq)->info = x;     
        (*pq)->i = currep;     
        (*pq)->next = NULL;     
        return;     
    }     
    p = npgetnode();     
    p->info = x;     
    p->i = currep;     
    p->next = (*pq);     
    *pq = p;     
}       

void order(notperm * pq, int s, int distance[])
{     
    notperm p, q, j;     
    q = NULL;     
    p = NULL;     
    p = *pq;     
    while ((p->i/*this statement always ends up with a segmentation fault*/) != s) 
    {     
        q = p;     
        p = p->next;     
    }     
    if (q == NULL)     
        *pq = p->next;     
    else     
        q->next = p->next;     
    q = NULL;     
    for (j = *pq; distance[(j->i)] < distance[(p->i)]; j = j->next)     
    q = j;     
    if (q == NULL) {     
        p->next = *pq;     
        *pq = p;     
    }     
    else     
    {     
        p->next = q->next;     
        q->next = p;     
    }     
}  

void chngstozero(notperm * pq, int s)
{     
    notperm p;     
    for (p = *pq; (p->i) != s; p = p->next);    
         p->info = 0;     
    }     
    int checkstat(notperm * pq, int s)
    {     
        notperm p;   
        for (p = *pq; (p->i) != s; p = p->next);     
        return (p->info);     
    }          
    int newminel(notperm * pq)
    {     
        notperm p;     
        for (p = *pq; (p->info) != 1; p = p->next);     
        p->info = 0;     
        return (p->i);     
    }        

    void Dijkstra(int graph, int s, int t, int *pd)
    {     
        unsigned int distance[MAXNODES], precede[MAXNODES];     
        int current, i, k, dc, currep;     
        unsigned int smalldist, newdist;     
        notperm p;     
        notperm nperm;    
        nperm = NULL;
        for (i = graph; hnode[i].next >= 0;) 
        {    
            insertnperm(&nperm, 1, i);    
            distance[i] = 500000;    
            i = hnode[i].next;
        }     
        distance[s] =0; 
        order(&nperm, s, distance);    
        chngstozero(&nperm, s);
        current = s;
        while (current != t) 
        {
            smalldist = 500000;
            dc = distance[current];
            for (currep = hnode[current].epoint; anode[currep].enext >= 0; currep = anode[currep].enext) 
            {
                if (checkstat(&nperm, currep)) 
                {
                    newdist = dc + anode[currep].info;
                    if (newdist < distance[currep]) 
                    {
                        distance[currep] = newdist;
                        order(&nperm, currep, distance);
                        precede[currep] = current;
                    }
                }
            }

main()
{
    int graph,a,b,c,d,e,wt,r,t,pd;
    graph=-1;
    int wt1=5;
    int wt2=3;
    int wt3=6;
    int wt4=2;
    int wt5=7;
    a=addnode(&graph,4);
    b=addnode(&graph,6);
    c=addnode(&graph,8);
    d=addnode(&graph,9);
    e=addnode(&graph,5);
    joinwt(a,b,wt);
    joinwt(a,c,wt1);
    joinwt(a,d,wt2);
    joinwt(a,e,wt3);
    joinwt(d,b,wt4);
    joinwt(c,e,wt5); 
    Dijkstra(graph,a,e,&pd);
    printf("%d",pd);

    getch();
    return 0;
}

Answer 1

while ((p->i/*this statement always ends up with a segmentation fault*/) != s) {
    q = p;
    p = p->next;
}

看起来您正在运行 p 指向的列表末尾。最后一个元素将为 p->next 提供一个 NULL；然后，您设置 p = p->next 并尝试取消引用 NULL p 指针，从而导致段错误。

解决方案是在检查 p->i 之前先检查 NULL p。