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

Slides:

Advertisements

Similar presentations

1 T HE U NIVERSITY OF T OKYO D EPARTMENT OF M ATHEMATICAL I NFORMATICS 数理情報工学演習第一Ｃプログラミング演習 ( 第 6 回 ) 2014/05/19.

Advertisements

【事例演習5】　字句解析　　　　解　説　“ハッシュを用いた字句解析の方法”.

アルゴリズムとデータ構造第２回　線形リスト（復習）.

基本情報技術概論 I 演習（第５回）埼玉大学理工学研究科堀山貴史

アルゴリズムとデータ構造補足資料13-4 「2分探索木の追加・削除（ダイジェスト）」

情報工学概論 (アルゴリズムとデータ構造)

情報システム基盤学基礎1 アルゴリズムとデータ構造

独習Java ・　10.6　　Hashtableクラス・　10.7　　String Tokenizerクラス　１２月１２日　　　小笠原　一恵.

オペレーティングシステムJ/K 2004年11月4日

アルゴリズムとデータ構造補足資料7-3 「単純選択ソートselsort.c」

データ構造とアルゴリズム第4回リスト～データ構造（１）～.

アルゴリズムとデータ構造補足資料4-2 「線形探索」

アルゴリズムとデータ構造補足資料6-3 「サンプルプログラムcat3.c」

第７章　データベース管理システム７．１データベース管理システムの概要７．２データベースの格納方式７．３問合せ処理.

エージェントを管理するボスの苦悩問題 n人のエージェントを部下に持つボスがいる．エージェントは出張・帰還を頻繁に繰り返す．

アルゴリズムとデータ構造第２回　線形リスト（復習その２）.

INSERT(x,p,L)の例（一部）磯直行 2009年5月5日

データ構造とアルゴリズム第八回知能情報学部新田直也.

アルゴリズムとデータ構造補足資料10-2 「nクイーン」

アルゴリズムとデータ構造 2011年6月20日

データ構造とアルゴリズム第十一回理工学部情報システム工学科新田直也.

データ構造とアルゴリズム第四回知能情報学部新田直也.

第3回配列，構造体，ポインタ～データ構造について学ぶための基礎～

第13回　ハッシュテーブルを使ったプログラム～高速に検索するには？～.

ハッシュテーブル.

ハッシュ表データ構造とプログラミング（１２）

データ構造とアルゴリズム第4回リスト～データ構造（１）～.

データ構造とアルゴリズム第6回キュー～データ構造（2）～.

アルゴリズムとデータ構造補足資料11-1 「mallocとfree」

2005年度データ構造とアルゴリズム第３回「C言語の復習：再帰的データ構造」

アルゴリズムとデータ構造補足資料5-2 「サンプルプログラムsetop.c」

アルゴリズムとデータ構造補足資料10-1 「騎士巡回」

アルゴリズムとデータ構造勉強会第６回スレッド木

アルゴリズムとデータ構造補足資料4-1 「メモリと配列」

アルゴリズムとデータ構造補足資料5-1 「メモリとポインタ」

アルゴリズムとデータ構造補足資料6-2 「サンプルプログラムcat2.c」

第9回優先度つき待ち行列，ヒープ，二分探索木

データ構造とアルゴリズム第五回知能情報学部新田直也.

Cプログラミング演習第１０回　二分探索木.

アルゴリズムとデータ構造1 2005年7月5日

2005年度データ構造とアルゴリズム第6回「ハッシュ法を用いた探索」

アルゴリズムとデータ構造 2011年7月8日課題の復習

簡易データベース情報画像工学実験 I : 実験２担当：関屋大雄（工学部１号棟５１５室）

６．データ構造入門６－１．連結リスト(Linked List) ６－２．スタック(Stack) ６－３．キュー(Queue)

データ構造とアルゴリズム第11回リスト構造（１）

第9回優先度つき待ち行列，ヒープ，二分探索木

