《数据结构实例教程（C语言版）：第8章 查找的分析与应用》由会员分享，可在线阅读，更多相关《数据结构实例教程（C语言版）：第8章 查找的分析与应用（16页珍藏版）》请在金锄头文库上搜索。
1、 数据结构实例教程（数据结构实例教程（C语言版）语言版）第第8 8章查找的分析与应用章查找的分析与应用 学习目标学习目标 了解查找的基本概念。 熟练掌握线性表的顺序查找和二分法查找方法及算法 实现。 熟练掌握二叉排序树的生成和查找方法。 熟练掌握散列表的构造方法、查找过程及解决冲突的 方法。 数据结构实例教程（数据结构实例教程（C语言版）语言版）8.18.1基本概念基本概念一、查找的定义 查找的定义是：给定一个值K，在含有N个结点的表中找出关键字等于给定值K的结点。二、查找的分类 1、动态查找和静态查找 2、内查找和外查找查找的同时进行插入或者删查找的同时进行插入或者删除操作属于动态查找，相反
2、除操作属于动态查找，相反就是静态查找。就是静态查找。整个查找过程都在内存进行整个查找过程都在内存进行属于内查找，查找过程中需属于内查找，查找过程中需要访问外存属于外查找要访问外存属于外查找 。三、平均查找长度 n是结点的个数；ci是找到第i个结点所需进行的比较次数； pi是查找第i个结点的概率，一般情况下p1=p2=pn=1/n； 数据结构实例教程（数据结构实例教程（C语言版）语言版）8.28.2线性表查找线性表查找一、顺序查找 1、顺序查找的基本思想：从表的一端开始，顺序扫描线性 表，依次将扫描到结点的关键字和给定值K相比较。如 果存在，查找成功，相反，查找失败。16517016018018
3、5查找身高K=180查找成功！查找成功！ 数据结构实例教程（数据结构实例教程（C语言版）语言版）8.28.2线性表查找线性表查找一、顺序查找 2 2、顺序查找算法源程序链接、顺序查找算法源程序链接 3、顺序查找的优点 4、顺序查找的缺点 算法简单，且对表的结构无任何要求，无论是用顺序还是 链式来存放结点，也无论结点之间是否按关键字有序，它 都同样适用。 查找效率低，因此，当n较大时不宜采用顺序查找。 数据结构实例教程（数据结构实例教程（C语言版）语言版）8.28.2线性表查找线性表查找二、二分查找 1、二分查找的基本思想：每次比较有序表中的中间位置的 数据，如果不相等，有序表逐渐减小一半（如果
4、有序表 减小到空，查找失败） ，重复比较中间位置数据，找到 相等数据，查找成功。160170165180185查找身高K=180查找成功！查找成功！ 数据结构实例教程（数据结构实例教程（C语言版）语言版）8.28.2线性表查找线性表查找二、二分查找 3 3、二分查找算法源程序链接、二分查找算法源程序链接 2、二分查找的过程描述查找K=22 数据结构实例教程（数据结构实例教程（C语言版）语言版）8.28.2线性表查找线性表查找二、二分查找 4、顺序查找的优点 5、顺序查找的缺点 如果是有序表，二分查找的效率高 。二分查找适用于那种一经建立就很少改动、而又经常需要查找的线性表。 二分查找只适用顺序
5、存储结构，为保持表的有序性，在顺序结构里插入和删除必须移动大量的结点。 数据结构实例教程（数据结构实例教程（C语言版）语言版）8.28.2线性表查找线性表查找三、分块查找 1、分块查找的基本思想：首先查找索引表，因为索引表是 有序表，故可采用二分查找或顺序查找，以确定待查的 结点在哪一块，然后在已确定的块中进行顺序查找 。 2、分块查找的优点 插入、删除或查找一个记录时，只要找到该记录所属的块, 块内进行任意插入或删除。 3、分块查找的缺点增加一个辅助数组的存储空间和初始表分块排序的运算。 数据结构实例教程（数据结构实例教程（C语言版）语言版）8.38.3二叉排序树二叉排序树一、二叉排序树定义
6、 1、二叉排序树定义 ：满足以下三个性质的二叉树。若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身又各是一棵二叉排序树。 2、举例 数据结构实例教程（数据结构实例教程（C语言版）语言版）8.38.3二叉排序树二叉排序树二、二叉排序树的插入和生成 1、插入和生成 过程若二叉排序树T为空，则为待插入的关键字key申请一个新结点，并令其为根；若二叉排序树T非空，将key和根的关键字比较，若小于则将key插入根的左子树中，否则插入根的右子树中。 2、举例：已知输入数据序列4,2,5,1,3,6，生成二叉排序树。42136
7、5 3 3、二叉排序树建立算法源程序链接、二叉排序树建立算法源程序链接 数据结构实例教程（数据结构实例教程（C语言版）语言版）8.38.3二叉排序树二叉排序树三、二叉排序树的删除 1、删除的三种情况若p结点是叶子，只需将p的双亲parent中指向p的指针域 置空即可。若p结点只有一个孩子，此时只需将child和p的双亲直接连接即可，删去p。421365若p结点有两个孩子，寻找p结点中序的后继结点q替代p结点。pp6521476p33 数据结构实例教程（数据结构实例教程（C语言版）语言版）8.38.3二叉排序树二叉排序树四、二叉排序树的查找 1、查找过程：若查找成功，则是从根结点出发走了一条从
8、根到待查结点的路径；若查找不成功，则是从根结点出 发走了一条从根到某个叶子的路径。 2、查找算法 BTreeNode *SearchBST(BTreeNode *T,int key)BTreeNode *SearchBST(BTreeNode *T,int key) if(T=NULL|key=T-key) if(T=NULL|key=T-key)return T;return T; if(keykey) if(keykey)return SearchBST(T-lchild,key);return SearchBST(T-lchild,key); else else return Searc
9、hBST(T-rchild,key); return SearchBST(T-rchild,key); 数据结构实例教程（数据结构实例教程（C语言版）语言版）8.48.4散列技术散列技术一、散列表的概念 1、散列表(也叫哈希表)的定义：通过把关键码值映射到表中 一个位置来访问记录，以加快查找的速度。这个映射函数 叫散列函数，存放记录的数组叫散列表。 2、冲突的定义：对不同的关键字可能得到同一散列地址， 即k1k2，而h(k1)=h(k2） 3、同义词的定义：具有相同函数值的关键字。 数据结构实例教程（数据结构实例教程（C语言版）语言版）8.48.4散列技术散列技术二、散列函数的构造方法 1、除
10、留余数法是最为简单常用的一种方法，它是以表长m来除关键字，取余数作为散列地址，即 h(key) = key%m。该方法的关键就是选取m。m一般取为略大于元素个数的第一个素数。 2、举例：如果给出一组数据(20,30,70,14,8,12,18,60,1,11),因为 一共10个数据，那么m应该选取为略大于10的素数11， 散列函数h(key) = key%11。 012345678910203070148同义词同义词1218601同义词同义词11 数据结构实例教程（数据结构实例教程（C语言版）语言版）8.48.4散列技术散列技术三、处理冲突的方法 1、开放定址法是在表中某个存储单元发生冲突时，去探测 未存储数据的存储单元，将关键字存在空的存储单元。012345678910203070148同义词同义词1218601同义词同义词11用线性探查法解决冲突，开放地址法的公式为：h(key)=(h(key)+i)%m i=1,2,m-1 数据结构实例教程（数据结构实例教程（C语言版）语言版）8.48.4散列技术散列技术三、处理冲突的方法 2、拉链法是将散列表中地址相同的关键字链接形成一个单 链表，每个单链表第一个结点的地址对应存储在散列表 相应的存储单元中。
