数据结构实验之哈希查找.doc

数据结构实验之哈希查找#include#include#include#include#define SIZE 11#define NAMENUM 5#define MANELEN 20#define RSIZE 99typedef structchar nameMANELEN;HashTable;void Createrand(int random);void NameArray(char nameNAMENUMMANELEN);int Hash(int key);int Hashrand(int random,int key,int k);/void Strcpy(char *S1,char *S2);/int StrCmp(char *S1,char *S2);void Hashsearch(char S,int &count,int &location,int random,char nameNAMENUMMANELEN) ;void main()int i,j,k=0,key=0,count=0,total=0,location=0,index=0,randomRSIZE;char tempMANELEN=0,nameNAMENUMMANELEN;HashTable HTSIZE;for(i=0;iSIZE;i+)HT0=0;NameArray(name); /创建姓名表Createrand(random); /创建伪随机数组 for(i=0;iNAMENUM;i+) /将NAMENUM个名字散列到Hash表中strcpy(temp,namei);for(j=0;tempj!=0;j+)key+=(tempj-a)*(tempj-a); /姓名中每个字母与a的ASCII码值之差的平方和作为其关键值printf(关键值为:%dn,key);index=Hash(key); /利用Hash函数计算下标值printf(下标为：%dn,index);if(HT=0) /若该位置空strcpy(HT,temp); /复制到表中相应位置else /若不空，即冲突 k=0;while(HT!=NULL) /只要不空就利用Hashrand函数再次计算下标，直到找到空的位置index=Hashrand(random,key,k);k+;strcpy(HT,temp); /复制到表中相应位置printf(1234567890); /Hash表建立完毕for(i=0;iNAMENUM;i+) /求质量因子Hashsearch(namei,count,location,random,name); /查找并计算该名字在表中位置及查找次数printf(%s查找了%d次,在表中第%d位n,namei,count,location);total+=count; /统计总查找次数printf(总查找次数为%d,total);printf(质量因子为%4.2f,(float)(NAMENUM/total); /求质量因子完毕printf(请任意输入一个待查找的名字：);/任意输入的查找scanf(%s,temp);Hashsearch(temp,count,location,random,name);if(location!=-1)printf(%s查找了%d次,在表中第%d位n,temp,count,location);else printf(无此姓名!n);void Createrand(int random)int i,tag=0;/printf(伪随机数组为：n);for(i=0;iRSIZE;i+)tag+;randomi=rand()%(10*RSIZE);/printf(%-4d,randomi);/if(tag%5=0) /printf(n);/printf(n);void NameArray(char nameNAMENUMMANELEN)int i,j=0,num;num=NAMENUM; printf(请输入%d个学生姓名：n,num);for(i=0;inum;i+)doscanf(%c,&nameij);j+;while(nameij-1!=n);nameij=0;namenum0=0;int Hash(int key)int index;index=key%SIZE;return index;int Hashrand(int random,int key,int k)int index;index=(Hash(key)+(k*k)%SIZE;return index;/*void Strcpy(char *S1,char *S2)int i=0;while(S2i!=0)S1i=S2i;i+;S1i=0;*/*int StrCmp(char *S1,char *S2)int i=0,flag=0;while(S1i=S2i)&(S1i!=0)i+;if(S1i=0)&(S2i=0)flag=1;return flag;*/void Hashsearch(char S,int &count,int &location,int random,char nameNAMENUMMANELEN)int i,index,key=0,flag;for(i=0;Si!=0;i+)key+=(Si-a)*(Si-a); count=1;location=-1;index=Hash(key);flag=strcmp(S,nameindex);if(flag=1)location=index;return;elsedoco