信息学奥赛-数据结构课件

信息学奥赛-数据结构课件数据结构数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通俗解释：数据相当于书通俗解释：数据相当于书.计算机相当于书架，存放了很多书，书架分为计算机相当于书架，存放了很多书，书架分为很多格子，书存放在不同格子（内存空间，对应一个地址），中。很多格子，书存放在不同格子（内存空间，对应一个地址），中。为了更快的取到想要的书为了更快的取到想要的书,要用特定的存放方式要用特定的存放方式数据结构数据结构数据结构数据结构是计算机存储、组织数据的方式。线性表性表线性表：性表：n个数据元素的有序集合，个数据元素的有序集合，“连成成线的的”是一种是一种常用的数据常用的数据结构。其中数据元素之构。其中数据元素之间的关系通常是一的关系通常是一对一一的关系，即除了第一个和最后一个数据元素之外，其它数的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的据元素都是首尾相接的实际应用中常见的特殊线性表：栈、队列、字符串、一维数组线性表线性表：n个数据元素的有序集合，“连成线的”是一种常用非非线性表性表非非线性表：各个数据元素不再保持在一个性表：各个数据元素不再保持在一个线性序列中，每性序列中，每个数据元素可能与零个或者多个其他数据元素个数据元素可能与零个或者多个其他数据元素发生生联系系主要代表：树、图结构、多维数组非线性表链表表链是一种存储单元上非连续、非顺序的存储结构，通过链链是一种存储单元上非连续、非顺序的存储结构，通过链表中的指针依次访问数据。表中的指针依次访问数据。链表由一系列结点（链表中每一个元素称为结点）组成，链表由一系列结点（链表中每一个元素称为结点）组成，数据元素可根据需要实时添加、动态生成。数据元素可根据需要实时添加、动态生成。由于非连续，链表无法随机读取，需要通过指针依次访问，查找数据时间长。链表链是一种存储单元上非连续、非顺序的存储结构，通过链表中的栈栈是栈是只能在某一端插入和删只能在某一端插入和删除除的数据结构。的数据结构。（想象用桶堆积物品，先堆进来的压在底下，随后一件件往上堆。取走时，只能从上面一件件取。堆和取都在顶部进行，底部一般是不动的。）栈进行删除和插入的一端称栈顶栈顶，另一堆称栈底栈底。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈的特征是“后进先出后进先出”栈栈是只能在某一端插入和删除的数据结构。栈一个栈可以用定长为的数组来表示用一个栈指针TOP指向栈顶。若TOP0，表示栈空，TOP=N时栈满。进栈时TOP加。退栈时TOP减。当TOP0）个元素组成的有限集合，其中：（1）每个元素称为结点结点 （2）有且仅有一个特定的结点，称为根结点或树根根结点或树根 （3）除根结点外，其余结点能分成m（m=0）个互不相交的有限集合 T0,T1,T2,Tm-1。其中的每个子集又都是一棵树，这些集合称为这棵树的子树。2的子的子节点节点5，6的父的父节点节点根节点根节点2的兄弟的兄弟树一棵树是由n（n0）个元素组成的有限集合，其中：2的子节树一个结点的子树个数，称为这个结点的一个结点的子树个数，称为这个结点的度度如：结点1的度为3，结点3的度为0度为度为0的结点称为的结点称为叶结点叶结点如：结点3、5、6、8、9度不为度不为0的结点称为的结点称为分支结点分支结点如：结点1、2、4、7根以外的分支结点又称为根以外的分支结点又称为内部结点内部结点如：结点2、4、7树中各结点的度的最大值称为树中各结点的度的最大值称为这棵树的度这棵树的度右侧这颗树度为33）。树树树节点的树节点的层次层次从根开始定义，根从根开始定义，根结点的层次为结点的层次为1 其它结点的层次等于它的父结其它结点的层次等于它的父结点层次加点层次加1 1 如：根节点层次为1，结点2、3、4的层次为2，结点5、6、7的层次为3，结点8、9的层次为4。一棵树中所有的结点的层次的最一棵树中所有的结点的层次的最大值称为树的深度（或高度大值称为树的深度（或高度）如：这棵树的深度为4。树树节点的层次从根开始定义，根结点的层次为1二叉二叉树 二叉树是一种特殊的树型结构，它是最大度数为最大度数为2 2的树。它的两棵子树分别称为左子树、右子树。二叉树的每个结点最多有两个子结点。每个结点的子结点分别称为左孩子、右孩子，。二叉树有5中基本形态：二叉树 二叉树是一种特殊的树型结构，它二叉二叉树的性的性质【性质1】在二叉树的第i层上最多有2i1个结点（i=1）。【性质2】深度（高度）为k的二叉树至多有2k-1个结点（k=1）。二叉树的性质【性质1】在二叉树的第i层上最多有2i1个结点二叉二叉树的性的性质【性质3】N=n0+n1+n2 【性质4】n0=n2+1 设二叉树中度为0,1,2的结点分别有no,n1,n2个,总结点数为N.二叉树的性质【性质3】N=n0+n1+n2 设二叉树树的遍的遍历 在应用树结构解决问题时，往往要求按照某种次在应用树结构解决问题时，往往要求按照某种次序获得树中全部结点的信息，这种操作叫作树的序获得树中全部结点的信息，这种操作叫作树的遍历。遍历的方法有多种，遍历。遍历的方法有多种，以以二叉树为例二叉树为例树的遍历 在应用树结构解决问题时，往往要求按照某种次序获得树树的遍历 先序遍先序遍历先序（根）遍历：(1)先访问根结点 先序遍历左子树先序遍历右子树如右图先序遍历的结果为：a b d e h i c f g 树的遍历 先序（根）遍历：树的遍历 中序遍中序遍历中序（根）遍历：中序遍历左子树访问处理根结点中序遍历右子树如右图中序遍历的结果为：d b h e i a f c g 树的遍历 中序（根）遍历：树的遍历 后序遍后序遍历后序（根）遍历：后序遍历左子树后序遍历右子树访问处理根结点如上图后序遍历的结果为：d h i e b f g c a 树的遍历 后序（根）遍历：树的遍历 层次遍次遍历层次遍历：按层次从小到大逐个访问，同一层次按照从左到右的次序。如右图层次遍历的结果为：h I d e f g b c a树的遍历 层次遍历：练习1、二叉树T，已知其前序遍历序列为1243576，中序遍历序列为4215736，则其后序遍历序列为（B）。A.4 2 5 7 6 3 1 B.4 2 7 5 6 3 1C.4 2 7 5 3 6 1 D.4 7 2 3 5 6 122练习1、二叉树T，已知其前序遍历序列为1 2 4 322图通俗说，各顶点用边连起来就叫做图通俗说，各顶点用边连起来就叫做图图和树的区别？图和树的区别？（1）树形结构中，每一个数据有可能有多个下层结点（孩子结点），但却只与一个上层结点相关。（2）图形结构中，结点之间的关系可以是任意的，图中任意两个数据之间都可能相关。图通俗说，各顶点用边连起来就叫做图图和树的区别？图 1 2 3 4 5 (a)1 2 3 4 5 (b)(a)(a)有向图：有向图：图的边有方向，只能按箭头方向从一点到另一点。(a)就是一个有向图。(b)(b)无向图：无向图：图的边没有方向，可以双向。(b)就是一个无向图。图 1 2 3 4 5 (a)1 2结点的度：结点的度：无向图中与结点相连的边的数目，称为结点的度。有向图中结点的度等于该结点的入度和出度之和结点的入度：结点的入度：在有向图中，以这个结点为终点的有向边的数目。结点的出度：结点的出度：在有向图中，以这个结点为起点的有向边的数目。1 2 3 4 5 (a)1 2 3 4 5 (b)结点的度：1 2 3 4 5 (a)1图的遍的遍历（1）深度优先遍历）深度优先遍历 从图中某个顶点v0出发，然后搜索V0的一个邻接点Vi,若Vi未被访问，则访问之.再搜索Vi的一个邻接点按此方式访问。若某顶点的邻接点全部访问完毕，则回到它的上一顶点，然后再从此顶点又按深度优先的方法搜索下去，直到访问完毕为止深度优先遍历得到的序列为：深度优先遍历得到的序列为：0-1-3-7-4-2-5-6图的遍历（1）深度优先遍历 深度优先遍历得到的序列为：图的遍的遍历（2）广度优先遍历）广度优先遍历类似树的按层次遍历，从图的某个顶点v0出发，访问了v0之后，依次访问与v0相邻的未被访问的顶点，直至所有的顶点都被访问完。广度优先遍历得到的序列为：广度优先遍历得到的序列为：0-1-2-3-4-5-6-7图的遍历（2）广度优先遍历广度优先遍历得到的序列为：图-最短路径算法最短路径算法如何求图中V0到V5的最短路径？权值：边的“费用”，可以形象地理解为边的长度。图-最短路径算法如何求图中V0到V5的最短路径？权值：边的图-最短路径算法最短路径算法http:/