第5章
数组和稀疏矩阵




数组可以看成线性表的推广，二维数组称为矩阵，为了节省空间,可以对一些特殊矩阵和稀疏矩阵采用压缩存储方法。
本章的学习要点如下： 
(1) 数组和一般线性表的差异。
(2) 数组的存储结构和元素地址计算方法。
(3) 各种特殊矩阵（如对称矩阵、上三角矩阵、下三角矩阵和对角矩阵）的压缩存储方法。
(4) 稀疏矩阵的各种存储结构以及基本运算实现算法。
(5) 灵活运用数组解决一些较复杂的应用问题。
5.1数组
5.1.1数组的基本概念



视频讲解


几乎所有的计算机语言都提供了数组类型，但直接将数组看成“连续的存储单元集合”是片面的，数组也分为逻辑结构和存储结构，尽管在计算机语言中实现数组通常采用连续的存储单元集合，但并不能说数组只能这样实现。
从逻辑结构上看，数组是二元组(idx，value)的集合，对每个idx，都有一个value值与之对应，idx称为下标，可以由一个整数、两个整数或多个整数构成，下标含有d(d≥1)个整数称维数是d。数组按维数分为一维、二维和多维数组。
一维数组A是n(n>1)个相同类型元素a0，a1，a2,…，an-1构成的有限序列，其逻辑表示为A=(a0，a1，a2,…，an-1)，其中，A是数组名，ai(0≤i≤n-1)是数组A中序号为i的元素。
一个二维数组可以看作每个数据元素都是相同类型的一维数组的一维数组。以此类推，多维数组可以看作一个这样的线性表： 其中的每个元素又是一个线性表。


图5.1一个二维数组

也可以这样看，一个d维数组中含有b1×b2×…×bd(假设第i维的大小为bi)个元素，每个元素受到d个关系的约束，且这d个关系都是线性关系。当d=1时，数组就退化为定长的线性表; 当d>1时，d维数组可以看成线性表的推广。例如，如图5.1所示的二维数组的逻辑关系用二元组表示如下： 

B=(D，R)

R={r1，r2}

r1={<1，2>，<2，3>，<3，4>，<5，6>，<6，7>，<7，8>，<9，10>，<10，11>，<11，12>}

r2={<1，5>，<5，9>，<2，6>，<6，10>，<3，7>，<7，11>，<4，8>，<8，12>}



其中含有12个元素，这些元素之间有两种关系，r1表示行关系，r2表示列关系，r1和r2均为线性关系。
一般地，数组具有以下特点： 
①  数组中的各元素都具有统一的数据类型。
②  d(d≥1)维数组中的非边界元素具有d个前驱元素和d个后继元素。
③  数组的维数确定后，数据元素个数与元素之间的关系不再发生改变，特别适合于顺序存储。
④  每个有意义的下标都存在一个与其相对应的数组元素值。
d维数组抽象数据类型的定义如下： 

ADT Array

{

数据对象： 

D={数组中的所有元素}

数据关系： 

R={r1，r2，…，rd}

ri={元素之间第i维的线性关系 | i=1，2,…，d}

基本运算： 

Value(A，i1，i2，…，id)： A是已存在的d维数组，其运算结果是返回A［i1，i2，…，id］值。

Assign(A，e，i1，i2，…，id)： A是已存在的d维数组，其运算结果是置A［i1，i2，…，id］=e。

…

}

数组的主要操作是存取元素值，如图5.2所示为一维数组的存取操作，由于数组没有插入和删除操作，所以数组通常采用顺序存储方式实现。


图5.2一维数组的基本操作



5.1.2数组的存储结构
1.  一维数组



视频讲解


一维数组的所有元素依逻辑次序存放在一片连续的内存存储单元中，其起始地址为元素a0的地址，即LOC(a0)。假设每个数据元素占用k个存储单元，则元素ai（0≤i<n）的存储地址LOC(ai)如下： 

LOC(ai)=LOC(a0)+i×k


该式说明一维数组中任一元素的存储地址可直接计算得到，即一维数组中的任一元素可直接存取，正因如此，一维数组具有随机存取特性。
C++中一维数组的定义方式如下： 

