アルゴリズムとデータ構造補足資料14-2 「ダイレクトチェイニング法」

アルゴリズムとデータ構造補足資料14-2 「ダイレクトチェイニング法」
横浜国立大学理工学部数物・電子情報系学科富井尚志

外部ハッシュ法サンプルプログラム：directchaining.c ダイレクトチェイニング法／外部ハッシュ法
指定されたIDに対してハッシュ値を作成アイテムは要素リストに格納されるハッシュ表はリスト先頭を保持格納できる長さに制限がない挿入：ハッシュ値衝突の際は要素リストの先頭にアイテムを追加する削除：ハッシュ値からハッシュ表を特定し、要素リストから削除する探索：ハッシュ表の特定はO(1)だが、リストの探索にO(N/B)を要する表の埋まり具合にゆとりを持たせる(N << B)と、O(1)に近くなる

ダイレクトチェイニング法開始前 ←x: ファイルから取り出したレコード1件を保持 ←dummy: ダミーのデータ（重複キーを持つ）
struct record x jname: ename: addr : ←x: ファイルから取り出したレコード1件を保持 ←dummy: ダミーのデータ（重複キーを持つ） struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); hashtable[ 2] hashtable[ 3] hashtable[ 4] hashtable[ 5] hashtable[ 6] hashtable[ 7] hashtable[ 8] hashtable[ 9] hashtable[10] hashtable[11] hashtable[12] ↑ハッシュ表：同じハッシュ値をもつアイテムへのポインタ配列

ダイレクトチェイニング法ハッシュ表初期化
struct record x jname: ename: addr : struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] NULL hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] NULL hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] NULL hashtable[ 9] NULL hashtable[10] NULL hashtable[11] NULL hashtable[12] NULL

ダイレクトチェイニング法レコード1件目取り出し
struct record x jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] NULL hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] NULL hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] NULL hashtable[ 9] NULL hashtable[10] NULL hashtable[11] NULL hashtable[12] NULL

ダイレクトチェイニング法レコード1件目ハッシュ関数計算
struct record x jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 hash(“Yokohama Kunihiro”) = 8 struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] NULL hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] NULL hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] NULL hashtable[ 9] NULL hashtable[10] NULL hashtable[11] NULL hashtable[12] NULL

ダイレクトチェイニング法レコード1件目ハッシュ表へ登録
struct record x jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 hash(“Yokohama Kunihiro”) = 8 struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] NULL hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] NULL hashtable[ 5] NULL data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] hashtable[ 9] NULL hashtable[10] NULL hashtable[11] NULL hashtable[12] NULL

struct record x jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] NULL hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] NULL hashtable[ 5] NULL data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] hashtable[ 9] NULL hashtable[10] NULL hashtable[11] NULL hashtable[12] NULL

struct record x jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 hash(“Kanagawa Hanako”) = 4 struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] NULL hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] NULL hashtable[ 5] NULL data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] hashtable[ 9] NULL hashtable[10] NULL hashtable[11] NULL hashtable[12] NULL

struct record x jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 hash(“Kanagawa Hanako”) = 4 struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] NULL hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] hashtable[ 9] NULL hashtable[10] NULL hashtable[11] NULL hashtable[12] NULL

struct record x jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] NULL hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] hashtable[ 9] NULL hashtable[10] NULL hashtable[11] NULL hashtable[12] NULL

struct record x jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 hash(“Hato Saburo”) = 8 struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] NULL hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] hashtable[ 9] NULL hashtable[10] NULL hashtable[11] NULL hashtable[12] NULL

struct record x jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 hash(“Hato Saburo”) = 8 struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] NULL hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 id: Hato Saburo hash: 8 next: data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] hashtable[ 9] NULL hashtable[10] NULL hashtable[11] NULL hashtable[12] NULL

struct record x jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] NULL hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 id: Hato Saburo hash: 8 next: data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] hashtable[ 9] NULL hashtable[10] NULL hashtable[11] NULL hashtable[12] NULL

struct record x jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 hash(“Hojo Umeko”) = 9 struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] NULL hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 id: Hato Saburo hash: 8 next: data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] hashtable[ 9] NULL hashtable[10] NULL hashtable[11] NULL hashtable[12] NULL

struct record x jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 hash(“Hojo Umeko”) = 9 struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] NULL hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 id: Hato Saburo hash: 8 next: data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] NULL hashtable[11] NULL hashtable[12] NULL

struct record x jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] NULL hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 id: Hato Saburo hash: 8 next: data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] NULL hashtable[11] NULL hashtable[12] NULL

struct record x jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 hash(“Ashigara Kintaro”) = 0 struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] NULL hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 id: Hato Saburo hash: 8 next: data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] NULL hashtable[11] NULL hashtable[12] NULL

