数据结构课程设计-通讯录的制作

软件学院课程设计报告书课程名称 数据结构课程设计 设计题目 通讯录的制作 专业班级 软件工程XXXX 学号 XXXXXXXX 姓名 XXX 指导教师 XXX 2012年01月目录TOC\o"1-5"\h\z\o"CurrentDocument"1、设计时间 3\o"CurrentDocument"2、设计目的 3\o"CurrentDocument"3、设计任务 3\o"CurrentDocument"4、设计内容 3\o"CurrentDocument"需求分析 3\o"CurrentDocument"总体设计 4\o"CurrentDocument"本程序中用到的所有抽象数据类型的定义 4\o"CurrentDocument"主程序的流程 4\o"CurrentDocument"详细设计 6\o"CurrentDocument"定义的所有数据类型 6\o"CurrentDocument"主函数 11\o"CurrentDocument"函数的调用关系图 12\o"CurrentDocument"测试与分析 13测试 13\o"CurrentDocument"分析 19\o"CurrentDocument"附录 19\o"CurrentDocument"5、总结与展望 28参考文献 291设计时间2012年12月30日至2012年1月5日2设计目的数据结构是计算机专业的核心课程，是计算机科学的算法理论基础和软件设计的技术基础。数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并上机调试的基本方法。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显着的促进作用。3设计任务设计任务：针对你所在班集体中的“人名”，设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查找过程。设计要求：(1)每个人的信息至少包括姓名，电话，地址。至少包括对通讯录的创建，添加和按姓名查找等功能。(2)假设人名为汉语拼音全拼形式，待插入哈希表的长度为你所在班级的人数。哈希函数用除留余数法构造，采用链地址法或二次探测再散列法解决冲突。(3)完成菜单设计。操作有必要的提示。实现提示：假设人名最大长度不超过20，取码可以采用折叠处理，将每个字符对应的ASCII码求和。4设计内容需求分析(1)程序所需要达到的功能：是通过创建哈希表，实现通讯录的创建，并通过哈希表的插入和查找使通讯录可以任意进行姓名、电话、地址的添加和相应的查找。(2)输入的形式和输入值的范围：姓名地址均使用汉语拼音全拼形式，电话使用数字，名片的添加不会超过班级总人数。（3）输出的形式：若输出整个哈希表内容，则按照哈希表的每一项所对应输入内容后，将整个名片表直接输出；若单个查找，则只会出现查找时对应的名片内容。（4）测试数据：输入的名片个数应该小于设定的电话本的记录数量（＜20），输入的名片姓名的汉语拼音的长度也应小于设定的姓名的最大长度（＜20），只要在规定的输入范围内输入都能得到想要的结果，若超过了规定范围，程序将结束进程。总体设计本程序中用到的所有抽象数据类型的定义1、MAXSIZE：通讯录的大小2、MAX_SIZE：通讯录中姓名、电话、地址的最大长度3、HASHSIZE：创建哈希表的容量4、SUCCESS：成功标志位5、UNSUCCESS：失败标志位6、NA：存储姓名、电话、地址的通用数据结构7、record:通讯录的结构体8、status：一个int型值本程序中用来标示返回值状态9、eq方法：传入两个NA作为参数，返回一个status，作用是比较两个NA是否相同10、fold方法：传入一个NA作为参数，返回一个long，作用是将NA按照一定的算法转换成数值型，作为hashCode11、collision：处理冲突，采用二次探测再散列法解决冲突12、CreateHash：创建哈希表，以电话号码为关键字，建立相应的散列表13、SearchHash：查找哈希表，在通讯录里查找电话号码关键字，若查找成功，显示信息主程序的流程流程如下图流程图所示程序开始T 图一主程序的流程图A基本信息显示菜单一 /输入i/定义节点类型 typedefstructRecord定义哈希表节点类型 typedefstructHashTable关键字比较——voideq（）人名的折叠处理，将名字转换成一个数值一一voidfold（）建立哈希函数 voidHash（）建立解决冲突的方法 voidcollision（）B.显示菜单：按照指定的长度建立通讯录显示通讯录内所有用户信息添加新的用户信息查找并显示给定用户名的记录查找并显示给定电话号码的记录显示版本信息并退出通讯录C.根据选项实际操作主函数voidmain（）分别调用下面函数并对应输出voidprintf（）录入内存内容 voidgetin（）显示用户信息 voidShowInformation（）输入新名片信息 voidinsert（）创建哈希表 voidCreateHash（）查找哈希表中的关键字 voidSearchHash（）详细设计定义的所有数据类型（1）定义通讯录节点结构体typedefstruct{ 〃每一条电话本记录NAname;NAtel;NAadd;}Record;（2）定义哈希表节点结构体

