當前位置:成語大全網 - 新華字典 - 用C設計哈希表——數據結構課程設計

用C設計哈希表——數據結構課程設計

#include <fstream>

#include <iostream>

#include <cmath>

using namespace std;

#define Maxsize 57

struct record

{ char name[20];

char tel[20];

char add[20];

};

typedef record * precord;struct HashTable

{ int elem[Maxsize]; //存放數組a[]的下標

int count;

};

typedef HashTable * pHashTable;

int Number; //統計當前數組a[]中的記錄總數

void Getdata(precord a) //從文件telphone.txt中讀取數據存放到數組a[]

{ Number=0;

ifstream infile("telphone.txt",ios::in|ios::binary);

if(!infile) {cout<<"文件打開失敗!\n"; exit(1);}

while(!infile.eof() && infile.get()!=EOF) //文件不為空並且文件指針沒有指到結束符

{infile.seekg(Number*sizeof(a[Number]),ios::beg); //定位文件指針<br> infile.read((char *)&a[Number],sizeof(a[Number]));<br> Number++;<br> }

infile.close();

}

void Add(precord a) //添加記錄

{ int i,num;

cout<<"當前文件內已有"<<Number<<"條記錄\n";

cout<<"請輸入添加的個數:";

cin>>num;

ofstream ofile("telphone.txt",ios::app);

if(! ofile) {cout<<"文件打開失敗!"; exit(1);}

for(i=0;i<num;i++)

{ cout<<"請輸入第"<<Number+1<<"個人的姓名"<<endl;

cin>>a[Number].name;

cout<<"請輸入第"<<Number+1<<"個人的電話"<<endl;

cin>>a[Number].tel;

cout<<"請輸入第"<<Number+1<<"個人的地址"<<endl;

cin>>a[Number].add;

ofile.seekp(ios::end);

ofile.write((char *)&a[Number],sizeof(a[Number]));

Number++;

}

ofile.close();

}

void Print(precord a) //顯示所有記錄

{ int i;

for(i=0;i<Number;i++)

{

cout<<"第"<<i+1<<"個人的信息為:\n";

cout<<" 姓名:"<<a[i].name<<endl;

cout<<" 電話:"<<a[i].tel<<endl;

cout<<" 地址:"<<a[i].add<<endl;

}

}

int Hash(char str[]) //除留取余

{ long val=0;char p[20],*p1;

strcpy(p,str);

p1=p;

while(*p1!='\0')

val=val+*p1++; //將字符串中的所有字符對應的ASCII值相加

return(val%Maxsize);

} int derter; //線性增量

int Line_Sollution(int address) //采用線性探測解決沖突

{

derter++;

if(derter==Maxsize) return(-1);

else return((address+derter)%Maxsize);

} int n;

int Square_Sollution(int address) //采用平方探測法解決沖突

{ int j;

derter++;

if(derter==Maxsize) return -1;

n=n*(-1);

j=(int(pow(derter,2))*n+address)%Maxsize;

return(j);

} void Init_Hash(pHashTable h) //初始化哈希表

{ int i;

for(i=0;i<Maxsize;i++)

h->elem[i]=-1;

}

int menu;

void Creathash_Name(pHashTable h,precord a)

//以用戶名為關鍵字創建哈希表

{ cout<<"--------------------------------------------------------------------------------\n";

cout<<" 1----以線性探測建表\n";

cout<<" 2----以平方探測建表\n";

cout<<"--------------------------------------------------------------------------------\n";

int i,address;

cin>>menu;

Init_Hash(h);

for(i=0;i<Number;i++)

{ derter=0;n=-1;

address=Hash(a[i].name);

while(h->elem[address]!=-1)

{if(menu==1) address=Line_Sollution(address);<br> else address=Square_Sollution(address);<br> if(address==-1) break;<br> } if(address!=-1) { h->elem[address]=i; h->count++;}

}

cout<<"姓名哈希表已成功建立!\n";

}

void Search_Name(pHashTable h,precord a) //查找並顯示指定姓名的記錄

{ cout<<"請輸入要查找的姓名:";

char nam[20];int address,i=1;

cin>>nam;

address=Hash(nam);

derter=0;n=-1;

while(h->elem[address]!=-1 && strcmp(nam,a[h->elem[address]].name)!=0)

{ if(menu==1) address=Line_Sollution(address);

else address=Square_Sollution(address);

i++;

if(address==-1) break;

}

if(h->elem[address]!=-1 && strcmp(nam,a[h->elem[address]].name)==0)

{ cout<<"妳要查找的信息為:\n";

cout<<" 姓名:"<<a[h->elem[address]].name<<endl;

cout<<" 電話:"<<a[h->elem[address]].tel<<endl;

cout<<" 地址:"<<a[h->elem[address]].add<<endl;

cout<<"比較次數為"<<i<<endl;

}

else cout<<"無此姓名,查找失敗!";

}

void Creathash_tel(pHashTable h,precord a)

//以電話號為關鍵字創建哈希表

{ cout<<"--------------------------------------------------------------------------------\n";

cout<<" 1----以線性探測建表\n";

cout<<" 2----以平方探測建表\n";

cout<<"--------------------------------------------------------------------------------\n";

int i,address;

cin>>menu;

Init_Hash(h);

for(i=0;i<Number;i++)

{ derter=0;n=-1;

address=Hash(a[i].tel);

while(h->elem[address]!=-1)

{if(menu==1) address=Line_Sollution(address);<br> else address=Square_Sollution(address);<br> if(address==-1) break;<br> } if(address!=-1) { h->elem[address]=i; h->count++;}

}

cout<<"電話號哈希表已成功建立!\n";

} void Search_tel(pHashTable h,precord a)

//查找並顯示指定電話號的記錄

{ cout<<"請輸入要查找的電話:";

char telphone[20];int address,i=1; //i統計比較次數

cin>>telphone;

address=Hash(telphone);

derter=0; n=-1; //初始化線性增量

while(h->elem[address]!=-1 && strcmp(telphone,a[h->elem[address]].tel)!=0)

{ if(menu==1) address=Line_Sollution(address);

else address=Square_Sollution(address);

i++;

if(address==-1) break;

}

if(h->elem[address]!=-1 && strcmp(telphone,a[h->elem[address]].tel)==0)

{ cout<<"妳要查找的信息為:\n";

cout<<" 姓名:"<<a[h->elem[address]].name<<endl;

cout<<" 電話:"<<a[h->elem[address]].tel<<endl;

cout<<" 地址:"<<a[h->elem[address]].add<<endl;

cout<<"比較次數為"<<i<<endl;

}

else cout<<"無此電話,查找失敗!";

} void Menu() //功能菜單函數

{for(int i=1;i<=5;i++)<br> cout<<endl;<br> cout<<" 電話號碼查詢系統\n";<br> cout<<'\n';<br> cout<<" ★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆\n";<br> cout<<" ☆ 0-------退出 ★\n";<br> cout<<" ★ 1-------添加 ☆\n";<br> cout<<" ☆ 2-------顯示所有 ★\n"; <br> cout<<" ★ 3-------以性命建立哈希表 ☆\n";<br> cout<<" ☆ 4-------以電話建立哈希表 ★\n";<br> cout<<" ★ 5-------按用戶名查找 ☆\n";<br> cout<<" ☆ 6-------按電話號查找 ★\n";<br> cout<<" ☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★\n";<br> cout<<" 使用說明:\n";<br> cout<<" 1.添加新紀錄後,如要進行查找請先進行3或4操作\n";<br> cout<<" 2.按用戶名查找之前,請先進行3操作建立用戶名哈希表\n";<br> cout<<" 3.按用戶名查找之前,請先進行4操作建立電話號哈希表\n";<br>} void exit()

{

int i;

for(i=1;i<=4;i++)

cout<<endl;

cout<<" ◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◇◆◇\n";

cout<<" ◆ ◆\n";

cout<<" ◇ 電 話 號 碼 查 詢 系 統 ◇\n";

cout<<" ◆ ◆\n";

cout<<" ◇ 謝 謝 您 的 使 用 ! ◇\n";

cout<<" ◆ ◆\n";

cout<<" ◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇\n";} int main()

{ record a[Maxsize];

pHashTable H=new HashTable;

Getdata(a); //將文件中的數據讀入到數組a中

start:

Menu();

int menu1;

cin>>menu1;

switch(menu1)

{ case 0:system("cls");exit();break;

case 1:Add(a);system("pause");system("cls");goto start;break;

case 2:Print(a);system("pause");system("cls");goto start;break;

case 3:Creathash_Name(H,a);system("pause");system("cls");goto start;break;

case 4:Creathash_tel(H,a);system("pause");system("cls");goto start;break;

case 5:Search_Name(H,a);system("pause");system("cls");goto start;break;

case 6:Search_tel(H,a);system("pause");system("cls");goto start;break;

default:cout<<"請輸入正確的操作選項!\n";system("cls");goto start;break;

}

return 0;

}