第十章-数据结构与算法概要

1、2021/3/131 2021/3/132o10.1 算法算法 o10.2 数据结构的基本概数据结构的基本概念念 o10.3 线性表及其顺序存储结线性表及其顺序存储结构构 o10.4 栈和队列栈和队列 o10.5 树与二叉树树与二叉树 2021/3/13310.1 算法算法 o10.1.1 算法的基本概念算法的基本概念 o10.1.2 算法复杂度算法复杂度 2021/3/13410.1.1 算法的基本概念算法的基本概念 2021/3/1351. 算法的基本特征算法的基本特征2021/3/1362021/3/1372021/3/1382021/3/1392021/3/13102. 算法的基本要素

2、算法的基本要素2021/3/13112021/3/1312 2021/3/13132021/3/13142021/3/13152021/3/13162021/3/13172021/3/131810.1.2 算法复杂度算法复杂度 2021/3/13191. 算法的时间复杂度算法的时间复杂度 2021/3/1320 2021/3/13212. 算法的空间复杂度算法的空间复杂度2021/3/132210.2 数据结构的基本概念数据结构的基本概念 2021/3/132310.2 数据结构的基本概念数据结构的基本概念o10.2.1 什么是数据结构什么是数据结构o10.2.2 线性结构与非线性结构线性结构

3、与非线性结构 2021/3/132410.2.1 什么是数据结构什么是数据结构 。2021/3/13252021/3/13262021/3/13271. 数据的逻辑结构数据的逻辑结构2021/3/13282021/3/13292. 数据的存储结构数据的存储结构2021/3/13303.数据结构的图形表示数据结构的图形表示2021/3/1331秋秋2021/3/133210.2.2 线性结构与非线性结构线性结构与非线性结构 2021/3/133310.3 线性表及其顺序存储结构线性表及其顺序存储结构 o10.3.1 线性表的基本概念线性表的基本概念 o10.3.2 线性表的顺序存储结构线性表的顺

4、序存储结构2021/3/133410.3.1 线性表的基本概念线性表的基本概念 2021/3/1335表10.1 学生情况登记表2021/3/13362021/3/133710.3.2 线性表的顺序存储结构线性表的顺序存储结构 2021/3/133810.4 栈和队列栈和队列 o10.4.1 栈及其基本运算栈及其基本运算o10.4.2 队列及其基本运算队列及其基本运算 2021/3/133910.4.1 栈及其基本运算栈及其基本运算2021/3/13401. 什么是栈什么是栈2021/3/13412. 栈的运算栈的运算2021/3/13422021/3/134310.4.2 队列及其基本运算队

5、列及其基本运算 2021/3/13442021/3/134510.5 树与二叉树树与二叉树 o10.5.1 树及其基本性质树及其基本性质o10.5.2 二叉树及其基本性质二叉树及其基本性质o10.5.3 二叉树的遍历二叉树的遍历 2021/3/134610.5.1 树及其基本性质树及其基本性质1.什么是树什么是树 树（树（tree）是指所有数据元素之间的关系）是指所有数据元素之间的关系具有明显层次特性的一种简单的非线性数据具有明显层次特性的一种简单的非线性数据结构。在用图形表示树这种数据结构时结构。在用图形表示树这种数据结构时,很很像自然界中的树像自然界中的树,只不过是一棵倒长的树只不过是一棵

6、倒长的树,因因此此,这种数据结构就用这种数据结构就用“树树”来命名。如图来命名。如图10.2所示。所示。2021/3/13472021/3/13482.树的基本性质树的基本性质o树具有明显的层次关系树具有明显的层次关系,在所有的层次关系中在所有的层次关系中,人们最熟人们最熟悉的是血缘关系悉的是血缘关系,按血缘关系可以很直观地理解树结构按血缘关系可以很直观地理解树结构中各数据元素结点之间的关系中各数据元素结点之间的关系,因此因此,在描述树结构时在描述树结构时,也经常使用血缘关系中的一些述语。也经常使用血缘关系中的一些述语。o（1）在树结构中）在树结构中,每一个结点只有一个前件每一个结点只有一个前

