C ハッシュテーブルの実装

Question

###前提・実現したいこと
二次元平面上の点をデータとするハッシュ表をチェイニングで実装しようとしています。
乱数を用いてデータを生成し、最終的に生成した各バケットに登録されているデータの個数の統計量を導出したいです。

###発生している問題・エラーメッセージ
生成したハッシュ表を画面に出力しようとしたところ、Segmentation Fault: 11が表示されます。
一度print_hashでH[i]がNULLのときに出力したところ、H[B]すべてがNULLでした。
原因がわからないのでご教授よろしくお願いします。

###該当のソースコード

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<time.h>
  4 #include<math.h>
  5 #define B 10000
  6 #define N 5
  7 #define M 5000  //使用しません
  8 #define X 10000
  9 #define Y 10000  //使用しません
 10 
 11 //二次元平面上の点
 12 typedef struct POINT{
 13   int x;
 14   int y;
 15 }point_t;
 16 
 17 //点の新規作成
 18 point_t new_point(int x, int y)
 19 {
 20   point_t p;
 21   p.x = x;
 22   p.y = y;
 23   return p;
 24 }
 25 
 26 //連結リストのノード
 27 typedef struct NODE{
 28   point_t point;  //登録する点
 29   struct NODE *next;
 30 }node_t;
 31 
 32 //ノードの新規作成
 33 node_t *new_node(point_t p)
 34 {
 35   node_t *ndPtr;
 36   ndPtr = malloc(sizeof(node_t));
 37   
 38   if (ndPtr == NULL) {
 39     return NULL;
 40   } else {
 41     ndPtr->point = p;
 42     ndPtr->next = NULL;
 43   }
 44 
 45   return ndPtr;
 46 }
 47 
 48 //ハッシュ表 = ノードへのポインタを格納する配列
 49 node_t *H[B];
 50 
 51 //ハッシュ表初期化関数
 52 void init_hash()
 53 {
 54   int i;
 55   for (i = 0; i < B; i++) H[i] = NULL;
 56 }
 57 
 58 //ハッシュ表出力関数
 59 void print_hash();
 60 {
 61   node_t *ndPtr;
 62   int i;
 63 
 64   for (i = 0; i < B; i++) {
 65     ndPtr = H[i];
 66     if (ndPtr != NULL) {
 67       printf("%6d %5d %5d\n", i, ndPtr->point.x, ndPtr->point.y);
 68       ndPtr = ndPtr->next;
 69     }
 70     while (ndPtr != NULL) {
 71       printf("       %5d %5d\n", ndPtr->point.x, ndPtr->point.y);
 72       ndPtr = ndPtr->next;
 73     }
 74   }
 75 }
 76 
 77 //ハッシュ関数1
 78 int hash1(point_t point)
 79 {
 80   int i;
 81   for (i = 0; i <= X; i++) {
 82     if (point.x == i) return i;
 83   }
 84   return -1;
 85 }
 86 
 87 //ノードの探索, *head:探索始点ノードへのポインタ, p:探す点
 88 //見つかればそのアドレスを, 見つからなければNULLを返す
 89 node_t *search_node(node_t *head, point_t p)
 90 {
 91   while (head != NULL) {
 92     if (head->point.x == p.x && head->point.y == p.y) return head;
 93     head = head->next;
 94   }
 95   return NULL;
 96 }
 97 
 98 //新しいノードをリストの先頭へ挿入, *head:先頭ノードへのポインタ, p:挿入する点
 99 int insert_node_top(node_t **head, point_t p)