T a［M］;//M为常量，T为数组元素类型

当然也可以使用vector<T>容器作为一维动态数组。
2. d维数组
对于d（d≥2）维数组，必须约定其元素的存放次序（即存储方案），这是因为存储单元是一维的（计算机的存储结构是线性的），而数组是d维的。通常d维数组的存储方案有按行优先和按列优先两种。
下面以m行n列的二维数组Am×n=(ai，j)为例进行讨论。
二维数组A按行优先存储的形式如图5.3所示，假设每个元素占用k个存储单元，用LOC(a0,0)表示首元素a0,0的存储地址，则元素ai，j（0≤i，j<n）的存储地址如下： 

LOC(ai,j)=LOC(a0,0)+(i×n+j)×k



图5.3按行优先存储


二维数组A按列优先存储的形式如图5.4所示，在前面假设的情况下，元素ai，j的存储地址如下： 

LOC(ai,j)=LOC(a0,0)+(j×m+i)×k

前面均假设二维数组的行、列下界为0。更一般的情况是二维数组行下界是c1、行上界是d1，列下界是c2、列上界是d2，即为数组A［c1..d1，c2..d2］A［c1..d1，c2..d2］表示数组A的行号从c1到c2，列号从d1到d2，通常数组下标从0开始，所以A［m］数组可以表示为A［0..m-1］，A［m］［n］或A［m,n］数组可以表示为A［0..m-1,0..n-1］。，则该数组按行优先存储时有： 

LOC(ai，j)=LOC(ac1，c2)+［(i-c1)×(d2-c2+1)+(j-c2)］×k

按列优先存储时有： 

LOC(ai，j)=LOC(ac1，c2)+［(j-c2)×(d1-c1+1)+(i-c1)］×k

综上所述，从二维数组的元素地址计算公式LOC(ai，j)看出，一旦数组元素的下标和元素类型确定，对应元素的存储地址就可以直接计算出来。也就是说，与一维数组相同，二维数组也具有随机存取特性。这样的推导公式和结论可推广至三维甚至更高维数组中。
C++中二维数组的定义方式如下： 

T a［M］［N］;//M、N为常量，T为数组元素类型

当然也可以使用vector<vector<T>>容器作为二维动态数组。


图5.4按列优先存储


【例5.1】设有二维数组a［1..50，1..80］，其a［1］［1］元素的地址为2000，每个元素占两个存储单元，若按行优先存储，则元素a［45］［68］的存储地址为多少?若按列优先存储，则元素a［45］［68］的存储地址为多少？
解： 在按行优先存储时，元素a［45］［68］前面有1~44行，每行80个元素； 计44×80个元素； 在第45行中，元素a［45］［68］前面有a［45］［1..67］计67个元素，这样元素a［45］［68］前面存储的元素个数=44×80+67，所以LOC(a［45］［68］)=2000+(44×80+67)×2=9174。
在按列优先存储时，元素a［45］［68］前面有1~67列，每列50个元素，计67×50个元素； 在第68列中，元素a［45］［68］前面有a［1..44］［68］计44个元素，这样元素a［45］［68］前面存储的元素个数=67×50+44，所以LOC(a［45］［68］)=2000+(67×50+44)×2=8788。
在C++语言中二维及以上维的数组就是按行优先存储的，当在程序中采用数组存放大量的数据时，这些数据存放在内存中。当CPU读数组中的元素时并不是立即访问内存，而是先访问Cache(高速缓存，其速度比访问内存快得多)，如果访问的数据在Cache中便直接取相应的数据(称为命中)，如果访问的数据不在Cache中才访问内存，并将访问数据所在的一个页块调入Cache，如图5.5所示，这称为程序局部性原理。


图5.5CPU存取数据的方式


显然，如果程序中连续读取的数据在内存中是相邻存放的，那么Cache命中率高，程序执行速度快； 反之，Cache命中率低，程序执行速度慢。好的程序员可以利用程序局部性原理尽可能提高程序的性能。例如，有以下两个功能一模一样的程序： 

