资源描述
*,*,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考!,数据结构课程内容,1/28,1,8.1,基本概念,8.2,静态查找表,8.3,动态查找表,8.4 哈希表,第,8,章 查找,教材第8、11和12章省略，因操作系统课程会包括。,2/28,2,8.1 基本概念,若表中存在特定元素，称查找成功，应输出该统计；,不然，称查找不成功（也应输出失败标志或失败位置）,查找表,查 找,查找成功,查找不成功,静态查找,动态查找,关键字,主关键字,次关键字,由同一类型数据元素（或统计）组成集合。,查询(,Searching),特定元素,是否在表中。,只查找，不改变集合内数据元素。,既查找，又改变集合内数据元素。,统计中某个数据项值，可用来识别一个统计,(预先确定统计某种标志),能够,唯一,标识一个统计关键字,比如“学号”,比如“女”,是一个数据结构,识别若干统计关键字,3/28,3,（2）对查找表惯用操作有,哪些？,查询某个“特定”数据元素是否在表中；,查询某个“特定”数据元素各种属性；,在查找表中插入一元素；,从查找表中删除一元素。,（3)有哪些查找方法？,查找方法取决于表中数据排列方式;,讨论：,（1）查找过程是怎样？,给定一个值K，在含有n个统计文件中进行搜索，寻找一个关键字值等于K统计，如找到则输出该统计，不然输出查找不成功信息。,比如查字典,针对静态查找表和动态查找表查找方法也有所不一样,。,“特定”=,关键字,4/28,4,（4）怎样评定查找方法优劣？,明确：,查找过程就是将给定K值与文件中各统计关键字项进行比较过程。所以用比较次数平均值来评定算法优劣。称为,平均查找长度,（ASL：average search length）。,其中：,n,是文件统计个数；,P,i,是查找第i个统计查找概率（通常取等概率,即P,i,=1/n）;,C,i,是找到第i个统计时所经历比较次数。,统计意义上数学期望值,物理意义：,假设每一元素被查找概率相同，则查找每一元素所需比较次数之总和再取平均，即为ASL。,显然，ASL值越小，时间效率越高。,5/28,5,针对静态查找表查找算法主要有：,8.2 静态查找表,静态查找表抽象数据类型参见教材P216。,一、,次序查找（线性查找）,二、,折半查找（二分或对分查找）,三、,静态树表查找,四、,分块查找（索引次序查找）,6/28,6,一、次序查找（,Linear search，,又称线性查找）,（1）,次序表机内存放结构：,typedef struct,ElemType *elem;,/表基址，0号单元留空。表容量为全部元素,int length;,/表长，即表中数据元素个数,SSTable;,次序查找：即用逐一比较方法次序查找关键字，这显然是最直接方法。,对,次序结构,怎样线性查找？,见下页之例,或教材P216；,对,单链表结构,怎样线性查找？函数虽未给出，但也很轻易编写；只要知道头指针head就能够“顺藤摸瓜”；,对,非线性树结构,怎样次序查找?可借助各种遍历操作！,7/28,7,（2）,算法实现：,技巧：,把待查关键字,key,存入表头或表尾（俗称“哨兵”），这么能够加紧执行速度。,例：,若将待查找特定值key,存入,次序表,首部,（如0号单元），则次序查找实现方案为：,从后向前,逐一比较！,int,Search_Seq,(SSTable,ST,KeyType key),/在次序表ST中，查找关键字与key相同元素；若成功，返回其位置信息，不然返回0,ST.elem,0,.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,;,/若抵达0号单元才结束循环，说明不成功，返回0值(i=0)。成功时则返回找到那个元素位置i。,/Search_Seq,8/28,8,返回特殊标志，比如返回空统计或空指针。前例中设置了“哨兵”，就是将关键字送入末地址ST.elem,0,.key使之结束并返回 i=0。,讨论,查找效率怎样计算？,用平均查找长度ASL衡量。,讨论,查不到怎么办？,讨论,怎样计算ASL？,分析：,查找第1个元素所需比较次数为1；,查找第2个元素所需比较次数为2；,查找第n个元素所需比较次数为n；,总计全部比较次数为：12n=(1+n)n/2,未考虑查找不成功情况：查找哨兵所需比较次数为n+1,这是查找成功情况,若求某一个元素平均查找次数，还应该除以n（等概率），,即：,ASL（1n）/2,，时间效率为,O(n),思索不成功计算,9/28,9,二、折半查找（又称二分查找或对分查找）,优点：,算法简单，且对次序结构或链表结构均适用。,缺点：,ASL 太长，时间效率太低。,这是一个轻易想到查找方法。,先给数据排序,（比如按升序排好），形成,有序表,，然后再将key与正中元素相比，若key小，则缩小至左半部内查找；再取其中值比较，每次缩小1/2范围，直到查找成功或失败为止。,对,次序表结构,怎样编程实现折半查找算法？,见下页之例,，或见教材（P219）,对,单链表结构,怎样折半查找？,无法实现！,因全部元素定位只能从头指针head开始,对,非线性(树)结构,怎样折半查找？,可借助二叉排序树来查找（属动态查找表形式）。,怎样改进？,讨论 次序查找特点：,10/28,10,运算步骤,：,(1)low=1,high=11,mid=6，待查范围是 1,11；,(2)若 ST.elemmid.key,key,，说明key,low,mid,-1,，,则令：,high=mid1,;重算 mid；,(4)若 ST.elem mid.key,=key,，说明查找成功，元素序号=mid;,结束条件：,（1）查找成功：ST.elemmid.key=key,（2）查找不成功：,highlow,（意即区间长度小于0）,解：先设定3个辅助标志:,low,high,mid，,折半查找举例：,Low指向待查元素所在区间下界,high指向待查元素所在区间上界,mid指向待查元素所在区间中间位置,已知以下11个元素,有序表,：（05 13 19 21 37 56 64 75 80 88 92）,请查找关键字为,21,和,85,数据元素。,显然有：,mid=,(low+high)/2,此例作为自测算法题之一，提议上机验证。,11/28,11,讨论 若关键字不在表中，怎样得知何时停顿？,经典标志是：当查找范围上界下界时停顿查找。,讨论 二分查找效率（ASL）,1次比较就查找成功元素有1个,（2,0,），,即,中间值；,2次比较就查找成功元素有2个,（2,1,），,即,1/4处（或3/4）处；,3次比较就查找成功元素有4个,（2,2,），,即,1/8处（或3/8）处,4次比较就查找成功元素有8个,（2,3,），,即,1/16处（或3/16）处,则第m次比较时查找成功元素会有,（2,m-1,）,个,；,为方便起见，假设表中全部n个元素 2,m,-1个，,此时就不讨论第m次比较后还有剩下元素情况了。,全部比较总次数为12,0,22,1,32,2,42,3,m2,m1,推导过程,12/28,12,平均每个数据查找时间还要除以n，所以：,（详细推导过程见教材P221附录）,课堂练习,（多项选择）：,采取链式存贮结构,统计长度128,采取次序存贮结构,统计按关键字递增有序,使用折半查找算法时，要求被查文件：,思索：,假设在有序线性表a20上进行折半查找，则平均查找长度为,。,13/28,13,查找过程可用,二叉树,描述：每个统计用一个结点表示；结点中值为该统计在表中位置，这个描述查找过程二叉树称为判定树。n个元素表折半查找判定树是唯一，即：判定树由表中元素个数决定。,找到有序表中任一统计过程就是,：走了一条从根结点到与该统计对应结点路径。,比较关键字个数：,为该结点在判定树上层次数。,查找成功时,比较关键字个数最多不超出树深度 d:,d=,log,2,n,+1,若全部结点空指针域设置为一个指向一个方形结点指针，称方形结点为判定树外部结点；对应，圆形结点为内部结点。,查找不成功过程,就是走了一条从根结点到外部结点路径。,做习题,新建 Microsoft Word 文档.doc,折半查找效率分析法2（参见教材P220）：,14/28,14,三、静态树表查找,讨论2：,当有序表中各统计,查找概率不相等,时，该怎样查？,首先要明确，此时,用折半查找法未必最优,！,（参见教材P222例）,改进：,若将各统计概率看作是二叉树之权值，则转为研究带权路径长度最小二叉树（类似最优二叉树）。,讨论1：,对,有序表,还有其它查找算法吗？,静态最优查找树算法,时间代价高；,实用算法：,近似最优查找树（,次优,查找树）,（参见教材P222225）,有，如斐波那契查找和插值查找等,（参见教材P221222）,15/28,15,四、分块查找（索引次序查找）,这是一个次序查找另一个改进方法。,先让数据,分块有序,，即分成若干子表，要求每个子表中数值（用关键字更准确）都比后一块中数值小（但子表内部未必有序）。,然后将各子表中最大关键字组成一个,索引表,，表中还要包含每个子表起始地址（即头指针）。,索引表,最大关键字,起始地址,22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53,第1块,第2块,第3块,22,48,86,例：,22,48,86,1,7,13,特点：块间有序，块内无序,16/28,16,查找步骤,分两步进行：,对索引表使用折半查找法（因为索引表是有序表）；,确定了待查关键字所在子表后，在子表内采取次序查找法（因为各子表内部是无序表）；,查找效率：,ASL=L,b,+L,w,对索引表查找ASL,对块内查找ASL,S为每块内部统计个数，,n/s,即块数目,比如当n=9，s=3时,，ASL,bs,=,3.5,而折半法为,3.1,次序法为,5,17/28,17,习题,要进行线性查找，则线性表,A,；要进行二分查找，则线性表,B,；要进行散列查找，则线性表,C,。次序存放表格，其中有90000个元素，已按关键项值上升次序排列。现假定对各个元素进行查找概率是相同，而且各个元素关键项值皆不相同。当用次序查找法查找时，平均比较次数约为,D,，最大比较次数为,E,。,供选择答案,：AC：必须以次序方式存放 必须以链表方式存放,必须以散列方式存放 既能够以次序方式，也能够以链表方式存放 必须以次序方式存放且数据元素已按值递增或递减次序排好 必须以链表方式存放且数据元素已按值递增或递减次序排好D，E：25000 30000 45000 90000,答案：A=,B=,C=,D,E,18/28,18,特点：,一、,二叉排序树定义,二、,二叉排序树插入与删除,三、,二叉排序树查找分析,四、平衡二叉树,8.2 动态查找表,表结构在查找过程中动态生成。,要求：,对于给定值key,若表中存在其关键字等于key统计，则查找成功返回；,不然插入关键字等于key 统计。,经典动态表,二叉排序树,19/28,19,一、二叉排序树定义,（a）,（b）,练：,以下2种图形中，哪个不是二叉排序树？,-或是一棵空树；或者是含有以下性质非空二叉树：,（1）左子树全部结点均小于根值；,（2）右子树全部结点均大于根值；,（3）它左右子树也分别为二叉排序树。,20/28,20,二、二叉排序树插入与删除,将数据元素结构成二叉排序树优点：,查找过程与次序结构有序表中,折半查找,相同，查找效率高；,中序遍历,此二叉树，将会得到一个关键字有序序列（,即实现了排序运算,）；,假如查找不成功，能够方便地将被查元素,插入到二叉树叶子结点,上，而且插入或删除时只需修改指针而不需移动元素。,注：,若,数据元素,输入次序不一样，则得到二叉排序树形态也不一样！,这种既查找又插入过程称为,动态查找,。,二叉排序树现有类似于折半查找特征，又采取了链表存放，它是动态查找表一个适宜表示。,21/28,21,45,24,53,12,90,假如待,查找关键字序列输入次序为：,（24，53，45，45，12，24，90），,24,53,45,12,90,查找成功，返回,查找成功，返回,讨论1：二叉排序树插入和查找操作,则生成二叉排序树过程为：,例,：,输入待查找关键字序列=（45，24，53，45，12，24，90）,则生成二叉排序树形态不一样：,查找成功，返回,查找成功，返回,22/28,22,二叉排序树查找&插入算法怎样实现？,查找算法,参见教材P228算法9.5（a,b）;,插入算法,参见教材P228算法9.6;,23/28,23,对于二叉排序树，删除树上一个结点相当于删除有序序列中一个统计，删除后仍需保持二叉排序树特征。,（对链表进行删除操作是很方便）,讨论2：二叉排序树删除操作,怎样删除一个结点？,假设：,*p,表示被删结点指针；,P,L,和,P,R,分别表示,*P左、右孩子指针；,*f,表示*p双亲结点指针；并假定*p是*f,左孩子,；则可能有三种情况：,P,R,为*S 右子树；S,L,为,Q,（*S双亲结点）右孩子,*p为叶子：,删除此结点时，直接修改,*f,指针域即可；,*p只有一棵子树（或左或右）：,令,P,L,或,P,R,为*f左孩子即可；,*p有两棵子树：情况最复杂,24/28,24,*p有两棵子树时，怎样进行删除操作？,分析：,设删除前中序遍历序列为：,.s,p,P,R,.,/显然p直接前驱是s,希望删除,p,后，其它元素相对位置不变。有两种处理方法：,法1：,令,*p,左子树为,*f,左子树，,*p,右子树为*s右子树；,/,即F,L,=P,L,;F,R,=P,R,;,法2：,令*s代替*p,/,*s为*p左子树最右下叶子,25/28,25,F,C,C,L,S,S,L,Q,L,P,P,R,Q,P,R,F,C,C,L,S,S,L,Q,L,P,P,R,Q,法2:,：,令*s代替*p,F,C,C,L,S,S,L,Q,L,P,P,R,Q,法1:,令,*p,左子树为,*f,左子树，,*p,右子树为*s右子树；,例：,请从下面二叉排序树中删除结点P。,S,S,L,26/28,26,1)二叉排序树上查找某关键字等于给定值结点过程，其实就是走了一条从根到该结点路径。,比较关键字次数,此结点层次数;,最多比较次数,树深度（或高度），即,log,2,n+1,2)一棵二叉排序树平均查找长度为：,三、二叉排序树查找分析,其中：,n,i,是每层结点个数；,C,i,是结点所在层次数；,m,为树深。,最坏情况：,即插入n个元素从一开始就有序，,变成单支树形态！,此时树深度为n ;ASL=(n+1)/2,此时查找效率与次序查找情况相同。,27/28,27,最好情况：,即：与折半查找中判定树相同（形态比较均衡）,3）对有 n 个关键字二叉排序树平均查找长度:,设每种树态出现概率相 同，查找每个关键字也是等概率。,则ASL求解过程可推导。,（详见教材P232）,树深度为：log,2,n +1；,ASL=log,2,(n+1)1；与折半查找相同。,结论：二叉排序树ASL2（11/n）ln n,28/28,28,
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
