数据结构中查找和排序算法的实验报告

第页，共页延安大学计算机学院试验报告纸附页姓名班级试验名称三．实验分析与步骤：1.折半查找分析：有序表表示静态查找表时，Search函数可用折半查找来实现。先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。2.顺序查找分析：查找操作的性能分析：查找算法中的基本操作是将记录的关键字和给定值进行比较，，通常以“其关键字和给定值进行过比较的记录个数的平均值”作为衡量依据。平均查找长度：为确定记录在查找表中的位置，需用和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度。其中：Pi为查找表中第i个记录的概率，且；Ci为找到表中其关键字与给定值相等的第i个记录时，和给定值已进行过比较的关键字个数。等概率条件下有：假设查找成功与不成功的概率相同：3.归并排序分析：第页，共页将两个或两个以上的有序表组合成一个新的有序表的方法叫归并。假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，如此重复。4.堆排序分析:只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。什么是堆？n个元素的序列{k1,k2,...,kn}当且仅当满足下列关系时，称之为堆。关系一：ki=k2i关系二：ki=k2i+1（i=1,2,...,n/2)堆排序要解决两个问题：1、如何由一个无序序列建成一个堆？2、如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？问题2的解决方法：四．实验数据与清单：1.折半查找算法描述如下：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.归并排序算法描述如下：merge(ListTyper,intl,intm,intn,ListType&r2){i=l;j=m+1;k=l-1;while(i=m)and(jn)do{k=k+1;if(r[i].key=r[j].key){r2[k]=r[i];i++;}else{r2[i]=r[j];j++}}if(i=m)r2[k+1..n]=r[i..m];if(j=n)r2[k+1..n]=r[j..n];}mergesort(ListType&r,ListType&r1,ints,intt){if(s==t)r1[s]=r[s];else{mergesort(r,r2,s,s+t/2);mergesort(r,r2,s+t/2+1,t);merge(r2,s,s+t/2,t,r1);}}4.堆排序算法描述如下：sift(ListType&r,intk,intm){i=k;j=2*i;x=r[k].key;finished=FALSE;t=r[k];第页，共页while((j=m)&&(!finished)){if((jm)&&(r[j].keyr[j+1].key))j++;if(x=r[j].key)finished:=TRUE;else{r[i]=r[j];i=j;j=2*i;}}r[i]=t;}HeapSort(ListType&r){for(i=n/2;i0;i--)sift(r,i,n);for(i=n;i1;i--){r[1]-r[i];sift(r,i,i-1)}}五．实验体会：通过本次排序和查找的练习，初步掌握了其基本概念和操作。查找的基本概念：查找表：是由同一类型的数据元素（或记录）构成的集合。查找表的操作：1、查询某个“特定的”数据元素是否在查找表中。2、检索某个“特定的”数据元素的各种属性。3、在查找表中插入一个数据元素；4、从查找表中刪去某个数据元素。排序：将一个数据元素的无序序列重新排列成一个按关键字有序的序列。内部排序：待排序记录存放在计算机随机存储器中进行的排序过程；外部排序：待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。