//程序A

int a［1000］［50］［8000］;

int main()

{

for (int i=0;i<1000;i++)

for (int j=0;j<50;j++)

for (int k=0;k<8000;k++)

a［i］［j］［k］=i+j+k;

return 0;

}

//程序B

int a［1000］［50］［8000］;

int main()

{

for (int k=0;k<8000;k++)

for (int j=0;j<50;j++)

for (int i=0;i<1000;i++)

a［i］［j］［k］=i+j+k;

return 0;

}

程序A的执行时间为1.597秒，程序B的执行时间为17.83秒，相差10多倍。原因是数组a按行优先存放，而程序A恰好也是按行优先访问a中元素的，所以性能高； 程序B则是按列优先访问a中元素的，所以性能低。
5.1.3数组的应用
由于数组的使用简单、方便，特别是具有随机存取特性，因此在编程中数组被广泛地使用。使用数组的目的一方面是为了存储大量的数据类型相同的数据，避免重复性操作； 另一方面用于模拟现实世界，例如顺序表就是采用数组模拟线性表。
下面的两个实战题分别是一维数组和二维数组的应用，前一个是有关前缀和，后一个是有关矩阵快速幂，前缀和与矩阵快速幂是高级编程中常用的技术。



【实战5.1】POJ2189——最多围栏个数
时间限制： 1000ms； 内存限制： 65536KB。


视频讲解


问题描述： 一个条形牧场用p（1≤p≤1000）个柱子（编号分别为1到p）分隔成等间距的围栏，每头牛只能在围栏中放牧，现有n（1≤n≤1000）头牛在放牧。请求出数量不超过c（0≤c≤1000）头牛的最大连续区域的围栏个数。

输入格式： 第1行是3个整数n、p和c。第2行到第n+1行，每行包含一个整数x，取值范围为1～p-1，指定一头牛在柱子x和柱子x+1的围栏中放牧。注意一个围栏中允许放牧多头牛。
输出格式： 在第1行中输出一个整数，表示最多有c头牛的最大连续区域的围栏个数。




【实战5.2】POJ3070——矩阵快速幂求Fibonacci数列
时间限制： 1000ms; 内存限制： 65536KB。


视频讲解


问题描述： Fibonacci数列是F0=0，F1=1，Fn=Fn-1+Fn-2（n≥2）。例如，前10项Fibonacci数列是0，1，1，2，3，5，8，13，21，34。
Fibonacci数列的另外一种写法是： 
Fn+1Fn
FnFn-1=11
10n=11
1011
10…11
10n次
给定一个整数n，请求出Fn的最后4位数字。
输入格式： 输入包含多个测试用例，每个测试用例由单个包含整数n（0≤n≤1000000000）的行构成，以n=-1表示结束。
输出格式： 对于每个测试用例，输出一行包含Fn的最后4位数字，如果均为0则输出'0'，否则忽略前导0（也就是输出Fn mod 10000）。




视频讲解



5.2特殊矩阵的压缩存储 
二维数组也称为矩阵。对于一个m行n列的矩阵，当m=n时称为方阵，方阵的元素可以分为三部分，即上三角部分、主对角线部分和下三角部分，如图5.6所示。
所谓特殊矩阵，是指非零元素或常量元素的分布有一定规律的矩阵。为了节省存储空间，可以利用特殊矩阵的规律对它们进行压缩存储，例如让多个相同值的元素共享同一个存储单元等。这里主要讨论对称矩阵、三角矩阵和对角矩阵，它们都是方阵。


图5.6一个方阵的三部分


5.2.1对称矩阵的压缩存储

若一个n阶方阵A的元素满足ai，j=aj，i(0≤i，j≤n-1)，则称其为n阶对称矩阵。
如果直接采用二维数组存储对称矩阵，占用的内存空间为n2个元素大小。由于对称矩阵的元素关于主对角线对称，因此在存储时可只存储其上三角和主对角线部分的元素，或者只存储其下三角和主对角线部分的元素，使得对称的元素共享同一存储空间，这样就可以将n2个元素压缩存储到n(n+1)/2个元素的空间中。不失一般性，在按行优先存储时仅存储其下三角和主对角线部分的元素，如图5.7所示。


