数据结构专升本资料第四周VIP免费

第五章多维数组和广义表5.1数组的定义一、数组的定义数组（Arrays）是由一组类型相同的数据元素构造而成的。它的每个元素由一个值和一组下标确定。二维数组每个元素aij均属于两个向量：第i行的行向量和第j列的列向量。最多可以有两个直接前驱和两个直接后继。二、数组的顺序存储结构数组的顺序存储结构指的是用一组连续的存储单元依次存放数组元素。行优先顺序：将数组元素按行向量排列，第i+1个行向量紧接在第i个行向量后面。列优先顺序：将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后。二维数组Amn按“行优先顺序”存储在内存中，假设每个元素占d个存储单元，则aij的地址计算函数为：LOC(aij)=LOC(a11)+[(i-1)×n+j-1]×d对应C语言的二维数组：DataTypeA[m][n];数组A[m][n]的两个下标的下界均为0，上界分别为m-1、n-1，每个数据元素占k个存储单元，二维数组中任一元素a[i,j]的存储位置可由下列公式确定。loc[i,j]=loc[0,0]+(n*i+j)*k其中，loc[0,0]是A[0][0]的存储位置，它是该二维数组的起始地址。loc[i,j]是A[i][j]的存储位置。这个式子确定了C语言的二维数组元素的位置和下标的关系。5.2矩阵的压缩存储实际工程问题中推导出的数组常常是高阶、含大量零元素的矩阵，或者是些有规律排列的元素。为了节省存储空间，通常是对这类矩阵进行压缩存储.压缩存储：相同值的多个非零元素占用一个存储单元；零元素不分配存储单元。一、特殊矩阵所谓特殊矩阵（SpecialMatrices）是指非零元素或零元素的分布有一定规律的矩阵。几种特殊矩阵的压缩存储：对称矩阵在一个n阶方阵A中，若元素满足下述性质：aij=aji0≤i，j≤n-1则称A为对称矩阵。如图所示：存储元素为：{1,5,0,1,8,9,3,0,2,5,7,0,6,1,3}，共15个。对于对称矩阵,可以为每一对对称元素分配一个存储空间,因此将n*n个元素压缩存放到n（n+1）/2个单元中.一般,可以将下三角的元素存放在一维数组s[0,n(n+1)/2-1]中。则s[k]和矩阵元素aij之间存在一一对应的关系，：i（i+1）/2+j当ij,下三角k=j（j+1）/2+i当ij//常数c的存储位置下三角矩阵中，sa[k]和aij的对应关系是：对角矩阵对角矩阵中，所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。如图所示：对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。二、稀疏矩阵设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数（即s＜＜m×n），则称A为稀疏矩阵（SparseMatrix）。当用三元组来表示非零元时，对稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储。1、三元组表按照压缩存储的概念，只存储稀疏矩阵的非零元素。因此，除了存储非零元素的值外，还必须记下它所在行和列的位置（i,j）。即用一个三元组（i,j,aij）唯一确定了矩阵A的一个非零元素。若将表示稀疏矩阵的非零元素的三元组按行优先（或列优先）的顺序排列（跳过零元素），则得到一个其结点均是三元组的线性表，我们将该线性表的顺序存储结构称为三元组表（Listof3-tuples）。三元组表类型描述：第六章树和二叉树6.1树的概念一、树的定义与表示法树（Tree）是n(n≥0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：①有且仅有一个特定的称为根（Root）的结点；②其余的结点可分为m(m≥0)个互不相交的子集T1，T2，…，Tm，其中每个子集本身又是一棵树，并称其为根的子树（Subtree）。树的递归定义刻化了树的固有特性，即一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。从该定义可知：只有一个结点的树，该结点为根结点；多个结点的树，除根结点之外，它的M棵子树T1，T2，…，Tm也是树，且...