数据结构课程的内容课件.ppt

《数据结构课程的内容课件.ppt》由会员分享，可在线阅读，更多相关《数据结构课程的内容课件.ppt（28页珍藏版）》请在三一文库上搜索。

1、1,数据结构课程的内容,2,8.1 基本概念 8.2 静态查找表 8.3 动态查找表 8.4 哈希表,第8章 查找,教材第8、11和12章省略，因操作系统课程会涉及。,3,8.1 基本概念,若表中存在特定元素，称查找成功，应输出该记录； 否则，称查找不成功（也应输出失败标志或失败位置）,查找表 查 找 查找成功 查找不成功 静态查找 动态查找 关键字 主关键字 次关键字,由同一类型的数据元素（或记录）构成的集合。,查询(Searching)特定元素是否在表中。,只查找，不改变集合内的数据元素。 既查找，又改变集合内的数据元素。 记录中某个数据项的值，可用来识别一个记录 ( 预先确定的记录的某种

2、标志 ) 可以唯一标识一个记录的关键字,例如“学号”,例如“女”,是一种数据结构,识别若干记录的关键字,4,（2）对查找表常用的操作有哪些？ 查询某个“特定的”数据元素是否在表中； 查询某个“特定的”数据元素的各种属性； 在查找表中插入一元素； 从查找表中删除一元素。,（3) 有哪些查找方法？ 查找方法取决于表中数据的排列方式;,讨论：,（1）查找的过程是怎样的？ 给定一个值K，在含有n个记录的文件中进行搜索，寻找一个关键字值等于K的记录，如找到则输出该记录，否则输出查找不成功的信息。,例如查字典,针对静态查找表和动态查找表的查找方法也有所不同。,“特定的”=关键字,5,（4）如何评估查找方法

3、的优劣？,明确：查找的过程就是将给定的K值与文件中各记录的关键字项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为平均查找长度（ASL：average search length）。,其中： n是文件记录个数； Pi是查找第i个记录的查找概率（通常取等概率,即Pi =1/n）; Ci是找到第i个记录时所经历的比较次数。,统计意义上的数学期望值,物理意义：假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为ASL。,显然，ASL值越小，时间效率越高。,6,针对静态查找表的查找算法主要有：,8.2 静态查找表,静态查找表的抽象数据类型参见教材P216。,一、顺

4、序查找（线性查找） 二、折半查找（二分或对分查找） 三、静态树表的查找 四、分块查找（索引顺序查找）,7,一、顺序查找（ Linear search，又称线性查找 ）,（1）顺序表的机内存储结构：,typedef struct ElemType *elem; /表基址，0号单元留空。表容量为全部元素 int length; /表长，即表中数据元素个数 SSTable;,顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最直接的办法。 对顺序结构如何线性查找？见下页之例或教材P216； 对单链表结构如何线性查找？函数虽未给出，但也很容易编写；只要知道头指针head就可以“顺藤摸瓜”； 对非线性

5、树结构如何顺序查找?可借助各种遍历操作！,8,（2）算法的实现：,技巧：把待查关键字key存入表头或表尾（俗称“哨兵”），这样可以加快执行速度。,例：,若将待查找的特定值key存入顺序表的首部（如0号单元），则顺序查找的实现方案为：从后向前逐个比较！,int Search_Seq( SSTable ST , KeyType key ) /在顺序表ST中，查找关键字与key相同的元素；若成功，返回其位置信息，否则返回0 ST.elem0.key =key; /设立哨兵，可免去查找过程中每一步都要检测是否查找完毕。当n1000时，查找时间将减少一半。 for( i=ST.length; ST.el

6、em i .key!=key; - - i ); /不要用for(i=n; i0; - -i) 或 for(i=1; i=n; i+) return i; /若到达0号单元才结束循环，说明不成功，返回0值(i=0)。成功时则返回找到的那个元素的位置i。 / Search_Seq,9,返回特殊标志，例如返回空记录或空指针。前例中设立了“哨兵”，就是将关键字送入末地址ST.elem0.key使之结束并返回 i=0。 讨论 查找效率怎样计算？ 用平均查找长度ASL衡量。,讨论 查不到怎么办？,讨论 如何计算ASL？,分析： 查找第1个元素所需的比较次数为1； 查找第2个元素所需的比较次数为2； 查找