图5.7对称矩阵的压缩存储



采用一维数组B={bk}作为n阶对称矩阵A的压缩存储结构，在B中只存储对称矩阵A的下三角+主对角线部分的元素ai，j（i≥j），这样B中的元素个数为n(n+1)/2。
① 将A中下三角+主对角线部分的元素ai，j（i≥j）存储在B数组的bk元素中。那么k和i、j之间是什么关系呢？
对于元素ai，j，求出它前面共存储的元素个数。不包括第i行，它前面共有i行（行下标为0～i-1，第0行有1个元素，第1行有2个元素，…，第i-1行有i个元素），则这i行有1+2+…+i=i(i+1)/2个元素。在第i行中，元素ai，j前面的元素是ai,0～ai,j-1，有j个元素，这样元素ai，j的前面共有i(i+1)/2+j个元素，所以有k=i(i+1)/2+j。也就是说，A中下三角+主对角线部分的元素ai，j存放在B中序号为i(i+1)/2+j的元素中。
② 对于A中上三角部分的元素ai，j（i<j），其值等于aj，i，而aj，i元素在B中的存储序号为j(j+1)/2+i。
归纳起来，A中任一元素ai，j和B中元素bk之间存在如下对应关系： 
k=
i（i+1）/2+ji≥j


j（j+1）/2+ii<j

上述关系用k=f(i，j)表示，该函数是对称矩阵压缩存储的关键。所谓压缩存储，就是对于n阶对称矩阵A，采用一维数组B存储（几乎节省一半空间），但需要提供类似A［i］［j］元素的操作，实现过程如下： 
① 存元素即执行A［i］［j］=x,求出k=f(i，j)，再执行B［k］=x。
② 取元素即执行y=A［i］［j］,求出k=f(i，j)，再执行y=B［k］。
说明： 在计算对称矩阵的压缩存储关系函数k=f(i，j)时需要考虑几点，压缩存储的元素是上三角+主对角线部分还是下三角+主对角线部分？存储的元素是按行优先还是按列优先？矩阵的下标是从1开始还是从0开始？
【例5.2】有两个n阶整型对称矩阵A、B。编写一个程序完成以下功能： 
（1） 将A、B均采用按行优先顺序存放其下三角和主对角线部分元素的压缩存储方式，A、B的压缩结果存放在一维数组a和b中。
（2） 通过a和b实现求A、B的乘积运算，结果存放在二维数组C中。
要求采用相关数据进行测试。
解： 对于两个n阶对称矩阵A、B，在求乘积C数组时，计算公式如下。
C［i］［j］=∑n-1k=0A［i］［k］×B［k］［j］
由于A、B均采用a、b压缩存储，设计getk(i，j)算法由i、j求压缩存储中的下标k。在矩阵乘法中，求出k1=getk(i，k)，k2=getk(k，j)，在求C［i］［j］时A［i］［k］用a［k1］替代，B［k］［j］用b［k2］替代即可。
对应的程序如下： 

#include<iostream>

#include<string>

using namespace std;

const int MAX=10;//最大维长度

void disp(int A［MAX］［MAX］,int n)//输出n阶二维数组A

{

for (int i=0;i<n;i++)

{

for (int j=0;j<n;j++)

printf("%3d",A［i］［j］);

printf("＼n");

}

}

void compression(int A［MAX］［MAX］,int n,int a［］)//将A压缩存储到a中

{

for (int i=0;i<n;i++)

for (int j=0;j<=i;j++)

{

int k=i*(i+1)/2+j;

a［k］=A［i］［j］;

}

}

int getk(int i,int j)//由i、j求压缩存储中的下标k

{

if (i>=j)

return i*(i+1)/2+j;

else

return j*(j+1)/2+i;

}

void Mult(int a［］,int b［］,int C［MAX］［MAX］,int n)//矩阵乘法

