西华大学数据结构复习

1、数据元素组成数据的有一定意义的基本单位。数据项(Data Item)： 一个数据元素可以由若干个数据项组成是数据不可分割的最小单 位。集合：数据元素“同属一个集合”，无其他关系线性结构：数据元素的关系是“一对一”，次序树形结构：数据元素的关系是“一对多”，层次图形结构：数据元素的关系“多对多”，网状顺序存储结构链式存储结构索引存储结构散列存储结构ADT抽象数据类型名数据对象：数据对象定义数据关系：数据关系定义数据操作：数据操作定义 ADT抽象数据类型名算法定义：具体问题求解方法和步骤的描述，是有限的指令序列。其中，每一条指令表 示一个或多个操作。五个重要特性有穷性：有限步内完成确定性：每一步是

2、确定的，不能有二义可行性：每一步有定义且能求解，如sin(x)=0)首元素无前驱尾元素无后继其余元素唯一前驱、唯一后继链表的特性以链式结构存储的线性表称为线性链表(链表)数据元素：用任意地址的存储单元存储逻辑上相邻元素，其存储位置可不相邻用指针来描述数据元素之间的相邻关系增加新元素时，动态分配内存空间KMP算法：知道如何生成一个next跳转表以及采用kmp算法执行的操作12.结点(Node)结点的度(Degree of an element) 树的度(Degree of a tree)一个数据元素该结点的子树数量（子结点数） 树中所有结点度的最大值叶子（Leaf）（叶结点，终端结点） 度为0的

3、结点（无子结点）分支结点（内部结点）-非终端节点度不为0的结点（非叶结点）无序树与有序树无序树：兄弟结点的左一右位置可以互换有序树：兄弟结点的左一右位置固定，不可互换森林（Forest）：多棵互不相交的树组成森林树的先序遍历（递归/非递归）树的中序遍历（递归/非递归）树的后序遍历（递归/非递归）有点特殊树的层次遍历（递归/非递归）获取树的高度树的存储结构双亲表示法孩子表示法孩子兄弟表示法一般树转换为二叉树（逆过程）长兄为父森林转换为二叉树（逆过程）新的二叉树的根结点作为原来二叉树根的右结点若度=2的结点数n2,则叶结点数n0 = n2+1设度=1的结点数n1，有：总结点数 n = n0 + n

4、1 + n2 （1）总分支数 n-1 = n1 + 2n2（2）（1）-（2） : n0 = n2+1完全二叉树：编号最大的分支结点i =n/2 （根据数组的长度计算其父节点的位置）线索二叉树循环链表判空空串与空白串行优先储存的内存地址，列优先存储的内存地址写递归应该注意的问题：（1）使用递归前应该保存什么数据（2）递归进入/退出的条件（3）递归的返回参数（4）弹栈的条件（5）入栈的条件路径（Path）从一个结点到另一结点的分支组成，如A-D-G-J分支：由边和结点组成，如A-B分支，B-F分支路径长度（Path Length ）边数定义：路径上的分支数（等于路径上的边数）结点定义：路径上的结

5、点数（也有这样定义）树的路径长度从根到每个结点的路径长度之和 WPL等于所有分支结点权值之和（注意看图）哈夫曼树（前缀编码）任一一个字符串的编码不会是另一个字符串编码的前缀变长编码：频繁出现的符号用较少位数编码较少出现的符号用较多位数编码路径长度：路径上的边或弧数，或各边的权值和（带权图）简单路径：路径上顶点不重复（每个顶点仅经过一次）回路/环（Cycle）:路径上第一个与最后一个顶点相同（首尾相连）简单回路（简单环）简单路径+回路：除首尾顶点外，其余顶点不重复连通（Connected）若两个顶点之间存在一条路径，则它们连通连通图（Connected Graph）任意两个顶点都连通的图连通分量（Connected Component）无向图的一个极大连通子图称为一个连通分量极大：边和顶点最多连通图的连通分量：只一个（自己）非连通图连通分量：有多个，下例强连通图：有向图G的任意两个顶点vi和vj, vvj和vjfvi的路径都存在，则G是强连通图生成树/ 支撑树（Spanning Tree, ST）树（自由树）：连通无环图生成树：包含连通图全部顶点的一个连通无环子图有向树只有一个顶点入度=0,其余顶点入度=1的有向图根（有向根）：入度=0图的存储结构邻接矩阵邻接表邻接矩阵：行：出度列：入度图的邻接表如何定义（邻接顶点的定义（边的定义）顶点的定义顶点数组的定义） 边的定义：边的权