c言語でハッシュを実装したい。

c言語でハッシュを作成したいです。

プログラムの全体は以下のようです。
ここでハッシュを操作する関数を定義します。
HashAlloc:サイズnのハッシュテーブルを動的生成
HashFree:ハッシュテーブルの開放
HashAdd:データ追加
HashGet:データの検索と取得
HashDelete:データ削除
HashCode:ハッシュ値計算。除数はn

以下に示したようにそれぞれ関数を定義したのですが、出力結果には何も表示されません。
お力添えいただければ幸いです。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* ハッシュテーブル構造定義 */
enum { FALSE = 0, TRUE = 1 };
enum { EMPTY = 0, FULL = 1 } ;

typedef struct {
  char key[64];
  char value[64];
  int state;	/* FULL:使用中 EMPTY:未使用 */
} HashRecord;

typedef struct {
  int size;
  HashRecord *table;
} Hash;

Hash* HashAlloc(int n);
void HashFree(Hash *);
int HashAdd(Hash *, char *, char *);
int HashGet(Hash *, char *, char *);
int HashCode(Hash *, char *);

void HashDump(Hash *);

//
Hash* HashAlloc(int n){
    Hash* hash=malloc(sizeof(Hash));
    
    if(hash->table=calloc(n,sizeof(HashRecord))==NULL){
        free(hash);
        return NULL;
    }
    hash->table->state=EMPTY;
    hash->size=n;
    
    return hash;
}

void HashFree(Hash *s){
    free(s->table);
    free(s);
}

int HashCode(Hash *hash,char *key){
   
    int strLen(const char s[]){
    int len =0;
    while(s[len]) len++;
    return len;
}



if(strLen(key)==0){return 0;}
else if(strLen(key)==1){
    return key[0] % hash->size -8;
}else{
    int n = strLen(key);
    int x = (key[0] - 65 + 26* (key[n/2 -1] - 65) + 26 * 26 * (key[n-2] - 65 )) % hash->size;
    return x;
}
}

int HashAdd(Hash *hash, char *key, char *value){
    int h=0;
    HashRecord *p;
    h=HashCode(hash,key);
    *p = hash->table[h];
    if(p->state == FULL){
        return FALSE;
    }
    *p->key = key;
    *p->value = value;
    p->state =FULL;
    return TRUE;

}

int HashGet(Hash *hash, char *key, char *value){
    int h;
    HashRecord *p;
    h=HashCode(hash,key);
    *p = hash->table[h];
    if(p->state == EMPTY && p->key != key){
        return FALSE;
    }
    value = p->value;
    return FALSE;
}

// ハッシュテーブルのレコードを全て表示する（ハッシュが空でも表示）．
void HashDump(Hash *hash)
{
  int i;
  
  for (i = 0; i < hash->size; i++) {
    printf("%4d: ", i);

    switch (hash->table[i].state) {
      case FULL:
        printf("(%s, %s)", hash->table[i].key, hash->table[i].value);
        break;
      case EMPTY:
        printf("empty");
        break;
      default:
        printf("unknown");
        break;
    }

    printf("\n");
  }
}

int main(void)
{
  int size = 0, h;
  char cmd, key[64], value[64], buf[64];
  Hash *hash;
  
  // ハッシュテーブルの生成
  printf("ハッシュテーブルの大きさを入力して下さい?> ");
  scanf("%d", &size);

  if (size < 1) return -1;// 入力数エラー

  hash = HashAlloc(size);

  if (hash == NULL) return -1;	// メモリ確保失敗
  
  puts("* ハッシュテーブルを操作するコマンドを入力して下さい．");
  puts("* a: データを格納");
  puts("* g: キーに対応するデータの取得");
  puts("* p: ハッシュテーブルを表示");
  puts("* q: 終了");
  
  do {
    printf("?> ");
    scanf("%s", buf);
    cmd = buf[0];
    
    switch (cmd) {
      case 'a':	/* データを格納 */
        printf("名前と血液型をスペース区切りで入力して下さい（例|HANA A）: ");
        scanf("%s %s", key, value);
        printf("%c -> %s %s\n", cmd, key, value);

        if (HashAdd(hash, key, value) == TRUE) {
          printf("(%s, %s) を格納しました．\n", key, value);
        } else {	/* 衝突 */
          printf("重複しています．\n");
        }
        break;
      case 'g':	/* キーに対応するデータを取得 */
        printf("名前を入力して下さい: ");
        scanf("%s", key);
        printf("%c -> %s\n", cmd, key);

        if (HashGet(hash, key, value) == TRUE) {
          printf("%sの血液型は%sです．\n", key, value);
        } else {
          printf("%sは登録されていません．\n", key);
        }
        break;
      case 'p':	/* データを表示 */
        printf("%c\n", cmd);
        HashDump(hash);
        break;
      case 'q':	/* 終了 */
        printf("%c\n", cmd);
        puts("プログラムを終了します．");
        break;
      case '\n':	/* 改行 */
      case '\r':	/* 復帰 */
        break;
      default:	/* 入力エラー */
        puts("不正なコマンドです．");
        break;
    }
  } while (cmd != 'q');
  
  HashDump(hash);	// 解放前の出力
  HashFree(hash);	// メモリ解放
  
  return 0;
}

