数据结构答案第9章查找学习与指导

83第9章查找9.1知识点分析1.基本概念（1）查找表由同一类型的数据元素（或记录）构成的集合称为查找表。（2）静态查找在查找过程中仅查找某个特定元素是否存在或它的属性的，称为静态查找。（3）动态查找在查找过程中对查找表进行插入元素或删除元素操作的，称为动态查找。（4）关键字关键字是数据元素（或记录）中某个数据项的值，用它可以标识数据元素（或记录）。关键字分主关键字（唯一地标识一个记录的关键字）和次关键字（标识若干个记录的关键字）。（5）查找在查找表中确定是否存在一个数据元素的关键字等于给定值的操作，称为查找（也称为检索）。（6）内查找、外查找整个查找过程全部在内存进行，则称为内查找；若在查找过程中还需要访问外存，则称为外查找。（7）平均查找长度ASL查找成功时平均查找长度：其中：Pi为找到表中第i个数据元素的概率，且有：Ci为查找表中第i个数据元素所用到的比较次数。不同的查找方法有不同的Ci。2．顺序查找顺序查找又称线性查找，是最基本的查找方法之一。顺序查找既适用于顺序表，也适用于链表。顺序查找的基本思想：从表的一端开始，顺序扫描线性表，依次按给定值kx与关键字（Key）进行比较，若相等，则查找成功，并给出数据元素在表中的位置；若整个表查找完毕，仍未找到与kx相同的关键字，则查找失败，给出失败信息。3．二分查找二分查找也叫折半查找，是一种效率较高的查找方法，但前提是表中元素必须按关键字有序（按关键字递增或递减）排列。二分查找的基本思想：在有序表中，取中间元素作为比较对象，若给定值与中间元素的关键字相等，则查找成功；若给定值小于中间元素的关键字，则在中间元素的左半区继续查找；若给定值大于中间元素的关键字，则在中间元素的右半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，查找失败。4．分块查找将具有n个元素的主表分成m个块（也称为子表），每块内的元素可以无序，但要求块niiiCPASL111niiP84与块之间必须有序，并建立索引表。索引表包括两个字段：关键字字段(存放对应块中的最大关键字值)和指针字段(存放指向对应块的首地址)。查找方法如下：（1）在索引表中检测关键字字段，以确定待找值kx所处的分块（可用二分查找）位置；（2）根据索引表指示的首地址，在该块内进行顺序查找。5．二叉排序树（BinarySortTree）二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于根结点的值；（3）左右子树也都是二叉排序树。6．平衡二叉树(AVL树)所谓平衡二叉树是指树中任一结点的左、右子树高度大致相等的二叉树。平衡二叉树（AVL树）定义如下：平衡二叉树或者是一棵空树，或者是具有以下性质的二叉排序树：（1）它的左子树和右子树的高度之差（称为平衡因子）的绝对值不超过1；（2）它的左子树和右子树又都是平衡二叉树。7．哈希表选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放。查找时，由同一个函数对给定值kx计算地址，将kx与地址单元中元素关键字进行比，确定查找是否成功，这就是哈希方法。哈希方法中使用的转换函数称为哈希函数，按这个思想构造的表称为哈希表。9.2典型习题分析【例1】静态查找和动态查找两者的根本区别在于（）。A．逻辑结构不同B．存储实现不同C．施加的操作不同D．数据元素类型不同分析：根据施加不同运算，查找分为静态查找和动态查找两类，静态查找仅包含检索操作，而动态查找不仅包含检索操作，还允许增加元素和删除元素等操作。所以是施加的操作不同，选择C。【例2】顺序查找法与二分查找法对存储结构的要求是()。A．顺序查找与二分查找均只适用于顺序表B．顺序查找只适用于顺序表C．顺序查找与二分查找既适用于顺序表，也适用于链表D．二分查找只适用于顺序表分析：由第1题知道顺序查找比较适用于顺序表和链表。故A和B不对。二分查找表中元素必须按关键字有序（按关键字递增或递减）排列，在有序表中，取中间元素作为比较对象，若给定值与中间元素的关键字相等，则查找成功……。从这里可以看出二分查找，要随机取元素的关键字和查找对像比较，二分查找只适合顺序存储，C也不正确，选D。【例3】顺序表可以采用的三种查找方法是什么？这三种查找方法对查找表中元素的要求各是什么？在含n个元素的顺序表中，其等概率情况下查找成功的平均查找长度各是多851812D1519201113161417少？分析：顺序表可以采用的三种查找方法，分别是顺序查找法、二分查找法和分块查找法。顺序查找法：表中的元素可以任意存放。二分查找法：表中元素必须按关键字有序存放。分块查找法：要求表中元素是分块有序，即前一块的关键字值均小于后一块的关键字值，同一块内元素可以按任意次序存放。具有n个元素的顺序表在等概率情况下，三种查找方法的查找成功的平均查找长度分别为：顺序查找法：ASL=（1+n）/2；二分查找法：ASL=log2（1+n）-1分块查找法：设每块含有s个元素，若用顺序查找确定元素所在的块，ASL=（n/s+s）/2+1；若用二分查找确定元素所在的块，ASL=log2（n/s+1）s/2。由此可见，二分查找法的平均查找长度最小，分块查找法次之，顺序查找法平均查找长度最大。【例4】画出对长度为20的有序表进行二分查找的判定树，并指出在等概率情况下，查找成功的平均查找长度以及查找失败时所需的最多与关键字值的比较次数。分析：对长度为20的有序顺序表进行二分查找的判定树如图9-1所示。图9-1判定树等概率情况下的平均查找长度：ASL=(1*1+2*2+3*4+4*8+6*5)/20=74/20=3.7二分查找在查找失败时所需与键值比较次数不超过判定树的高度，因为判定树中度小于2的结点只可能在最下面的两层上，所以n个结点的判定树高度与n个结点的完全二叉树的高度相同，即为1)(nlog2。所以n个元素的有序表，查找失败时与关键字值最多比较1)(nlog2次。所以20个元素的有序表查找失败时最多与关键字值的比较次数为：1)(nlog2=21log2=5。1025637184986【例5】对含有n个互不相同元素的集合，同时找最大元素和最小元素至少需进行多少次比较?分析：设变量max和min用于存放最大元素和最小元素的位置，第一次取两个元素进行比较，大的放入max，小的放入min。从第2次开始，每次取一个元素先和max比较，如果大于max则以它替换max，并结束本次比较；若小于max则再与min相比较，在最好的情况下，比较下去都不用和min相比较，所以这种情况下，至少要进行n-1次比较就能找到最大元素和最小元素。解：n-1次。【例6】构造有12个元素的二分查找的判定树，并求解下列问题：（1）各元素的查找长度最大是多少？（2）查找长度为1、2、3、4的元素各有多少？具体是哪些元素？（3）查找第5个元素依次要比较哪些元素？分析：12个元素的判断树如图9-2所示：图9-2判定树（1）最大查找长度是树的深度4。（2）查找长度为1的元素有1个，为第6个。查找长度为2的元素有2个，为第3个和第9个。查找长度为3的元素有4个，为第1、4、7、11个。查找长度为4的元素有5个，为第2、5、8、10、12个。（3）查找第五个元素依次比较6，3，4，5。【例7】对于给定结点的关键字集合K={42，57，82，32，70，35，12，48，96，18}，（1）试构造一棵二叉排序树；（2）求等概率情况下的平均查找长度ASL；（3）如何得到关键字值的有序序列；（4）对于上述10个关键字值的不同排列次序，构造不同的二叉排序树中，最好和最坏情况下的高度各是多少；（5）查找70，要比较多少次才能找到；（6）画出删除结点42，以后的二叉排序树。分析：（1）二叉排序树构造如图9-3所示。87图9-3构造二叉排序（2）ASL=(1*1+2*2+3*4+4*3)/10=29/10=2.9（3）对二叉排序树进行中序遍历即可以得到原关键字值的有序序列。（4）对于关键字值的不同排列次序构造的二叉排序树中，最好情况二叉排序树的高度为11log2=4；最坏情况是原关键字值有序排列，则二叉排序树的高度为10。（5）查找70，要比较4次才能找到,依次与42、57、82、70进行比较。（6）在二叉树中删除结点可用中序直接前驱法（如图9-4）或中序直接后继法（如图9-4）。图9-4中序直接前驱法图9-5中序直接后继法【例8】现有一组单词（WEK,SUN,MON,TUE,WED,THU,FRI,SAT），其相应的散列函数值为(3，2，6，3，2，5，6，0)，散列表长度为10（散列地址空间为0..9），要求：（1）构造该散列表，并用线性探测法解决冲突；（2）若对每个元素查找一次，求总的比较次数。分析：（1）构造散列函数H＝key%10WEK关键字为3，H=3%10=3，WEK放在3单元。SUN关键字为2，H=2%10=2，SUN放在2单元。MON关键字为6，H=6%10=2，MON放在6单元。TUE关键字为3，H=3%10=3，和WEK冲突，由线性探测法H＝（3＋1）%10＝4，TUE放在4单元。WED关键字为2，H=2%10=2，和SUN冲突，由线性探测法H＝（2＋1）%10＝3，还冲突，再求H＝（2＋2）%10＝4，还冲突。再求H=（2＋3）%10＝5，WED放在5单元。573532D124282709618485732D12358270961848573532D12488270961888THU关键字为5，H=5%10=5，冲突。H=(5+1)%10=6，还冲突。H=(5+2)%10=7，THU放在7单元。FRI关键字为6，H=6%10=6，冲突。H=(6+1)%10=7，还冲突。H=(6+2)%10=8，FRI放在7单元。SAT关键字为0，H=0%10=0，WEK放在0单元。0123456789SATSUNWEKTUEWEDMONTHUFRI（2）WEK查找1次，SUN查找1次，MON查找1次，TUE查找2次，WED查找4次，THU查找2次，FRI查找3次，SAT查找1次。总比较次数=1+1+1+2+4+2+3+1=15(次)。【例9】给定结点的关键字序列为：12，18，30，70，20，8，63，15，19，设散列函数为H(k)=k%11，试画出采用拉链法解决冲突所构造的哈希表，并求等概率情况下的ASL。解：拉链法解决冲突的结果如图9-6所示。图9-6拉链法在等概率情况下成功的平均查找长度为：ASL＝(1*5+2*2+3*1+4*1)/9=16/9【例10】设计一个算法，求出指定结点在给定的二叉排序树中所在的层数。分析：查找成功时的比较次数即为结点所在层数。可设置查找时计数，比较一次计数器加1。如查找成功时返回计数器累加数字；不成功时，返回0。算法如下：#includestdio.h#includetype.hintsearch_depth(BiTreeT,ElemTypekey)//求当前结点所在层数{BiTNode*p;intdep=0;p=T;while(p)89{if(key==T-data){dep++;break;}elseif(keyT-data){dep++;p=p-rchild;}else{dep++;p=p-lchild;}}if(p)returndep;elsereturn0;}【例11】试编写利用二分查找法确定记录的所在块的分块查找算法。分析：采用分块查找时，除了顺序表之外，还要有索引表。其中索引表中含有各块索引。在各块中进行顺序查找时，监视哨可设在本块的表尾，即将下一块的第一个记录暂时移走（若本块内记录没有填满，则监视哨的位置仍在本块的尾部），待块内顺序查找完成后再移回来。此时增加了赋值运算，但免去了判断下标变量是否越界的比较。注意，最后一块需进行特殊处理。在块内进行顺序查找时，如果需要设置监视哨，则必须先保存相邻块的相邻元素，以免数据丢失。算