数据结构计算机与信息学院 姜敏数据结构课程的内容数据结构课程的内容1数据结构第1516次课-查找数据结构计算机与信息学院 姜敏8.1 8.1 基本概念基本概念8.2 8.2 静态查找静态查找8.3 8.3 动态查找动态查找8.4 8.4 哈希查找哈希查找第第8 8章章 查找查找2数据结构第1516次课-查找数据结构计算机与信息学院 姜敏8.1 基本概念基本概念(1) 定义定义 查找查找查询查询特定元素特定元素是否在查找列表中。是否在查找列表中。(3) 目的目的 提高查找效率提高查找效率(2) 实质实质 关键字关键字的比较或匹配。的比较或匹配。 猜价格游戏：已知物品价格为猜价格游戏：已知物品价格为1至至9之间的整之间的整数，请按两种不同方式来猜物品价格。数，请按两种不同方式来猜物品价格。63数据结构第1516次课-查找数据结构计算机与信息学院 姜敏 (4) (4)评估查找方法优劣的标准评估查找方法优劣的标准 一般用查找次数的平均值来评估算法的优劣。称一般用查找次数的平均值来评估算法的优劣。称为为平均查找长度平均查找长度（ASLASL：average search lengthaverage search length）。）。 静态查找静态查找只查找，不改变查找表的数据元素。只查找，不改变查找表的数据元素。 动态查找动态查找既查找，又改变查找表内的数据元素既查找，又改变查找表内的数据元素。(5) 分类分类4数据结构第1516次课-查找数据结构计算机与信息学院 姜敏静态查找算法主要有：静态查找算法主要有： 8.2 静态查找静态查找1、顺序查找（线性查找）顺序查找（线性查找）2、二分查找（折半或对分查找）二分查找（折半或对分查找）3、分块查找（索引顺序查找）、分块查找（索引顺序查找）4、静态树表的查找、静态树表的查找5数据结构第1516次课-查找数据结构计算机与信息学院 姜敏1.1.顺序查找（又称线性查找）顺序查找（又称线性查找）定义：用定义：用逐一比较逐一比较的办法顺序查找关键字。的办法顺序查找关键字。 i例 1 2 3 4 5 6 7 8 9 10 115 63 59 21 17 56 64 45 80 38 92找64iiii6数据结构第1516次课-查找数据结构计算机与信息学院 姜敏1 1、顺序查找（、顺序查找（ Linear searchLinear search，又称线性查找又称线性查找 ）顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最直接的办法。直接的办法。 v对对顺序结构顺序结构如何线性查找？如何线性查找？见下页之例见下页之例; ;v对对单单链链表表结结构构如如何何线线性性查查找找？函函数数虽虽未未给给出出，但但也也很很容容易易编编写；只要知道头指针写；只要知道头指针headhead就可以就可以“顺藤摸瓜顺藤摸瓜”；v对对非线性树结构非线性树结构如何顺序查找如何顺序查找? ?可借助各种遍历操作！可借助各种遍历操作！7数据结构第1516次课-查找数据结构计算机与信息学院 姜敏 （1） 已知顺序表元素存储在已知顺序表元素存储在a 1-n 中，要在其中中，要在其中查找查找关键字为关键字为k的某元素的位置，该如何编程？的某元素的位置，该如何编程？(找到找到返回位置，找不到返回返回位置，找不到返回0）int seqsrch( int a, int n, int k ) for(int i=1; i0; - -i) for(i=n; i0; - -i) 或或 for(i=1; i=n; i+) for(i=1; i=n; i+) return i; /若到达若到达0 0号单元才结束循环，说明不成功，返回号单元才结束循环，说明不成功，返回0 0值值(i=0)(i=0)。成功时则返回找到的那个元素的位置。成功时则返回找到的那个元素的位置i i。 / Search_Seq（2 2）改进算法：改进算法：10数据结构第1516次课-查找数据结构计算机与信息学院 姜敏返回特殊标志，例如返回空记录或空指针。前例中设立了返回特殊标志，例如返回空记录或空指针。前例中设立了“哨兵哨兵”，就是将关键字送入末地址，就是将关键字送入末地址ST.elemST.elem0 0.key.key使之结束并返回使之结束并返回 i=0 i=0。讨论讨论 查找效率怎样计算？查找效率怎样计算？用平均查找长度用平均查找长度ASL衡量。衡量。讨论讨论 查不到怎么办？查不到怎么办？讨论讨论 如何计算如何计算ASL？分析：分析：查找第查找第1个元素所需的比较次数为个元素所需的比较次数为1；查找第查找第2个元素所需的比较次数为个元素所需的比较次数为2；查找第查找第n个元素所需的比较次数为个元素所需的比较次数为n；总计全部比较次数为：总计全部比较次数为：12n = (1+n)n/2未考虑查找不成功的未考虑查找不成功的情况：查找哨兵所需情况：查找哨兵所需的比较次数为的比较次数为n+1n+1这是查找成功的情况这是查找成功的情况若求某一个元素的平均查找次数，还应当除以若求某一个元素的平均查找次数，还应当除以n（等概率），（等概率），即：即： ASL（1n）/2 ，时间效率为，时间效率为 O(n)11数据结构第1516次课-查找数据结构计算机与信息学院 姜敏二、折半查找（又称二分查找或对分查找）二、折半查找（又称二分查找或对分查找）优点：优点：算法简单，且对顺序结构或链表结构均适用。算法简单，且对顺序结构或链表结构均适用。缺点：缺点： ASL 太长，时间效率太低。太长，时间效率太低。这是一种容易想到的查找方法。这是一种容易想到的查找方法。先给数据排序先给数据排序（例如按升序排好），形成（例如按升序排好），形成有序表有序表，然后再将，然后再将keykey与正中元素相比，若与正中元素相比，若keykey小，则缩小至右半部内查找；再取其中小，则缩小至右半部内查找；再取其中值比较，每次缩小值比较，每次缩小1/21/2的范围，直到查找成功或失败为止。的范围，直到查找成功或失败为止。如何改进？如何改进？讨论讨论 顺序查找的特点：顺序查找的特点：12数据结构第1516次课-查找数据结构计算机与信息学院 姜敏lowhighmid例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找211 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 92lowhighmid归纳：归纳：mid（highlow）/2朝左找修改朝左找修改highmid1朝右找修改朝右找修改lowmid113数据结构第1516次课-查找数据结构计算机与信息学院 姜敏例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找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 92low highmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid14数据结构第1516次课-查找数据结构计算机与信息学院 姜敏1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighlowhigh表明查找区间空，查找终止15数据结构第1516次课-查找数据结构计算机与信息学院 姜敏讨论讨论 若关键字不在表中，怎样得知和停止？若关键字不在表中，怎样得知和停止？典型标志是：当查找范围的上界典型标志是：当查找范围的上界highhigh时时，返返回回查查找找失失败败信信息息 / 表表空空，查查找找失失败败 lowhigh，mid=(low+high)/2; / 取中点取中点 a. 若若kxelemmid.key，low=mid+1； 转转 / 查找在右半区进行查找在右半区进行 c. 若若kx=elemmid.key，返回数据元素在表中位置，返回数据元素在表中位置 / 查找成功查找成功 二分查找思路归纳：如何编程实现二分查找算法？如何编程实现二分查找算法？*18数据结构第1516次课-查找数据结构计算机与信息学院 姜敏int BinSrch(ElemType ElemType r, int n, int k) int low,high,mid; low=1; high=n; while( low rmid.key) low=mid+1; /大大向向右右 else if(k=rmid.key) break ; else high=mid-1 ; /小向左小向左 if (low=high) return mid; /找到找到 else return 0; /未找到未找到 折半查找非递归算法折半查找非递归算法19数据结构第1516次课-查找数据结构计算机与信息学院 姜敏int BinSrch(ElemTypeElemType r, int n, int k) int low,high,mid,found=0; /找到标记找到标记low=1; high=n; while( ) & ( ) mid=(low+high)/2; if(k rmid.key) low=mid+1; else if(k=rmid.key) ; else ;if( found=1 ) return ;else return 0; 折半查找非递归算法折半查找非递归算法20数据结构第1516次课-查找数据结构计算机与信息学院 姜敏折半查找递归算法折半查找递归算法递归的使用条件递归的使用条件：步骤一样、问题规模变小，必有出口步骤一样、问题规模变小，必有出口二分查找符合上述条件么？二分查找符合上述条件么？二分查找递归函数定义应该是什么样的？二分查找递归函数定义应该是什么样的？int BinSrch(int r, int n, int k)/非递归定义非递归定义int BinSch(ElemTypeElemType r，keytype k，int low，int high）步骤一样（三步）、问题规模变小，必有出口（区域变空）步骤一样（三步）、问题规模变小，必有出口（区域变空）21数据结构第1516次课-查找数据结构计算机与信息学院 姜敏int int BinschBinsch( ( ElemType A ,int low,int high,KeyType KElemType A ,int low,int high,KeyType K ) ) ifif（_）/查找区域非空查找区域非空 int mid=(low+high)/2;int mid=(low+high)/2;ifif（_）return mid;return mid; /查找成功，返回元素的下标查找成功，返回元素的下标else if(KAmid.key)else if(KAmid.key) return Binsch(A,low,mid-1,K); return Binsch(A,low,mid-1,K); /在左子表上继续查找在左子表上继续查找else return _else return _； /在右子表上继续查找在右子表上继续查找 else _else _；/查找失败，返回查找失败，返回-1-1 折半查找递归算法填空折半查找递归算法填空22数据结构第1516次课-查找数据结构计算机与信息学院 姜敏查找过程可用查找过程可用二叉树二叉树描述：每个记录用一个结点表示；结点中值为描述：每个记录用一个结点表示；结点中值为该记录在表中位置，这个描述查找过程的二叉树称为该记录在表中位置，这个描述查找过程的二叉树称为判定树。判定树。n个元个元素的表的折半查找的素的表的折半查找的判定树是唯一判定树是唯一的，即：判定树由表中元素个数的，即：判定树由表中元素个数决定。决定。 找到有序表中任一记录的过程就是找到有序表中任一记录的过程就是：走了一条从根结点到与该记录：走了一条从根结点到与该记录相应的结点的路径。相应的结点的路径。 比较的关键字个数：比较的关键字个数：为该结点在判定树上的层次数。为该结点在判定树上的层次数。 查找成功时查找成功时比较的关键字个数最多不超过树的深度比较的关键字个数最多不超过树的深度 d : d = log2 n + 1 若所有结点的空指针域设置为一个指向一个方形结点的指针，称若所有结点的空指针域设置为一个指向一个方形结点的指针，称方形结点为判定树的外部结点；对应的，圆形结点为内部结点。方形结点为判定树的外部结点；对应的，圆形结点为内部结点。 查找不成功的过程查找不成功的过程 就是走了一条从根结点到外部结点的路径。就是走了一条从根结点到外部结点的路径。折半查找效率分析法折半查找效率分析法2 21185210741936mid构成判定树：23数据结构第1516次课-查找数据结构计算机与信息学院 姜敏v对对顺序表结构顺序表结构如何编程实现折半查找算法？如何编程实现折半查找算法？ 见前见前面折半查找递归及非递归算法面折半查找递归及非递归算法v对对单链表结构单链表结构如何折半查找？如何折半查找？ 无法实现！无法实现！因全部元素的定位只能从头指针因全部元素的定位只能从头指针headhead开始开始v对对非线性非线性(树树)结构结构如何折半查找？如何折半查找？ 可借助二叉排序树来查找（属动态查找表形式）。可借助二叉排序树来查找（属动态查找表形式）。 讨论讨论2：当有序表中各记录的当有序表中各记录的查找概率不相等查找概率不相等时，该如何查找？时，该如何查找？此时此时用折半查找法未必最优用折半查找法未必最优！讨论讨论1：对对有序表有序表还有其他查找算法吗？还有其他查找算法吗？有，如斐波那契查找和插值查找等有，如斐波那契查找和插值查找等24数据结构第1516次课-查找数据结构计算机与信息学院 姜敏三、静态树表的查找三、静态树表的查找（自学）（自学）改进：改进：若将各记录概率看作是二叉树之权值，则转为研究带若将各记录概率看作是二叉树之权值，则转为研究带权路径长度最小的二叉树（类似最优二叉树）。权路径长度最小的二叉树（类似最优二叉树）。静态最优查找树算法静态最优查找树算法时间代价高；时间代价高；实用算法：实用算法：近似最优查找树（近似最优查找树（次优次优查找树）查找树） 25数据结构第1516次课-查找数据结构计算机与信息学院 姜敏四、分块查找（索引顺序查找）四、分块查找（索引顺序查找） 这是一种顺序查找的另一种改进方法。这是一种顺序查找的另一种改进方法。 先让数据先让数据分块有序分块有序，即分成若干子表，要求每个子表中的，即分成若干子表，要求每个子表中的数值（用关键字更准确）都比后一块中数值小（但子表内部未数值（用关键字更准确）都比后一块中数值小（但子表内部未必有序）。必有序）。 然后将各子表中的最大关键字构成一个然后将各子表中的最大关键字构成一个索引表索引表，表中还要，表中还要包含每个子表的起始地址（即头指针）。包含每个子表的起始地址（即头指针）。索引表索引表最大关键字起始地址22 12 138920 33 42 44 38 24 48 60 58 74 49 86 53第第1 1块块第第2 2块块第第3 3块块224886例：例：2248861713特点：块间有特点：块间有序，块内无序序，块内无序26数据结构第1516次课-查找数据结构计算机与信息学院 姜敏查找步骤查找步骤分两步进行：分两步进行： 对索引表使用折半查找法（因为索引表是有序表）；对索引表使用折半查找法（因为索引表是有序表）； 确定了待查关键字所在的子表后，在子表内采用顺序确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；查找法（因为各子表内部是无序表）；查找效率：查找效率：ASL=LASL=Lb b+L+Lw w对索引表查找的对索引表查找的ASL对块内查找的对块内查找的ASLS为每块内部的记录个数，为每块内部的记录个数，n/s即块的数目即块的数目例如当例如当n=9n=9，s=3s=3时时，ASLASLbsbs= =3.53.5, ,而折半法为而折半法为3.13.1, ,顺序法为顺序法为5 527数据结构第1516次课-查找数据结构计算机与信息学院 姜敏ASL最大最大最小最小两者之间两者之间表结构表结构有序表、无序表有序表、无序表 有序表有序表分块有序表分块有序表存储结构存储结构顺序存储结构顺序存储结构线性链表线性链表顺序存储结构顺序存储结构 顺序存储结构顺序存储结构线性链表线性链表三种静态查找方法比较三种静态查找方法比较顺序查找顺序查找折半查找折半查找分块查找分块查找小结小结：28数据结构第1516次课-查找