哈希表 数据结构学校使用

//哈希表设计 //崔海洋 2015.12.25 #include <stdio.h> #include<malloc.h> #include<string.h> #include<iostream> using namespace std; #define HASH_LEN 50 //哈希表的长度 #define M 47 #define NAME_NO 30 //人名的个数 typedef struct NAME { char *py; //名字的拼音 int k; //拼音所对应的整数 }NAME; NAME NameList[HASH_LEN]; typedef struct hterm //哈希表 { char *py; //名字的拼音 int k; //拼音所对应的整数 int si; //查找长度 }HASH; HASH HashList[HASH_LEN]; /*-----------------------姓名（结构体数组）初始化---------------------------------*/ void InitNameList() { NameList[0].py="cuiyunpeng"; NameList[1].py="zhaopeng"; NameList[2].py="nipeigui"; NameList[3].py="lichao"; NameList[4].py="libingrui"; NameList[5].py="liubing"; NameList[6].py="xijingjing"; NameList[7].py="tianyuexiao"; NameList[8].py="mengkai"; NameList[9].py="sunmengxue"; NameList[10].py="lipeng"; NameList[11].py="wuyinong"; NameList[12].py="wangzhongle"; NameList[13].py="mengyongwang"; NameList[14].py="cuihaiyang"; NameList[15].py="tangweicheng"; NameList[16].py="zhangchun"; NameList[17].py="wangsaisai"; NameList[18].py="yuanzhiyu"; NameList[19].py="gaojunjie"; NameList[20].py="hanxinyang"; NameList[21].py="lixueyu"; NameList[22].py="wangzhao"; NameList[23].py="wangshuyuan"; NameList[24].py="lihongchuan"; NameList[25].py="chengruijie"; NameList[26].py="wangguanxiong"; NameList[27].py="jitengfei"; NameList[28].py="wumingxia"; NameList[29].py="wuji"; char *f; int r,s0; for (int i=0;i<NAME_NO;i++)// 求出各个姓名的拼音所对应的整数 { s0=0; f=NameList[i].py; for (r=0;*(f+r) != '\0';r++) //方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字 s0=*(f+r)+s0; NameList[i].k=s0; } } /*-----------------------建立哈希表---------------------------------*/ void CreateHashList() { for (int i=0; i<HASH_LEN;i++)//哈希表的初始化 { HashList[i].py=""; HashList[i].k=0; HashList[i].si=0; } for (int i=0; i<=NAME_NO;) { int sum=0; int adr=(NameList[i].k) % M; //哈希函数 int d=adr; if(HashList[adr].si==0) //如果不冲突 { HashList[adr].k=NameList[i].k; HashList[adr].py=NameList[i].py; HashList[adr].si=1; } else //冲突 { do { d=(d+((NameList[i].k))%10+1)%M; //伪散列 sum=sum+1; //查找次数加1 } while (HashList[d].k!=0); HashList[d].k=NameList[i].k; HashList[d].py=NameList[i].py; HashList[d].si=sum+1; }i++; } } /*-------------------------------------查找------------------------------------*/ void FindList() { printf("\n\n请输入姓名的拼音: "); //输入姓名 char name[20]={0}; //scanf("%s",name); cin>>name; int s0=0; for (int r=0;r<20;r++) //求出姓名的拼音所对应的整数(关键字) s0+=name[r]; int sum=1; int adr=s0 % M; //使用哈希函数 int d=adr; if(HashList[adr].k==s0) //分3种情况进行判断,哈希表中存在 { cout<<"姓名： "<<HashList[d].py<<endl; cout<<"关键字："<<s0<<endl; cout<<"查找长度： 1"<<endl; } else if (HashList[adr].k==0)//若查找单元为空，则输出查找失败 cout<<"无该记录!"; else { int g=0; do { d=(d+s0%10+1)%M; //伪散列，有冲突， 计算下一个散列地址 sum=sum+1; if (HashList[d].k==0) { cout<<endl; cout<<"无记录! "<<endl; g=1; } if (HashList[d].k==s0) { cout<<"姓名:"<<" "<<"关键字"<<" "<<"查找长度"<<endl; cout<<HashList[d].py<<" "<<s0<<" "<<sum; g=1; } }while(g==0); } } /*--------------------------------显示哈希表----------------------------*/ void Display() { int i; printf("\n\n地址\t关键字\t\t搜索长度\tH(key)\t\t拼音 \n"); //显示的格式 for(int i=0; i<15; i++) { printf("%d ",i); printf("\t%d ",HashList[i].k); printf("\t\t%d ",HashList[i].si); printf("\t\t%d ",(HashList[i].k)%M); printf("\t %s ",HashList[i].py); printf("\n"); } for( i=15; i<30; i++) { printf("%d ",i); printf("\t%d ",HashList[i].k); printf("\t\t%d ",HashList[i].si); printf("\t\t%d ",(HashList[i].k)%M); printf("\t %s ",HashList[i].py); printf("\n"); } for( i=30; i<40; i++) { printf("%d ",i); printf("\t%d ",HashList[i].k); printf("\t\t%d ",HashList[i].si); printf("\t\t%d ",(HashList[i].k)%M); printf("\t %s ",HashList[i].py); printf("\n"); } for( i=40; i<50; i++) { printf("%d ",i); printf("\t%d ",HashList[i].k); printf("\t\t%d ",HashList[i].si); printf("\t\t%d ",(HashList[i].k)%M); printf("\t %s ",HashList[i].py); printf("\n"); } float average=0; for (i=0;i<HASH_LEN;i++) average+=HashList[i].si; average/=NAME_NO; printf("\n\n平均查找长度：ASL(%d)=%f \n\n",NAME_NO,average); } void main() { printf("\n------------------------哈希表的建立和查找----------------------"); InitNameList(); CreateHashList (); while(1) { cout<<endl<<endl; cout<<" 1. 显示哈希表"<<endl; cout<<" 2. 查找"<<endl; cout<<" 3. 退出"<<endl; err: char ch1; scanf("%c",&ch1); if (ch1=='1') Display(); else if (ch1=='2') FindList(); else if (ch1=='3') return; else { printf("\n请输入您的选择!"); goto err; } } }