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

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

ただいまの
回答率

87.77%

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

受付中

回答 2

投稿

  • 評価
  • クリップ 2
  • VIEW 398

score 0

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;
}
  • 気になる質問をクリップする

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

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

  • dodox86

    2021/01/27 10:29

    > 以下に示したようにそれぞれ関数を定義したのですが、出力結果には何も表示されません。

    どこまで意図通り正しく動いているか、確認されているのでしょうか。作りっぱなしではなく、まずご自身でデバッグしましょう。

    キャンセル

  • sk001016

    2021/01/27 10:33

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

    キャンセル

  • nob.

    2021/01/27 11:52

    「出力結果」って、何のことですか?
    HashDump()が呼び出されない、ってことですか?
    そういう事を、第三者に分かるように書いて下さい、ということです。

    ハッシュテーブルが怪しいなら、その内容を printf() などで確認しましょう。
    そういう作業はプログラムの作成者がすべきことです。

    キャンセル

回答 2

0

回答ではないですが

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

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

0

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

#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));

      hash->table = calloc(n,sizeof(HashRecord));
      if (hash->table == NULL){
        free(hash);
        return NULL;
    }
    hash->size=n;
    int i;
    for (i = 0; i < n; i++){
        hash->table[i].state=EMPTY;
    }

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


    int x;
    if(strLen(key)==0){return 0;}
    else if(strLen(key)==1){
        x = key[0] % hash->size -8;
        if (x < 0) x = 0;
    }else{
        int n = strLen(key);
        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);
    printf("hash-code=%d\n",h);
    p = &hash->table[h];
    if(p->state == FULL){
        return FALSE;
    }
    strcpy(p->key,key);
    strcpy(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 || strcmp(p->key,key) != 0){
        return FALSE;
    }
    strcpy(value,p->value);
    return TRUE;
}

// ハッシュテーブルのレコードを全て表示する(ハッシュが空でも表示).
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;
}


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

@@ -29,12 +29,16 @@
 Hash* HashAlloc(int n){
     Hash* hash=malloc(sizeof(Hash));

-    if(hash->table=calloc(n,sizeof(HashRecord))==NULL){
+      hash->table = calloc(n,sizeof(HashRecord));
+      if (hash->table == NULL){
         free(hash);
         return NULL;
     }
-    hash->table->state=EMPTY;
     hash->size=n;
+    int i;
+    for (i = 0; i < n; i++){
+        hash->table[i].state=EMPTY;
+    }

     return hash;
 }
@@ -47,33 +51,35 @@
 int HashCode(Hash *hash,char *key){

     int strLen(const char s[]){
-    int len =0;
-    while(s[len]) len++;
-    return len;
-}
-
+        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;
+    int x;
+    if(strLen(key)==0){return 0;}
+    else if(strLen(key)==1){
+        x = key[0] % hash->size -8;
+        if (x < 0) x = 0;
+    }else{
+        int n = strLen(key);
+        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];
+    printf("hash-code=%d\n",h);
+    p = &hash->table[h];
     if(p->state == FULL){
         return FALSE;
     }
-    *p->key = key;
-    *p->value = value;
+    strcpy(p->key,key);
+    strcpy(p->value,value);
     p->state =FULL;
     return TRUE;

@@ -83,12 +89,12 @@
     int h;
     HashRecord *p;
     h=HashCode(hash,key);
-    *p = hash->table[h];
-    if(p->state == EMPTY && p->key != key){
+    p = &hash->table[h];
+    if(p->state == EMPTY || strcmp(p->key,key) != 0){
         return FALSE;
     }
-    value = p->value;
-    return FALSE;
+    strcpy(value,p->value);
+    return TRUE;
 }

 // ハッシュテーブルのレコードを全て表示する(ハッシュが空でも表示).

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

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

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

関連した質問

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