第9章查找ppt课件

1、嘉应学院嘉应学院数学系数学系数据构造讲义 - 静态查找表假设表中存在特定元素，称查找胜利，应输出假设表中存在特定元素，称查找胜利，应输出该记录；该记录；否那么，称查找不胜利否那么，称查找不胜利也应输出失败标志或也应输出失败标志或失败位置失败位置查找表查找表 查查 找找查找胜利查找胜利查找不胜利查找不胜利静态查找静态查找动态查找动态查找关键字关键字主关键字主关键字次关键字次关键字由同一类型的数据元素由同一类型的数据元素或记录或记录构成的集合。构成的集合。查询查询(Searching)特定元素能否在表中。特定元素能否在表中。只查找，不改动集合内的数据元素。只查找，不改动集合内的数据元素。既查找，又

2、改动既查找，又改动增减增减集合内的数据元素。集合内的数据元素。记录中某个数据项的值，可用来识别一个记录记录中某个数据项的值，可用来识别一个记录 ( 预先确定的记录的某种标志预先确定的记录的某种标志 ) 可以独一标识一个记录的关键字可以独一标识一个记录的关键字例如例如“学号学号例如例如“女女是一种数据构造是一种数据构造识别假设干记录的关键识别假设干记录的关键字字2对查找表常用的操作有哪些？对查找表常用的操作有哪些？ 查询某个查询某个“特定的特定的数据元素能否在表中；数据元素能否在表中；查询某个查询某个“特定的特定的数据元素的各种属性；数据元素的各种属性；在查找表中插入一元素；在查找表中插入一元素

3、；从查找表中删除一元素。从查找表中删除一元素。 3) 有哪些查找方法？有哪些查找方法？ 查找方法取决于表中数据的陈列方式查找方法取决于表中数据的陈列方式;1查找的过程是怎样的？查找的过程是怎样的？ 给定一个值给定一个值K，在含有，在含有n个记录的文件中进展搜索，个记录的文件中进展搜索，寻觅一个关键字值等于寻觅一个关键字值等于K的记录，如找到那么输出的记录，如找到那么输出该记录，否那么输出查找不胜利的信息。该记录，否那么输出查找不胜利的信息。例如查字典例如查字典针对静态查找表和动态查找表的查找方法也有所不同。针对静态查找表和动态查找表的查找方法也有所不同。“特定的特定的=关键关键字字明确：查找的

4、过程就是将给定的明确：查找的过程就是将给定的K值与文件中各记录的关键字值与文件中各记录的关键字项进展比较的过程。所以用比较次数的平均值来评价算法的优项进展比较的过程。所以用比较次数的平均值来评价算法的优劣。称为平均查找长度劣。称为平均查找长度ASL：average search length。niiiCPASL1其中：其中：n是文件记录个数；是文件记录个数；Pi是查找第是查找第i个记录的查找概率个记录的查找概率通常取等概率通常取等概率,即即Pi =1/n;Ci是找到第是找到第i个记录时所阅历的比较次数。个记录时所阅历的比较次数。统计意义上的统计意义上的数学期望值数学期望值物理意义：假设每一元素

5、被查找的概率一样，那么查找物理意义：假设每一元素被查找的概率一样，那么查找每一元素所需的比较次数之总和再取平均，即为每一元素所需的比较次数之总和再取平均，即为ASL。显然，显然，ASLASL值越小，时间效率越高。值越小，时间效率越高。 4如何评价查找方法的优劣？如何评价查找方法的优劣？针对静态查找表的查找算法主要有：针对静态查找表的查找算法主要有： 静态查找表的笼统数据类型参见教材静态查找表的笼统数据类型参见教材P216。一、顺序查找一、顺序查找线性查找线性查找二、折半查找二、折半查找二分或对分查找二分或对分查找三、静态树表的查找三、静态树表的查找四、分块查找四、分块查找索引顺序查找索引顺序查

6、找1顺序表的机内存储构造：顺序表的机内存储构造：typedef struct ElemType *elem; /表基址，表基址，0号单元留空。表容量为全号单元留空。表容量为全部元素部元素 int length; /表长，即表中数据元素个数表长，即表中数据元素个数SSTable;顺序查找：即用逐一比较的方法顺序查找关键字，这显然是最顺序查找：即用逐一比较的方法顺序查找关键字，这显然是最直接的方法。直接的方法。 对顺序构造如何线性查找？见下页之例或教材对顺序构造如何线性查找？见下页之例或教材P216；对单链表构造如何线性查找？函数虽未给出，但也很容易编写；对单链表构造如何线性查找？函数虽未给出，但