アルゴリズムとデータ構造1 2006年7月4日

コレクション・フレームワーク J2EE I (データベース論) 第6回 /

コレクション・フレームワークデータベース論第7回.

オペレーティングシステムJ/K (管理のためのデータ構造)

アルゴリズムとデータ構造1 2006年6月23日

基本情報技術概論（第６回）埼玉大学理工学研究科堀山貴史

第11回放送授業.

アルゴリズムとデータ構造1 2009年6月15日

アルゴリズムとデータ構造補足資料11-3 「線形リストのオペレータ」

ネットワーク・プログラミング Cプログラミングの基礎.

プログラミング論構造体

お問合せ：留学生支援相談窓口（KANAFAN STATION）

アルゴリズムとデータ構造 2012年6月21日

アルゴリズムとデータ構造補足資料7-1 「メモリでの『構造体の配列』」

アルゴリズムとデータ構造補足資料6-1 「サンプルプログラムcat1.c」

アルゴリズムとデータ構造 2010年6月17日

アルゴリズムとデータ構造補足資料5-3 「サンプルプログラムstrcat.c」

新人研修発表平成１３年５月１４日（月）探索アルゴリズム　ハッシュ法について株式会社　エーアイネット・テクノロジ　　　　　　　　　須田　哲生.

データ構造とアルゴリズム第四回知能情報学部新田直也.

アルゴリズムとデータ構造1 2005年7月12日

アルゴリズムとデータ構造1 2007年7月6日

JXTA総まとめ P2P特論最終回 /

TList リスト構造とは？複数のデータを扱うために、データの内容と、次のデータへのポインタを持つ構造体を使う。

Ibaraki Univ. Dept of Electrical & Electronic Eng.

Presentation transcript:

アルゴリズムとデータ構造補足資料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

ダイレクトチェイニング法レコード2件目取り出し 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

ダイレクトチェイニング法レコード2件目ハッシュ関数計算 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

ダイレクトチェイニング法レコード2件目ハッシュ表へ登録 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

ダイレクトチェイニング法レコード3件目取り出し 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

ダイレクトチェイニング法レコード3件目ハッシュ関数計算 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

ダイレクトチェイニング法レコード3件目ハッシュ表へ登録 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

ダイレクトチェイニング法レコード4件目取り出し 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

ダイレクトチェイニング法レコード4件目ハッシュ関数計算 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

ダイレクトチェイニング法レコード4件目ハッシュ表へ登録 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

ダイレクトチェイニング法レコード5件目取り出し 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

ダイレクトチェイニング法レコード5件目ハッシュ関数計算 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

ダイレクトチェイニング法レコード5件目ハッシュ表へ登録 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

ダイレクトチェイニング法レコード6件目取り出し 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

ダイレクトチェイニング法レコード6件目ハッシュ関数計算 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

ダイレクトチェイニング法レコード6件目ハッシュ表へ登録 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

ダイレクトチェイニング法レコード7件目取り出し 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

ダイレクトチェイニング法レコード7件目ハッシュ関数計算 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

ダイレクトチェイニング法レコード7件目ハッシュ表へ登録 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

ダイレクトチェイニング法レコード8件目取り出し 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

ダイレクトチェイニング法レコード8件目ハッシュ関数計算 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

ダイレクトチェイニング法レコード8件目ハッシュ表へ登録 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

ダイレクトチェイニング法削除2 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: 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

ダイレクトチェイニング法削除2: リストからの削除 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

ダイレクトチェイニング法削除3 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: 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

ダイレクトチェイニング法削除3: リストからの削除 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

ダイレクトチェイニング法削除4 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

ダイレクトチェイニング法削除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 特定されたハッシュ値からリストを探索したが、発見できなかった

ダイレクトチェイニング法削除5 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

ダイレクトチェイニング法削除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

ダイレクトチェイニング法削除5: リストからの削除 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 ) (平均)