数据结构复习2010级-副本.DOC.D3C7273FA4A3637FDA38D7771CC6DAEF.docVIP

数据结构复习要点 概论 数据结构概念 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 数据结构=数据元素+关系（结构） 数据的结构的分类 集合、线性结构、树形结构、图（网）状结构 线性结构、非线性结构元素之间的关系 线性结构中各数据成员之间的线性关系:有直接前驱和直接后继(除最前、最后一个元素) 非线性结构中各数据成员之间的没有线性关系: 前驱和后继可能多于一个 存储结构 数据元素在计算机中的表示称为数据的存储结构。包括数据元素的表示和关系的表示。 顺序存储和链式存储。 算法的高效与简易之间的关系 首先算法必须是正确的。此外还需考虑： 1、算法易于理解，易于编程（在计算机上实现）, 易于调试。 2、要求算法高效，节省时间与空间。 时间复杂度是问题规模的函数 － T( n ) 线性表 线性表的两个特征 有且仅有一个开始结点(表头结点)a0，它没有直接前驱，只有一个直接后继;有且仅有一个终端结点(表尾结点)an-1，它没有直接后继，只有一个直接前驱;其它结点都有一个直接前驱和直接后继；元素之间为一对一的线性关系。 串比较compare(s) 求子串substring（int index,int len) 串连接concat（s）串定位indexof(s,startpos) 串插入串删除 字符串的简单模式匹配及其过程 Brute-Force算法 1）获取从主串startpos位置开始到主串最后一个字符的子串 2）将主串从startpos开始的子串中的每个字符与s中的每个字符比较，若相等则继续比较后续字符，否则从主串中子串的下一个位置开始比较。依此类推 3）若存在模式串中的每个字符依次和主串中一个连续的字符序列相等，则匹配成功，返回模式串s第一个字符在主串中的位置，否则返回-1。 计算数组元素在内存地址的因素 一般矩阵、对称矩阵、三角矩阵元素地址的计算公式 字符串及数组的应用 树 树的定义、表示法、基本术语、逻辑特征 二叉树的定义 二叉树（Binary Tree）是n(n≥0)个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。 二叉树的性质，完全二叉树和满二叉树的性质 性质1 一棵非空二叉树的第i层上最多有2^(i-1)个结点（i≥1）。 性质2 一棵深度为k的二叉树中，最多具有2^k－1个结点。 性质3 对于一棵非空的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有: n0＝n2＋1。 性质4 具有n个结点的完全二叉树的深度k为[log2n]+1。 性质5 对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有： （1）如果i1，则序号为i的结点的双亲结点的序号为i/2(“/”表示整除)；如果i＝1，则序号为i的结点是根结点，无双亲结点。 （2）如果2i≤n，则序号为i的结点的左孩子结点的序号为2i；如果2in，则序号为i的结点无左孩子。 （3）如果2i＋1≤n，则序号为i的结点的右孩子结点的序号为2i＋1；如果2i＋1n，则序号为i的结点无右孩子。 此外，若对二叉树的根结点从0开始编号，则相应的i号结点的双亲结点的编号为（i－1）/2，左孩子的编号为2i＋1，右孩子的编号为2i＋2。 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。 完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。 树和二叉树的存储结构 树和二叉树的遍历序列，递归算法 树和二叉树的互相转换 什么是哈夫曼树，哈夫曼树的构造过程 哈夫曼编码的构造过程及电文的互译 图 图的术语，图与连通图 在一个无向图 G 中，若从顶点vi到顶点vj有路径相连(当然从vj到vi也一定有路径)，则称vi和vj是连通的。如果 G 是有向图，那么连接vi和vj的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图 生成树是连通图的极小连通子图。所谓极小是指：若在树中任意增加一条边，则将出现一个回路；若去掉一条边，将会使之变成非连通图。 Prime算法）和最短路径生成树（Dijkstra算法） AOE网的关键路径的求法 排序 直接插入法的排序过程 直接插入排序的基本操作是将当前无序区的第1个记录R[i]插人到有序区R[1．．i-1]中适当的位置上，使R[1．．i]变为新的有序区。因为这种方法每次使有序区增加1个记录，通常称增量法。Shell排序的过程 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个