struct record x jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 hash(“Ashigara Kintaro”) = 0 data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 id: Hato Saburo hash: 8 next: data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] NULL hashtable[11] NULL hashtable[12] NULL

struct record x jname: 上野蘭々 ename: Ueno Ranran addr : 台東区上野公園 data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 id: Hato Saburo hash: 8 next: data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] NULL hashtable[11] NULL hashtable[12] NULL

struct record x jname: 上野蘭々 ename: Ueno Ranran addr : 台東区上野公園 hash(“Ueno Ranran”) = 9 data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 id: Hato Saburo hash: 8 next: data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] NULL hashtable[11] NULL hashtable[12] NULL

struct record x jname: 上野蘭々 ename: Ueno Ranran addr : 台東区上野公園 hash(“Ueno Ranran”) = 9 data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 id: Hato Saburo hash: 8 next: data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 上野蘭々 ename: Ueno Ranran addr : 台東区上野公園 id: Ueno Ranran hash: 9 next: data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] NULL hashtable[11] NULL hashtable[12] NULL

struct record x jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 id: Hato Saburo hash: 8 next: data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 上野蘭々 ename: Ueno Ranran addr : 台東区上野公園 id: Ueno Ranran hash: 9 next: data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] NULL hashtable[11] NULL hashtable[12] NULL

struct record x jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 hash(“Mitsuki Mausu”) = 10 data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 id: Hato Saburo hash: 8 next: data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 上野蘭々 ename: Ueno Ranran addr : 台東区上野公園 id: Ueno Ranran hash: 9 next: data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] NULL hashtable[11] NULL hashtable[12] NULL

struct record x jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 hash(“Mitsuki Mausu”) = 10 data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 id: Hato Saburo hash: 8 next: data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 上野蘭々 ename: Ueno Ranran addr : 台東区上野公園 id: Ueno Ranran hash: 9 next: data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL

struct record x jname: 野比寅右衛門 ename: Nobi Toraemon addr : 横須賀市野比 data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 id: Hato Saburo hash: 8 next: data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 上野蘭々 ename: Ueno Ranran addr : 台東区上野公園 id: Ueno Ranran hash: 9 next: data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL

struct record x jname: 野比寅右衛門 ename: Nobi Toraemon addr : 横須賀市野比 hash(“Nobi Toraemon”) = 0 data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 id: Hato Saburo hash: 8 next: data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 上野蘭々 ename: Ueno Ranran addr : 台東区上野公園 id: Ueno Ranran hash: 9 next: data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL

struct record x jname: 野比寅右衛門 ename: Nobi Toraemon addr : 横須賀市野比 hash(“Nobi Toraemon”) = 0 data: jname: 野比寅右衛門 ename: Nobi Toraemon addr : 横須賀市野比 id: Nobi Toraemon hash: 0 next: data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 id: Hato Saburo hash: 8 next: data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 上野蘭々 ename: Ueno Ranran addr : 台東区上野公園 id: Ueno Ranran hash: 9 next: data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL

ダイレクトチェイニング法登録後 ↑ハッシュ表の状態が印刷される struct record x struct record dummy
jname: ename: addr : data: jname: 野比寅右衛門 ename: Nobi Toraemon addr : 横須賀市野比 id: Nobi Toraemon hash: 0 next: data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 id: Hato Saburo hash: 8 next: data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 上野蘭々 ename: Ueno Ranran addr : 台東区上野公園 id: Ueno Ranran hash: 9 next: data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL ↑ハッシュ表の状態が印刷される

ダイレクトチェイニング法重複データ登録の試み
struct record x jname: ename: addr : data: jname: 野比寅右衛門 ename: Nobi Toraemon addr : 横須賀市野比 id: Nobi Toraemon hash: 0 next: data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 id: Hato Saburo hash: 8 next: data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 上野蘭々 ename: Ueno Ranran addr : 台東区上野公園 id: Ueno Ranran hash: 9 next: data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL

ダイレクトチェイニング法重複データ登録の試み
struct record x jname: ename: addr : hash(“Yokohama Kunihiro”) = 8 data: jname: 野比寅右衛門 ename: Nobi Toraemon addr : 横須賀市野比 id: Nobi Toraemon hash: 0 next: data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 id: Hato Saburo hash: 8 next: data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 上野蘭々 ename: Ueno Ranran addr : 台東区上野公園 id: Ueno Ranran hash: 9 next: data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL “Yokohama Kunihiro” は、すでに登録されているので登録拒否

ダイレクトチェイニング法探索1 found <(8) Hato Saburo 鳩三郎鎌倉市小町>
struct record x jname: ename: addr : hash(“Hato Saburo”) = 8 data: jname: 野比寅右衛門 ename: Nobi Toraemon addr : 横須賀市野比 id: Nobi Toraemon hash: 0 next: data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 id: Hato Saburo hash: 8 next: data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 上野蘭々 ename: Ueno Ranran addr : 台東区上野公園 id: Ueno Ranran hash: 9 next: data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL found <(8) Hato Saburo 鳩三郎鎌倉市小町> ハッシュ値8をもつリストを探索すれば見つかる