{

for (int i=0;i<n;i++)

for (int j=0;j<n;j++)

{

int s=0;

for (int k=0;k<n;k++)

{

int k1=getk(i,k);

int k2=getk(k,j);

s+=a［k1］*b［k2］;

}

C［i］［j］=s;

}

}

int main()

{

int n=3;

int m=n*(n+1)/2;

int A［MAX］［MAX］={{1,2,3},{2,4,5},{3,5,6}};

int B［MAX］［MAX］={{2,1,3},{1,5,2},{3,2,4}};

int C［MAX］［MAX］;

int* a=new int［m］;

int* b=new int［m］;

printf("A:＼n"); disp(A,n);

printf("A压缩存储到a中＼n");

compression(A,n,a);

printf("a: ");

for (int i=0;i<m;i++)

printf("%3d",a［i］);

printf("＼n");

printf("B:＼n"); disp(B,n);

printf("B压缩存储到b中＼n");

compression(B,n,b);

printf("b: ");

for (int i=0;i<m;i++)

printf("%3d",b［i］);

printf("＼n");

printf("C=A*B＼n");

Mult(a,b,C,n);

printf("C:＼n"); disp(C,n);

return 0;

}



上述程序的执行结果如下： 

A:

123

245

356

A压缩存储到a中

a: 124356

B:

213

152

324

B压缩存储到b中

b: 215324

C=A*B

C:

13 17 19

23 32 34

29 40 43

5.2.2三角矩阵的压缩存储


视频讲解


有些非对称的矩阵也可借用上述方法存储，例如n阶下(上)三角矩阵。所谓n阶下(上)三角矩阵，是指矩阵的上(下)三角部分(不包括主对角线)中的元素均为常数c的n阶方阵。
n阶三角矩阵A采用一维数组B={bk}压缩存储，常量c仅存放一次，这样B中的元素个数为n(n+1)/2+1。A中任一元素ai，j和B中元素bk之间存在着如下对应关系。
上三角矩阵： 
k=i（2n-i+1）/2+j-ii≤j


n（n+1）/2i>j
下三角矩阵： 
k=i（i+1）/2+ji≥j


n（n+1）/2i<j
其中，B的最后元素bn(n+1)/2中存放常数c。
5.2.3对角矩阵的压缩存储


视频讲解


若一个n阶方阵A满足其所有非零元素都集中在以主对角线为中心的带状区域中，其他元素均为0，则称其为n阶对角矩阵。其主对角线上、下方各有b条次对角线，称b为矩阵半带宽，(2b+1)为矩阵的带宽。对于半带宽为b(0≤b≤(n-1)/2)的对角矩阵，其|i-j|≤b的元素ai，j不为零，其余元素为零。图5.8所示为半带宽为b的对角矩阵示意图。


图5.8半带宽为b的

对角矩阵

对于b=1的三对角矩阵A，只存储其非零元素，并按行优先存储到一维数组B中，将A的非零元素ai，j存储到B的元素bk中，k的计算过程如下： 
①  当i=0时为第0行，共2个元素。
②  当i>0时，第0行~第i-1行共2+3(i-1)个元素。
③  对于非零元素ai，j，第i行最多3个元素，该行的首非零元素为ai，i-1(另外两个元素是ai，i和ai，i+1)，即该行中元素ai，j前面存储的非零元素个数为j-(i-1)=j-i+1。
所以,非零元素ai，j前面压缩存储的元素总个数=2+3(i-1)+j-i+1=2i+j，即k=2i+j。
以上讨论的对称矩阵、三角矩阵、对角矩阵的压缩存储方法是把有一定分布规律的值相同的元素(包括0)压缩存储到一个存储空间中。这样的压缩存储只需在算法中按公式作一映射即可实现矩阵元素的随机存取。
5.3稀疏矩阵
当一个阶数较大的矩阵中的非零元素个数s相对于矩阵元素的总个数t非常小时，即st时，称该矩阵为稀疏矩阵。例如一个100×100的矩阵，若其中只有100个非零元素，就可称其为稀疏矩阵。
抽象数据类型稀疏矩阵与抽象数据类型d(d=2)维数组的定义相似，这里不再介绍。
5.3.1稀疏矩阵的三元组表示


