第5章多维数组和广义表 数据结构（C+描述） 5.5 广义表5.1多维数组5.2多维数组的存储结构5.3 特殊矩阵及其压缩存储5.4 稀疏矩阵退出目录5.1多维数组 5.1.1多维数组的概念 1一维数组一维数组可以看成是一个线性表或一个向量（第 二章已经介绍），它在计算机内是存放在一块连 续的存储单元中，适合于随机查找。这在第二章 的线性表的顺序存储结构中已经介绍。2二维数组二维数组可以看成是向量的推广。 例如，设A是一个有m行n列的二维数组，则A可以 表示为：在此，可以将二维数组A看成是由m个行向量X0，X1， ，Xm1T组成，其中，Xi=( ai0, ai1, .,ain1)， 0im1 ；也可以将二维数组A看成是由n个列向量y0, y1, ,yn1组成，其中 yi=(a0i, a1i, .,am1i)， 0in1。 由此可知二维数组中的每一个元素 最多可有二个直接 前驱和两个直接后继（边界除外），故是一种典型的 非线性结构。3多维数组同理，三维数组最多可有三个直接前驱和三个直接后继， 三维以上数组可以作类似分析。因此，可以把三维以上的 数组称为多维数组，多维数组可有多个直接前驱和多个直 接后继，故多维数组是一种非线性结构。5.1.2 多维数组在计算机内的存放怎样将多维数组中元素存入到计算机内存中呢？由于 计算机内存结构是一维的（线性的），因此，用一维 内存存放多维数组就必须按某种次序将数组元素排成 一个线性序列，然后将这个线性序列顺序存放在存储 器中 5.2多维数组的存储结构由于数组一般不作插入或删除操作，也就是说，一旦建 立了数组，则结构中的数组元素个数和元素之间的关系 就不再发生变动，即它们的逻辑结构就固定下来了，不 再发生变化。因此，采用顺序存储结构表示数组是顺理 成章的事了。本章中，仅重点讨论二维数组的存储，三 维及三维以上的数组可以作类似分析。多维数组的顺序存储有两种形式：5.2.1 行优先顺序1存放规则 行优先顺序也称为低下标优先或左边下标优先于右边下 标。具体实现时，按行号从小到大的顺序，先将第一行 中元素全部存放好，再存放第二行元素，第三行元素， 依次类推 在BASIC语言、 PASCAL语言、 C/C+语言等高级语言 程序设计中，都是按行优先顺序存放的。例如，对刚才 的Amn二维数组，可用如下形式存放到内存：a00， a01, a0n1，a10，a11，.， a1 n1，am1 0 ， am1 1，am1 n1。即二维数组按行优先存放到内存后，变成了一个 线性序列（线性表）。因此，可以得出多维数组按行优先存放到内存的规律 ：最左边下标变化最慢，最右边下标变化最快，右边 下标变化一遍，与之相邻的左边下标才变化一次。因 此，在算法中，最左边下标可以看成是外循环，最右 边下标可以看成是最内循环。 2地址计算 由于多维数组在内存中排列成一个线性序列，因此，若 知道第一个元素的内存地址，如何求得其它元素的内存 地址？我们可以将它们的地址排列看成是一个等差数列 ，假设每个元素占l个字节，元素aij 的存储地址应为第一 个元素的地址加上排在aij 前面的元素所占用的单元数， 而aij 的前面有i行(0i1)共in个元素，而本行前面又有j 个元素，故aij的前面一共有in+j个元素，设a00的内存地 址为LOC(a00)，则aij的内存地址按等差数列计算为 LOC(aij)=LOC(a00)+（in+j）l。同理，三维数组Amnp 按行优先存放的地址计算公式为： LOC(aijk)=LOC(a000)+(inp+jp+k)l。5.2.2 列优先顺序1存放规则列优先顺序也称为高下标优先或右边下标优先于左边下 标。具体实现时，按列号从小到大的顺序，先将第一列 中元素全部存放好，再存放第二列元素，第三列元素， 依次类推 在FORTRAN语言程序设计中，数组是按列优先顺序存 放的。例如，对前面提到的Amn二维数组，可以按如下 的形式存放到内存：a00， a10， am10， a01，a11， ， am1 1， a0 m1，a1m1，.， am1 n1。 即二维数组按列 优先存放到内存后，也变成了一个线性序列（线性表） 。因此，可以得出多维数组按列优先存放到内存的规律 ：最右边下标变化最慢，最左边下标变化最快，左边 下标变化一遍，与之相邻的右边下标才变化一次。因 此，在算法中，最右边下标可以看成是外循环，最左 边下标可以看成是最内循环。2地址计算 同样与行优先存放类似，若知道第一个元素的内存地址 ，则同样可以求得按列优存放的某一元素aij的地址。对二维数组有：LOC(aij)=LOC(a00)+(jm+i)l对三维数组有： LOC(aijk)=LOC(a000)+(kmn+jm+i)l5.3 特殊矩阵及其压缩存储 5.3.1 特殊矩阵 若一个n阶方阵A中元素满足下列条件： aij=aji 其中 0 i, jn1 ， 则称A为对称 矩阵。例如，图51是一个3*3的对称矩阵。1对称矩阵 2三角矩阵 （1）上三角矩阵即矩阵上三角部分元素是随机的，而下三角部分元 素全部相同（为某常数C）或全为0，具体形式见 图52(a)。 （2）下三角矩阵即矩阵的下三角部分元素是随机的，而上三角部 分元素全部相同（为某常数C）或全为0，具体形 式见图52(b)。 3对角矩阵 若矩阵中所有非零元素都集中在以主对角线为中 心的带状区域中，区域外的值全为0，则称为对角 矩阵。常见的有三对角矩阵、五对角矩阵、七对 角矩阵等。 例如，图53为77的三对角矩阵（即有三条对角 线上元素非0）。 5.3.2 压缩存储1对称矩阵 若矩阵Ann是对称的，对称的两个元素可以共用一个存 储单元，这样，原来n 阶方阵需 n2个存储单元，若采用 压缩存储，仅需 n(n+1)/2个存贮单元，将近节约一半存 贮单元，这就是实现压缩的好处。但是，将n阶对称方 阵存放到一个向量空间s0到s 1 中，我们怎样找到sk与aij的一一对称应关系呢？使我们 在sk中直接找到aij。我们仅以行优先存放分两种方式讨论：（1）只存放下三角部分由于对称矩阵关于主对角线对称，故我们只需存放主 对角线及主对角线以下的元素。这时， a00存入 s0，a10 存入s1，a11存入 s2，具体参 见图54。这时sk与aij的对应关系为：i(i+1)/2+j 当 ijk=j(j+1)/2+i 当 ij时，交换i与j即可。故sk与aij 的对应关系为：i*n +ji 当ij k= j*n +ij 当ij2三角矩阵 （1）下三角矩阵下三角矩阵的压缩存放与对称矩阵用下三角形式存放 类似，但必须多一个存储单元存放上三角部分元素， 使用的存储单元数目为n(n+1)/2+1。故可以将nn的下 三角矩阵压缩存放到只有n(n+1)/2+1个存储单元的向量 中，假设仍按行优先存放，这时sk与aij的对应关系 为：i(i+1)/2+j ijk= n(n+1)/2 ij 3对角矩阵我们仅讨论三对角矩阵的压缩存贮，五对角矩阵，七 对角矩阵等读者可以作类似分析。在一个nn的三对角矩阵中，只有n+n1+n1个非零元 素，故只需3n2个存储单元即可，零元已不占用存储 单元。故可将nn三对角矩阵A压缩存放到只有3n2个存储单 元的s向量中，假设仍按行优先顺序存放，则：sk与aij的对应关系为：3i1 当 i=j+1k= 3i 当i=j3i+1 当i=j15.4 稀疏矩阵 在上节提到的特殊矩阵中，元素的分布呈现某种规 律，故一定能找到一种合适的方法，将它们进行压 缩存放。但是，在实际应用中，我们还经常会遇到 一类矩阵：其矩阵阶数很大，非零元个数较少，零 元很多，但非零元的排列没有一定规律，我们称这 一类矩阵为稀疏矩阵。按照压缩存储的概念，要存放稀疏矩阵的元素，由于 没有某种规律，除存放非零元的值外，还必须存贮适 当的辅助信息，才能迅速确定一个非零元是矩阵中的 哪一个位置上的元素。下面将介绍稀疏矩阵的几种存 储方法及一些算法的实现。 5.4.1 稀疏矩阵的存储 1三元组表在压缩存放稀疏矩阵的非零元同时，若还存放此非零元 所在的行号和列号，则称为三元组表法，即称稀疏矩阵 可用三元组表进行压缩存储，但它是一种顺序存贮（按 行优先顺序存放）。一个非零元有行号、列号、值，为 一个三元组，整个稀疏矩阵中非零元的三元组合起来称 为三元组表。此时，数据类型可描述如下：const int maxsize=100;/定义非零元的最大数目struct node /定义一个三元组 int i , j; /非零元行、列号int v; /非零元值; struct sparmatrix /定义稀疏矩阵 int rows,cols ; /稀疏矩阵行、列数int terms; /稀疏矩阵非零元个数node data maxsize; /三元组表;稀疏矩阵M和N的三元组表见图58。 2带行指针的链表 把具有相同行号的非零元用一个单链表连接起来，稀 疏矩阵中的若干行组成若干个单链表，合起来称为带 行指针的链表。例如，图56 的稀疏矩阵M的带行指针 的链表描述形式见图59。 3十字链表 当稀疏矩阵中非零元的位置或个数经常变动时，三元组 就不适合于作稀疏矩阵的存储结构，此时，采用链表作 为存储结构更为恰当。十字链表为稀疏矩阵中的链接存储中的一种较好的存储 方法，在该方法中，每一个非零元用一个结点表示，结 点中除了表示非零元所在的行、列和值的三元组(i,j,v)外 ，还需增加两个链域：行指针域(rptr)，用来指向本行中 下一个非零元素；列指针域(cptr) ，用来指向本列中下一 个非零元素。稀疏矩阵中同一行的非零元通过向右的rptr 指针链接成一个带表头结点的循环链表。同一列的非零 元也通过cptr指针链接成一个带表头结点的循链链表。因 此，每个非零元既是第i行循环链表中的一个结点，又是 第j列循环链表中的一个结点，相当于处在一个十字交叉 路口，故称链表为十字链表。另外，为了运算方便，我们规定行、列循环链表的表头 结点和表示非零元的结点一样，也定为五个域，且规定 行、列、域值为0，并且将所有的行、列链表和头结点 一起链成一个循环链表。在行(列)表头结点中，行、列域的值都为0，故两组表 头结点可以共用，即第i行链表和第i列链表共用一个表 头结点，这些表头结点本身又可以通过V域(非零元值域 ，但在表头结点中为next，指向下一个表头结点)相链接 。另外，再增加一个附加结点(由指针hm指示，行、列 域分别为稀疏矩阵的行、列数目)，附加结点指向第一 个表头结点，则整个十字链表可由hm指针唯一确定。十字链表的数据类型描述如下：struct linknode int i, j;linknode *cptr, *rptr;union vnext /定义一个共用体 int v; /表结点使用V域,表示非零元值linknode *nex