7、也很容易编写；只需知道头指针只需知道头指针head就可以就可以“顺藤摸瓜顺藤摸瓜；对非线性树构造如何顺序查找对非线性树构造如何顺序查找?可借助各种遍历操作！可借助各种遍历操作！技巧：把待查关键字技巧：把待查关键字key存入表头或表尾存入表头或表尾俗称俗称“哨兵哨兵，这样可以加快执行速度。这样可以加快执行速度。例：例：假设将待查找的特定值假设将待查找的特定值keykey存入顺序表的首部存入顺序表的首部如如0 0号单号单元元，那么顺序查找的实现方案为：从后向前逐个比较！，那么顺序查找的实现方案为：从后向前逐个比较！int Search_Seq( SSTable ST , KeyType key )

8、 /在顺序表在顺序表ST中，查找关键字与中，查找关键字与key一样的元素；一样的元素；假设胜利，前往其位置信息，否那么前往假设胜利，前往其位置信息，否那么前往0 ST.elem0.key =key; /设立哨兵，可免去查找过设立哨兵，可免去查找过程中每一步都要检测能否查找终了。当程中每一步都要检测能否查找终了。当n1000时，时，查找时间将减少一半。查找时间将减少一半。 for( i=ST.length; ST.elem i .key!=key; - - i ); /不要用不要用for(i=n; i0; - -i) 或或 for(i=1; i=n; i+) return i; /假设到达假设到

9、达0号单元才终了循环，阐明不胜号单元才终了循环，阐明不胜利，前往利，前往0值值(i=0)。胜利时那么前往找到的那个。胜利时那么前往找到的那个元素的位置元素的位置i。 / Search_Seq前往特殊标志，例如前往空记录或空指针。前例中设立前往特殊标志，例如前往空记录或空指针。前例中设立了了“哨兵哨兵，就是将关键字送入末地址，就是将关键字送入末地址ST.elem0.key使之终使之终了并前往了并前往 i=0。讨论讨论 查找效率怎样计算？查找效率怎样计算？用平均查找长度用平均查找长度ASL衡量。衡量。讨论讨论 如何计算如何计算ASL？分析：分析：查找第查找第1个元素所需的比较次数为个元素所需的比较

10、次数为1；查找第查找第2个元素所需的比较次数为个元素所需的比较次数为2；查找第查找第n个元素所需的比较次数为个元素所需的比较次数为n；总计全部比较次数为：总计全部比较次数为：12n = (1+n)n/2未思索查找不胜利的未思索查找不胜利的情况：查找哨兵所需情况：查找哨兵所需的比较次数为的比较次数为n+1n+1这是查找胜利的情况这是查找胜利的情况假设求某一个元素的平均查找次数，还该当除以假设求某一个元素的平均查找次数，还该当除以n等概等概率率，即：即： ASL1n/2 ，时间效率为，时间效率为 O(n)优点：算法简单，且对顺序构造或链表构造均适用。优点：算法简单，且对顺序构造或链表构造均适用。缺

11、陷：缺陷： ASL 太长，时间效率太低。太长，时间效率太低。这是一种容易想到的查找方法。这是一种容易想到的查找方法。先给数据排序先给数据排序例如按升序排好例如按升序排好，构成有序表，然后再将，构成有序表，然后再将key与正中元素相比，假设与正中元素相比，假设key小，那么减少至右半部内查找；再取小，那么减少至右半部内查找；再取其中值比较，每次减少其中值比较，每次减少1/2的范围，直到查找胜利或失败为止。的范围，直到查找胜利或失败为止。v 对顺序表构造如何编程实现折半查找算法？对顺序表构造如何编程实现折半查找算法？ v 见下页之例，或见教材见下页之例，或见教材P219v 对单链表构造如何折半查找

12、？对单链表构造如何折半查找？v 无法实现！因全部元素的定位只能从头指针无法实现！因全部元素的定位只能从头指针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.ke

13、y keyST.elemmid.key key，阐明，阐明keykeylow ,mid-low ,mid-11， 那么令：那么令：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 意即区间长意即区间长度小