7、件,称为父结称为父结点。在树中点。在树中,没有前件的结点只有一个没有前件的结点只有一个,称为树的根结点称为树的根结点,简称为树的根。如在图简称为树的根。如在图10.2中中,结点结点R是树的根结点。是树的根结点。o（2）在树结构中）在树结构中,每一个结点可以有多个后件每一个结点可以有多个后件,它们都它们都称为该结点的子结点。没有后件的结点称为叶子结点。称为该结点的子结点。没有后件的结点称为叶子结点。如在图如在图10.2中中,结点结点C、M、F、E、X、G、S、L、Z、A均为叶子结点。均为叶子结点。2021/3/1349o（3）在树结构中,一个结点所拥有的后件个数称为该结点的度。如在图10.2中,

8、根结点R的度为4;结点T的度为3;结点K、B、N、H的度为2;结点P、Q、D、O、Y、W的度为1。叶子结点的度为0。在树中,所有结点中的最大度称为树的度。如图10.2所示的树的度为4。o在树结构中,一般按如下原则分层:o根结点在第l层;同一层上所有结点的所有子结点在下一层。如在图10.2中:根结点R在第1层;结点K、P、Q、D在第2层;结点B、E、N、O、T在第3层;结点C、H、X、Y、S、W、Z、A在第4层;结点M、F、G、L在第5层。树的最大层次称为树的深度。如图10.2所示的树的深度为5。2021/3/1350o在树中,以某结点的一个子结点为根构成的树称为该结点的一棵子树。如在图10.2

9、中,结点R有4棵子树,它们分别以K、P、Q、D为根结点;结点P有1棵子树,其根结点为N;结点T有3棵子树,它们分别以W、Z、A为根结点。在树中,叶子结点没有子树。2021/3/135110.5.2 二叉树及其基本性质二叉树及其基本性质 1. 二叉树二叉树o二叉树（binary tree）是一种很有用的非线性结构。它与树结构很相似,并且,树结构的所有术语都可以用到二叉树这种数据结构上。o二叉树具有以下两个特点:一是非空二叉树只有一个根结点; 二是每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树,其次序不能任意颠倒。2021/3/1352o由以上特点可以看出,在二叉树中,每一个结点的度最

10、大为2,即所有子树（左子树或右子树）也均为二叉树。另外,二叉树中的每一个结点的子树被明显地分为左子树与右子树。在二叉树中,一个结点可以只有左子树而没有右子树,也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时,该结点即是叶子结点。o一棵深度为4的二叉树。如图10.3所示。 2021/3/13532021/3/13542. 二叉树的基本性质二叉树的基本性质o二叉树具有以下几个性质。o性质1 在二叉树的第K层上,最多有2k-1 （k1）个结点。o根据二叉树的特点,这个性质是显然的。 o性质2 深度为m的二叉树最多有-1个结点。o深度为m的二叉树是指二叉树共有m层。o根据性质1,只要

11、将第1层到第m层上的最大的结点数相加,就可以得到整个二叉树中结点数的最大值,即2021/3/1355o性质3 在任意一棵二叉树中,度为0的结点（即叶子结点）总是比度为2的结点多一个。 o如在图10.3所示的二叉树中,有3个叶子结点,有2个度为2的结点,度为0的结点比度为2的结点多一个。o性质4具有n个结点的二叉树,其深度至少为 +1,其中 表示取的整数部分。 o这个性质可以由性质2直接得到。2021/3/13563. 满二叉树与完全二叉树满二叉树与完全二叉树o满二叉树与完全二叉树是两种特殊形态的二叉树。o 满二叉树o满二叉树是指除最后一层外,每一层上的所有结点都有两个子结点。这就是说,在满二叉

