BohYoh.comトップページへ

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

戻る  

演習3-7(その1)の解答

 List 3-11は、番号をキー値としている。氏名をキー値に変更したプログラムを作成せよ。

/* 演習3-7《その1》 ハッシュ(チェイン法)の実現例(キーは氏名) */ #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); }


戻る