typedefstruct//哈希表Record*elem[HASHSIZE];//数据元素存储基址intcount;//当前数据元素个数intsize;〃当前容量}HashTable;（3）关键字的比较Statuseq(NAx,NAy)//关键字比较，相等返回SUCCESS；否则返回UNSUCCESSif(strcmp(x,y)==0)returnSUCCESS;elsereturnUNSUCCESS;}StatusNUM_BER;typedefstruct//哈希表Record*elem[HASHSIZE];//数据元素存储基址intcount;//当前数据元素个数intsize;〃当前容量}HashTable;（3）关键字的比较Statuseq(NAx,NAy)//关键字比较，相等返回SUCCESS；否则返回UNSUCCESSif(strcmp(x,y)==0)returnSUCCESS;elsereturnUNSUCCESS;}StatusNUM_BER;//记录的个数（4）对姓名的折叠处理longfold(NAs)//姓名的折叠处理,就是将名字转换成一个数值char*p;longsum=0;NAss;strcpy(ss,s);//复制字符串不改变原字符串的大小写，将字符串ss转换为大写形式p=ss;while(*p!='\0')sum+=*p++;//将字符串转换成一个int型的值用于hash表的计算比较returnsum;（5）建立哈希函数intHash1(NAstr)〃哈希函数longn;intm;n=fold(str);//先将用户名进行折叠处理n=fold(str);m=n%HASHSIZE;〃折叠处理后的数，用除留余数法构造哈希函数m=n%HASHSIZE;〃折叠处理后的数，用除留余数法构造哈希函数returnm; 〃并返回模值)(6)解决冲突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;returnUNSUCCESS;}else{q=(p-i*i)%HASHSIZE;c++;if(q>=0)returnq;elsei=c/2+1;returnUNSUCCESS;}}returnUNSUCCESS;}(7)创建以姓名为关键字哈希表voidCreateHash1(HashTable*H,Record*a){ //建表，以姓名为关键字，建立相应的散列表〃若哈希地址冲突，进行冲突处理inti,p=-1,c,pp;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)continue;}//无法解决冲突，跳入下一循环}H->elem[pp]=&(a[i]); //求得哈希地址，将信息存入H->count++;)(8)查找以姓名为关键字的哈希表voidSearchHash1(HashTable*H,intc){ //在通讯录里查找姓名关键字，若查找成功，显示信息intp,pp; //c用来记录冲突次数，查找成功时显示冲突次数NAstr;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)returnSUCCESS;elsereturnUNSUCCESS;)(9)创建以电话号码为关键字的哈希表voidCreateHash2(HashTable*H,Record*a){ //建表，以电话号码为关键字，建立相应的散列表〃若哈希地址冲突，进行冲突处理inti,p=-1,c,pp;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)continue;}H->elem[pp]=&(a[i]); //求得哈希地址，将信息存入H->count++;}}(10)查找以电话号码为关键字的哈希表voidSearchHash2(HashTable*H,intc){ //在通讯录里查找电话号码关键字，若查找成功，显示信息//c用来记录冲突次数，查找成功时显示冲突次数intp,pp;NAtele;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)returnSUCCESS;elsereturnUNSUCCESS;)(11)录入内存内容voidgetin(Record*a) 〃录入通讯录的内容，传入一个record的指针，然后针对这个指针指向的内存记录进行操作{inti;scanf("%d”,&NUM_BER); 〃输入要创建通讯录的人数for(i=0;i<NUM_BER;i++)scanf(a[i].name,a[i].tel,a[i].add);)(12)插入新名片信息intinsert(Record*a) 〃插入新同学的方法{inti;if(NUM_BER>=HASHSIZE)return0;else{scanf(a[NUM_BER].name); //输入要新增名片的姓名for(i=0;i<NUM_BER;i++){if(strcmp(a[i].name,a[NUM_BER].name)==0)return0;}//此名片已经存在，重新输入scanf(a[NUM_BER].tel); //输入要新增名片的电话号码for(i=0;i<NUM_BER;i++){if(strcmp(a[i].tel,a[NUM_BER].tel)==0)return0;}//此号码已经存在，重新输入

