第6章-多维数组和广义表

实用数据结构基础第6章多维数组和广义表第6章树多维数组和广义表可以看作是线性表的推广，其特点是线性表中的数据元素仍然是一个表。知识点多维数组的逻辑结构和存储结构特殊矩阵的压缩存储稀疏矩阵的三元组存储、十字链表存储广义表的逻辑结构、存储结构及其基本算法难点要求第6章目录6-1多维数组6-2特殊矩阵的压缩存储6-3稀疏矩阵6-4广义表小结验证性实验６：稀疏矩阵和广义表子系统自主性实验6：稀疏矩阵十字链表的存储单元练习66-1多维数组6.1.1逻辑结构数组作为一种数据结构，其特点是结构中的元素可以是具有某种结构的数据，但属于同一数据类型。比如，一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组。一般把三维以上的数组称为多维数组，n维的多维数组可以视为n1维数组元素组成的线性结构。其中每一个一维数组又由m个单元组成。图6-1是一个n行m列的数组。在二维数组中的每一个元素最多可以有两个直接前驱和两个直接后继（边界除外），在n维数组中的每一个元素最多可以有n个直接前驱和n个直接后继。所以多维数组是一种非线性结构。数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识，通常在很多高级语言中数组一旦被定义，每一维的大小及上下界都不能改变。因此，在数组上一般不做插入或删除数据元素的操作。在数组中经常做的两种操作如下。（1）取值操作：给定一组下标，读取其对应的数据元素。（2）赋值操作：给定一组下标，存储或修改与其相对应的数据元素。6.1.2存储结构通常，数组在内存被映象为向量，即用向量作为数组的一种存储结构，这是因为在计算机内存储结构是一维的。数组的行列固定后，通过一个映象函数，就可以根据数组元素的下标得到它的存储地址。对于一维数组只要按下标顺序分配即可；对多维数组分配时，要把它的元素映象存储在一维存储器中。1．存储方式（1）以行为主（rowmajororder）以行为主的存储方式也称为按行优先顺序方式，实现时按行号从小到大的顺序，先存储第0行的全部元素，再存放第1行的元素、第2行的元素……一个2×3二维数组的逻辑结构如图6-2所示，以行为主的内存映象如图6-3（a）所示，其分配顺序为：a00，a01，a02，a10，a11，a12。以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变……，从右向左，最后是左下标。（2）以列为主序（columnmajororder）以列为主的存储方式也称为按列优先顺序方式，实现时按列号从小到大的顺序，先存储第0列的全部元素，再存储第1列的元素、第2列的元素……图6-2所示的逻辑结构，以列为主的内存映象如图6-3（b）所示，其分配顺序为：a00，a10，a01，a11，a02，a12。以列为主分配的规律恰好与以行为主次序相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变……，从左向右，最后是右下标。2．存储地址“以行为主”次序分配存储单元为例看其地址的计算（1）二维数组中aij的地址在C语言中数组中每一维的下界定义为0，数组的基址为LOC(a00)，每个数组元素占据d个字节，那么aij的物理地址可用一个线性寻址函数计算：LOC(aij)=LOC(a00)+(i×n+j)×d（0下标起始的语言）（2）三维数组中aijk的地址同理对于三维数组元素aijk的物理地址为：LOC(aijk)=LOC(a000)+((i×n×p+j×p+k)×d（0下标起始的语言）【例6-1】设二维数组A5×6，每个元素占4个字节（Byte），存储器按字节编址。已知A的起始地址为2000。计算（1）数组的大小n×m×d=5×6×4=120Byte（2）数组结点a45的存储地址LOC(aij)=LOC(a00)+(i*n+j)*d//n为总列数LOC(a45)=2000+(4×6+5)×4=2116（3）按行为主存储，计算a32的存储地址LOC(aij)=LOC(a00)+(i*n+j)*d//n为总列数LOC(a32)=2000+(3×6+2)×4=2080（4）按列为主存储，计算a32的存储地址LOC(aij)=LOC(a00)+(j*m+i)*d//m为总行数LOC(a32)=2000+(2×5+3)×4=2052【例6-2】若矩阵An×m中存在某个元素aij，满足：aij是第i行中最小值且是第j列中的最大值，则称该元素为矩阵A的一个鞍点。试编写一个算法，找出A中的所有鞍点。基本思想：在矩阵A中求出每一行的最小值元素，然后判断该元素是否是它所在列中的最大值。如果是则打印输出，接着处理下一行。设矩阵A用一个二维数组表示，其算法如下：voidsaddle(intA[][],intn,intm){inti,j,min;for(i=0;in;i++)//按行处理{min=A[i][0]for(j=1;jm;j++)if(A[i][j]min)min=A[i][j];//找第i行最小值for(j=0;jm;j++)//检测最小值是否是鞍点if(A[i][j]==min){k=j;p=0;while(pn&&A[p][j]min)p++;if(p=n)printf(＂%d,%d,%d\n＂,i,k,min);}}}算法的时间复杂度为O(n(m+nm))。6-2特殊矩阵的压缩存储矩阵是一个二维数组，是众多科学与工程计算问题中研究的数学对象。在矩阵中非零元素或零元素的分布有一定规律的矩阵称为特殊矩阵，如三角矩阵、对称矩阵、带状矩阵、稀疏矩阵等。当矩阵的阶数很大时，用普通的二维数组存储这些特殊矩阵将会占用很多的存储单元。从节约存储空间的角度考虑，下面来考虑这些特殊矩阵的存储方法。6.2.1对称矩阵对称矩阵是一种特殊矩阵，n阶方阵的元素满足性质：aij=aji（0=i,j=n1）。如图6-4所示是一个５阶对称矩阵。对称矩阵是关于主对角线的对称，因此只需存储上三角或下三角部分的数据即可。比如，只存储下三角中的元素aij，其特点是中j=i且0=i=n1，对于上三角中的元素aij，它和对应的aji相等，因此当访问的元素在上三角时，直接去访问和它对应的下三角元素即可，这样，原来需要nn个存储单元，现在只需要n(n+1)/2个存储单元了，节约了n(n1)/2个存储单元。图6-45阶对称方阵及它的压缩存储如何只存储下三角部分呢？将下三角部分以行序为主序顺序存储到一个向量SA中去。在下三角中共有n(n+1)/2个元素，存储到一个向量空间SA[0]至SA[n(n+1)/2-1]中，存储顺序可用图6-5示意。图6-5对称矩阵下三角压缩存储原矩阵下三角中的某一个元素aij具体对应一个sak，用“以行优先”存放下三角部分的元素时，a00存入sa0，a10存入sa1，a11存入sa2……。sak与aij的一一对应关系为：k=j(j+1)/2+i（0=kn(n+1)/21）当i≥j时，在下三角部分aij前有i行，共有1+2+3+…+i个元素，而aij是第i行的第j个元素，即有k=1+2+3+……+i+j=i(i+1)/2+j。当ij时，aij是上三角中的元素，因为aij=aji，这样，访问上三角中的元素aij时则去访问和它对应的下三角中的aji即可，因此将上式中的行列下标交换就是上三角中的元素在SA中的对应关系：k=j(j+1)/2+i（0=kn(n+1)/21）6.2.2三角矩阵三角矩阵的特殊性是以主对角线划分矩阵。主对角线任意一侧（不包括主对角线中）的元素均为常数，如图6-6所示（矩阵中的c为某个常数）。三角矩阵又可以分为下三角矩阵（主对角线以上均为同一个常数和上三角矩阵（主对角线以下均为同一个常数）。下面讨论三角矩阵的压缩存储方法。1．下三角矩阵的存储下三角矩阵的存储与对称矩阵的下三角形存储类似，不同之处在于存完下三角中的元素之后，紧接着存储对角线上方的常量。因为是同一个常数，所以只要增加一个存储单元即可，这样一共需要n(n+1)/2+1个存储单元。将nn的下三角矩阵压缩存储设到向量SA[n(n+1)/2+1]中，这种的存储方式可节约n(n1)/21个存储单元。sak与aji的对应关系为：下三角矩阵压缩存储如图6-7所示。2．上三角矩阵对于上三角矩阵，其存储思想与下三角类似，共需要n(n+1)/2+1个存储单元。sak与aji的对应关系为：上三角矩阵压缩存储如图6-8所示。图6-8上三角矩阵压缩存储6.3稀疏矩阵上述特殊矩阵，由于元素的分布具有某种规律，所以能找到一种合适的方法进行压缩存储。但实际应用中有一种矩阵，在mn的矩阵中有t个非零元素，且t远小于mn，我们这样的矩阵称为稀疏矩阵。在很多科学管理及工程计算中，常会遇到阶数很高的大型稀疏矩阵。若按常规方法顺序分配在计算机内，那是相当浪费内存的。为此提出另外一些存储方法，仅仅存放非零元素。但对于这类矩阵，通常零元素分布没有规律，为了能找到相应的元素，仅存储非零元素的值是不够的，还要记下它所在的行和列等信息。下面介绍几种常用的稀疏矩阵存储方法以及算法的实现。6.3.1稀疏矩阵的存储1．三元组表存储将非零元素所在的行、列以及它的值构成一个三元组，然后再按某种规律存储这些三元组，采用这种方法存储稀疏矩阵称为三元组表，可以大大节约稀疏矩阵的存储空间。如图6-9的稀疏矩阵A，采用按行优先顺序方式存储该表，其三元组表如图6-10所示。显然，要唯一的表示一个稀疏矩阵，每个非零元素必须存储行、列、值（i,j,v）三个信息。三元组表的定义：#defineSMAX100//定义一个足够大的三元组表structSPNode//定义三元组{inti,j,v;//三元组非零元素的行、列和值};structsparmatrix//定义稀疏矩阵{introws,cols,terms;//稀疏矩阵行、列和非零元素的个数SPNodedata[SMAX];//三元组表};这样的存储方法确实节约了存储空间，但矩阵的运算可能会变得复杂一些。2．带行指针的链表存储若把具有同一行号的非零元素用一个链表连接起来，则稀疏矩阵中的若干行组成若干个单向链表，合起来就成为带行指针的单向链表。图6-9的稀疏矩阵A，可以用图6-11带行指针的单向链表表示。3．十字链表存储三元组表可以看作稀疏矩阵顺序存储，但是在做一些操作（如加法、乘法）时，非零元素的位置和个数会发生变化，三元组表就不太合适了。此时采用十字链表来表示稀疏矩阵将是很方便的。用十字链表存储稀疏矩阵的基本思想是：把每个非零元素作为一个结点存储，结点中除了表示非零元素所在的行、列、值的三元组（i,j,v）以外还增加两个指针域，其结构如图6-14所示。其中：列指针域down用来指向本列中下一个非零元素；行指针域right用来指向本行中下一个非零元素。图6-13稀疏矩阵A的十字链表稀疏矩阵中每一行的非零元素结点按其列号从小到大的顺序由right域连成一个带表头结点的循环行链表，同样每一列中的非零元素按其行号从小到大的顺序由down域也连成一个带表头结点的循环列链表。即每个非零元素aij既是第i行循环链表中的一个结点，又是第j列循环链表中的一个结点。行链表、列链表的头结点的i域和j域置0。每一列链表的表头结点的down域指向该列链表的第一个元素结点，每一行链表的表头结点的right域指向该行表的第一个元素结点。由于各行、列链表头结点的i域、j域和v域均为零，行链表头结点只用right指针域，列链表头结点只用right指针域，故这两组表头结点可以合用。为了方便地找到每一行或每一列，将每行（列）的这些头结点们链接起来，因为头结点的值域空闲，所以用头结点的值域作为连接各头结点的链域，即第i行（列）的头结点的值域指向第i+1行（列）的头结点……，形成一个循环表。这个循环表又有一个头结点，这就是最后的总头结点，指针HA指向它。总头结点的i和j域存储原矩阵的行数和列数。因为非零元素