数据结构(c++)(第08章

《数据结构(c++)(第08章》由会员分享，可在线阅读，更多相关《数据结构(c++)(第08章（80页珍藏版）》请在金锄头文库上搜索。

1、第8章 查找本章学习内容 8.1 查找的基本概念8.2 线性表的查找8.3 树表查找8.4 散列查找*18.1 查找的基本概念在前面几章中，我们介绍了线性表、栈和队列、串等线性结构及多维数组、广 义表、树和图等非线性结构，讨论了它们的逻辑结构、存储结构及运算，并且 在运算中，曾经讨论过一些简单的查找运算。但由于查找运算的使用频率相当 高，几乎在任何一个计算机系统中都会涉及到，所以当问题的规模相当大时， 查找算法的效率就显得十分重要。因此，本章将着重讨论各种查找方法，并通 过对它们的效率分析来比较各种查找方法的优劣。查找，也称为检索。在我们的日常生活中，随处可见查找的实例。如查找某人的 地址、电

2、话号码；查某单位45岁以上职工等，都属于查找范畴。本书中，我们 规定查找是按关键字进行的。所谓关键字（key）是数据元素（或记录）中某个 数据项的值，用它可以标识（或识别）一个数据元素。例如，描述一个考生的信 息，可以包含：考号、姓名、性别、年龄、家庭住址、电话号码、成绩等关键字 。但有些关键字不能惟一标识一个数据元素，而有的关键字可以惟一标识一个数 据元素。如刚才的考生信息中，姓名不能惟一标识一个数据元素（因有同名同姓 的人），而考号可以惟一标识一个数据元素（每个考生考号是惟一的，不能相同 ）。我们将能惟一标识一个数据元素的关键字称为主关键字，而其他关键字称为 辅助关键字或从关键字。*2有了

3、主关键字及关键字后，我们可以给查找下一个完整的定义。所谓查找，就是根 据给定的值，在一个表中查找出其关键字等于给定值的数据元素，若表中有这样的 元素，则称查找是成功的，此时查找的信息为给定整个数据元素的输出或指出该元 素在表中的位置；若表中不存在这样的记录，则称查找是不成功的，或称查找失败 ，并可给出相应的提示。因为查找是对已存入计算机中的数据所进行的操作，所以采用何种查找方法，首先 取决于使用哪种数据结构来表示“表”，即表中结点是按何种方式组织的。为了提高查 找速度，我们经常使用某些特殊的数据结构来组织表。因此在研究各种查找算法时 ，我们首先必须弄清这些算法所要求的数据结构，特别是存储结构。

4、查找有内查找和外查找之分。若整个查找过程全部在内存进行，则称这样的查找为 内查找；反之，若在查找过程中还需要访问外存，则称之为外查找。我们仅介绍内 查找。*3要衡量一种查找算法的优劣，主要是看要找的值与关键字的比较次数，我们将找 到给定值与关键字的比较次数的平均值来作为衡量一个查找算法好坏的标准，对 于一个含有n个元素的表，查找成功时的平均查找长度可表示为ASL= ， 其中pi为查找第i个元素的概率，且 =1。一般情形下我们认为查找每个元 素的概率相等，ci为查找第i个元素所用到的比较次数。*48.2 线性表的查找 8.2.1 顺序查找1顺序查找的基本思想顺序查找是一种最简单的查找方法，它的基

5、本思想是：从表的一端开始， 顺序扫描线性表，依次将扫描到的结点关键字和待找的值相比较，若相 等，则查找成功，若整个表扫描完毕，仍未找到关键字等于的元素，则 查找失败。顺序查找既适用于顺序表，也适用于链表。若用顺序表，查找可从前往后扫 描，也可从后往前扫描，但若采用单链表，则只能从前往后扫描。另外，顺 序查找的表中元素可以是无序的。下面以顺序表的形式来描述算法。*52顺序查找算法实现const int n=maxn/n为表的最大长度 struct node elemtype key;/key为关键字，类型设定为elemtype ;int seqsearch (node Rn+1,elemtype

6、 k) /在表R中查找关键字值为k的元素 R0.key=k; int i=n; /从表尾开始向前扫描 while(Ri.key!=k) i-; return i; *6在函数seqsearch中，若返回的值为表示查找不成功，否则查找成功。函数中查 找的范围从Rn到R1，R0为监视哨，起两个作用：其一，是为了省去判定while 循环中下标越界的条件i1，从而节省比较时间；其二，保存要找值的副本，若查 找时遇到它，表示查找不成功。 若算法中不设立监视哨R0，程序花费的时间将会增加，这时的算法可写为下面 的形式：int seqsearch(node Rn+1，elemtype k) int i=n;

7、 while(Ri.key!=k) return i; 当然上面的算法也可以改成从表头向后扫描，将监视哨设在右边，这种方法请读者 自己完成。*73顺序查找性能分析假设在每个位置查找的概率相等，即有pi=1/n，由于查找是从后往前扫描，则有每 个位置的查找比较次数cn=1，cn-1=2，c1=n，于是，查找成功的平均查找 ASL= = = ， 即它的时间复杂度为O(n)。 这就是说，查找成功的平均比较次数约为表长的一半。若k值不在表中，则必须 进行n+1次比较之后才能确定查找失败。另外，从ASL可知，当n较大时，ASL值 较大，查找的效率较低。顺序查找的优点是算法简单，对表结构无任何要求，无论是

8、用向量还是用链表来 存放结点，也无论结点之间是否按关键字有序或无序，它都同样适用。顺序查找 的缺点是查找效率低，当n较大时，不宜采用顺序查找，而必须寻求更好的查找方 法。*88.2.2 二分查找1二分查找的基本思想二分查找，也称折半查找，它是一种高效率的查找方法。但二分查找有条件限制 ：要求表必须用向量作存储结构，且表中元素必须按关键字有序（升序或降序均 可）。我们不妨假设表中元素为升序排列。 二分查找的基本思想是：首先将待查值k与有序表R1Rn的中点mid上的关键 字Rmid.key进行比较，若相等，则查找成功；否则，若Rmid.keyk，则在 R1Rmid-1中继续查找，若有Rmid.ke

9、yk)high=mid-1; /在左子区间中查找else low=mid+1; /在右子区间中查找 return 0; /查找失败 例如，假设给定有序表中关键字为8,17,25,44,68,77,98,100,115,125，将查找 k=17和k=120的情况描述为图8-1和图8-2的形式。*10图8-1 查找k=17的示意图（查找成功）*11（a）初始情形（b）经过一次比较后的情形（c）经过二次比较后的情形（d）经过三次比较后的情形（e）经过四次比较后的情形（high data = X;p-left=p-right=NULL;BST=p;else if (BST-data = X )Inse

10、rt ( BST - left,X); /在左子树中插入else Insert (BST-right,X); /在右子树中插入 *29（2）二叉排序树的建立只要反复调用二叉排序树的插入算法即可，算法描述为：btreenode *Creat (int n) /建立含有n个结点的二叉排序树 btreenode *BST= NULL; for ( int i=1; ix; /输入关键字序列 Insert( BST,x); return BST ; 例如，结定关键字序列79，62，68，90，88，89，17，5，100，120，生成二叉 排序树的过程如图8-6所示。（注：二叉排序树与关键字排列顺序有

11、关，排列顺序 不一样，得到的二叉排序树也不一样）。*30（a） （b） （c） （d） （e） （f） （g） （h） （i） （j） 图8-6 二叉排序树的生成过程*31（3）二叉排序树的删除二叉排序树的删除比插入要复杂得多，因为被插入的结点都被链接到树中的叶子 结点上，故不会破坏树的结构，而删除则不同，它可能是删除叶子结点，也可能 是删除非叶子结点，当删除非叶子结点时，就会破坏原有结点的链接关系，需要 重新修改指针，使得删除后仍为一棵二叉排序树。具体算法 见书中。4二叉排序树上的查找（1）二叉排序树的查找思想若二叉排序树为空，则查找失败，否则，先拿根结点值与待查值进行比较，若相 等，则查找

12、成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进 入右子树重复此步骤，若在查找过程中遇到二叉排序树的叶子结点时，还没有找 到待找结点，则查找不成功。*32（2）二叉排序树查找的算法实现treenode * find( btreenode *BST,elemtype x) /在以BST为根指针的二叉排序树中查找值为x的结点 if ( BST=NULL)return NULL; /查找失败else if (BST-data=x) /查找成功return BST;else if (BST-datax) /进入左子树查找return find ( BST-left,x);else /进入右

13、子树查找return find (BST-right,x);*33当然，上述算法也可以改成如下的非递归算法：btreenode * find1 ( btreenode *BST, elemtype x ) if(BST=NULL)return NULL; /查找失败else btreenode p=BST;while (p!=NULL) if (p-data=x) break;else if (p-datax) p=p-left;else p=p-right; if(p!=NULL) return P; /查找成功 else return NULL; /查找不成功 *345二叉排序树查找的性能

14、分析在二叉排序树查找中，成功的查找次数不会超过二叉树的深度，而具有n个 结点的二叉排序树的深度，最好为log2n，最坏为n。因此，二叉排序树查 找的最好时间复杂度为O(log2n)，最坏时间复杂度为O(n)，一般情形下， 其时间复杂度大致可看成O(log2n)，比顺序查找效率要好，但比二分查找 要差。【例8-1】给定关键字序列1,2,3，试写出它的所有二叉排序树。分析：由于关键字序列1,2,3，有6种排列，故最多有6棵二叉排序树。第一棵的关键字序列为1,2,3，生成的二叉排序树见图8-7（a）； 第二棵的关键字序列为1,3,2，生成的二叉排序树见图8-7（b）； 第三棵的关键字序列为2,1,3，生成的二叉排序树见图8-7（c）； 第四棵的关键字序列为2,3,1，生成的二叉排序树见图8-7（d）； 第五棵的关键字序列为3,2,1，生成的二叉排序树见图8-7（e）； 第六棵的关键字序列为3,1,2，生成的二叉排序树见图8-7（f）。*35（a） （b