数据结构与算法-ppt课件

第四章第四章 数据的组织数据的组织 4.1 数据结构数据结构 4.2 文件结构文件结构 4.3 数据库数据库第四章 数据的组织 4.1 数据结构本讲主要内容本讲主要内容 一、数据结构一、数据结构 二、线性表二、线性表 三、栈三、栈 四、队列四、队列 五、树与二叉树五、树与二叉树 本讲主要内容 一、数据结构一、数据结构一、数据结构 存储器分内存储器和外存储器，数据结构研究具有逻辑结构关系的数据在计算机内存储器的存储方法和在外存储器中以文件形式的组织和存储方式n 数据结构：数据的组织形式和存储方式一、数据结构 存储器分内存储器和外存储器，数据生活中的数据结构生活中的数据结构9季度名称组成的集合 春，夏，秋，冬春，夏，秋，冬 是数据结构：9家庭成员祖父、父亲、儿子是数据结构数据元素之间有位置上的前后关系数据元素之间有位置上的前后关系 数据元素之间有层次上的高低关系数据元素之间有层次上的高低关系 生活中的数据结构季度名称组成的集合春，夏，秋，冬家庭成员学号姓名性别出生日期班级专业20040001刘强男1984/02/1314001机械制造20040002王晓女1986/05/0614001机械制造20040003李明男1984/10/2514001机械制造20040041张宇男1984/06/1414002机械电子工程9学号和姓名等组成的学籍表是数据结构学号姓名性别出生日期班级专业20040001刘强男1984/n数据结构数据结构：指互相之间存在着一种或多种关系的数据元素：指互相之间存在着一种或多种关系的数据元素 的集合。的集合。主要研究：数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；在处理数据时，各数据元素在计算机中的存储关系，即数据的物理结构（存储结构）；对数据进行的操作（运算），包括插入、删除、查找、排序等。n数据结构包括数据的数据结构包括数据的逻辑结构和物理结构逻辑结构和物理结构（或存储结构）（或存储结构）定义：定义：数据结构：指互相之间存在着一种或多种关系的数据元素 数据的逻辑结构数据的逻辑结构 只抽象地反映数据元素的结构，而不管其存储方只抽象地反映数据元素的结构，而不管其存储方式的数据结构。式的数据结构。数据之间的数据之间的4 4 种基本逻辑结构：种基本逻辑结构：集合集合、线性线性、树形树形、图状图状 集合结构集合结构:结构中的数据元素之间除了同属结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。于一个集合的关系外，无任何其它关系。集合集合 数据的逻辑结构 只抽象地反映数据元素的结构，线性结构线性结构：结构中的数据元素之间存在着结构中的数据元素之间存在着一对一的线性关系。一对一的线性关系。线性线性例如:春夏冬秋 线性结构：结构中的数据元素之间存在着线性例如:春夏冬秋 树形结构树形结构：结构中的数据元素之间存在着一结构中的数据元素之间存在着一对多的对多的层次层次关系。关系。树树图图 图状（网状）结构图状（网状）结构：结构中的数据元素之结构中的数据元素之间存在着多对多的任意关系。间存在着多对多的任意关系。树形结构：结构中的数据元素之间存在着一对多的层次关系。树图 由于集合关系松散，因此可用其他结构由于集合关系松散，因此可用其他结构代替，故数据的逻辑结构可概括为：代替，故数据的逻辑结构可概括为：线性结构 非线性结构有且只有一个开始结点和一个终端结点，并且每个结点最多只有一个前驱和一个后继，线性结构也称为线性表。栈、队列、数组和串等是特殊线性表非线性结构包括树和图 由于集合关系松散，因此可用其他结构代替，故数据的逻辑三、线性表三、线性表三、线性表向量2，43，68，45，32是线性表。季度名称 春，夏，秋，冬是线性表。英文字母表 A，B，Z是线性表。学生基本信息:(20040001,(20040001,刘强刘强,男男,1984/02/13,14001,1984/02/13,14001,机械制造机械制造),),(20040002,(20040002,王晓红王晓红,女女,1986/05/06,14001,1986/05/06,14001,机械制造机械制造),),(20040003,(20040003,李明李明,男男,1984/10/25,14001,1984/10/25,14001,机械制造机械制造)是线性表。向量2，43，68，45，32是线性表。季度名称 线性表是由n（n=0）个数据元素组成的一个有限序列，表中的每一个数据元素，除了第一个元素无直接前驱，最后一个元素无直接后继，其它元素有且只有一个直接前驱和直接后继。即可表示为：（a1,a2,ai,an），其中ai是性质相同的数据元素，也称为线性表中的一个结点。线性表线性表 线性表是由n（n=0）个数据元素组成的一个举例：用桶堆积物品，先放进来的压在底下，举例：用桶堆积物品，先放进来的压在底下，随后一件一件往上放。取走时，只能从上面一随后一件一件往上放。取走时，只能从上面一件一件取。放和取都在顶部进行，底部一般是件一件取。放和取都在顶部进行，底部一般是不动的。不动的。四、栈四、栈 举例：手枪子弹夹中的子弹，子弹的装入与举例：手枪子弹夹中的子弹，子弹的装入与子弹弹出膛均在弹夹的最上端进行，先装入子弹弹出膛均在弹夹的最上端进行，先装入的子弹后发出，后装入的子弹先发出。的子弹后发出，后装入的子弹先发出。举例：用桶堆积物品，先放进来的压在底下，随后一件一件往上放。栈是限定只能在表的一一端端进行插入和删除的线性表。它按照“后后进进先先出出”（LIFO）的原则组织数据。表中允许插入和删除的一端叫做栈栈顶顶，表中的固定端叫做栈底栈底。栈是限定只能在表的一端进行插入和删除的线性五、队列五、队列 五、队列 队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。它按照“先先进进先先出出”（FIFO）的原则组织数据。表中允许插入的一端叫做队尾，允许删除的一端叫做队头。a2a1a3 an出队列出队列入队列入队列头头尾尾队列示意图队列示意图 队列是限定只能在表的一端进行插入，在表a2a1六、树六、树与二叉树与二叉树n因为现实世界中存在着“树”这种结构 族谱族谱、等级制度等级制度、目录分类目录分类等。n特别是在大量数据处理（如文件系统、编译系统、目录组织等）方面，树型结构的应用非常广泛。n而为了研究这类问题，必须能够将树储存，而如何储存将取决于所需要的操作。树树六、树与二叉树因为现实世界中存在着“树”这种结构 族谱、n 树形结构是一种简单的非线性结构。树是由n(n0)个结点组成的有限集合。当n=0时，称为空树；否则，有且仅有一个根结点，当n1时，其余结点被分成m(m0)个互不相交的子集T1，T2,.,Tm，每个子集又是一棵树。树树1、树的基本术语、树的基本术语 每个结点只有一个前驱，称为父结点；只有一个没有前驱的结点，称为根结点；树形结构是一种简单的非线性结构。树是由n(n0)个每个结点可以有多个后继，称为该结点的子结点；没有后继的结点称为叶子结点；AEBCDFGHIJKL根子结点叶子结点每个结点可以有多个后继，称为该结点的子结点；AEBCDFG一个结点所拥有的后继个数称为该结点的度；树中所有结点的度的最大值度的最大值称为树的度；AEBCDFGHIJKL一个结点所拥有的后继个数称为该结点的度；AEBCDFGHI树中结点的最大层次称为树的深度。AEBCDFGHIJKL 结点的层次从根结点算起，根结点的层次为1，根的直接后继结点的层次为2，依次类推。1 1 2 2 3 3 4 4树中结点的最大层次称为树的深度。AEBCDFGHIJK 二叉树二叉树 n对树应该讨论它的实现与操作，由于树结构的不确定性，每个结点的度可以不同，处理时相对比较麻烦。讨论另外一种树二叉树相对来说简单一些。n树型结构通常转换成二叉树来讨论，因为二叉树适合计算机处理。下面讨论二叉树的概念及遍历。二叉树 对树应该讨论它的实现与操作，由于树 满足以下两个条件的树型结构叫做二叉树：n每个结点的度都不大于2，即每个结点最多有两棵子树（度只能是0、1、2）。n每个结点的孩子结点次序不能颠倒，即严格区分是左子树还是右子树。ABCDEFGHABCDEF 满足以下两个条件的树型结构叫做二叉树：ABCDEFGH非空二叉树有且只有一个根结点；每个结点最多有两棵子树,且有左右之分特点：A AT TX XC CZ ZY YB BP P深度为4的二叉树非空二叉树有且只有一个根结点；特点：ATXCZYBP深度为41 1、五种基本形态五种基本形态 空二叉树只有根结点只有左子树有左和右子树只有右子树1、五种基本形态 空二叉树只有根结点只有左子树有左和右子树2、二叉树的基本性质、二叉树的基本性质在二叉树的第i层上，最多有2i-1（i=1）个结点。深度为k的二叉树中结点总数结点总数最多为2k-1。2、二叉树的基本性质在二叉树的第i层上，最多有2i-1（i3、满二叉树 深度为k的二叉树有2k-1个结点（即性质2中允许的最大值）。3、满二叉树 深度为k的二叉树有2k-1个结点（4、完全二叉树 除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。4、完全二叉树 除最后一层n 为什么需要遍历二叉树？为什么需要遍历二叉树？5、二叉树的遍历二叉树的遍历 二叉树是非线性数据结构，通过遍历可以将二叉树中的结点访问一次且仅一次访问一次且仅一次，从而得到访问结点的顺序序列。从这个意义上说，遍历操作就是将二叉树中结点按一定规律线性化的操作，目的目的在于将非线性化结构变成线性化的访问序列。为什么需要遍历二叉树？5、二叉树的遍历 n遍历二叉树：按照遍历二叉树：按照某种顺序某种顺序访问二叉树中访问二叉树中每个结点的过程，每个结点被访问一次且每个结点的过程，每个结点被访问一次且仅一次仅一次。n根据对根访问的次序，二叉树的遍历分为根据对根访问的次序，二叉树的遍历分为先序遍历先序遍历(DLR)、中序遍历中序遍历（LDR）和和后后序遍历序遍历（LRD）。遍历二叉树：按照某种顺序访问二叉树中每个结点的过程，每个结点先序遍历先序遍历(DLR)访问根结点 先序遍历左子树 先序遍历右子树A AT TX XC CZ ZY YB BP P深度为4的二叉树A A遍历结果：T TB BZ ZX XC CP PY Y因为左子树因为左子树空，故遍历空，故遍历右子树右子树先序遍历(DLR)访问根结点ATXCZYBP深度为4中序中序遍历遍历（LDR）中序遍历左子树 访问根结点 中序遍历右子树A AT TX XC CZ ZY YB BP P深度为4的二叉树A AT TZ ZB BC CX XY YP P因为左子树空因为左子树空遍历结果：中序遍历（LDR）中序遍历左子树ATXCZYBP深度为4 后序遍历左子树 后序遍历右子树 访问根结点后序后序遍历遍历（LRD）A AT TX XC CZ ZY YB BP P深度为4的二叉树遍历结果：A AT TX XC CZ ZY YB BP P深度为4的二叉树A AT TZ ZB BC CX XY YP P因为左子树因为左子树空，故遍历空，故遍历右子树右子树 后序遍历左子树后序遍历（LRD）ATXCZYBP深度为按先序遍历序列按先序遍历序列(DLR)ABDECFGH 按中序遍历序列按中序遍历序列(LDR)DEBFCGAHAHEFGDCB按后序遍历序列按后序遍历序列(LRD)EDFGCBHA 按先序遍历序列(DLR)ABDECFGH 按中序遍历序列思考思考1：给定结点的中序序列和后序序：给定结点的中序序列和后序序列是否可以唯一确定一棵二叉树？列是否可以唯一确定一棵二叉树？思考思考2：给定结点的前序序列和后序序：给定结点的前序序列和后序序列是否可以唯一确定一棵二叉树？列是否可以唯一确定一棵二叉树？思考1：给定结点的中序序列和后序序列是否可以唯一确定一棵二叉1 1、下列选项中不属于算法特征的是（、下列选项中不属于算法特征的是（D D）。）。A A）有穷性和确定性）有穷性和确定性 B B）有效性）有效性 C C）至少一个输出）至少一个输出 D D）集合性）集合性2 2、栈和队列的共同特点是（、栈和队列的共同特点是（C C）A A）都是先进先出）都是先进先出B B）都是先进后出）都是先进后出C C）只允许在端点处插入和删除元素）只允许在端点处插入和删除元素D D）没有共）没有共同点同点课堂练习：课堂练习：1、下列选项中不属于算法特征的是（D）。课堂练习：3、下列关于队列的说法正确的是（、下列关于队列的说法正确的是（C）。）。A）在队列中只能插入数）在队列中只能插入数B）在队列中只能删除数）在队列中只能删除数据据 C）队列是先进先出的线性表）队列是先进先出的线性表 D）队列是先进后出的）队列是先进后出的线性表线性表4、在计算机中，算法是指（、在计算机中，算法是指（B）。）。）加工方法）加工方法 ）解决给定问题的一种方法）解决给定问题的一种方法 ）排序方法）排序方法 ）查询方法）查询方法3、下列关于队列的说法正确的是（C）。5、以下不属于数据的四类基本逻辑结构的是（、以下不属于数据的四类基本逻辑结构的是（B）。）。A）集合结构）集合结构 B）圆形结构）圆形结构 C）树形结构）树形结构 D）线）线性结构性结构6、数据结构包括数据的【、数据结构包括数据的【逻辑逻辑】结构和物理结构。】结构和物理结构。7、算法的复杂度主要包括【、算法的复杂度主要包括【时间时间】复杂度和空间复】复杂度和空间复杂度。杂度。5、以下不属于数据的四类基本逻辑结构的是（B）。总结总结n一、算法一、算法n二、数据结构二、数据结构n三、线性表三、线性表n四、栈四、栈n五、队列五、队列n六、树与二叉树六、树与二叉树总结一、算法n下次课内容：下次课内容：11.1 Word 2003 11.1 Word 2003文字处理软件（文字处理软件（2 2）n文档排版 字符格式化、段落格式化、页面格式化n文档打印n作业：作业：课后习题全部课后习题全部 预习第十一章的预习第十一章的wordword（2 2）部分）部分下次课内容：下课了。下课了。追求追求休息一会儿。休息一会儿。下课了。追求休息一会儿。