Ｃ言語によるアルゴリズムとデータ構造

戻る  

演習3-7（その１）の解答

/*
    演習3-7《その１》
    ハッシュ（チェイン法）の実現例（キーは氏名）
*/

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

#define  NO     1               /* 番号（入力用）*/
#define  NAME   2               /* 氏名（入力用）*/

/*--- メニュー ---*/
typedef enum {
    Term, Insert, Delete, SrchNo, Dump
} Menu;

/*--- データ ---*/
typedef struct {
    int   no;                   /* 番号 */
    char  name[10];             /* 氏名 */
} Data;

/*--- ノード ---*/
typedef struct __node {
    Data           data;        /* データ */
    struct __node  *next;       /* 後続ノードへのポインタ */
} Node;

/*--- ハッシュ表 ---*/
typedef struct {
    int   size;                 /* ハッシュ表の大きさ */
    Node  **table;              /* ハッシュ表の先頭要素へのポインタ */
} Hash;

/*--- ハッシュ関数（keyのハッシュ値を返す） ---*/
int hash(char *key)
{
    unsigned h = 0;

    while (*key)
        h += *(key++);
    return (h % 13);
}

/*--- ノードの各メンバに値を設定 ----*/
void SetNode(Node *n, Data x, Node *next)
{
    n->data = x;                        /* データ */
    n->next = next;                     /* 後続ノードへのポインタ */
}

/*--- ハッシュ表を初期化 ---*/
int InitHash(Hash *h, int size)
{
    int  i;

    h->size = 0;
    if ((h->table = calloc(size, sizeof(Node *))) == NULL)
        return (0);

    h->size = size;
    for (i = 0; i < size; i++)
        h->table[i] = NULL;
    return (1);
}

/*--- ハッシュ表を後始末 ---*/
void TermHash(Hash *h)
{
    int  i;

    for (i = 0; i < h->size; i++) {
        Node  *p = h->table[i];
        while (p != NULL) {
            Node  *next = p->next;
            free(p);
            p = next;
        }
    }
    free(h->table);
}

/*--- 探索 ---*/
Node *SearchNode(Hash *h, Data x)
{
    int   key = hash(x.name);           /* 探索するデータのハッシュ値 */
    Node  *p = h->table[key];           /* 着目ノード */

    while (p != NULL) {
        if (!strcmp(p->data.name, x.name))  /* 探索成功 */
            return (p);
        p = p->next;                    /* 後続ノードに着目 */
    }
    return (NULL);                      /* 探索失敗 */
}

/*--- データの追加 ---*/
int InsertNode(Hash *h, Data x)
{
    int   key = hash(x.name);           /* 追加するデータのハッシュ値 */
    Node  *p = h->table[key];           /* 着目ノード */
    Node  *temp;

    while (p != NULL) {
        if (p->data.no == x.no)         /* このキーは登録済み */
            return (1);
        p = p->next;                    /* 後続ノードに着目 */
    }
    if ((temp = (Node *)calloc(1, sizeof(Node))) == NULL)
        return (2);
    SetNode(temp, x, h->table[key]);    /* 追加するノードに値を設定 */
    h->table[key] = temp;
    return (0);
}

/*--- データの削除 ---*/
int DeleteNode(Hash *h, Data x)
{
    int   key = hash(x.name);           /* 削除するデータのハッシュ値 */
    Node  *p = h->table[key];           /* 着目ノード */
    Node  **pp = &h->table[key];        /* 着目ノードへのポインタ */

    while (p != NULL) {
        if (!strcmp(p->data.name, x.name)) {    /* 見つけたら */
            *pp = p->next;
            free(p);                    /* 解放 */
            return (0);
        }
        pp = &p->next;
        p = p->next;                    /* 後続ノードに着目 */
    }
    return (1);                         /* そのキー値は存在しない */
}

/*--- ハッシュ表をダンプ ---*/
void DumpHash(Hash *h)
{
    int  i;

    for (i = 0; i < h->size; i++) {
        Node  *p = h->table[i];
        printf("%02d  ", i);
        while (p != NULL) {
            printf("→ %d (%s)  ", p->data.no, p->data.name);
            p = p->next;
        }
        putchar('\n');
    }
}

/*--- データの番号と氏名を表示 ---*/
void PrintData(Data x)
{
    printf("%d %s\n", x.no, x.name);
}

/*--- データの入力 ---*/
Data Read(char *message, int sw)
{
    Data  temp;

    printf("%sするデータを入力してください。\n", message);

    if (sw & NO)    { printf("番号：");   scanf("%d", &temp.no);  }
    if (sw & NAME)  { printf("名前：");   scanf("%s", temp.name); }

    return (temp);
}

/*--- メニュー選択 ---*/
Menu SelectMenu(void)
{
    int  i, ch;

    do {
        printf("(1) 追加  (2) 削除  (3) 探索  (4) ダンプ  (0) 終了 ：");
        scanf("%d", &ch);
    } while (ch < Term  ||  ch > Dump);
    return ((Menu)ch);
}

/*--- メイン ---*/
int main(void)
{
    Menu  menu;
    Hash  hash;

    InitHash(&hash, 13);                            /* ハッシュ表の初期化 */

    do {
        int   result;
        Data  x;
        Node  *temp;

        switch (menu = SelectMenu()) {
         case Insert :  x = Read("追加", NO | NAME);
                        result = InsertNode(&hash, x);
                        if (result)
                            printf("追加に失敗しました（%s）。\n",
                                (result == 1) ? "登録済み" : "メモリ不足");
                        break;

         case Delete :  x = Read("削除", NAME);
                        result = DeleteNode(&hash, x);
                        if (result == 1)
                            printf("その番号のデータは存在しません。\n");
                        break;

         case SrchNo :  x = Read("探索", NAME);
                        temp = SearchNode(&hash, x);
                        if (temp == NULL)
                            printf("探索に失敗しました。\n");
                        else {
                            printf("探索に成功しました。\n");
                            PrintData(temp->data);
                        }
                        break;

         case Dump :    DumpHash(&hash);
                        break;
        }
    } while (menu != Term);

    TermHash(&hash);                                /* ハッシュ表の後始末 */

    return (0);
}

戻る