视频讲解


由于稀疏矩阵中的非零元素个数很少，显然其压缩存储方法就是只存储非零元素。不同于前面介绍的各种特殊矩阵，稀疏矩阵中非零元素的分布没有规律(或者说随机分布)，所以在存储非零元素时除了存储元素值还需存储对应的行、列下标。这样稀疏矩阵中的每一个非零元素需由一个三元组(i，j，ai，j)表示，稀疏矩阵中的所有非零元素构成一个三元组线性表。
如图5.9所示为一个6×7阶稀疏矩阵A(为图示方便，所取的行、列数都很小)及其对应的三元组表示。从中看到，这里的稀疏矩阵三元组表示是一种顺序存储结构。


图5.9一个稀疏矩阵A及其对应的三元组表示


三元组表示中每个元素的类型定义如下： 

struct TupElem//单个三元组元素的类型

{

int r;//行号

int c;//列号

int d;//元素值

TupElem() {}//构造函数

TupElem(int r1,int c1,int d1)//重载构造函数

{

r=r1;

c=c1;

d=d1;

}

};


设计稀疏矩阵三元组存储结构类TupClass如下： 

class TupClass//三元组存储结构类

{

int rows;//行数

int cols;//列数

int nums;//非零元素个数

TupElem* data;//稀疏矩阵对应的三元组顺序表

//基本运算算法

};


TupClass类中包含如下基本运算算法。
①  CreateTup(A，m，n)： 由m行n列的稀疏矩阵A创建其三元组表示。
②  Setvalue(i，j，x)： 利用三元组给稀疏矩阵的元素赋值,即执行A［i］［j］=x(x为非零值)。
③  Getvalue(i，j，x)： 利用三元组取稀疏矩阵的元素值即执行x=A［i］［j］。
④  DispTup()： 输出稀疏矩阵的三元组表示。
其中，data列表用于存放稀疏矩阵中的所有非零元素，通常按行优先顺序排列。这种有序性可简化大多数稀疏矩阵运算算法。
以Setvalue(i，j，x)算法为例，其功能是将A［i］［j］赋值为一个非零值。实现过程是，第一步检查参数的正确性，当参数错误时返回false。当参数正确时，第二步是查找，先按行号找到第i行的第一个非零元素，然后在第i行中查找第j列的元素(按有序性第i行的所有非零元素按列号顺序存放)。若找到了该元素，说明A［i］［j］本身是一个非零元素，只需要将其值替换为新值x，否则说明A［i］［j］是一个零元素，需要修改为非零元素，此时在三元组中执行第三步，即插入操作，先将该位置后面的元素向后移动一个位置，然后在该位置存放x元素。对应的算法如下： 

bool Setvalue(int i,int j,int x)//三元组元素赋值:A［i］［j］=x

{

if (i<0 || i>=rows || j<0 || j>=cols)

return false;//参数错误时返回false

int k=0,k1;

while (k<nums && i>data［k］.r)

k++;//查找第i行的第一个非零元素

while (k<nums && i==data［k］.r && j>data［k］.c)

k++;//在第i行中查找第j列的元素

if (data［k］.r==i&& data［k］.c==j)//找到了这样的元素

data［k］.d=x;

else//不存在这样的元素时插入一个元素

{

for (k1=nums-1; k1>=k;k1--)//后移元素以便插入

{

data［k1+1］.r=data［k1］.r;

data［k1+1］.c=data［k1］.c;

data［k1+1］.d=data［k1］.d;

}

data［k］.r=i; data［k］.c=j; data［k］.d=x;

nums++;

}

return true;//赋值成功时返回true

}

说明： 若稀疏矩阵采用一个二维数组存储，此时具有随机存取特性； 若稀疏矩阵采用一个三元组顺序表存储，则不再具有随机存取特性。
5.3.2稀疏矩阵的十字链表表示


视频讲解


