第九章-查找课1

1第九章查找9.1静态查找表

9.1.1顺序表的查找

9.1.2有序表的查找

9.1.4索引顺序表的查找9.2动态查找表

9.2.1二叉排序树9.3哈希表

9.3.1什么是哈希表

9.3.2哈希函数的构造方法

9.3.3处理冲突的方法

9.3.4哈希表的查找及其分析2第九章查找学习要点：熟练掌握顺序表和有序表的查找方法熟练掌握二叉排序树的构造和查找方法熟练掌握哈希表的构造方法,深刻理解哈希表与其他结构的表的实质性的差别3重点：顺序查找、二分查找、二叉树查找以及散列表上查找的基本思想、表示方法和算法实现第九章查找4基本概念：第九章查找——若表中存在特定元素，称查找成功，应输出该记录；——否则，称查找不成功（也应输出失败标志或失败位置）查找表

查找查找成功查找不成功静态查找动态查找关键字主关键字次关键字——由同一类型的数据元素（或记录）构成的集合。——查询(Searching)特定元素是否在表中。——只查找，不改变集合内的数据元素。——既查找，又改变（增减）集合内的数据元素。——记录中某个数据项的值，可用来识别一个记录

(预先确定的记录的某种标志)

——可以唯一标识一个记录的关键字例如“学号”例如“女”是一种数据结构——识别若干记录的关键字5第九章查找6如何进行查找？

取决于查找表的结构，即：记录在查找表中所处的位置。

查找表本身是一种很松散的结构，因此，为了提高查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，换句话说，用另外一种结构来表示查找表，以便按某种规则进行查找。第九章查找7（2）对查找表常用的操作有哪些？查询某个“特定的”数据元素是否在表中；查询某个“特定的”数据元素的各种属性；在查找表中插入一元素；从查找表中删除一元素。

（3)有哪些查找方法？

查找方法取决于表中数据的排列方式;讨论：（1）查找的过程是怎样的？

给定一个值K，在含有n个记录的文件中进行搜索，寻找一个关键字值等于K的记录，如找到则输出该记录，否则输出查找不成功的信息。例如查字典针对静态查找表和动态查找表的查找方法也有所不同。“特定的”=关键字8明确：查找的过程就是将给定的K值与文件中各记录的关键字项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为平均查找长度（ASL：averagesearchlength）。其中：n是文件记录个数；Pi是查找第i个记录的查找概率（通常取等概率,即Pi=1/n）;Ci是找到第i个记录时所经历的比较次数。统计意义上的数学期望值物理意义：假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为ASL。显然，ASL值越小，时间效率越高。如何评估查找方法的优劣？9第一小节9.1静态查找表109.1静态查找表针对静态查找表的查找算法主要有：

静态查找表的抽象数据类型参见教材P216。9.1.1顺序查找（线性查找）9.1.2折半查找（二分或对分查找）9.1.4分块查找（索引顺序查找）119.1静态查找表一、顺序查找顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最直接的办法。