scanf(a[NUM_BER].add); //输入要新增名片的地址NUM_BER++;return1;}}(13)显示输入的用户信息voidShowInformation(Record*a) 〃显示输入的用户信息{inti;for(i=0;i<NUM_BER;i++)printf(a[i].name,a[i].tel,a[i].add);}主函数intmain()(Recorda[MAXSIZE];intc,flag=1,i;intnum;HashTable*H;H二(HashTable*)malloc(LEN);for(i=0;i<HASHSIZE;i++)(H->elem[i]=NULL;H->size二HASHSIZE;H->count=0;)getch();while(flag) 〃当前永真，也可以让退出方法将flag赋值为0然后下次循环的时候退出程序scanf("%d",&num); //按照具体菜单输入需要执行的数字switch(num){case1:getin(a);break;ShowInformation(a);break;c=0;CreateHash1(H,a);SearchHash1(H,c);break;c=0;CreateHash2(H,a);SearchHash2(H,c);break;if(!insert(a))returnUNSUCCESS;elsereturnSUCCESS;break;case0:getch();exit(1);default:)}system("pause");return0; //程序结束4.3.3函数的调用关系图函数调用关系图如下图所示 新增同学调用voidgetin() 图二函数的调用关系图4.4测试与分析4.4.1测试(1)打开程序，会“按任意键开始程序〜”字样，然后按任意键开始程序，显示主菜单界面如下:然后输入你的选择，进入你所要进行的操作中。(2)选择“1”，按照指定的长度建立通讯录，则有下图:输入要创建的通讯录人数，设为3,则输入“3”，则有下图:输入第一个记录的用户名，输入“由。照丫印2"，则有下图:输入第一个记录的电话号码，输入“”，则有下图：输入第一个记录的地址，输入“乂合卜0/，，则有下图:故已经输入完一个名片信息，继续输入另外两个名片信息，则有下图:31c31c31c31c31c 31c31c21c31c31c31c请选择操作：1输入要创建通讯录的人数二3请输入第1个记录的用户名：chengyujia请输入第1个记录的电话号码输入第1个记录的地址：suzhou请输入第2个记录的用户名：lishengqiang请输入第2个记录的电话号码输入第2个记录的地址：tieling请输入第3个记录的用户名：liuyu请输入第3个记录的电话号码输入第3个记录的地址：benxi当输入最后一个信息后，确认后返回开始菜单，如下图:

