前提・実現したいこと
struct node( int element, struct node next);
struct node p;
のようなノードで線形リストで
p
↓
[0]->[1]->[2]
というよなelementの要素が入ったリストを作り
while(p != NULL) {
p = p->next;
}
とし
p->element = 2のとき
p = p->next;
とするとセグメントエラーになってしまいました。
これはNULLを参照してしまったからでしょうか?
いつもはこの様な方法でもおそらくNULLがそのまま代入されてセグメントエラーになってなかったと思うのですが
今回のプログラムではセグメントエラーになってしまいました。
関数dijkstraの局所局所にprint文を入れてどこでエラーなるかチェックしたところ
adjlist[cur] = adjlist[cur]->next;の手前まで出力されていたためこれが原因かと思っていました。。
C
1#include<stdio.h> 2#include<stdlib.h> 3#include<limits.h> 4#define ROSENZU "rosenzu.txt" /* 路線図データファイル */ 5#define SETMAX 10600 /* 集合の要素数の最大値 (駅の数) */ 6char buf[256]; /* 入力された文字列を格納するグローバル変数 */ 7 8int dist[SETMAX]; /* 指定された駅から各駅までの最短距離を格納するグローバル変数 */ 9 10struct node { int eki, rosen, kyori; struct node *next; }; 11struct set { int elements[SETMAX]; int size; }; 12 13void init_set(struct set *p, int n, int e) { 14 int i, j=0; 15 p->size = n-1; 16 for(i = 0; i < p->size; i++) { 17 if(j == e) 18 j++; 19 p->elements[i] = j++; 20 } 21} 22 23int delete_min(struct set *p) { 24 int i=0, j, min = dist[p->elements[0]];//一回ループを省力するため添字0の値を\ 25代入しておく 26 if(p->size == 0) //空集合の場合 27 return -1; 28 else 29 for(j=1; j < p->size; j++) { //一番小さい値の添字の探索 30 if(dist[p->elements[j]] < min) { 31 min = dist[p->elements[j]]; 32 i = j; 33 } 34 } 35 min = p->elements[i]; //minにはreturnする要素を格納 36 p->elements[i] = p->elements[p->size -1]; //最小値の場所に格納 37 p->size--; 38 return min; 39} 40 41//一方向の経路の挿入 42struct node* insert_edge(struct node *list, int eki, int rosen, float kyori) { 43 struct node *n; 44 n = (struct node*)malloc(sizeof(struct node)); 45 n->eki = eki; 46 n->rosen = rosen; 47 n->kyori = kyori; 48 n->next = list; 49 return n; 50} 51 52void add_edge(struct node *adjlist[], int eki1, int eki2, int rosen, int kyori) { 53 adjlist[eki1] = insert_edge(adjlist[eki1], eki2, rosen, kyori); 54 adjlist[eki2] = insert_edge(adjlist[eki2], eki1, rosen, kyori); 55} 56 57int dijkstra(struct node *adjlist[], int eki1, int eki2, int ekisu) { 58 int i, cur; //cur:直前に最短距離が確定した駅の変数 59 struct set unknown; 60 for(i=0; i<ekisu; i++) { //到達可能かわからない要素をINT_MAXにする 61 if(i == eki1) 62 dist[i] = 0; 63 else 64 dist[i] = INT_MAX; 65 } 66 cur = eki1; 67 init_set(&unknown, ekisu, cur); 68//セグメントエラー確認のためここでリストを巡回させるとやはりエラーになった////////////////////// 69 while(adjlist[eki1] != NULL) { 70 adjlist[eki1] = adjlist[eki1]->next; 71 printf("%d->%d\n",adjlist[eki1],adjlist[eki1]->next); 72 } 73 //////////////////////////////////////////////////////////////// 74 75 76 while(unknown.size !=0 || cur != eki2) { 77 while(adjlist[cur] != NULL) { 78 printf("dist[%d] + adjlist[%d]->kyori < dist[%d] = %d + %d < %d\n",cur,cur,adjlist[cur]->eki,dist[cur],adjlist[cur]->kyori,dist[adjlist[cur]->eki]); 79 if(dist[cur] + adjlist[cur]->kyori < dist[adjlist[cur]->eki]) 80 dist[adjlist[cur]->eki] = dist[cur] + adjlist[cur]->kyori; 81 printf("next\n"); 82printf("eki = %d, next = %d\n", adjlist[cur]->eki, adjlist[cur]->next->eki); 83 printf("%d\n",adjlist[cur]->next); 84 adjlist[cur] = adjlist[cur]->next; //この前までのprintは出力された 85 printf("eki = %d, next = %d\n", adjlist[cur]->eki, adjlist[cur]->next->eki); 86 } 87 printf("srgsrgs\n"); 88 cur = delete_min(&unknown); //集合unknownの最短距離の駅をcurに格納 89 printf("are\n"); 90 } 91 printf("1\n\n"); 92 return dist[eki2]; 93} 94 95int main() { 96 int eki1, eki2, rosen, ekisu, i, kyori; 97 FILE *fp = fopen(ROSENZU,"r"); /* 路線図ファイルを読む準備 */ 98 fscanf(fp, "%d ", &ekisu); /* 1行めの駅数を読取り */ 99 struct node *adjlist[ekisu]; 100 /* 隣接リスト表現を初期化.すべての頂点に対する隣接リストを空にする */ 101 for(i=0;i<ekisu;++i) adjlist[i] = NULL; 102 while(fgets(buf,sizeof(buf),fp)!=NULL) { 103 /* 隣り合う駅の情報を読取り */ 104 sscanf(buf, "%d:%d:%d:%d␣", &eki1, &eki2, &rosen, &kyori); 105 /* そのデータを隣接リスト表現のグラフに追加 */ 106 add_edge(adjlist, eki1, eki2, rosen, kyori); 107 } 108 fclose(fp); 109 scanf("%d %d ", &eki1, &eki2); 110 printf("%d\n", dijkstra(adjlist, eki1, eki2, ekisu)); 111 /* for(i=0;i<ekisu;++i) 112 if(dist[i] < INT_MAX) 113 printf("%d: %d\n", i, dist[i]); */ 114 return 0; 115} 116
回答1件
あなたの回答
tips
プレビュー