实验五-查找和排序实验报告

1实验五查找和排序1、实验目的1.掌握顺序查找的基本方法2.掌握简单排序和二分法查找的算法。2．能运用线性表的查找方法解决实际问题。2、实验内容1、给出在一个无序表A，采用顺序查找算法查找值为x的元素的算法2、给出一个无序表B，采用简单排序方法使该表递增有序，并采用二分查找算法查找值为x的元素的算法。3、实验步骤（1）仔细分析实验内容，给出其算法和流程图；（2）用C语言实现该算法；（3）给出测试数据，并分析其结果；（4）在实验报告册上写出实验过程。4、实验报告要求实验报告要求书写整齐，步骤完整，实验报告格式如下：1、［实验目的］2、［实验设备］3、［实验步骤］4、［实验内容］5、［实验结果(结论)］21.折半查找算法描述如下：intSearch_Bin(SSTableST,KeyTypekey)low=1;high=ST.length;while(low=high){mid=(low+high)/2;ifEQ(key,ST.elem[mid].key)returnmid;elseifLT(key,ST.elem[mid].key)high=mid-1;elselow=mid+1;}return0;}//Search_Bin;2.顺序查找算法描述如下：typedefstruct{ElemType*elem;intlength;}SSTable;顺序查找：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，查找不成功。intSearch_Seq(SSTableST,KeyTypekey){ST.elme[0].key=key;for(i=ST.length;!EQ(ST.elem[i].key,key);--i);returni;}(3)写出源程序清单（加适当的注释）。#includestdio.htypedefstructBiTNode{intdata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;voidinsert(BiTree*bt,BiTrees){//在二叉树中插入一个新节点,并将较大数至于右子树,较小数至于左子树if(*bt==NULL)*bt=s;elseif(s-data=(*bt)-data)insert(&((*bt)-lchild),s);elseif(s-data(*bt)-data)insert(&((*bt)-rchild),s);}voidZXBL(BiTreebt){//中序遍历,二叉树已排好顺序if(bt!=NULL){ZXBL(bt-lchild);printf(%5d,bt-data);ZXBL(bt-rchild);}}voidmain(){charch;intkey;BiTrees,bt=NULL;inti=0;//建立一个二叉树，元素从键盘输入，直到回车为止printf(\n请输入要一列整数,以空格隔开,回车结束.\n);while(ch!='\n'){scanf(%d,&key);s=(BiTree)malloc(sizeof(BiTNode));s-data=key;s-lchild=s-rchild=NULL;insert(&bt,s);ch=getchar();}printf(\n排序后:\n);ZXBL(bt);//中序遍历while(1){printf(\n输入你要查找的关键字:);3BiTreeselect(BiTreebt,intkey)//在二叉排序树bt中查找关键字等于给定值的结点是否存在{if(bt==NULL)returnNULL;elseif(bt-data==key)returnbt;elseif(keybt-data)returnselect(bt-lchild,key);elsereturnselect(bt-rchild,key);}scanf(%d,&key);s=select(bt,key);if(s!=NULL)printf(%d查找成功!,s-data);elseprintf(未发现你输入的数!);printf(\n再次查找?(Y/N):);ch=getch();if(ch!='y'&&ch!='Y')return0;}}(4)调试说明。包括上机调试的情况、调试所遇到的问题是如何解决的，并对调试过程中的问题进行分析，对执行结果进行分析。1,问题:malloc无法识别.解决:百度得知缺少头文件,导入stdlib.h后解决.2,问题:输入后程序无响应.解决:scanf中缺少&,添加后解决.3,问题:结果显示不正确,为ASCII码解决:输出改为”%c”.(5)测试结果及说明。对完成所要执行的功能情况分析。（1）（2）五．实验体会：通过本次排序和查找的练习，初步掌握了其基本概念和操作。查找的基本概念：查找表：是由同一类型的数据元素（或记录）构成的集合。查找表的操作：1、查询某个“特定的”数据元素是否在查找表中。2、检索某个“特定的”数据元素的各种属性。43、在查找表中插入一个数据元素；4、从查找表中刪去某个数据元素。排序：将一个数据元素的无序序列重新排列成一个按关键字有序的序列。内部排序：待排序记录存放在计算机随机存储器中进行的排序过程；外部排序：待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。