课程设计-散列法

福建工程学院课程设计课程：数据结构课程设计题目：散列法的实验研究专业：计算机科学与技术班级：计算机1001姓名：张扬文学号：3100301142011年12月24日实验题目:散列法的实验研究第一．需要解决的问题首先要输入你的用户信息并构建哈希表，其间会产生冲突我们必须构建一个解决冲突的函数；我们还要以人名和电话号码两种方式建立哈希表。最后，要人名和电话号码方式查找用户信息。在此次设计中需要解决的问题主要有以下几点：1，输入用户信息函数；2，根据输入信息构建哈希表；3，以人名和用户信息的方式搜索用户信息；4，解决输入信息冲突的问题；第二．算法的基本思路描述输入用户信息时会产生冲突，于是我们构建了二次探测函数来解决冲突，再者应把人名进行折叠处理，然后除留取余数法取得哈希模值，才能用于二次探索。建立好哈希表后，就要以人名和电话号码形式查找信息，就要构造两个函数，最后构建一个主函数起调用作用，将各个函数相互组合串联在一起，形成了具有某种功能的一个小系统。第三．算法的设计3.1）数据结构的设计和说明在设计中运用到了两个结构体，Record结构体中主要包含三项，一个是姓名，电话号码和地址，另一个结构体中有数据元素存储地址，当前数据元素的个数和当前容量。在主函数中首先输出菜单界面，显示菜单界面供使用者选择要操作的序号。当操作者选择出序号后在，switch调用相应的函数。使用者只要根据提示进行操作即可。1-添加用户信息2-读取所有用户信息3-以姓名建立哈希表4-以电话号码建立哈希表5-查找并显示给定用户名的记录6-查找并显示给定电话号码的记录7-退出程序3.2）关键算法设计（其他函数大致相同不详加介绍了）1,冲突处理函数DataTypecollision(intp,intc){//冲突处理函数，采用二次探测再散列法解决冲突inti,q;i=c/2+1;//求递增序列while(iHASH_SIZE){//当序列小于表长if(c%2==0){//保证递增序列每次加1c++;q=(p+i*i)%HASH_SIZE;//求空地址if(q=0)returnq;elsei=c/2+1;}else{q=(p-i*i)%HASH_SIZE;c++;if(q=0)returnq;elsei=c/2+1;}}return-1;}2,创建哈希表函数voidCreate_Hash1(HashTable*H,Record*a){//建表，以人名为关键字，建立相应的散列表若哈希地址冲突，进行冲突处理inti,p,c=0,pp;for(i=0;inum;i++){p=Hash1(a[i].name);//构造哈希函数pp=p;while(H-elem[pp]!=NULL)//当表中有值存在时，调用二次探测解决冲突{pp=collision(p,c);if(pp0){printf(第%d记录无法解决冲突,i+1);//需要显示冲突次数时输出continue;}//无法解决冲突，跳入下一循环}H-elem[pp]=&(a[i]);//求得哈希地址，将信息存入H-count++;}printf(\n建表完成！\n哈希表容量为%d,当前表内存储的记录个数为%d\n,HASH_SIZE,H-count);}3,以人名查找函数voidSearch_Hash2(HashTable*H,intc){//在通讯录里查找电话号码关键字，若查找成功，显示信息//c用来记录冲突次数，查找成功时显示冲突次数elemtypetele;printf(\n输入要查找记录的电话号码:);scanf(%s,tele);intp,pp;p=Hash2(tele);//用除留余数法构造哈希函数pp=p;while((H-elem[pp]!=NULL)&&(Equite(tele,H-elem[pp]-telphone)==-1))//当表中地址有值存在时，进行探测处理pp=collision(p,c);if(H-elem[pp]!=NULL&&Equite(tele,H-elem[pp]-telphone)==1){//当表中的值与要查找的值一样时，成功printf(\n查找成功!以下是您需要查找的信息:\n,c);printf(姓名:%s电话号码:%s联系地址:%s\n,H-elem[pp]-name,H-elem[pp]-telphone,H-elem[pp]-address);}else{printf(\n此号码不存在，查找失败！！！\n);}}3.3）模块结构图及各模块功能算法模块图：1).主函数2）输入用户信息3）打印用户信息4）人名方式建立哈希函数5）电话号码方式建立哈希函数6）姓名方式查找信息7）电话号码方式查找信息8)二次探测解决冲突8)二次探测解决冲突8)二次探测解决冲突9)折叠函数1主函数intmain()主要起调用函数的作用，将其它函数组合起来实现算法功能。2二次探测函数DataTypecollision(intp,intc)主要是当关键码得到的哈希地址产生冲突时就按照二次探测的方法寻找其他的地址。3读取函数voidShow_Information(Record*s)打印出所有用户的信息。4创建哈希表voidCreate_Hash1(HashTable*H,Record*a)以人名构造哈希表。5创建哈希表voidCreate_Hash2(HashTable*H,Record*a)以电话号码构造哈希表。6以姓名方式查找函数voidSearch_Hash1(HashTable*H,intc)以人名为关键字进行查找。7以电话号码方式查找函数voidSearch_Hash2(HashTable*H,intc)以电话号码为关键字进行查找。8二次探测函数DataTypecollision(intp,intc)产生冲突时，以H(key)=（H（key）+d）modm方式找到其他空地址，将数据存入。9折叠函数intfold(elemtypes)将姓名字符串转化为大写形式计算长度。第四．源程序清单#includestdio.h#includestdlib.h#includestring.h#defineMAXSIZE30//电话簿记录最大长度#defineMAX_SIZE20//人名的最大长度#defineHASH_SIZE35//定义表最大长度#defineLENsizeof(HashTable)//结构体HashTable占用的字节数typedefintDataType;//用户自定义typedefcharelemtype[MAX_SIZE];typedefstruct{//记录elemtypename;elemtypetelphone;elemtypeaddress;}Record;typedefstruct{//哈希表Record*elem[HASH_SIZE];//数据元素存储地址intcount;//当前数据元素个数intsize;//当前容量}HashTable;DataTypenum;//记录的个数DataTypeEquite(elemtypex,elemtypey){//关键字比较，相等返回1;否则返回-1if(strcmp(x,y)==0)return1;elsereturn-1;}voidget_Inforamance(Record*s){//输入用户详细信息printf(请输入要添加的个数：);scanf(%d,&NUM_BER);inti;for(i=0;inum;i++){printf(请输入第%d个记录的用户名:,i+1);scanf(%s,s[i].name);printf(请输入第%d个记录的电话号码:,i+1);scanf(%s,s[i].telphone);printf(请输入第%d个记录的地址：,i+1);scanf(%s,s[i].address);}}voidShow_Information(Record*s)//输入的用户信息{inti;for(i=0;inum;i++)printf(\n第%d个用户信息:姓名:%s电话号码:%s联系地址:%s,i+1,s[i].name,s[i].telphone,s[i].address);}intfold(elemtypes){//人名的折叠处理char*p;intsum=0;elemtypea;strcpy(a,s);//复制字符串，不改变原字符串的大小写strupr(a);//将字符串a转换为大写形式p=a;while(*p!='\0')sum+=*p++;returnsum;}intHash1(elemtypestr){//哈希函数intn;intm;n=fold(str);//先将用户名进行折叠处理m=n%HASH_SIZE;//折叠处理后的数，用除留余数法构造哈希函数returnm;//并返回模值}intHash2(elemtypestr){//哈希函数longn;intm;n=atoi(str);//把字符串转换成整型数m=n%HASH_SIZE;//用除留余数法构造哈希函数returnm;//并返回余数值}DataTypecollision(intp,intc){//冲突处理函数，采用二次探测再散列法解决冲突inti,q;i=c/2+1;while(iHASH_SIZE){if(c%2==0){c++;q=(p+i*i)%HASH_SIZE;if(q=0)returnq;elsei=c/2+1;}else{q=(p-i*i)%HASH_SIZE;c++;if(q=0)returnq;elsei=c/2+1;}}return-1;}voidCreate_Hash1(HashTable*H,Record*a){//建表，以人名为关键字，建立相应的散列表若哈希地址冲突，进行冲突处理inti,p,c=0,pp;for(i=0;inum;i++){p=Hash1(a[i].name);pp=p;while(H-elem[pp]!=NULL){pp=collision(p,c);if(pp0){printf(第%d记录无法解决冲突,i+1);//需要显示冲突次数时输出continue;}//无法解决冲突，跳入下一循环}H-elem[pp]=&(a[i]);//求得哈希地址，将信息存入H-count++;}printf(\n建表完成！\n哈希表容量为%d,当前表内存储的记录个数为%d\n,HASH_SIZE,H-count);}voidSearch_Hash1(HashTable*H,intc){//在通讯录里查找姓名关键字，若查找成功，显示信息c用来记录冲突次数，查找成功时显示冲突次数elemtypestr;printf(\n请输入要查找记录的姓名:\n);scanf(%s,str);intp,pp;p=Hash1(str);pp=p;while((H-elem[pp]!=NULL)&&(Equite(str,H-elem[pp]-name)==-1))pp=collision(p,c);if(H-elem[pp]!=NULL&&Equite(str,H-elem[pp]-name)==1){printf(\n查找成功！以下是您需要查找的信息:\n,c);printf(姓名:%s电话号码:%s联系地址:%s\n,H-elem[pp]-name,H-elem[pp]-telphone,H-elem[pp]-address);}elseprintf(\n此人不存在，查找失败！！！\n);}voidCreate_Hash2(HashTable*H,Record*a){//建表，以电话号码为关键字，建立相应的散列表//若哈希地址冲突，进行冲突处理inti,p=-1,c=0,pp;for(i=0;inum;i++){p=Hash2(a[i].telphone);pp=p;while(H-elem[pp]!=N