内蒙古大学《算法与数据结构》课件第5章集合与查找

1第第5章章 集合与查找集合与查找5.1 基本概念基本概念5.2 具有具有Merge、Find的的ADT集合集合5.3 静态查找表静态查找表5.4 Hash表表5.5 二叉查找树二叉查找树(动态查找表动态查找表)5.6 平衡二叉查找树（平衡二叉查找树（AVL树）树）5.7 B-树树2若表中存在特定元素，称查找成功，应输出该元素。若表中存在特定元素，称查找成功，应输出该元素。否则，称查找不成功（也应输出失败标志或失败位置）否则，称查找不成功（也应输出失败标志或失败位置）查找表查找表查查 找找查找成功查找成功查找不成功查找不成功静态查找静态查找动态查找动态查找关键字关键字主关键字主关键字次关键字次关键字由同一类型的数据元素所构成的集合。由同一类型的数据元素所构成的集合。查询查询(Searching)特定数据元素特定数据元素是否在表中。是否在表中。只查找，不改变查找表中的数据元素。只查找，不改变查找表中的数据元素。既查找，又改变（增减）查找表中的数据元素。既查找，又改变（增减）查找表中的数据元素。元素中某个数据项的值，可用来识别一个元素。元素中某个数据项的值，可用来识别一个元素。 可以可以唯一唯一标识一个元素的关键字。标识一个元素的关键字。 例如例如“学号学号”例如例如“性别性别”识别若干元素的关键字。识别若干元素的关键字。5.1 基本概念基本概念3v 对查找表常用的操作有对查找表常用的操作有哪些？哪些？ v查询查询某个某个“特定的特定的”数据元素是否在表中；数据元素是否在表中；v在查找表中在查找表中插入插入一元素；一元素；v从查找表中从查找表中删除删除一元素。一元素。 v查找的过程是怎样的？查找的过程是怎样的？ 5.1 5.1 基本概念基本概念4v如何评估查找算法的优劣？如何评估查找算法的优劣？ 查找的过程就是将给定的查找的过程就是将给定的K值与值与查找表查找表中各元素的中各元素的关键字进行比较的过程。所以用比较次数的平均值来关键字进行比较的过程。所以用比较次数的平均值来评估算法的优劣，称为评估算法的优劣，称为平均查找长度平均查找长度（ASL：average search length）。）。显然，显然，ASL值越小，时间效率越高。值越小，时间效率越高。 5.1 基本概念基本概念 niiniiisuccpcpASL11) 1 ( .5一、顺序查找（线性查找）一、顺序查找（线性查找）二、折半查找（二分或对分查找）二、折半查找（二分或对分查找）三、分块查找（索引顺序查找）三、分块查找（索引顺序查找）5.3 静态查找表静态查找表6所谓顺序查找，又称线性查找，主要用于在所谓顺序查找，又称线性查找，主要用于在线性结构线性结构中中进行查找。进行查找。设若表中有设若表中有 n 个元素，则顺序查找从表的前端开始，顺个元素，则顺序查找从表的前端开始，顺序用各元素的关键字与给定值序用各元素的关键字与给定值x进行比较，直到找到与其进行比较，直到找到与其值相等的元素，则查找成功，给出该元素在表中的位置。值相等的元素，则查找成功，给出该元素在表中的位置。n若整个表都已检测完仍未找到关键字与若整个表都已检测完仍未找到关键字与x相等的元素，相等的元素，则查找失败，给出失败信息。则查找失败，给出失败信息。n以以顺序表或单链表顺序表或单链表表示静态查找表表示静态查找表一、顺序查找（一、顺序查找（Linear search,又称线性查找）又称线性查找）7一、顺序查找一、顺序查找1).1).顺序表的存储结构：顺序表的存储结构：int MaxListSize=100;class DataType KeyType Key; other;class SeqList DataType dataMaxListSize; /表基址，表基址，0号单元留空。号单元留空。 int size; /表长，即表中数据元素个数表长，即表中数据元素个数 ;8 int Locate (DataType e) int i = 0; while ( i =size ) return -1; /没有找到没有找到 else return i; /找到此元素，返回其下标找到此元素，返回其下标/ Locate 第二章讲的查找算法：第二章讲的查找算法：92).算法的实现：算法的实现：编程技巧：编程技巧： 把待查关键字把待查关键字keykey存入表头或表尾（俗称存入表头或表尾（俗称“哨兵哨兵”），），这样可以加快执行速度（避免每一次查找都检测整个表这样可以加快执行速度（避免每一次查找都检测整个表是否查找完毕）。是否查找完毕）。一、顺序查找一、顺序查找10int Search( KeyType key ) /在顺序表中，查找关键字与在顺序表中，查找关键字与keykey相同的元素；若成功相同的元素；若成功 / /返回其位置信息，否则返回返回其位置信息，否则返回0 0data0.key =key; for( i=size; data i .key!=key; - - i );return i; / Search同学们自己考虑对同学们自己考虑对单链表单链表如何线性查找？如何线性查找？2).算法的实现：算法的实现：一、顺序查找一、顺序查找11为确定元素在查找表中的位置，需给定值进行比较的关键字个数为确定元素在查找表中的位置，需给定值进行比较的关键字个数的期望值的期望值其中其中: n 为表长，为表长，Pi 为查找表中第为查找表中第i个记录的概率，假设每次查找个记录的概率，假设每次查找都是成功的都是成功的,则有则有 Pi=1Ci为找到该记录时，比为找到该记录时，比较过的关键字的个数，较过的关键字的个数，Ci = n-i+1，ASL = nP1 +(n-1)P2 +2Pn-1+Pn，如果要查找的元素如果要查找的元素在表中的任何位置的概率是相等的，在表中的任何位置的概率是相等的，P=1/n，ASL=(n+1)/23) 顺序查找算法的平均查找长度顺序查找算法的平均查找长度(ASL)一、顺序查找一、顺序查找 niiniiisuccpcpASL11) 1 ( .12顺序查找的优缺点：顺序查找的优缺点： 优点：对表中元素没有要求优点：对表中元素没有要求 缺点缺点: 平均查找长度较大平均查找长度较大一、顺序查找一、顺序查找13二、折半查找（二分或对分查找）二、折半查找（二分或对分查找）1) 算法思想：算法思想： 设设n个元素存放在一个个元素存放在一个顺序有序表顺序有序表L中，并按其关键字从中，并按其关键字从小到大排好了序。小到大排好了序。 先求位于查找区间正中的元素的下标先求位于查找区间正中的元素的下标mid，用其关键字用其关键字与给定值与给定值x比较比较: Lmid.Key = x，查找成功；查找成功； Lmid.Key x，把查找区间缩小到表的把查找区间缩小到表的前半部分前半部分，再继续进行对分查找；再继续进行对分查找； Lmid.Key x，把查找区间缩小到表的把查找区间缩小到表的后半部分后半部分，再继续进行对分查找。再继续进行对分查找。 每比较一次，查找区间缩小一半。如果查找区间已缩小每比较一次，查找区间缩小一半。如果查找区间已缩小到一个元素，仍未找到想要查找的元素，则查找失败。到一个元素，仍未找到想要查找的元素，则查找失败。查找成功的例子查找成功的例子- -1 0 1 3 4 6 8 10 1260 1 2 3 4 5 6 7 8lowmidhigh6 6 8 10 125 6 7 8low midhigh665low mid high6查找失败的例子查找失败的例子- -1 0 1 3 4 6 8 10 1250 1 2 3 4 5 6 7 8lowmidhigh5 6 8 10 125 6 7 8low midhigh655low midhigh516考虑对考虑对单链表结构单链表结构如何折半查找？如何折半查找？ 无法实现！无法实现！17class OrderSearchTable int n; DataType *orderT; public: OrderSearchTable(int len) n=len; orderT=new DataTypen; void Create(); int Search(KeyType key);/OrderSearchTable二、折半查找（二分或对分查找）二、折半查找（二分或对分查找）18int Search_Bin (KeyType key ) / 在有序表中折半查找其关键字等于在有序表中折半查找其关键字等于key的数据元素。的数据元素。/ 若找到，则函数值为该元素在表中的位置，否则为若找到，则函数值为该元素在表中的位置，否则为-1。low =0; high =n-1; / 置区间初值置区间初值while (low = high) mid = (low + high) / 2; if (key = orderTmid.key) return mid; / 找到待查元素找到待查元素 else if ( key orderTmid.key) high = mid - 1; / 继续在前半区间进行查找继续在前半区间进行查找 else low = mid + 1; / 继续在后半区间进行查找继续在后半区间进行查找 return -1; / 顺序表中不存在待查元素顺序表中不存在待查元素 / Search_Bin193）算法分析：）算法分析：orderT: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 2 4 6 8 10 13 15 18 20 22 24 25 27 30 156241081324202718222530折半查找的判定树：比较次数不超过完全二叉树高度。折半查找的判定树：比较次数不超过完全二叉树高度。20最多的比较次数不超过二叉树的高度：所以最多的比较次数不超过二叉树的高度：所以最坏情况下最坏情况下的查找长度是：的查找长度是：折半折半查找成功查找成功的平均查找长度：的平均查找长度： 设查找任一元素的概率都相等，即：设查找任一元素的概率都相等，即：pi=1/n 在第在第k层上最多有层上最多有2k-1 个结点，在第个结点，在第k层上的结点需层上的结点需比较比较k次。所以：次。所以： )1n(log)n(T2 niiniiisuccpcpASL11) 1 ( niisucccASL1n1)2*h2*)1h(.2*32*21*1(n12*kn1cn1ASL1h2h211kh1kin1isucc 12)1h(2h2)1h( 232211h1h2h21 nlog1) 1n(logn1n )n) 1n(log) 1n(n1) 12) 1h(n1 ASL222hsucc 22二、折半查找（二分或对分查找）二、折半查找（二分或对分查找）23已知一个长度为已知一个长度为16的顺序表的顺序表L，其元素按关键字有序，其元素按关键字有序排列，若采用折半查找法查找一个不存在的元素，排列，若采用折半查找法查找一个不存在的元素，则比较次数最多是（）则比较次数最多是（） A：4 B：5 C：6 D：72010年全国研究生考试计算机统考真题年全国研究生考试计算机统考真题 24三、索引顺序表的查找三、索引顺序表的查找(分块查找分块查找)1. 概念：是顺序查找的一种改进。概念：是顺序查找的一种改进。索引项索引项：(key,addr), key 是关键字，是关键字，addr是地址。是地址。索引表：索引表：由索引项构成的顺序表。由索引项构成的顺序表。22 15 13 8 17 20 35 24 33 40 36 29 50 48 60 68 54 6122 40 680 6 12最大关键字最大关键字(key)起始地址起始地址(addr)如何查找关键字为如何查找关键字为60的元素的元素?252.分块查找的算法思想：分块查找的算法思想：D=d1,d2,.,dn1) 将数据分为将数据分为s个块个块 B1,B2, , Bs ；2) 块间有序：当块间有序：当ikey=key: 查找成功，返回查找成功，