信息学奥赛数据结构

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