第5章〓数组和稀疏矩阵
数组是由相同性质的数据元素组成的，可以看成是线性表的推广。本章介绍数组的概念、几种特殊矩阵的压缩存储和稀疏矩阵的相关算法。
5.1数组
5.1.1数组的定义
一维数组是n(n>1)个相同性质的数据元素a1，a2，…，an构成的有限序列，它本身就是一个线性表。二维数组可以看成是这样的一个线性表，它的每个数据元素也是一个线性表。例如，如图5.1所示的二维数组A以m行n列的矩阵形式表示，它可以看成是一个线性表：
A=(A1，A2，…，Ai，…，Am)
其中每个数据元素Ai也是一个线性表：
Ai=(ai,1，ai,2，…，ai,n)
Am×n=a1,1a1,2…a1,na2,1a2,2…a2,n
…………
am,1am,2…am,n
图5.1二维数组的逻辑结构表示
对于d(d>1)维数组，数据元素之间有d个关系(如二维数组中数据元素之间有行和列两个关系)，但每个关系仍是线性关系。例如，如图5.1所示的二维数组A可以采用二元组形式化描述如下。
A=(D，R)
D={a1，1，a1，2，…，a1，n，…，am，1，…，am，n}
R={Row，Col}
Row={<a1，1，a1，2>，<a1，2，a1，3>，…，<a1，n-1，a1，n>，<a2，1，a2，2>，<a2，2，a2，3>，…，
<a2，n-1，a2，n>，…，<am，1，am，2>，<am，2，am，3>，…，<am，n-1，am，n>}
Col={<a1，1，a2，1>，<a2，1，a3，1>，…，<am-1，1，am-2，1>，<a1，2，a2，2>，<a2，2，a3，2>，…，
<am-1，2，am，2>，…，<a1，n，a2，n>，<a2，n，a3，n>，…，<am-1，n，am，n>}
其中，Row是行关系，Col是列关系。这种规则可以推广到三维及以上的数组。
通常，数组的基本运算主要有存取元素值。
几乎所有的高级程序设计语言都实现了数组数据结构，称为数组类型。在C/C++语言中，数组类型具有如下特点。
(1) 一个数组中所有元素具有相同的数据类型。
(2) 数组一旦被定义，它的维数和每维大小就不再改变。
(3) 数组中每个元素对应唯一的下标，可以通过该下标对元素进行存取操作。
5.1.2数组的存储结构
由于数组一般不做插入或删除操作，也就是说，一旦建立了数组，其数据元素个数和元素之间的关系就不再发生变动，所以数组通常采用顺序存储结构。
由于内存的存储单元是一维结构，而数组是多维的，则用一组连续存储单元存放数组的元素就有个次序约定问题。
以二维数组为例，在C/C++语言中，由于数组下标从0开始，所以除特别指出外，后面的数组表示均统一为下标从0开始。
二维数组的存储次序有按行优先和按列优先两种方式，按行优先存储的形式如图5.2所示，假设每个元素占k个存储单元，LOC(a0,0)表示a0,0元素的存储地址，对于元素ai,j，其存储地址为：
LOC(ai,j)=LOC(a0,0)+(i×n+j)×k每个元素占k个存储单元
在第i行中，ai,j前面j个元素
ai,j前面有0～i-1共i行，每行n个元素，共有i×n个元素
图5.2按行优先存储
按列优先存储的形式如图5.3所示，对于元素ai,j，其存储地址为：
LOC(ai,j)=LOC(a0,0)+(j×m+i)×k每个元素占k个存储单元
在第j列中，ai,j前面i个元素
ai,j前面有0～j-1共j列，每列m个元素，共有j×m个元素
图5.3按列优先存储
【例5.1】对于二维数组A［0..2］［0..5］，当按行优先存储时，元素A［2］［3］是第几个元素？当按列优先存储时，元素A［2］［4］是第几个元素？
这里m=3，n=6，当按行优先存储时，每行6个元素，元素A［2］［3］的前面有两行计12个元素，在第2行中前面有三个元素，所以元素A［2］［3］是12+3+1=16个元素。
当按列优先存储时，每列3个元素，元素A［2］［4］的前面有4列计12个元素，在第4列中前面有两个元素，所以元素A［2］［4］是12+2+1=15个元素。
5.1.3数组的算法设计示例
本节通过两个示例说明数组算法设计。
【例5.2】设计一个算法，实现一个m×n的整型数组A的转置运算。
对于一个m×n的数组Am×n，其转置矩阵是一个n×m的矩阵Bn×m，且B［i］［j］=A［j］［i］，0≤i<m，0≤j<n，对应的算法如下。
void TransMat(int A［ ］［MAX］, int B［ ］［MAX］,int m,int n)
{int i,j;
for (i=0;i<m;i++)
{for (j=0;j<n;j++)
B［i］［j］=A［j］［i］;
}
}
其中，MAX为常量，表示二维数组的最大行、列数。
【例5.3】设计一个算法，实现一个m×n的整型数组A和一个n×k的整型数组B的相乘运算。
设C=A×B，其中，A是m×n矩阵，B是n×k矩阵，则C为m×k矩阵，且C［i］［j］=∑n－1l=0A［i］［l］×B［l］［j］。 对应的算法如下。
void MutMat(int A［ ］［MAX］,int B［ ］［MAX］,int C［ ］［MAX］,int m,int n,int k)
{int i,j,l;
for (i=0;i<m;i++)
{for (j=0;j<k;j++)
{C［i］［j］=0;
for (l=0;l<n;l++)
C［i］［j］+=A［i］［l］*B［l］［j］;
}
}
}
5.2特殊矩阵的压缩存储
特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，为了节省存储空间，特别是在高阶矩阵的情况下，可以利用特殊矩阵的规律，对它们进行压缩存储，也就是说，使多个相同的非零元素共享同一个存储单元，对零元素不分配存储空间。特殊矩阵的主要形式有对称矩阵、对角矩阵等，它们都是方阵，即行数和列数相同。
1. 对称矩阵的压缩存储
若一个n阶方阵A={ai,j}中的元素满足ai,j=aj,i(0≤i，j≤n-1)，则称其为n阶对称矩阵。
一个n阶方阵的所有元素ai,j可以根据行、列下标划分为三部分，即上三角部分(i<j)、主对角线部分(i=j)和下三角部分(i>j)，如图5.4所示。
图5.4一个n阶方阵
如果直接采用二维数组存储对称矩阵，占用的内存空间为n2个元素大小。由于对称矩阵的元素关于主对角线对称，因此在存储时可只存储其上三角和主对角线部分元素，或者下三角和主对角线部分的元素，使得对称的元素共享同一存储空间。这样，就可以将n2个元素压缩存储到n(n+1)/2个元素的空间中。不失一般性，以行序为主序存储其下三角和主对角线部分的元素，如图5.5所示。
图5.5对称矩阵的压缩存储
假设以一维数组B={bk}作为n阶对称矩阵A的压缩存储结构，在B中只存储对称矩阵A的下三角和主对角线部分的元素ai,j(i≥j)，这样B中的元素个数为n(n+1)/2。
(1) 将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的前面也有j个元素，则元素ai,j之前共有i(i+1)/2+j个元素，所以有k=i(i+1)/2+j。
(2) 对于A中上三角部分元素ai,j(i<j)，它的值等于aj,i，而aj,i元素在B中的存储位置k=j(j+1)/2+i。
归纳起来，对于A中任一元素ai,j和B中元素bk之间存在着如下对应关系：
k=i（i+1）/2+j，当i≥j时
j（j+1）/2+i，当i<j时
2. 三角矩阵的压缩存储
有些非对称的矩阵也可借用上述方法存储，如n阶下(上)三角矩阵。所谓n阶下(上)三角矩阵，是指矩阵的上(下)三角部分(不包括主对角线)中的元素均为常数c的n阶方阵。
设以一维数组B={bk}作为n阶三角矩阵A的存储结构，B中的元素个数为n(n+1)/2+1(其中常数c占用一个元素空间)，则A中任一元素ai,j和B中元素bk之间存在着如下对应关系。
上三角矩阵：
k=i（2n-i+1）/2+j-i，当i≤j时
n（n+1）/2，当i>j时
下三角矩阵：
k=i（i+1）/2+j，当i≤j时
n（n+1）/2，当i>j时
其中，B的最后元素bn(n+1)/2中存放常数c。
3. 对角矩阵的压缩存储
若一个n阶方阵A满足其所有非零元素都集中在以主对角线为中心的带状区域中，则称其为n阶对角矩阵。其主对角线上下方各有b条次对角线，
图5.6半带宽为b的
对角矩阵
称b为矩阵半带宽，(2b+1)为矩阵的带宽。对于半带宽为b(0≤b≤(n-1)/2)的对角矩阵，其|i-j|≤b的元素ai,j不为零，其余元素为零。如图5.6所示是半带宽为b的对角矩阵示意图。
对于b=1的三对角矩阵A，只存储其非零元素，并按行优先存储到一维数组B中，将A的非零元素ai,j存储到B的元素bk中。A中第0行和第n-1行都只有两个非零元素，其余各行有三个非零元素。对于不在第0行的非零元素ai,j来说，在它前面存储了矩阵的前i行元素，这些元素的总数k为2+3(i-1)。
(1) 若ai,j是第i行中需要存储的第1个元素，则k=2+3(i-1)=3i-1，此时，j=i-1，即k=2i+i-1=2i+j。
(2) 若ai,j是第i行中需要存储的第2个元素，则k=2+3(i-1)+1=3i，此时，i=j，即k=2i+i=2i+j。
(3) 若ai,j是第i行中需要存储的第3个元素，则k=2+3(i-1)+2=3i+1，此时，j=i+1，即k=2i+i+1=2i+j。
归纳起来有： k=2i+j。
以上讨论的对称矩阵、三角矩阵、对角矩阵的压缩存储方法，是把有一定分布规律的值相同的元素(包括0)压缩存储到一个存储空间中。这样的压缩存储只需在算法中按相应公式做一映射即可实现矩阵元素的随机存取。
5.3稀 疏 矩 阵
一个阶数较大的矩阵中的非零元素个数s相对于矩阵元素的总个数t非常小时，即st时，称该矩阵为稀疏矩阵。例如一个100×100的矩阵，若其中只有100个非零元素，就可称其为稀疏矩阵。
稀疏矩阵的压缩存储方法是只存储非零元素，主要有三元组和十字链表两种方法。
5.3.1稀疏矩阵的三元组表示
由于稀疏矩阵中非零元素的分布没有任何规律，所以在存储非零元素时还必须同时存储该非零元素所对应的行、列下标。这样稀疏矩阵中的每一个非零元素需由一个三元组(i，j，ai，j)唯一确定，稀疏矩阵中的所有非零元素构成一个三元组线性表，将其采用顺序存储结构存储，称为稀疏矩阵的三元组表示。
如图5.7所示是一个6×7阶稀疏矩阵A(为图示方便，所取的行列数都很小)及其对应的三元组表示。
图5.7一个稀疏矩阵A及其对应的三元组表示
完整的稀疏矩阵三元组表示的类型声明如下。
#define MaxSize 100//矩阵中非零元素的最多个数
typedef struct
{int r;//行号
int c;//列号
ElemType d;//元素值为ElemType类型
} TupNode;//三元组定义
typedef struct
{int rows;//行数
int cols;//列数
int nums;//非零元素个数
TupNode data［MaxSize］;
} TSMatrix;//三元组顺序表定义
其中，data域中表示的非零元素通常以行序为主序顺序排列，它是一种下标按行有序的存储结构。这种有序存储结构可简化大多数矩阵运算算法。下面的讨论均假设data域按行有序存储。
稀疏矩阵运算通常包括矩阵转置、矩阵加、矩阵减、矩阵乘等。这里仅讨论基本运算算法。
1. 从一个二维稀疏矩阵创建其三元组表示
算法的思路是，以行序方式扫描二维稀疏矩阵A，将其非零的元素插入三元组t中。对应的算法如下。
void CreatMat(TSMatrix &t,ElemType A［M］［N］)
{int i,j;
t.rows=M;t.cols=N;t.nums=0;
for (i=0;i<M;i++)
{for (j=0;j<N;j++)
{if (A［i］［j］!=0) //只存储非零元素
{t.data［t.nums］.r=i;t.data［t.nums］.c=j;
t.data［t.nums］.d=A［i］［j］;t.nums++;
}
}
}
}
2. 三元组元素赋值
该运算的功能是对于稀疏矩阵A执行A［i］［j］=x操作(通常x是一个非零值)。由于A不是直接采用二维数组存储而是三元组t存储的，需要在t中实现该赋值操作。
算法思路是，根据i、j下标先在三元组t中找到适当的位置k，如果该元素原来就是非零元素(在t中找到了该元素)，直接将元素值修改为x； 否则(在t中找不到该元素)将k~t.nums个元素后移一个位置，将指定元素x插入t.data［k］处。对应的算法如下。
int Value(TSMatrix &t,ElemType x,int i,int j)
{int k=0,k1;
if (i>=t.rows || j>=t.cols)
return 0;//参数错误时返回0
while (k<t.nums && i>t.data［k］.r) k++;//查找行
while (k<t.nums && i==t.data［k］.r && j>t.data［k］.c) k++; //查找列
if (k<t.nums && t.data［k］.r==i && t.data［k］.c==j)//存在这样的元素
t.data［k］.d=x;
else//不存在这样的元素时插入一个元素
{for (k1=t.nums-1;k1>=k;k1--)
{t.data［k1+1］.r=t.data［k1］.r;
t.data［k1+1］.c=t.data［k1］.c;
t.data［k1+1］.d=t.data［k1］.d;
}
t.data［k］.r=i;t.data［k］.c=j;t.data［k］.d=x;
t.nums++;
}
return 1;//成功时返回1
}
3. 将指定位置的元素值赋给变量
该运算的功能是对于稀疏矩阵A执行x=A［i］［j］操作。由于A不是直接采用二维数组存储而是三元组t存储的，需要在t中实现该取值操作。
算法思路是，根据i、j下标先在三元组t中找到指定的位置k，如果该元素原来是非零元素(在t中找到了该元素)，直接将对应的元素值赋给x； 否则(在t中找不到该元素)说明该元素是一个零元素，置x=0。对应的算法如下。
int Assign(TSMatrix t,ElemType &x,int i,int j)
{int k=0;
if (i>=t.rows || j>=t.cols)
return 0;//参数错误时返回0
while (k<t.nums && i>t.data［k］.r) k++;//查找行
while (k<t.nums && i==t.data［k］.r && j>t.data［k］.c) k++; //查找列
if (k<t.nums && t.data［k］.r==i && t.data［k］.c==j)
x=t.data［k］.d;
else
x=0;//在三元组中没有找到表示是零元素
return 1;//成功时返回1
}
4. 输出三元组运算算法
该运算的功能是输出稀疏矩阵对应的三元组表示。直接从头到尾扫描三元组t，依次输出元素值。对应的算法如下。
void DispMat(TSMatrix t)
{int i;
if (t.nums<=0)//没有非零元素时返回
return;
printf("＼t%d＼t%d＼t%d＼n",t.rows,t.cols,t.nums);
printf("＼t------------------＼n");
for (i=0;i<t.nums;i++)
printf("＼t%d＼t%d＼t%d＼n",t.data［i］.r,t.data［i］.c,t.data［i］.d);
}
提示： 将稀疏矩阵三元组表示的类型声明及其基本运算函数存放在TSMatrix.cpp文件中。
当稀疏矩阵三元组表示的基本运算设计好后，给出以下主函数调用这些基本运算函数，读者可以对照程序执行结果进行分析，进一步体会稀疏矩阵三元组表示的各种操作的实现过程。
#define M 6
#define N 7
#include "TSMatrix.cpp"//包括稀疏矩阵三元组表示的基本运算算法
int main()
{TSMatrix t;
ElemType x;
ElemType a［M］［N］={{0,0,1,0,0,0,0},{0,2,0,0,0,0,0},{3,0,0,0,0,0,0},
{0,0,0,5,0,0,0},{0,0,0,0,6,0,0},{0,0,0,0,0,7,4}};
CreatMat(t,a);
printf("三元组t表示:＼n"); DispMat(t);
printf("执行A［4］［1］=8＼n");
Value(t,8,4,1);
printf("三元组t表示:＼n"); DispMat(t);
printf("求x=A［4］［1］＼n");
Assign(t,x,4,1);
printf("x=%d＼n",x);
}
上述程序的执行结果如下。
三元组t表示:
677
-----------
021
112
203
335
446
557
564
执行A［4］［1］=8
三元组t表示:
678
------------
021
112
203
335
418
446
557
564
求x=A［4］［1］
x=8
【例5.4】一个稀疏矩阵采用三元组表示压缩存储后，和直接采用二维数组存储相比会失去特性。
A. 顺序存储B. 随机存取C. 输入输出D. 以上都不对
当稀疏矩阵直接采用二维数组存储时，它具有随机存取特性。而采用三元组表示(或十字链表表示)时，对于给定稀疏矩阵中某个元素的下标(i，j)，在其三元组表示中查找对应元素值的时间不再是O(1)，所以尽管三元组表示占用的空间会减少，但不再具有随机存取特性。本题答案为B。
5.3.2稀疏矩阵的十字链表表示
十字链表是稀疏矩阵的一种链式存储结构。
对于一个m×n的稀疏矩阵，每个非零元素用一个结点表示，该结点中存放该零元素的行号、列号和元素值。同一行中的所有非零元素结点链接成一个带行头结点的行循环单链表，将同一列的所有非零元素结点链接成一个带列头结点的列循环单链表。之所以采用循环单链表，是因为矩阵运算中常常是一行(列)操作完后进行下一行(列)操作，最后一行(列)操作完后进行第一行(列)操作。
这样对稀疏矩阵的每个非零元素结点来说，它既是某个行链表中的一个结点，同时又是某个列链表中的一个结点，每个非零元素就好比在一个十字路口，由此称作十字链表。
每个非零元素结点的类型设计成如图5.8(a)所示的结构，其中，i、j、value分别代表非零元素所在的行号、列号和相应的元素值； down和right分别称为向下指针和向右指针，分别用来链接同列中和同行中的下一个非零元素结点。
这样行循环单链表个数为m(每一行对应一个行循环单链表)，列循环单链表个数为n(每一列对应一个列循环单链表)，那么行列头结点的个数就是m+n。实际上，行头结点与列头结点是共享的，即h［i］表示第i行循环单链表的头结点，同时也是第i列循环单链表的头结点，这里0≤i<MAX{m，n}，即行列头结点的个数是MAX{m，n}，所有行列头结点的类型与非零元素结点类型相同。
另外，将所有行列头结点再链接起来构成一个带头结点的循环单链表，这个头结点称为总头结点即hm，通过hm来标识整个十字链表。
总头结点的类型设计成如图5.8(b)所示的结构(之所以这样设计，是为了与非零元素结点类型一致，这样在整个十字链表中采用指针扫描所有结点时更方便)，它的link域指向第一个行列头结点，其i、j域分别存放稀疏矩阵的行数m和列数n，而down和right域没有作用。
图5.8十字链表结点结构
从中看出，在m×n的稀疏矩阵的十字链表存储结构中，有m个行循环单链表，n个列循环单链表，另加一个行列头结点构成的循环单链表，总的循环单链表个数是m+n+1，总的头结点个数是MAX{m，n}+1。
设稀疏矩阵如下：
B3×4=100200300004
对应的十字链表如图5.9所示。为图示清楚，把每个行列头结点分别画成两个，实际上行列值相同的头结点只有一个。
图5.9一个稀疏矩阵的十字链表
十字链表结点结构和头结点合起来声明的结点类型如下。
#define M 3//矩阵行数
#define N 4//矩阵列数
#define Max ((M)>(N)?(M):(N))//矩阵行列中较大者
typedef struct mtxn
{int i;//行号
int j;//列号
struct mtxn *right,*down;//向右和向下的指针
union
{ElemType value;//存放非零元素值
struct mtxn *link;
} tag;
} MatNode;//十字链表类型定义
有关稀疏矩阵采用十字链表表示时的相关运算算法与三元组表示类似，但更复杂，这里不再讨论。
【例5.5】一个m行n列的稀疏矩阵采用十字链表表示时，其中循环单链表的个数为。
A. m+1B. n+1C. m+n+1D. MAX{m，n}+1
稀疏矩阵采用十字链表表示时，每个非零元素对应一个结点，每行的所有结点构成一个带行头结点的循环单链表，每列的所有结点构成一个带列头结点的循环单链表，这些行列循环单链表的头结点是共享的，即第i行和第i列的头结点是共享的，所以行列头结点个数为MAX{m，n}。最后将所有头结点合起来构成一个带总头结点的循环单链表。因此其中循环单链表的个数为m+n+1，而头结点的个数为MAX{m，n}+1。本题答案为C。
小结
(1) 数组是线性表的推广，d(d≥1)维数组中存在d个线性关系。
(2) 数组通常采用顺序存储方法，分为以行优先和以列优先两种存储方式。
(3) 特殊矩阵不是指具有特殊用途的矩阵，是指一类元素值分布具有某种规律的矩阵，可以采用压缩存储方法。
(4) 对称矩阵、三角矩阵和对角矩阵采用压缩存储的目的是节省内存空间。
(5) 数组通常采用顺序存储结构，具有随机存取特性。
(6) 稀疏矩阵的压缩存储方式主要有三元组和十字链表表示，前者属顺序存储结构，后者属链式存储结构。
(7) 稀疏矩阵采用三元组或十字链表压缩存储方式后，不再具有随机存取特性。
练习题
上机实验题
不需要学习计算机基础课程？
关于学校里面开设的课程，大家可能会觉得不够时髦，不够酷，净是一些计算机组成原理、数据结构等老掉牙的课程，远没有什么SPRING框架来得过瘾。呵呵，不过根据我的经验，工作几年以后，大家可能会觉得，最值钱的，恰恰是这些最土气的课程。用框架，永远不算本事，也没有什么核心竞争力，哪天框架死了，你就死了。而另一方面，框架也是人做的，大家以为，做框架需要哪些知识？是不是上述old的知识？
——摘自著名的IT达人肖舸等著《IT学生解惑真经》