//ハッシュ法を用いたデータベース管理
#include<iostream.h>
const int Nothing = -1; // 未格納であることを示す
const int N = 10; // データ格納領域の個数
// 但し格納可能個数はN-1個
int Key[N]; // キー値を格納
double Table[N];
// データ値を格納
int M = 0; // 現格納個数
//ハッシュ関数
int H(int k)
{
int n;
n
= k - N * int(k / N);
return
n;
}
// 移動チェック
int ido_check(int i,
int j)
{
int sw2 = 0;
int r = H(Key[i]); //正規の場所
if(r
<= i)
{ //正規の場所はそこから前
if(j
< i)
//
if(r
<= j) //正規の場所は削除したところから前
sw2
= 1; //移動の必要あり
}
else
{
//正規の場所はそこより後
if(j
>= r) //正規の場所は削除したところから前
sw2
= 1; //移動の必要あり
else
if(j
< i)
//
sw2
= 1; //移動の必要あり
}
return
sw2;
}
//削除処理
void Sakujoshori(int
i)
{
int j = i;
int sw1 = 0;
int sw2 = 0;
do{
Key[i] = Nothing;
Table[i] = Nothing;
//後続のデータを詰める作業
do{
i++;
if(i==N)i=0;
if(Key[i] == Nothing)
{
sw1
= 1; //これ以上後続のデータを詰める作業必要無し
break;
}
else
{
//移動の必要性チェック
sw2
= ido_check(i,j);
}
}while(sw1
== 0 || sw2 == 0);
//移動の必要性の有る場合のデータの移動処理
if(sw2
== 1)
{
sw2
= 0;
Key[j]=Key[i];
Table[j]=Table[i];
}
}while(sw1
== 0);
}
void Kakunou(void)
{
int i,k;
double
Data;
char
c=' ',cc=' ';
do
{
//格納するデータのキー値を入力
do
{
cout << "現在 " << M << " 個のデータがあります。\n"
<< "格納データのキー値(正整数)を入力せよ。"
<< "(格納中止は999を入力。)"
<< '\n';
cin >> k;
if(k==999)break;
cout << "キー値は " << k << " ですね。(Y/N)
->";
cin >> c;
}while
(c=='n' || c=='N');
if(k==999)break;
//格納場所を探す。
i = H(k);
while(Key[i] != Nothing && Key[i]
!= k)
{
i++;
if(i>=N)i=0;
}
//格納するデータを入力
if(Key[i]==k)
{
cout << "既にそのデータは存在しています。\n";
}
if(M>=N-1)
{
cout << "格納場所に空きがありません。\n";
break;
}
if(Key[i]!=k)
{
cout << "格納場所のアドレスは " << i << " です。\n";
Key[i] = k;
cout << "格納するデータ(実数値)を入力してください。\n";
cin >>
Data;
Table[i] = Data;
cout << "データ：" << Data <<
"が格納されました。\n";
M++;
}
//続行判断
cout << "格納を続けますか。(Y/N) ->";
cin >>
cc;
}
while(cc=='y' || cc=='Y');
cout << "入力を終了します。\n\n";
}
void Kensaku(void)
{
int i,k;
char
c;
do
{
//検索するデータのキー値を入力
do
{
cout << "検索するデータのキー値を入力してください。"
<< "(中止は999を入力)\n";
cin >> k;
if
(k==999)break;
cout << "検索するデータのキー値は " << k
<< " ですね。(Y/N) ->";
cin >> c;
}
while(c=='n' || c=='N');
if
(k==999)break;
//検索実行
i=H(k);
do
{
if(Key[i]==k)
{
cout << "データは存在しました。データは "
<< Table[i]
<< "です。\n";
break;
}
else
{
if(Key[i] == Nothing)
{
cout << "データは存在しません。\n";
break;
}
else
{
i++;
}
}
if(i>=N)i=0;
}
while(1);
//続行判断
cout << "別のデータを検索しますか。(Y/N) ->";
cin >> c;
}
while (c=='y' || c=='Y');
cout << "検索を終了します。\n";
}
void Sakujo(void)
{
int i,k;
char
c;
do
{
//削除するデータのキー値を入力
do
{
cout << "削除するデータのキー値を入力してください。"
<< "(中止は999を入力)\n";
cin >> k;
if(k==999)break;
cout << "削除するデータのキー値は " << k
<< " ですね。(Y/N) ->";
cin >> c;
}
while(c=='n' || c=='N');
if
(k==999)break;
//削除するデータの存在場所を見つける
i = H(k);
do
{
if(Key[i]==k)
{
cout << "データが見つかりました。\n";
Sakujoshori(i); //削除処理実行
cout << "データを削除しました。\n";
M--;
cout << "格納データの個数は " << M
<< " 個になりました。\n";
break;
}
else
if(Key[i] == Nothing)
{
cout << "そのデータは存在しません。\n";
break;
}
else
{
i++;
}
if(i>=N)i=0;
}
while(1);
//続行判断
cout << "別のデータを削除しますか。(Y/N) ->";
cin >> c;
}
while (c=='y' || c=='Y');
cout << "削除を終了します。\n";
}
int main(void)
{
int k,p;
for(k=0;k<12;k++)
{
Key[k]
= Nothing; //キー値の初期化
Table[k]
= Nothing;//データ値の初期化
}
do{
cout << "作業を選択してください。\n"
<< "1．データ格納 \n"
<< "2．データ検索 \n"
<< "3．データ削除 \n"
<< "9. 終了 \n"
<< "(1/2/3/9) ->";
cin >> p;
if(p==9)break;
if(p>0
|| p<4)
{
switch(p)
{
case
1://データの格納
cout << "「データの格納」が選択されました。\n";
Kakunou();
break;
case
2://データの検索
cout << "「データの検索」が選択されました。\n";
Kensaku();
break;
case
3://データの削除
cout << "「データの削除」が選択されました。\n";
Sakujo();
break;
}
}
}while(1);
return(0);
}