《数结_8查找j1》由会员分享，可在线阅读，更多相关《数结_8查找j1（47页珍藏版）》请在金锄头文库上搜索。
1、第九章 查找第九章 查找/检索 (Search)查找概述9.1 静态查找表9.2 动态查找表二叉排序树9.3 散列表（哈希表）查找概述查找表(Search Table)：同类型数据元素/记录的集合数据元素/记录：关键字其他项 ElemType keyother查找操作：给定一个值K，在查找表中找出键值等于K的记 录查找 查找概述 查找表的存储结构：线性结构：顺序表，链表树形结构：二叉排序树，B树散列结构：哈希表（散列表）查找 查找概述 查找性能的评价指标：平均查找长度ASL: n -查找表中记录个数Ci -查找到第i条记录时，K K与关键字的比较次数与关键字的比较次数Pi -查找第i条记录的概
2、率查找 查找概述 查找表的基本运算：创建表： Create( /数组的基地址int length； /表中记录的个数 SSTable；0123n STR1R2R3RnST.length查找 静态查找表 顺序查找 顺序查找思想：从表的一端开始，逐个将给定值K与关键字进行比较，直到找到记录或查找失败；注意：这里“顺序”的含义不是查找表是顺序存储的，而是顺着表的自然次序逐个比较。查找 静态查找表 顺序查找 int Search(SSTable ST, KeyType K) /从表尾开始，顺序查找, 查找成功返回元素的位置下 标/查找失败，返回0int i=ST.length;while( i0 re
3、turn i ;0123n STR1R2R3Rn检测下标 i 是否越界查找 静态查找表 顺序查找 int Search(SSTable ST, KeyType K) /带哨兵的检索，从表尾开始，顺序查找/查找成功返回元素的位置下标；查找失败，返回0int i=ST.length; ST.elem0.key=K;while( ST.elem i .key !=K ) i - -;return i;0123n STKR1R2R3Rn监视哨查找 静态查找表 顺序查找 查找效率：查找成功时的ASL：查找 静态查找表 顺序查找 查找失败时的ASL： ASL=n+1平均：ASL3(n+1)/4顺序查找小结
4、：最朴素的查找方法对表的限制最少不仅适用于顺序存储结构，而且适用于链式存 储结构时间性能最差，O(n) 等概情况下查找成功时ASL(n+1)/2查找 静态查找表 顺序查找 9.1.2 折半查找(二分查找)对表的限制： 1. 顺序存储； 2. 按关键字有序排列 查找方法：设查找区间为R low . . high 取mid(low+high)/2，则当KRmid.key： 下一个查找区间为 R mid+1. . High 当K=Rmid.key： 查找成功，结束当lowhigh： 查找失败，结束查找 静态查找表 折半查找 02161122 25 27 3342 56 778179013245687
5、910111312lowmidhigh例，K39K33 low=mid+1midK02 low=mid+1K11 low=mid+1经过与关键字33, 16, 02, 11的比较，查找失败查找 静态查找表 折半查找 int Search_Bin(SSTable ST, KeyType K) int low=1, high=ST.length;int mid;while(lowSTmid.key) low=mid+1; /在右区间继续查找else return mid; /查找成功的出口return 0; /查找失败的出口查找 静态查找表 折半查找 折半查找判定树：mid左半区间右半区间Lowm
6、id-1mid+1high查找 静态查找表 折半查找 n=13的折半查找判定树71. .68. .133101. .24. .68. .911. .131581224691113折半查找判定树是一棵理想平衡树树的高度为 H=log2(n+1) 或 H=log2n+1树的形态取决于n值查找 静态查找表 折半查找 查找成功的过程是自树根沿树枝到达目标结点，K与关键字的最大比较次数不超过树高log2n+17310158122469111302161122 25 27 3342 56 778179013245687910111312 39查找K39：查找 静态查找表 折半查找 查找失败的过程是从树根开
7、始，沿树枝到达一个外部结 点，K与关键字的最大比较次数也不超过树高 7310158122469111302161122 25 27 3342 56 778179013245687910111312 39查找K13：R2key: 在bt的左子树上继续查找K bt-key: 在bt的右子树上继续查找K=bt-key: 查找成功3248263929563412441946bt3248263929563412441946例如:K34 K18查找成功：自树根沿树枝到达目标结点查找失败：自树根沿树枝到达一个外部结点成功或失败的最大比较次数都不超过树高查找的非递归算法:BiTree BSTSearch(Bi
8、Tree bt, KeyType K) /在根为bt的二叉排序树上查找键值等于K的记录BiTree p=bt; /定义一个临时指 针while (p) if (Kkey) p=p-lchild; /在左子树上继续 找else if (K p-key) p=p-rchild; /在右子树上继续 找else return p; /查找成功 return p; /查找失败，返回空指针 查找的递归算法:BiTree BSTSearch(BiTree bt, KeyType K) /在根为bt的二叉排序树上查找键值等于K的记录if ( !bt | K=bt-key ) return bt; /查找成功或
9、失败而结 束else if (K key) return BSTSearch (bt-lchild, K) /在左子树上继续 找elsereturn BSTSearch (bt-rchild, K) /在右子树上继续 找 查找分析：查找成功时：ASL(1122344351) /11 = 34/11查找失败时：ASL(354552) /12 = 45/12ASL值与树的形态有关32482639295634124419469.2.3二叉排序树的插入与生成新结点作为一个叶子插到二叉排序树上53248527关键字序列： 53，24，45，85，27，121245ASL=(11223241) / 6 =
10、 15/6关键字序列 45，24，27，53，12 ，85452453122785ASL=(112233) / 6 = 14/6关键字序列 12，24，27，45, 53，85124585272453ASL=(123456) / 6 = 21/6插入算法：void InsertBST ( BiTree /插在左子树 上else if (S-keybt-key) InsertBST(bt-rchild, S); /插在右子 树上else return；/键值已存在，不插9.2.4二叉排序树的删除操作在下面的讨论中设：P是待删结点F是P的双亲S是P的中序前驱Q是S的双亲 P的度0直接删 FP FR
11、FP FLFFRFFLF-lchild=NULL F-rchild=NULL 2. P的度1 将P的唯一的孩子交给双亲FP FRPLFP FRPR.PL,P,F,FR. P, PR,F,FR.FFRPLFFRPR.PL, F,FRPR, F,FR.Flchild=P-lchild F-lchild=P-rchild3. P的度2 两种删除方法.CL,C,., SL,S,P,PR,F,FR.FPFRPRCCL.SSLPFFRPRCCL.SSL.CL,C,., SL,S, PR,F,FR.方法一：s=p-lchild;while(s-rchild) s=s-rchild ; /找P的中序前驱 Ss
12、-rchild=p-rchild; /P的右孩子交给 SF-lchild=p-lchild; / P的左孩子交给 Ffree(p);.CL,C,.,QL,Q,SL,S,P,PR,F,FR.方法二：FPFRPRCCL.QQLSSLPSSLFFRPRCCL.QQLS.CL,C,.,QL,Q,SL,S,PR,F,FR.q=p; s=p-lchild;whild(s-rchild) q=s; s=s-rchild ; /找P的中序前驱Sp-key=s-key; p-other=s-other; if (p != q) q-rchild=s-lchild /S的左孩子交给Qelse q-lchild=s-lchildfree(s)FPFRPRSSLq352418302833506078908246394843n=15, h=6, ASL=55/1521
