数据结构课程设计-哈希表实验报告

..福建工程学院课程设计课程：算法与数据结构题目：哈希表专业：网络工程__xxxxxx班座号：xxxxxxxxxxxx__xxxxxxx2011年12月实验题目：哈希表要解决的问题针对同班同学信息设计一个通讯录,学生信息有姓名,学号,号码等。以学生姓名为关键字设计哈希表,并完成相应的建表和查表程序。基本要求：姓名以汉语拼音形式,待填入哈希表的人名约30个,自行设计哈希函数,用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。运行的环境：MicrosoftVisualC++6.0二、算法基本思想描述设计一个哈希表〔哈希表内的元素为自定义的结构体用来存放待填入的30个人名,人名为中国姓名的汉语拼音形式,用除留余数法构造哈希函数,用线性探查法解决哈希冲突。建立哈希表并且将其显示出来。通过要查找的关键字用哈希函数计算出相应的地址来查找人名。通过循环语句调用数组中保存的数据来显示哈希表。三、设计1、数据结构的设计和说明〔1结构体的定义typedefstruct//记录{NAname;NAxuehao;NAtel;}Record;录入信息结构体的定义,包含姓名,学号,号码。typedefstruct//哈希表{Record*elem[HASHSIZE];//数据元素存储基址intcount;//当前数据元素个数intsize;//当前容量}HashTable;哈希表元素的定义,包含数据元素存储基址、数据元素个数、当前容量。2、关键算法的设计〔1姓名的折叠处理longfold<NAs>//人名的折叠处理{char*p;longsum=0;NAss;strcpy<ss,s>;//复制字符串,不改变原字符串的大小写strupr<ss>;//将字符串ss转换为大写形式p=ss;while<*p!='\0'>sum+=*p++;printf<"\nsum====================%d",sum>;returnsum;}〔2建立哈希表1、用除留余数法构建哈希函数2、用线性探测再散列法处理冲突intHash1<NAstr>//哈希函数{longn;intm;n=fold<str>;//先将用户名进行折叠处理m=n%HASHSIZE;//折叠处理后的数,用除留余数法构造哈希函数returnm;//并返回模值}Statuscollision<intp,intc>//冲突处理函数,采用二次探测再散列法解决冲突{inti,q;i=c/2+1;while<i<HASHSIZE>{if<c%2==0>{c++;q=<p+i*i>%HASHSIZE;if<q>=0>returnq;elsei=c/2+1;}else{q=<p-i*i>%HASHSIZE;c++;if<q>=0>returnq;elsei=c/2+1;}}returnUNSUCCESS;}voidbenGetTime<>;voidCreateHash1<HashTable*H,Record*a>//建表,以人的姓名为关键字,建立相应的散列表{inti,p=-1,c,pp;system<"cls">;//若哈希地址冲突,进行冲突处理benGetTime<>;for<i=0;i<NUM_BER;i++>{c=0;p=Hash1<a[i].name>;pp=p;while<H->elem[pp]!=NULL>{pp=collision<p,c>;if<pp<0>{printf<"第%d记录无法解决冲突",i+1>;//需要显示冲突次数时输出continue;}//无法解决冲突,跳入下一循环}H->elem[pp]=&<a[i]>;//求得哈希地址,将信息存入H->count++;printf<"第%d个记录冲突次数为%d。\n",i+1,c>;//需要显示冲突次数时输出}printf<"\n建表完成!\n此哈希表容量为%d,当前表内存储的记录个数为%d.\n",HASHSIZE,H->count>;benGetTime<>;}〔3查找哈希表voidSearchHash1<HashTable*H,intc>//在通讯录里查找姓名关键字,若查找成功,显示信息{intp,pp;NAstr;system<"cls">;//c用来记录冲突次数,查找成功时显示冲突次数benGetTime<>;printf<"\n请输入要查找记录的__\n">;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<"\n查找成功！\n查找过程冲突次数为%d．以下是您需要要查找的信息：\n\n",c>;printf<"姓名：%s\n__%s\n号码：%s\n",H->elem[pp]->name,H->elem[pp]->xuehao,H->elem[pp]->tel>;}elseprintf<"\n此人不存在,查找不成功!\n">;benGetTime<>;}〔4显示哈希表voidShowInformation<Record*a>//显示输入的用户信息{inti;system<"cls">;for<i=0;i<NUM_BER;i++>printf<"\n第%d个用户信息:\n__%s\n__%s\n号码：%s\n",i+1,a[i].name,a[i].xuehao,a[i].tel>;}〔5主函数的设计voidmain<intargc,char*argv[]>{Recorda[MAXSIZE];intc,flag=1,i=0;HashTable*H;H=<HashTable*>malloc<LEN>;for<i=0;i<HASHSIZE;i++>{H->elem[i]=NULL;H->size=HASHSIZE;H->count=0;}while<1>{intnum;printf<"\n">;printf<"\n欢迎使用同学通讯录录入查找系统">;printf<"\n哈希表的设计与实现">;printf<"\n[1].添加用户信息">;printf<"\n[2].读取所有用户信息">;printf<"\n[3].以姓名建立哈希表<再哈希法解决冲突>">;printf<"\n[4].以号码建立哈希表<再哈希法解决冲突>">;printf<"\n[5].查找并显示给定用户名的记录">;printf<"\n[6].查找并显示给定号码的记录">;printf<"\n[7].清屏">;printf<"\n[8].保存">;printf<"\n[9].退出程序">;printf<"\n温馨提示：">;printf<"\nⅠ.进行5操作前请先输出3">;printf<"\nⅡ.进行6操作前请先输出4">;printf<"\n">;printf<"请输入一个任务选项>>>">;printf<"\n">;scanf<"%d",&num>;switch<num>{case1:getin<a>;break;case2:ShowInformation<a>;break;case3:CreateHash1<H,a>;/*以姓名建立哈希表*/break;case4:CreateHash2<H,a>;/*以号码建立哈希表*/break;case5:c=0;SearchHash1<H,c>;break;case6:c=0;SearchHash2<H,c>;break;case7:Cls<a>;break;case8:Save<>;break;case9:return0;break;default:printf<"你输错了,请重新输入!">;printf<"\n">;}}system<"pause">;return0;}3、模块结构图及各模块的功能：四、源程序清单：#include<stdio.h>#include<stdlib.h>#include<string.h>#include<windows.h>#defineMAXSIZE20#defineMAX_SIZE20#defineHASHSIZE53#defineSUCCESS1#defineUNSUCCESS-1#defineLENsizeof<HashTable>typedefintStatus;typedefcharNA[MAX_SIZE];typedefstruct{NAname;NAxuehao;NAtel;}Record;typedefstruct{Record*elem[HASHSIZE];intcount;intsize;}HashTable;Statuseq<NAx,NAy>{if<strcmp<x,y>==0>returnSUCCESS;elsereturnUNSUCCESS;}StatusNUM_BER;voidgetin<Record*a>{inti;system<"cls">;printf<"输入要添加的个数：\n">;scanf<"%d",&NUM_BER>;for<i=0;i<NUM_BER;i++>{printf<"请输入第%d个记录的姓名:\n",i+1>;scanf<"%s",a[i].name>;printf<"请输入%d个记录的学号:\n",i+1>;scanf<"%s",a[i].xuehao>;printf<"请输入第%d个记录的号码:\n",i+1>;scanf<"%s",a[i].tel>;}}voidShowInformation<Record*a>{inti;system<"cls">;for<i=0;i<NUM_BER;i++>printf<"\n第%d个用户信息:\n__%s\n__%s\n号码：%s\n",i+1,a[i].name,a[i].xuehao,a[i].tel>;}voidCls<Record*a>{printf<"*">;system<"cls">;}longfold<NAs>{char*p;longsum=0;NAss;strcpy<ss,s>;strupr<ss>;p=ss;while<*p!='\0'>sum+=*p++;printf<"\nsum====================%d",sum>;returnsum;}intHash1<NAstr>{longn;intm;n=fold<str>;m=n%HASHSIZE;returnm;}intHash2<NAstr>{longn;intm;n=atoi<str>;m=n%HASHSIZE;returnm;}Statuscollision<intp,intc>{inti,q;i=c/2+1;while<i<HASHSIZE>{if<c%2==0>{c++;q=<p+i*i>%HASHSIZE;if<q>=0>returnq;elsei=c/2+1;}else{q=<p-i*i>%HASHSIZE;c++;if<q>=0>returnq;elsei=c/2+1;}}returnUNSUCCESS;}voidbenGetTime<>;voidCreateHash1<HashTable*H,Record*a>{inti,p=-1,c,pp;system<"cls">;benGetTime<>;for<i=0;i<NUM_BER;i++>{c=0;p=Hash1<a[i].name>;pp=p;while<H->elem[pp]!=NULL>{pp=collision<p,c>;if<pp<0>{printf<"第%d记录无法解决冲突",i+1>;continue;}}H->elem[pp]=&<a[i]>;H->count++;printf<"第%d个记录冲突次数为%d。\n",i+1,c>;}printf<"\n建表完成!\n此哈希表容量为%d,当前表内存储的记录个数为%d.\n",HASHSIZE,H->count>;benGetTime<>;}voidSearchHash1<HashTable*H,intc>{intp,pp;NAstr;system<"cls">;benGetTime<>;printf<"\n请输入要查找记录的__\n">;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<"\n查找成功！\n查找过程冲突次数为%d．以下是您需要要查找的信息：\n\n",c>;printf<"姓名：%s\n__%s\n号码：%s\n",H->elem[pp]->name,H->elem[pp]->xuehao,H->elem[pp]->tel>;}elseprintf<"\n此人不存在,查找不成功!\n">;benGetTime<>;}voidbenGetTime<>{SYSTEMTIMEsys;GetLocalTime<&sys>;printf<"%4d/%02d/%02d%02d:%02d:%02d.%03d\n",sys.wYear,sys.wMonth,sys.wDay,sys.wHour,sys.wMinute,sys.wSecond,sys.wMilliseconds>;}voidCreateHash2<HashTable*H,Record*a>{inti,p=-1,c,pp;benGetTime<>;for<i=0;i<NUM_BER;i++>{c=0;p=Hash2<a[i].tel>;pp=p;while<H->elem[pp]!=NULL>{pp=collision<p,c>;if<pp<0>{printf<"第%d记录无法解决冲突",i+1>;continue;}}H->elem[pp]=&<a[i]>;H->count++;printf<"第%d个记录冲突次数为%d。\n",i+1,c>;}printf<"\n建表完成!\n此哈希表容量为%d,当前表内存储的记录个数为%d.\n",HASHSIZE,H->count>;benGetTime<>;}voidSearchHash2<HashTable*H,intc>{NAtele;intp,pp;system<"cls">;benGetTime<>;printf<"\n请输入要查找记录的号码：\n">;scanf<"%s",tele>;p=Hash2<tele>;pp=p;while<<H->elem[pp]!=NULL>&&<eq<tele,H->elem[pp]->tel>==-1>>pp=collision<p,c>;if<H->elem[pp]!=NULL&&eq<tele,H->elem[pp]->tel>==1>{printf<"\n查找成功！\n查找过程冲突次数为%d．以下是您需要要查找的信息：\n\n",c>;printf<"姓名：%s\n__%s\n号码：%s\n",H->elem[pp]->name,H->elem[pp]->xuehao,H->elem[pp]->tel>;}elseprintf<"\n此人不存在,查找不成功!\n">;benGetTime<>;}voidSave<>{FILE*fp;if<<fp=fopen<"c:\test.txt","w">>==NULL>{printf<"\nERRORopeningcustometfile">;}fclose<fp>;}voidmain<intargc,char*argv[]>{Recorda[MAXSIZE];intc,flag=1,i=0;HashTable*H;H=<HashTable*>malloc<LEN>;for<i=0;i<HASHSIZE;i++>{H->elem[i]=NULL;H->size=HASHSIZE;H->count=0;}while<1>{intnum;printf<"\n">;printf<"\n欢迎使用同学通讯录录入查找系统">;printf<"\n哈希表的设计与实现">;printf<"\n[1].添加用户信息">;printf<"\n[2].读取所有用户信息">;printf<"\n[3].以姓名建立哈希表<再哈希法解决冲突>">;printf<"\n[4].以号码建立哈希表<再哈希法解决冲突>">;printf<"\n[5].查找并显示给定用户名的记录">;printf<"\n[6].查找并显示给定号码的记录">;printf<"\n[7].清屏">;printf<"\n[8].保存">;printf<"\n[9].退出程序">;printf<"\n温馨提示：">;printf<"\nⅠ.进行5操作前请先输出3">;printf<"\nⅡ.进行6操作前请先输出4">;printf<"\n">;printf<"