teratail
回答率
85.48%
質問するログイン新規登録

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

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

新規登録して質問してみよう
ただいま回答率
85.48%
トップCに関する質問
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

ハッシュ

ハッシュは、高速にデータ検索を行うアルゴリズムのことです。

Q&A

2回答

2622閲覧

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

sk001016
sk001016

総合スコア0

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

ハッシュ

ハッシュは、高速にデータ検索を行うアルゴリズムのことです。

0グッド

2クリップ

投稿2021/01/27 01:24

0

2

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

気になる質問をクリップする

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

dodox86
dodox86

2021/01/27 01:29

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

2021/01/27 01:33

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

2021/01/27 02:52

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

回答2件

0

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

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
tatsu99

総合スコア5438

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

回答ではないですが

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

投稿2021/01/27 01:54

y_waiwai
y_waiwai

総合スコア87774

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

質問の解決につながる回答をしましょう。 サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。 また、読む側のことを考えた、分かりやすい文章を心がけましょう。

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

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

ただいまの回答率
85.48%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

トップCに関する質問

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