计算机软件基础(自考本科)(1.12)

桂林电子科技大学GUILINUNIVERSITYOFELECTRONICTECHNOLOGY计算机软件基础第二篇数据结构基础第十二章常用的查找方法桂林电子科技大学GUILINUNIVERSITYOFELECTRONICTECHNOLOGY一、设监视哨的顺序查找1.查找思路将n个数据存入一维数组的A[1…n]区域中；A[0]作为监视哨，存放要查找的给定值K。整个查找过程从最后一个数据A[n]开始，向前依次与K比较，直至A[1]。结论：如果与K都不相等，则查找失败，返回0；否则，查找成功，返回数据的下标位置。桂林电子科技大学GUILINUNIVERSITYOFELECTRONICTECHNOLOGY一、设监视哨的顺序查找2.算法流程A[0]=K开始NYYNi=nA[i]=K?i=0?没找到返回0结束找到返回ii--桂林电子科技大学GUILINUNIVERSITYOFELECTRONICTECHNOLOGY一、设监视哨的顺序查找3.程序示例#defineN6intseqfind(intx[],intk){inti=N;x[0]=k;while(x[i]!=k)i--;if(i==0)return(0);elsereturn(i);}main(){inta[N+1],i,functionV,k;for(i=1;i=N;i++)scanf(%d,&a[i]);scanf(%d,&k);functionV=seqfind(a,k);printf(%d\n,functionV);}桂林电子科技大学GUILINUNIVERSITYOFELECTRONICTECHNOLOGY二、折半查找1.实施折半查找先决条件（1）待查数据必须顺序存储；（2）待查数据按升序或降序排列。桂林电子科技大学GUILINUNIVERSITYOFELECTRONICTECHNOLOGY二、折半查找2.折半查找的思路将要查找的数据和“中间位置”数据进行比较，如果相等，则查找成功；如果小于“中间位置”数据，则在前半部分按上述方法进行查找；否则，在后半部分按上述方法进行查找。桂林电子科技大学GUILINUNIVERSITYOFELECTRONICTECHNOLOGY二、折半查找3.算法流程Y开始low=1,high=nlow≤high结束2highlowmidk=mid?high=mid-1low=mid+1查找成功返回mid查找失败N大于小于等于桂林电子科技大学GUILINUNIVERSITYOFELECTRONICTECHNOLOGY二、折半查找3.程序示例#defineN7inthalffind(intx[],intk){intlow=1，high=N，mid;while(low=high){mid=(low+high)/2;if(k==x[mid])return(mid);elseif(kx[mid])high=mid-1;else(kx[mid])low=mid+1;}return(0);}main(){inta[N],i,functionV,k;for(i=1;i=N;i++)scanf(%d,&a[i]);scanf(%d,&k);functionV=halffind(a,k);printf(%d\n,functionV);}桂林电子科技大学GUILINUNIVERSITYOFELECTRONICTECHNOLOGY三、折半查找判定树1.折半查找判定树：用来描述折半查找过程的判定树。2.折半查找判定树特点：（1）树中每个节点对应待查序列中的一个数据；（2）节点值为所对应数据的下标序号；（3）根节点是待查序列中间数据的下标位置序号mid；（4）左子树为mid位置左边节点的下标位置序号；（5）右子树为mid位置右边节点的下标位置序号；桂林电子科技大学GUILINUNIVERSITYOFELECTRONICTECHNOLOGY三、折半查找判定树例：求待查数据序列为2、5、9、13、18、26、32的折半查找判定树。解：数据序列25913182632位置序号1234567折半查找判定树为：4261357桂林电子科技大学GUILINUNIVERSITYOFELECTRONICTECHNOLOGY三、折半查找判定树3.折半查找判定树的意义：（1）待查节点在判定树中的层数为该节点折半查找成功的比较次数；（2）折半查找的过程恰好走了一条从根节点到被查节点的路径。查找过程中进行比较的节点为该路径上的所有节点；（3）假设每个数据查找的概率相等，则折半查找成功的平均查找次数为：（4）不成功的查找次数不超过树的高度。节点个数（总数）各节点所在判定中树数节点个数（总数）各节点成功的查找次数ASL桂林电子科技大学GUILINUNIVERSITYOFELECTRONICTECHNOLOGY三、折半查找判定树例1：（2010.4）对100个有序数据，若采用二分法查找某一个元素，比较次数最多的是（）。A.6B.7C.8D.100例2：（2009.4）已知一个有序表{1,4,9,13,32,41,54,62,75，77,87,95,100}，用折半法查找关键字值15时，查找不成功的比较次数是——————————。知识点：1）待查节点在判定树中的层数为该节点折半查找成功的比较数；2）不成功的查找次数不超过树的高度。关键点：构建折半查找判定树。桂林电子科技大学GUILINUNIVERSITYOFELECTRONICTECHNOLOGY四、二叉排序树上的查找1.二叉排序树：满足以下条件的二叉树。条件：（1）树中的每个节点值是待查序列中的各个数（不是位置序号）。（2）如果树中节点的左、右子树非空，那么该节点值大于它左子树上所有节点值，而小于或等于它右子树上的所有节点值。桂林电子科技大学GUILINUNIVERSITYOFELECTRONICTECHNOLOGY四、二叉排序树上的查找2.根据已知序列构造二叉排序树的方法step1:取给定序列中的第一个数作为根节点；step2:依次将给定序列中剩余的各个数加入到该根的二叉树中。注意：（1）每加入一个数，应从根开始逐层比较，使其符合二叉排序树的定义；（2）每加入一个数，不得破坏已形成的树形。桂林电子科技大学GUILINUNIVERSITYOFELECTRONICTECHNOLOGY四、二叉排序树上的查找例：（2009.4）已知关键字序列为{46,57,84,32,73,36，15,48,90,20}，要求：（1）按照给定关键字的先后次序构造一颗二叉排序树；（2）在等概率的情况下，计算已构造的二叉排序树查找成功的平均查找次数（ASL）。4632571536488473902010291034432211ASL桂林电子科技大学GUILINUNIVERSITYOFELECTRONICTECHNOLOGY四、二叉排序树上的查找3.二叉排序树上的查找在二叉排序树上的查找与有序序列的折半查找相类似，结论也相类似。