《哈希表c语言程序代码》由会员分享，可在线阅读，更多相关《哈希表c语言程序代码（10页珍藏版）》请在金锄头文库上搜索。
1、/* 实验项目名称:电话号码查询系统的实现 实验目的与要求: 1.基础知识:掌握数据结构中的查找、排序等算法相关知识; 掌握C或VC+语言中程序设计的方法。 2.参考教材相关算法，完成以下程序功能: (1)自选存储结构实现电话号码表的初始化； (2)编写一个电话号码查询系统,要求有电话号码记录的录入(插入)存储、查询、记录删除、排序、打印等模块; 实验性质: 综合性(4学时) 说明: 存储结构可采用哈希表的方式,完成用电话号码或姓名为关键字构建哈希表,并进行查询、添加、删除、打印记录等功能模 块(此方式为推荐方式),其次子函数的调用顺序由最终用户决定(可用多分支结构),程序中应有用户的操作选择
2、界面. */# include stdio.h# include stdlib.h# define SUCCESS 1# define NULL_KEY -2 /-2为无标志记录# define UNSUCCESS 0# define DUPLICATE -1int hashsize=11,19,29,37; /哈希表容量递增表,一个合适的素数序列int m=0; /哈希表表长,全局变量typedef int KeyType; /设关键字为整形typedef struct char name; /姓名KeyType num; /号码Node;typedef struct Node *elem;
3、 /数据元素存储地址,动态分配数组int count; /当前数据元素个数int sizeindex; /hashsizeH.sizeindex为当前容量HashTable;void ChuangJian(HashTable &H) /构建一个空哈希表int i;H.count=0; /当前元素个数H.sizeindex=0; /初试存储容量为hashsize0m=hashsize0;H.elem=(Node *)malloc(m*sizeof(Node);if (!H.elem)exit (-2); /存储分配失败for (i=0;im;i+)H.elemi.num=NULL_KEY; /未
4、填记录的标志void DaYin(int p,Node e) /打印下标为p的记录printf (哈希下标=%d 姓名:%c 号码:%dn,p,e.name,e.num);int HaXi(KeyType K) /哈希函数(m为表长,全局变量)return K%m;void ChongTu(int &p,int d) /线性探测再散列p=(p+d)%m;int EQ(int a,int v) /判断a和v是否相等 if(a=v)return 1; /相等返回1else return 0; /否则返回0int Find(HashTable H,KeyType K,int &p) /在开放定址哈希
5、表H中查找关键字为K的元素,若查找成/功,以p指示待查数据元素在表中下标,并返回SUCCESS;否则,返回UNSUCCESSint c=0;p=HaXi(K); /求得哈希地址while(H.elemp.num!=NULL_KEY&!EQ(K,H.elemp.num) /该位置中填有记录,并且与关键字不相等c+;if(cm)ChongTu(p,c); /求得下一探查地址pelsereturn UNSUCCESS; /查找不成功if (EQ(K,H.elemp.num)return SUCCESS; /查找成功,p返回待查数据元素下标elsereturn UNSUCCESS; /查找不成功int
6、 ChaXun(HashTable H,KeyType K,int &p,int &c) /在开放定址哈希表中查找关键字为K的元素,若查找成功,以p指示/待查数据元素在表中位置,并返回SUCCESS;否则,以p指示插入位置,并返回UNSUCCESS;c用以计冲突次数,其初值为0p=HaXi(K); /求得哈希地址while(H.elemp.num!=NULL_KEY&!EQ(K,H.elemp.num) /该位置中填有记录,并且与关键字不相等if(cm)ChongTu(p,c); /求得下一探查地址pelsebreak;if (EQ(K,H.elemp.num)return SUCCESS;
7、/查找成功,p返回待查数据元素下标elsereturn UNSUCCESS; /若查找不成功,p返回插入位置void ChongJian(HashTable &H) /重建哈希表 int ChaRu(HashTable &H,Node e);int i,count=H.count;Node *p,*elem=(Node *)malloc(count*sizeof(Node);p=elem;printf (重建哈希表!n);for(i=0;inum!=NULL_KEY)/该单元有数据*p+=*(H.elem+i);H.count=0;H.sizeindex+; /增大存储容量m=hashsize
8、H.sizeindex;p=(Node *)realloc(H.elem,m*sizeof(Node);if(!p)exit(-2); /存储分配失败H.elem=p;for(i=0;im;i+)H.elemi.num=NULL_KEY; /未填记录的标志化for(p=elem;pelem+count;p+)/将原有的数据按照新的表长插入到重建的哈希表中ChaRu(H,*p);int ChaRu(HashTable &H,Node e) /查找不成功时插入数据e到开放定址哈希表H中,并返回1;若冲突次数过大,则重建哈希表int c=0,p;if(H.count=m-1) H.sizeindex
9、+; /增大存储容量 m=hashsizeH.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);return DUPLICATE;else if (chashsizeH.sizeindex/2) /冲突次数c未达到上限H.elemp=e; /插入e+H.count;return 1;else ChongJian(H); /重建哈希表re
10、turn UNSUCCESS;int BaoCun(HashTable H) /将哈希表中所有数据保存到phone.txtFILE *fp;int i=0,p;if(fp=fopen(phone.txt,w+)=NULL) return 0; for (p=0;pm;p+) /表中当前记录的个数if(H.elemp.num!=NULL_KEY)i+; fprintf(fp,%dn,i); for (p=0;pm;p+) /将哈希表中所有数据写到phone.txtif(H.elemp.num!=NULL_KEY)fprintf(fp,%d %c %dn,p,H.elemp.name,H.elem
11、p.num);fclose(fp);printf (保存成功!n);return 1;int DuQu(HashTable &H) /将phone.txt所有数据读到哈希表中FILE *fp;int i,p,n;char a15;if(fp=fopen(phone.txt,r+)=NULL) return 0;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.elemp.name=a0;fscanf(fp,%s,a);H.elemp.num=atoi(a);fclose(fp); return 1;void QingKong(HashTable &H) /清空哈希表int i;H.count=0; /当前元素个数置为0H.sizeindex=0; /初试存储容量为hashsize0m=hashsize0;H.elem=(Node *)malloc(m*sizeof(Node);if (!H.elem)exit (-2); /存储分配失败for (i=0;im;i+)H.elemi.num=NULL_KEY; /未填记录的标志printf (哈希表已清空!n