100 {
101   node_t *ndPtr;
102   ndPtr = new_node(p);
103   if (ndPtr == NULL) return -1;
104   *head = ndPtr;
105   return 1;
106 }
107 
108 //pointの探索, pがハッシュ表に含まれていれば1, 含まれていなければ0を返す
109 int search_hash(point_t p)
110 {
111   int b;
112   b = hash1(p);
113 
114   if (search_node(H[b], p) != NULL) return 1;
115   else return 0;
116 }
117 
118 //点をハッシュ表に重複なしで登録する関数
119 int insert_hash(point_t p)
120 {
121   int b;
122   b = hash1(p);
123 
124   if (search_hash(p) == 0) {
125     insert_node_top(&H[b], p);
126     return 1;
127   }
128   else return 0;
129 }
130 
131 //各バケット(H[0], H[1],...)に登録されているデータの個数の最大値と最小値および分散
132 void hash_status()
133 {
134   int max = 0, min = B;  //登録データ数の最大値, 最小値
135   double sum = 0;  //登録データ数の和
136   double ave, var, dif = 0;   //平均, 分散, 二乗差
137   int i;
138   int count[B] = {};  //各バケットに登録されているデータの個数
139 
140   for (i = 0; i < B; i++) {
141     node_t *ndPtr;
142     if (H[i] != NULL) {
143       ndPtr = H[i];
144       while (ndPtr != NULL) {
145         count[i]++;
146         ndPtr = ndPtr->next;
147       }
148       if (count[i] > max) max = count[i];
149       if (count[i] < min) min = count[i];
150       sum += count[i];
151     }
152   }
153 
154   ave = sum / B;
155 
156   for (i = 0; i < B; i++) {
157     dif += pow(count[i] - ave, 2);
158   }
159   var = dif / B;
160 
161   printf("MAX : %5d\n", max);
162   printf("MIN : %5d\n", min);
163   printf("VARIANCE : %5.5f\n", var);
164 }
165 
166 int main()
167 {
168   int i = 0;
169 
170   init_hash();
171 
172   srand((unsigned)time(NULL));  //乱数生成
173 
174   while (i < N) {
175     int rx, ry;
176     point_t p;
177 
178     rx = rand() % B;  //0-9999の整数
179     ry = rand() % B;  //0-9999の整数
180 
181     if (rx >= ry) {
182       p = new_point(rx, ry);
183       if (insert_hash(p) == 1) i++;
184     }
185   }
186 
187   print_hash();
188 
189   hash_status();
190 
191  return 0;
192 }                                                                                                                                

Comments

[退会済みユーザー]

main()のwhileループが終わったときの i の値はどうなっていますか？

Answer 1

Ideoneで試したら動いてしまいました。
但し、60行目の文末にセミコロンがついていたので修正しましたが。

Answer 2

軽く動かしてみました。
60行目の";"、hash_statusでint count[B]={0};、new_nodeで(node_t*)にキャストを変更してます。
とりあえず動きますが、new_nodeでmallocしたものが開放されてないと言われます。
多分そこが終了時にセグメントフォールトするのではないでしょうか？

Answer 3

node_tのnextに代入しているのはnew_node関数の中でNULLを代入しているだけなので、nextを使おうとすると落ちるのでは?
nextには適切なポインタを設定する必要があると思います。
insert_node_topでheadがNULLの場合とそうでない場合に処理を分けて、NULLでない場合は新しく作成したnode_tのnextに元々のheadの値を代入するのが正しいのかな。

Comments

[退会済みユーザー]

insert_node_topでndPtr->next = *headを追加したら解決しました。
ありがとうございました。

Answer 4

解答ではなく解決策の提案です。
ノードを作成・挿入している部分にバグがあるんでしょうから、それを順に追って正しいデータが得られているかどうかダンプしてみたらどうでしょう？

int insert_hash(point_t p)
{
  printf("insert_hash : p = (\d, \d)\n", p.x, p.y);
  int b;
  b = hash1(p);
  printf("insert_hash : b=%d\n", b);

  if (search_hash(p) == 0) {
    printf("insert_hash : search_hash(p) == 0\n");
    insert_node_top(&H[b], p);
    printf("insert_hash : H[b] = \x\n", H[b]);
    return 1;
  }
  else return 0;
}