对顺序结构如何线性查找？；对单链表结构如何线性查找？函数虽未给出，但也很容易编写；只要知道头指针head就可以“顺藤摸瓜”；对非线性树结构如何顺序查找?可借助各种遍历操作！129.1静态查找表一、顺序查找顺序查找：从表中最后一个记录始，逐个进行记录的关键字和给定值的比较，若相等则查找成功，否则直至第一个记录。静态查找表的顺序存储结构：typedefstruct{ElemType*elem;//数据元素存储空间基址，建表时按实际长度分配，0号单元留空

intlength;//表长度}SStable;//length=n+1,n：结点个数139.1静态查找表能不能把i<=n的比较省掉？149.1静态查找表算法优化：把待查关键字key存入表头或表尾（俗称“哨兵”），这样可以加快执行速度。设置哨兵的好处：

在顺序表中总可以找到待查结点。

否则，必须将判断条件i>=0加进for语句。159.1静态查找表169.1静态查找表例：查找key=8的结点所在的数组元素的下标179.1静态查找表查找成功，则i是key值为

8的结点所在的数组元素的下标。189.1静态查找表199.1静态查找表209.1静态查找表查找失败，则i=0。21——返回特殊标志，例如返回空记录或空指针。前例中设立了“哨兵”，就是将关键字送入末地址ST.elem[0].key使之结束并返回i=0。讨论②查找效率怎样计算？——用平均查找长度ASL衡量。讨论①查不到怎么办？22讨论③如何计算ASL？分析：查找第1个元素所需的比较次数为1；查找第2个元素所需的比较次数为2；……查找第n个元素所需的比较次数为n；总计全部比较次数为：1＋2＋…＋n=(1+n)n/2未考虑查找不成功的情况：查找哨兵所需的比较次数为n+1这是查找成功的情况若求某一个元素的平均查找次数，还应当除以n（等概率），即：ASL＝（1＋n）/2，时间效率为O(n)239.1静态查找表上面讨论的前提是每次查找都是“成功”的，但实际上不一定对于给定的每个值都能找到相应的记录，即会产生查找“不成功”的情况，如果查找不成功的情形不容忽视时，查找算法平均查找长度应是查找成功时的平均查找长度与查找不成功时的平均查找长度之和。假设查找成功和不成功的概率相等，即均为1/2，则顺序查找的平均查找长度为：

249.1静态查找表顺序查找的优缺点：

优点：简单且适用面广，对表的结构没有要求，无论记录是否按关键字有序都可应用。

缺点：效率低。平均查找长度较大，特别不适用于表长较大的查找表。259.1静态查找表二、有序查找表折半查找（又称二分查找或对分查找）这是一种容易想到的查找方法。先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小至右半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。对顺序表结构如何编程实现折半查找算法？

——见后面例子，或见教材（P219）对单链表结构如何折半查找？

——无法实现！因全部元素的定位只能从头指针head开始对非线性(树)结构如何折半查找？

——可借助二叉排序树来查找（属动态查找表形式）。

26②运算步骤：(1)low=1,high=11,mid=6，待查范围是[1,11]；(2)若ST.elem[mid].key<key，说明key[mid+1,high]，则令：low=mid+1;重算mid＝(low+high)/2；.(3)若ST.elem[mid].key>

key，说明key[low,mid-1]，则令：high=mid–1;重算mid；(4)若ST.elem[mid].key=key，说明查找成功，元素序号=mid;结束条件（1）查找成功：ST.elem[mid].key=key

（2）查找不成功：high≤low（意即区间长度小于0）解：①先设定3个辅助标志:

low,high,mid，折半查找举例：Low指向待查元素所在区间的下界high指向待查元素所在区间的上界mid指向待查元素所在区间的中间位置

已知如下11个元素的有序表：

（0513192137566475808892）,请查找关键字为21

和85的数据元素。显然有：mid=(low+high)/2279.1静态查找表例：查找key=9的结点所在数组元素的下标地址。查找成功的情况：数组ST.elem如下图所示有序数组ST.elem：递增序ST.elem[i].Key<=ST.elem[i+1].Key;i=1,2,……n-1查找范围：low（低下标）=1;high（高下标）=7;比较对象：中点元素，其下标地址为

mid=（low+high）/2=4289.1静态查找表查找范围：low（低下标）=1;high（高下标）=3;查找范围：low（低下标）=1;high（高下标）=3;比较对象：mid=（low+high）/2=2299.1静态查找表查找范围：low（低下标）=1;high（高下标）=3;比较对象：mid=（low+high）/2=2查找范围：low（低下标）=3;high（高下标）=3;309.1静态查找表查找范围：low（低下标）=3;high（高下标）=3;查找范围：low（低下标）=3;high（高下标）=3;比较对象：mid=（low+high）/2=3319.1静态查找表例：查找key=5的结点所在的数组元素的下标地址329.1静态查找表339.1静态查找表349.1静态查找表359.1静态查找表intSearch_bin(SStableST,KeyTypekey)//在有序表中查找关键字之值为key的结点，找到返回该结点在表中的下标地址，否则返回0{low=1;high=ST.length;

while(low<=high){mid=(low+ligh)/2;if(EQ(ST.elem[mid].key,key)returnmid;elseif(LT(key,ST.elem[mid].key))high=mid-1;elselow=mid+1;}return0；

}//Search_Bin36讨论①若关键字不在表中，怎样得知和停止？——典型标志是：当查找范围的上界≤下界时停止查找。讨论②二分查找的效率（ASL平均查找长度）1次比较就查找成功的元素有1个（20），即中间值；2次比较就查找成功的元素有2个（21），即1/4处（或3/4）处；3次比较就查找成功的元素有4个（22），即1/8处（或3/8）处…4次比较就查找成功的元素有8个（23），即1/16处（或3/16）处………则第m次比较时查找成功的元素会有（2m-1）个；为方便起见，假设表中全部n个元素＝2m-1个，此时就不讨论第m次比较后还有剩余元素的情况了。全部比较总次数为1×20＋2×21＋3×22＋4×23…＋m×2m—1

＝推导过程37平均每个数据的查找时间还要除以n，所以：（详细推导过程见教材P221的附录1）课堂练习（多项选择）：Ａ．采用链式存贮结构 Ｂ．记录的长度≤128Ｃ．采用顺序存贮结构Ｄ．记录按关键字递增有序√√使用折半查找算法时，要求被查文件：上述平均查找长度（ASL）计算成立的前提是第m次比较时恰好剩余2m-1个。38填空：假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为

2；比较四次查找成功的结点数为

8；平均查找长度为

3.7

。显然，平均查找长度＝O（log2n）<5次（25）。但具体是多少次，则不应当按照公式来计算（即（21×log221）/20＝4.6次并不正确！）。因为这是在假设n＝2m-1的情况下推导出来的公式。应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74；

ASL＝74/20=3.7！！！39查找过程可用二叉树描述：每个记录用一个结点表示；结点中值为该记录在表中位置，这个描述查找过程的二叉树称为判定树。n个元素的表的折半查找的判定树是唯一的，即：判定树由表中元素个数决定。

找到有序表中任一记录的过程就是：走了一条从根结点到与该记录相应的结点的路径。

比较的关键字个数：为该结点在判定树上的层次数。

查找成功时比较的关键字个数最多不超过树的深度d:d=log2n+1

查找不成功的过程就是走了一条从根结点到外部结点的路径。折半查找效率分析法（参见教材P220）：409.1静态查找表四、索引顺序查找（分块查找）

对比顺序表和有序表的查找性能之差别：

顺序表有序表表的特性无序表有序表存储结构顺序结构或链表结构顺序结构插删操作易于进行需移动元素

ASL值大（顺序查找）小（折半查找）

索引顺序表=索引+顺序表一般情况下，索引是一个有序表41四、索引顺序查找（分块查找）是一种顺序查找的另一种改进方法。先让数据分块有序，即分成若干子表，要求每个子表中的数值（用关键字更准确）都比后一块中数值小（但子表内部未必有序）。然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针）。索引表最大关键字起始地址2212138920334244382448605874498653第1块第2块第3块224886例：2248861713特点：块间有序，块内无序429.1静态查找表索引顺序表应用范围：分块表示的顺序表。块内元素之间无序、有序皆可。块间元素有序。439.1静态查找表查找方法：

1）由索引确定记录所在区间；

2）在顺序表的某个区间内进行查找。所以，这也是一种缩小区间的查找方法例：查找key=47的结点索引。查索引表，确定在第三块在第三块内进行顺序查找449.1静态查找表索引顺序表的平均查找长度为在索引中进行查找的平均查找长度和在顺序表中进行查找的平均查找长度之和。45查找步骤分两步进行：①对索引表使用折半查找法（因为索引表是有序表）；②确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；查找效率：ASL=Lb+Lw对索引表查找的ASL对块内查找的ASLS为每块内部的记录个数，n/s即块的数目例如当n=9，s=3时，ASLbs=3.5,而折半法为3.1,顺序法为5。469.1静态查找表47下一小节9.2动态查找表48动态查找表：用于频繁进行插入、删除、查找的查找表。特点：表结构本身是在查找过程中动态生成的。要求：即对于给定值key，若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。9.2动态查找表499.2动态查找树表一、二叉排序树（二叉查找树）

1．定义：------二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值；（3）它的左、右子树也都分别是二叉排序树。50（a）（b）练：下列2种图形中，哪个不是二叉排序树？----或是一棵空树；或者是具有如下性质的非空二叉树：

（1）左子树的所有结点均小于根的值；（2）右子树的所有结点均大于根的值；（3）它的左右子树也分别为二叉排序树。讨论：对左图中序遍历后的结果是什么？519.2动态查找树表例：

通常，可取二叉链表作为二叉排序树的存储结构522.将数据元素构造成二叉排序树的优点：①查找过程与顺序结构有序表中的折半查找相似，查找效率高；②中序遍历此二叉树，将会得到一个关键字的有序序列（即实现了排序运算）；③如果查找不成功，能够方便地将被查元素插入到二叉树的叶子结点上，而且插入或删除时只需修改指针而不需移动元素。注：若数据元素的输入顺序不同，则得到的二叉排序树形态也不同！——这种既查找又插入的过程称为动态查找。二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态查找表的一种适宜表示。一、二叉排序树（二叉查找树）539.2动态查找树表3．二叉排序树的查找算法：

若二叉排序树为空，则查找不成功；否则1）若给定值等于根结点的关键字，则查找成功；2）若给定值小于根结点的关键字，则继续在左子树上进行查找；3）若给定值大于根结点的关键字，则继续在右子树上进行查找。549.2动态查找树表559.2动态查找树表BitreeSearchBST(BiTreeT,KeyTypekey)//在二叉分类树查找关键字之值为key的结点，找到返回该结点的地址，否则返回空。T为二叉分类树的根结点的地址。

{if((!T)||EQ(key,T->data.key))return(T);//查找结束

elseif(LT(key,T->data.key))return(SearchBST(T->lchild,key));//在左子树中继续查找

elsereturn(SearchBST(T->rchild,key));//在右子树中继续查找

}//SearchBST569.2动态查找树表4．二叉排序树的插入算法对于动态查找表，在查找不成功的情况下，尚需插入关键字等于给定值的记录，并且从查找的过程容易得出插入的算法：插入算法首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入；若二叉树为空，则新插入的结点为根结点。注意：新插入的结点总是叶子结点，其插入位置由查找过程中得到。574524531290如果待查找的关键字序列输入顺序为：（24，53，45，45，12，24，90），2453451290查找成功，返回查找成功，返回讨论1：二叉排序树的插入和查找操作则生成二叉排序树的过程为：例：输入待查找的关键字序列=（45，24，53，45，12，24，90）则生成的二叉排序树形态不同：查找成功，返回查找成功，返回589.2动态查找树表例：将数的序列：122、99、250、110、300、280作为二叉查找树的结点的关键字值，生成二叉查找树。1222503001102809912212299122250991222501109912225030011099599.2动态查找树表如：插入280的过程。609.2动态查找树表619.2动态查找树表629.2动态查找树表5．二叉排序树的删除算法和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。可分三种情况讨论：（1）被删除的结点是叶子：直接删除，更改它的父亲结点的相应指针值为空。639.2动态查找树表（2）被删除的结点只有左子树或者只有右子树由左子树或右子树取代被删结点。649.2动态查找树表

删除数据值为99的结点。659.2动态查找树表

删除数据值为200的结点。669.2动态查找树表（3）被删除的结点既有左子树，也有右子树，则通常的做法：选取“替身”取代被删结点。有资格充当该替身的是谁哪？

左子树中最大的结点(被删结点的左子树中的最右的结点，其右儿子指针值为空)或右子树中最小的结点(被删结点的右子树中的最左的结点，其左儿子指针值为空)

要点：维持二叉分类树的特性不变。在中序遍历中紧靠着被删结点的结点才有资格作为“替身”679.2动态查找树表（3）被删除的结点既有左子树，也有右子树689.2动态查找树表（3）被删除的结点既有左子树，也有右子树2002503001109910523021640045050020025030011099105230216400450500699.2动态查找树表结论：先将替身的数据值复制到被删结点将原替身的另一儿子作为它的父亲结点的儿子，究竟是作为左儿子还是右儿子依原替身结点和其父亲结点的关系而定。释放原替身结点的空间。709.2动态查找树表结论：PL、PR皆空，直接删除PL或PR为空

PL为空，删除后的情况719.2动态查找树表结论：PL、PR皆不空72FCCLSSLQ