信息学奥赛辅导数据结构基础知识.doc

数据结构基础知识 根据数据元素间关系的基本特征，有四种基本数据结构： 集合：数据元素间除“同属于一个集合”外，无其它关系。 线性结构：一个对一个，如线性表、栈、队列。 树形结构：一个对多个，如树。 图状结构：多个对多个，如图。 数据的存储结构一般有两种，用一组物理地址相邻的存储单元来存储数据元素的存储方式称之为顺序存储结构；借助于动态数据结构来存储数据元素的存储方式称之为链式存储结构。 数组的存储一般采用的是顺序存储结构，如一维数组和多维数组。按照顺序往下存储数据。如图1 栈结构的特点是“先进后出”，如图2举例说明。 队列结构的特点是“先进先出”，比如排队买票等，如图3举例说明。 树结构：树是n(n=0)个结点的有限集。 任意一棵树，只有一个特定的称为根的结点（如图4中的A）；当n1时，其余结点可分为m(m0)个互不相交的有限集，其中每一个集合本身又是一棵树，并且称为根的子树。 结点拥有的子树数称为结点的度。（如图4中的B所拥有的度为2） 度为0的结点称为叶子或终端节点。（如图4中的H、I、J、K等都是叶子结点） 度不为0的结点称为非终端结点或分支结点。 结点的层次从根开始定义起，根为第一层，根的分支为第二层，依此类推（如图4的树结构最大层次为4层）。树中结点的最大层次称为树的深度或高度。（如图4的树结构的深度或高度为4） 二叉树是一种特殊的树形结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒，所以二叉树是由根节点、左子树、右子树三个基本单元构成。 一棵深度为k的二叉树至多只有2 k－1个结点，此二叉树称为满二叉树（如图4为深度为4的满二叉树），最少也有K个结点（如图5为深度为4的最小二叉树）。可以验证具有n个叶子结点的满二叉树共有2n－1个结点（如图5的满二叉树）。 在二叉树的第i层上至多有2 i－1个结点。 树的遍历：按照根节点在访问中的先后位置，我们有三种树的遍历方式。（当然每次访问都是左子树在右子树的前面。） 先序遍历（先访问根节点，再访问左子树，最后访问右子树）： 如图4的先序遍历为：A、B、D、H、I、E、J、K、C、F、L、M、G、N、O。 中序遍历（先访问左子树，再访问根节点，最后访问右子树）： 如图4的中序遍历为：H、D、I、B、J、E、K、A、L、F、M、C、N、G、O。 后序遍历（先访问左子树，再访问右子树，最后访问根节点）： 如图4的后序遍历为：H、I、D、J、K、E、B、L、M、F、N、O、G、C、A。 由上面三种遍历树结构的方式可知，先序遍历最先访问的是根节点；后序遍历最后访问的是根节点；由中序遍历的根节点的位置可知，在根节点的左边全部都是根节点的左子树，在根节点的右边全部都是根节点的右子树。必须掌握，由任意两种树的遍历结果，能够画出该二叉树，然后根据该二叉树，写出另一种遍历结果。 哈夫曼树称为最优树，是一类带权路径长度最短的树。 图结构：图是由顶点集V和边集E组成，一般把图G记为G＝（V，E）。 在图6中，边有方向性，我们称之为有向图，有向图的边称之为弧。 在图7中，边没有方向性，即边v1,v2和v2,v1指的是同一条边，我们称之为无向图。 在有向图中，从某顶点出发的弧的数目称为该顶点的出度，到达某顶点的有向弧的数目称为该顶点的入度。（如图6的有向图中，顶点V1的出度为2，入度为1。） 在无向图中，与顶点依附的边的条数称为该顶点的度。（如图7中，顶点V1的度为2。） 完全图定义：如果用n表示图中顶点数目，用e表示边或者弧的数目，则有： 对于有向图，具有n(n-1)条弧的有向图称为有向完全图(任意两个顶点之间都有2条有向弧) 对于无向图，具有n(n-1)/2条边的无向图称为完全图（任意两个顶点之间都有一条边。） 连通图定义：在无向图中，若图中任意两个顶点之间都存在路径，则称该无向图为连通图。在有向图中，对于任意两个顶点Vi和Vj（Vi≠Vj），若从Vi到Vj和从Vj到Vi之间均存在路径，则称该有向图为强连通图。 带权图定义：有时图的边往往与具有一定意义的数值有关，我们把这种与图的边相关的数称为边上的权。权可以表示从一个顶点到另一个顶点的距离、费用或代价等，由这种带权的边构成的图称为带权图。 图的遍历方式有两种：深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站。 二分法查找：具体方法见课本P147～P148面。二分法查找（又称折半查找）算法如下： 首先需要设三个指示器top、bot、mid，分别指向查找范围的顶部、底部和中间位置。假定有11个元素的有序数列(2，5，7，10，14，15，18，23，35，41，52)，待查找数为41，则一开始top＝1、bot＝11、mid＝（top＋bot）div 2＝