1、第五章 多维数组和广义表5.1 数组的定义一、数组的定义数组（Arrays）是由一组类型相同的数据元素构造而成的。它的每个元素由一个值和一组下标确定。二维数组每个元素 aij 均属于两个向量：第 i 行的行向量和第 j 列的列向量。最多可以有两个直接前驱和两个直接后继。二、 数组的顺序存储结构数组的顺序存储结构指的是用一组连续的存储单元依次存放数组元素。 行优先顺序：将数组元素按行向量排列，第 i+1 个行向量紧接在第 i 个行向量后面。 列优先顺序：将数组元素按列向量排列，第 j+1 个列向量紧接在第 j 个列向量之后。 二维数组 Amn 按“行优先顺序”存储在内存中，假设每个元素占 d 个
2、存储单元，则 aij 的地址计算函数为：LOC(aij)=LOC(a11)+(i-1)n+j-1d 对应 C 语言的二维数组：DataType Amn; 数组 Amn的两个下标的下界均为 0，上界分别为 m-1、n-1，每个数据元素占 k 个存储单元，二维数组中任一元素 ai,j的存储位置可由下列公式确定。 loci,j=loc0,0+( n * i + j ) * k 其中，loc0,0是 A00的存储位置，它是该二维数组的起始地址。loci,j 是 Aij的存储位置。这个式子确定了 C 语言的二维数组元素的位置和下标的关系。5.2 矩阵的压缩存储实际工程问题中推导出的数组常常是高阶、含大量
3、零元素的矩阵，或者是些有规律排列的元素。为了节省存储空间，通常是对这类矩阵进行压缩存储. 压缩存储：相同值的多个非零元素占用一个存储单元；零元素不分配存储单元。一、特殊矩阵所谓特殊矩阵（Special Matrices）是指非零元素或零元素的分布有一定规律的矩阵。 几种特殊矩阵的压缩存储： 对称矩阵 在一个 n 阶方阵 A 中，若元素满足下述性质：aij=aji 0i，jn-1 则称 A 为对称矩阵。如图所示：存储元素为：1,5,0,1,8,9,3,0,2,5,7,0,6,1,3，共 15 个。 对于对称矩阵,可以为每一对对称元素分配一个存储空间,因此将 n*n 个元素压缩存放到 n（n+1
4、）/2 个单元中. 一般,可以将下三角的元素存放在一维数组 s0,n(n+1)/2-1中 。则 sk和矩阵元素 aij 之间存在一一对应的关系，：i（i+1）/2+j 当 ij,下三角k = j（j+1）/2+i 当 ij /常数 c 的存储位置下三角矩阵中，sak和 aij 的对应关系是： 对角矩阵 对角矩阵中，所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。如图所示： 对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。二、稀疏矩阵设矩阵 Amn 中有 s
5、 个非零元素，若 s 远远小于矩阵元素的总数（即s mn） ，则称 A 为稀疏矩阵（ Sparse Matrix） 。 当用三元组来表示非零元时，对稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储。 1、三元组表按照压缩存储的概念，只存储稀疏矩阵的非零元素。因此，除了存储非零元素的值外，还必须记下它所在行和列的位置（i,j） 。即用一个三元组（i,j, aij ）唯一确定了矩阵 A 的一个非零元素。若将表示稀疏矩阵的非零元素的三元组按行优先（或列优先）的顺序排列（跳过零元素） ，则得到一个其结点均是三元组的线性表，我们将该线性表的顺序存储结构称为三元组表（List of 3-tuples
6、） 。 三元组表类型描述：第六章 树和二叉树6.1 树的概念一、树的定义与表示法树（Tree）是 n(n0)个结点的有限集 T，T 为空时称为空树，否则它满足如下两个条件： 有且仅有一个特定的称为根（Root）的结点； 其余的结点可分为 m(m0)个互不相交的子集 T1，T 2，T m，其中每个子集本身又是一棵树，并称其为根的子树（Subtree） 。树的递归定义刻化了树的固有特性，即一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。从该定义可知：只有一个结点的树，该结点为根结点；多个结点的树，除根结点之外，它的 M 棵子树 T1，T 2，T m 也是树，且互不相交。 二、树的
7、表示法：树形表示法 嵌套集合表示法 凹入表表示法 广义表表示法 三、树的有关术语 结点：树的结点包含一个数据元素及若干指向其子树的分支。 度（Degree）：一个结点拥有的子树数称为该结点的度。 树的度：一棵树的度是指该树中结点的最大度数。 叶子（Leaf ）和分支结点：度为零的结点称为叶子或终端结点。度不为零的结点称为分支结点或非终端结点。除根结点之外的分支结点统称为内部结点，根结点又称为开始结点。 双亲（Parents）和孩子（Child ）：树中某个结点的子树之根称为该结点的孩子或儿子，相应地，该结点称为孩子的双亲或父亲。 兄弟（Sibling）和堂兄弟：同一个双亲的孩子称为兄弟。双亲在
8、同一层的结点互为堂兄弟。 祖先（Ancestor ）和子孙（ Descendant）：一个结点的祖先是指从树的根到该结点所经分支上的所有结点（包括根结点） 。一个结点的子树的所有结点都称为该结点的子孙。 结点的层数（Level）：是从根起算，设根的层数为 1，其余结点的层数等于其双亲结点的层数加 1。 树的高度（Height ）：树中结点的最大层数称为树的高度或深度（Depth） 。 有序树（Ordered Tree）和无序树（Unordered Tree）：若将树中每个结点的各子树看成是从左到右有次序的（即不能互换） ，则称该树为有序树；否则称为无序树。 在有序树中最左边的子树的根称为第一个
9、孩子，最右边的称为最后一个孩子。 森林（Forest）：是 m(m0)棵互不相交的树的集合。 对树中每个结点而言，其子树的集合即为森林；反之，给一个森林加上一个结点，使原森林的各棵树成为所加结点的子树，便得到一棵树。6.2 二叉树一、 二叉树的定义 二叉树（Binary Tree）是 n(n0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。若二叉树为空集，则称为空二叉树。二叉树是有序的，它的每个结点至多只有两棵子树，且有左、右之分，不能互换；左右子树也可以是空二叉树。 二叉树的基本形态 空二叉树 仅有根结点的二叉树 右子树
10、为空的二叉树 左子树为空的二叉树 左右子树均非空的二叉树 二、二叉树的性质性质 1：在二叉树的第 i 层上至多有 2i-1 个结点（i1） 。性质 2： 深度为 k 的二叉树至多有 2k-1 个结点（k1） 。性质 3： 对任何一棵二叉树 T，如果其终端结点数为 n0，度为2 的结点数为 n2，则 n0=n21三、 二叉树的特殊形态 满二叉树（Full Binary Tree）：一棵深度为 k 且有 2k-1 个结点的二叉树。 特点 1：二叉树的所有分支结点都存在左子树和右子树 特点 2：二叉树的所有叶子结点都在同一层上 完全二叉树（Complete Binary Tree）：深度为 k 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应。 特点 1：叶子结点只可能在层次最大的两层上出现 特点 2：对任一结点，若其右分支下的子孙的最大层次为 L，则其左分支下的子孙的最大层次必为 L 或 L+1 性质 4： 具有 n 个结点的完全二叉树的深度为log2n+1性质 5： 如果对一棵有 n 个结点的完全二叉树（其深度为log2n+1 ）的结点按层序编号（从第 1 层到第 log2n+1 层，每层从左到右） ，则对任一结点 i（1in） ，有