（3）选择“2”，显示通讯录内所有用户信息，则有下图：然后有返回初始菜单，继续选择。（4）选择“3”，添加新的用户信息，则有下图：按照（2）的方式继续输入一个名片信息，确认后，则有下图：然后有返回初始菜单，继续选择。（5）选择“4”，查找并显示给定用户名的记录，则有下图：输入要查找的记录姓名，输入—ishengqiang”，则有下图：然后有返回初始菜单，继续选择。（6）选择“5”，查找并显示给定电话号码的记录，则有下图：继续输入“”，则有下图：然后有返回初始菜单，继续选择。（7）选择“0”，显示通讯录信息并退出通讯录，则有下图：然后按任意键退出程序。4.4.2分析调试过程中我认为比较复杂的是用哈希表的二次探测再散列法解决冲突的算法不是特别容易研究明白，故对整个哈希表的定义与执行都是个不小的挑战，于是我设法通过查询资料，对其算法进行了仔细的分析，只要将二次探测再散列法的数学关系式琢磨透了，对于算法的表达就容易多了。因为二次探测再散列法是对出现冲突后，进行的摆动数列的方法解决冲突，其中需要考虑数据的变化、符号的改变和位置的准确移动，所以数学关系式思考起来比较麻烦。4.5附录#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAXSIZE20〃电话薄记录数量#defineMAXSIZE20〃人名的最大长度#defineHASHSIZE31〃定义表长#defineMAXSIZE20〃电话薄记录数量#defineMAXSIZE20〃人名的最大长度#defineHASHSIZE31〃定义表长#defineSUCCESS1#defineUNSUCCESS-1

#defineLENsizeof(HashTable)typedefintStatus;typedefcharNA[MAX_SIZE];typedefstruct{NAname;NAtel;#defineLENsizeof(HashTable)typedefintStatus;typedefcharNA[MAX_SIZE];typedefstruct{NAname;NAtel;NAadd;}Record;typedefstruct{Record*elem[HASHSIZE];intcount;intsize;}HashTable;Statuseq(NAx,NAy){//hashTable的长度〃每一条电话本记录//哈希表//数据元素存储基址//当前数据元素个数〃当前容量//关键字比较，相等返回SUCCESS；否则返回UNSUCCESSif(strcmp(x,y)==0)returnSUCCESS;elsereturnUNSUCCESS;}StatusNUM_BER; 〃记录的个数longfold(NAs){ //人名的折叠处理,就是将名字转换成一个数值char*p;longsum=0;NAss;strcpy(ss,s); //复制字符串，不改变原字符串的大小写//strupr(ss);//将字符串ss转换为大写形式p=ss;while(*p!='\0')sum+=*p++; //将字符串转换成一个int型的值用于hash表的计算比较printf("\n%s的转换hashCode是％ld\n”,s,sum);returnsum;〃哈希函数intHash1(NAstr){longn;intm;