12、树中,每一层上的结点数都达到最大值,即在满二叉树的第k层上有-1个结点,且深度为m的满二叉树有-1个结点。o深度为2、3、4的满二叉树。如图10.4（a）、10.4（b）、10.4（c）所示。2021/3/1357（a）深度为2的满二叉树 （b）深度为3的满二叉树 （c）深度为4的满二叉树2021/3/1358o 完全二叉树 o完全二叉树是指除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。o更确切地说,如果从根结点起,对二叉树的结点自上而下、自左至右用自然数进行连续编号,则深度为m,且有n个结点的二叉树,当且仅当其每一个结点都与深度为m的满二叉树中编号从1到n的结

13、点一一对应时,称之为完全二叉树。o深度为4的完全二叉树。如图10.5所示。2021/3/13592021/3/1360o对于完全二叉树来说,叶子结点只可能在层次最大的两层上出现;对于任何一个结点,若其右分支下的子孙结点的最大层次为p,则其左分支下的子孙结点的最大层次为p,或为p+l。o由满二叉树与完全二叉树的特点可以看出,满二叉树也是完全二叉树,而完全二叉树一般不是满二叉树。 o完全二叉树还具有以下两个性质:o性质5 具有n个结点的完全二叉树的深度为 n2log2021/3/1361o性质6 设完全二叉树共有n个结点。如果从根结点开始,按层序（每一层从左到右）用自然数1,2,n给结点进行编号,

14、则对于编号为k（k=1,2,n）的结点有以下结论:o若k1,则该结点为根结点,它没有父结点;若kl,则该结点的父结点编号为INT（k2）。o若2kn,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点（显然也没有右子结点）。o若2k+1n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点。o根据完全二叉树的这个性质,如果按从上到下、从左到右顺序存储完全二叉树的各结点,则很容易确定每一个结点的父结点、左子结点和右子结点的位置。 2021/3/136210.5.3 二叉树的遍历二叉树的遍历 o二叉树的遍历是指不重复地访问二叉树中的所有结点。 由于二叉树是一种非线性结构,因此,

15、对二叉树的遍历要比遍历线性表复杂得多。在遍历二叉树的过程中,当访问到某个结点时,再往下访问可能有两个分支,对于二叉树来说,需要访问根结点、左子树上的所有结点、右子树上的所有结点,在这三者中,究竟先访问哪一个?也就是说,遍历二叉树的方法实际上是要确定访问各结点的顺序,以便不重不漏地访问到二叉树中的所有结点。o在遍历二叉树的过程中,一般先遍历左子树,然后再遍历右子树。在先左后右的原则下,根据访问根结点的次序,二叉树的遍历可以分为三种:前序遍历、中序遍历、后序遍历。下面分别介绍这三种遍历的方法。 2021/3/13631. 前序遍历前序遍历o前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中,

16、首先访问根结点,然后遍历左子树,最后遍历右子树;并且,在遍历左右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树。因此,前序遍历二叉树的过程是一个递归的过程。下面是二叉树前序遍历的简单描述:o若二叉树为空,则结束返回;否则o 访问根结点。o 前序遍历左子树。o 前序遍历右子树。o在此特别要注意的是,在遍历左右子树时仍然采用前序遍历的方法。如果对图10.3中的二叉树进行前序遍历,则遍历的结果为A,T,B,Z,X,C,Y,P（称该二叉树的前序序列）。2021/3/13642.中序遍历中序遍历o中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中,首先遍历左子树,然后访问根结点,最后遍历右子树;并且,在遍历左右子树时,仍然先遍历左子树,然后访问根结点,最后遍历右子树。下面是二叉树中序遍历的简单描述:o若二叉树为空,则结束返回;否则o 中序遍历左子树;o 访问根结点;o 中序遍历右子树。 o在此也要特别注意的是,在遍历左右子树时仍然采用中序遍历的方法。如果对图10.3中的二叉树进行中序遍历,则遍历结果为T,Z,B,A,C,Y,X,P（称该二叉树的序列）。2021/3/13653. 后序遍历后序遍历o