哈希查找算法的源代码 c语言

哈希查找算法的源代码 c语言 【问题描述】

针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。 [基本要求]

假设人名为中国姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构照，用链表法处理冲突。 [测试数据]

读取熟悉的30个人的姓名。 #include #include #include 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(\if(!infile) {cout<<\文件打开失败!\\n\

while(!infile.eof() && infile.get()!=EOF) //文件不为空并且文件指针没有指到结束符

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

}

infile.close(); }

void Add(precord a) //添加记录 { int i,num;

cout<<\当前文件内已有\条记录\\n\cout<<\请输入添加的个数:\cin>>num;

ofstream ofile(\

if(! ofile) {cout<<\文件打开失败!\for(i=0;i

{ cout<<\请输入第\个人的姓名\cin>>a[Number].name;

cout<<\请输入第\个人的电话\cin>>a[Number].tel;

cout<<\请输入第\个人的地址\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

cout<<\第\个人的信息为:\\n\cout<<\姓名:\cout<<\电话:\cout<<\地址:\} }

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;ielem[i]=-1; }

int menu;

void Creathash_Name(pHashTable h,precord a) //以用户名为关键字创建哈希表

{ cout<<\--------------------\\n\

cout<<\以线性探测建表\\n\cout<<\以平方探测建表\\n\

cout<<\------------------\\n\int i,address; cin>>menu; Init_Hash(h);

for(i=0;i

address=Hash(a[i].name); while(h->elem[address]!=-1)

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