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

计算机软件基础,第二篇数据结构基础,第十二章常用的查找方法,一、设监视哨的顺序查找,1.查找思路,将n个数据存入一维数组的A1n区域中；A0作为监视哨，存放要查找的给定值K。整个查找过程从最后一个数据An开始，向前依次与K比较，直至A1。结论：如果与K都不相等，则查找失败，返回0；否则，查找成功，返回数据的下标位置。,一、设监视哨的顺序查找,2.算法流程,一、设监视哨的顺序查找,3.程序示例,#defineN6intseek(intx,intk)inti=N;x0=k;while(xi!=k)i-;if(i=0)return(0);elsereturn(i);main()intaN+1,i,w,k;for(i=1;i=N;i+)scanf(%d,二、折半查找,1.实施折半查找先决条件,（1）待查序列必须顺序存储；,（2）待查序列按按关键词有序排列。,二、折半查找,2.折半查找的思路,将要查找的数据和“中间位置”数据进行比较，如果相等，则查找成功；如果小于“中间位置”数据，则在前半部分按上述方法进行查找；否则，在后半部分按上述方法进行查找。,二、折半查找,3.算法流程,二、折半查找,3.程序示例,#defineN7inthalffind(intx,intk)intlow=1,high=N,mid;while(lowxmid)low=mid+1;return(0);main()intaN,i,k;for(i=1;i=N;i+)scanf(%d,三、折半查找判定树,1.折半查找判定树：用来描述折半查找过程的判定树。,2.折半查找判定树特点：,（1）树中每个节点对应待查序列中的一个数据；,（2）节点值为所对应数据的下标序号；,（3）根节点是待查序列中间数据的下标位置序号mid；,（4）左子树为mid位置左边节点的下标位置序号；,（5）右子树为mid位置右边节点的下标位置序号；,三、折半查找判定树,例：求待查数据序列为2、5、9、13、18、26、32的折半查找判定树。,解：,折半查找判定树为：,4,2,6,1,3,5,7,2,9,5,13,26,18,32,三、折半查找判定树,3.折半查找判定树的意义：,（1）待查节点在判定树中的层数为该节点折半查找成功的比较次数；,（2）折半查找的过程恰好走了一条从根节点到被查节点的路径。查找过程中进行比较的节点为该路径上的所有节点；,（3）假设每个数据查找的概率相等，则折半查找成功的平均查找次数为：,（4）不成功的查找次数不超过树的高度。,三、折半查找判定树,例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）不成功的查找次数不超过树的高度。,关键点：构建折半查找判定树。,四、二叉排序树上的查找,1.二叉排序树：满足以下条件的二叉树。,条件：,（1）树中的每个节点值是待查序列中的各个数（不是位置序号）。,（2）如果树中节点的左、右子树非空，那么该节点值大于它左子树上所有节点值，而小于或等于它右子树上的所有节点值。,四、二叉排序树上的查找,2.根据已知序列构造二叉排序树的方法,step1:取给定序列中的第一个数作为根节点；,step2:依次将给定序列中剩余的各个数加入到该根的二叉树中。,注意：,（1）每加入一个数，应从根开始逐层比较，使其符合二叉排序树的定义；,（2）每加入一个数，不得破坏已形成的树形。,四、二叉排序树上的查找,例：（2009.4）已知关键字序列为46,57,84,32,73,36，15,48,90,20，要求：,（1）按照给定关键字的先后次序构造一颗二叉排序树；,（2）在等概率的情况下