信息学奥赛-数据结构

数据结构数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通俗解释：数据相当于书.计算机相当于书架，存放了很多书，书架分为很多格子，书存放在不同格子（内存空间，对应一个地址），中。为了更快的取到想要的书,要用特定的存放方式—数据结构线性表线性表：n个数据元素的有序集合，“连成线的”是一种常用的数据结构。其中数据元素之间的关系通常是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的实际应用中常见的特殊线性表：栈、队列、字符串、一维数组非线性表非线性表：各个数据元素不再保持在一个线性序列中，每个数据元素可能与零个或者多个其他数据元素发生联系主要代表：树、图结构、多维数组链表链是一种存储单元上非连续、非顺序的存储结构，通过链表中的指针依次访问数据。链表由一系列结点（链表中每一个元素称为结点）组成，数据元素可根据需要实时添加、动态生成。由于非连续，链表无法随机读取，需要通过指针依次访问，查找数据时间长。栈栈是只能在某一端插入和删除的数据结构。（想象用桶堆积物品，先堆进来的压在底下，随后一件件往上堆。取走时，只能从上面一件件取。堆和取都在顶部进行，底部一般是不动的。）栈进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈的特征是“后进先出”栈一个栈可以用定长为Ｎ的数组Ｓ来表示用一个栈指针TOP指向栈顶。若TOP＝0，表示栈空，TOP=N时栈满。进栈时TOP加１。退栈时TOP减１。当TOP0时为下溢。练习某个车站呈狭长形，宽度只能容下一辆车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的顺序为1，2，3，4，5，6，7，则车辆出站的顺序为（C）。A.1,2,3,4,5B.1,2,4,5,7C.1,4,3,7,6D.1,4,3,7,2队列跟栈相反，队列是限定只能在表的一端进行插入，在表的另一端进行删除的数据结构。队列的特征是“先进先出”（就像排队买东西，排在前面的人买完东西后离开队伍（删除），而后来的人总是排在队伍未尾（插入））通常把队列的删除和插入分别称为出队和入队。•允许删除的一端——队头(front)•允许插入的一端——队尾(rear)a1a2a3…………………….an入队出队队头frontRear队尾队列Q=(a1,a2,……,an)队列a1a2a3…………………….an入队出队frontrear队列Q=(a1,a2,……,an)队列可以用数组Q[m+1]来存储，数组的上界ｍ即是队列所容许的最大容量。在队列的运算中需设两个指针：head：队头指针，指向实际队头元素的前一个位置tail：队尾指针，指向实际队尾元素所在的位置树一棵树是由n（n0）个元素组成的有限集合，其中：（1）每个元素称为结点（2）有且仅有一个特定的结点，称为根结点或树根（3）除根结点外，其余结点能分成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的层次为3，结点8、9的层次为4。一棵树中所有的结点的层次的最大值称为树的深度（或高度）如：这棵树的深度为4。二叉树二叉树是一种特殊的树型结构，它是最大度数为2的树。它的两棵子树分别称为左子树、右子树。二叉树的每个结点最多有两个子结点。每个结点的子结点分别称为左孩子、右孩子，。二叉树有5中基本形态：二叉树的性质【性质1】在二叉树的第i层上最多有2i–1个结点（i=1）。【性质2】深度（高度）为k的二叉树至多有2k-1个结点（k=1）。二叉树的性质【性质3】N=n0+n1+n2【性质4】n0=n2+1设二叉树中度为0,1,2的结点分别有no,n1,n2个,总结点数为N.树的遍历在应用树结构解决问题时，往往要求按照某种次序获得树中全部结点的信息，这种操作叫作树的遍历。遍历的方法有多种，以二叉树为例树的遍历先序遍历先序（根）遍历：(1)先访问根结点⑵先序遍历左子树⑶先序遍历右子树如右图先序遍历的结果为：abdehicfg树的遍历中序遍历中序（根）遍历：⑴中序遍历左子树⑵访问处理根结点⑶中序遍历右子树如右图中序遍历的结果为：dbheiafcg树的遍历后序遍历后序（根）遍历：⑴后序遍历左子树⑵后序遍历右子树⑶访问处理根结点如上图后序遍历的结果为：dhiebfgca树的遍历层次遍历层次遍历：按层次从小到大逐个访问，同一层次按照从左到右的次序。如右图层次遍历的结果为：hIdefgbca练习1、二叉树T，已知其前序遍历序列为1243576，中序遍历序列为4215736，则其后序遍历序列为（B）。A.4257631B.4275631C.4275361D.472356122图通俗说，各顶点用边连起来就叫做图图和树的区别？（1）树形结构中，每一个数据有可能有多个下层结点（孩子结点），但却只与一个上层结点相关。（2）图形结构中，结点之间的关系可以是任意的，图中任意两个数据之间都可能相关。图12345(a)12345(b)(a)有向图：图的边有方向，只能按箭头方向从一点到另一点。(a)就是一个有向图。(b)无向图：图的边没有方向，可以双向。(b)就是一个无向图。结点的度：无向图中与结点相连的边的数目，称为结点的度。有向图中结点的度等于该结点的入度和出度之和结点的入度：在有向图中，以这个结点为终点的有向边的数目。结点的出度：在有向图中，以这个结点为起点的有向边的数目。12345(a)12345(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的最短路径？权值：边的“费用”，可以形象地理解为边的长度。图-最短路径算法=HhWTqiBZp4ulwCMG0gUa-jOTXQHKYzPHRqlHfYhICEovxHLrYhSxkBTIJwKS2qKpBXv2QaFPJpsY6mF8C1wd9YceEcKosxzIrNbM4oYzP7S