0

関数Dijkstraで、情報フィールドを持つ優先度付きキューnpermを初期化します。これは、ノードがセットのメンバーであるかどうかを示します。次に、実際にポインター（配列インデックス）を格納する「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)てノードまでトラバースしますが、セグメンテーション違反が発生します。これについてはわかりません。を使用して「i」にアクセスすると、セグメンテーション違反が発生するようですp->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;
}
4

1 に答える 1

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

が指すリストの最後まで実行しているようですp。最後の要素にはNULLfor がp->nextあります。次にp = p->next、ポインターを設定して逆参照しようとするとNULL p、セグメンテーション違反が発生します。

解決策は、 に対してチェックするNULL p前に、 もチェックすることp->iです。

于 2013-02-02T19:59:05.403 に答える