アルゴリズムとデータ構造
補足資料14-2
「ダイレクトチェイニング法」
横浜国立大学
理工学部
数物・電子情報系学科
富井尚志
外部ハッシュ法
サンプルプログラム：directchaining.c
• ダイレクトチェイニング法／外部ハッシュ法
• 指定されたIDに対してハッシュ値を作成
• アイテムは要素リストに格納される
• ハッシュ表はリスト先頭を保持
• 格納できる長さに制限がない
• 挿入：ハッシュ値衝突の際は要素リストの先頭にアイテムを追加する
• 削除：ハッシュ値からハッシュ表を特定し、要素リストから削除する
• 探索：ハッシュ表の特定はO(1)だが、リストの探索にO(N/B)を要する
– 表の埋まり具合にゆとりを持たせる(N << B)と、O(1)に近くなる
ダイレクトチェイニング法
開始前
struct record x
ename:
jname:
addr :
struct record dummy
←x: ファイルから取り出したレコード1件を保持
←dummy: ダミーのデータ（重複キーを持つ）
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
struct item *hashtable[B]
hashtable[ 0]
hashtable[ 1]
hashtable[ 2]
hashtable[ 3]
hashtable[ 4]
hashtable[ 5]
hashtable[ 6]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
hashtable[ 8]
hashtable[10]
hashtable[11]
hashtable[12]
↑ハッシュ表： 同じハッシュ値をもつアイテムへのポインタ配列
struct record x
ename:
jname:
addr :
ダイレクトチェイニング法
ハッシュ表初期化
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
struct item *hashtable[B]
hashtable[ 0]
NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
hashtable[ 4]
NULL
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
hashtable[ 8]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
NULL
hashtable[10]
NULL
hashtable[11]
NULL
hashtable[12]
NULL
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
struct record x
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
ダイレクトチェイニング法
レコード1件目取り出し
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
struct item *hashtable[B]
hashtable[ 0]
NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
hashtable[ 4]
NULL
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
hashtable[ 8]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
NULL
hashtable[10]
NULL
hashtable[11]
NULL
hashtable[12]
NULL
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
ダイレクトチェイニング法
レコード1件目ハッシュ関数計算
struct record x
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hash(“Yokohama Kunihiro”) = 8
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
struct item *hashtable[B]
hashtable[ 0]
NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
hashtable[ 4]
NULL
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
hashtable[ 8]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
NULL
hashtable[10]
NULL
hashtable[11]
NULL
hashtable[12]
NULL
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
ダイレクトチェイニング法
レコード1件目ハッシュ表へ登録
struct record x
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
hash(“Yokohama Kunihiro”) = 8
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
struct item *hashtable[B]
hashtable[ 0]
NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
hashtable[ 4]
NULL
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
NULL
hashtable[10]
NULL
hashtable[11]
NULL
hashtable[12]
NULL
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next: NULL
hashtable[ 8]
struct record x
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
ダイレクトチェイニング法
レコード2件目取り出し
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
struct item *hashtable[B]
hashtable[ 0]
NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
hashtable[ 4]
NULL
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
NULL
hashtable[10]
NULL
hashtable[11]
NULL
hashtable[12]
NULL
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next: NULL
hashtable[ 8]
ダイレクトチェイニング法
レコード2件目ハッシュ関数計算
struct record x
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hash(“Kanagawa Hanako”) = 4
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
struct item *hashtable[B]
hashtable[ 0]
NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
hashtable[ 4]
NULL
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
NULL
hashtable[10]
NULL
hashtable[11]
NULL
hashtable[12]
NULL
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next: NULL
hashtable[ 8]
ダイレクトチェイニング法
レコード2件目ハッシュ表へ登録
struct record x
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hash(“Kanagawa Hanako”) = 4
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
next: NULL
hashtable[ 4]
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
NULL
hashtable[10]
NULL
hashtable[11]
NULL
hashtable[12]
NULL
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next: NULL
hashtable[ 8]
struct record x
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
ダイレクトチェイニング法
レコード3件目取り出し
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
next: NULL
hashtable[ 4]
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
NULL
hashtable[10]
NULL
hashtable[11]
NULL
hashtable[12]
NULL
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next: NULL
hashtable[ 8]
ダイレクトチェイニング法
レコード3件目ハッシュ関数計算
struct record x
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hash(“Hato Saburo”) = 8
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
next: NULL
hashtable[ 4]
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
NULL
hashtable[10]
NULL
hashtable[11]
NULL
hashtable[12]
NULL
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next: NULL
hashtable[ 8]
ダイレクトチェイニング法
レコード3件目ハッシュ表へ登録
struct record x
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
hash(“Hato Saburo”) = 8
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
next: NULL
hashtable[ 4]
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
NULL
hashtable[10]
NULL
hashtable[11]
NULL
hashtable[12]
NULL
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 8]
id: Hato Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next:
next: NULL
struct record x
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
ダイレクトチェイニング法
レコード4件目取り出し
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
next: NULL
hashtable[ 4]
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
NULL
hashtable[10]
NULL
hashtable[11]
NULL
hashtable[12]
NULL
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 8]
id: Hato Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next:
next: NULL
ダイレクトチェイニング法
レコード4件目ハッシュ関数計算
struct record x
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hash(“Hojo Umeko”) = 9
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
next: NULL
hashtable[ 4]
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
NULL
hashtable[10]
NULL
hashtable[11]
NULL
hashtable[12]
NULL
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
hashtable[ 8]
id: Hato Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next:
next: NULL
ダイレクトチェイニング法
レコード4件目ハッシュ表へ登録
struct record x
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hash(“Hojo Umeko”) = 9
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
next: NULL
hashtable[ 4]
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
id: Hato Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next:
next: NULL
hashtable[ 8]
hashtable[10]
NULL
hashtable[11]
NULL
hashtable[12]
NULL
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
next: NULL
struct record x
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
ダイレクトチェイニング法
レコード5件目取り出し
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
next: NULL
hashtable[ 4]
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
id: Hato Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next:
next: NULL
hashtable[ 8]
hashtable[10]
NULL
hashtable[11]
NULL
hashtable[12]
NULL
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
next: NULL
ダイレクトチェイニング法
レコード5件目ハッシュ関数計算
struct record x
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hash(“Ashigara Kintaro”) = 0
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
next: NULL
hashtable[ 4]
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
id: Hato Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next:
next: NULL
hashtable[ 8]
hashtable[10]
NULL
hashtable[11]
NULL
hashtable[12]
NULL
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
next: NULL
ダイレクトチェイニング法
レコード5件目ハッシュ表へ登録
struct record x
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
hash(“Ashigara Kintaro”) = 0
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
next: NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
next: NULL
hashtable[ 4]
hashtable[ 5]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
id: Hato Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next:
next: NULL
hashtable[ 8]
hashtable[10]
NULL
hashtable[11]
NULL
hashtable[12]
NULL
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
next: NULL
struct record x
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
ダイレクトチェイニング法
レコード6件目取り出し
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
next: NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
next: NULL
hashtable[ 4]
hashtable[ 5]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
id: Hato Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next:
next: NULL
hashtable[ 8]
hashtable[10]
NULL
hashtable[11]
NULL
hashtable[12]
NULL
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
next: NULL
ダイレクトチェイニング法
レコード6件目ハッシュ関数計算
struct record x
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hash(“Ueno Ranran”) = 9
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
next: NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
next: NULL
hashtable[ 4]
hashtable[ 5]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
id: Hato Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next:
next: NULL
hashtable[ 8]
hashtable[10]
NULL
hashtable[11]
NULL
hashtable[12]
NULL
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
next: NULL
ダイレクトチェイニング法
レコード6件目ハッシュ表へ登録
struct record x
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
hash(“Ueno Ranran”) = 9
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
next: NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
next: NULL
hashtable[ 4]
hashtable[ 5]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
id: Hato Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next:
next: NULL
id: Ueno Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
next:
next: NULL
hashtable[ 8]
hashtable[10]
NULL
hashtable[11]
NULL
hashtable[12]
NULL
struct record x
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
ダイレクトチェイニング法
レコード7件目取り出し
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
next: NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
next: NULL
hashtable[ 4]
hashtable[ 5]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
id: Hato Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next:
next: NULL
id: Ueno Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
next:
next: NULL
hashtable[ 8]
hashtable[10]
NULL
hashtable[11]
NULL
hashtable[12]
NULL
ダイレクトチェイニング法
レコード7件目ハッシュ関数計算
struct record x
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
hash(“Mitsuki Mausu”) = 10
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
next: NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
next: NULL
hashtable[ 4]
hashtable[ 5]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
id: Hato Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next:
next: NULL
id: Ueno Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
next:
next: NULL
hashtable[ 8]
hashtable[10]
NULL
hashtable[11]
NULL
hashtable[12]
NULL
ダイレクトチェイニング法
レコード7件目ハッシュ表へ登録
struct record x
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
hash(“Mitsuki Mausu”) = 10
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
next: NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
next: NULL
hashtable[ 4]
hashtable[ 5]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
id: Hato Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next:
next: NULL
id: Ueno Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
next:
next: NULL
hashtable[ 8]
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
struct record x
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
ダイレクトチェイニング法
レコード8件目取り出し
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
next: NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
next: NULL
hashtable[ 4]
hashtable[ 5]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
id: Hato Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next:
next: NULL
id: Ueno Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
next:
next: NULL
hashtable[ 8]
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
ダイレクトチェイニング法
レコード8件目ハッシュ関数計算
struct record x
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hash(“Nobi Toraemon”) = 0
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
next: NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
next: NULL
hashtable[ 4]
hashtable[ 5]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
id: Hato Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next:
next: NULL
id: Ueno Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
next:
next: NULL
hashtable[ 8]
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
ダイレクトチェイニング法
レコード8件目ハッシュ表へ登録
struct record x
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
hash(“Nobi Toraemon”) = 0
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
next:
next: NULL
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
next: NULL
hashtable[ 4]
hashtable[ 5]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
id: Nobi Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
id: Hato Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next:
next: NULL
id: Ueno Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
next:
next: NULL
hashtable[ 8]
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
struct record x
ename:
jname:
addr :
ダイレクトチェイニング法
登録後
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
next:
next: NULL
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
next: NULL
hashtable[ 4]
hashtable[ 5]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
id: Nobi Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
id: Hato Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next:
next: NULL
id: Ueno Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
next:
next: NULL
hashtable[ 8]
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
↑ハッシュ表の状態が印刷される
struct record x
ename:
jname:
addr :
ダイレクトチェイニング法
重複データ登録の試み
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
next:
next: NULL
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
next: NULL
hashtable[ 4]
hashtable[ 5]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
id: Nobi Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
id: Hato Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next:
next: NULL
id: Ueno Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
next:
next: NULL
hashtable[ 8]
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
ダイレクトチェイニング法
重複データ登録の試み
struct record x
ename:
jname:
addr :
hash(“Yokohama Kunihiro”) = 8
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
next:
next: NULL
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
next: NULL
hashtable[ 4]
hashtable[ 5]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
id: Nobi Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
id: Hato Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next:
next: NULL
id: Ueno Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
next:
next: NULL
hashtable[ 8]
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
“Yokohama Kunihiro” は、すでに登録されているので登録拒否
ダイレクトチェイニング法
探索1
struct record x
ename:
jname:
addr :
hash(“Hato Saburo”) = 8
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
next:
next: NULL
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
next: NULL
hashtable[ 4]
hashtable[ 5]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
id: Nobi Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
id: Hato Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next:
next: NULL
id: Ueno Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
next:
next: NULL
hashtable[ 8]
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
found <(8) Hato Saburo 鳩三郎 鎌倉市小町>
ハッシュ値8をもつリストを探索すれば見つかる
ダイレクトチェイニング法
探索2
struct record x
ename:
jname:
addr :
hash(“Yokohama Kunihiro”) = 8
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
next:
next: NULL
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
next: NULL
hashtable[ 4]
hashtable[ 5]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
id: Nobi Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
id: Hato Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next:
next: NULL
id: Ueno Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
next:
next: NULL
hashtable[ 8]
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
found <(8) Yokohama Kunihiro 横浜国大 横浜市保土ヶ谷区常盤台>
同じハッシュ値をもつ場合には、リスト内を順次探索する
struct record x
ename:
jname:
addr :
ダイレクトチェイニング法
削除1
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
next:
next: NULL
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
next: NULL
hashtable[ 4]
hashtable[ 5]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
id: Nobi Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
id: Hato Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next:
next: NULL
id: Ueno Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
next:
next: NULL
hashtable[ 8]
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
ダイレクトチェイニング法
削除1: 探索
struct record x
ename:
jname:
addr :
hash(“Hato Saburo”) = 8
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
next:
next: NULL
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
next: NULL
hashtable[ 4]
hashtable[ 5]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
id: Nobi Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
id: Hato Saburo
hash: 8
data:
ename: Hato Saburo
jname: 鳩三郎
addr : 鎌倉市小町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next:
next: NULL
id: Ueno Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
next:
next: NULL
hashtable[ 8]
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
ダイレクトチェイニング法
削除1: リストからの削除
struct record x
ename:
jname:
addr :
hash(“Hato Saburo”) = 8
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
next:
next: NULL
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
next: NULL
hashtable[ 4]
hashtable[ 5]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
id: Nobi Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next: NULL
hashtable[ 8]
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
id: Ueno Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
next:
next: NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
struct record x
ename:
jname:
addr :
ダイレクトチェイニング法
削除2
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
next:
next: NULL
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
next: NULL
hashtable[ 4]
hashtable[ 5]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
id: Nobi Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next: NULL
hashtable[ 8]
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
id: Ueno Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
next:
next: NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
ダイレクトチェイニング法
削除2: 探索
struct record x
ename:
jname:
addr :
hash(“Ueno Ranran”) = 9
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
next:
next: NULL
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
next: NULL
hashtable[ 4]
hashtable[ 5]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
id: Nobi Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next: NULL
hashtable[ 8]
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
id: Ueno Ranran
hash: 9
data:
ename: Ueno Ranran
jname: 上野蘭々
addr : 台東区上野公園
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
next:
next: NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
ダイレクトチェイニング法
削除2: リストからの削除
struct record x
ename:
jname:
addr :
hash(“Ueno Ranran”) = 9
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
next:
next: NULL
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
next: NULL
hashtable[ 4]
hashtable[ 5]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
id: Nobi Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next: NULL
hashtable[ 8]
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
next: NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
struct record x
ename:
jname:
addr :
ダイレクトチェイニング法
削除3
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
next:
next: NULL
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
next: NULL
hashtable[ 4]
hashtable[ 5]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
id: Nobi Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next: NULL
hashtable[ 8]
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
next: NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
ダイレクトチェイニング法
削除3: 探索
struct record x
ename:
jname:
addr :
hash(“Nobi Toraemon”) = 0
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
next:
next: NULL
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
next: NULL
hashtable[ 4]
hashtable[ 5]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
id: Nobi Toraemon
hash: 0
data:
ename: Nobi Toraemon
jname: 野比寅右衛門
addr : 横須賀市野比
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next: NULL
hashtable[ 8]
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
next: NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
ダイレクトチェイニング法
削除3: リストからの削除
struct record x
ename:
jname:
addr :
hash(“Nobi Toraemon”) = 0
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
next: NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
next: NULL
hashtable[ 4]
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next: NULL
hashtable[ 8]
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
next: NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
struct record x
ename:
jname:
addr :
ダイレクトチェイニング法
削除4
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
next: NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
next: NULL
hashtable[ 4]
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next: NULL
hashtable[ 8]
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
next: NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
ダイレクトチェイニング法
削除4: 探索
struct record x
ename:
jname:
addr :
hash(“Nanashi Gonbei”) = 8
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
next: NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
next: NULL
hashtable[ 4]
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next: NULL
hashtable[ 8]
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
next: NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
特定されたハッシュ値からリストを探索したが、発見できなかった
struct record x
ename:
jname:
addr :
ダイレクトチェイニング法
削除5
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
next: NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
next: NULL
hashtable[ 4]
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next: NULL
hashtable[ 8]
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
next: NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
ダイレクトチェイニング法
削除5: 探索
struct record x
ename:
jname:
addr :
hash(“Yokohama Kunihiro”) = 8
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
next: NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
next: NULL
hashtable[ 4]
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
id: Yokohama Kunihiro
hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜国大
addr : 横浜市保土ヶ谷区常盤台
next: NULL
hashtable[ 8]
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
next: NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
ダイレクトチェイニング法
削除5: リストからの削除
struct record x
ename:
jname:
addr :
hash(“Yokohama Kunihiro”) = 8
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
next: NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
next: NULL
hashtable[ 4]
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
hashtable[ 8]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
next: NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
※削除されたのは、同じキーを持った要素だったことに注意
struct record x
ename:
jname:
addr :
ダイレクトチェイニング法
削除後
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
next: NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
next: NULL
hashtable[ 4]
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
hashtable[ 8]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
next: NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
ダイレクトチェイニング法
探索
struct record x
ename:
jname:
addr :
hash(“Hato Saburo”) = 8
hash(“Yokohama Kunihiro”) = 8
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
next: NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
next: NULL
hashtable[ 4]
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
hashtable[ 8]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
next: NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
どちらもハッシュ表を参照するだけで、存在しないことが分かる
ダイレクトチェイニング法
挿入
struct record x
ename:
jname:
addr :
hash(“Yokohama Kunihiro”) = 8
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
next: NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
next: NULL
hashtable[ 4]
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
hashtable[ 8]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
next: NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
今回挿入するレコードの内容は、dummyに書かれている内容であることに注意
ダイレクトチェイニング法
挿入
struct record x
ename:
jname:
addr :
hash(“Yokohama Kunihiro”) = 8
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
next: NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
next: NULL
hashtable[ 4]
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
id: Yokohama Kunihiro hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
next: NULL
hashtable[ 8]
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
next: NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
今回挿入するレコードの内容は、dummyに書かれている内容であることに注意
struct record x
ename:
jname:
addr :
ダイレクトチェイニング法
挿入後
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
next: NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
next: NULL
hashtable[ 4]
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
id: Yokohama Kunihiro hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
next: NULL
hashtable[ 8]
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
next: NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
今回挿入するレコードの内容は、dummyに書かれている内容であることに注意
ダイレクトチェイニング法
探索1
struct record x
ename:
jname:
addr :
hash(“Yokohama Kunihiro”) = 8
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
next: NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
next: NULL
hashtable[ 4]
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
id: Yokohama Kunihiro hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
next: NULL
hashtable[ 8]
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
next: NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
found <(8) Yokohama Kunihiro 横浜邦博 横浜市中区日本大通>
今度の結果は、先ほど新たに挿入されたデータであることに注意
struct record x
ename:
jname:
addr :
ダイレクトチェイニング法
終了直前の状態
id: Ashigara Kintaro
hash: 0
data:
ename: Ashigara Kintaro
jname: 足柄金太郎
addr : 南足柄市金時山
struct record dummy
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
/* ハッシュ表初期化 */
makenull(hashtable);
printhashtable(hashtable);
/* 初期データ登録 */
while( getrecord(&x) )
insert(&x, x.ename, hashtable);
printhashtable(hashtable);
struct item *hashtable[B]
hashtable[ 0]
next: NULL
hashtable[ 1]
NULL
hashtable[ 2]
NULL
hashtable[ 3]
NULL
next: NULL
hashtable[ 4]
hashtable[ 5]
NULL
hashtable[ 6]
NULL
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
hashtable[ 7]
NULL
/* ハッシュ表からのデータ削除 */
delete("Hato Saburo", hashtable);
delete("Ueno Ranran", hashtable);
delete("Nobi Toraemon", hashtable);
delete("Nanashi Gonbei", hashtable);
delete(dummy.ename, hashtable);
printhashtable(hashtable);
hashtable[ 9]
/* 重複データの登録試み */
insert(&dummy, dummy.ename, hashtable);
/* ハッシュ表を対象とした探索 */
printsearch("Hato Saburo", hashtable);
printsearch(dummy.ename, hashtable);
/* 再登録・再探索 */
printf("===Re-insert===\n");
insert(&dummy, dummy.ename, hashtable);
printsearch(dummy.ename, hashtable);
printsearch("Mitsuki Mausu", hashtable);
printhashtable(hashtable);
id: Kanagawa Hanako hash: 4
data:
ename: Kanagawa Hanako
jname: 神奈川花子
addr : 横浜市神奈川区三ッ沢上町
id: Yokohama Kunihiro hash: 8
data:
ename: Yokohama Kunihiro
jname: 横浜邦博
addr : 横浜市中区日本大通
next: NULL
hashtable[ 8]
id: Hojo Umeko
hash: 9
data:
ename: Hojo Umeko
jname: 北条梅子
addr : 小田原市城山
hashtable[10]
hashtable[11]
NULL
hashtable[12]
NULL
next: NULL
id: Mitsuki Mausu
hash: 10
data:
ename: Mitsuki Mausu
jname: 三月磨臼
addr : 浦安市舞浜
next: NULL
まとめ
•動的データ管理： 探索、挿入、削除
• ハッシュ表の該当箇所を見つけるには、O(1)： 登録済みのデータ件数には依存しない
• ハッシュ表の要素リストの中からアイテムを見つけるには、リストの要素数に依存 O( N/B ) (平均)

Bitches - Jaquenetta

Startliste Trainingsdressur

Document

Declaration of Conformity

通知書サンプル