teratail
回答率
85.48%
質問するログイン新規登録
トップに関する質問線形リストでセグメントエラーになってしまいます。

編集履歴

質問編集履歴

4

tuiki

2019/01/30 05:50

投稿

apeirogon0813
apeirogon0813

スコア117

test CHANGED
File without changes
test CHANGED
@@ -38,6 +38,12 @@
38
38
 
39
39
  今回のプログラムではセグメントエラーになってしまいました。
40
40
 
41
+
42
+
43
+ 関数dijkstraの局所局所にprint文を入れてどこでエラーなるかチェックしたところ
44
+
45
+ adjlist[cur] = adjlist[cur]->next;の手前まで出力されていたためこれが原因かと思っていました。。
46
+
41
47
  ```C
42
48
 
43
49
  #include<stdio.h>

3

tuiki

2019/01/30 05:50

投稿

apeirogon0813
apeirogon0813

スコア117

test CHANGED
File without changes
test CHANGED
@@ -174,7 +174,9 @@
174
174
 
175
175
  init_set(&unknown, ekisu, cur);
176
176
 
177
+ //セグメントエラー確認のためここでリストを巡回させるとやはりエラーになった//////////////////////
178
+
177
- while(adjlist[eki1]->next != NULL) {
179
+ while(adjlist[eki1] != NULL) {
178
180
 
179
181
  adjlist[eki1] = adjlist[eki1]->next;
180
182
 
@@ -182,11 +184,15 @@
182
184
 
183
185
  }
184
186
 
185
-
187
+ ////////////////////////////////////////////////////////////////
188
+
189
+
190
+
191
+
186
192
 
187
193
  while(unknown.size !=0 || cur != eki2) {
188
194
 
189
- while(adjlist[cur]->next != NULL) {
195
+ while(adjlist[cur] != NULL) {
190
196
 
191
197
  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]);
192
198
 
@@ -200,7 +206,7 @@
200
206
 
201
207
  printf("%d\n",adjlist[cur]->next);
202
208
 
203
- adjlist[cur] = adjlist[cur]->next;
209
+ adjlist[cur] = adjlist[cur]->next; //この前までのprintは出力された
204
210
 
205
211
  printf("eki = %d, next = %d\n", adjlist[cur]->eki, adjlist[cur]->next->eki);
206
212
 

2

tuiki

2019/01/30 05:48

投稿

apeirogon0813
apeirogon0813

スコア117

test CHANGED
File without changes
test CHANGED
@@ -37,3 +37,233 @@
37
37
  いつもはこの様な方法でもおそらくNULLがそのまま代入されてセグメントエラーになってなかったと思うのですが
38
38
 
39
39
  今回のプログラムではセグメントエラーになってしまいました。
40
+
41
+ ```C
42
+
43
+ #include<stdio.h>
44
+
45
+ #include<stdlib.h>
46
+
47
+ #include<limits.h>
48
+
49
+ #define ROSENZU "rosenzu.txt" /* 路線図データファイル */
50
+
51
+ #define SETMAX 10600 /* 集合の要素数の最大値 (駅の数) */
52
+
53
+ char buf[256]; /* 入力された文字列を格納するグローバル変数 */
54
+
55
+
56
+
57
+ int dist[SETMAX]; /* 指定された駅から各駅までの最短距離を格納するグローバル変数 */
58
+
59
+
60
+
61
+ struct node { int eki, rosen, kyori; struct node *next; };
62
+
63
+ struct set { int elements[SETMAX]; int size; };
64
+
65
+
66
+
67
+ void init_set(struct set *p, int n, int e) {
68
+
69
+ int i, j=0;
70
+
71
+ p->size = n-1;
72
+
73
+ for(i = 0; i < p->size; i++) {
74
+
75
+ if(j == e)
76
+
77
+ j++;
78
+
79
+ p->elements[i] = j++;
80
+
81
+ }
82
+
83
+ }
84
+
85
+
86
+
87
+ int delete_min(struct set *p) {
88
+
89
+ int i=0, j, min = dist[p->elements[0]];//一回ループを省力するため添字０の値を\
90
+
91
+ 代入しておく
92
+
93
+ if(p->size == 0) //空集合の場合
94
+
95
+ return -1;
96
+
97
+ else
98
+
99
+ for(j=1; j < p->size; j++) { //一番小さい値の添字の探索
100
+
101
+ if(dist[p->elements[j]] < min) {
102
+
103
+ min = dist[p->elements[j]];
104
+
105
+ i = j;
106
+
107
+ }
108
+
109
+ }
110
+
111
+ min = p->elements[i]; //minにはreturnする要素を格納
112
+
113
+ p->elements[i] = p->elements[p->size -1]; //最小値の場所に格納
114
+
115
+ p->size--;
116
+
117
+ return min;
118
+
119
+ }
120
+
121
+
122
+
123
+ //一方向の経路の挿入
124
+
125
+ struct node* insert_edge(struct node *list, int eki, int rosen, float kyori) {
126
+
127
+ struct node *n;
128
+
129
+ n = (struct node*)malloc(sizeof(struct node));
130
+
131
+ n->eki = eki;
132
+
133
+ n->rosen = rosen;
134
+
135
+ n->kyori = kyori;
136
+
137
+ n->next = list;
138
+
139
+ return n;
140
+
141
+ }
142
+
143
+
144
+
145
+ void add_edge(struct node *adjlist[], int eki1, int eki2, int rosen, int kyori) {
146
+
147
+ adjlist[eki1] = insert_edge(adjlist[eki1], eki2, rosen, kyori);
148
+
149
+ adjlist[eki2] = insert_edge(adjlist[eki2], eki1, rosen, kyori);
150
+
151
+ }
152
+
153
+
154
+
155
+ int dijkstra(struct node *adjlist[], int eki1, int eki2, int ekisu) {
156
+
157
+ int i, cur; //cur:直前に最短距離が確定した駅の変数
158
+
159
+ struct set unknown;
160
+
161
+ for(i=0; i<ekisu; i++) { //到達可能かわからない要素をINT_MAXにする
162
+
163
+ if(i == eki1)
164
+
165
+ dist[i] = 0;
166
+
167
+ else
168
+
169
+ dist[i] = INT_MAX;
170
+
171
+ }
172
+
173
+ cur = eki1;
174
+
175
+ init_set(&unknown, ekisu, cur);
176
+
177
+ while(adjlist[eki1]->next != NULL) {
178
+
179
+ adjlist[eki1] = adjlist[eki1]->next;
180
+
181
+ printf("%d->%d\n",adjlist[eki1],adjlist[eki1]->next);
182
+
183
+ }
184
+
185
+
186
+
187
+ while(unknown.size !=0 || cur != eki2) {
188
+
189
+ while(adjlist[cur]->next != NULL) {
190
+
191
+ 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]);
192
+
193
+ if(dist[cur] + adjlist[cur]->kyori < dist[adjlist[cur]->eki])
194
+
195
+ dist[adjlist[cur]->eki] = dist[cur] + adjlist[cur]->kyori;
196
+
197
+ printf("next\n");
198
+
199
+ printf("eki = %d, next = %d\n", adjlist[cur]->eki, adjlist[cur]->next->eki);
200
+
201
+ printf("%d\n",adjlist[cur]->next);
202
+
203
+ adjlist[cur] = adjlist[cur]->next;
204
+
205
+ printf("eki = %d, next = %d\n", adjlist[cur]->eki, adjlist[cur]->next->eki);
206
+
207
+ }
208
+
209
+ printf("srgsrgs\n");
210
+
211
+ cur = delete_min(&unknown); //集合unknownの最短距離の駅をcurに格納
212
+
213
+ printf("are\n");
214
+
215
+ }
216
+
217
+ printf("1\n\n");
218
+
219
+ return dist[eki2];
220
+
221
+ }
222
+
223
+
224
+
225
+ int main() {
226
+
227
+ int eki1, eki2, rosen, ekisu, i, kyori;
228
+
229
+ FILE *fp = fopen(ROSENZU,"r"); /* 路線図ファイルを読む準備 */
230
+
231
+ fscanf(fp, "%d ", &ekisu); /* 1行めの駅数を読取り */
232
+
233
+ struct node *adjlist[ekisu];
234
+
235
+ /* 隣接リスト表現を初期化．すべての頂点に対する隣接リストを空にする */
236
+
237
+ for(i=0;i<ekisu;++i) adjlist[i] = NULL;
238
+
239
+ while(fgets(buf,sizeof(buf),fp)!=NULL) {
240
+
241
+ /* 隣り合う駅の情報を読取り */
242
+
243
+ sscanf(buf, "%d:%d:%d:%d␣", &eki1, &eki2, &rosen, &kyori);
244
+
245
+ /* そのデータを隣接リスト表現のグラフに追加 */
246
+
247
+ add_edge(adjlist, eki1, eki2, rosen, kyori);
248
+
249
+ }
250
+
251
+ fclose(fp);
252
+
253
+ scanf("%d %d ", &eki1, &eki2);
254
+
255
+ printf("%d\n", dijkstra(adjlist, eki1, eki2, ekisu));
256
+
257
+ /* for(i=0;i<ekisu;++i)
258
+
259
+ if(dist[i] < INT_MAX)
260
+
261
+ printf("%d: %d\n", i, dist[i]); */
262
+
263
+ return 0;
264
+
265
+ }
266
+
267
+
268
+
269
+ ```

1

追記

2019/01/30 05:45

投稿

apeirogon0813
apeirogon0813

スコア117

test CHANGED
File without changes
test CHANGED
@@ -31,3 +31,9 @@
31
31
  とするとセグメントエラーになってしまいました。
32
32
 
33
33
  これはNULLを参照してしまったからでしょうか？
34
+
35
+
36
+
37
+ いつもはこの様な方法でもおそらくNULLがそのまま代入されてセグメントエラーになってなかったと思うのですが
38
+
39
+ 今回のプログラムではセグメントエラーになってしまいました。