数据结构(下)课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《数据结构(下)课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课件
- 资源描述:
-
1、1数据结构数据结构(下下)2第第8章查找章查找第第9章章 排序排序第第10章章 索引与散列索引与散列3第8章 查找4 查找,也称为检索。查找某人的地址、电话号码;查某单位45岁以上职工等,都属于查找范畴。本书中,我们规定查找是按关键字进行的,所谓关键字(key)是数据元素(或记录)中某个数据项的值,用它可以标识(或识别)一个数据元素。例如,描述一个考生的信息,可以包含:考号、姓名、性别、年龄、家庭住址、电话号码、成绩等关键字。但有些关键字不能唯一标识一个数据元素,而有的关键字可以唯一标识一个数据元素。如刚才的考生信息中,姓名不能唯一标识一个数据元素(因有同名同姓的人),而考号可以唯一标识一个数
2、据元素(每个考生考号是唯一的,不能相同)。我们将能唯一标识一个数据元素的关键字称为主关键字,而其它关键字称为次关键字。一、查找的基本概念一、查找的基本概念5 有了主关键字及关键字后,我们可以给查找下一个完整的定义。所谓查找,就所谓查找,就是根据给定的值,在一个表中查找出其关是根据给定的值,在一个表中查找出其关键字等于给定值的数据元素键字等于给定值的数据元素(即记录即记录),若表中有这样的元素,则称查找是成功的,此时查找的信息为给定整个数据元素的输出或指出该元素在表中的位置;若表中不存在这样的记录,则称查找是不成功的,或称查找失败,并可给出相应的提示。6 要衡量一种查找算法的优劣,主要是看要找的
3、值与关键字的比较次数,但我们将找到给定值与关键字的比较次数的平均值(平均查找长度平均查找长度)来作为衡量一个查找算法好坏的标准,对于一个含有n个元素的表,查找成功时的平均查找长度可表示为ASL=,其中i为查找第i个元素的概率,且 =1。一般情形下我们认为查找每个元素的概率相等,i为查找第i个元素所用到的比较次数。niiicp1niip171、顺序查找顺序查找二、二、静态查找表静态查找表 顺序查找的基本思想 顺序查找是一种最简单的查找方法,它的基本思想是:从表的一端开始,顺序扫描线性表,依次将扫描到的结点关键字和待找的值相比较,若相等,则查找成功,若整个表扫描完毕,仍末找到关键字等于的元素,则查
4、找失败。顺序查找既适用于顺序表,也适用于链表。若用顺序表,查找可从前往后扫描,也可从后往前扫描,但若采用单链表,则只能从前往后扫描。另外,顺序查找的表中元素可以是无序的。8 顺序查找性能分析(1)在最坏的情况下,顺序查找需要比较n次,即最大查找长度MSL=n。(2)假设在每个记录查找的概率相等,即有pi=1/n,由于查找第i个记录需要比较i次,即Ci=i,于是,查找成功的平均查找长度 ASL=从ASL可知,当n较大时,ASL值较大,查找的效率较低。niiicp1ninin11)1(21n 顺序查找的优点是算法简单。顺序查找的缺点顺序查找的缺点是查找效率低,当当n n较大时,不宜采用顺序查找较大
5、时,不宜采用顺序查找。92 2、折半查找、折半查找 首先将待查值K与有序表R1到Rn的中点mid上的关键字Rmid.key进行比较,若相等,则查找成功;否则,若Rmid.keyk,则在R1到Rmid-1中继续查找,若有Rmid.keyk,则在Rmid+1到Rn中继续查找。每通过一次关键字的比较,区间的长度就缩小一半,区间的个数就增加一倍,如此不断进行下去,直到找到关键字为K的元素;若当前的查找区间为空(表示查找失败)。折半查找的基本思想 折半查找,也称二分查找,它是一种高效查找方法。10从上述查找思想可知,每进行一次关键字比较,区间长度缩小一半,故称为折半(查找的范围缩小一半)。而区间数目增加
6、一倍,故也称为二分(区间一分为二),mid=(low+high)/2注:折半查找的结束条件是(1)区间中间位置记录的关键字等于给定的值,区间中间位置记录的关键字等于给定的值,则表明查找成功。则表明查找成功。(2)查找区间的大小差小于查找区间的大小差小于0,表明查找不成功。,表明查找不成功。11例:假 设 给 定 有 序 表 中 关 键 字 为8,17,25,44,68,77,98,100,115,125,将查找K=17和和K=120的情况描述为图8-1及图8-2所示。8 17 25 44 68 77 98 10 115 125 low high (a)初始情形 8 17 25 44 68 44
7、 98 100 115 125 low high mid (b)经过一次比较后的情形 12 8 17 25 44 68 77 98 100 115 125(c)经过二次比较后的情形 (Rmid.key=17)low mid high 图 8-1 查找 K=17 的示意图(查找成功)8 17 25 44 68 77 98 100 115 125 (a)初始情形 low high 13 8 17 25 44 68 77 98 100 115 125 (b)经过一次比较后的情形 mid low high 8 17 25 44 68 77 98 100 115 125 (c)经过二次比较后的情形 mi
8、d low high 14 8 17 25 44 68 77 98 100 115 125 (d)经过三次比较后的情形 mid low high 17 25 44 77 98 100 115 125 high low m id (e)经 过 四 次 比 较 后 的 情 形(highlow)图 8-2 查 找 K=120 的 示 意 图 (查 找 不 成 功)15折半查找的性能分析 可用二叉树来描述折半查找过程。把当前查找区间的中点作为根结点,左子区间和右子区间分别作为根的左子树和右子树,左子区间和右子区间再按类似的方法,由此得到的二叉树称为二分查找的判定树。例如,图8-1给定的关键字序列的判定
9、树见图8-3。44 8 25 17 98 77 68 100 115 125 图 8-3 具有 10 个关键字序列的二分查找判定树 16 从图8-3可知,查找根结点68,需一次查找,查找17和100,各需二次查找,查找8、25、77、115各需三次查找,查找44、98、125各需四次查找。于是,可以得到结论:二叉树第k层结点的查找次数各为k次(根结点为第1层),而第k层结点数最多为2k-1个。假设该二叉树的深度为h,则折半查找的成功的平均查找长度为(假设每个结点的查找概率相等):ASL=1/n 1/n(1+22+322+h2h-1)niiicp1niic117三、动态查找表三、动态查找表 1
10、1、二叉排序树、二叉排序树二叉排序树的概述 二叉排序树或者是一棵空树,或者是一棵具有如下特征的非空二叉树:(1)若它的左子树非空,则左子树上所有结点的关键字均小于根结点的关键字;(2)若它的右子树非空,则右子树上所有结点的关键字均大于等于根结点的关键字;(3)左、右子树本身又都是一棵二叉排序树。18二叉排序树的数据类型描述可用一个二叉链表来描述一棵二叉排序树,具体为:struct Btreenode elemtype key;/代表关键字 Btreenode *lch,*rch;/代表左、右孩子 ;二叉排序树的插入运算 若二叉排序树为空,则作为根结点插入,否则,若待插入的值小于根结点值,则作为
11、左子树插入,否则作为右子树插入。19例:给定关键字序列79,62,68,90,88,89,17,5,100,120,生成二叉排序树过程如图8-4所示。(注:二叉排序树与关键字排列顺序有关,排列顺序不一样,得到的二叉排序树也不一样)79 62 79 68 62 79 68 62 79 90 88 68 62 79 90(a)(b)(c)(d)(e)20 88 68 62 79 90 89 89 17 88 68 62 79 90 17 5 88 68 62 79 90 89(f)(g)(h)89 17 5 88 68 62 79 90 100 89 17 5 88 68 62 79 90 100
12、 120 图 8-4 二叉排序树的生成过程(i)(j)21二叉排序树上的查找 若二叉排树为空,则查找失败,否则,先拿根结点值与待查值进行比较,若相等,则查找成功,若根结点值大于待查值,则进入左子树重复此步骤,否则,进入右子树重复此步骤,若在查找过程中遇到二叉排序树的叶子结点时,还没有找到待找结点,则查找不成功。二叉排序树查找的性能分析 在二叉排序树查找中,成功的查找次数不会超过二叉树的深度,而具有n个结点的二叉排序树的深度,最好为log2n,最坏为n。因此,二叉排序树查找的最好时间复杂度为O(log2n),最坏的时间复杂度为O(n)。222 2、平衡二叉树查找、平衡二叉树查找平衡二叉树概述 由
13、阿德尔森一维尔斯和兰迪斯(Adelson-Velskii and Landis)于1962年首先提出的,所以又称为AVL树。若一棵二叉树中每个结点的左、右子树的深度之差的绝对值不超过1,则称这样的二叉树为平衡二叉树。将该结点的左子树深度减去右子树深度的值,称为该结点的平衡因子(balance factor)。即,一棵二叉排序树中,所有结点的平衡因子只能为0、1、-1时,则该二叉排序树就是一棵平衡二叉树,否则就不是一棵平衡二叉树。23 5 2 3 4 16 7 图 8-5 一棵平衡二叉树 6 1 2 3 4 8 5 7 图 8-6 一 棵 非 平 衡 二 叉 树 非平衡二叉树的平衡处理 LL型的
14、处理(左左型)24 如图8-7所示,在C的左孩子B上插入一个左孩子结点A,使C的平衡因子由1变成了2,成为不平衡的二叉树序树。这时的平衡处理为:将C顺时针旋转,成为B的右子树,而原来B的右子树则变成C的左子树,待插入结点A作为B的左子树。平 衡外 理 1 A B C 0 2 C B A 0 0 0 图 8-7 LL 型 平 衡 外 理 25LR型的处理(左右型)如图8-8所示,在C的左孩子A上插入一个右孩子B,使的C的平衡因子由1变成了2,成为不平衡的二叉排序树。这是的平衡处理为:将B变到A与C 之间,使之成为LL型,然后按第(1)种情形LL型处理。0-1 C A B 2 0 1 C A B
15、2 B 0 0 C A 0 平衡处理 旋转 图 8-8 LR 型平衡处理 26RR型的处理(右右型)如图8-9所示,在A的右孩子B上插入一个右孩子C,使A的平衡因子由-1变成-2,成为不平衡的二叉排序树。这时的平衡处理为:将A逆时针旋转,成为B的左子树,而原来B的左子树则变成A的右子树,待插入结点C成为B的右子树。平衡处理 a-1 C B A 0-2 C B A 0 0 0 图 8-9 RR 型平衡处理 27RL型的处理(右左型)如图8-10所示,在A的右孩子B上插入一个右孩子C,使A的平衡因子由-1变成-2,成为不平衡的二叉排序树。这时的平衡处理为:将A逆时针旋转,成为B的左子树,而原来B的
16、左子树则变成A的右子树,待插入结点C成为B的右子树。平衡处理 a-1 C B A 0-2 C B A 0 0 0 图 8-10 RR 型平衡处理 28例:设一组记录的关键字按以下次序进行插入:4、5、7,2、1、3、6,其生成及调整成二叉平衡树的过程示于图8-11。图8-11 二叉平衡树插入结点(结点旁的数字为其平衡因子)29平衡二叉树的查找及性能分析 平衡二叉树本身就是一棵二叉排序树,故它的查找与二叉排序树完全相同。但它的查找 性能优于二叉排序树,不像二叉排序树一样,会出现最坏的时间复杂度O(n),它的时间复杂度与二叉排序树的最好时间复杂相同,都为O(log2n)。例:对关键字序列4,5,7
17、,2,1,3,6,试用二叉排序树和平衡二叉树两种方法查找,给出查找6的次数及成功的平均查找长度。分析:由于关键字序列的顺序己经确定,故得到的二叉排序树和平衡二叉树都是唯一的。得到的平衡二叉树见图8-12,得到的二叉排序树见图8-13。30 0 6 2 1 4 3 7 0 0 0 0 0 5 0 4 2 3 1 5 7 6 图8-13 由关键字序列4,5,7,2,1,3,6生成的二叉排序树 图8-12 由关键字序列4,5,7,2,1,3,6生成的平衡二叉树从图8-13的二叉排序树可知,查找6需4次,平均查找长度ASL=(1+2+2+3+3+3+4)/7=18/72.57。从图8-12的平衡二叉树
18、可知,查找6需2次,平均查找长度ASL=(1+2+2+3+3+3+3)=17/72.43。从结果可知,平衡二叉树的查找性能优于二叉排序树。31第第9章章 排序排序 32学习重点:排序的基本概念和术语 插入排序:直接插入排序和希尔排序 交换排序:冒泡排序和快速排序 选择排序:简单选择排序和堆排序 归并排序 基数排序 各种排序方法的比较分析339.1 排序的基本概念排序的基本概念9.2 插入排序插入排序9.3 交换排序交换排序9.4选择排序选择排序9.5 归并排序归并排序9.6 基数排序基数排序9.7 小结小结34 排序(排序(SortingSorting)排序又称分类,是把一组记排序又称分类,是
19、把一组记录(元素)按照某个域的值的递增(即由小到大)录(元素)按照某个域的值的递增(即由小到大)或递减(即由大到小)的次序重新排列的过程。或递减(即由大到小)的次序重新排列的过程。可以使杂乱无章的数据序列重新排列成有序序列。可以使杂乱无章的数据序列重新排列成有序序列。35排序方法的分类排序方法的分类 内部排序是指待排序的记录存放在计算机内存之中;外部排序是指待排序的记录数量很大,以至于内存容纳不下而存放在外存储器之中,排序过程需要访问外存。本章主要讨论内部排序本章主要讨论内部排序 36 排序的依据可以是记录的主关键字,也可以是次关键字,甚至是若干数据项的组合。为了方便讨论,把排序所依据的数据项
20、统称排序关键字,简称关键字。假设含有n个记录的序列为R1,R2,Rn,其相应的关键字序列为K1,K2,Kn,所谓排序就是将记录Ri按关键字Ki非递减(或非递增)的顺序重新排列起来。37内部排序的方法内部排序的方法插入类插入类交换类交换类选择类选择类 归并类归并类其它方法其它方法38 将要排序的记录集合,在本章中选用顺序存储方法。为了讨论方便,在此把排序关键字假设为整型。假设排序依据的关键字为整型。记录的结构定义如下:const MAXSIZE=1000;/*数组最大容量*/typedef int ElemType;/*关键字的类型*/typedef struct /*记录结构 *ElemTyp
21、e key;/*排序关键字域*/int oth;/*其它域,根据需要自己设定*/node;399.2 插入排序插入排序 插入排序(插入排序(Insertion Sort)又可分)又可分几种不同的方法,这里仅介绍三种几种不同的方法,这里仅介绍三种方法:方法:直接插入排序直接插入排序 折半插入排序折半插入排序 希尔排序希尔排序409.2.1 直接插入排序直接插入排序 直接插入排序(直接插入排序(Straight Insertion Sort)是一种最简单的排序方法。是一种最简单的排序方法。它的基本操作是将一个记录插入到一个它的基本操作是将一个记录插入到一个长度为长度为m(假设)的有序表中,使之仍(
22、假设)的有序表中,使之仍保持有序,从而得到一个新的长度为保持有序,从而得到一个新的长度为m1的有序表。的有序表。41算法思路:设有一组关键字设有一组关键字K1,K2,Kn;排序;排序一开始就认为一开始就认为K1是一个有序序列;让是一个有序序列;让K2插入上插入上述表长为述表长为1的有序序列,使之成为一个表长为的有序序列,使之成为一个表长为2的有序序列;然后让的有序序列;然后让K3插入上述表长为插入上述表长为2的有的有序序列,使之成为一个表长为序序列,使之成为一个表长为3的有序序列;的有序序列;依次类推,最后让依次类推,最后让Kn插入上述表长为插入上述表长为n-1的有的有序序列,得一个表长为序序
23、列,得一个表长为n的有序序列。的有序序列。42例例9.1设有一组关键字序列设有一组关键字序列55,22,44,11,33,这里,这里n=5,即有,即有5个记录。请将其按由小个记录。请将其按由小到大的顺序排序。到大的顺序排序。43直接插入排序算法如下:直接插入排序算法如下:void stinsort(node rMAXSIZE,int n)for(i=2;i r0.key)rj+1=rj;j-;rj+1=r0;/*将r0即原ri记录内容,插到rj后一位置*/*sinsort*/44 此算法外循环n-1次,在一般情况下内循环平均比较次数的数量级为(n),所以算法总时间复杂度为(n2)。由于比较过程
24、中,当Kj 与K0 相等时并不移动记录,因此直接插入排序方法是稳定的。直接插入排序也可用单链表做存储结构 459.2.2 折半插入排序折半插入排序 当直接插入排序进行到某一趟时,对于当直接插入排序进行到某一趟时,对于ri.key来讲,前边来讲,前边i-1个记录已经按关键个记录已经按关键字有序。此时不用直接插入排序的方法,字有序。此时不用直接插入排序的方法,而改为折半查找,找出而改为折半查找,找出ri.key应插的位应插的位置,然后插入。这种方法就是折半插入置,然后插入。这种方法就是折半插入排序(排序(Binary insertion sort)。)。算法如下:算法如下:46 void bina
25、sort(struct node rMAXSIZE,int n)for(i=2;i=n;i+)r0=ri;l=1;h=i-1;/*认为在认为在rlow和和ri-1之间已经有序之间已经有序*/whil(l=h)/*对有序表进行折半查找对有序表进行折半查找*/mid=(l+h)/2;if(r0.key=l;j-)rj+1=rj;rl=r0;/*此处可以改为此处可以改为rh=r0;吗?;吗?*/*binasort*/47 折半插入排序,关键字的比较次数折半插入排序,关键字的比较次数由于采用了折半查找而减少,数量由于采用了折半查找而减少,数量级为级为(nlog2n),但是元素移动次数,但是元素移动次数
展开阅读全文