〃哈希函数n=fold(str);m=n%HASHSIZE;returnm;)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){ printf("is0&&q>0");returnq;}else{i=c/2+1;printf("is0&&q<0");returnUNSUCCESS;}}else{q=(p-i*i)%HASHSIZE;c++;if(q>=0) {returnq;}else{i=c/2+1;printf("isnot0&&q<0");returnUNSUCCESS;}}}returnUNSUCCESS;)voidCreateHash1(HashTable*H,Record*a){ //建表，以人的姓名为关键字，建立相应的散列表〃若哈希地址冲突，进行冲突处理inti,p=-1,c,pp;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("createHash1第％~记录无法解决冲突",i+1);//需要显示冲突次数时输出continue;} //无法解决冲突，跳入下一循环}H->elem[pp]=&(a[i]); //求得哈希地址，将信息存入H->count++;printf("createHash1第％~个记录冲突次数为%d。\n",i+1,c);//需要显示冲突次数时输出}printf("\ncreateHash1建表完成!\n此哈希表容量为％&当前表内存储的记录个数为％d.\n",HASHSIZE,H->count);}voidSearchHash1(HashTable*H,intc){ //在通讯录里查找姓名关键字，若查找成功，显示信息intp,pp; //c用来记录冲突次数，查找成功时显示冲突次数NAstr; 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]->tel,H->elem[pp]->add);)elseprintf("\n此人不存在，查找不成功!\n");)voidCreateHash2(HashTable*H,Record*a){ //建表，以电话号码为关键字，建立相应的散列表〃若哈希地址冲突，进行冲突处理inti,p=-1,c,pp;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);)voidSearchHash2(HashTable*H,intc){ //在通讯录里查找电话号码关键字，若查找成功，显示信息//c用来记录冲突次数，查找成功时显示冲突次数intp,pp;NAtele;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]->tel,H->elem[pp]->add);}elseprintf("\n此人不存在，查找不成功!\n");)voidgetin(Record*a){〃录入通讯录的内容，传入一个record的指针，然后针对这个指针指向的内存记录进行操作inti; printf("输入要创建通讯录的人数：\n");scanf("%d”,&NUM_BER);for(i=0;i<NUM_BER;i++){printf("请输入第％~个记录的用户名:\n",i+1);scanf("%s",a[i].name);printf("请输入第％~个记录的电话号码:\n",i+1);scanf("%s",a[i].tel);printf("请输入第％~个记录的地址:\n",i+1);scanf("%s",a[i].add); //gets(str2);??????}}intinsert(Record*a){ 〃插入新同学的方法inti;if(NUM_BER>=HASHSIZE)(printf("hashTable已经达到班级人数的最大值：％d!请修改班级初始人数！”,HASHSIZE);return0;}else{ printf(”请输入要新增同学的姓名：\n");scanf("%s",a[NUM_BER].name);for(i=0;i<NUM_BER;i++){if(strcmp(a[i].name,a[NUM_BER].name)==0){printf("此同学：%s已经存在，请重新确认姓名！",a[NUM_BER].name);return0;}}printf(”请输入要新增同学的电话号码：\n");scanf("%s",a[NUM_BER].tel);for(i=0;i<NUM_BER;i++){if(strcmp(a[i].tel,a[NUM_BER].tel)==0){ printf("此号码：%s已经存在，请重新确认号码！\n",a[NUM_BER].tel);return0;}}printf(”请输入要新增同学的地址：\n");scanf("%s",a[NUM_BER].add);NUM_BER++;return1;}}voidShowInformation(Record*a) 〃显示输入的用户信息

{inti;printf("姓名％-16$电话％-16s住址％-20s\n",”O;for(i=0;i<NUM_BER;i++)printf("%-20s%-20s%-20s\n",a[i].name,a[i].tel,a[i].add);//printf("\n第％~个用户信息:\n姓名：%s\n电话号码：%s\n联系地址：%s\n",i+1,a[i].name,a[i].tel,a[i].add);intmain(){Recorda[MAXSIZE];intc,flag=1,i;intnum;HashTable*H;H=(HashTable*)malloc(LEN);for(i=0;i<HASHSIZE;i++)H->elem[i]=NULL;H->size二HASHSIZE;H->count=0;printf(********************************\n");printf("addressbook\n");printf("madebyLishengqiang\n");printf("addressbook\n");printf("madebyLishengqiang\n");printf(********************************\n");printfC按任意键开始程序〜\n");getch();while(flag){ 〃当前永真，也可以让退出方法将flag赋值为0然后下次循环的时候退出程序printf("\n小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小");printf("\n欢迎来到软件工程10-01李胜强的数据结构课程设计!!);printf("\n小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小");printf("\n.按照指定的长度建立通讯录");printf("\nprintf("\n小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小");printf("\n欢迎来到软件工程10-01李胜强的数据结构课程设计!!);printf("\n小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小小");printf("\n.按照指定的长度建立通讯录");printf("\n.显示通讯录内所有用户信息");printf("\n3.添加新的用户信息 ")printf("\n4.查找并显示给定用户名的记录 ")printf("\n5.查找并显示给定电话号码的记录 ")printf("\n0.显示通讯录信息并退出通讯录 ")printf("\n1V****************************************printf("\n请选择操作： \n"););scanf("%d”,&num);;;;switch(num){case1:getin(a);printf("\n3.添加新的用户信息 ")printf("\n4.查找并显示给定用户名的记录 ")printf("\n5.查找并显示给定电话号码的记录 ")print