ダイレクトチェイニング法探索2 found <(8) Yokohama Kunihiro 横浜国大横浜市保土ヶ谷区常盤台>
struct record x jname: ename: addr : hash(“Yokohama Kunihiro”) = 8 data: jname: 野比寅右衛門 ename: Nobi Toraemon addr : 横須賀市野比 id: Nobi Toraemon hash: 0 next: data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 id: Hato Saburo hash: 8 next: data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 上野蘭々 ename: Ueno Ranran addr : 台東区上野公園 id: Ueno Ranran hash: 9 next: data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL found <(8) Yokohama Kunihiro 横浜国大横浜市保土ヶ谷区常盤台> 同じハッシュ値をもつ場合には、リスト内を順次探索する

ダイレクトチェイニング法削除1 struct record x struct record dummy
jname: ename: addr : data: jname: 野比寅右衛門 ename: Nobi Toraemon addr : 横須賀市野比 id: Nobi Toraemon hash: 0 next: data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 id: Hato Saburo hash: 8 next: data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 上野蘭々 ename: Ueno Ranran addr : 台東区上野公園 id: Ueno Ranran hash: 9 next: data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL

ダイレクトチェイニング法削除1: 探索 struct record x hash(“Hato Saburo”) = 8
jname: ename: addr : hash(“Hato Saburo”) = 8 data: jname: 野比寅右衛門 ename: Nobi Toraemon addr : 横須賀市野比 id: Nobi Toraemon hash: 0 next: data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 鳩三郎 ename: Hato Saburo addr : 鎌倉市小町 id: Hato Saburo hash: 8 next: data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 上野蘭々 ename: Ueno Ranran addr : 台東区上野公園 id: Ueno Ranran hash: 9 next: data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL

ダイレクトチェイニング法削除1: リストからの削除
struct record x jname: ename: addr : hash(“Hato Saburo”) = 8 data: jname: 野比寅右衛門 ename: Nobi Toraemon addr : 横須賀市野比 id: Nobi Toraemon hash: 0 next: data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 上野蘭々 ename: Ueno Ranran addr : 台東区上野公園 id: Ueno Ranran hash: 9 next: data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL

jname: ename: addr : data: jname: 野比寅右衛門 ename: Nobi Toraemon addr : 横須賀市野比 id: Nobi Toraemon hash: 0 next: data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 上野蘭々 ename: Ueno Ranran addr : 台東区上野公園 id: Ueno Ranran hash: 9 next: data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL

ダイレクトチェイニング法削除2: 探索 struct record x hash(“Ueno Ranran”) = 9
jname: ename: addr : hash(“Ueno Ranran”) = 9 data: jname: 野比寅右衛門 ename: Nobi Toraemon addr : 横須賀市野比 id: Nobi Toraemon hash: 0 next: data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 上野蘭々 ename: Ueno Ranran addr : 台東区上野公園 id: Ueno Ranran hash: 9 next: data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL

struct record x jname: ename: addr : hash(“Ueno Ranran”) = 9 data: jname: 野比寅右衛門 ename: Nobi Toraemon addr : 横須賀市野比 id: Nobi Toraemon hash: 0 next: data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL

jname: ename: addr : data: jname: 野比寅右衛門 ename: Nobi Toraemon addr : 横須賀市野比 id: Nobi Toraemon hash: 0 next: data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL

ダイレクトチェイニング法削除3: 探索 struct record x hash(“Nobi Toraemon”) = 0
jname: ename: addr : hash(“Nobi Toraemon”) = 0 data: jname: 野比寅右衛門 ename: Nobi Toraemon addr : 横須賀市野比 id: Nobi Toraemon hash: 0 next: data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL

struct record x jname: ename: addr : hash(“Nobi Toraemon”) = 0 data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL

jname: ename: addr : data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL

ダイレクトチェイニング法削除4: 探索特定されたハッシュ値からリストを探索したが、発見できなかった struct record x
jname: ename: addr : hash(“Nanashi Gonbei”) = 8 data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL 特定されたハッシュ値からリストを探索したが、発見できなかった

jname: ename: addr : data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL

ダイレクトチェイニング法削除5: 探索 struct record x hash(“Yokohama Kunihiro”) = 8
jname: ename: addr : hash(“Yokohama Kunihiro”) = 8 data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 横浜国大 ename: Yokohama Kunihiro addr : 横浜市保土ヶ谷区常盤台 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL

struct record x jname: ename: addr : hash(“Yokohama Kunihiro”) = 8 data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] NULL data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL ※削除されたのは、同じキーを持った要素だったことに注意