dodox86

2021/01/27 01:29

> 以下に示したようにそれぞれ関数を定義したのですが、出力結果には何も表示されません。どこまで意図通り正しく動いているか、確認されているのでしょうか。作りっぱなしではなく、まずご自身でデバッグしましょう。

sk001016

2021/01/27 01:33

返信ありがとうございます。おそらくハッシュテーブルの動的生成の部分がうまくいっていないためだと考えられます。

nob.

2021/01/27 02:52

「出力結果」って、何のことですか？ HashDump()が呼び出されない、ってことですか？そういう事を、第三者に分かるように書いて下さい、ということです。ハッシュテーブルが怪しいなら、その内容を printf() などで確認しましょう。そういう作業はプログラムの作成者がすべきことです。

行動規範の内容に同意します

回答2件

とりあえず、動くようにしておきました。不明点があれば、質問してください。

C
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5/* ハッシュテーブル構造定義 */
6enum { FALSE = 0, TRUE = 1 };
7enum { EMPTY = 0, FULL = 1 } ;
8
9typedef struct {
10  char key[64];
11  char value[64];
12  int state;    /* FULL:使用中 EMPTY:未使用 */
13} HashRecord;
14
15typedef struct {
16  int size;
17  HashRecord *table;
18} Hash;
19
20Hash* HashAlloc(int n);
21void HashFree(Hash *);
22int HashAdd(Hash *, char *, char *);
23int HashGet(Hash *, char *, char *);
24int HashCode(Hash *, char *);
25
26void HashDump(Hash *);
27
28//
29Hash* HashAlloc(int n){
30    Hash* hash=malloc(sizeof(Hash));
31
32      hash->table = calloc(n,sizeof(HashRecord));
33      if (hash->table == NULL){
34        free(hash);
35        return NULL;
36    }
37    hash->size=n;
38    int i;
39    for (i = 0; i < n; i++){
40        hash->table[i].state=EMPTY;
41    }
42
43    return hash;
44}
45
46void HashFree(Hash *s){
47    free(s->table);
48    free(s);
49}
50
51int HashCode(Hash *hash,char *key){
52
53    int strLen(const char s[]){
54        int len =0;
55        while(s[len]) len++;
56        return len;
57    }
58
59
60    int x;
61    if(strLen(key)==0){return 0;}
62    else if(strLen(key)==1){
63        x = key[0] % hash->size -8;
64        if (x < 0) x = 0;
65    }else{
66        int n = strLen(key);
67        x = (key[0] - 65 + 26* (key[n/2 -1] - 65) + 26 * 26 * (key[n-2] - 65 )) % hash->size;
68    }
69    return x;
70}
71
72int HashAdd(Hash *hash, char *key, char *value){
73    int h=0;
74    HashRecord *p;
75    h=HashCode(hash,key);
76    printf("hash-code=%d\n",h);
77    p = &hash->table[h];
78    if(p->state == FULL){
79        return FALSE;
80    }
81    strcpy(p->key,key);
82    strcpy(p->value,value);
83    p->state =FULL;
84    return TRUE;
85
86}
87
88int HashGet(Hash *hash, char *key, char *value){
89    int h;
90    HashRecord *p;
91    h=HashCode(hash,key);
92    p = &hash->table[h];
93    if(p->state == EMPTY || strcmp(p->key,key) != 0){
94        return FALSE;
95    }
96    strcpy(value,p->value);
97    return TRUE;
98}
99
100// ハッシュテーブルのレコードを全て表示する（ハッシュが空でも表示）．
101void HashDump(Hash *hash)
102{
103  int i;
104
105  for (i = 0; i < hash->size; i++) {
106    printf("%4d: ", i);
107
108    switch (hash->table[i].state) {
109      case FULL:
110        printf("(%s, %s)", hash->table[i].key, hash->table[i].value);
111        break;
112      case EMPTY:
113        printf("empty");
114        break;
115      default:
116        printf("unknown");
117        break;
118    }
119
120    printf("\n");
121  }
122}
123
124int main(void)
125{
126  int size = 0, h;
127  char cmd, key[64], value[64], buf[64];
128  Hash *hash;
129
130  // ハッシュテーブルの生成
131  printf("ハッシュテーブルの大きさを入力して下さい?> ");
132  scanf("%d", &size);
133
134  if (size < 1) return -1;// 入力数エラー
135
136  hash = HashAlloc(size);
137
138  if (hash == NULL) return -1;    // メモリ確保失敗
139
140  puts("* ハッシュテーブルを操作するコマンドを入力して下さい．");
141  puts("* a: データを格納");
142  puts("* g: キーに対応するデータの取得");
143  puts("* p: ハッシュテーブルを表示");
144  puts("* q: 終了");
145
146  do {
147    printf("?> ");
148    scanf("%s", buf);
149    cmd = buf[0];
150
151    switch (cmd) {
152      case 'a':    /* データを格納 */
153        printf("名前と血液型をスペース区切りで入力して下さい（例|HANA A）: ");
154        scanf("%s %s", key, value);
155        printf("%c -> %s %s\n", cmd, key, value);
156
157        if (HashAdd(hash, key, value) == TRUE) {
158          printf("(%s, %s) を格納しました．\n", key, value);
159        } else {    /* 衝突 */
160          printf("重複しています．\n");
161        }
162        break;
163      case 'g':    /* キーに対応するデータを取得 */
164        printf("名前を入力して下さい: ");
165        scanf("%s", key);
166        printf("%c -> %s\n", cmd, key);
167
168        if (HashGet(hash, key, value) == TRUE) {
169          printf("%sの血液型は%sです．\n", key, value);
170        } else {
171          printf("%sは登録されていません．\n", key);
172        }
173        break;
174      case 'p':    /* データを表示 */
175        printf("%c\n", cmd);
176        HashDump(hash);
177        break;
178      case 'q':    /* 終了 */
179        printf("%c\n", cmd);
180        puts("プログラムを終了します．");
181        break;
182      case '\n':    /* 改行 */
183      case '\r':    /* 復帰 */
184        break;
185      default:    /* 入力エラー */
186        puts("不正なコマンドです．");
187        break;
188    }
189  } while (cmd != 'q');
190
191  HashDump(hash);    // 解放前の出力
192  HashFree(hash);    // メモリ解放
193
194  return 0;
195}
196

