哈希表制作通讯录 数据结构程序设计

软件学院课程设计报告书课程名称数据结构设计题目哈希表制作通讯录专业班级学号姓名指导教师2014年1月目录1设计时间.....................................................12设计目的.....................................................13设计任务.....................................................14设计内容.....................................................14.1需求分析................................................14.11程序所能达到的功能..................................14.12输入的形式和输入的范围..............................14.2总体设计................................................14.21说明本程序中用到的所有抽象数据类型的定义.............14.22说明主程序的流程....................................24.23说明各程序模块之间的层次（调用）关系.................24.3详细设计................................................34.31实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法.................................................34.32对主程序和其它主要函数写出伪码算法..................44.4测试....................................................54.5附录....................................................65总结与展望..................................................16参考文献......................................................17成绩评定......................................................1811设计时间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说明本程序中用到的所有抽象数据类型的定义该程序采用的是结构体类型来处理学生的所有基本信息，如下所述。2typedefstruct{/*用结构体类型来处理学生的所有基本信息*/NAname;/*NA为typedef定义的字符数组类型*/}Record;typedefstruct{/*哈希表*/Record*elem[HASHSIZE];//数据元素存储基址intcount;//当前存储的数据元素个数intsize;//当前容量，即表长}HashTable;4.22说明主程序的流程4.23说明各程序模块之间的层次（调用）关系mainmenu_selectenterddeletelistsearchsavesaveloadexitinputsinsertfinddisplay文件函数之间的相互调用3各函数模块之间的调用关系主要是主函数调用主要功能函数，即：输入与保存函数、哈希表建立函数、查找信息函数，主要功能函数也会调用一些基本功能函数完成相应功能，如：CreateHash()会调用Hash()来求哈希地址，而Hash()会调用fold()对关键字先进行折叠处理，当地址冲突时，Hash()又会调用collision()解决冲突；SearchHash()也会调用Hash()、fold()、collision()以及eq()。并且主函数利用while循环使各个功能函数运行完毕后都会回到菜单，询问是否继续进行操作。4.3详细设计4.31实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法voidmain(){start=last=NULL;for(;;)/*无限循环*/{switch(menu_select())/*调用主界面的选择函数，带回返回值*/{case1:enter();continue;case2:ddelete(&start,&last);continue;case3:list();continue;case4:search();continue;case5:save();continue;case6:load();continue;case7:exit(0);}}}intmenu_select(void)/*主目录*/{chars[80];intc;printf(………………^欢迎使用DOS通讯录系统^………………\n);printf(************请在做其它操作前先导入*************\n);4printf(***********************************************\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(\nPleaseenteryourchoice:\n);gets(s);c=atoi(s);/*将获取的字符串转换成整型*/}while(c0||c7);returnc;/*返回输入值*/}4.32对主程序和其它主要函数写出伪码算法structaddress*info;/*定义当前结点*/for(;;){info=(structaddress*)malloc(sizeof(structaddress));/*为当前结点分配空间*/if(!info){printf(\nOutofmemory);exit(0);/*如果分配空间失败，退出程序*/}printf(输入空姓名结束:\n);inputs(请输入姓名:,info-name,10);if(!info-name[0])break;/*如果输入姓名为空，结束循环*/inputs(请输入街道:,info-street,50);inputs(请输入城市:,info-city,15);inputs(请输入国家:,info-state,15);inputs(请输入电话:,info-tel,7);insert(info,&start,&last);/*调用结点插入函数*/}54.4测试图4-1程序运行图图4-2输入信息图6图4-3显示信息4.5附录#includestdio.h#includestdlib.h#includestring.hstructaddress{/*定义结构*/charname[10];charstreet[50];charcity[10];charstate[15];chartel[7];structaddress*next;/*后继指针*/structaddress*prior;/*前驱指针*/};7structaddress*start;/*首结点*/structaddress*last;/*尾结点*/structaddress*find(char*);/*声明查找函数*/voidenter();/*函数声明*/voidsearch();voidsave();voidload();voidlist();voidddelete(structaddress**start,structaddress**last);voidinsert(structaddress*i,structaddress**start,structaddress**last);voidinputs(char*,char*,int);voiddisplay(structaddress*);intmenu_select(void);voidmain(){start=last=NULL;for(;;){switch(menu_select()){case1:enter();continue;case2:ddelete(&start,&last);continue;case3:list();8continue;case4:search();continue;case5:save();continue;case6:load();continue;case7:exit(0);}}}intmenu_select(void)/*主目录*/{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(\nPleaseenteryourch