線形リストでセグメントエラーになってしまいます。

Question

前提・実現したいこと

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;の手前まで出力されていたためこれが原因かと思っていました。。

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define ROSENZU "rosenzu.txt" /* 路線図データファイル */
#define SETMAX 10600 /* 集合の要素数の最大値 (駅の数) */
char buf[256]; /* 入力された文字列を格納するグローバル変数 */

int dist[SETMAX]; /* 指定された駅から各駅までの最短距離を格納するグローバル変数 */

struct node { int eki, rosen, kyori; struct node *next; };
struct set { int elements[SETMAX]; int size; };

void init_set(struct set *p, int n, int e) {
  int i, j=0;
  p->size = n-1;
  for(i = 0; i < p->size; i++) {
    if(j == e)
      j++;
    p->elements[i] = j++;
  }
}

int delete_min(struct set *p) {
  int i=0, j, min = dist[p->elements[0]];//一回ループを省力するため添字０の値を\
代入しておく                                                                    
  if(p->size == 0) //空集合の場合                                               
    return -1;
  else
    for(j=1; j < p->size; j++) { //一番小さい値の添字の探索                     
      if(dist[p->elements[j]] < min) {
        min = dist[p->elements[j]];
        i = j;
      }
    }
 min = p->elements[i]; //minにはreturnする要素を格納                           
 p->elements[i] = p->elements[p->size -1]; //最小値の場所に格納                
 p->size--;
 return min;
}

//一方向の経路の挿入
struct node* insert_edge(struct node *list, int eki, int rosen, float kyori) {
  struct node *n;
  n = (struct node*)malloc(sizeof(struct node));
  n->eki = eki;
  n->rosen = rosen;
  n->kyori = kyori;
  n->next = list;
  return n;
}

void add_edge(struct node *adjlist[], int eki1, int eki2, int rosen, int kyori) {
  adjlist[eki1] = insert_edge(adjlist[eki1], eki2, rosen, kyori);
  adjlist[eki2] = insert_edge(adjlist[eki2], eki1, rosen, kyori);
}

int dijkstra(struct node *adjlist[], int eki1, int eki2, int ekisu) {
  int i, cur; //cur:直前に最短距離が確定した駅の変数
  struct set unknown;
  for(i=0; i<ekisu; i++) { //到達可能かわからない要素をINT_MAXにする
    if(i == eki1)
      dist[i] = 0;
    else
      dist[i] = INT_MAX;
  }
  cur = eki1;
  init_set(&unknown, ekisu, cur);
//セグメントエラー確認のためここでリストを巡回させるとやはりエラーになった//////////////////////
  while(adjlist[eki1] != NULL) { 
    adjlist[eki1] = adjlist[eki1]->next;
    printf("%d->%d\n",adjlist[eki1],adjlist[eki1]->next);
  }
  ////////////////////////////////////////////////////////////////


    while(unknown.size !=0 || cur != eki2) {
      while(adjlist[cur] != NULL) {
	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]);
	if(dist[cur] + adjlist[cur]->kyori < dist[adjlist[cur]->eki])
	  dist[adjlist[cur]->eki] = dist[cur] + adjlist[cur]->kyori;
	printf("next\n");
printf("eki = %d, next = %d\n", adjlist[cur]->eki, adjlist[cur]->next->eki);
 printf("%d\n",adjlist[cur]->next);
	adjlist[cur] = adjlist[cur]->next; //この前までのprintは出力された
	printf("eki = %d, next = %d\n", adjlist[cur]->eki, adjlist[cur]->next->eki);
      }
      printf("srgsrgs\n");
      cur = delete_min(&unknown); //集合unknownの最短距離の駅をcurに格納
      printf("are\n");
    }
    printf("1\n\n");
  return dist[eki2];
}

int main() {
  int eki1, eki2, rosen, ekisu, i, kyori;
  FILE *fp = fopen(ROSENZU,"r"); /* 路線図ファイルを読む準備 */
 fscanf(fp, "%d ", &ekisu); /* 1行めの駅数を読取り */
 struct node *adjlist[ekisu];
 /* 隣接リスト表現を初期化．すべての頂点に対する隣接リストを空にする */
 for(i=0;i<ekisu;++i) adjlist[i] = NULL;
 while(fgets(buf,sizeof(buf),fp)!=NULL) {
   /* 隣り合う駅の情報を読取り */
   sscanf(buf, "%d:%d:%d:%d␣", &eki1, &eki2, &rosen, &kyori);
   /* そのデータを隣接リスト表現のグラフに追加 */
   add_edge(adjlist, eki1, eki2, rosen, kyori);
 }
 fclose(fp);
 scanf("%d %d ", &eki1, &eki2);
 printf("%d\n", dijkstra(adjlist, eki1, eki2, ekisu));
 /* for(i=0;i<ekisu;++i)
    if(dist[i] < INT_MAX)
    printf("%d: %d\n", i, dist[i]); */
 return 0;
}

Comments

[y_waiwai]

ソースコードを提示してください。
バグはあなたの思っているところではありませんｗ

[apeirogon0813]

