Dijkstra를 구현하려고 시도했지만 의미가없는 분할 오류가있는 경우

Question

Dijkstra 함수에서 정보 필드가있는 우선 순위 대기열 nperm을 초기화하고 노드가 영구 세트가 아닌지 여부를 알려줍니다.

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

거리 : 나는 실제로 초기화가 이루어집니다 어떻게 모든 노드가 notpermanent set.This의 구성원 인 그 그래프 노드와 다음 pointer.Initially 포인터 (배열 인덱스)를 저장하는 'I'필드가 [i]는 기본적으로 지금까지 알려진 루트 노드에서 노드 i까지의 거리이므로 알고리즘이 진행됨에 따라 거리가 업데이트되므로 거리에 따라 우선 순위 큐 nperm의 순서가 변경되어야합니다. 우선 순위 대기열의 포인터에 대한 포인터를 전달하고 동일한 유형의 다른 변수 인 notperm p; p = *pq;에 해당 포인터의 값을 저장합니다. 우선 순위 대기열의 모든 노드는 해당 포인터의 색인을 포함하는 필드 'i'를 가지므로 그래프 노드, 나는 그 거리가 최근에 업데이트 된 노드까지리스트를 가로 지르며 그 노드를 제거하고 그 노드를 오름차순 우선 순위 큐에 놓는다.

while ((p->i) != s) 문을 사용하여 노드를 트래버스하지만 세분화 오류가 발생합니다. 그 중 일부는 잘 모릅니다. p->i을 사용하여 "i"에 액세스 할 때 세그먼트 오류가 발생하는 것 같습니다.

누구든지 내게 설명 할 수 있습니까? 당신이 p가 가리키는리스트의 끝을 실행하는 것처럼

#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->next에 대해 NULL입니다. 그런 다음 p = p->next을 설정하고 NULLp 포인터를 비 참조 화하여 세그먼트 화 오류를 일으 킵니다.

해결 방법은 p->i을 확인하기 전에 NULLp을 확인하는 것입니다.