7、第n个元素所需的比较次数为n；,总计全部比较次数为：12n = (1+n)n/2,未考虑查找不成功的情况：查找哨兵所需的比较次数为n+1,这是查找成功的情况,若求某一个元素的平均查找次数，还应当除以n（等概率）， 即： ASL（1n）/2 ，时间效率为 O(n) 思考不成功的计算,10,二、折半查找（又称二分查找或对分查找）,优点：算法简单，且对顺序结构或链表结构均适用。 缺点： ASL 太长，时间效率太低。,这是一种容易想到的查找方法。 先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小至左半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成

8、功或失败为止。,对顺序表结构如何编程实现折半查找算法？ 见下页之例，或见教材（P219） 对单链表结构如何折半查找？ 无法实现！因全部元素的定位只能从头指针head开始 对非线性(树)结构如何折半查找？ 可借助二叉排序树来查找（属动态查找表形式）。,如何改进？,讨论 顺序查找的特点：,11, 运算步骤： (1) low =1,high =11 ,mid =6 ，待查范围是 1,11； (2) 若 ST.elemmid.key key，说明keylow ,mid-1， 则令：high =mid1;重算 mid ； (4)若 ST.elem mid .key = key，说明查找成功，元素序号=m

9、id; 结束条件： （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,此例作为自测的算法题之一，建议上机验证。,12,讨论 若关键字不在表中，怎样得知何时停止？

10、,典型标志是：当查找范围的上界下界时停止查找。,讨论 二分查找的效率（ASL）,1次比较就查找成功的元素有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）个； 为方便起见，假设表中全部n个元素 2m-1个，此时就不讨论第m次比较后还有剩余元素的情况了。,全部比较总次数为120221322423m2m1 ,推导过程,13,平均每个数据的查找时间还要除以n，所以：,（详细推导

11、过程见教材P221的附录）,课堂练习（多项选择）：,采用链式存贮结构 记录的长度128 采用顺序存贮结构 记录按关键字递增有序,使用折半查找算法时，要求被查文件：,思考：假设在有序线性表a20上进行折半查找，则平均查找长度为 。,14,查找过程可用二叉树描述：每个记录用一个结点表示；结点中值为该记录在表中位置，这个描述查找过程的二叉树称为判定树。n个元素的表的折半查找的判定树是唯一的，即：判定树由表中元素个数决定。 找到有序表中任一记录的过程就是：走了一条从根结点到与该记录相应的结点的路径。 比较的关键字个数：为该结点在判定树上的层次数。 查找成功时比较的关键字个数最多不超过树的深度 d :

12、d = log2 n + 1 若所有结点的空指针域设置为一个指向一个方形结点的指针，称方形结点为判定树的外部结点；对应的，圆形结点为内部结点。 查找不成功的过程 就是走了一条从根结点到外部结点的路径。 做习题新建 Microsoft Word 文档.doc,折半查找效率分析法2（参见教材P220）：,15,三、静态树表的查找,讨论2：当有序表中各记录的查找概率不相等时，该如何查？,首先要明确，此时用折半查找法未必最优！（参见教材P222例）,改进：若将各记录概率看作是二叉树之权值，则转为研究带权路径长度最小的二叉树（类似最优二叉树）。,讨论1：对有序表还有其他查找算法吗？,静态最优查找树算法时

13、间代价高； 实用算法：近似最优查找树（次优查找树） （参见教材P222225）,有，如斐波那契查找和插值查找等（参见教材P221222）,16,四、分块查找（索引顺序查找）,这是一种顺序查找的另一种改进方法。 先让数据分块有序，即分成若干子表，要求每个子表中的数值（用关键字更准确）都比后一块中数值小（但子表内部未必有序）。 然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针）。,索引表,最大关键字,起始地址,第1块,第2块,第3块,22,48,86,例：,特点：块间有序，块内无序,17,查找步骤分两步进行：, 对索引表使用折半查找法（因为索引表是有序表）； 确定

14、了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）； 查找效率：ASL=Lb+Lw,对索引表查找的ASL,对块内查找的ASL,S为每块内部的记录个数，n/s即块的数目,例如当n=9，s=3时，ASLbs=3.5,而折半法为3.1,顺序法为5,18,习题 要进行线性查找，则线性表 A ；要进行二分查找，则线性表 B ；要进行散列查找，则线性表 C 。顺序存储的表格，其中有90000个元素，已按关键项的值的上升顺序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查找法查找时，平均比较次数约为 D ，最大比较次数为 E 。 供选择的答案

