《第9章查找ppt课件》由会员分享，可在线阅读，更多相关《第9章查找ppt课件（19页珍藏版）》请在金锄头文库上搜索。
1、第9章 查找嘉应学院嘉应学院数学系数学系数据构造讲义 - 静态查找表9.1 9.1 根本概念根本概念假设表中存在特定元素，称查找胜利，应输出假设表中存在特定元素，称查找胜利，应输出该记录；该记录；否那么，称查找不胜利否那么，称查找不胜利也应输出失败标志或也应输出失败标志或失败位置失败位置查找表查找表 查查 找找查找胜利查找胜利查找不胜利查找不胜利静态查找静态查找动态查找动态查找关键字关键字主关键字主关键字次关键字次关键字由同一类型的数据元素由同一类型的数据元素或记录或记录构成的集合。构成的集合。查询查询(Searching)特定元素能否在表中。特定元素能否在表中。只查找，不改动集合内的数据元素
2、。只查找，不改动集合内的数据元素。既查找，又改动既查找，又改动增减增减集合内的数据元素。集合内的数据元素。记录中某个数据项的值，可用来识别一个记录记录中某个数据项的值，可用来识别一个记录 ( 预先确定的记录的某种标志预先确定的记录的某种标志 ) 可以独一标识一个记录的关键字可以独一标识一个记录的关键字例如例如“学号学号例如例如“女女是一种数据构造是一种数据构造识别假设干记录的关键识别假设干记录的关键字字2对查找表常用的操作有哪些？对查找表常用的操作有哪些？ 查询某个查询某个“特定的特定的数据元素能否在表中；数据元素能否在表中；查询某个查询某个“特定的特定的数据元素的各种属性；数据元素的各种属性
3、；在查找表中插入一元素；在查找表中插入一元素；从查找表中删除一元素。从查找表中删除一元素。 3) 有哪些查找方法？有哪些查找方法？ 查找方法取决于表中数据的陈列方式查找方法取决于表中数据的陈列方式;讨论：讨论：讨论：讨论：1查找的过程是怎样的？查找的过程是怎样的？ 给定一个值给定一个值K，在含有，在含有n个记录的文件中进展搜索，个记录的文件中进展搜索，寻觅一个关键字值等于寻觅一个关键字值等于K的记录，如找到那么输出该的记录，如找到那么输出该记录，否那么输出查找不胜利的信息。记录，否那么输出查找不胜利的信息。例如查字典例如查字典针对静态查找表和动态查找表的查找方法也有所不同。针对静态查找表和动态
4、查找表的查找方法也有所不同。“特定的特定的=关键关键字字明确：查找的过程就是将给定的明确：查找的过程就是将给定的K值与文件中各记录的关键字值与文件中各记录的关键字项进展比较的过程。所以用比较次数的平均值来评价算法的优项进展比较的过程。所以用比较次数的平均值来评价算法的优劣。称为平均查找长度劣。称为平均查找长度ASL：average search length。其中：其中：n是文件记录个数；是文件记录个数；Pi是查找第是查找第i个记录的查找概率个记录的查找概率通常取等概率通常取等概率,即即Pi =1/n;Ci是找到第是找到第i个记录时所阅历的比较次数。个记录时所阅历的比较次数。统计意义上的统计意
5、义上的数学期望值数学期望值物理意义：假设每一元素被查找的概率一样，那么查找物理意义：假设每一元素被查找的概率一样，那么查找每一元素所需的比较次数之总和再取平均，即为每一元素所需的比较次数之总和再取平均，即为ASL。显然，显然，ASLASL值越小，时间效率越高。值越小，时间效率越高。 4如何评价查找方法的优劣？如何评价查找方法的优劣？针对静态查找表的查找算法主要有：针对静态查找表的查找算法主要有： 9.2 9.2 静态查找表静态查找表静态查找表的笼统数据类型参见教材静态查找表的笼统数据类型参见教材P216。一、顺序查找一、顺序查找线性查找线性查找二、折半查找二、折半查找二分或对分查找二分或对分查
6、找三、静态树表的查找三、静态树表的查找四、分块查找四、分块查找索引顺序查找索引顺序查找一、顺序查找一、顺序查找一、顺序查找一、顺序查找 Linear search Linear search，又称线性查找，又称线性查找，又称线性查找，又称线性查找 1顺序表的机内存储构造：顺序表的机内存储构造：typedef struct ElemType *elem; /表基址，表基址，0号单元留空。表容量为全号单元留空。表容量为全部元素部元素 int length; /表长，即表中数据元素个数表长，即表中数据元素个数SSTable;顺序查找：即用逐一比较的方法顺序查找关键字，这显然是最顺序查找：即用逐一比较
7、的方法顺序查找关键字，这显然是最直接的方法。直接的方法。 对顺序构造如何线性查找？见下页之例或教材对顺序构造如何线性查找？见下页之例或教材P216；对单链表构造如何线性查找？函数虽未给出，但也很容易编写；对单链表构造如何线性查找？函数虽未给出，但也很容易编写；只需知道头指针只需知道头指针head就可以就可以“顺藤摸瓜顺藤摸瓜；对非线性树构造如何顺序查找对非线性树构造如何顺序查找?可借助各种遍历操作！可借助各种遍历操作！2 2算法的实现：算法的实现：算法的实现：算法的实现：技巧：把待查关键字技巧：把待查关键字key存入表头或表尾存入表头或表尾俗称俗称“哨兵哨兵，这样可以加快执行速度。这样可以加快
8、执行速度。例：例：假设将待查找的特定值假设将待查找的特定值keykey存入顺序表的首部存入顺序表的首部如如0 0号单号单元元，那么顺序查找的实现方案为：从后向前逐个比较！，那么顺序查找的实现方案为：从后向前逐个比较！int Search_Seq( SSTable ST , KeyType key ) /在顺序表在顺序表ST中，查找关键字与中，查找关键字与key一样的元素；一样的元素；假设胜利，前往其位置信息，否那么前往假设胜利，前往其位置信息，否那么前往0 ST.elem0.key =key; /设立哨兵，可免去查找过设立哨兵，可免去查找过程中每一步都要检测能否查找终了。当程中每一步都要检测能
9、否查找终了。当n1000时，时，查找时间将减少一半。查找时间将减少一半。 for( i=ST.length; ST.elem i .key!=key; - - i ); /不要用不要用for(i=n; i0; - -i) 或或 for(i=1; i=n; i+) return i; /假设到达假设到达0号单元才终了循环，阐明不胜号单元才终了循环，阐明不胜利，前往利，前往0值值(i=0)。胜利时那么前往找到的那个。胜利时那么前往找到的那个元素的位置元素的位置i。 / Search_Seq算法演示算法演示前往特殊标志，例如前往空记录或空指针。前例中设立前往特殊标志，例如前往空记录或空指针。前例中设
10、立了了“哨兵哨兵，就是将关键字送入末地址，就是将关键字送入末地址ST.elem0.key使之终使之终了并前往了并前往 i=0。讨论讨论 查找效率怎样计算？查找效率怎样计算？用平均查找长度用平均查找长度ASL衡量。衡量。讨论讨论讨论讨论 查不到怎样办？查不到怎样办？查不到怎样办？查不到怎样办？讨论讨论 如何计算如何计算ASL？分析：分析：查找第查找第1个元素所需的比较次数为个元素所需的比较次数为1；查找第查找第2个元素所需的比较次数为个元素所需的比较次数为2；查找第查找第n个元素所需的比较次数为个元素所需的比较次数为n；总计全部比较次数为：总计全部比较次数为：12n = (1+n)n/2未思索查
11、找不胜利的未思索查找不胜利的情况：查找哨兵所需情况：查找哨兵所需的比较次数为的比较次数为n+1n+1这是查找胜利的情况这是查找胜利的情况假设求某一个元素的平均查找次数，还该当除以假设求某一个元素的平均查找次数，还该当除以n等概率等概率，即：即： ASL1n/2 ，时间效率为，时间效率为 O(n)二、折半查找二、折半查找二、折半查找二、折半查找又称二分查找或对分查找又称二分查找或对分查找又称二分查找或对分查找又称二分查找或对分查找优点：算法简单，且对顺序构造或链表构造均适用。优点：算法简单，且对顺序构造或链表构造均适用。缺陷：缺陷： ASL 太长，时间效率太低。太长，时间效率太低。这是一种容易想
12、到的查找方法。这是一种容易想到的查找方法。先先给给数数据据排排序序例例如如按按升升序序排排好好，构构成成有有序序表表，然然后后再再将将key与与正正中中元元素素相相比比，假假设设key小小，那那么么减减少少至至右右半半部部内内查查找找；再再取取其中值比较，每次减少其中值比较，每次减少1/2的范围，直到查找胜利或失败为止。的范围，直到查找胜利或失败为止。v对顺序表构造如何编程实现折半查找算法？对顺序表构造如何编程实现折半查找算法？ v 见下页之例，或见教材见下页之例，或见教材P219v对单链表构造如何折半查找？对单链表构造如何折半查找？v 无法实现！因全部元素的定位只能从头指针无法实现！因全部元
13、素的定位只能从头指针head开场开场v对非线性对非线性(树树)构造如何折半查找？构造如何折半查找？v 可借助二叉排序树来查找可借助二叉排序树来查找属动态查找表方式属动态查找表方式。 如何改良如何改良？讨论讨论 顺序查找的特点：顺序查找的特点： 运算步骤：运算步骤：(1) low =1,high =11 ,mid =6 (1) low =1,high =11 ,mid =6 ，待查范围是，待查范围是 1,111,11；(2) (2) 假设假设 ST.elemmid.key keyST.elemmid.key keyST.elemmid.key key，阐明，阐明keykey low ,mid-1
14、low ,mid-1， 那么令：那么令：high =mid1;high =mid1;重算重算 mid mid ；(4)(4)假设假设 ST.elem mid .key = keyST.elem mid .key = key，阐明查找胜利，元素序，阐明查找胜利，元素序号号=mid;=mid;终了条件：终了条件： 1 1查找胜利查找胜利 ： ST.elemmid.key = keyST.elemmid.key = key 2 2查找不胜利查找不胜利 ： highlow highlow 意即区间长度意即区间长度小于小于0 0解：解： 先设定先设定3个辅助标志个辅助标志: low,high,mid，折
15、半查找举例：折半查找举例：折半查找举例：折半查找举例：LowLow指向待查元素指向待查元素所在区间的下界所在区间的下界highhigh指向待查元素所指向待查元素所在区间的上界在区间的上界midmid指向待查元素所在指向待查元素所在区间的中间位置区间的中间位置 知如下知如下11个元素的有序表：个元素的有序表：05 13 19 21 37 56 64 75 80 88 92, 请查找关键字为请查找关键字为21 和和85的数据元素。的数据元素。显然有：显然有：mid= mid= (low+high)/2(low+high)/2 算法演示算法演示编程实现编程实现讨论讨论讨论讨论 假设关键字不在表中，怎
16、样得知和停顿？假设关键字不在表中，怎样得知和停顿？假设关键字不在表中，怎样得知和停顿？假设关键字不在表中，怎样得知和停顿？典型标志是：当查找范围的上界典型标志是：当查找范围的上界下界时停顿查找。下界时停顿查找。讨论讨论 二分查找的效率二分查找的效率ASLASL1次比较就查找胜利的元素有次比较就查找胜利的元素有1个个20，即中间值；，即中间值；2次比较就查找胜利的元素有次比较就查找胜利的元素有2个个21，即，即1/4处处或或3/4处；处；3次比较就查找胜利的元素有次比较就查找胜利的元素有4个个22，即，即1/8处处或或3/8处处 4次比较就查找胜利的元素有次比较就查找胜利的元素有8个个23，即，
17、即1/16处处或或3/16处处 那么第那么第m次比较时查找胜利的元素会有次比较时查找胜利的元素会有2m-1个；个；为方便起见，假设表中全部为方便起见，假设表中全部n个元素个元素 2m-1个，此时就不讨论第个，此时就不讨论第m次比较后还有剩余元素的情况了。次比较后还有剩余元素的情况了。全部比较总次数为全部比较总次数为120221322423m2m1 推推导导过过程程平均每个数据的查找时间还要除以平均每个数据的查找时间还要除以平均每个数据的查找时间还要除以平均每个数据的查找时间还要除以n n，所以：，所以：，所以：，所以：详细推导过程见教材详细推导过程见教材P221的附录的附录1课堂练习课堂练习多
18、项选择多项选择：采用链式存贮构造采用链式存贮构造 记录的长度记录的长度128 采用顺序存贮构造采用顺序存贮构造 记录按关键字递增有序记录按关键字递增有序运用折半查找算法时，要求被查文件：运用折半查找算法时，要求被查文件：思索：假设在有序线性表思索：假设在有序线性表a20上进展折半查上进展折半查找，那么平均查找长度为找，那么平均查找长度为 。查找过程可用二叉树描画：每个记录用一个结点表示；结查找过程可用二叉树描画：每个记录用一个结点表示；结点中值为该记录在表中位置，这个描画查找过程的二叉树点中值为该记录在表中位置，这个描画查找过程的二叉树称为断定树。称为断定树。n个元素的表的折半查找的断定树是独
19、一的，个元素的表的折半查找的断定树是独一的，即：断定树由表中元素个数决议。即：断定树由表中元素个数决议。 找到有序表中任一记录的过程就是：走了一条从根结点找到有序表中任一记录的过程就是：走了一条从根结点到与该记录相应的结点的途径。到与该记录相应的结点的途径。 比较的关键字个数：为该结点在断定树上的层次数。比较的关键字个数：为该结点在断定树上的层次数。 查找胜利时比较的关键字个数最多不超越树的深度查找胜利时比较的关键字个数最多不超越树的深度 d : d = log2 n + 1 假设一切结点的空指针域设置为一个指向一个方形结点假设一切结点的空指针域设置为一个指向一个方形结点的指针，称方形结点为断
20、定树的外部结点；对应的，圆形的指针，称方形结点为断定树的外部结点；对应的，圆形结点为内部结点。结点为内部结点。 查找不胜利的过程查找不胜利的过程 就是走了一条从根结点到外部结点的就是走了一条从根结点到外部结点的途径。途径。折半查找效率分析法折半查找效率分析法折半查找效率分析法折半查找效率分析法参见教材参见教材参见教材参见教材P220P220：三、分块查找三、分块查找三、分块查找三、分块查找索引顺序查找索引顺序查找索引顺序查找索引顺序查找这是一种顺序查找的另一种改良方法。这是一种顺序查找的另一种改良方法。先先让让数数据据分分块块有有序序，即即分分成成假假设设干干子子表表，要要求求每每个个子子表表
21、中中的的数数值值用用关关键键字字更更准准确确都都比比后后一一块块中中数数值值小小但但子子表表内内部部未未必有序必有序。然然后后将将各各子子表表中中的的最最大大关关键键字字构构成成一一个个索索引引表表，表表中中还还要要包包含每个子表的起始地址含每个子表的起始地址即头指针即头指针。索引表索引表最大关键字起始地址2212138920334244382448605874498653第第1 1块块第第2 2块块第第3 3块块224886例：例：2248861713特点：块间有特点：块间有序，块内无序序，块内无序查找步骤分两步进展：查找步骤分两步进展：查找步骤分两步进展：查找步骤分两步进展： 对索引表运用
22、折半查找法对索引表运用折半查找法由于索引表是有序表由于索引表是有序表； 确定了待查关键字所在的子表后，在子表内采用顺序确定了待查关键字所在的子表后，在子表内采用顺序查找法查找法由于各子表内部是无序表由于各子表内部是无序表；查找效率：查找效率：ASL=Lb+LwASL=Lb+Lw对索引表查找的对索引表查找的ASL对块内查找的对块内查找的ASLS为每块内部的记录个数，为每块内部的记录个数，n/s即块的数目即块的数目例如当例如当n=9n=9，s=3s=3时，时，ASLbs=3.5,ASLbs=3.5,而折半法为而折半法为3.1,3.1,顺序法为顺序法为5 5算法演示算法演示编程实现编程实现作业l假设
23、在有序线性表假设在有序线性表a20a20上进展折半查找，那上进展折半查找，那么比较一次查找胜利的结点数为么比较一次查找胜利的结点数为1 1；比较两次；比较两次查找胜利的结点数为查找胜利的结点数为 ；比较四次查找；比较四次查找胜利的结点数为胜利的结点数为 ；平均查找长度为；平均查找长度为 。l折半查找有序表折半查找有序表4 4，6 6，1212，2020，2828，3838，5050，7070，8888，100100，假设查找表中元素，假设查找表中元素2020，它，它将依次与表中元素将依次与表中元素 比较大小。比较大小。 l对对2222个记录的有序表作折半查找，当查找失败个记录的有序表作折半查找，当查找失败时，至少需求比较时，至少需求比较 次关键字。次关键字。
