还剩18页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
软件学院课程设计报告书课程名称数据结构设计题目哈希表制作通讯录专业班级学号姓名指导教师2014年1月目录TOC\o1-3\h\z\u1设计时间12设计目的13设计任务14设计内容
14.1需求分析
14.11程序所能达到的功能
14.12输入的形式和输入的范围
14.2总体设计
14.21说明本程序中用到的所有抽象数据类型的定义
14.22说明主程序的流程
24.23说明各程序模块之间的层次(调用)关系
34.3详细设计
34.31实现概要设计中定义的所有数据类型,对每个操作只需要写出伪码算法
34.32对主程序和其它主要函数写出伪码算法
44.4测试
54.5附录65总结与展望16____18成绩评定181设计时间2014年1月13日到2014年1月15号2设计目的要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并上机调试的基本方法这对于学生基本程序设计素养的培养和软件工__工作作风的训练,将起到显著的促进作用3设计任务针对你所在班__中的“人名”,设计一个哈希表,使得平均查找长度不超过R,完成相应的建表和查找过程4设计内容1每个人的信息至少包括姓名,__,地址至少包括对通讯录的创建,添加和按姓名查找等功能2假设人名为汉语拼音全拼形式,待插入哈希表的长度为你所在班级的人数哈希函数用除留余数法构造,采用链地址法或二次探测再散列法解决冲突3完成菜单设计操作有必要的提示
4.1需求分析
4.11程序所能达到的功能以人命的汉语拼音全拼形式查找你所在班级的人的信息(姓名,__,地址)
4.12输入的形式和输入的范围把人名都到转换成汉语拼音全拼的形式,人命最大长度不超过20个字符
4.2总体设计
4.21说明本程序中用到的所有抽象数据类型的定义该程序采用的是结构体类型来处理学生的所有基本信息,如下所述typedefstruct{/*用结构体类型来处理学生的所有基本信息*/NAname;/*NA为typedef定义的字符数组类型*/}Record;typedefstruct{/*哈希表*/Record*elem[HASHSIZE];//数据元素存储基址intcount;//当前存储的数据元素个数intsize;//当前容量,即表长}HashTable;
4.22说明主程序的流程
4.23说明各程序模块之间的层次(调用)关系各函数模块之间的调用关系主要是主函数调用主要功能函数,即输入与保存函数、哈希表建立函数、查找信息函数,主要功能函数也会调用一些基本功能函数完成相应功能,如CreateHash会调用Hash来求哈希地址,而Hash会调用fold对关键字先进行折叠处理,当地址冲突时,Hash又会调用collision解决冲突;SearchHash也会调用Hash、fold、collision以及eq并且主函数利用while循环使各个功能函数运行完毕后都会回到菜单,询问是否继续进行操作
4.3详细设计
4.31实现概要设计中定义的所有数据类型,对每个操作只需要写出伪码算法void__in{start=last=NULL;for;;/*无限循环*/{switchmenu_select/*调用主界面的选择函数,带回返回值*/{case1:enter;continue;case2:ddeletestartlast;continue;case3:list;continue;case4:search;continue;case5:s__e;continue;case6:load;continue;case7:exit0;}}}intmenu_selectvoid/*主目录*/{chars
[80];intc;printf………………^欢迎使用DOS通讯录系统^………………\n;printf************请在做其它操作前先导入*************\n;printf***********************************************\n;printf*****************
1.输入信息******************\n;printf*****************
2.删除信息******************\n;printf*****************
3.显示信息******************\n;printf*****************
4.查找******************\n;printf*****************
5.存盘******************\n;printf*****************
6.导入******************\n;printf*****************
7.退出******************\n;printf***********************************************\n;do{printf\nPleaseenteryourchoi__:\n;getss;c=atois;/*将获取的字符串转换成整型*/}whilec0||c7;returnc;/*返回输入值*/}
4.32对主程序和其它主要函数写出伪码算法structaddress*info;/*定义当前结点*/for;;{info=structaddress*__llocsizeofstructaddress;/*为当前结点分配空间*/if!info{printf\nOutofmemory;exit0;/*如果分配空间失败,退出程序*/}printf输入空姓名结束:\n;inputs请输入姓名:info-name10;if!info-name
[0]break;/*如果输入姓名为空,结束循环*/inputs请输入街道:info-street50;inputs请输入城市:info-city15;inputs请输入国家:info-state15;inputs请输入__:info-tel7;insertinfostartlast;/*调用结点插入函数*/}
4.4测试图4-1程序运行图图4-2输入信息图图4-3显示信息
4.5附录#includestdio.h#includestdlib.h#includestring.hstructaddress{/*定义结构*/charname
[10];charstreet
[50];charcity
[10];charstate
[15];chartel
[7];structaddress*next;/*后继指针*/structaddress*prior;/*前驱指针*/};structaddress*start;/*首结点*/structaddress*last;/*尾结点*/structaddress*findchar*;/*声明查找函数*/voidenter;/*函数声明*/voidsearch;voids__e;voidload;voidlist;voidddeletestructaddress**startstructaddress**last;voidinsertstructaddress*istructaddress**startstructaddress**last;voidinputschar*char*int;voiddisplaystructaddress*;intmenu_selectvoid;void__in{start=last=NULL;for;;{switchmenu_select{case1:enter;continue;case2:ddeletestartlast;continue;case3:list;continue;case4:search;continue;case5:s__e;continue;case6:load;continue;case7:exit0;}}}intmenu_selectvoid/*主目录*/{chars
[80];intc;printf………………^欢迎使用DOS通讯录系统^………………\n;printf************请在做其它操作前先导入*************\n;printf***********************************************\n;printf*****************
1.输入信息******************\n;printf*****************
2.删除信息******************\n;printf*****************
3.显示信息******************\n;printf*****************
4.查找******************\n;printf*****************
5.存盘******************\n;printf*****************
6.导入******************\n;printf*****************
7.退出******************\n;printf***********************************************\n;do{printf\nPleaseenteryourchoi__:\n;getss;c=atois;}whilec0||c7;returnc;/*返回输入值*/}voidenter/*输入函数本函数循环输入资料,当输入姓名为空时退出*/{structaddress*info;/*定义当前结点*/for;;{info=structaddress*__llocsizeofstructaddress;/*为当前结点分配空间*/if!info{printf\nOutofmemory;exit0;/*如果分配空间失败,退出程序*/}printf输入空姓名结束:\n;inputs请输入姓名:info-name10;if!info-name
[0]break;/*如果输入姓名为空,结束循环*/inputs请输入街道:info-street50;inputs请输入城市:info-city15;inputs请输入国家:info-state15;inputs请输入__:info-tel7;insertinfostartlast;/*调用结点插入函数*/}}voidinputschar*promptchar*sintcount/*输入函数,有越界检测功能*/{charp
[255];do{printfprompt;fgetsp254stdin;ifstrlenpcountprintf\nTooLong\n;}whilestrlenpcount;p[strlenp-1]=0;strcpysp;}voidinsert/*数据插入函数*/structaddress*istructaddress**startstructaddress**last{if*last==NULL/*如果尾结点为空意味着当前链表为空*/{i-next=NULL;i-prior=NULL;*last=i;*start=i;return;}else{*last-next=i;i-prior=*last;i-next=NULL;*last=*last-next;}}voidddeletestructaddress**startstructaddress**last/*删除函数*/{structaddress*info;chars
[80];inputs请输入姓名:s10;/*输入欲删除结点的name域内容*/info=finds;/*查找该内容*/ifinfo/*如果找到*/{printfDeleting......\n;if*start==info/*如果该结点为首结点把该结点的下驱作为新的首结点(入口)*/{*start=info-next;if*start*start-prior=NULL;else*last=NULL;}else/*如果欲删除的结点不是首结点*/{info-prior-next=info-next;/*令该结点的前驱的next指针指向该结点的后驱,*又令该结点的后驱的prior指点指向该结点的前驱*/ifinfo!=*last/*如果该结点是尾结点,则令该结点的前驱为尾结点*/info-next-prior=info-prior;else*last=info-prior;}freeinfo;/*释放该结点所占用的内存*/printf-Ok删除成功!\n;}}structaddress*findchar*name/*查找函数形参为欲查找结点的name域*/{structaddress*info;info=start;whileinfo{if!strcmpnameinfo-namereturninfo;info=info-next;}printf未找到相关信息.\n;returnNULL;}/*输出整个链表*/voidlistvoid{structaddress*info;info=start;ifinfo==NULLprintf当前记录为空!;elseprintf姓名\t街道\t\t城市\t国家\t__\t\n;whileinfo{displayinfo;ifinfo-next==NULL{break;}info=info-next;};printf\n\n;}voiddisplaystructaddress*info/*输出传入结点函数*/{printf%s\tinfo-name;printf%s\tinfo-street;printf%s\tinfo-city;printf%s\tinfo-state;printf%s\tinfo-tel;printf\n;}voidsearchvoid/*查找函数*/{charname
[40];structaddress*info;printf请输入要查找的姓名:;/*输入欲查找的姓名*/getsname;info=findname;if!infoprintf姓名不存在\n;/*如果没找到,显示Notfound*/elsedisplayinfo;/*如果找到,显示该结点资料*/}voids__evoid/*保存函数*/{structaddress*info;FILE*fp;fp=fopenrecord.___wb;/*生成文件*/if!fp{printfCannotopenfile.\n;return;}printf\nS__eing……\n;info=start;whileinfo/*把链表写入文件*/{fwriteinfosizeofstructaddress1fp;info=info-next;}printf-ok!\n;fclosefp;/*链表全部写入文件后,关闭文件*/}voidload/*调用预存文件函数*/{registerinttsize;structaddress*info*temp=0;char*p;FILE*fp;/*打开文件*/iffp=fopenrecord.___r==NULL{printfCannotopenfile!\n;return;}printf\n\nLoading...\n;/*调用文件*/size=sizeofstructaddress;/*为结点分配内存*/start=structaddress*__llocsize;if!start/*如果读取失败,返回*/{printfOutofmemory!\n;exit0;}info=start;p=char*info;while*p++=getcfp!=EOF{fort=0;tsize-1;++t*p++=getcfp;info-next=structaddress*__llocsize;if!info-next{printfOutofmemory!\n;return;}info-prior=temp;temp=info;info=info-next;p=char*info;}temp-next=0;last=temp;start-prior=0;fclosefp;printf-OK!\n;}5总结与展望通过一星期的数据结构与算法分析课程设计实习,我从中受益匪浅对数据结构程序设计这一门课程有了更深一步的认识,对一些细节语法有了更新、更深刻的理解,知其然,亦知其所以然尤其在程序调试过程中,程序的执行过程与语法相__,尽量__差错纠错,最后请教老师,对程序的优化设计和调试方法都有了很大的进步这次课程设计的进步是很大的,我了解到,我们需要将所学的理论知识和实践__起来,在实践设计中不断进步,不断熟练,光是读透书本知识是不够的虽然我对一些C语言知识运用得还不是很熟练,但是我相信在接下来的学习过程中,我会有更大的进步,还有很大的空间可以发挥在这次课程设计中,我做的是课题10,建立27人的通讯录,设计散列表实现通讯录查找系统,并完成相应的建表和查表程序其中运用了很多方面的知识如,运用结构体建通讯录,保存信息构建哈希表,用除留余数法构造哈希函数,采用二次探测再散列法解决冲突,对关键字的折叠处理等等可以看出,一个简单设计的完成,需要很多方面的知识来共同完成,每方面的知识都要理解透彻,运用熟练,其实我们需要在平日里打好基础而且,要会用其他算法或其他数据结构来优化算法,这对知识运用的灵活性掌握有很高的要求所以,通过一次短短的课程设计就可以看出,我们需要学习的还很多,掌握的知识也不够透彻明白总之,这次课程设计,让我看到很多不足,为我今后的学习指出了新的学习方向,这是我最大的收获____
[1]严蔚敏,吴伟民《数据结构》清华大学计算机系列教材北京清华大学出版社,2007
[2]陈锐《零基础学数据结构》北京机械工业出版社,2010]谭浩强《C程序设计(第三版)》北京清华大学出版社,2005成绩评定成绩教师签字__inmenu_selectenterddeletelistsearchs__es__eloadexitinputsinsertfinddisplay文件函数之间的相互调用。