ハッシュ・テーブルの例
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#define Size 11
typedef struct{
char name[30];
char address[20];
//float num;
char num[30];
int c;//
}record;
typedef struct{
record data[Size];
int count;
int size;
}Hashtable;
void init(Hashtable &h)
{
for(int i=0;i<Size;i++)
{h.data[i].num[0]=0;
h.data[i].c=0;}//!
h.size=Size;
h.count=0;
}
int exchange(char str[])
{
int i,n,sum=0;
n=strlen(str);
for(i=0;i<n;i++)
sum=sum+str[i]-'0';
return sum;
}
int HashSearch1(Hashtable &h,char *str,int &p) //
{
int i,j,k=exchange(str);
j=k%Size;
if(strcmp(str,h.data[j].num)==0)
{
return j;
h.data[j].c++;//!
}// ，
if(h.data[j].num[0]==0)
{
p=j;
return 0;
}
else
{
h.data[j].c++;//!
i=(j+1)%Size;// 1
while(h.data[i].num[0]!=0&&i!=j)
{
if(strcmp(str,h.data[i].num)==0)
{
h.data[j].c++;//!
return i;
}// ，
i=(i+1)%Size; //
}
if (i==j)
printf("
");
else
{
p=i;
h.data[j].c++;//!
return 0;//
}
}
}
int HashSearch2(Hashtable &h,char *str,int &p)
{
int i,j,t=1,d=1;
int k=exchange(str);
j=k%Size;
if(strcmp(str,h.data[j].num)==0)
{
h.data[j].c++;//!
return j;
} // ，
if(h.data[j].num[0]==0)
{
p=j;
return 0;
}
else
{
i=(j+d)%Size;// 1
while(h.data[i].num[0]!=0&&i!=j)
{
if(strcmp(str,h.data[i].num)==0)
{
h.data[j].c++;//!
return i;
}
if(t>0)
t=-1*d*d;
else
{
d=d+1;
t=-1*d*d ;
}
i=(j+t+Size)%Size; //
while(i<0)
{
h.data[j].c++;//!
i=(i+Size)%Size;
} }
if (i==j)
printf("
");
else
{
p=i;
h.data[j].c++;//!
return 0;//
}
}
}
void disp(Hashtable h)
{
printf(" :
");
for(int i=0;i<Size;i++)
{
if(h.data[i].num[0])
printf("-.%7s s %s
",i,h.data[i].name,h.data[i].address,h.data[i].num);
}
}
//
int compasl(Hashtable h)
{
int sum=0;
for(int i=0;i<Size;i++)
sum+=h.data[i].c;
return sum;
}
int menu()
{
int num;
while(1)
{
system("cls");
printf("
--------- ( )---------
");
printf("
**********************************************
");
printf("
0. 1.
");
printf("
2. 1 3. 2
");
printf("
4. 1 5. 2
");
printf("
6. 1 ASL 7. 2 ASL
");
printf("
**********************************************
");
printf("
----------------------------------------------
");
printf("
(0--7):
");
scanf("%d",&num);
if(num<0||num>7)
printf(" ， !
");
break;
}
return num;
}
void main()
{
Hashtable h1,h2;
int i,j,n,a,m,flag=1;
char num[30];
char name[30],address[50];
init(h1);init(h2);
while(1)
{
j=menu();
switch(j){
case 0:printf("(@ @) ， ! (^ ^)
");
exit(0);
getch();
break;
case 1:
if(flag){
FILE *fp;
if((fp=fopen("1234.txt","r+"))==NULL)
{
puts(" ！");
exit(0);
}
fscanf(fp,"%d",&n);
for(i=0;i<n;i++)
{
fscanf(fp,"%s%s%s",name,address,num);
HashSearch1(h1,num,a);
strcpy(h1.data[a].num,num);
strcpy(h1.data[a].address,address);
strcpy(h1.data[a].name,name);
h1.count++;
}
puts("\t 1!");
disp(h1);
fclose(fp);
if((fp=fopen("1234.txt","r+"))==NULL)
{
puts(" ");
exit(0);
}
fscanf(fp,"%d",&n);
for(i=0;i<n;i++)
{
fscanf(fp,"%s%s%s",name,address,num);
HashSearch2(h2,num,a);
strcpy(h2.data[a].num,num);
strcpy(h2.data[a].address,address);
strcpy(h2.data[a].name,name);
h2.count++;
}
puts("\t 2!");
disp(h2);
fclose(fp);
printf(" !
");
getch();}
flag=0;
break;
case 2:
printf(" 1:
");
printf(" ：
");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf(" %d 、 ( )
",i+1);
scanf("%s%s%s",name,address,num);
if(HashSearch1(h1,num,a))
{
printf(" ");
i--;
}
else
{
strcpy(h1.data[a].num,num);
strcpy(h1.data[a].address,address);
strcpy(h1.data[a].name,name);
h1.count++;
}
}
disp(h1);
printf(" !
");
getch();
break;
case 3:printf(" 2:
");
printf("
");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf(" %d 、 ( )
",i+1);
scanf("%s%s%s",name,address,num);
if(HashSearch2(h2,num,a))
{
printf(" ");
i--;
}
else
{
strcpy(h2.data[a].num,num);
strcpy(h2.data[a].address,address);
strcpy(h2.data[a].name,name);
h2.count++;
}
}
disp(h2);
printf(" !
");
getch();
break;
case 4:disp(h1);
printf(" 1 :
");
scanf("%s",num);
printf("
");
if(m=HashSearch1(h1,num,a))
{
printf(" :
");
printf(" 、 :
%s,%s,%s
",h1.data[m].name,h1.data[m].address,h1.data[m].num);
}
else
printf(" ， !
");
printf(" !
");
getch();
break;
case 5:disp(h2);
printf(" 2 :
");
scanf("%s",num);
printf("
");
if(m=HashSearch2(h2,num,a))
{
printf(" :
");
printf(" 、 :
%s,%s,%s
",h2.data[m].name,h2.data[m].address,h2.data[m].num);
}
else
printf(" ， !
");
printf(" !
");
getch();
break;
case 6:printf(" 1 ASL :
");
printf("%d %d
",compasl(h1),h1.count);
printf(" !
");
getch();
break;
case 7:printf(" 2 ASL :
");
printf("%d %d
",compasl(h2),h2.count);
printf(" !
");
getch();
break;
}
}
}以下は、カリキュラム設計のレポートです.
一、カリキュラム設計の目的と要求
1. 目的:データ構造とアルゴリズムを応用して相応のプログラムを設計し、学生問題解決モジュールのフレームワーク設計と詳細設計、関連プログラムの実現とデバッグ能力を育成し、革新能力と実践能力の訓練を完成する.
2. 要求:高級プログラムで言語Cコードを設計し、VC++開発プラットフォームでデバッグする.
二、設計本文
(一)カリキュラム設計テーマ
ハッシュテーブルを設計して電話番号照会システムを実現する
(二)需要分析
各記録には以下のデータ項目がある:電話番号、ユーザー名、住所;
(1)データ導入(ファイルから各レコードを読み出し、それぞれ電話番号をキーワードにハッシュテーブルを作成する);
(2)キーボードからレコードを読み取り、ハッシュテーブルに挿入する.
(3)所定の電話番号の記録を検索して表示する.
(4)電話番号記録をファイルに保存する.
(5)衝突を種々の異なるタイプで処理する方法を試み,平均ルックアップ長の変化を考察する.
分析:テーマは電話番号をキーワードとして表を作ることが要求されるため、電話番号の長さが異なることを考慮して、直接電話番号を表す文字列をキーワードにすれば、一定の面倒をもたらす可能性がある.したがって、電話番号を表す文字列を1つの関数で対応する数字に変換し、これらの数字の和をキーワードとして上記トラブルを解消することができる.
(三)概要設計
上記のプログラムの機能を実現するには、以下の抽象データ型を定義する必要があります.
ADT hashtable {
データ・オブジェクト:ハッシュ・テーブルに格納された電話レコード.
データ関係:表中の隣接要素の間に前と後の関係がある.
基本操作:
init(Hashtable &h)
操作結果:ハッシュテーブルを初期化しました.
int exchange(char str[])
操作結果:ボールはキーワードを取ります;
int HashSearch1(Hashtable &h,char *str,int &p)
操作結果:テーブル内でデータを線形に検出し、データの挿入位置を返す.
int HashSearch2(Hashtable &h,char *str,int &p)
操作結果:テーブル内でデータを二次的に検出し、データの挿入位置を返す.
void disp(Hashtable h)
操作結果:ハッシュテーブルに格納された電話記録を表示する.
}ADT hashtable
電話番号、ユーザー名、アドレスを含む各個人の情報を1つのレコードとして記録し、衝突の回数を記録するための整数変数もあり、ASLの計算を容易にし、ハッシュテーブルは記録配列、表現メモリ、容量から構成され、具体的なデータ型は以下の通りである.
typedef struct {
char name[30];
char address[20];
char num[30];
}record;
typedef struct{
record data[Size];
int count;
int size;
}Hashtable;
キーワード処理---電話番号を表す文字列を1つの関数で対応する数字に変換し、その数字の和をキーワードとします.具体的な関数は次のとおりです.
int exchange(char str[])
{
int i,n,sum=0;
n=strlen(str);
for(i=0;i
return sum;
}
最後に,衝突をそれぞれ線形と二次プローブ法で処理する2つの方法でテーブルを構築した.
このプログラムのすべての関数リスト:
void init(Hashtable &h);//ハッシュテーブルの初期化
int exchange(char str[]);//キーワードを求める
int HashSearch1(Hashtable &h,char *str,int &p);//せんけいプローブしょりコンフリクト
int HashSearch2(Hashtable &h,char *str,int &p);//二次検出処理の競合
void disp(Hashtable h);//ハッシュ表の表示
int menu();//メインメニュー
void main();//しゅかんすう
各関数間の呼び出し関係は次のとおりです.
メイン関数main()
メニュー関数menu()
線形プローブ衝突解決hashserch 1()
ユーザーの検索
考察ASL 1
二次プローブ衝突解決hashsearch 2()
ユーザーの検索
考察ASL
電話帳dispを表示()
(四)詳細設計
1)上記プログラムの機能を実現するためには、以下のデータ型を定義する必要がある.
typedef struct{
char name[30];
char address[20];
//float num;
char num[30];
int c;//統計比較回数
}record;//記録
typedef struct{
record data[Size];
int count;
int size;
}Hashtable;//ハッシュ表
2)主な関数:
int exchange(char str[])/キーワード処理関数
{
int i,n,sum=0;
n=strlen(str);
for(i=0;i
return sum;
}
int HashSearch 1(Hashtable&h,char*str,int&p)//リニアプローブ
{
int i,j,k=exchange(str);
j=k%Size;
if(strcmp(str,h.data[j].num)==0)
{
return j;
h.data[j].c++;//!
}//衝突は発生せず、比較して検索に成功
if(h.data[j].num[0]==0)
{
p=j;
return 0;
}
else
{
h.data[j].c++;//!
i=(j+1)%Size;//第1回衝突解決
while(h.data[i].num[0]!=0&&i!=j)
{
if(strcmp(str,h.data[j].num)==0)
{
h.data[j].c++;//!
return i;
}//競合が発生し、何回か比較して検索に成功
i=(i+1)%Size;//位置を後ろに探る
}
if (i==j)
printf(「オーバーフロー」);
else
{
p=i;
h.data[j].c++;//!
return 0;//検索に失敗しました
}
}
}
int HashSearch 2(Hashtable&h,char*str,int&p)//二次プローブ
{
int i,j,t=1,d=1;
int k=exchange(str);
j=k%Size;
if(strcmp(str,h.data[j].num)==0)
{
h.data[j].c++;//!
return j;
}//競合が発生していないため、一度の検索を比較できました
if(h.data[j].num[0]==0)
{
p=j;
return 0;
}
else
{
i=(j+d)%Size;//第1回衝突解決
while(h.data[i].num[0]!=0&&i!=j)
{
if(strcmp(str,h.data[j].num)==0)
{
h.data[j].c++;//!
return i;
}
if(t>0)
t=-1*d*d;
else
{
d=d+1;
t=-1*d*d ;
}
i=(j+t+Size)%Size;//新しい位置を探る
while(i<0)
{
h.data[j].c++;//!
i=(i+Size)%Size;
}
if (i==j)
printf(「オーバーフロー」);
else
{
p=i;
h.data[j].c++;//!
return 0;//検索が失敗した場合に挿入
}
}
}
}
(五)デバッグ分析
本実験の実行環境はVC++である.要求に応じて、事前にいくつかの記録を導入しなければならない.以下は本実験のテストデータである.
4
侯進斌北京6627584
王璐太原6650370
唐磊天津6626074
高启波太原6651805
メニューの指示に従って操作すればいいです.
(六)使用説明
プログラム名はhashtable.exe、実行環境はVC++です.メニューに詳細な操作プロンプトがあるので、上記のプロンプトに従って一歩一歩操作すればいいです.
(七)テストデータ
プログラムが実行されると、次のメニューが表示されます.
1を選択すると、次のウィンドウが表示され、既存のレコードが表示されます.
操作2を選択すると、電話帳1に記録を追加できます.以下のようにします.
操作3は、電話帳2に記録を追加し、以下のようにする.
次に、クエリー操作を行うこともできます.4を選択すると、電話帳1で探している人の情報をクエリーできます.
同様に、5を選択すると、電話帳2で対応するクエリーを行うこともできます.
電話帳1で検索する速度(専門用語:ASL)を比較したい場合は、操作6を選択します.
電話帳2の機能も同様に表示できます.
操作を終了するには、0を選択してシステムを終了します.
以上が本システムの主な機能です.
三、カリキュラム設計の総括或いは結論
1.完成した仕事
この実験のすべての要求:ハッシュ表の作成、2つの異なる方法で衝突を処理して、各種の衝突を処理する方法のASLを考察します;
2.未完了の作業
なし
3.必要な改善
衝突をより多く処理する方法を試みるべきだ.
いくつかのコードの効率は低く、改善が必要です.
四、参考文献
『データ構造』(C言語版)清華大学出版社厳蔚敏呉偉民編著