十字链表是稀疏矩阵的一种链式存储结构。
对于一个m×n的稀疏矩阵，每个非零元素用一个结点表示，该结点中存放该零元素的行号、列号和元素值。同一行中的所有非零元素结点链接成一个带行头结点的行循环单链表，同一列中的所有非零元素结点链接成一个带列头结点的列循环单链表。之所以采用循环单链表，是因为矩阵运算中经常是一行(列)操作完后进行下一行(列)操作，最后一行(列)操作完后进行首行(列)操作。
这样对稀疏矩阵的每个非零元素结点来说，它既是某个行链表中的一个结点，同时又是某个列链表中的一个结点，每个非零元素就好比在一个十字路口，由此称作十字链表。
每个非零元素结点的类型设计成如图5.10(a)所示的结构，其中i、j、value分别代表非零元素所在的行号、列号和相应的元素值； down和right分别称为向下指针和向右指针，分别用来链接同列中和同行中的下一个非零元素结点。这样行循环单链表个数为m(每一行对应一个行循环单链表)，列循环单链表个数为n(每一列对应一个列循环单链表)，那么行列头结点的个数就是m+n。实际上，行头结点与列头结点是共享的，即h［i］表示第i行循环单链表的头结点，同时也是第i列循环单链表的头结点，这里0≤i<MAX{m，n}，即行列头结点的个数是MAX{m，n}，所有行列头结点的类型与非零元素结点的类型相同。


图5.10十字链表结点结构


另外，将所有行列头结点再链接起来构成一个带头结点的循环单链表，这个头结点称为总头结点，即hm，通过hm来标识整个十字链表。总头结点的类型设计成如图5.10(b)所示的结构(之所以这样设计，是为了与非零元素结点的类型一致，这样在整个十字链表中采用指针遍历所有结点时更方便)，它的link域指向第一个行列头结点，其i、j域分别存放稀疏矩阵的行数m和列数n，而down和right域没有作用。
从中看出，在m×n的稀疏矩阵的十字链表存储结构中有m个行循环单链表、n个列循环单链表，另外有一个行列头结点构成的循环单链表，总的循环单链表个数是m+n+1，总的头结点个数是MAX{m，n}+1。
设稀疏矩阵如下： 
B3×4=1002
0030
0004
对应的十字链表如图5.11所示。为图示清楚，把每个行列头结点分别画成两个，实际上行、列值相同的头结点只有一个。


图5.11一个稀疏矩阵的十字链表


十字链表结点类型MatNode定义如下： 

template <typename T>

struct MatNode //十字链表结点类型

{

int row;//行号或者行数

int col;//列号或者列数

struct mtxn* right,*down;//行、列指针

union

{

T value;//非零元素值

struct mtxn* link;//指向下一个头结点

} tag;

};

有关稀疏矩阵采用十字链表表示时的相关运算算法与三元组表示的类似，但更复杂，这里不再讨论。



【实战5.3】HDU4920——稀疏矩阵乘法


视频讲解



时间限制： 2000ms; 内存限制： 131072KB。
问题描述： 给定两个n×n矩阵a和b，求它们的积，结果矩阵中每个元素值模3。
输入格式： 输入包含多个测试用例，每个测试用例的第一行为n(1≤n≤800)； 接下来的n行每行n个整数，表示矩阵a，第i行的第j个整数为aij； 类似地，再接下来的n行为矩阵b(0≤aij，bij≤109)。
输出格式： 对于每个测试用例，输出n行，每行n个整数表示a×b的结果。



5.4练习题
5.4.1问答题

1.  为什么说数组是线性表的推广或扩展，而不说数组就是一种线性表？
2.  为什么数组一般不使用链式存储结构？
3.  如果某个一维整数数组A的元素个数n很大，存在大量重复的元素，且所有值相同的元素紧跟在一起，请设计一种压缩存储方式使得存储空间更节省。
4.  有一个5×6的二维数组a，起始元素a［1］［1］的地址是1000，每个元素的长度为4。
(1) 采用按行优先存储，给出元素a［4］［5］的地址。
(2) 采用按列优先存储，给出元素a［4］［5］的地址。
5.  一个n阶对称矩阵存入内存，在采用压缩存储和非压缩存储时占用的内存空间分别是多少？
6.  一个6阶对称矩阵A中主对角线以上部分的元素已按列优先顺序存放于一维数组B中，主对角线上的元素均为0。根据以下B的内容画出A矩阵。