```C
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define ROSENZU "rosenzu.txt" /* 路線図データファイル */
#define SETMAX 10600 /* 集合の要素数の最大値 (駅の数) */
char buf[256]; /* 入力された文字列を格納するグローバル変数 */

int dist[SETMAX]; /* 指定された駅から各駅までの最短距離を格納するグローバル変数 */

struct node { int eki, rosen, kyori; struct node *next; };
struct set { int elements[SETMAX]; int size; };

void init_set(struct set *p, int n, int e) {
int i, j=0;
p->size = n-1;
for(i = 0; i < p->size; i++) {
if(j == e)
j++;
p->elements[i] = j++;
}
}

int delete_min(struct set *p) {
int i=0, j, min = dist[p->elements[0]];//一回ループを省力するため添字０の値を\
代入しておく
if(p->size == 0) //空集合の場合
return -1;
else
for(j=1; j < p->size; j++) { //一番小さい値の添字の探索
if(dist[p->elements[j]] < min) {
min = dist[p->elements[j]];
i = j;
}
}
min = p->elements[i]; //minにはreturnする要素を格納
p->elements[i] = p->elements[p->size -1]; //最小値の場所に格納
p->size--;
return min;
}

//一方向の経路の挿入
struct node* insert_edge(struct node *list, int eki, int rosen, float kyori) {
struct node *n;
n = (struct node*)malloc(sizeof(struct node));
n->eki = eki;
n->rosen = rosen;
n->kyori = kyori;
n->next = list;
return n;
}

void add_edge(struct node *adjlist[], int eki1, int eki2, int rosen, int kyori) {
adjlist[eki1] = insert_edge(adjlist[eki1], eki2, rosen, kyori);
adjlist[eki2] = insert_edge(adjlist[eki2], eki1, rosen, kyori);
}

int dijkstra(struct node *adjlist[], int eki1, int eki2, int ekisu) {
int i, cur; //cur:直前に最短距離が確定した駅の変数
struct set unknown;
for(i=0; i<ekisu; i++) { //到達可能かわからない要素をINT_MAXにする
if(i == eki1)
dist[i] = 0;
else
dist[i] = INT_MAX;
}
cur = eki1;
init_set(&unknown, ekisu, cur);
while(adjlist[eki1]->next != NULL) {
adjlist[eki1] = adjlist[eki1]->next;
printf("%d->%d\n",adjlist[eki1],adjlist[eki1]->next);
}

while(unknown.size !=0 || cur != eki2) {
while(adjlist[cur]->next != NULL) {
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]);
if(dist[cur] + adjlist[cur]->kyori < dist[adjlist[cur]->eki])
dist[adjlist[cur]->eki] = dist[cur] + adjlist[cur]->kyori;
printf("next\n");
printf("eki = %d, next = %d\n", adjlist[cur]->eki, adjlist[cur]->next->eki);
printf("%d\n",adjlist[cur]->next);
adjlist[cur] = adjlist[cur]->next;
printf("eki = %d, next = %d\n", adjlist[cur]->eki, adjlist[cur]->next->eki);
}
printf("srgsrgs\n");
cur = delete_min(&unknown); //集合unknownの最短距離の駅をcurに格納
printf("are\n");
}
printf("1\n\n");
return dist[eki2];
}

int main() {
int eki1, eki2, rosen, ekisu, i, kyori;
FILE *fp = fopen(ROSENZU,"r"); /* 路線図ファイルを読む準備 */
fscanf(fp, "%d ", &ekisu); /* 1行めの駅数を読取り */
struct node *adjlist[ekisu];
/* 隣接リスト表現を初期化．すべての頂点に対する隣接リストを空にする */
for(i=0;i<ekisu;++i) adjlist[i] = NULL;
while(fgets(buf,sizeof(buf),fp)!=NULL) {
/* 隣り合う駅の情報を読取り */
sscanf(buf, "%d:%d:%d:%d␣", &eki1, &eki2, &rosen, &kyori);
/* そのデータを隣接リスト表現のグラフに追加 */
add_edge(adjlist, eki1, eki2, rosen, kyori);
}
fclose(fp);
scanf("%d %d ", &eki1, &eki2);
printf("%d\n", dijkstra(adjlist, eki1, eki2, ekisu));
/* for(i=0;i<ekisu;++i)
if(dist[i] < INT_MAX)
printf("%d: %d\n", i, dist[i]); */
return 0;
}

```

[y_waiwai]

ここではコードが見づらいので、質門の方を編集し、<code>ボタンで、出てくる’’’の枠の中にコードを貼り付けてください

[apeirogon0813]

関数dijkstraの局所局所にprint文を入れてどこでエラーなるかチェックしたところ
adjlist[cur] = adjlist[cur]->next;の手前まで出力されていたためこれが原因かと思っていました。。

[y_waiwai]

そこらへんの情報ももらさず質問に追記していただければ、解決も早いかと思いますです

[apeirogon0813]

ありがとうございます

Answer 1

while(adjlist[eki1] != NULL) { 
    adjlist[eki1] = adjlist[eki1]->next;
    printf("%d->%d\n",adjlist[eki1],adjlist[eki1]->next);
}

↓こうじゃない？

while(adjlist[eki1] != NULL) { 
    printf("%d->",adjlist[eki1]);
    adjlist[eki1] = adjlist[eki1]->next;
    if (adjlist[eki1] != NULL){
        printf("%d",adjlist[eki1]);
    }
    printf("\n");
}

じゃない？

Comments

[apeirogon0813]

これはつまりNULLのnextを参照しようとしてエラーになっているのでしょうか？

[stdio]

そうだと思います。
その上、
printf("%d->%d\n",adjlist[eki1],adjlist[eki1]->next);
では、NULLの後のnextを参照しようとしているので、さらにエラーが出ていると思われます。

[stdio]

そして、元のコードでは、
少し笑えますが、printf消したら治るな。

[apeirogon0813]

おっしゃるとおりでした。。。

[apeirogon0813]

有難うございました。