ダイレクトチェイニング法削除後 struct record x struct record dummy
jname: ename: addr : data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] NULL data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL

ダイレクトチェイニング法探索どちらもハッシュ表を参照するだけで、存在しないことが分かる struct record x
jname: ename: addr : hash(“Hato Saburo”) = 8 hash(“Yokohama Kunihiro”) = 8 data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] NULL data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL どちらもハッシュ表を参照するだけで、存在しないことが分かる

ダイレクトチェイニング法挿入今回挿入するレコードの内容は、dummyに書かれている内容であることに注意 struct record x
jname: ename: addr : hash(“Yokohama Kunihiro”) = 8 data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] NULL data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL 今回挿入するレコードの内容は、dummyに書かれている内容であることに注意

ダイレクトチェイニング法挿入今回挿入するレコードの内容は、dummyに書かれている内容であることに注意 struct record x
jname: ename: addr : hash(“Yokohama Kunihiro”) = 8 data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL 今回挿入するレコードの内容は、dummyに書かれている内容であることに注意

ダイレクトチェイニング法挿入後今回挿入するレコードの内容は、dummyに書かれている内容であることに注意 struct record x
jname: ename: addr : data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL 今回挿入するレコードの内容は、dummyに書かれている内容であることに注意

ダイレクトチェイニング法探索1 found <(8) Yokohama Kunihiro 横浜邦博横浜市中区日本大通>
struct record x jname: ename: addr : hash(“Yokohama Kunihiro”) = 8 data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL found <(8) Yokohama Kunihiro 横浜邦博横浜市中区日本大通> 今度の結果は、先ほど新たに挿入されたデータであることに注意

ダイレクトチェイニング法終了直前の状態 struct record x struct record dummy
jname: ename: addr : data: jname: 足柄金太郎 ename: Ashigara Kintaro addr : 南足柄市金時山 id: Ashigara Kintaro hash: 0 next: NULL struct record dummy struct item *hashtable[B] jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 hashtable[ 0] hashtable[ 1] NULL /* ハッシュ表初期化 */ makenull(hashtable); printhashtable(hashtable); /* 初期データ登録 */ while( getrecord(&x) ) insert(&x, x.ename, hashtable); /* 重複データの登録試み */ insert(&dummy, dummy.ename, hashtable); /* ハッシュ表を対象とした探索 */ printsearch("Hato Saburo", hashtable); printsearch(dummy.ename, hashtable); /* ハッシュ表からのデータ削除 */ delete("Hato Saburo", hashtable); delete("Ueno Ranran", hashtable); delete("Nobi Toraemon", hashtable); delete("Nanashi Gonbei", hashtable); delete(dummy.ename, hashtable); /* 再登録・再探索 */ printf("===Re-insert===\n"); printsearch("Mitsuki Mausu", hashtable); data: jname: 神奈川花子 ename: Kanagawa Hanako addr : 横浜市神奈川区三ッ沢上町 id: Kanagawa Hanako hash: 4 next: NULL hashtable[ 2] NULL hashtable[ 3] NULL hashtable[ 4] hashtable[ 5] NULL data: jname: 横浜邦博 ename: Yokohama Kunihiro addr : 横浜市中区日本大通 id: Yokohama Kunihiro hash: 8 next: NULL hashtable[ 6] NULL hashtable[ 7] NULL hashtable[ 8] data: jname: 北条梅子 ename: Hojo Umeko addr : 小田原市城山 id: Hojo Umeko hash: 9 next: NULL hashtable[ 9] hashtable[10] hashtable[11] NULL hashtable[12] NULL data: jname: 三月磨臼 ename: Mitsuki Mausu addr : 浦安市舞浜 id: Mitsuki Mausu hash: 10 next: NULL まとめ　動的データ管理：　探索、挿入、削除　ハッシュ表の該当箇所を見つけるには、O(1)：　登録済みのデータ件数には依存しない　ハッシュ表の要素リストの中からアイテムを見つけるには、リストの要素数に依存 O( N/B ) (平均)

アルゴリズムとデータ構造補足資料14-2 「ダイレクトチェイニング法」

Similar presentations

Presentation on theme: "アルゴリズムとデータ構造補足資料14-2 「ダイレクトチェイニング法」"— Presentation transcript:

Similar presentations

About project

フィードバック

ログインする

Auth with social network:

アルゴリズムとデータ構造 補足資料14-2 「ダイレクトチェイニング法」

Similar presentations

Presentation on theme: "アルゴリズムとデータ構造 補足資料14-2 「ダイレクトチェイニング法」"— Presentation transcript:

Similar presentations

About project

フィードバック

アルゴリズムとデータ構造補足資料14-2 「ダイレクトチェイニング法」

Presentation on theme: "アルゴリズムとデータ構造補足資料14-2 「ダイレクトチェイニング法」"— Presentation transcript: