BohYoh.comトップページへ

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

z 戻る  

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

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

/* 演習3-7《その2》 ハッシュ(オープンアドレス法)の実現例(キーは氏名) */ #include <stdio.h> #include <stdlib.h> #include <string.h> #define NO 1 /* 番号(入力用)*/ #define NAME 2 /* 氏名(入力用)*/ /*--- メニュー ---*/ typedef enum { Term, Insert, Delete, SrchNo, Dump } Menu; /*--- 要素の状態 ---*/ typedef enum { Occupied, Empty, Deleted } Status; /*--- データ ---*/ typedef struct { int no; /* 番号 */ char name[10]; /* 氏名 */ } Data; /*--- 要素 ---*/ typedef struct { Data data; /* データ */ Status stat; /* 要素の状態*/ } Bucket; /*--- ハッシュ表 ---*/ typedef struct { int size; /* ハッシュ表の大きさ */ Bucket *table; /* ハッシュ表の先頭要素へのポインタ */ } Hash; /*--- ハッシュ関数(keyのハッシュ値を返す) ---*/ int hash(char *key) { unsigned h = 0; while (*key) h += *(key++); return (h % 13); } /*--- 再ハッシュ関数 ---*/ int rehash(int key) { return ((key + 1) % 13); } /*--- ノードの各メンバに値を設定 ----*/ void SetBucket(Bucket *n, Data x, Status stat) { n->data = x; /* データ */ n->stat = stat; /* 要素の状態 */ } /*--- ハッシュ表を初期化 ---*/ int InitHash(Hash *h, int size) { int i; h->size = 0; if ((h->table = calloc(size, sizeof(Bucket))) == NULL) return (0); h->size = size; for (i = 0; i < size; i++) h->table[i].stat = Empty; return (1); } /*--- ハッシュ表を後始末 ---*/ void TermHash(Hash *h) { free(h->table); } /*--- 探索 ---*/ Bucket *SearchBucket(Hash *h, Data x) { int i; int key = hash(x.name); /* 探索するデータのハッシュ値 */ Bucket *p = &h->table[key]; /* 着目ノード */ for (i = 0; p->stat != Empty && i < h->size; i++) { if (p->stat == Occupied && !strcmp(p->data.name, x.name)) return (p); key = rehash(key); p = &h->table[key]; } return (NULL); } /*--- データの追加 ---*/ int InsertBucket(Hash *h, Data x) { int i; int key = hash(x.name); /* 追加するデータのハッシュ値 */ Bucket *p = &h->table[key]; /* 着目ノード */ if (SearchBucket(h, x)) /* このキーは登録済み */ return (1); for (i = 0; i < h->size; i++) { if (p->stat == Empty || p->stat == Deleted) { SetBucket(p, x, Occupied); return (0); } key = rehash(key); p = &h->table[key]; } return (2); /* ハッシュ表が満杯 */ } /*--- データの削除 ---*/ int DeleteBucket(Hash *h, Data x) { Bucket *p = SearchBucket(h, x); if (p == NULL) return (1); /* そのキー値は存在しない */ p->stat = Deleted; return (0); } /*--- ハッシュ表をダンプ ---*/ void DumpHash(Hash *h) { int i; for (i = 0; i < h->size; i++) { printf("%02d : ", i); switch (h->table[i].stat) { case Occupied : printf("%d (%s)\n", h->table[i].data.no, h->table[i].data.name); break; case Empty : printf("-- 未登録 --\n"); break; case Deleted : printf("-- 削除済 --\n"); break; } } } /*--- データの番号と氏名を表示 ---*/ 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; Bucket *temp; switch (menu = SelectMenu()) { case Insert : x = Read("追加", NO | NAME); result = InsertBucket(&hash, x); if (result) printf("追加に失敗しました(%s)。\n", (result == 1) ? "登録済み" : "表は満杯"); break; case Delete : x = Read("削除", NAME); result = DeleteBucket(&hash, x); if (result == 1) printf("その番号のデータは存在しません。\n"); break; case SrchNo : x = Read("探索", NAME); temp = SearchBucket(&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); }


戻る