资源描述：
《数据结构课程设计_哈希表实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、福建工程学院课程设计课程：算法与数据结构题目：哈希表专业：网络工程班级：xxxxxx班座号：xxxxxxxxxxxx：xxxxxxx2011年12月31日...实验题目：哈希表一、要解决的问题针对同班同学信息设计一个通讯录，学生信息有，学号，等。以学生为关键字设计哈希表，并完成相应的建表和查表程序。基本要求：以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按查询的操作。运行的环境：MicrosoftVisualC++6.0二、算法基本思想描述设计一个哈希表（哈希表的元素为自定义的结构体）用来存放待填
2、入的30个人名，人名为中国的汉语拼音形式，用除留余数法构造哈希函数，用线性探查法解决哈希冲突。建立哈希表并且将其显示出来。通过要查找的关键字用哈希函数计算出相应的地址来查找人名。通过循环语句调用数组中保存的数据来显示哈希表。三、设计1、数据结构的设计和说明（1）结构体的定义typedefstruct//记录{NAname;NAxuehao;NAtel;}Record;录入信息结构体的定义，包含，学号，。typedefstruct//哈希表{Record*elem[HASHSIZE];//数据元素存储基址intcount;//当前数据元素个数intsize;//当前容量}HashTab
3、le;哈希表元素的定义，包含数据元素存储基址、数据元素个数、当前容量。2、关键算法的设计（1）的折叠处理longfold(NAs)//人名的折叠处理...{char*p;longsum=0;NAss;strcpy(ss,s);//复制字符串，不改变原字符串的大小写strupr(ss);//将字符串ss转换为大写形式p=ss;while(*p!=' ')sum+=*p++;printf("sum====================%d",sum);returnsum;}（2）建立哈希表1、用除留余数法构建哈希函数2、用线性探测再散列法处理冲突intHash1(NAstr)//
4、哈希函数{longn;intm;n=fold(str);//先将用户名进行折叠处理m=n%HASHSIZE;//折叠处理后的数，用除留余数法构造哈希函数returnm;//并返回模值}Statuscollision(intp,intc)//冲突处理函数，采用二次探测再散列法解决冲突{inti,q;i=c/2+1;while(i=0)returnq;elsei=c/2+1;}else{q=(p-i*i)%HASHSIZE;c++;if(q>=0)returnq;elsei=c/2+1;}
5、}returnUNSUCCESS;}voidbenGetTime();voidCreateHash1(HashTable*H,Record*a)...//建表，以人的为关键字，建立相应的散列表{inti,p=-1,c,pp;system("cls");//若哈希地址冲突，进行冲突处理benGetTime();for(i=0;ielem[pp]!=NULL){pp=collision(p,c);if(pp<0){printf("第%d记录无法解决冲突",i+1);//需要显示冲突次数时
6、输出continue;}//无法解决冲突，跳入下一循环}H->elem[pp]=&(a[i]);//求得哈希地址，将信息存入H->count++;printf("第%d个记录冲突次数为%d。",i+1,c);//需要显示冲突次数时输出}printf("建表完成!此哈希表容量为%d,当前表存储的记录个数为%d.",HASHSIZE,H->count);benGetTime();}（3）查找哈希表voidSearchHash1(HashTable*H,intc)//在通讯录里查找关键字，若查找成功，显示信息{intp,pp;NAstr;system("cls");//c用
7、来记录冲突次数,查找成功时显示冲突次数benGetTime();printf("请输入要查找记录的：");scanf("%s",str);p=Hash1(str);pp=p;while((H->elem[pp]!=NULL)&&(eq(str,H->elem[pp]->name)==-1))pp=collision(p,c);if(H->elem[pp]!=NULL&&eq(str,H->elem[pp]->name)==1){printf("