01234567891011121314




B： 250340014263012


7.  设A［0..9,0..9］是一个10阶对称矩阵，采用按行优先将其下三角+主对角线部分的元素压缩存储到一维数组B中。已知每个元素占用两个存储单元，其第一个元素A［0］［0］的存储位置为1000，求以下问题的计算过程及结果： 
(1) 给出A［4］［5］的存储位置。
(2) 给出存储位置为1080的元素的下标。
8.  设n阶下三角矩阵A［0..n-1,0..n-1］已压缩存储到一维数组B［1..m］中，若按行为主序存储，则A［i］［j］(i≥j)元素对应的B中存储位置为多少?给出推导过程。
9.  用十字链表表示一个有k个非零元素的m×n的稀疏矩阵，则其总的结点数为多少？
10.  特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取特性？为什么？
5.4.2算法设计题
1.  设计一个算法，将含有n个整数元素的数组a［0..n-1］循环右移m位，要求算法的空间复杂度为O(1)。
2.  有一个含有n个整数元素的数组a［0..n-1］，设计一个算法求其中最后一个最小元素的下标。
3.  设a是一个含有n个元素的double型数组，b是一个含有n个元素的整数数组，其值介于0~n-1，且所有元素不相同。现设计一个算法，要求按b的内容调整a中元素的顺序，例如当b［2］=11时，要求将a［11］元素调整到a［2］中。如n=5，a［］={1,2,3,4,5}，b［］={2,3,4,1,0}，执行本算法后a［］={3,4,5,1,2}。
4.  设计一个算法，实现m行n列的二维数组a的就地转置，当m≠n时返回false，否则返回true。
5.  设计一个算法，求一个m行n列的二维整型数组a的左上角－右下角和右上角－左下角两条主对角线元素之和，当m≠n时返回false，否则返回true。
5.5上机实验题
5.5.1基础实验题


1.  编写一个实验程序，给定一个m行n列的二维数组a，每个元素的长度k，数组的起始地址d，该数组按行优先还是按列优先存储，数组的初始下标c1(假设a的行、列初始下标均为c1)，求元素a［i］［j］的地址，并用相关数据进行测试。
2.  编写一个实验程序，给定一个n阶对称矩阵A，采用压缩存储存储在一维数组B中，指出存储下三角+主对角部分的元素还是上三角+主对角部分的元素，按行优先还是按列优先，A的初始下标c1和B的初始下标c2，求元素a［i］［j］在B中的地址k，并用相关数据进行测试。
3.  编写一个实验程序，假设稀疏矩阵采用三元组压缩存储，设计相关基本运算算法，并用相关数据进行测试。
5.5.2应用实验题
1.  给定n(n≥1)个整数的序列用整型数组a存储，要求求出其中的最大连续子序列之和。例如序列(-2，11，-4，13，-5，-2)的最大连续子序列和为20，序列(-6，2，4，-7，5，3，2，-1，6，-9，10，-2)的最大连续子序列和为16。分析算法的时间复杂度。
2.  求马鞍点问题。如果矩阵a中存在一个元素a［i］［j］满足条件“a［i］［j］是第i行中值最小的元素，且又是第j列中值最大的元素”，则称之为该矩阵的一个马鞍点。设计一个程序，计算出m×n的矩阵a的所有马鞍点。
3.  对称矩阵压缩存储的恢复。一个n阶对称矩阵A采用一维数组a压缩存储，压缩方式是按行优先顺序存放A的下三角和主对角线部分的各元素。完成以下功能： 

(1) 由A产生压缩存储a。
(2) 由b恢复对称矩阵C。
通过相关数据进行测试。
5.6在线编程题
1.  LeetCode48——旋转图像
2.  HDU1575——方阵A的迹
3.  HDU1559——最大子矩阵
4.  POJ3213——矩阵乘法问题
5.  POJ3292——求H半素数个数