资源描述：
《信息学奥赛-数据结构》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通俗解释：数据相当于书.计算机相当于书架，存放了很多书，书架分为很多格子，书存放在不同格子（内存空间，对应一个地址），中。为了更快的取到想要的书,要用特定的存放方式—数据结构线性表线性表：n个数据元素的有序集合，“连成线的”是一种常用的数据结构。其中数据元素之间的关系通常是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的实际应用中常见的特殊线性表：栈、队列、字符串、一维数组非线性表非线性表：各个数据元素不再保持在一个线性
2、序列中，每个数据元素可能与零个或者多个其他数据元素发生联系主要代表：树、图结构、多维数组链表链是一种存储单元上非连续、非顺序的存储结构，通过链表中的指针依次访问数据。链表由一系列结点（链表中每一个元素称为结点）组成，数据元素可根据需要实时添加、动态生成。由于非连续，链表无法随机读取，需要通过指针依次访问，查找数据时间长。栈栈是只能在某一端插入和删除的数据结构。（想象用桶堆积物品，先堆进来的压在底下，随后一件件往上堆。取走时，只能从上面一件件取。堆和取都在顶部进行，底部一般是不动的。）栈进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（PUSH
3、），删除则称为退栈（POP）。栈的特征是“后进先出”栈一个栈可以用定长为Ｎ的数组Ｓ来表示用一个栈指针TOP指向栈顶。若TOP＝0，表示栈空，TOP=N时栈满。进栈时TOP加１。退栈时TOP减１。当TOP<0时为下溢。练习某个车站呈狭长形，宽度只能容下一辆车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的顺序为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队列跟栈相反
4、，队列是限定只能在表的一端进行插入，在表的另一端进行删除的数据结构。队列的特征是“先进先出”（就像排队买东西，排在前面的人买完东西后离开队伍（删除），而后来的人总是排在队伍未尾（插入））通常把队列的删除和插入分别称为出队和入队。允许删除的一端——队头(front)允许插入的一端——队尾(rear)a1a2a3…………………….an入队出队队头frontRear队尾队列Q=(a1,a2,……,an)队列a1a2a3…………………….an入队出队frontrear队列Q=(a1,a2,……,an)队列可以用数组Q[m+1]来存储，数组的上界ｍ即是队列所容许
5、的最大容量。在队列的运算中需设两个指针：head：队头指针，指向实际队头元素的前一个位置tail：队尾指针，指向实际队尾元素所在的位置树一棵树是由n（n>0）个元素组成的有限集合，其中：（1）每个元素称为结点（2）有且仅有一个特定的结点，称为根结点或树根（3）除根结点外，其余结点能分成m（m>=0）个互不相交的有限集合T0,T1,T2,……Tm-1。其中的每个子集又都是一棵树，这些集合称为这棵树的子树。2的子节点5，6的父节点根节点2的兄弟树一个结点的子树个数，称为这个结点的度如：结点1的度为3，结点3的度为0度为0的结点称为叶结点如：结点3、5、6、
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的树。它的两棵子树分别称为左子树、右子树。二叉树的每个结点最多有两个子结点。每个结点的子结点分别称
7、为左孩子、右孩子，。二叉树有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)先访问根结点⑵先序遍历左子树⑶先序遍历右子树如右图先序遍历的结果为：ab
8、dehicfg树的遍历中序遍历中序（根）遍历：⑴中序遍历左子树⑵访问处理根结点⑶中序遍历右子树