14、于度小于0 0解：解： 先设定先设定3个辅助标志个辅助标志: low,high,mid，LowLow指向待查元素指向待查元素所在区间的下界所在区间的下界highhigh指向待查元素所指向待查元素所在区间的上界在区间的上界midmid指向待查元素所在指向待查元素所在区间的中间位置区间的中间位置 知如下知如下11个元素的有序表：个元素的有序表：05 13 19 21 37 56 64 75 80 88 92, 请查找关键字为请查找关键字为21 和和85的数据元素。的数据元素。显然有：显然有：mid= mid= (low+high)/2(low+high)/2mjjj112典型标志是：当查找范围的上

15、界典型标志是：当查找范围的上界下界时停顿查找。下界时停顿查找。讨论讨论 二分查找的效率二分查找的效率ASLASL1次比较就查找胜利的元素有次比较就查找胜利的元素有1个个20，即中间值；，即中间值；2次比较就查找胜利的元素有次比较就查找胜利的元素有2个个21，即，即1/4处处或或3/4处；处；3次比较就查找胜利的元素有次比较就查找胜利的元素有4个个22，即，即1/8处处或或3/8处处 4次比较就查找胜利的元素有次比较就查找胜利的元素有8个个23，即，即1/16处处或或3/16处处 那么第那么第m次比较时查找胜利的元素会有次比较时查找胜利的元素会有2m-1个；个；为方便起见，假设表中全部为方便起见

16、，假设表中全部n个元素个元素 2m-1个，此时就不讨论第个，此时就不讨论第m次比较后还有剩余元素的情况了。次比较后还有剩余元素的情况了。全部比较总次数为全部比较总次数为120221322423m2m1 推推导导过过程程详细推导过程见教材详细推导过程见教材P221的附录的附录1课堂练习课堂练习多项选择多项选择：采用链式存贮构造采用链式存贮构造 记录的长度记录的长度128 采用顺序存贮构造采用顺序存贮构造 记录按关键字递增有序记录按关键字递增有序nnnnjnASLmjj2211log1) 1(log121运用折半查找算法时，要求被查文件：运用折半查找算法时，要求被查文件：思索：假设在有序线性表思索

17、：假设在有序线性表a20上进展折半查上进展折半查找，那么平均查找长度为找，那么平均查找长度为 。查找过程可用二叉树描画：每个记录用一个结点表示；查找过程可用二叉树描画：每个记录用一个结点表示；结点中值为该记录在表中位置，这个描画查找过程的二结点中值为该记录在表中位置，这个描画查找过程的二叉树称为断定树。叉树称为断定树。n个元素的表的折半查找的断定树是独个元素的表的折半查找的断定树是独一的，即：断定树由表中元素个数决议。一的，即：断定树由表中元素个数决议。 找到有序表中任一记录的过程就是：走了一条从根结点找到有序表中任一记录的过程就是：走了一条从根结点到与该记录相应的结点的途径。到与该记录相应的

18、结点的途径。 比较的关键字个数：为该结点在断定树上的层次数。比较的关键字个数：为该结点在断定树上的层次数。 查找胜利时比较的关键字个数最多不超越树的深度查找胜利时比较的关键字个数最多不超越树的深度 d : d = log2 n + 1 假设一切结点的空指针域设置为一个指向一个方形结点假设一切结点的空指针域设置为一个指向一个方形结点的指针，称方形结点为断定树的外部结点；对应的，圆的指针，称方形结点为断定树的外部结点；对应的，圆形结点为内部结点。形结点为内部结点。 查找不胜利的过程查找不胜利的过程 就是走了一条从根结点到外部结点的就是走了一条从根结点到外部结点的途径。途径。这是一种顺序查找的另一种

19、改良方法。这是一种顺序查找的另一种改良方法。先让数据分块有序，即分成假设干子表，要求每个子表中的先让数据分块有序，即分成假设干子表，要求每个子表中的数值数值用关键字更准确用关键字更准确都比后一块中数值小都比后一块中数值小但子表内部未但子表内部未必有序必有序。然后将各子表中的最大关键字构成一个索引表，表中还要包然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址含每个子表的起始地址即头指针即头指针。索引表索引表最大关键字起始地址22 12 138920 33 42 44 38 24 48 60 58 74 49 86 53第第1 1块块第第2 2块块第第3 3块块224886例：例：2248861713特点：块间有特点：块间有序，块内无序序，块内无序 对索引表运用折半查找法对索引表运用折半查找法由于索引表是