#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct _tri {
int a; //辺 a の長さ
int b; //辺 b の長さ
int c; //辺 c の長さ
} TRI;
#define B 2003 /* ハッシュ表のサイズ */
#define occupied 0
#define empty 1
#define deleted 2
/* 配列要素のデータ型 */
typedef struct _harray {
TRI *tri; /* 登録する三角形データへのポインタ) */
int state; /* 使用状況 0:occupied, 1:empty, 2:deleted */
} HARRAY;
/* ハッシュ表 = HARRAY 型の配列(大域変数として定義) */
HARRAY H[B];
/* ハッシュ表を初期化する関数 */
void init_hash();
/* ハッシュ関数 */
int h(TRI *p, int count);
/* ハッシュに挿入する関数 */
int insert_hash(TRI *p);
/* ハッシュを探索する関数 */
int search_hash(TRI *p);
/* 1~99の乱数を得る関数 */
int GetRandom();
int main(void){
int i,coll;/*collは衝突の回数*/
srand(time(NULL));
for(i=0;i<2;i++){
TRI *q;
q = (TRI *)malloc(sizeof(TRI));
do{
q->a = GetRandom();
q->b = GetRandom();
q->c = GetRandom();
}while((q->a>=q->b+q->c)||(q->b>=q->a+q->c)||(q->c>=q->b+q->a));
do{
coll = insert_hash(q);
}while(coll=-1);
if(coll!=-2){
printf("%d回目:%d回衝突\n",i+1,coll);
}
}
init_hash();
int j,check;/*checkは探索したデータの数*/
for(j=0;j<2;j++){
TRI *r;
r = (TRI *)malloc(sizeof(TRI));
do{
r->a = GetRandom();
r->b = GetRandom();
r->c = GetRandom();
}while((r->a>=r->b+r->c)||(r->b>=r->a+r->c)||(r->c>=r->b+r->a));
do{
coll = insert_hash(r);
}while(coll=-1);
check = search_hash(r);
if(check>=0){
printf("%d個登録済で成功:%d回\n",j,check);
}
if(check<0){
printf("%d個登録済で失敗:%d\n",j,check);
}
}
return 0;
}
/* ハッシュ表を初期化する関数 */
void init_hash() {
int i;
for (i = 0; i < B; i++) H[i].state = empty;
}
/* ハッシュ関数 */
int h(TRI *p, int count){
int x = p->a;
int y = p->b;
int z = p->c;
return (x+y+z+count)%B;
}
/* ハッシュに挿入する関数 */
int insert_hash(TRI *p){
if(search_hash(p)>0){
return -1;
}
int count = 0;
int b = h(p,count);
int init_b = b;
do{
if((H[b].state == empty)||(H[b].state == deleted)){
H[b].tri = p;
H[b].state = occupied;
return count;
}
count++;
b = h(p,count);
}while(b!=init_b);
return -2;
}
/* ハッシュを探索する関数 */
int search_hash(TRI *p){
int count = 0;
int b = h(p,count);
int init_b = b;
do{
if(H[b].state == occupied){
if(H[b].tri == p) return count;
}
else if(H[b].state == empty){
return (-1)*count;
}
count++;
b = h(p,count);
}while(b!=init_b);
return 2004;
}
/* 1~99の乱数を得る関数 */
int GetRandom(){
return (rand()%99)+1;
}
【課題の概要】
TRI 型の 1 つの三角形データへのポインタ p と再ハッシュの回数 count を受け取り,ハッシュ値を返すハッ
シュ関数(兼,再ハッシュ関数)int h(TRI *p, int count) を作成せよ.なお,最初のハッシュ値を求
めるときには,count の値を 0 として呼び出すことを想定している。
TRI 型の 1 つの三角形データへのポインタ p を受け取り,これを上記のハッシュ表 H に登録する関数
int insert hash(TRI *p) を作成せよ.なお,3 辺の長さの組み合わせが同一であっても,対応する辺 a,
b, c 同士が同じ長さでない場合は,別の三角形と見なすものとし,対応する辺 a, b, c 同士が全て同じ長さ
の場合のみ,同一三角形として扱うものとする1.そして,同一の三角形データへのポインタが既に登録済
の場合には,重複登録せず,登録失敗として返り値として-1を返し(なお,このような登録失敗は,衝突と
見なさない),また,ハッシュ表がオーバーフローした場合(すなわち,配列の全ての要素にデータが入っ
ている状態で,さらにデータを登録しようとした場合)も登録失敗と考え,返り値として-2を返すものと
する.三角形データの登録に成功した場合には,登録が完了するまでの衝突回数を返すものとする(一度
も衝突せずに登録に成功した場合には 0 を返す).なお,この衝突回数には,与えられた三角形と同一の
三角形が既に登録済かどうかを調べる際の衝突回数は含めないこと.
TRI 型の(1 つの)三角形データへのポインタ p を受け取り,そのデータと同一の三角形を探索する関数
int search hash(TRI *p) を作成せよ.なお,この関数は,データを発見した場合には,返り値として,
そのデータを発見するまでに訪問した配列要素の個数を返すものとする2(すなわち,最初の配列要素でデー
タが発見できた場合には1を返す).また,データを発見できなかった場合には,データが格納されていないこ
とが判明するまでに訪問した配列要素の個数に (−1) を掛けた値を返すものとする(例えば,3 個の配列要
素をチェックした結果,データが存在しないことがわかれば,-3 を返す)
上記のコードをもとに以下の手順に沿って実行する。
(1) 関数 malloc を用いて,TRI 型の三角形データの領域を確保する.各辺 a, b, c の長さを 1 以上 100 未満と
し,乱数を用いて得られた 3 辺 a, b, c の長さを上記で確保した領域に代入することにより,1 つの TRI 型
の三角形データを生成する.このとき,三角形が成立する条件(a < b + c, b < a + c, c < a + b を全て
満たす)が成立するもののみを採用すること.そして,その領域へのポインタを関数 insert hash を用い
ることにより,上記のハッシュ表に登録する.
(2) (1) を繰り返し,最終的に N 個(但し N < B)の三角形データが登録されるまでの途中の過程において,n
個のデータが登録された状態で,n + 1 個目のデータを登録する際に発生した衝突回数 c について記録する
(すなわち,n を 0 ∼ N − 1 まで変えながら,n + 1 個目の三角形データを登録する際の衝突回数 c を(n
の値とともに)記録する).
(3) 次に,(1) と同様に乱数を用いて 1 つの TRI 型の三角形データを生成し,そのデータと同一の三角形がハッ
シュ表 H に登録されているかどうかを探索することを考える.すなわち,既に n 個のデータが登録さ
れた状態において,関数 search hash を用いて生成したデータと同一のデータがハッシュ表に登録済かど
うかをチェックするとともに,その際に訪問した配列要素の個数 v を調査する.同じ作業を,生成する三
角形データを変えながら何回も行い,n と v の組み合わせを,データの発見に成功した場合と失敗した場
合に分けて記録する.以上の処理を,登録済のデータ数 n を変えながら繰り返し,最終的に様々な n に対
する複数の v の値を(データの発見に成功した場合と失敗した場合に分けて)集計する.