15、： AC： 必须以顺序方式存储 必须以链表方式存储 必须以散列方式存储 既可以以顺序方式，也可以以链表方式存储 必须以顺序方式存储且数据元素已按值递增或递减的次序排好 必须以链表方式存储且数据元素已按值递增或递减的次序排好 D，E： 25000 30000 45000 90000 答案： A= B= C= D E ,19,特点：,一、二叉排序树的定义 二、二叉排序树的插入与删除 三、二叉排序树的查找分析 四、平衡二叉树,8.2 动态查找表,表结构在查找过程中动态生成。,要求：,对于给定值key, 若表中存在其关键字等于key的记录，则查找成功返回； 否则插入关键字等于key 的记录。,典型的动

16、态表二叉排序树,20,一、二叉排序树的定义,练：下列2种图形中，哪个不是二叉排序树 ？,-或是一棵空树；或者是具有如下性质的非空二叉树： （1）左子树的所有结点均小于根的值； （2）右子树的所有结点均大于根的值； （3）它的左右子树也分别为二叉排序树。,21,二、二叉排序树的插入与删除,将数据元素构造成二叉排序树的优点： 查找过程与顺序结构有序表中的折半查找相似，查找效率高； 中序遍历此二叉树，将会得到一个关键字的有序序列（即实现了排序运算）； 如果查找不成功，能够方便地将被查元素插入到二叉树的叶子结点上，而且插入或删除时只需修改指针而不需移动元素。,注：若数据元素的输入顺序不同，则得到的二叉

17、排序树形态也不同！,这种既查找又插入的过程称为动态查找。 二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态查找表的一种适宜表示。,22,45,如果待查找的关键字序列输入顺序为： （24，53， 45，45，12，24，90），,24,讨论1：二叉排序树的插入和查找操作,则生成二叉排序树的过程为：,例：输入待查找的关键字序列=（45，24，53，45，12，24，90）,则生成的二叉排序树形态不同：,23,二叉排序树的查找&插入算法如何实现？,查找算法参见教材P228算法9.5（a,b）; 插入算法参见教材P228算法9.6;,24,对于二叉排序树，删除树上一个结点相当于删除有序序

18、列中的一个记录，删除后仍需保持二叉排序树的特性。 （对链表进行删除操作是很方便的）,讨论2：二叉排序树的删除操作,如何删除一个结点？ 假设：*p表示被删结点的指针； PL和PR 分别表示*P的左、右孩子指针； *f表示*p的双亲结点指针；并假定*p是*f的左孩子；则可能有三种情况： PR 为 * S 的右子树； SL 为 Q（ * S的双亲结点）右孩子,*p为叶子： 删除此结点时，直接修改*f指针域即可； *p只有一棵子树（或左或右）：令PL或PR为*f的左孩子即可； *p有两棵子树：情况最复杂 ,25,*p有两棵子树时，如何进行删除操作？,分析： 设删除前的中序遍历序列为： . s p PR

19、 . /显然p的直接前驱是s 希望删除p后，其它元素的相对位置不变。有两种解决方法： 法1：令*p的左子树为 *f的左子树，*p的右子树为*s的右子树； /即FL=PL ; FR=PR ; 法2：令*s代替*p / *s为*p左子树最右下的叶子,26,法2:：令*s代替*p,法1:令*p的左子树为 *f的左子树，*p的右子树为*s的右子树；,例：请从下面的二叉排序树中删除结点P。,S,27,1) 二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径。 比较的关键字次数此结点的层次数; 最多的比较次数树的深度（或高度），即 log2 n+1 2) 一棵二叉排序树的平均

20、查找长度为：,三、二叉排序树的查找分析,其中： ni 是每层结点个数； Ci 是结点所在层次数； m 为树深。,最坏情况：即插入的n个元素从一开始就有序， 变成单支树的形态！ 此时树的深度为n ; ASL= (n+1)/2 此时查找效率与顺序查找情况相同。,28,最好情况：即：与折半查找中的判定树相同（形态比较均衡）,3）对有 n 个关键字的二叉排序树的平均查找长度: 设每种树态出现概率相 同 ，查找每个关键字也是等概率的。 则ASL求解过程可推导。 （详见教材P232）,树的深度为：log 2n +1 ； ASL=log 2(n+1) 1 ；与折半查找相同。,结论：二叉排序树的ASL2（11/n）ln n,