数组不再是单纯的数据结构的原子类型，而可以形容为线性表的综合体，尤其像多维数组，更像其元素为线性表的线性表（如：二维数组可以看做每个元素是一位数组的一位数组，以此类推）。
数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。
由于数组一般不做插入或和删除操作，也就是说，一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不再发生变化。因此，采用顺序存数结构表示数组就是很自然的事情了。
由于存储单元是一维的结构，而数组是个多维的结构，则用一组连续存储单元存放数组的数据元素就有个次序约定问题。比如：二维数组要如何存储到线性的内存中？其实不同语言处理起来是不一样的。BASIC，PL/1，COBOC，PASCAL和C语言则采用了以行序为主序的存储结构，说白了，就是在线性内存中，先存储a00，...，a0n直到存储，an0，...，ann，而在FOR，TRAN等语言中，则一列序为主序，先存储a00，...，an0 直到存储 an0，...，ann。存储方式各有优劣，但对于高级语言来说，大部分时候不用考虑这些细节。
对于数组，一旦规定了它的维度和各维的长度，便可以为它分配存储空间，反之，只要给出一组下标，便可以求得相应数组元素的存储位置。
假设每个数据元素占L个存储单元，则二维数组A中任意一个元素aij的存储位置可由下式确定
LOC(i，j) = LOC（0，0）+（b2 x i + j）L
其中LOC（i，j）是aij的存储位置，LOC（0，0）是a00的存储位置，而二维数组A的起始位置，也称为基地址或基址，当然，这是二维数组，特殊到一半，便可得到n维数组的数据元存储位置的计算公式：
LOC(j1，j2，....，jn) = LOC（0，0，...，0）+Σni=1 ciji
其中cn=L，cij=bi x ci （1 i就是常数。由于计算各个元素存储位置的时间相等，所以存取数组中任意元素的时间也相等。称有这一特点的存储结构为随机存储结构。其实这样可以看出来，像使用C语言等编程语言的时候，使用数组其实在隐性的进行着下标运算以获得内存位置。
typedef struct{
ElemYype *base; //数组元素基址
int dim; //数组维数
int *bounds; //数组维界基址
int *constants; //数组映像函数常量基址
}Array;
多为数组的管理方式有点像上一章提到的页指针和行指针。
也许现在再看数组的ADT感觉十分多余，在C语言甚至C++的基础语法学完后感觉数组就没有什么研究的深度可讲。其实不然，如果脱离高级编程语言，使用低级语言比如汇编，这种存储的数据结构还是很有意义的。语言是在发展的，虽然越发展越是对底层的东西不可见，但也正是越底层的东西，越是不经常改变的。
矩阵的压缩存储
在数值分析中经常出现一些阶数很高的矩阵，同时在矩阵中有许多值相同的元素或者是零元素。有时为了节省内存空间，可以对这类矩阵进行压缩存储。所谓的压缩存储是指：为多个值相同的元素分配一个存储空间，对零元素不分配存储空间。
假若值相同的元素或者零元素在矩阵中的分布有一定的规律，则我们称此类矩阵为特殊矩阵，反之，称之为稀疏矩阵。
特殊矩阵
若n阶矩阵A中的元素满足下述性质：aij = aji （1 2个元素压缩到n(n + 1) / 2个元素的空间中，不失一般性，我们可以行序为主序的存储其下三角（包括对角线）中的元。
假设以一维数组sa[n(n +１)/2]作为n阶对称矩阵A的存储结构，则sa[k]和矩阵元aij之间存在着一一对应的关系。
k = i(i - 1)/2 + j - 1 （当i >=j时）
j(j - 1)/2 + i - 1 （当i ij，反之对所有k=0,1,2，....，n(n + 1)/2 - 1中，都能确定sa[k]中的元在矩阵中的位置（i，j）。由此，称sa[n(n +１)/2]作为n阶对称矩阵A的压缩存储。
不仅是对称矩阵，上下三角矩阵也可以如此压缩成一个一维数组。
稀疏矩阵
在实际应用中，我们还经常遇到另一类矩阵，其非零元较零元少，而且分布没有一定规律，我们称之为稀疏矩阵。
稀疏矩阵只是一个凭人们的直觉来了解的概念。假设m X n的矩阵中，有t个元素不为零，令δ=t/(m + n)，称δ为矩阵的稀疏因子，通常认为认为δ<= 0.05时称之为稀疏矩阵。
稀疏矩阵的特点是非零元少，那么，这也是压缩策略。
三元顺序表：直接存储行纵坐标及值，当然，为了各种方便，一般以行序或列序为主序顺序排列。
#define MAXSIZE 12500
typedef struct{
int i,j; //存储非零元的下标
ElemType e;
}Triple;
typedef struct{
Triple data[MAXSIZE + 1]; //非零元三元组表，data[0]未用
int mu,nu,tu; //矩阵的行数，列数，和非零元的个数
}TSMatrix;
三元组实现矩阵转置：
1.将矩阵的行列值（mu，nu）互相交换
2.将每个三元组中的i和j相互调换
3.重排三元组之间的次序便可实现矩阵的转置
开始的时候没感觉到什么，可是书中在强调第三步，明明就是一个二级排序嘛，有什么大不了，慢点的话用冒泡，快点用快排，二级排序嘛。
其实不然，如果是两个for进行冒泡，它的时间复杂度是什么？
for(col = 1;col <=M.nu;++col)
for(p = 1;p <= M.tu;++p)
if(...)
{
...
}
注意第二个for，他才是导致这个算法有待考虑的关键，因为这个算法不是单纯的O（长X宽），而是O（长X非零元个数），也就是说，这个算法，严重受到非零元个数影响。
如果不用三元组的方式，不压缩矩阵，时间复杂度明显是O（长X宽）即O（mu X nu），那么如果tu << mu X nu的话，这个算法还是可以考虑的但因为tu的取值范围是[0，mu X nu]，万一tu和mu X nu是一个数量级，那么时间复杂度（O（mu X nu^2））就是成倍的增加.
快速转置法提供了这样一种思路，如果已经确定了转换后的存储位置，那么在转置过程中便可以实现重排操作。但是问题来了，要如何确定转置后的位置？动态线性存储和二维数组不一样，我们无法以交换下标的方式来确定位置。
其实快速转置法是这样解决的，它先定义两个向量（说白了就是一维数组）num和cpot，来分别记录每一列中非零元素的个数和第一个非零元转置后在data中适当的位置。其实这个记录方式和数组相仿。数组也不过就是记录了同地址（cpot的作用）和数组长度（num的作用）。在数组中，对头地址加任何一个小于num的数，便可以访问以头地址为行头的这一维元素的任意元素。如果加的数大于num了呢？那就说明这一行完了，开始下一行（维）了。
for(col = 1;col <= M.nu;++col) num[col] = 0;
for(t = 1;t <= M.tu;++t) ++num[M.data[t].j]; //求每一列的非零元个数
//初始化
cpot[1] = 1;
//请第col列中第一个非零元在b.data中的序号
for(col = 2;col <= M.nu;++col) cpot[col] = cpot[col - 1] + num[col - 1];
for(p = 1;p <= M.tu;++p){
col = M.data[p].j;
q = cpot[col];
T.data[q].i = M.data[p].j;
T.data[q].j = M.data[p].i;
T.data[q].e = M.data[p].e;
++cpot[col];
}
其中++cpot[col];一定要注意，原位置在被占用之后，可使用位置向后推一。
虽然看起来又多了两个for循环，却是并列关系，所以实际上把时间复杂度降到了O（nu + tu）。
三元组顺序表又称有序的双下标法，他的特点是非零元在表中按行序处理的矩阵运算。然而，若需按行号存取某一行的非零元，则需从头开始进行查找。
行逻辑链接的顺序表（三元组的优化）
为了便于随机存取任意一行的非零元，则需知道每一行的第一个非零元在三元组表中的位置。为此，可使用类似上文提到的cpot向量，只不过cpot记录的是各列第一个非零元素。我们现在需要的是一个记录各行第一个非零元素在data的位置的向量。
那么便重新构建了这一个数据类型：
typedef struct{
Triple data[MAXSIZE + 1]; //非零元三元组表，data[0]未用
int rpos[MAXRC + 1］; //各行第一个非零元的位置表
int mu,nu,tu; //矩阵的行数，列数，和非零元的个数
}RLSMatrix;
因为可以方便的访问非零元，则这种数据结构可以更方便的进行矩阵乘法。
在计算机中，一个矩阵实际上就是一个二维数组。一个m行n列的矩阵与一个n行p列的矩阵可以相乘，得到的结果是一个m行p列的矩阵，其中的第i行第j列位置上的数为第一个矩阵第i行上的n个数与第二个矩阵第j列上的n个数对应相乘后所得的n个乘积之和。（摘自百度百科）
对于二维数组运算只需要：
for(i = 1;i <= m1;++i)
for(j = 1;j <= n2;++j){
Q[i][j] = 0;
for(k = 1;k <= n1;++k) Q[i][j] += M[i][k] * N[k][j];
}
但对于三元组表，这种算法显然是不合适的。
我们看点本质的东西，如何确定结果Q数组？
Q（i，j） = Σ（n1，k = 1）M（i，k） X N（k，j） （1 <= i <= m1，1 <= j <= n2）
在经典算法中，无论M（i，k）和N（k，j）是否为零，都需要进行一次运算，因此，在对稀疏矩阵运算的时候应该避免这种运算。换句话说，为求Q的值，只需要在M.data和N.data中找到相应的各对元素（即M.data中的j值和N.data中的i值相等的各对元素）相乘即可。
由此可得，如果想要矩阵相乘，需要从N矩阵中找到i值和M矩阵j相同的元素相乘。那么就需要一个确定某行的快速遍历。这样，rpos数组就有用武之地了。
又因为稀疏矩阵的乘积不一定为稀疏矩阵，而且，因为结果矩阵的每个元都是加和而成的，所以，即使相乘不为0，但加和可能为零，也就是说结果三元组可能存在零元，最后需要剔除。
那么算法可以精简为：
1.清零Q（i，j）
2.选取M中的元M（i，j）
3.找到N中i值与M的j值相等的元N（i，j）
4.相乘累加到Q（i，j）
5.压缩Q矩阵
伪代码如下：
Q初始化;
if(Q是非零矩阵){ //逐行求积
for(arow = 1;arow <= M.mu;++arow){ //处理M的每一行
ctemp[] = 0 //累加器清零
计算Q中第arow行的积并存入ctemp[]中;
将ctemp[]中非零元压缩存储到Q.data;
}
}
在书中还提供了比较详细的代码，感觉十分美妙，继续整理：
Status MultSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix &Q)
{
//求矩阵乘积Q = M X N,采用行逻辑链接表示
if(M.nu != N.mu) return ERROR;
//Q初始化
Q.mu = M.mu;
Q.nu = N.nu;
Q.tu = 0;
if(M.tu * N.tu != 0){ //Q是非零矩阵
for(arow = 1;arow MAXSIZE) return ERROR;
Qdata[Q.tu] = (arow,ccol,ctemp[ccol]);
}
}
}
return OK;
}
这个时间复杂度为O（M.mu X N.nu + M.tu X N.tu / N.mu）
一般在快速矩阵乘法中大都采用快速幂，能让时间复杂度压到O(n^2.81)。
3.十字链表
名字很高大上的样子，在集训队总结图的存储结构的时候我自学过一种叫十字链表的东西，它是正邻接表和逆邻接表的结合体，
这里的十字链表是不一样的，我学过的那个结构才真像十字结构，而这里的十字链表有点像网状结构，真想起来当时学链表的时候和王政他们开玩笑说写个链网来代替二维数组，其实这个就是类似实现，只不过里面保存的只是非零元素。
先说说为什么要用十字链表，对于三元组来说，有个问题很奇特，就是当矩阵加法的时候，可能会导致大量零元变成非零元，然后线性表里会增加很多元素，这样来说，顺序便会打乱。如果再次排序的话，时间复杂度不低。与其在末尾添加最后排序不如之间插入到应有的位置（插排），而对于插入，删除等能引起成员位置移动的操作，当然要选链式结构了，时间复杂度能降到一个数量级。
再说说为什么说这像个链网。每个元素是一个节点，保存有5个域（值），其中i，j，e来分别保存该非零元素的行坐标，列坐标和值，向右域right用以链接同一行中下一个非零元，向下域down用以链接同一列中下一个非零元。同一行的非零元通过right域链接成一条线性表，同一列非零元素通过down域链接成一条线性表。然后在矩阵中有chead和ehead数组来控制坐标头地址，与其说形成一个十字结构不如说是一个网状结构（但是只是考虑单一结点，还是是个十字的）。
typedef struct OLNode{
int i,j;
ElemType e;
struct OLNode *right,*down;
}OLNode;
typedef struct{
Olink *rhead,*chead;
int mu,nu,tu;
}CrossList;
对于十字链表的使用，比链表也难不到哪去，一定要有模型的概念，注意细节就好了。
最后说一下对于十字链表处理矩阵加法。
其实不难，就是繁琐，按行或列处理，一个一个相加，注意一共四种情况：
1.A为不为零，B不为零，加和不为零
2.A为零，B不为零
3.A不为零，B为零
4.1.A为不为零，B不为零，加和为零
处理好这四种情况的对链结的增减，矩阵加法也不过如此。
虽然矩阵在这一章属于数组范围，但是矩阵运算着实不简单，之所以不简单因为离不开线性表的灵活运用。
