中南大学数据结构实验报告(六)

中南大学数据结构试验报告题目实验六学生姓名王云鹏学号8213180228指导老师郑瑾学院计算机学院专业班级物联网1802完成时间2020.6指导老师评定签名实验六1.需求分析2．二分查找算法（设计性实验）问题描述从键盘读入一串整数和一个待查键，查找在该整数串中是否有这个待查键。如果有，就输出它在整数串中的位置；如果没有，输出1。基本要求掌握二分查找算法。测试数据由读者依据软件工程的测试技术自己确定。注意测试边界数据，如单个结点。实现提示利用二分查找算法查找实现。4．简单个人电话号码查询系统（综合性实验）问题描述人们在日常生活中经常要查找某个人或某个单位的电话号码，本实验将实现一个简单的个人电话号码查询系统，根据用户输入的信息（如姓名等）进行快速查询。基本要求(1)在外存上，用文件保存电话号码信息。(2)在内存中，设计数据结构存储电话号码信息。(3)提供查询功能：根据姓名实现快速查询。(4)提供其他维护功能，如插入、删除、修改等。测试数据由读者依据软件工程的测试技术自己确定。注意测试边界数据，如单个结点。实现提示由于要管理的电话号码信息较多，而且要在程序运行结束后仍然保存电话号码信息，所以电话号码信息采用文件的形式存放到外存中。在系统运行时，要将电话号码信息从文件调入内存来进行查找等操作。为了接收文件中的内容，要有一个数据结构与之对应，可以设计如下结构类型的数组来接收数据。constintmax＝10;structTeleNumber｛Stringname;//姓名StringphoneNumber,//固定电话号码StringmobileNumber,//移动电话号码Stringemail;//电子邮箱｝Tele[max];为了实现对电话号码的快速查询，可以将上述结构数组排序，以便应用二分查找，但是，在数组中实现插入和删除操作的代价较高。如果记录需频繁进行插入或删除操作，可以考虑采用二叉排序树组织电话号码信息，这样查找和维护都能获得较高的时间性能。更复杂地，需考虑该二叉排序树是否平衡，如何使之达到平衡。2.概要设计设计性实验函数：综合性实验函数：3.详细设计设计性实验#includeiostreamusingnamespacestd;typedefintKeyType;//数据类型typedefstruct{KeyTypekey;}ElemType,TElemType;//数组中数据类型typedefstruct{ElemType*elem;//数组intlength;//数组中元素个数}SSTable;//存放二分查找的数据类型intsearch_bin(SSTableST,KeyTypekval){//二分查找intlow=0;inthigh=ST.length;while(low=high){//不断二分intmid=(low+high)/2;if(kval==ST.elem[mid].key){//找到返回位置returnmid;}elseif(kvalST.elem[mid].key){//没找到缩小范围继续寻找high=mid-1;}else{low=mid+1;}}return-1;}intmain(){//测试SSTableST;intlength;intkval;cout输入将要输入的数字个数endl;//输入数据，初始化要查找的数组cinlength;ST.length=length;ST.elem=(ElemType*)malloc(length*sizeof(ElemType));cout输入数字序列endl;for(inti=0;ilength;i++){cinST.elem[i].key;}cout输入要查找的数字endl;cinkval;if(search_bin(ST,kval)!=-1){cout要查找的数字位于第search_bin(ST,kval)+1个endl;}else{cout要查找的数字不存在endl;}return0;}#includeiostream#includefstream#includecstringusingnamespacestd;typedefstruct{stringname;stringphoneNumber;stringmobileNumber;stringemail;}Tele;//存放信息的结构体constintTele_size_max=10;Telet[Tele_size_max];//Tele数组intTele_size=0;voidstore_tele_to_file(Telet[])//将Tele[]存入文件{ofstreamoutfile;outfile.open(./Tele_info.txt,ios::out);//打开文件for(inti=0;iTele_size;i++)//向文件写入数据{outfilet[i].namet[i].phoneNumbert[i].mobileNumbert[i].emailendl;}outfile.close();//关闭文件cout写入成功endl;}voidextract_tele_from_file(Telet[])//从文件中提取Tele{ifstreaminfile;infile.open(./Tele_info.txt,ios::in);//打开文件while(!infile.eof()){//从文件中读出数据infilet[Tele_size].namet[Tele_size].phoneNumbert[Tele_size].mobileNumbert[Tele_size].email;Tele_size++;}infile.close();//关闭文件cout导入成功endl;}intinquire_tele_index(Telet[],stringname)//从Tele[]中根据姓名查询Tele所在下标，返回位置{for(inti=0;iTele_size;i++){if(name.compare(t[i].name)==0){returni;}}coutfailtofindnameendl;return-1;//查找失败返回-1}Teleinquire_tele(Telet[],stringname)//从Tele[]中根据姓名查询Tele，返回查到的结构体{returnt[inquire_tele_index(t,name)];}voidinsert_tele(Telet[],Teletemp)//将temp插入Tele[]中{t[Tele_size++]=temp;}voiddelete_tele(Telet[],stringname)//从Tele[]中根据姓名删除对应Tele{for(inti=inquire_tele_index(t,name)+1;i=Tele_size;i++){//后面前挪覆盖t[i-1]=t[i];}//memset(&t[Tele_size-1],0,sizeof(Tele));Tele_size--;}voidmodi_tele(Telet[],intchoice,stringname,stringinfo){//根据choice和提供的name选择性修改Tele中的某项内容,choice:1、name2、phoneNumber3、mobileNumber4、emailswitch(choice)//根据choice选择功能{case1:t[inquire_tele_index(t,name)].name=info;break;case2:t[inquire_tele_index(t,name)].phoneNumber=info;break;case3:t[inquire_tele_index(t,name)].mobileNumber=info;break;case4:t[inquire_tele_index(t,name)].email=info;break;default:coutillegalchoiceendl;break;}}voidprint_tele(Telet)//打印结构体{coutt.namet.phoneNumbert.mobileNumbert.emailendl;}voidprint_teles(Telet[])//打印结构体数组{coutTele数组中的内容为：endl;for(inti=0;iTele_size;i++)//遍历{print_tele(t[i]);}}intmain()//测试{//插入Teletemp1={小刚,111,222,333};insert_tele(t,temp1);print_teles(t);Teletemp2={小明,444,555,666};insert_tele(t,temp2);print_teles(t);//查询cout以temp1.name为名的查询结果为：endl;print_tele(inquire_tele(t,temp1.name));//删除cout删除后还剩：endl;delete_tele(t,temp1.name);print_teles(t);//修改cout修改结果：endl;综合性实验4.调试分析1)采用IDE中自带的调试功能进行调试，手动添加断点和查看程序。2)对设计和编码的讨论和分析。该程序实现了顺序栈的操作。分析程序代码的质量，主要从以下几个方面考虑。·正确性。在一定的数据范围内，该程序能实现所需功能，所以正确性是没有问题的。·健壮性。在一定的数据输入范围内，该程序能较好的实现操作。但是如果输入数据非法，该程序还是可能会产生一些预想不到的输出结构，或是不做任何处理。所以，该程序的健壮性有待进一步的提高。要综合考虑一些情况，当输入有误时，应返回一个表示错误的值，并中止程序的执行，以便在更高的抽象层次上进行处理。5.使用说明按照屏幕提示，选择想要的功能并输入对应数字，按下ENTER键后，根据屏幕提示进行输入，即可得到想要的结果。6.测试程序运行结果设计性实验综合性实验modi_tele(t,4,temp2.name,777);print_teles(t);//存入文件store_tele_to_file(t);cout删除后还剩：endl;delete_tele(t,temp2.name);print_teles(t);//从文件读出extract_tele_from_file(t);print_teles(t);return0;}7.心得体会通过本次实验，使我对数据结构有了更深的理解，对指针的运用更加熟练，熟悉了对函数的定义和操作。