C言語関係掲示板

過去ログ

No.1324 構造体を用いたハッシュ法について

[戻る] [ホームページ]
No.17651

構造体を用いたハッシュ法について
投稿者---Y.M(2004/10/31 22:51:29)


ハッシュ表の挿入と一覧表示処理を作成していますが、
うまく一覧表示されません。
多分insert関数の p = malloc(sizeof(CELL));の後に
ポインタを指定していないのが原因だと思いますが、
mallocの処理がないとstrcpyうまく動作しません。
ですのでmallocのあとにpにポインタの変数を格納しましたが、
やり方が悪いのかコレもダメでした。
解決方法を教えてください。
回答のほどよろしくお願いいたします。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define WORD_LENGTH  50    /* 文字列の最大長 */

/* ハッシュ表の定義 */
#define TBL_SIZE  10       /* ハッシュ表の大きさ */
typedef struct cell{       /* ハッシュ表に登録されるセルを実装する構造体 */
    char key[WORD_LENGTH]; /* 実際のデータ値(キー) */
    char tel[WORD_LENGTH]; /* 実際のデータ値(data) */
    struct cell *next;     /* 次のセルへのポインタ */
} CELL;

CELL *table[TBL_SIZE];
int  insert(char key[], char tel[]);   /* ハッシュ表にキーを挿入する */
int  list_up(void);                    /* 登録データをリストアップする */
void init(void);                       /* ハッシュ表の初期化 */
int  hash(char *s);                    /* ハッシュ関数 */

void main(void)
{
    char name[WORD_LENGTH];
    char number[WORD_LENGTH];
    int  menu, cnt;
    CELL *p;
    
    init();
    
    do{
        printf("\n------------------ メニュー ------------------\n");
        printf("1:挿入 4:一覧 9:終了\n");
        printf("番号を入力してください : ");
        scanf("%d", &menu);
        rewind(stdin);
        switch(menu){
            case 1: /* データ登録 */
                printf("名前を入力して下さい: ");
                gets(name);
                printf("電話番号を入力して下さい: ");
                gets(number);
                if(insert(name, number) == 1){
                    printf("%s : \n", name);
                    printf("%s を登録しました\n", number);
                }
                else
                    printf("既に %s は登録済みです\n", name);
                break;
           
            case 4:  /* データ一覧 */
                printf("現在の登録者一覧\n");
                cnt = list_up();
                printf("以上 %d 件登録\n", cnt);
                break;
        }
    }while(menu < 9);
}



/*  insert  -- ハッシュ表にデータを挿入する             */
/*       登録に成功したら 1 を返す                      */
/*       登録に失敗(すでに同じキーを持つデータがある) */
/*       したら 0 を返す                                */
int insert(char key[], char tel[])
{
    
    CELL *p;
    int   h;
    
    h = hash(key);
    /*
    if( != NULL)
        return(0);
    */
    if((p = malloc(sizeof(CELL))) == NULL) {
        printf("out of memory\n");
        exit(2);
    }
    
    for(p = table[h]; p != NULL; p = p -> next){
        if(strcmp(key, p -> key))
            return(0);
    }
    p = malloc(sizeof(CELL));
    strcpy(p -> key, key);
    strcpy(p -> tel, tel);
    return(1);
}
/*  list_up  -- ハッシュ表に登録されている要素を列挙する */
/*              登録件数を返す                           */
int list_up(void)
{
    int i, cnt = 0;
    CELL *p;
    
    
    for (i = 0; i < TBL_SIZE; i++){
        if(table[i] != NULL){
            for(p = table[i]; p != NULL; p = p -> next, cnt++)
                printf("%d : %s %s\n", cnt, p -> key, p -> tel);
        }
    }
    return(cnt);
}

/*  init  -- ハッシュ表を初期化する  */
void init(void)
{
    int i;

    for (i = 0; i < TBL_SIZE; i++)
        table[i] = NULL;
}

/* ハッシュ値 = 各文字コードの和 % ハッシュ表の大きさ */
int hash(char *s)
{
    int i = 0;
    
    while(*s){     /* NULL になったらループを抜ける */
        i += *s++; /* *(s++)の意味 */
    }
    return(i % TBL_SIZE);
}




No.17652

Re:構造体を用いたハッシュ法について
投稿者---かずま(2004/10/31 23:08:17)


    for (p = table[h]; p != NULL; p = p -> next)
        if (strcmp(key, p->key) == 0) return 0;
    p = malloc(sizeof(CELL));
    strcpy(p->key, key);
    strcpy(p->tel, tel);
    p->next = table[h];
    table[h] = p;
    return 1;



No.17827

Re:構造体を用いたハッシュ法について
投稿者---かずま(2004/11/05 23:40:34)


>   for (p = table[h]; p != NULL; p = p -> next)
>       if (strcmp(key, p->key) == 0) return 0;
>   p = malloc(sizeof(CELL));
>   strcpy(p->key, key);
>   strcpy(p->tel, tel);
>   p->next = table[h];
>   table[h] = p;
>   return 1;

    p = malloc(sizeof(CELL));

の次に

    if (p == NULL) puts("out of memory"), exit(1);

を追加。

修正内容について何も説明しなかったのは、見れば分かると思ったからですが、
要するに strcmp の結果判定と、table[h] に p をつなぐ処理が必要だという
ことですね。

質問者はもう見ていないのでしょうか?
回答をもらったら、結果を報告するのがマナーでは?



No.17848

Re:構造体を用いたハッシュ法について
投稿者---Y.M(2004/11/07 21:27:35)


返答遅くなって申し訳ございません。
言い訳にしか聞こえないかもしれませんが、
今週は何かと多忙だったので、返答が遅くなりました。
回答のほう見せて頂きましたところ、
プログラムに反映させるとうまく動きました。
おかげでハッシュ表を完成させることができました。
本当にありがとうございます。