《数据结构教程（第3版）四ppt》由会员分享，可在线阅读，更多相关《数据结构教程（第3版）四ppt（238页珍藏版）》请在金锄头文库上搜索。
1、数据结构教程（第3版）四,第10章 查找,10.1 查找的基本概念,本章小结,10.2 线性表的查找,10.3 树表的查找,10.4 哈希表查找,10.1 查找的基本概念 被查找的对象是由一组记录组成的表或文件,而每个记录则由若干个数据项组成,并假设每个记录都有一个能惟一标识该记录的关键字。 在这种条件下,查找的定义是：给定一个值k,在含有n个记录的表中找出关键字等于k的记录。若找到,则查找成功,返回该记录的信息或该记录在表中的位置；否则查找失败,返回相关的指示信息。,采用何种查找方法? (1) 使用哪种数据结构来表示“表”,即表中记录是按何种方式组织的。 (2) 表中关键字的次序。是对无序集
2、合查找还是对有序集合查找?,若在查找的同时对表做修改运算(如插入和删除),则相应的表称之为动态查找表,否则称之为静态查找表。,由于查找运算的主要运算是关键字的比较,所以通常把查找过程中对关键字需要执行的平均比较次数(也称为平均查找长度)作为衡量一个查找算法效率优劣的标准。平均查找长度ASL(Average Search Length)定义为：,其中,n是查找表中记录的个数。pi是查找第i个记录的概率,一般地,均认为每个记录的查找概率相等,即pi=1/n(1in),ci是找到第i个记录所需进行的比较次数。,10.2 线性表的查找 在表的组织方式中,线性表是最简单的一种。三种在线性表上进行查找的方
3、法： (1) 顺序查找 (2) 二分查找 (3) 分块查找。 因为不考虑在查找的同时对表做修改,故上述三种查找操作都是在静态查找表上实现的。,查找与数据的存储结构有关,线性表有顺序和链式两种存储结构。本节只介绍以顺序表作为存储结构时实现的顺序查找算法。定义被查找的顺序表类型定义如下： #define MAXL typedef struct KeyType key; /*KeyType为关键字的数据类型*/ InfoType data; /*其他数据*/ NodeType; typedef NodeType SeqListMAXL; /*顺序表类型*/,10.2.1 顺序查找 顺序查找是一种最简
4、单的查找方法。 它的基本思路是：从表的一端开始,顺序扫描线性表,依次将扫描到的关键字和给定值k相比较,若当前扫描到的关键字与k相等,则查找成功；若扫描结束后,仍未找到关键字等于k的记录,则查找失败。,例如,在关键字序列为3,9,1,5,8,10,6,7,2,4的线性表查找关键字为6的元素。 顺序查找过程如下：,开始: 3 9 1 5 8 10 6 7 2 4 第1次比较: 3 9 1 5 8 10 6 7 2 4 i=0 第2次比较: 3 9 1 5 8 10 6 7 2 4 i=1 第3次比较: 3 9 1 5 8 10 6 7 2 4 i=2 第4次比较: 3 9 1 5 8 10 6 7
5、 2 4 i=3 第5次比较: 3 9 1 5 8 10 6 7 2 4 i=4 第6次比较: 3 9 1 5 8 10 6 7 2 4 i=5 第7次比较: 3 9 1 5 8 10 6 7 2 4 i=6 查找成功,返回序号6,顺序查找的算法如下(在顺序表R0n-1中查找关键字为k的记录,成功时返回找到的记录位置,失败时返回-1)： int SeqSearch(SeqList R,int n,KeyType k) int i=0; while (i=n) return -1; else return i; ,从顺序查找过程可以看到(不考虑越界比较in),ci取决于所查记录在表中的位置。如查
6、找表中第1个记录R0时,仅需比较一次；而查找表中最后一个记录Rn-1时,需比较n次,即ci=i。因此,成功时的顺序查找的平均查找长度为：,查找成功时的平均比较次数约为表长的一半 。,10.2.2 二分查找 二分查找也称为折半查找要求线性表中的结点必须己按关键字值的递增或递减顺序排列。它首先用要查找的关键字k与中间位置的结点的关键字相比较,这个中间结点把线性表分成了两个子表,若比较结果相等则查找完成;若不相等,再根据k与该中间结点关键字的比较大小确定下一步查找哪个子表,这样递归进行下去,直到找到满足条件的结点或者该线性表中没有这样的结点。,例如,在关键字有序序列2,4,7,9,10,14,18,
7、26,32,40中采用二分查找法查找关键字为7的元素。 二分查找过程如下：,开始: 2 4 7 9 10 14 18 26 32 40 low=0 high=9 mid=(0+9)/2=4 第1次比较: 2 4 7 9 10 14 18 26 32 40 low=0 high=3 mid=(0+3)/2=1 第2次比较: 2 4 7 9 10 14 18 26 32 40 low=2 high=3 mid=(2+3)/2=2 第3次比较: 2 4 7 9 10 14 18 26 32 40 R2.key=7 查找成功,返回序号2,其算法如下(在有序表R0n-1中进行二分查找,成功时返回记录的位
8、置,失败时返回-1)： int BinSearch(SeqList R,int n,KeyType k) int low=0,high=n-1,mid; while (lowk) /*继续在Rlowmid-1中查找*/ high=mid-1; else low=mid+1; /*继续在Rmid+1high中查找*/ return -1; ,二分查找过程可用二叉树来描述,我们把当前查找区间的中间位置上的记录作为根,左子表和右子表中的记录分别作为根的左子树和右子树,由此得到的二叉树,称为描述二分查找的判定树或比较树。,R010的二分查线的判定树(n=11),例10.1对于给定11个数据元素的有序表
9、2,3,10,15,20,25,28,29,30,35,40,采用二分查找,试问： (1)若查找给定值为20的元素,将依次与表中哪些元素比较？ (2)若查找给定值为26的元素,将依次与哪些元素比较？ (3)假设查找表中每个元素的概率相同,求查找成功时的平均查找长度和查找不成功时的平均查找长度。,二分查找判定树,(2)若查找给定值为26的元素,依次与25,30,28元素比较,共比较3次。 (3)在查找成功时,会找到图中某个圆形结点,则成功时的平均查找长度：,(1)若查找给定值为20的元素,依次与表中25,10,15,20元素比较,共比较4次。,在查找不成功时,会找到图中某个方形结点,则不成功时的
10、平均查找长度：,10.2.3 分块查找 分块查找又称索引顺序查找,它是一种性能介于顺序查找和二分查找之间的查找方法。 它要求按如下的索引方式来存储线性表：将表R0n-1均分为b块,前b-1块中记录个数为s=n/b,最后一块即第b块的记录数小于等于s；每一块中的关键字不一定有序,但前一块中的最大关键字必须小于后一块中的最小关键字,即要求表是“分块有序”的；抽取各块中的最大关键字及其起始位置构成一个索引表IDX0b-1,即IDXi(0ib-1)中存放着第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的,所以索引表是一个递增有序表。,索引表的数据类型定义如下： #define MAXI
11、 typedef struct KeyType key; /*KeyType为关键字的类型*/ int link; /*指向对应块的起始下标*/ IdxType; typedef IdxType IDXMAXI; /*索引表类型*/,例如,设有一个线性表,其中包含25个记录,其关键字序列为8,14,6,9,10,22,34,18,19,31,40,38,54,66, 46,71,78,68,80,85,100, 94,88,96,87。假设将25个记录分为5块,每块中有5个记录,该线性表的索引存储结构如下图所示。,采用二分查找索引表的分块查找算法如下(索引表I的长度为m)： int IdxSe
12、arch(IDX I,int m,SeqList R,int n,KeyType k) int low=0,high=m-1,mid,i; int b=n/m; /*b为每块的记录个数*/ while (low=k) high=mid-1; else low=mid+1; ,if (lowm) /*在块中顺序查找*/ i=Ilow.link; while (i=Ilow.link+b-1 ,若以二分查找来确定块,则分块查找成功时的平均查找长度为：,若以顺序查找确定块,则分块查找成功时的平均查找长度为：,10.3 树表的查找 当表的插入或删除操作频繁时,为维护表的有序性,需要移动表中很多记录。这
13、种由移动记录引起的额外时间开销,就会抵消二分查找的优点。也就是说,二分查找只适用于静态查找表。若要对动态查找表进行高效率的查找,可采用下面介绍的几种特殊的二叉树或树作为表的组织形式,在这里将它们统称为树表。下面将分别讨论在这些树表上进行查找和修改操作的方法。,10.3.1 二叉排序树 二叉排序树(简称BST)又称二叉查找(搜索)树,其定义为：二叉排序树或者是空树,或者是满足如下性质的二叉树： (1) 若它的左子树非空,则左子树上所有记录的值均小于根记录的值； (2) 若它的右子树非空,则右子树上所有记录的值均大于根记录的值； (3) 左、右子树本身又各是一棵二叉排序树。,在讨论二叉排序树上的运
14、算之前,定义其结点的类型如下： typedef struct node /*记录类型*/ KeyType key; /*关键字项*/ InfoType data; /*其他数据域*/ struct node *lchild,*rchild; /*左右孩子指针*/ BSTNode;,1. 二叉排序树上的查找 因为二叉排序树可看做是一个有序表,所以在二叉排序树上进行查找,和二分查找类似,也是一个逐步缩小查找范围的过程。递归查找算法SearchBST()如下(在二叉排序树bt上查找关键字为k的记录,成功时返回该结点指针,否则返回NULL)： BSTNode *SearchBST(BSTNode *b
15、t,KeyType k) if (bt=NULL | bt-key=k) /*递归终结条件*/ return bt; if (kkey) return SearchBST(bt-lchild,k); /*在左子树中递归查找*/ else return SearchBST(bt-rchild,k); /*在右子树中递归查找*/ ,2. 二叉排序树的插入和生成 在二叉排序树中插入一个新记录,要保证插入后仍满足BST性质。其插入过程是：若二叉排序树T为空,则创建一个key域为k的结点,将它作为根结点；否则将k和根结点的关键字比较,若二者相等,则说明树中已有此关键字k,无须插入,直接返回0；若kkey,则将k插入根结点的左子树中,否则将它插入右子树中。对应的递归算法InsertBST()如下：,int InsertBST(BSTNode * /*插入到右子树中*/ ,二叉排序树的生成,是从一个空树开始,每插入一个关键字,就调用一次插入算法将它插入到当前已生成的二叉排序树中。从关键字数组A0n-1生成二叉排序树的算法CreatBST()如下： BSTNode *CreatBST(KeyType A,int n) /*返回树根指针*/ BSTNode *bt=NULL; /*初始时bt为空树*/ int i=0; while (in) InsertBST(bt,Ai); /*将Ai插入
