假期连载之九
（数组和广义表）
本节介绍线性表的两个推广结构—数组和广义表，这也是线性结构和表结构部分最后两个重要内容。
数组
我们在介绍线性表基本存储结构时曾提到数组，这是因为在大多数高级程序设计语言中，数组即被用来表示一段连续的存储空间，它对一般线性表的概念和原理起到了很好的诠释作用。但是，在很多工程领域中，数组并不单以一维数组的形态出现，我们大量接触到了二维甚至是三维数组，它们通常是计算机图形学、工业设计、医疗等领域的计算工具。
本部分内容重点介绍多维数组的计算及其内部存储实现。
数组是由下标index和值value组成的序对的集合。在数组中，每个有定义的下标都有一个值对应，这个值被称作数组元素。前面的讲解中曾介绍过C++独特的静态数组和动态数组，在其它一些高级语言中数组的定义也是大同小异，例如在Visual Basic中还可以定义变长的数组。
二维数组，其数学模型实际上就是矩阵。相对于一维数组给定下标值即可唯一确定一个元素，以及该元素的直接前驱和直接后继，二维数组需要同时给定两个下标值，且其直接前驱分为x向和y向两类。例如对于二维数组a[m][n]，元素a[j][k]的直接前驱分别为a[j-1][k]和a[j][k-1]，其直接后继分别为a[j+1][k]和a[j][k+1]。因此可以把二维数组可以看作最简单的非线性结构。
对于任意三维数组a[m][n][o]，我们先将a看作一维数组a[m]，其中任意元素a[j]中还存在一个二维数组，相应地，其直接前驱和直接后继就有三个。上述结论推广至n维数组，其直接前驱与后继个数即为n。
多维数组的存储表示
多维数组之所以复杂，是因为在计算机存储内部并没有真正涉及到多维数组存储，其存储表示是基于一维数组来实现的。
一般地对于一维数组a[n]，若设它的第一个数组元素的存储起始地址为a，每一个数组元素的存储大小为l，则任一数组元素的存储地址LOC(i)可以用如下的递推公式计算：
a ,i=0
LOC(i)={LOC(i-1),i>1
因此有：LOC(i)=LOC(i-1)+l=a+i*l
对于二维数组a[n][m]，为能根据它们的数组元素的下标计算出在相应一维数组种对应的下标，需要区分两种存储方式，即行优先顺序和列优先顺序。
按照行优先顺序，所有数组元素按行向量排列，第i+1个行向量紧跟在第i个行向量后面，这样得到数组元素存于一维数组的一种线性序列。这种行优先策略被使用在如ALGOL、PASCAL、C/C++、BASIC和Ada等多数高级语言中。
相应地，存在一种按列优先的顺序，所有数组元素按列向量依次排列。FORTRAN语言即是以此为策略实现二维数组的。
现在我们以行优先顺序为例，讨论二维数组地址的映射方法。
设二维数组a[n][m]的第一个元素a[0][0]存于相应一维数组的第一个位置，其地址为a，每个元素占1大小的空间，根据一维数组元素a[j][k]地址计算公式：
LOC(j,k)=LOC(j,0)+k
=LOC(j-1)+m+k
…
=LOC(0,0)+j*m+k
=a+j*m+k
以上就是二维数组对一维数组元素地址的映射公式。
对于三维数组a[m][n][o]，其优先顺序就不简单地判定为“谁优先”的问题，而是分优先级别。假设m为页号，n、o分别为页内二维数组的行列号，则有页最优先，其次为行优先的策略，同样可能共有六种不同的顺序。我们先以第一种策略为例计算其对一维数组元素地址的映射公式：
LOC(i,j,k)=LOC(i,0,0)+j*o+k
=LOC(i-1,0,0)+n*o+j*o+k
…
=LOC(0,0,0)+i*m*o+j*o+k
=a+i*m*o+j*o+k
推广至n维数组a[m1]…[mn]来说，设其第一个数组元素a[0]…[0]在相应一维数组中也是第一个位置，其下标为a，优先顺序随着下标维数增大而逐渐变小，则一个数组元素a[i1]…[in]在相应一维数组中的存储地址为：
LOC(i1,i2,…,in)
=LOC(0,0,…,0)+i1*m2*m3…*mn+i2*m3*m4…*mn+…+in
特殊矩阵
矩阵操作是多维数组最广泛的应用。矩阵的知识最初介绍于大学理工类科目基础课程线性代数中，它是科学计算、工程数学，尤其是数值分析经常研究的对象。而在一些高级矩阵中，存在大量0元素，使得非零元素极少（远小于m*n），如果仍然根据普通数组存储顺序存放，将造成存储空间的很大浪费。基于节省存储空间的考虑，我们进一步讨论特殊矩阵的内部规律，以及利用这些规律制定策略，实现压缩存储，达到提高存储空间利用率的目的。
1、对称矩阵
对于特殊矩阵的研究通常基于两点，一是矩阵内部元素的分布有明显规律，二是矩阵内部非零元素个数远小于m*n。对称矩阵即属于第一种情况。
在一个n阶方阵A中，对A中任意元素a[i][j]有i<j时，aij=c(通常c=0)，则称其为下三角矩阵，相反地为上三角矩阵。对于三角阵其元素包括了对角线以及对角线一边的元素，其个数共有n+(n-1)+…2+1=n(n-1)/2。要压缩存储矩阵，即只要存储三角阵中非零一边的元素即可，其核心实际上为三角阵对一维数组元素地址的映射问题。
同样以行优先为顺序，当只存储下三角部分时，对于i>j时的任意元素aij，其前方有i行的元素及i+1行的前j个元素，则其地址事实上可以转换为简单的求和公式：
LOC(i,j)=1+2+3+…+i+j=i*(i+1)/2+j
对于对称矩阵，可以据此求出未被实际存储的元素aji的值：
LOC(i,j)=LOC(j,i)=(j+1)*j/2+i
当存储上三角矩阵时，第0行存放n个元素，第i+1行从aii算起，aij前共有j-i个元素，则其地址映射公式为：
LOC(i,j)=n+n-1+…+n-i+1+j-i=(2n-i+1)*i/2+j-i=(2n-i-1)*i/2+j
则当i>j时的对称矩阵元素aji的值可由以下公式求得：
LOC(i,j)=LOC(j,i)=(2n-j-1)*j/2+i
2、带状矩阵
带状矩阵实际上是一种特殊的稀疏矩阵，其元素一般分布在主对角线为中心的带状区域内。其中最常见的是三对角带状矩阵。
三对角线矩阵中，除了主对角线及其左右两条对角线的元素外，其余元素值均为0。对于三对角线矩阵的压缩存储，其实质和三角矩阵相比并无太大区别。依然以行优先为顺序，三对角线矩阵的非零元素个数为3n-2。由此推广至多对角线矩阵存储，假设主对角线一侧分别有b条次对角线包含非零元素，据此求得多对角线矩阵的非零元素个数为n+2(n-1+n-2+…+n-b)=n+b(2n-b-1)=(2b+1)n-b-b*b。对于求带状矩阵对一维数组元素地址的映射公式，我们要基于以下三种情况分别考虑：
当1<=i<=b时，此时元素属于矩阵的上部区域。则元素aij的定位：
LOC(i,j)=b+1+b+2+b+3+…+b+i-1+j-1=(2b+i)(i-1)/2+j-1
当b<i<n-b+1时，元素处于矩阵的中部区域。
LOC(i,j)=(b+1)+(b+2)+(b+3)+…+(b+b)+(i-b-1)(2b+1)+j-i+b=(3b+1)b/2+(i-b-1)(2b+1)+j-i+b
当n-b+1<=i<=n时，元素处于矩阵的下部区域，则：
LOC(i,j)=(3b+1)/2+(n-2b)(2b+1)+(3b-i+n+2)(i-n+b-1)/2+j-i+b
综上即可求出各种情况下按行优先的带状矩阵对一维数组元素的映射地址。
特殊地，对于三对角线矩阵，公式简化为：
LOC(i,j)=2(i-1)+j-1
3、稀疏矩阵
稀疏矩阵Sparse Matrix是非零元素个数远小于零元素个数的一类矩阵的统称。大多数的稀疏矩阵其非零元素分布上一般无规律可循。
一般在n*m矩阵中定义一个稀疏因子δ，其非零元素个数为t，有δ=t/(m+n)，当δ<0.05时可以认为该矩阵为稀疏矩阵。
为了合理表示和存储稀疏矩阵，一般采取三元组表的方法。对于稀疏矩阵只存储非零元素，则先定义一个三元组结构：
#define MaxSize 1000 //非零元素的个数最多为1000
typedef struct
{
int row,col; //记录了非零元素在原矩阵中的行号、列号
ElementType e; //值
}Triple;
再根据此结构建立三元组表
typedef struct
{
Triple data[MaxSize+1]; //设定三元组表，data[0]未用
int m,n,len; //记录矩阵的行数、列数以及非零元素的个数
}
稀疏矩阵的转置运算
矩阵转置是指变换元素位置，使位于(row,col)上的元素与(col,row)上的元素进行互换，即行列互换运算。这是矩阵的一种基本运算形式。
稀疏矩阵由于其特殊的存储结构，转置操作就与普通矩阵转置有很大不同。我们先来看一般矩阵的经典转置算法：
TransMatrix(ElementType source[m][n]，ElementType dest[n][m])
{
int i,j;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
dest[j][i]=source[i][j];
}
显然稀疏矩阵的三元组表形式无法使用经典算法转置。
有一种简单的转置方法，首先把三元组表中元素的row和col值互换，然后按新row值递增序列重新排序。此方法理论上达到了转置的目的，但排序效率较低，并不是合适的转置算法。
一般来说三元组表的转置有两种普遍算法：
1、“列序”递增转置法
算法开始按照col列序为1，行序递增的顺序从头到尾找出转置后的第一行元素，行列值互换后存入dest，然后再从头到尾按列序位2，行序递增的顺序重复操作……直到找出第k行全部元素，其中1<=k<=n。程序主体为双循环结构：
for(k=1;k<=A.n;k++)
for(i=1;i<A.len;i++)
//互换
j++;//j值储存的是dest中下一个转置后元素的位置下标
该算法的时间复杂度为O(A.n*A.len)，最坏情况时A.n*A.m=A.len，即全部为非零元素，则时间复杂度为O(A.m*A.n*A.n0)，反而远高于经典算法的O(A.m*A.n)，因此此算法仅适用于三元组表转置。
2、“一次定位快速转置”法
现在对第一种算法进行性能优化，突破点在消除双重循环上。我们从前几节的连载中得到一种经验，在类似于将一种结构按一定规律转化为另一种结构的过程中，如果要进行性能优化，就必须深入探究原有结构内部的规律，凭借此规律取得的一部分资源，恰可以替代外层循环的作用。例如连载七中对字符串简单模式匹配算法的改进算法KMP。
现在我们分析三元组表，根据此表的分析我们可以得出两个有益的信息：一是转置后每行非零元素的个数，二是转置后每行第一个非零元素的位置。这两个信息足以达到消除一层循环的目的。
设num[col]记录三元组表col=1,2,…,n中元素的个数，position[col]记录三元组表col=1,2,…,n中第一个元素在表中的下标值。算法程序主体为单循环结构（我们省略了计算两个辅助数组的部分）：
for(p=1;p<=A.len;p++)
{
//该方法的原理是，由于转置后每列第一个非零元素必然在三元组表中优先出现，因此直接与position在相应列的位置配对，算法结束后相应位置加1以便放入该列内的剩余元素
col=A.data[p].col;
q=position[col];
//dest[q]与A.data[p]互换数值
position[col]++;
}
实际程序中由于数组初始化等因素，共用到四个单循环，总的时间复杂度为O(A.n+A.len)，较第一种方法而言在性能上有了很大提高，但也必须看到，由于所需存储空间增加，事实上说明算法在时间上的节省是以更多的存储空间为代价。
稀疏矩阵的正交链表存储
这里我们忽略了三元组表中对于稀疏矩阵四则运算操作的实现，这是因为矩阵加减法较为简单，而乘法虽然规则清晰，但由于依然涉及到遍历的问题，有时甚至需要三重循环来实现运算，较为复杂，且不符合本次系列连载的目的。
但矩阵运算所带来的问题却不容忽视，尤其是其对三元组表可能发生元素值的修改、元素个数的增减等等复杂运算。为了更有利于实际应用，有时候稀疏矩阵使用正交链表的存储形式，也称“十字链表”。
稀疏矩阵的正交链表结点共有六个域，分别为row、col、down(链接列链表中下一个结点)、right(链接行链表中下一个结点)、head（是否为附加头结点）、value。因此正交链表其实就是将矩阵的每一行与每一列分别建立链表，逻辑上是“十字交叉”状的。
广义表
广义表同样作为线性表的一种推广，但更准确地讲，广义表才能真正意义上被称为“表”，线性表可以被当作一种特殊的表，但在实际中往往可能特殊的结构反而更容易被广泛使用。
广义表generalized list长期以来主要用于人工智能领域的研究，向前继承了离散数学的部分内容。在List processor语言LISP中，其表达式就是用表的形式来实现的。
广义表的显著特点是允许表中有表，广义表也是一组有限的序列，表中第一个元素被称为广义表表头head，除此之外的其它元素所组成的表称作表尾tail。下面给出一些广义表的实例：
D=()，空表，长度为0；
A=(a,(b,c))，表长度为2，表头为a，表尾为((b,c))；
B=(A,A,D)，长度为3，表头为A，第三个元素为空表D；
C=(a,C)，表长为2的递归定义的广义表，C相当于无穷表。
由上可得出广义表的五个性质：
1、 有次序性，因为表中元素是按线性排列的，其前驱、后继关系依然存在。
2、 有长度，广义表元素的个数是一定的，不能是无限长，且可以为空。
3、 有深度，广义表的元素可以是原表的子表，子表的元素还可以是子表……从而形成多层次结构。
4、 可递归的，广义表本身可以是自己的子表。
5、 可共享的，广义表可以被其它表共享。
广义表存储结构的实现
由于广义表本身结构的不确定性，因此凭借顺序结构很难对其进行表示，因此一般使用链式存储结构来表示。
1、 广义表的头尾链表存储结构
广义表链式存储的结点分为两类，一类是单个元素结点，其结点由标志域和值域构成；另一类是子表结点，其结点由标志域、指向标头的指针域和指向表尾的指针域构成。
现在给出C语言描述的广义表头尾链表存储结构的类型定义：
typedef enum{ATOM,LIST} ElemTag;
typedef stuct GLNode
{
ElemTag tag;
union
{
AtomType atom;
struct
{
struct GLNode *hp,*tp;
}htp;
}atom_htp;
}GLNode,*Glist;
2、 广义表的扩展线性链表存储结构
扩展线性链表存储结构的特点是，其子表结点和元素结点均由三个域构成：标志域、表头指针/值域、表尾指针。在两种表示形式中需要注意，标志域虽然为enum型，但实际默认ATOM为0，LIST为1，在绘制结构图时需要特别注意。
广义表的递归运算
由于广义表的递归性，因此很多关于广义表的基本运算也是递归的。我们省略了取表头、表尾、长度等几个较简单的运算，直接举例求解广义表深度的C语言算法描述：
int Depth(Glist L)
{
int d,max;
GLNode *x;
if(L==NULL) //为空表，默认为深度为1
return 1;
if(L->tag==ATOM)
return 0; //元素结点深度为0
s=L;
max=0; //初始化表/子表深度值
while(s!=NULL) //求每个子表的最大深度值，回溯结束后即为最深子表的深度
{
d=Depth(s->atom_htp.htp.hp);
if(d>max)
max=d;
s=s->atom_htp.htp.tp;
}
return max+1; //最终深度等于最深子表的深度加1
}
现在，我们已经介绍了简单数据结构线性表部分的全部内容，按照计划，后面的几期连载将继续介绍几种简单的数据结构。近期会制定总结出返校后本连载的内容方向，以及其它一些内容。
（未完待续）