修正個所は下記を参照してください。

diff
1@@ -29,12 +29,16 @@
2 Hash* HashAlloc(int n){
3     Hash* hash=malloc(sizeof(Hash));
4 
5-    if(hash->table=calloc(n,sizeof(HashRecord))==NULL){
6+      hash->table = calloc(n,sizeof(HashRecord));
7+      if (hash->table == NULL){
8         free(hash);
9         return NULL;
10     }
11-    hash->table->state=EMPTY;
12     hash->size=n;
13+    int i;
14+    for (i = 0; i < n; i++){
15+        hash->table[i].state=EMPTY;
16+    }
17 
18     return hash;
19 }
20@@ -47,33 +51,35 @@
21 int HashCode(Hash *hash,char *key){
22 
23     int strLen(const char s[]){
24-    int len =0;
25-    while(s[len]) len++;
26-    return len;
27-}
28-
29+        int len =0;
30+        while(s[len]) len++;
31+        return len;
32+    }
33 
34 
35-if(strLen(key)==0){return 0;}
36-else if(strLen(key)==1){
37-    return key[0] % hash->size -8;
38-}else{
39-    int n = strLen(key);
40-    int x = (key[0] - 65 + 26* (key[n/2 -1] - 65) + 26 * 26 * (key[n-2] - 65 )) % hash->size;
41+    int x;
42+    if(strLen(key)==0){return 0;}
43+    else if(strLen(key)==1){
44+        x = key[0] % hash->size -8;
45+        if (x < 0) x = 0;
46+    }else{
47+        int n = strLen(key);
48+        x = (key[0] - 65 + 26* (key[n/2 -1] - 65) + 26 * 26 * (key[n-2] - 65 )) % hash->size;
49+    }
50     return x;
51 }
52-}
53 
54 int HashAdd(Hash *hash, char *key, char *value){
55     int h=0;
56     HashRecord *p;
57     h=HashCode(hash,key);
58-    *p = hash->table[h];
59+    printf("hash-code=%d\n",h);
60+    p = &hash->table[h];
61     if(p->state == FULL){
62         return FALSE;
63     }
64-    *p->key = key;
65-    *p->value = value;
66+    strcpy(p->key,key);
67+    strcpy(p->value,value);
68     p->state =FULL;
69     return TRUE;
70 
71@@ -83,12 +89,12 @@
72     int h;
73     HashRecord *p;
74     h=HashCode(hash,key);
75-    *p = hash->table[h];
76-    if(p->state == EMPTY && p->key != key){
77+    p = &hash->table[h];
78+    if(p->state == EMPTY || strcmp(p->key,key) != 0){
79         return FALSE;
80     }
81-    value = p->value;
82-    return FALSE;
83+    strcpy(value,p->value);
84+    return TRUE;
85 }
86 
87 // ハッシュテーブルのレコードを全て表示する（ハッシュが空でも表示）．
88

投稿2021/01/28 08:46

編集2021/01/29 04:24

tatsu99

総合スコア5493

回答ではないですが

C言語のコードを書くなら、デバッグできる環境を整えましょう。
Eclipseや、WindowsならVisualStudioなど。
コードの任意の場所で実行を止め、変数のナカミを見ることができます。そこから１行づつ実行して、コードの流れを見れるようになります
そうすれば、アテズッポでコードを書かなくて済むようになります。

投稿2021/01/27 01:54