哈希表的建立与查找 C语言 数据结构练习

#include"c1.h" #include"c2.h" int m=41;//哈希表表长 int chose() { int i; printf("*********************************************************\n"); printf("* 试验6-2 哈希表的建立与查找 *\n"); printf("*********************************************************\n"); printf(" 1、显示哈希表 \n"); printf(" 2、查找人名 \n"); printf(" 3、退出本程序 \n"); printf("*********************************************************\n"); printf("请选择："); fflush(stdin); scanf("%d",&i); return i; } void InitHashTable(HashTable &H) {//初始化哈希表 int i; H.count=0;//人名计数器 H.elem=(ElemType*)malloc(m*sizeof(ElemType));//分配内存 if(!H.elem) exit(OVERFLOW); for(i=0;i<m;i++){//初始化关键值，H（key），查找长度，人名 H.elem[i].key=0; H.elem[i].Hkey=0; H.elem[i].length=0; for(int j=0;j<SIZE;j++){ H.elem[i].name[j]=NULL; } } } int SearchHash(HashTable H,int k,int &p,int &c) {//查找人名 p=k%m;//除留余数法 while(H.elem[p].key!=0&&H.elem[p].key!=k){ ++c;//每处理冲突一次加1 collision(p,1); } if(k==H.elem[p].key)//找到相等的关键值时返回1 return 1; else return -1; } void collision(int &p,int d) // 线性探测再散列 { // 开放定址法处理冲突 p=(p+d)%m; } int InsertHash(HashTable &H,char name[SIZE]) {//插入一组相关信息 int c=0,p,k=0; for(int i=0;name[i]!=NULL;i++){ k+=(int)name[i]; } if(SearchHash(H,k,p,c)==1) return 0; else{//当查找不到时，给插入的一组信息链接起来 H.elem[p].key=k; H.elem[p].length=c+1; H.elem[p].Hkey=k%m; strcpy(H.elem[p].name,name); ++H.count;//计数器加1 return 1; } } void output(HashTable H) {//显示哈希表 double b; int j=0,i; printf("地址\t 关键字\t 搜索长度 H(key) 拼音\n"); for(i=0;i<20;i++){ printf("%d\t %d\t %d\t %d\t %s\n",i,H.elem[i].key,H.elem[i].length,H.elem[i].Hkey,H.elem[i].name); } printf("按任意键继续显示..."); getch(); printf("\n"); for(i=20;i<m;i++){ printf("%d\t %d\t %d\t %d\t %s\n",i,H.elem[i].key,H.elem[i].length,H.elem[i].Hkey,H.elem[i].name); } for(i=0;i<m;i++) j+=H.elem[i].length; b=(double)j/H.count; printf("平均查找长度为：ASL(%d)：%f\n",H.count,b); } void Search(HashTable H) {//查找人名 int c=0,p,k=0; char ch[SIZE]; printf("请输入姓名的拼音："); scanf("%s",ch); for(int i=0;ch[i]!=NULL;i++){ k+=(int)ch[i]; } if(SearchHash(H,k,p,c)==1&&strcmp(ch,H.elem[p].name)==0){ //若关键值相同并且人名相同则输出其相关信息 printf("姓名：%s\n",H.elem[p].name); printf("关键字：%d\n",H.elem[p].key); printf("查找长度：%d\n",H.elem[p].length); } else{ printf("该名字没找到！\n"); } }