数据结构实验报告-查找算法.doc

数据结构第八次实验报告学生姓名学生班级学生学号指导老师重庆邮电大学计算机学院计算机专业实验中心1、 实验内容1) 有序表的二分查找 建立有序表，然后进行二分查找 2) 二叉排序树的查找 建立二叉排序树，然后查找 2、 需求分析二分查找的基本思想是将n个元素分成大致相等的两部分，取an/2与x做比较，如果x=an/2,则找到x,算法中止；如果xan/2,则只要在数组a的右半部搜索x.时间复杂度无非就是while循环的次数！总共有n个元素，渐渐跟下去就是n,n/2,n/4,.n/2k（接下来操作元素的剩余个数），其中k就是循环的次数由于你n/2k取整后=1即令n/2k=1可得k=log2n,（是以2为底，n的对数）所以时间复杂度可以表示O()=O(logn)下面提供一段二分查找实现的伪代码:BinarySearch(max,min,des)mid-(max+min)/2while(mindes thenmax=mid-1elsemin=mid+1return max折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取an/2与欲查找的x作比较，如果x=an/2则找到x，算法终止。如 果xan/2，则我们只要在数组a的右 半部继续搜索x。3、 概要设计 1、顺序查找，在顺序表R0.n-1中查找关键字为k的记录，成功时返回找到的记录位置，失败时返回-1，具体的算法如下所示：int SeqSearch(SeqList R,int n,KeyType k)int i=0;while(i=n)return -1;else printf(%d,Ri.key);return i;2、二分查找，在有序表R0.n-1中进行二分查找，成功时返回记录的位置，失败时返回-1，具体的算法如下：int BinSearch(SeqList R,int n,KeyType k)int low=0,high=n-1,mid,count=0;while(lowk)high=mid-1;elselow=mid+1;return -1; 四、详细设计源代码：#include#includestatic int a1024,count=0;void Find1(int low,int high,int x) int mid; if(lowx)Find1(low,mid-1,x); else if(amidx)Find1(mid+1,high,x); else printf(n查找到?元a素?位?置?为a%d，?查找次?数簓为a%d。,mid,count); else printf(n查找失骸?败悒?，?查找次?数簓为a%d。,count); void Find2(int low,int high,int x) int mid; if(low=high) mid=(low+high)/2; count+; if(amidx)Find2(mid+1,high,x); else printf(n查找到?元a素?位?置?为a%d，?查找次?数簓为a%d。,mid,count); else printf(n查找失骸?败悒?，?查找次?数簓为a%d。,count); int main() int n,x; printf(请?输?入?元a素?个?数簓:); scanf(%d,&n); printf(n请?按恪?从洙?高?到?低台?或从洙?低台?到?高?顺3序输?入?各元a素?(以?空?格?隔?开a):nn); for(int i=1;i=n;i+) scanf(%d,&ai); printf(n请?输?入?要癮查找的?元a素?：阰); scanf(%d,&x); if(a1=an)Find1(1,n,x); else Find2(1,n,x); printf(nn); system(pause); 五、心得体会通过这次在实现顺序和二分查找算法的过程中，让我对顺序和二分查找算法有了更多的了解。查找根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）的操作，应用十分广泛。顺序查找是一种最简单的查找方法。它的基本思路是：从表的一端开始,顺序扫描线性表,依次将扫描到的关键字和给定值k相比较,若当前扫描到的关键字与k相等,则查找成功；若扫描结束后,仍未找到关键字等于k的记录,则查找失败。二分查找也称为折半查找要求线性表中的结点必须己按关键字值的递增或递减顺序排列。它首先用要查找的关键字k与中间位置的结点的关键字相比较,这个中间结点把线性表分成了两个子表,若比较结果相等则查找完成