数据结构-C语言-第九章查找课件

1、第九章 查找4 学时第九章 查找4 学时教学目标熟练掌握顺序表和有序表（折半查找）的查找算法及其性能分析方法；熟练掌握二叉排序树的构造和查找算法及其性能分析方法；掌握二叉排序树的插入算法，了解二叉排序树的删除算法；熟练掌握哈希函数（除留余数法）的构造熟练掌握哈希函数解决冲突的方法及其特点教学目标熟练掌握顺序表和有序表（折半查找）的查找算法及其性能查找的基本概念 查找表（Search Table）：由同一类型的数据元素（或记录）构成的集合，是一种以集合为逻辑结构、以查找为核心运算的数据结构。 静态查找表：只对查找表进行查询某个特定的数据元素或某个特定数据元素的各种属性的操作。如：查询成绩表中是否

2、有某学生或该学生某门课程的成绩。 动态查找表：对查找表进行插入或删除某个数据元素的操作。如：插入某个学生某门课程的成绩。查找的基本概念 查找表（Search Table）：由同一类查找的基本概念关键字：是数据元素中某个数据项的值，它可以标识一个数据元素主关键字：可以唯一标识一个记录的关键字次关键字：可以标识若干个记录的关键字 查找(Search)：也称检索，是根据给定的某个值，在查找表中确定一个关键字等于给定值的记录或数据元素。查找成功：即找到满足条件的数据对象，这时作为结果可报告该对象在结构中的位置, 还可给出该对象中的具体信息。查找不成功：或搜索失败。作为结果应报告一些信息, 如失败标志、

3、位置等。 查找的基本概念关键字：是数据元素中某个数据项的值，它可以标识查找的基本概念衡量查找算法的标准：平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度。n：记录的个数pi：查找第i个记录的概率 ( 通常认为pi =1/n )ci：找到第i个记录所需的比较次数算法所需要的存储量和算法的复杂性等查找的基本概念衡量查找算法的标准：数据结构静态查找表(基于线性表的查找)第一节数据结构静态查找表(基于线性表的查找)第一节查找方式：从表的第一个元素开始，将给定的值与表中逐个元素的关键字进

4、行比较，直到两者符合，查到所要找的元素为止。否则就是表中没有要找的元素，检索不成功。适用范围：顺序表或线性链表表示的静态查找表，表内元素之间无序。顺序表的表示 typedef struct ElemType *elem; /表基址 int length; /表长 SSTable;顺序查找实现 int LocateELem(SqList L,ElemType e) for (i=0;i0; - -i) 或 for(i=1; i=n; i+) return i; i例 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找64 64监

