質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.37%

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

解決済

回答 4

投稿

  • 評価
  • クリップ 1
  • VIEW 2,317
退会済みユーザー

退会済みユーザー

前提・実現したいこと

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

発生している問題・エラーメッセージ

生成したハッシュ表を画面に出力しようとしたところ、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 }
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • 退会済みユーザー

    退会済みユーザー

    2016/06/13 13:11

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

    キャンセル

回答 4

+1

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

checkベストアンサー

0

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/06/14 10:43

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

    キャンセル

0

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

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;
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.37%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る