哈希表c语言程序代码

/*实验项目名称:电话号码查询系统的实现实验目的与要求:1.基础知识:掌握数据结构中的查找、排序等算法相关知识;掌握C或VC++语言中程序设计的方法。2.参考教材相关算法，完成以下程序功能:(1)自选存储结构实现电话号码表的初始化；(2)编写一个电话号码查询系统,要求有电话号码记录的录入(插入)存储、查询、记录删除、排序、打印等模块;实验性质:综合性(4学时)说明:存储结构可采用哈希表的方式,完成用电话号码或姓名为关键字构建哈希表,并进行查询、添加、删除、打印记录等功能模块(此方式为推荐方式),其次子函数的调用顺序由最终用户决定(可用多分支结构),程序中应有用户的操作选择界面.*/#includestdio.h#includestdlib.h#defineSUCCESS1#defineNULL_KEY-2//-2为无标志记录#defineUNSUCCESS0#defineDUPLICATE-1inthashsize[]={11,19,29,37};//哈希表容量递增表,一个合适的素数序列intm=0;//哈希表表长,全局变量typedefintKeyType;//设关键字为整形typedefstruct{charname;//姓名KeyTypenum;//号码}Node;typedefstruct{Node*elem;//数据元素存储地址,动态分配数组intcount;//当前数据元素个数intsizeindex;//hashsize[H.sizeindex]为当前容量}HashTable;voidChuangJian(HashTable&H){//构建一个空哈希表inti;H.count=0;//当前元素个数H.sizeindex=0;//初试存储容量为hashsize[0]m=hashsize[0];H.elem=(Node*)malloc(m*sizeof(Node));if(!H.elem)exit(-2);//存储分配失败for(i=0;im;i++)H.elem[i].num=NULL_KEY;//未填记录的标志}voidDaYin(intp,Nodee){//打印下标为p的记录printf(哈希下标=%d姓名:%c号码:%d\n,p,e.name,e.num);}intHaXi(KeyTypeK){//哈希函数(m为表长,全局变量)returnK%m;}voidChongTu(int&p,intd){//线性探测再散列p=(p+d)%m;}intEQ(inta,intv){//判断a和v是否相等if(a==v)return1;//相等返回1elsereturn0;//否则返回0}intFind(HashTableH,KeyTypeK,int&p){//在开放定址哈希表H中查找关键字为K的元素,若查找成//功,以p指示待查数据元素在表中下标,并返回SUCCESS;否则,返回UNSUCCESSintc=0;p=HaXi(K);//求得哈希地址while(H.elem[p].num!=NULL_KEY&&!EQ(K,H.elem[p].num)){//该位置中填有记录,并且与关键字不相等c++;if(cm)ChongTu(p,c);//求得下一探查地址pelsereturnUNSUCCESS;//查找不成功}if(EQ(K,H.elem[p].num))returnSUCCESS;//查找成功,p返回待查数据元素下标elsereturnUNSUCCESS;//查找不成功}intChaXun(HashTableH,KeyTypeK,int&p,int&c){//在开放定址哈希表中查找关键字为K的元素,若查找成功,以p指示//待查数据元素在表中位置,并返回SUCCESS;否则,以p指示插入位置,并返回UNSUCCESS;c用以计冲突次数,其初值为0p=HaXi(K);//求得哈希地址while(H.elem[p].num!=NULL_KEY&&!EQ(K,H.elem[p].num)){//该位置中填有记录,并且与关键字不相等if(cm)ChongTu(p,c);//求得下一探查地址pelsebreak;}if(EQ(K,H.elem[p].num))returnSUCCESS;//查找成功,p返回待查数据元素下标elsereturnUNSUCCESS;//若查找不成功,p返回插入位置}voidChongJian(HashTable&H){//重建哈希表intChaRu(HashTable&H,Nodee);inti,count=H.count;Node*p,*elem=(Node*)malloc(count*sizeof(Node));p=elem;printf(重建哈希表!\n);for(i=0;im;i++)//保存原有数据到elem中if((H.elem+i)-num!=NULL_KEY)//该单元有数据*p++=*(H.elem+i);H.count=0;H.sizeindex++;//增大存储容量m=hashsize[H.sizeindex];p=(Node*)realloc(H.elem,m*sizeof(Node));if(!p)exit(-2);//存储分配失败H.elem=p;for(i=0;im;i++)H.elem[i].num=NULL_KEY;//未填记录的标志化for(p=elem;pelem+count;p++)//将原有的数据按照新的表长插入到重建的哈希表中ChaRu(H,*p);}intChaRu(HashTable&H,Nodee){//查找不成功时插入数据e到开放定址哈希表H中,并返回1;若冲突次数过大,则重建哈希表intc=0,p;if(H.count==m-1){H.sizeindex++;//增大存储容量m=hashsize[H.sizeindex];H.elem=(Node*)realloc(H.elem,m*sizeof(Node));//追加空间if(!H.elem)exit(-2);//追加空间失败}if(ChaXun(H,e.num,p,c)){//表中已有与e有相同关键字的元素printf(表中已有相同关键字的元素!\n);returnDUPLICATE;}else{if(chashsize[H.sizeindex]/2){//冲突次数c未达到上限H.elem[p]=e;//插入e++H.count;return1;}else{ChongJian(H);//重建哈希表returnUNSUCCESS;}}}intBaoCun(HashTableH){//将哈希表中所有数据保存到phone.txtFILE*fp;inti=0,p;if((fp=fopen(phone.txt,w+))==NULL)return0;for(p=0;pm;p++){//表中当前记录的个数if(H.elem[p].num!=NULL_KEY)i++;}fprintf(fp,%d\n,i);for(p=0;pm;p++){//将哈希表中所有数据写到phone.txtif(H.elem[p].num!=NULL_KEY)fprintf(fp,%d%c%d\n,p,H.elem[p].name,H.elem[p].num);}fclose(fp);printf(保存成功!\n);return1;}intDuQu(HashTable&H){//将phone.txt所有数据读到哈希表中FILE*fp;inti,p,n;chara[15];if((fp=fopen(phone.txt,r+))==NULL)return0;fscanf(fp,%s,a);n=atoi(a);//phone.txt中当前记录的个数H.count=n;for(i=0;in;i++){//将phone.txt所有数据读到哈希表中fscanf(fp,%s,a);p=atoi(a);fscanf(fp,%s,a);H.elem[p].name=a[0];fscanf(fp,%s,a);H.elem[p].num=atoi(a);}fclose(fp);return1;}voidQingKong(HashTable&H){//清空哈希表inti;H.count=0;//当前元素个数置为0H.sizeindex=0;//初试存储容量为hashsize[0]m=hashsize[0];H.elem=(Node*)malloc(m*sizeof(Node));if(!H.elem)exit(-2);//存储分配失败for(i=0;im;i++)H.elem[i].num=NULL_KEY;//未填记录的标志printf(哈希表已清空!\n);}voidPaiXu(HashTable&H1,HashTableH){//排序inti,j;Nodee;H1.count=H.count;H1.sizeindex=H.sizeindex;m=hashsize[0];H1.elem=(Node*)malloc(m*sizeof(Node));if(!H1.elem)exit(-2);for(i=0;im;i++)//将哈希表H中所有数据赋给哈希表H1H1.elem[i]=H.elem[i];for(i=0;im-1;i++)//在哈希表H1中按姓名排序for(j=i+1;jm;j++)if(H1.elem[i].num!=-2&&H1.elem[j].num!=-2)if(H1.elem[i].nameH1.elem[j].name){e=H1.elem[i];H1.elem[i]=H1.elem[j];H1.elem[j]=e;}}intmain(){//主函数inti,j,p;charc,v;Nodee;KeyTypeK;HashTableH,H1;ChuangJian(H);DuQu(H);while(1){system(cls);system(colorF0);printf(\t|===========================================================|\t\n);printf(\t||\t\n);printf(\t|电话号码系统|\t\n);printf(\t||\t\n);printf(\t|===========================================================|\t\n);printf(\n\t【1】--打印!\t\t【2】--查询!\t\t【3】--插入!\n);printf(\n\t【4】--修改!\t\t【5】--删除!\t\t【6】--排序!\n);printf(\n\t【7】--保存!\t\t【8】--清空!\t\t【0】--退出!\n);printf(\n\n\t\t\t请输入你的选择:);scanf(%d,&i);switch(i){case1://打印if(H.count0){printf(按哈希表下标遍历结果如下:\n);for(p=0;pm;p++)if(H.elem[p].num!=NULL_KEY)DaYin(p,H.elem[p]);}elseprintf(哈希表为空,不用打印!\n);system(pause);break;case2://查询do{printf(请输入你要查询的关键字:);scanf(%d,&K);j=Find(H,K,p);if(j==SUCCESS){printf(你输入的关键字查询结果如下:\n);DaYin(p,H.elem[p]);}elseprintf(该哈希表中没有你要查找的关键字!\n);printf(是否继续查找?是/否,y/n:);getchar();}while((c=getchar())=='y'||(c=getchar())=='Y');system(pause);break;case3://插入do{p