信息学奥赛-数据结构.ppt

1、数据结构,数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系 的数据元素的集合。通俗解释：数据相当于书. 计算机相当于书架，存放了很多书，书架分为 很多格子，书存放在不同格子（内存空间，对应一个地址），中。 为了更快的取到想要的书,要用特定的存放方式数据结构,线性表,线性表：n个数据元素的有序集合，“连成线的”是一种常用的数据结构。其中数据元素之间的关系通常是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的实际应用中常见的特殊线性表：栈、队列、字符串、一维数组,非线性表,非线性表：各个数据元素不再保持在一个线性序列中，每个数据元素可能与

2、零个或者多个其他数据元素发生联系主要代表：树、图结构、多维数组,链表,链是一种存储单元上非连续、非顺序的存储结构，通过链表中的指针依次访问数据。 链表由一系列结点（链表中每一个元素称为结点）组成，数据元素可根据需要实时添加、动态生成。由于非连续，链表无法随机读取，需要通过指针依次访问，查找数据时间长。,栈,栈是只能在某一端插入和删除的数据结构。（想象用桶堆积物品，先堆进来的压在底下，随后一件件往上堆。取走时，只能从上面一件件取。堆和取都在顶部进行，底部一般是不动的。）栈进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（PUSH），删除则称为退栈（POP）。 栈的特征是“后进先出”,栈

3、,一个栈可以用定长为的数组来表示用一个栈指针TOP指向栈顶。若TOP0，表示栈空，TOP=N时栈满。进栈时TOP加。退栈时TOP减。当TOP0时为下溢。,练习某个车站呈狭长形，宽度只能容下一辆车，并且只有一个出入口。已知某时刻该车站状态为空，从 这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的 顺序为 1，2，3，4，5，6，7 ，则车辆出站的顺序为（ C ）。A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 4, 3, 7, 6 D. 1, 4, 3, 7, 2,队列,跟栈相反，队列是限定只能在表的一端进行插入，在表的

4、另一端进行删除的数据结构。队列的特征是“先进先出” （就像排队买东西，排在前面的人买完东西后离开队伍（删除），而后来的人总是排在队伍未尾（插入）通常把队列的删除和插入分别称为出队和入队。 允许删除的一端队头(front) 允许插入的一端队尾(rear),队列,队列可以用数组Qm+1来存储，数组的上界即是队列所容许的最大容量。在队列的运算中需设两个指针：head：队头指针，指向实际队头元素的前一个位置tail：队尾指针，指向实际队尾元素所在的位置,树,一棵树是由n（n0）个元素组成的有限集合，其中：（1）每个元素称为结点（2）有且仅有一个特定的结点，称为根结点或树根（3）除根结点外，其余结点能分

5、成m（m=0）个互不相交的有限集合 T0,T1,T2,Tm-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的层次

6、为3，结点8、9的层次为4。 一棵树中所有的结点的层次的最大值称为树的深度（或高度）如：这棵树的深度为4。,二叉树,二叉树是一种特殊的树型结构，它是最大度数为2的树。 它的两棵子树分别称为左子树、右子树 。二叉树的每个结点最多有两个子结点。每个结点的子结点分别称为左孩子、右孩子，。二叉树有5中基本形态：,二叉树的性质,【性质1】在二叉树的第i层上最多有2i1个结点（i=1）。 【性质2】深度（高度）为k的二叉树至多有2k-1个结点（k=1）。,二叉树的性质,【性质3】N=n0+n1+n2 【性质4】n0=n2+1,设二叉树中度为0,1,2的结点分别有no,n1,n2个,总结点数为N.,树的遍历

7、,在应用树结构解决问题时，往往要求按照某种次序获得树中全部结点的信息，这种操作叫作树的遍历。遍历的方法有多种，以二叉树为例,树的遍历,先序遍历,先序（根）遍历：(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,树的遍历,层次遍历,层次遍历：按层次从小到大逐个访问，

8、同一层次按照从左到右的次序。如右图层次遍历的结果为：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）图形结构中，结点之间的关系可以是任意的，图中任意两个数据之间都可能相关。,图,

9、(a)有向图：图的边有方向，只能按箭头方向从一点到另一点。(a)就是一个有向图。(b)无向图：图的边没有方向，可以双向。(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的最短路径？,权值：边的“费用”，可以形象地理解为边的长度。,图-最短路径算法,http:/