数据结构第七章查找

第七章 查找Review 单源最短路径单源最短路径 DistDist和和pathpath数组数组 图的遍历图的遍历 广度优先搜索广度优先搜索 宽度优先搜索宽度优先搜索查找 查找表查找表 由同一类型的数据元素构成的集合由同一类型的数据元素构成的集合 关键字关键字 数据元素中某个数据项的值，可以标示一个数据元素数据元素中某个数据项的值，可以标示一个数据元素 查找查找 根据给定的某个值，在查找表中确定一个其关键字等根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录于给定值的记录查找方法 如何查找？如何查找？ 取决于表中数据元素依据何种关系组织在一起取决于表中数据元素依据何种关系组织在一起动态查找动态查找静态查找静态查找顺序查找 最简单的查找方法最简单的查找方法 从线性表的一端开始，顺序扫描线性表，依次将从线性表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值扫描到的结点关键字和给定值k k相比较相比较 当前扫描到的元素关键字与当前扫描到的元素关键字与k k相等，则查找成功相等，则查找成功 若扫描结束后，仍未找到关键字等于若扫描结束后，仍未找到关键字等于k k的结点，则查的结点，则查找失败找失败顺序查找 例例7.17.1在关键字序列为在关键字序列为3,9,1,5,8,10,6,7,2,43,9,1,5,8,10,6,7,2,4的线性表中从前往后查的线性表中从前往后查找关键字为找关键字为6 6的元素的元素顺序查找 例例7.17.1在关键字序列为在关键字序列为3,9,1,5,8,10,6,7,2,43,9,1,5,8,10,6,7,2,4的线性表中从前的线性表中从前往后查找关键字为往后查找关键字为6 6的元素的元素解：顺序查找过程如下图所示：解：顺序查找过程如下图所示： 开始开始 3 9 1 5 8 10 6 7 2 43 9 1 5 8 10 6 7 2 4 第一次第一次 3 9 1 5 8 10 6 7 2 43 9 1 5 8 10 6 7 2 4i=0i=0 第二次第二次 3 9 1 5 8 10 6 7 2 43 9 1 5 8 10 6 7 2 4i=1i=1 第三次第三次 3 9 1 5 8 10 6 7 2 43 9 1 5 8 10 6 7 2 4i=2i=2顺序查找 第四次第四次 3 9 1 5 8 10 6 7 2 43 9 1 5 8 10 6 7 2 4i=3i=3 第五次第五次 3 9 1 5 8 10 6 7 2 43 9 1 5 8 10 6 7 2 4i=4i=4 第六次第六次 3 9 1 5 8 10 6 7 2 43 9 1 5 8 10 6 7 2 4i=5i=5 第七次第七次 3 9 1 5 8 10 6 7 2 43 9 1 5 8 10 6 7 2 4i=6i=6 查找成功，返回序号查找成功，返回序号6 6顺序查找算法int SeqSearch( LineList R , int n , KeyType k )int SeqSearch( LineList R , int n , KeyType k ) int i = 0 ; int i = 0 ; while( in & while( i= n ) if( i= n ) else else return -1 ; return -1 ; return i ; return i ;查找的性能分析 时间复杂度时间复杂度 空间复杂度空间复杂度 平均查找长度平均查找长度 为确定记录在查找表中的位置，需为确定记录在查找表中的位置，需和给定值进和给定值进行比较的关键字个数行比较的关键字个数的的期望值期望值顺序查找-平均查找长度 含有含有n n个元素的线性表，元素查找在个元素的线性表，元素查找在等概率等概率的前提下，查的前提下，查找成功的概率找成功的概率p pi i=1/n=1/n 第第i i个元素个元素( (序号为序号为i-1i-1的元素的元素) )查找成功需比较查找成功需比较i i次次 查找成功时的平均查找长度查找成功时的平均查找长度nnsucciii 1i 111n1ASLp C*i(12.n)O(n)nn2二分查找 先确定待查记录所在的范围，然后逐步缩小范围先确定待查记录所在的范围，然后逐步缩小范围直到找到或找不到该记录直到找到或找不到该记录 要求线性表中的元素必须已按要求线性表中的元素必须已按关键字递增或递减关键字递增或递减顺序排列顺序排列二分查找 用查找的关键字用查找的关键字k k与线性表与线性表中间位置中间位置的元素的关键的元素的关键字相比较字相比较 这个中间元素把线性表分成了两个子表这个中间元素把线性表分成了两个子表 若比较结果相等则查找完成若比较结果相等则查找完成 若不相等再根据若不相等再根据k k与该中间元素的关键字比较的结果与该中间元素的关键字比较的结果确确定下一步查找哪个子表定下一步查找哪个子表 这样递归进行下去，直到找到满足条件的元素或这样递归进行下去，直到找到满足条件的元素或该线性表中没有这样的元素该线性表中没有这样的元素二分查找 算法思想（默认线性表是递增的）算法思想（默认线性表是递增的）设表长为设表长为n n，lowlow、highhigh和和midmid分别指向待查元素所在区间的分别指向待查元素所在区间的上界、下界和中点上界、下界和中点, ,k k为给定值为给定值初始时，令初始时，令low=low=0 0,high=,high=n-1n-1,mid=,mid= (low+high)/2(low+high)/2 让让k k与与midmid指向的记录比较指向的记录比较若若k=rmid.keyk=rmid.key，查找成功查找成功若若krmid.keykrmid.keykrmid.key，则则low=mid+1low=mid+1 例例7.17.1在在关键字有序序列关键字有序序列为为2,4,7,9,10,14,18,26,32,402,4,7,9,10,14,18,26,32,40中采用中采用二分查找法查找关键字为二分查找法查找关键字为7 7的元素的元素解：二分查找过程如下图所示解：二分查找过程如下图所示 开始开始 2 4 7 9 10 14 18 26 32 402 4 7 9 10 14 18 26 32 40low=0low=0high=9high=9 第一次第一次 2 4 7 9 10 14 18 26 32 402 4 7 9 10 14 18 26 32 40low=0low=0high=3high=3mid=4mid=4二分查找 第二次第二次 2 4 7 9 10 14 18 26 32 402 4 7 9 10 14 18 26 32 40low=2low=2high=3high=3 第三次第三次 2 4 7 9 10 14 18 26 32 402 4 7 9 10 14 18 26 32 40mid=2mid=2mid=1mid=1二分查找 查找成功，返回序号查找成功，返回序号2 2 二分查找过程构造一个树，把当前查找区间的二分查找过程构造一个树，把当前查找区间的中间位置上的记中间位置上的记录作为根录作为根，左子表和右子表中的记录分别作为根的左子树和右子树，左子表和右子表中的记录分别作为根的左子树和右子树0-9 R40-9 R40-3 R20-3 R25-9 R75-9 R70-1 R00-1 R03-3 R33-3 R31-1 R11-1 R15-6 R55-6 R58-9 R88-9 R86-6 R66-6 R69-9 R99-9 R9二分查找判定树二分查找判定树 成功的二分查找过程恰好是走了一条成功的二分查找过程恰好是走了一条从判定树的根到被查从判定树的根到被查记录记录的路径，经历的路径，经历比较的关键字次数比较的关键字次数恰好为恰好为该记录在树中该记录在树中的层数的层数 若查找失败，则其比较过程是经历了一条从判定树根到某若查找失败，则其比较过程是经历了一条从判定树根到某个外部结点的路径，所需的关键字比较次数是该路径上内个外部结点的路径，所需的关键字比较次数是该路径上内部结点的总数部结点的总数 在二分查找过程中，关键字与在二分查找过程中，关键字与k k每比较一次每比较一次查找范围就缩小一半查找范围就缩小一半 比较次数与可能涉及的元素个数之间的关系比较次数与可能涉及的元素个数之间的关系比较次数比较次数 1 2 3 4 1 2 3 4 j j可能涉及的元素个数可能涉及的元素个数 1 2 4 8 21 2 4 8 2j-1j-1 n n为有序表中元素个数为有序表中元素个数 则二分查找的最大查找长度为：则二分查找的最大查找长度为：22jlo g(n1)lo gn二分查找判定树lowhighmid例例 0 1 2 3 4 5 6 7 8 9 105 13 19 21 37 56 64 75 80 88 92找找210 1 2 3 4 5 6 7 8 9 105 13 19 21 37 56 64 75 80 88 92lowhighmid0 1 2 3 4 5 6 7 8 9 105 13 19 21 37 56 64 75 80 88 92lowhighmid二分查找判定树例例 0 1 2 3 4 5 6 7 8 9 105 13 19 21 37 56 64 75 80 88 92lowhighmid找找700 1 2 3 4 5 6 7 8 9 105 13 19 21 37 56 64 75 80 88 92lowhighmid0 1 2 3 4 5 6 7 8 9 105 13 19 21 37 56 64 75 80 88 92lowhighmid二分查找判定树0 1 2 3 4 5 6 7 8 9 105 13 19 21 37 56 64 75 80 88 92low highmid0 1 2 3 4 5 6 7 8 9 105 13 19 21 37 56 64 75 80 88 92lowhigh二分查找判定树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 60 58 74 57 86 5322 48 861 7 13索引表分块查找分块查找 又称索引顺序查找，其性能介于顺序查找和二分查找之间又称索引顺序查找，其性能介于顺序查找和二分查找之间 把线性表分为若干块，把线性表分为若干块，每一块中的元素存储顺序是任意每一块中的元素存储顺序是任意的的，但，但块与块之间块与块之间必须按必须按关键字大小有序关键字大小有序排列排列 建立一个索引表建立一个索引表 索引项由关键字域和链域组成索引项由关键字域和链域组成 关键字域存放相应块的关键字域存放相应块的最大最大关键字关键字 链域存放指向本块链域存放指向本块第一个元素第一个元素的指针的指针 索引表按关键字递增索引表按关键字递增( (或递减或递减) )顺序排列顺序排列分块查找 查找过程查找过程 将表分成几块，将表分成几块，块内无序，块间有序块内无序，块间有序 先确定待查记录所在块，再在块内查找先确定待查记录所在块，再在块内查找 算法思想算法思想 用数组存放待查记录用数组存放待查记录, ,每个数据元素至少含有关键字域每个数据元素至少含有关键字域 建立建立索引表索引表，每个索引表结点含有最大关键字域和指向本，每个索引表结点含有最大关键字域和指向本块第一个结点的指针块第一个结点的指针 例例7.3 7.3 对于关键字序列为对于关键字序列为 9,22,12,14,35,42,44,38,48,60,58,47,78,80,77,829,22,12,14,35,42,44,38,48,60,58,47,78,80,77,82的线的线性表采用分块查找法查找关键字为性表采用分块查找法查找关键字为4848的元素的元素假设其分块索引和索引表如下图所示：假设其分块索引和索引表如下图所示：序号序号0 01 12 23 34 45 56 67 78 89 9101011111212131314141515关键关键字字9 9222212121414353542424444383848486060585847477878808077778282keykeylowlowhighhigh22220 03 344444 47 760608 81111828212121515 采用采用二分查找法二分查找法查找关键字查找关键字4848所在的块所在的块 该块元素，其关键字分别为该块元素，其关键字分别为4848，6060，5858，4747，在其中按，在其中按顺序查找法顺序查找法进行查找进行查找分块查找算法分析 假设有假设有n n个元素，分成个元素，分成bnbn块，每块有块，每块有s s个元素，即个元素，即bn=n/s,bn=n/s,每块的查找概率为每块的查找概率为1/bn,1/bn,块内每个元素的块内每个元素的查找概率为查找概率为1/s1/s。平均查找长度为。平均查找长度为2/) 1/(log2ssnASL1 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 60 58 74 57 86 5322 48 861 7 13索引表索引表查查38分块查找breakReview 查找查找 平均查找长度平均查找长度 顺序查找顺序查找 二分查找二分查找 分块查找分块查找练习 假设按下述递归方法进行顺序表的查找：若表长假设按下述递归方法进行顺序表的查找：若表长 1010，则进行顺序查找，否则进行二分查找。试，则进行顺序查找，否则进行二分查找。试画出对表长画出对表长n=50n=50的顺序表进行上述查找时，描述的顺序表进行上述查找时，描述该查找的判定树，并求出等概率情况下查找成功该查找的判定树，并求出等概率情况下查找成功的平均查找长度的平均查找长度动态查找 表结构本身在查找过程中动态生成表结构本身在查找过程中动态生成 给定值给定值keykey，若表中存在其关键字等于，若表中存在其关键字等于keykey的记录的记录，则查找成功返回，否则插入关键字等于，则查找成功返回，否则插入关键字等于keykey的的记录记录二叉排序树 或者是一棵空树，或者是一棵具有如下特性的非或者是一棵空树，或者是一棵具有如下特性的非空二叉树：空二叉树： 若它的若它的左子树左子树非空，则左子树上所有结点的关键字均非空，则左子树上所有结点的关键字均小于小于根结点的关键字根结点的关键字 若它的右子树非空，则若它的右子树非空，则右子树右子树上所有结点的关键字均上所有结点的关键字均大于大于根结点的关键字根结点的关键字 左，右子树本身又各是一棵二叉排序树左，右子树本身又各是一棵二叉排序树二叉排序树 如下图所示的二叉树是一棵二叉排序树如下图所示的二叉树是一棵二叉排序树10106 612123 38 820209 915152525二叉排序树的基本运算 查找结点查找结点 插入结点插入结点 创建二叉排序树创建二叉排序树 输出二叉排序树输出二叉排序树 删除结点删除结点查找结点 采用不回溯的方法采用不回溯的方法若若k k等于当前结点的关键字，则返回等于当前结点的关键字，则返回若若k k小于当前结点的关键字，则在左子树中查找小于当前结点的关键字，则在左子树中查找若若k k大于当前结点的关键字，则在右子树中查找大于当前结点的关键字，则在右子树中查找10106 612123 38 820209 915152525btbtbt1bt1bt2bt2bt3bt3查找关键字为查找关键字为9 9的结点的结点插入结点 用用f f指回其双亲结点，若指回其双亲结点，若p p为为NULLNULL，表示插入关键，表示插入关键字为字为k k的结点为的结点为* *f f的左或右孩子结点的左或右孩子结点 创建关键字为创建关键字为k k的结点的结点* *p p，再插入，再插入* *p p结点结点10106 612123 38 820209 915152525btbtbt1bt1bt2bt2bt3bt3插入关键字为插入关键字为7 7的结点的结点创建二叉排序树BSTNode BSTNode * *BSTSearch(BSTNode BSTSearch(BSTNode * *&bt , KeyType str, int n)&bt , KeyType str, int n) bt = NULL ;bt = NULL ;int i = 0 ;int i = 0 ;while( i n )while( i n ) BSTInsert( bt , stri ) ;BSTInsert( bt , stri ) ;i+i+；创建二叉排序树 关键字序列为关键字序列为1010，6 6，1212，8 8，3 3，2020，9 9，2525，151510106 612123 38 820209 915152525删除结点 在二叉排序树在二叉排序树btbt中删除关键字为中删除关键字为k k的结点的结点 首先在二叉排序树中查找关键字为首先在二叉排序树中查找关键字为k k的结点的结点p,p,用用f f指向指向其双亲结点其双亲结点 若若* *p p结点结点无左子树无左子树，则用，则用* *p p结点的结点的右孩子右孩子替换它替换它 若若* *p p结点结点无右子树无右子树，则用，则用* *p p结点的结点的左孩子左孩子替换它替换它 若若* *p p结点结点既有左子树又有右子树既有左子树又有右子树，则可以用，则可以用* *p p结点的结点的左子树的最右下结点左子树的最右下结点替换它，也可以用替换它，也可以用* *p p结点的右子结点的右子树的最左下结点替换它，这里采用前者树的最左下结点替换它，这里采用前者10106 612123 38 820209 9151525259 96 612123 38 8202015152525删除后的二叉排序树删除后的二叉排序树二叉排序树的插入和删除操作，其平均执行时间均为二叉排序树的插入和删除操作，其平均执行时间均为O(logO(log2 2n)n)删除结点删除关键字为删除关键字为1010的结点的结点哈希表 在元素的在元素的存储位置和其关键字存储位置和其关键字之间建立某种直接之间建立某种直接关系关系 哈希表通过对元素的关键字值进行某种运算，哈希表通过对元素的关键字值进行某种运算，直直接求出元素的地址接求出元素的地址，而不需要反复比较。又叫，而不需要反复比较。又叫散散列法列法哈希表 哈希函数哈希函数利用函数利用函数H H将数据集中的元素将数据集中的元素映射映射到表到表A A中，中， H(H(k ki i) )便是便是k ki i在表中的在表中的存储位置存储位置 冲突现象冲突现象保证对于任意不同的保证对于任意不同的k ki i和和k kj j，有，有 。若若 , ,而而H(H(k ki i)=H()=H(k kj j) )的现象称为的现象称为冲突现象冲突现象)()(jikHkHjikk 哈希表的构造方法 直接地址法直接地址法 H(H(k ki i) = a ) = a k ki i + b + b ( ( a,ba,b是常量是常量) ) 数学分析法数学分析法假设有一组关键字，每个关键字由假设有一组关键字，每个关键字由n n为数字组成，如为数字组成，如k k1 1k k2 2k kn n。数字分析法是从中提取。数字分析法是从中提取数字分布比较均匀的数字分布比较均匀的若干位若干位作为哈希地址作为哈希地址哈希表的构造方法 除留余数法除留余数法 用关键字用关键字k ki i除以一个合适的，不大于哈希表长除以一个合适的，不大于哈希表长m m的正整的正整数数p p所得余数作为哈希地址的方法所得余数作为哈希地址的方法 H(kH(ki i) = k) = ki i MOD p MOD p 实践证明，当实践证明，当p p取小于哈希表长取小于哈希表长m m的某个的某个素数素数时，产生时，产生的哈希函数较好的哈希函数较好 平方取中法平方取中法 折叠法折叠法