5、视哨 iiii比较次数=5 比较次数：查找第n个元素： 1查找第n-1个元素：2.查找第1个元素： n查找第i个元素： n+1-i查找失败： n+19.1.1 顺序查找int Search_Seq( SST9.1.1 顺序查找顺序查找方法的特点 表结构为有序表、无序表均可适用； 存储结构为顺序存储和链式存储的表均适用； 适合于短表，方法简单； 时间复杂度为O(n)； 平均查找长度比其他方法大，查找成功时： 9.1.1 顺序查找顺序查找方法的特点9.1.2 折半查找查找方法：首先选择表中间的一个记录，比较其关键字与要查找关键字的值；若要找的记录的关键字值大，则再取表的后半部的中间记录进行比较；否

6、则取前半部的中间记录进行比较，如此反复，直到找到为止。适用范围：采用顺序存储结构的有序表 9.1.2 折半查找查找方法：首先选择表中间的一个记录，比9.1.2 折半查找折半查找的实现令low=1,high=n, mid= (low+high)/2 若kelemmid.key，则low=mid+1lowhighmid例1 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找21 当k=elemmid.key,查找成功！9.1.2 折半查找折半查找的实现lowhighmid例19.1.2 折半查找lowhighmid1 2 3 4 5 6

7、7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找701 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighlowhigh 不成功！9.1.2 折半查找lowhighmid1 29.1.2 折半查找算法描述设表长为n，low、high和mi

8、d分别指向待查元素所在区间的上界、下界和中点，k为给定值。初始时，令low=1,high=n,mid= (low+high)/2 让k与mid指向的记录比较若k=elemmid.key，查找成功若kelemmid.key，则low=mid+1重复上述操作，直至lowhigh时，查找失败9.1.2 折半查找算法描述9.1.2 折半查找int Search.Bin ( SSTable ST,KeyType key) / 在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为 该元素在表中的位置，否则为0。 low = 1; high = ST.length; /置区间初值 whil

9、e (low50)时间复杂度 O(log2n)9.1.2 折半查找折半查找方法的特点9.1.3 索引顺序查找（分块查找 ）查找方法：将n个元素均匀地分成块，每块有s个记录，块间按大小排序，块内元素不排序。要建立一个块的最大（或最小）关键字表。查找时，先用顺序查找或折半查找法由最大关键字查出所在的块，再用顺序查找法在块中查找。 适用条件：分块有序表9.1.3 索引顺序查找（分块查找 ）查找方法：将n个元素均9.1.3 索引顺序查找（分块查找 ）1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48

10、 60 58 74 57 86 5322 48 861 7 13索引表查38成功算法实现： 用数组存放待查记录，每个数据元素至少含有关键字域 建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针。9.1.3 索引顺序查找（分块查找 ）1 2 39.1.3 索引顺序查找（分块查找 ）分块查找方法特点：对存储结构为顺序和线性链表的均适用；平均查找长度比顺序查找小； 用折半查找确定所在块时：若用顺序查找确定所在块时：9.1.3 索引顺序查找（分块查找 ）分块查找方法特点：9.1.4 基于线性表的查找方法比较顺序查找折半查找分块查找ASL最大(N+1)/2最小ASL=log2(n+1)

11、 -1两者之间表结构有序表无序表有序表分块有序表存储结构顺序存储线性链表顺序存储顺序存储线性链表9.1.4 基于线性表的查找方法比较顺序查找折半查找分块查找数据结构动态查找表(基于树的查找)第二节数据结构动态查找表(基于树的查找)第二节动态查找表的特点 表结构在查找过程中动态生成 对于给定值key，若表中存在，则成功返回；否则插入关键字等于key 的记录二叉排序树平衡二叉树B-树B+树键树动态查找表的特点二叉排序树9.2.1 二叉排序树二叉排序树的定义： 二叉排序树或是空树，或是满足如下性质的二叉树： 若其左子树非空，则左子树上所有结点的值均小于根结点的值； 若其右子树非空，则右子树上所有结点

12、的值均大于等于根结点的值； 其左右子树本身又各是一棵二叉排序树9.2.1 二叉排序树二叉排序树的定义：9.2.1 二叉排序树下列图形中，哪个不是二叉排序树 ？16245103798319210746589.2.1 二叉排序树下列图形中，哪个不是二叉排序树 ？1中序遍历二叉排序树后的结果有什么规律？9.2.1 二叉排序树353123745100246190783，12，24，37，45，53，61，78，90，100递增得到一个关键字的递增有序序列中序遍历二叉排序树后的结果有什么规律？9.2.1 二叉排序9.2.1 二叉排序树二叉排序树的操作查找若查找的关键字等于根结点，成功否则若小于根结点，查

13、其左子树若大于根结点，查其右子树在左右子树上的操作类似7218123810找 8 9.2.1 二叉排序树二叉排序树的操作查找72181237.2.1 数组（邻接矩阵）表示法二叉排序树查找的算法思想若二叉排序树为空，则查找失败，返回空指针。若二叉排序树非空，将给定值key与根结点的关键字T-data.key进行比较： 若key等于T-data.key，则查找成功，返回根结点地址； 若key小于T-data.key，则进一步查找左子树； 若key大于T-data.key，则进一步查找右子树。7.2.1 数组（邻接矩阵）表示法二叉排序树查找的算法思想9.2.1 二叉排序树BiTree SearchB

14、ST(BiTree T, KeyType key) / 在根指针bst所指二叉排序树中，递归查找某关键字等于key的元素，若查找成功，返回指向该元素结点指针，否则返回空指针 if(!T) | key=T-data.key) return T; /查找成功 else if (T-data.key key) return SearchBST(T-lchild, key); /在左子树继续查找else return SearchBST(T-rchild, key); /在右子树继续查找 9.2.1 二叉排序树BiTree SearchBST(B9.2.1 二叉排序树Status SearchBST(

15、BiTree T,KeyType key,BiTree f,BiTree &P) /在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元/素，若查找成功，则指针p指向该数据元素结点，并返回TRUE，否/则指针p指向查找路径上访问的最后一个结点并返回FALSE，指针f指向T的双亲，其初始调用值为NULL if (!T) p=f; return FALSE; /查找不成功 else if EQ(key,T-data.key) p=T; return TRUE; /查找成功 else if LT(key,T-data.key) return SearchBST(T-lchild,key,T

16、,P) /在左子树中继续查找 else return SearchBST(T-rchild,key,T,P) /在右子树中继续查找 / SearchBST9.2.1 二叉排序树Status SearchBST(B9.2.1 二叉排序树二叉排序树的操作插入若二叉排序树为空，则插入结点应为根结点否则，继续在其左、右子树上查找 树中已有，不再插入 树中没有，查找直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子插入的元素一定在叶子结点上35312374510024619078插入20 209.2.1 二叉排序树二叉排序树的操作插入插入的元素一定9.2.1 二叉排序树二

17、叉排序树的操作创建从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树。第一个关键字是根结点。例 10， 18， 3， 8， 12， 2， 7， 310101810183101838101838121018381221018381227101838122739.2.1 二叉排序树二叉排序树的操作创建例 10，9.2.1 二叉排序树二叉排序树的操作创建同样的关键字，给出的顺序不同，生成的树不同。4024551237122437405540，24，12，37，5512，24，37，40，559.2.1 二叉排序树二叉排序树的操作创建40245519.2.1 二叉排序树二叉排序树的操作删

18、除删除的要求将因删除结点而断开的二叉链表重新链接起来防止重新链接后树的高度增加删除的原则：删除后保持所有节点的中序遍历顺序不变9.2.1 二叉排序树二叉排序树的操作删除数据结构-C语言-第九章查找9.2.1 二叉排序树删除叶子结点：只需将其双亲结点指向它的指针清零，再释放它即可。被删结点缺左子树或右子树：被删结点缺右子树，可以拿它的左子女结点顶替它的位置，再释放它。被删结点缺左子树，可以拿它的右子女结点顶替它的位置，再释放它。被删结点左、右子树都存在：可以在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删结点中，再来处理这个结点的删除问题。9.2.1 二叉排序树删除叶子结点

19、：只需将其双亲结点指向它9.2.1 二叉排序树 第i层结点需比较i次。在等概率的前提下，上述两图的平均查找长度为：40245512371224374055 平均查找长度和二叉树的形态有关，即，最好：log2n（形态匀称，与折半查找的判定树相似）最坏: (n+1)/2（斜树）二叉排序树查找的性能分析9.2.1 二叉排序树 第i层结点需比较i次。在等9.2.2 平衡二叉树问题：如何提高二叉排序树的查找效率？尽量让二叉树的形状均衡 平衡二叉树（Balanced Binary Tree ）的定义（AVL树） 左、右子树是平衡二叉树； 所有结点的左、右子树深度之差的绝对值 1 结点的平衡因子BF (Ba

20、lance Factor) 该结点左子树与右子树的高度差，任一结点的平衡因子只能取：-1、0 或 1； 如果树中任意一个结点的平衡因子的绝对值大于1，则这棵二叉树就失去平衡，不再是AVL树；平衡二叉树 对于一棵有n个结点的AVL树，其高度保持在O(log2n)数量级，ASL也保持在O(log2n)量级。9.2.2 平衡二叉树问题：如何提高二叉排序树的查找效率？9.2.2 平衡二叉树练习：判断下列二叉树是否AVL树？(a) 平衡树 (b) 不平衡树00011-1-120001-19.2.2 平衡二叉树练习：判断下列二叉树是否AVL树？(9.2.2 平衡二叉树平衡化旋转 如果在一棵AVL树中插入一

21、个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。单向左旋平衡处理单向右旋平衡处理左右双旋平衡处理右左双旋平衡处理保证二叉排序树的次序不变9.2.2 平衡二叉树平衡化旋转单向左旋平衡处理保证二叉排9.2.2 平衡二叉树若在A的左子树的左子树上插入结点，使A的平衡因子从1增加至2，需要进行一次顺时针旋转。(以B为旋转轴）ABCABC若在A的右子树的右子树上插入结点，使A的平衡因子从-1增加至-2，需要进行一次逆时针旋转。(以B为旋转轴）2 单向右旋平衡处理ABCABC1 单向左旋平衡处理9.2.2 平衡二叉树若在A的左子树的左子树上插入结点，使9.

22、2.2 平衡二叉树若在A的右子树的左子树上插入结点，使A的平衡因子从-1增加至-2，需要先进行顺时针旋转，再逆时针旋转。(以插入的结点C为旋转轴）4 右左双旋平衡处理ABCABCABC若在A的左子树的右子树上插入结点，使A的平衡因子从1增加至2，需要先进行逆时针旋转，再顺时针旋转。(以插入的结点C为旋转轴）ABCABCABC3 左右双旋平衡处理9.2.2 平衡二叉树若在A的右子树的左子树上插入结点，使9.2.2 平衡二叉树例：输入关键码序列为 16, 3, 7, 11, 9, 26, 18, 14, 15 ，插入和调整过程如下。160163+1016370-1+2左右双旋73160007311

23、0+1-116右单旋37169000-1113711269160-1-1-273161190+1+2-29.2.2 平衡二叉树例：输入关键码序列为 16, 39.2.2 平衡二叉树右左双旋左单旋181600073261190031609-171126-27390182611+116-1183+1+1716140269-111例：输入关键码序列为 16, 3, 7, 11, 9, 26, 18, 14, 15 ，插入和调整过程如下。9.2.2 平衡二叉树右左双旋左单旋181600073269.2.2 平衡二叉树例：输入关键码序列为 16, 3, 7, 11, 9, 26, 18, 14, 15

24、，插入和调整过程如下。左右双旋15-231816+2071491126-1+218730011+116150-1261499.2.2 平衡二叉树例：输入关键码序列为 16, 39.2.2 平衡二叉树二叉平衡树的适用范围 适合于组织在内存中的较小的索引(或目录)。对于存放在外存中的较大的文件系统，用二叉平衡树来组织索引不太合适。在文件检索系统中大量使用的是用B-树或B+树做文件索引。9.2.2 平衡二叉树二叉平衡树的适用范围数据结构哈希表 第三节数据结构哈希表 第三节9.3.1 哈希表的基本概念哈希查找的基本思想 在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样不经过比较，一次存取就

25、能得到所查元素的查找方法。哈希函数 在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象。哈希函数可写成：addr(ai)=H(ki) 其中：ai是表中的一个元素 addr(ai)是ai的存储地址 ki是ai的关键字9.3.1 哈希表的基本概念哈希查找的基本思想9.3.1 哈希表的基本概念哈希表 应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表。哈希查找 又叫散列查找，利用哈希函数进行查找的过程叫哈希查找。例 30个地区的各民族人口统计表编号 地区 总人口 汉族 回族.1 北京2 上

26、海.以编号作关键字，构造哈希函数：H(key)=keyH(1)=1H(2)=2以地区作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=199.3.1 哈希表的基本概念哈希表例 30个地区的各民族9.3.1 哈希表的基本概念冲突key1key2，但H(key1)=H(key2)的现象叫冲突。同义词：具有相同函数值的两个关键字，叫该哈希函数的同义词。哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法。9.3.1 哈希表的基本概念冲突9.3.2 哈希函数的构造方法直接定址

27、法构造 取关键字或关键字的某个线性函数作哈希地址，即 H(key)=key 或 H(key)=akey+b 比如：统计1-100岁的人口，用年龄做关键字，哈希函数可以就取关键字本身。特点直接定址法所得地址集合与关键字集合大小相等，不会发生冲突实际中能用这种哈希函数的情况很少9.3.2 哈希函数的构造方法直接定址法9.3.2 哈希函数的构造方法数字分析法构造 对关键字进行分析，取关键字的若干位或其组合作哈希地址。 比如：取学号某些位排定学生宿舍号。 11 0611 2 01 楼号 层号 房间号特点 适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况。9.3.2 哈希函数的构造方法数

28、字分析法9.3.2 哈希函数的构造方法例：有80个记录，关键字为8位十进制数，哈希地址为2位十进制数，怎么取合适？8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5. 分析： 只取8 只取1 只取3、4 只取2、7、5 数字分布近乎随机所以：取任意两位或两位 与另两位的叠加作哈希地址9.3.2 哈希函数的构造方法例：有80个记录，关键字为89.3.2 哈希函数的构造方法平方取中法构造：取关键字平方后中间几

29、位作哈希地址特点：适于不知道全部关键字情况折叠法构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址种类移位叠加：将分割后的几部分低位对齐相加间界叠加：从一端沿分割界来回折叠，然后对齐相加特点：适于关键字位数很多，且每一位上数字分布大致均匀情况9.3.2 哈希函数的构造方法平方取中法9.3.2 哈希函数的构造方法例 关键字为 ：0442205864，哈希地址位数为 4 5 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位叠加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092间界叠加9.3.2 哈希函数的构造方法例 关

30、键字为 ：04429.3.2 哈希函数的构造方法除留余数法构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即 H(key)=key MOD p，p m特点：简单、常用，可与上述几种方法结合使用p的选取很重要；p选的不好，容易产生同义词随机数法构造：取关键字的随机函数值作哈希地址，即H(key)=random(key)特点：适于关键字长度不等的情况9.3.2 哈希函数的构造方法除留余数法9.3.2 哈希函数的构造方法选取哈希函数应考虑的因素计算哈希函数所需时间关键字长度哈希表长度（哈希地址范围）关键字分布情况记录的查找频率9.3.2 哈希函数的构造方法选取哈希函数应考虑的因素

31、9.3.3 处理冲突的方法开放定址法方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即 Hi=(H(key)+di)MOD m， i=1,2,k(k m-1) 其中：H(key)哈希函数 m哈希表表长 di增量序列分类：线性探测再散列： di=1,2,3,m-1二次探测再散列： di=1,-1,2,-2,3,k(km/2)伪随机探测再散列： di=伪随机数序列9.3.3 处理冲突的方法开放定址法9.3.3 处理冲突的方法 例：表长为11的哈希表中已填有关键字为17，60，29的记录， H(key)=key MOD 11

32、，现有第4个记录，其关键字为38， 按三种处理冲突的方法，将它填入表中0 1 2 3 4 5 6 7 8 9 1060 17 29(1) H(38)=38 MOD 11=5 冲突 H1=(5+1) MOD 11=6 冲突 H2=(5+2) MOD 11=7 冲突 H3=(5+3) MOD 11=8 不冲突 38(2) H(38)=38 MOD 11=5 冲突 H1=(5+1) MOD 11=6 冲突 H2=(5-1) MOD 11=4 不冲突38(3) H(38)=38 MOD 11=5 冲突 设伪随机数序列为9，则： H1=(5+9) MOD 11=3 不冲突389.3.3 处理冲突的方法

33、例：表长为11的哈希表中已9.3.3 处理冲突的方法再哈希法方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，即：Hi=Rhi(key) i=1,2,k 其中：Rhi不同的哈希函数特点：计算时间增加链地址法方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针9.3.3 处理冲突的方法再哈希法9.3.3 处理冲突的方法例：已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：H(key)=key MOD 13, 用链地址法处理冲突0 1 2 3 4 5 6 7 8 9 10 11 12 1412779685519842

34、02310119.3.3 处理冲突的方法例：已知一组关键字(19,14,9.3.4 哈希查找过程及分析哈希查找过程给定k值 计算H(k) 此地址为空 关键字=k 查找失败 查找成功 按处理冲突方法计算Hi YNYN9.3.4 哈希查找过程及分析哈希查找过程给定k值 计算H9.3.4 哈希查找过程及分析哈希查找分析哈希查找过程仍是一个给定值与关键字进行比较的过程评价哈希查找效率仍要用ASL哈希查找过程与给定值进行比较的关键字的个数取决于：哈希函数处理冲突的方法哈希表的填满因 =表中填入的记录数 / 哈希表长度 越大，表中记录数越多，说明表装得越满，发生冲突的可能性就越大，查找时比较次数就越多。9

35、.3.4 哈希查找过程及分析哈希查找分析 越大，表中记9.3.4 哈希查找过程及分析9.3.4 哈希查找过程及分析9.3.4 哈希查找过程及分析例：已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：H(key)=key MOD 13, 哈希表长为m=16， 设每个记录的查找概率相等(1) 用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD mH(55)=3 冲突，H1=(3+1)MOD16=4 冲突，H2=(3+2)MOD16=5 H(79)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4 冲突，H4=(