第四章 数组数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表
§ 4.1 数组的定义和特点
定义
mnmm
n
n
nm
aaa
aaa
aaa
A
..,..,
..,..,..,..,..,
..,..,
..,..,
21
22221
11211
数组特点
数组结构固定
数据元素同构
数组运算
给定一组下标，存取相应的数据元素
给定一组下标，修改数据元素的值
( )
( )
( )
( )(
)
(
)
(
)
(
)
(
)
§ 4.2 数组的顺序存储结构
次序约定
以行序为主序
以列序为主序
a11 a12 …….,a 1n
a21 a22 …….,a 2n
am1 am2 …….,a mn
………………….
Loc( aij)=Loc(a11)+[(i-1)n+(j-1)]*l
按行序为主序存放
amn
…….,
am2
am1
……….
a2n
…….,
a22
a21
a1n
…….
a12
a110
1
n-1
m*n-1
n
按列序为主序存放 1
m-
m*n-1
m
……..
2n
1n
……….
m2
……..
12
m1
…….
21
a11 a12 …….,a1n
a21 a22 …….,a2n
am1 am2 …….,amn
………………….
Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l
§ 4.3 矩阵的压缩存储
对称矩阵
jiijj
jijiik
,12/)1(
12/)1(,
a11 a12 …,… ….,a1n
a21 a22 …….,……,a2n
an1 an2 …….,ann
…………………,
a11 a21 a22 a31 a32 an1 ann…..,…...
k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1
按行序为主序：
三角矩阵
a11 0 0 …….,0
a21 a22 0 …….,0
an1 an2 an3…….,ann
…………………,0
Loc(aij)=Loc(a11)+[( +(j-1)]*li(i-1)2
a11 a21 a22 a31 a32 an1 ann…..,…...
k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1
按行序为主序：
对角矩阵
a11 a12 0 ……………,0
a21 a22 a23 0 …………… 0
0 0 … an-1,n-2 an-1,n-1 an-1,n
0 0 … … an,n-1 ann.
0 a32 a33 a34 0 ……… 0
……………………………
Loc(aij)=Loc(a11)+2(i-1)+(j-1)
a11 a12 a21 a22 a23 ann-1 ann…..,…...
k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1
按行序为主序：
数组可看成是一种特殊的线性表，其特殊在于，
表中的数所元素本身也是一种线性表。
数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，
数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组：
a11 a12 … a 1n
a21 a22 … a 2n
… … … …
am1 am2 … a mn
Amn=
4.1 数组的定义可以看成是由个行向量组成的向量，也可以看成是个列向量组成的向量。
在 C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说，
typedef elemtype array2[m][n];
等价于：
typedef elemtype array1[n];
typedef array1 array2[m];
同理，一个维数组类型可以定义为其数据元素为维数组类型的一维序组类型。
数组一旦被定义，它的维数和维界就不再改变。
因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。
2 数组的顺序表示和实现由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。
又由于对数组一般不做插入和删除操作，
也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，
一般都是采用顺序存储的方法来表示数组。
通常有两种顺序存储方式：
⑴行优先顺序 ——将数组元素按行排列，第 i+1个行向量紧接在第 i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为：
a11,a12,…,a1n,a21,a22,… a2n,……,am1,am2,…,amn
在 PASCAL,C语言中，数组就是按行优先顺序存储的。
⑵列优先顺序 ——将数组元素按列向量排列，第 j+1
个列向量紧接在第 j个列向量之后,A的 m*n个元素按列优先顺序存储的线性序列为：
a11,a21,…,am1,a12,a22,… am2,……,an1,an2,…,anm
在 FORTRAN语言中，数组就是按列优先顺序存储的。
以上规则可以推广到多维数组的情况：优先顺序可规定为先排最右的下标，从右到左，最后排最左下标：列优先顺序与此相反，先排最左下标，从左向右，最后排最右下标。
按上述两种方式顺序存储的序组，只要知道开始结点的存放地址（即基地址），
维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，
数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。
例如，二维数组 Amn按,行优先顺序,存储在内存中，
假设每个元素占用 d个存储单元。
元素 aij的存储地址应是数组的基地址加上排在
aij前面的元素所占用的单元数。因为 aij位于第 i行、
第 j列，前面 i-1行一共有 (i-1) × n个元素，第 i行上 aij前面又有 j-1个元素，故它前面一共有 (i-1)
× n+j-1个元素，因此,aij的地址计算函数为：
LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*d
同样，三维数组 Aijk按,行优先顺序,存储，其地址计算函数为：
LOC(aijk)=LOC(a111)+[(i-1)*n*p+(j-1)*p
+(k-1)]*d
上述讨论均是假设数组各维的下界是不是 1，
更一般的二维数组是 A[c1..d1,c2..d2]，这里 c1,c2不一定是 1。 aij前一共有 i-c1行，二维数组一共有 d2-c2+1列，故这 i-c1行共有
(i-c1)*(d2-c2+1)个元素，第 i行上 aij前一共有 j-c2个元素，因此,aij的地址计算函数为：
LOC(aij)=LOC(ac1c2)+[(i-c1)*(d2-c2+1)+j-
c2)]*d
例如，在 C语言中，数组各维下标的下界是
0，因此在 C语言中，二维数组的地址计算公式为：
LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d
在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述为一个二维数组。
矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为 1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为 1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。
4.2 矩阵的压缩存储所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。
1、对称矩阵在一个 n阶方阵 A中，若元素满足下述性质：
aij=aji 0≦ i,j≦ n-1
则称 A为对称矩阵。对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，
这样，能节约近一半的存储空间。不失一般性，
我们按,行优先 顺序”存储主对角线（包括对角线）以下的元素。
1 特殊矩阵存储形式如图所示：
1 5 1 3 7 a00
5 0 8 0 0 a10 a 11
1 8 9 2 6 a20 a21 a23
3 0 2 5 1 ………………..
7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 …a n-1 n-1
在这个下三角矩阵中，第 i行恰有 i+1个元素，元素总数为,(i+1)=n(n+1)/2
可以将这些元素存放在一个向量 sa[0..n(n+1)/2-1]
中。为了便于访问对称矩阵 A中的元素，我们必须在
aij和 sa[k]之间找一个对应关系。
若 i≧ j，则 ai j在下三角形中。 ai j之前的 i行（从第 0行到第 i-1行）一共有 1+2+…+i=i(i+1)/2 个元素，在第 i行上，
ai j之前恰有 j个元素（即 ai0,ai1,ai2,…,a ij-1），因此有：
k=i*(i+1)/2+j 0≦ k<n(n+1)/2
若 i<j，则 aij是在上三角矩阵中。因为 aij=aji，所以只要交换上述对应关系式中的 i和 j即可得到：
k=j*(j+1)/2+i 0≦ k<n(n+1)/2
令 I=max(i,j),J=min(i,j)，则 k和 i,j的对应关系可统一为：
k=I*(I+1)/2+J 0≦ k<n(n+1)/2
因此,aij的地址可用下列式计算：
LOC(aij)=LOC(sa[k])
=LOC(sa[0])+k*d=LOC(sa[0]+[I*(I+1)/2+J]*d
有了上述的下标交换关系，对于任意给定一组下标
(i,j)，均可在 sa[k]中找到矩阵元素 aij，反之，对所有的 k=0,1,2,…n(n -1)/2-1，都能确定 sa[k]中的元素在矩阵中的位置 (i,j)。由此，称 sa[n(n+1)/2]为阶对称矩阵 A的压缩存储，见下图：
k=0 1 2 3 n(n-1)/2 n(n-1)/2-1
例如 a21和 a12均存储在 sa[4]中，这是因为
k=I*(I+1)/2+J=2*(2+1)/2+1=4
a00 a10 a11 a20 …… an-1 0 …
…
an-1,n-1
以主对角线划分，三角矩阵有上三角和下三角两种。
上三角矩阵如图所示，它的下三角（不包括主对角线）
中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数。在大多数情况下，
三角矩阵常数为零。
a00 a01 … a 0 n-1 a00 0 … 0
0 a11 … a 1 n-1 a10 a11 … 0
………………….,……………..
0 0 … a n-1 n-1 an-1 0 an-1 1 … a n-1 n-1
(a)上三角矩阵 (b)下三角矩阵
2、三角矩阵三角矩阵中的重复元素 c可共享一个存储空间，
其余的元素正好有 n(n+1)/2个，因此，三角矩阵可压缩存储到向量 sa[0..n(n+1)/2]中，其中 c存放在向量的最后一个分量中，
上三角矩阵中，主对角线之上的第 p行
(0≦ p<n)恰有 n-p个元素，按行优先顺序存放上三角矩阵中的元素 aij时,aij之前的 i行一共有
(n-p)=i(2n-i+1)/2
个元素，在第 i行上,aij前恰好有 j-i个元素：
aij,aij+1,… aij-1。因此,sa[k]和 aij的对应关系是：
i(2n-i+1)/2+j-i 当 i≦ j
n(n+1)/2 当 i>jk=
下三角矩阵的存储和对称矩阵类似,sa[k]和 aij对应关系是：
i(i+1)/2+j i≧ j
n(n+1)/2 i>j
3、对角矩阵对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵，
a00 a01
a10 a11 a12
a21 a22 a23
…,….,…,
an-2 n-3 an-2 n-2 an-2 n-1
an-1 n-2 an-1 n-1
k=
非零元素仅出现在主对角 (aii,0≦ i≦ n-1上，
紧邻主对角线上面的那条对角线上
(aii+1,0≦ i≦ n-2)和紧邻主对角线下面的那条对角线上 (ai+1 i,0≦ i≦ n-2)。显然，当
∣ i-j∣ >1时，元素 aij=0。
由此可知，一个 k对角矩阵 (k为奇数 )A是满足下述条件的矩阵：若 ∣ i-j∣ >(k-1)/2,则元素 aij=0。
对角矩阵可按行优先顺序或对角线的顺序，
将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。
在三对角矩阵里附满足条件 i=0,j=0,1，或
i=n-1j=n-2,n-1或 1<i<n-1,j=i-1,i,i+1的元素 aij外，其余元素都是零。
对这种矩阵，我们也可按行优序为主序来存储。
除第 0行和第 n-1行是 2个元素外，每行的非零元素都要是 3个，因此，需存储的元素个数为 3n-2。
a00 a01 a10 a11 a12 a21 … … a n-1 n-2 a n-1 n-1
K=0 1 2 3 4 5 … … 3n -2 3n-1
数组 sa中的元素 sa[k]与三对角带状矩阵中的元素 aij存在一一对应关系，在 aij之前有 i行,共有 3*i-1
个非零元素，在第 i行，有 j-i+1个非零元素，这样，
非零元素 aij的地址为：
LOC(i,j)=LOC(0,0)+[3*i-1+(j-i+1)]*d
=LOC(0,0)+(2i+j)*d
上例中,a34对应着 sa[10]。
k=2*i+j=2*3+4=10
a21对应着 sa[5]
k=2*2+1=5
由此，我们称 sa[0..3*n-2]是阶三对角带状矩阵 A的压缩存储表示。
上述的各种特殊矩阵非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。
什么是稀疏矩阵？简单说，设矩阵 A中有 s个非零元素，若 s远远小于矩阵元素的总数（即
s≦ m× n），则称 A为稀疏矩阵。
4.3 稀疏矩阵例如，下列三元组表
((1,2,12)(1,3,9),(3,1,- 3),(3,6,14),(4,3,24),
(5,2,18),(6,1,15),(6,4,-7))
加上 (6,7)这一对行、列值便可作为下列矩阵 M的另一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。
0 12 9 0 0 0 0 0 0 -3 0 0 15
0 0 0 0 0 0 0 12 0 0 0 18 0
-3 0 0 0 0 14 0 9 0 0 24 0 0
0 0 24 0 0 0 0 0 0 0 0 0 –7
0 18 0 0 0 0 0 0 0 14 0 0 0
15 0 0 –7 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0
稀疏矩阵 M和 T
M=
T=
假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法 ——三元顺序表。
#define maxsize 10000
typedef int datatype;
typedef struct{
int i,j;
datatype v;
}triple;
一、三元组顺序表 转置
typedef struct{
triple data[maxsize];
int m,n,t;
}tripletable;
设 A为 tripletable型的结构变量，图 5.4中所示的稀疏矩阵的三元组的表示如下：
i j v
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
以矩阵的转置为例，说明在这种压缩存储结构上如何实现矩阵的运算。
一个 m× n的矩阵 A，它的转置 B是一个 n× m的矩阵，且 a[i][j]=b[j][i],0≦ i≦ m,0≦ j≦ n，
即 A的行是 B的列,A的列是 B的行。
将 A转置为 B，就是将 A的三元组表 a.data置换为表 B的三元组表 b.data，如果只是简单地交换
a.data中 i和 j的内容，那么得到的 b.data将是一个按列优先顺序存储的稀疏矩阵 B，要得到按行优先顺序存储的 b.data，就必须重新排列三元组的顺序。
由于 A的列是 B的行，因此，按 a.data的列序转置，所得到的转置矩阵 B的三元组表 b.data
必定是按行优先存放的。
按这种方法设计的算法，其基本思想是：对 A中的每一列 col(0≦ col≦ n-1)，通过从头至尾扫描三元表 a.data，找出所有列号等于 col的那些三元组，将它们的行号和列号互换后依次放入 b.data中，即可得到 B的按行优先的压缩存储表示。
i j v
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
Void transmatrix(tripletable a,tripletable b)
{
int p q col;
b.m=a.n;
b.n=a.m;
b.t=a.t;
if(b.t<=0)
printf(―A=0\n‖);
q=0;
for(col=1;col<=a.n;col++)
for(p=0;p<=a.t;p++)
if(a.data[p].j==col){
b.data[q].i=a.data[p].j;
b.data[q].j=a.data[p].i;
b.data[q].v=a.data[p].v;
q++;
}
}
分析这个算法，主要的工作是在 p和 col的两个循环中完成的，故算法的时间复杂度为
O(n*t)，即矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算法为：
for(col=0;col<=n-1;++col)
for(row=0;row<=m;++row)
t[col][row]=m[row][col];
其时间复杂度为 O(n*m)。当非零元素的个数
t和 m*n同数量级时，算法 transmatrix的时间复杂度为 O(n*n2)。
三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算是法的难度。因此，此算法仅适用于 t<=m*n的情况。
下面给出一种快速转置的算法，其算法思想为：对 A扫描一次，按 A第二列提供的列号一次确定位置装入 B的一个三元组。具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法的关键。
为了预先确定矩阵 M中的每一列的第一个非零元素在数组 B中应有的位置，需要先求得矩阵
M中的每一列中非零元素的个数。因为：矩阵
M中第一列的第一个非零元素在数组 B中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。
为此，需要设置两个一维数组 num[0..n]
和 cpot[0..n]
num[0..n]：统计 M中每列非零元素的个数，
num[col]的值可以由 A的第二列求得。
cpot[0..n]：由递推关系得出 M中的每列第一个非零元素在 B中的位置。
算法通过 cpot数组建立位置对应关系：
cpot[1]=1
cpot[i]=cpot[i-1]+num[i-1]
2<=i<=a.n
例如：图中的矩阵 M和相应的三元组 A可以求得 num[i]和 cpot[i]的值如下：
i 1 2 3 4 5 6 7
num[i] 2 2 2 1 0 1 0
cpot[i] 1 3 5 7 8 8 9
1 2 v
q …
A i j v 第一列元素个数 第二列元素个数第三列元素个数
num
cpot
q=cpot[i]
2 1 v
p
q
快速转置算法如下：
void fasttranstri(tritupletable b,tritupletable a){
int p,q,l,k;
int num[a.n],copt[a.n];
b.m=a.n; b.n=a.m; b.t=a.t;
if(b.t<=0)
printf(―a=0‖\n);
for(l=1;l<=a.n;++l)
num[l]=0;
for(k=1;k<=a.t;++k)
++num[a.data[k].j];
cpot[0]=1;
for(l=2; l<=a.t;++l)
cpot[l]=cpot[l-1]+num[l-1];
for(p=1;p<=a.t;++p){
col=a.data[p].j; q=cpot[l];
b.data[q].i=a.data[p].j;
b.data[q].j=a.data[p].i;
b.data[q].v=a.data[p].v;++cpot[l];
}
}
}
有时为了方便某些矩阵运算，我们在按行优先存储的三元组中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。当将行表作为三元组表的一个新增属性加以描述时，我们就得到了稀疏矩阵的另一种顺序存储结构：带行表的三元组表。
其类型描述如下：
二、带行表的三元组 乘法
#define maxrow 100
typedef struct{
triple data[maxsize];
int rpos[maxrow];
int n,m,t;
}rtripletable;
下面讨论两个稀疏矩阵相乘的例子，容易看出这种表示方法的优越性。
两个矩阵相乘的经典算法也是大家所熟悉的。设
Q=M*N 其中,M是 m1*n1矩阵,N是 m2*n2矩阵。
当 n1=m2时有：
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];
}
此算法的复杂度为 O(m1*n1*n2)。
当 M和 N是稀疏矩阵并用三元组表存储结构时，就不能套用上述算法。假设 M和 N分别为：
3 0 0 5
0 -1 0 0
2 0 0 0
M=
0 2
1 0
-2 4
0 0
N=
则 Q=M*N为：
0 6
-1 0
0 4
Q=
它们的三元组分别为：
i j v i j v i j v
1 1 3 1 2 2 1 2 6
1 4 5 2 1 1 2 1 -1
3 2 -1 3 1 -2 3 2 4
3 1 2 3 2 4 q.data
m.data n.data
稀疏矩阵相乘的基本思想是：对于 M中每个元素 M，找到 N 中所有满足条件的元素，求得和的乘积，而从式得知，乘积矩阵 Q中每个元素的值是个累加和，
这个乘积只是中的一部分。为了便于操作，应对每个元素设一累加和的变量，其初值为零，然后扫描数组 M，求得相应元素的乘积并累加到适当的求累计和的变量上。
void multsmatrix(rtripletable a,
rtripletable b,rtripletable c){
if(a.n!=b.m){ //不能相乘
printf(―error\n‖); exit(0);
}
c.m=a.m; c.n=b.n; c.t=0;
if(a.t*b.t!=0){
for(arow=1;arow<=a.m;++arow){
ctemp[arow]=0;
c.rpos[arow]=c.t+1;
for(p=a.rops[arow];p<a.rpos[arow+1];++p){
brow=a.data[p].j;
if(brow<b.t) t=b.rpos[brow+1]
else t=b.t+1;
for(q=b.rpos[brow]; q<t;++q){
ccol=n.data[q].j;
ctemp[ccol]+=a.data[p].v*b.data[q].v;
}
}
for(ccol=1;ccol<=c.n;++ccol)
if(ctemp[ccol]){
if(++c.t>maxsize)
exit(0);
c.data[c.t]={arow,ccol,ctemp[ccol]};
}
}
}
}
7600070015
00000180
00002400
01400003
0000000
00009120
M
M由 {(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),
(5,2,18),(6,1,15),(6,4,-7) } 和矩阵维数（ 6,7）唯一确定
稀疏矩阵
定义：非零元较零元少，且分布没有一定规律的矩阵
压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值稀疏矩阵 (其他讲解方式 )
稀疏矩阵的压缩存储方法
顺序存储结构
三元组表 #define M 20typedef struct node
{ int i,j;
int v;
}JD;
JD ma[M];
三元组表所需存储单元个数为 3(t+1)
其中 t为非零元个数
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
ma
i j v
0
1
2
3
4
5
6
7
8
ma[0].i,ma[0].j,ma[0].v分别存放矩阵行列维数和非零元个数行列下标 非零元值 7600070015
00000180
00002400
01400003
0000000
00009120
M
带辅助行向量的二元组表增加一个辅助数组 NRA[m+1],其物理意义是第 i行第一个非零元在二元组表中的起始地址（ m为行数）
显然有,POS[1]=1
POS[i]=POS[i-1]+第 i-1行非零元个数 (i?2)
0
1
2
3
4
5
6
POS
1
3
3
5
6
7
6 7 8
2 12
3 9
1 -3
6 14
3 24
2 18
1 15
4 -7
ma
j v
0
1
2
3
4
5
6
7
8
矩阵列数和非零元个数列下标和非零元值POS[0]不用或存矩阵行数二元组表需存储单元个数为 2(t+1)+m+1
7600070015
00000180
00002400
01400003
0000000
00009120
M
伪地址表示法伪地址：本元素在矩阵中（包括零元素）
按行优先顺序的相对位置
6 7
2 12
3 9
15 -3
20 14
24 24
30 18
36 15
39 -7
ma
addr v伪地址 非零元值矩阵行列维数0
1
2
3
4
5
6
7
8
伪地址表示法需存储单元个数为 2(t+1)
7600070015
00000180
00002400
01400003
0000000
00009120
M
求转置矩阵
问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表
问题分析一般矩阵转置算法：
for(col=0;col<n;col++)
for(row=0;row<m;row++)
n[col][row]=m[row][col];
T(n)=O(m?n)
7600070015
00000180
00002400
01400003
0000000
00009120
M
67000000
0001400
000000
700000
0024009
01800012
1500300
N
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
i j v
0
1
2
3
4
5
6
7
8
ma
i j v
7 6 8
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
0
1
2
3
4
5
6
7
8
mb
解决思路：只要做到
将矩阵行、列维数互换
将每个三元组中的 i和 j相互调换
重排三元组次序，使 mb中元素以 N的行 (M的列 )为主序方法一：按 M的列序转置即按 mb中三元组次序依次在 ma中找到相应的三元组进行转置。
为找到 M中每一列所有非零元素，需对其三元组表 ma从第一行起扫描一遍。由于 ma中以 M行序为主序,所以由此得到的恰是 mb
中应有的顺序
算法描述,
算法分析,T(n)=O(M的列数 n?非零元个数 t)
若 t 与 m?n同数量级，则 )()( 2nmOnT
Ch4_1.c
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
i j v
0
1
2
3
4
5
6
7
8 ma
7 6 8
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
i j v
0
1
2
3
4
5
6
7
8 mb
kp
p
p
p
p
p
p
p
k
k
k
k
p
p
p
p
p
p
p
p
col=1 col=2
方法二：快速转置即按 ma中三元组次序转置，转置结果放入 b中恰当位置此法关键是要预先确定 M中每一列第一个非零元在 mb中位置，
为确定这些位置，转置前应先求得 M的每一列中非零元个数实现：设两个数组
num[col]：表示矩阵 M中第 col列中非零元个数
cpot[col],指示 M中第 col列第一个非零元在 mb中位置显然有,cpot[1]=1;
cpot[col]=cpot[col-1]+num[col-1]; (2?col?ma[0].j)
1 3 5 7 8 8 9
col
num[col]
cpot[col]
1
2
2
2
3
2
4
1
5
0
6
1
7
0
7600070015
00000180
00002400
01400003
0000000
00009120
M
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
i j v
0
1
2
3
4
5
6
7
8 ma
i j v
0
1
2
3
4
5
6
7
8 mb
col
num[col]
cpot[col]
1
1
2
2
3
2
3
5
2
4
7
1
5
8
0
6
8
1
7
9
0
7 6 8
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
p
p
p
p
p
p
p
p
4 62 9
753
算法分析,T(n)=O(M的列数 n+非零元个数 t)
若 t 与 m?n同数量级，则 T(n)=O(m?n)
算法描述：
Ch4_2.c
链式存储结构
带行指针向量的单链表表示
每行的非零元用一个单链表存放
设置一个行指针数组，指向本行第一个非零元结点；若本行无非零元，则指针为空
表头结点与单链表结点类型定义typedef struct node{ int col;
int val;
struct node *link;
}JD;
typedef struct node *TD;
02000
00000
00021
00100
70003
A
^
1 3 5 7
3 -1
1 -1 2 -2
4 2 ^
^
^
^
需存储单元个数为 3t+m
链式存储结构
十字链表
设行指针数组和列指针数组，分别指向每行、
列第一个非零元
结点定义
typedef struct node
{ int row,col,val;
struct node *down,*right;
}JD;
row col val
down right
34008
000
450
003
A
1 1 3
4 1 8
2 2 5 2 3 4
^
^ ^
^
^ ^ ^
从键盘接收信息建立十字链表算法
算法分析,T(n)=o(t?s)
其中,t——非零元个数
s= max(m,n)
Ch4_3.c
令 q=NULL,p=rh[r-1],
（ 1） 寻找插入位置,当 p!=NULL且 c>p->col时,p和 q右移
（ 2）插入：
a、若 p==NULL且 q==NULL，即本行空,则 rh[r-1]==s;
b,若 p==NULL,q!=NULL,即走到行末，则 q->right=s
c,若 c==p->col,则修改 p->val
d,若 c<p->col且 q==NULL,则在 p之前插入 s,即 s是行链表中第一个结点，令 rh[r-1]=s; s->right=p;
e,若 c<p->col且 q!=NULL,则在 p之前插入 s，
即 s->right=p; q->right=s;
4 1 8
^ ^
2 3 4
^ ^
m=4,n=3
1,1,3
2,2,5
2,3,4
4,1,8
2,1,7
Ch4_3.c
1 1 3
^^
2 1 7
^ ^
2 2 5
^ ^
§ 4.1 数组的定义和特点
定义
mnmm
n
n
nm
aaa
aaa
aaa
A
..,..,
..,..,..,..,..,
..,..,
..,..,
21
22221
11211
数组特点
数组结构固定
数据元素同构
数组运算
给定一组下标，存取相应的数据元素
给定一组下标，修改数据元素的值
( )
( )
( )
( )(
)
(
)
(
)
(
)
(
)
§ 4.2 数组的顺序存储结构
次序约定
以行序为主序
以列序为主序
a11 a12 …….,a 1n
a21 a22 …….,a 2n
am1 am2 …….,a mn
………………….
Loc( aij)=Loc(a11)+[(i-1)n+(j-1)]*l
按行序为主序存放
amn
…….,
am2
am1
……….
a2n
…….,
a22
a21
a1n
…….
a12
a110
1
n-1
m*n-1
n
按列序为主序存放 1
m-
m*n-1
m
……..
2n
1n
……….
m2
……..
12
m1
…….
21
a11 a12 …….,a1n
a21 a22 …….,a2n
am1 am2 …….,amn
………………….
Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l
§ 4.3 矩阵的压缩存储
对称矩阵
jiijj
jijiik
,12/)1(
12/)1(,
a11 a12 …,… ….,a1n
a21 a22 …….,……,a2n
an1 an2 …….,ann
…………………,
a11 a21 a22 a31 a32 an1 ann…..,…...
k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1
按行序为主序：
三角矩阵
a11 0 0 …….,0
a21 a22 0 …….,0
an1 an2 an3…….,ann
…………………,0
Loc(aij)=Loc(a11)+[( +(j-1)]*li(i-1)2
a11 a21 a22 a31 a32 an1 ann…..,…...
k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1
按行序为主序：
对角矩阵
a11 a12 0 ……………,0
a21 a22 a23 0 …………… 0
0 0 … an-1,n-2 an-1,n-1 an-1,n
0 0 … … an,n-1 ann.
0 a32 a33 a34 0 ……… 0
……………………………
Loc(aij)=Loc(a11)+2(i-1)+(j-1)
a11 a12 a21 a22 a23 ann-1 ann…..,…...
k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1
按行序为主序：
数组可看成是一种特殊的线性表，其特殊在于，
表中的数所元素本身也是一种线性表。
数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，
数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组：
a11 a12 … a 1n
a21 a22 … a 2n
… … … …
am1 am2 … a mn
Amn=
4.1 数组的定义可以看成是由个行向量组成的向量，也可以看成是个列向量组成的向量。
在 C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说，
typedef elemtype array2[m][n];
等价于：
typedef elemtype array1[n];
typedef array1 array2[m];
同理，一个维数组类型可以定义为其数据元素为维数组类型的一维序组类型。
数组一旦被定义，它的维数和维界就不再改变。
因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。
2 数组的顺序表示和实现由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。
又由于对数组一般不做插入和删除操作，
也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，
一般都是采用顺序存储的方法来表示数组。
通常有两种顺序存储方式：
⑴行优先顺序 ——将数组元素按行排列，第 i+1个行向量紧接在第 i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为：
a11,a12,…,a1n,a21,a22,… a2n,……,am1,am2,…,amn
在 PASCAL,C语言中，数组就是按行优先顺序存储的。
⑵列优先顺序 ——将数组元素按列向量排列，第 j+1
个列向量紧接在第 j个列向量之后,A的 m*n个元素按列优先顺序存储的线性序列为：
a11,a21,…,am1,a12,a22,… am2,……,an1,an2,…,anm
在 FORTRAN语言中，数组就是按列优先顺序存储的。
以上规则可以推广到多维数组的情况：优先顺序可规定为先排最右的下标，从右到左，最后排最左下标：列优先顺序与此相反，先排最左下标，从左向右，最后排最右下标。
按上述两种方式顺序存储的序组，只要知道开始结点的存放地址（即基地址），
维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，
数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。
例如，二维数组 Amn按,行优先顺序,存储在内存中，
假设每个元素占用 d个存储单元。
元素 aij的存储地址应是数组的基地址加上排在
aij前面的元素所占用的单元数。因为 aij位于第 i行、
第 j列，前面 i-1行一共有 (i-1) × n个元素，第 i行上 aij前面又有 j-1个元素，故它前面一共有 (i-1)
× n+j-1个元素，因此,aij的地址计算函数为：
LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*d
同样，三维数组 Aijk按,行优先顺序,存储，其地址计算函数为：
LOC(aijk)=LOC(a111)+[(i-1)*n*p+(j-1)*p
+(k-1)]*d
上述讨论均是假设数组各维的下界是不是 1，
更一般的二维数组是 A[c1..d1,c2..d2]，这里 c1,c2不一定是 1。 aij前一共有 i-c1行，二维数组一共有 d2-c2+1列，故这 i-c1行共有
(i-c1)*(d2-c2+1)个元素，第 i行上 aij前一共有 j-c2个元素，因此,aij的地址计算函数为：
LOC(aij)=LOC(ac1c2)+[(i-c1)*(d2-c2+1)+j-
c2)]*d
例如，在 C语言中，数组各维下标的下界是
0，因此在 C语言中，二维数组的地址计算公式为：
LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d
在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述为一个二维数组。
矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为 1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为 1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。
4.2 矩阵的压缩存储所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。
1、对称矩阵在一个 n阶方阵 A中，若元素满足下述性质：
aij=aji 0≦ i,j≦ n-1
则称 A为对称矩阵。对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，
这样，能节约近一半的存储空间。不失一般性，
我们按,行优先 顺序”存储主对角线（包括对角线）以下的元素。
1 特殊矩阵存储形式如图所示：
1 5 1 3 7 a00
5 0 8 0 0 a10 a 11
1 8 9 2 6 a20 a21 a23
3 0 2 5 1 ………………..
7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 …a n-1 n-1
在这个下三角矩阵中，第 i行恰有 i+1个元素，元素总数为,(i+1)=n(n+1)/2
可以将这些元素存放在一个向量 sa[0..n(n+1)/2-1]
中。为了便于访问对称矩阵 A中的元素，我们必须在
aij和 sa[k]之间找一个对应关系。
若 i≧ j，则 ai j在下三角形中。 ai j之前的 i行（从第 0行到第 i-1行）一共有 1+2+…+i=i(i+1)/2 个元素，在第 i行上，
ai j之前恰有 j个元素（即 ai0,ai1,ai2,…,a ij-1），因此有：
k=i*(i+1)/2+j 0≦ k<n(n+1)/2
若 i<j，则 aij是在上三角矩阵中。因为 aij=aji，所以只要交换上述对应关系式中的 i和 j即可得到：
k=j*(j+1)/2+i 0≦ k<n(n+1)/2
令 I=max(i,j),J=min(i,j)，则 k和 i,j的对应关系可统一为：
k=I*(I+1)/2+J 0≦ k<n(n+1)/2
因此,aij的地址可用下列式计算：
LOC(aij)=LOC(sa[k])
=LOC(sa[0])+k*d=LOC(sa[0]+[I*(I+1)/2+J]*d
有了上述的下标交换关系，对于任意给定一组下标
(i,j)，均可在 sa[k]中找到矩阵元素 aij，反之，对所有的 k=0,1,2,…n(n -1)/2-1，都能确定 sa[k]中的元素在矩阵中的位置 (i,j)。由此，称 sa[n(n+1)/2]为阶对称矩阵 A的压缩存储，见下图：
k=0 1 2 3 n(n-1)/2 n(n-1)/2-1
例如 a21和 a12均存储在 sa[4]中，这是因为
k=I*(I+1)/2+J=2*(2+1)/2+1=4
a00 a10 a11 a20 …… an-1 0 …
…
an-1,n-1
以主对角线划分，三角矩阵有上三角和下三角两种。
上三角矩阵如图所示，它的下三角（不包括主对角线）
中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数。在大多数情况下，
三角矩阵常数为零。
a00 a01 … a 0 n-1 a00 0 … 0
0 a11 … a 1 n-1 a10 a11 … 0
………………….,……………..
0 0 … a n-1 n-1 an-1 0 an-1 1 … a n-1 n-1
(a)上三角矩阵 (b)下三角矩阵
2、三角矩阵三角矩阵中的重复元素 c可共享一个存储空间，
其余的元素正好有 n(n+1)/2个，因此，三角矩阵可压缩存储到向量 sa[0..n(n+1)/2]中，其中 c存放在向量的最后一个分量中，
上三角矩阵中，主对角线之上的第 p行
(0≦ p<n)恰有 n-p个元素，按行优先顺序存放上三角矩阵中的元素 aij时,aij之前的 i行一共有
(n-p)=i(2n-i+1)/2
个元素，在第 i行上,aij前恰好有 j-i个元素：
aij,aij+1,… aij-1。因此,sa[k]和 aij的对应关系是：
i(2n-i+1)/2+j-i 当 i≦ j
n(n+1)/2 当 i>jk=
下三角矩阵的存储和对称矩阵类似,sa[k]和 aij对应关系是：
i(i+1)/2+j i≧ j
n(n+1)/2 i>j
3、对角矩阵对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵，
a00 a01
a10 a11 a12
a21 a22 a23
…,….,…,
an-2 n-3 an-2 n-2 an-2 n-1
an-1 n-2 an-1 n-1
k=
非零元素仅出现在主对角 (aii,0≦ i≦ n-1上，
紧邻主对角线上面的那条对角线上
(aii+1,0≦ i≦ n-2)和紧邻主对角线下面的那条对角线上 (ai+1 i,0≦ i≦ n-2)。显然，当
∣ i-j∣ >1时，元素 aij=0。
由此可知，一个 k对角矩阵 (k为奇数 )A是满足下述条件的矩阵：若 ∣ i-j∣ >(k-1)/2,则元素 aij=0。
对角矩阵可按行优先顺序或对角线的顺序，
将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。
在三对角矩阵里附满足条件 i=0,j=0,1，或
i=n-1j=n-2,n-1或 1<i<n-1,j=i-1,i,i+1的元素 aij外，其余元素都是零。
对这种矩阵，我们也可按行优序为主序来存储。
除第 0行和第 n-1行是 2个元素外，每行的非零元素都要是 3个，因此，需存储的元素个数为 3n-2。
a00 a01 a10 a11 a12 a21 … … a n-1 n-2 a n-1 n-1
K=0 1 2 3 4 5 … … 3n -2 3n-1
数组 sa中的元素 sa[k]与三对角带状矩阵中的元素 aij存在一一对应关系，在 aij之前有 i行,共有 3*i-1
个非零元素，在第 i行，有 j-i+1个非零元素，这样，
非零元素 aij的地址为：
LOC(i,j)=LOC(0,0)+[3*i-1+(j-i+1)]*d
=LOC(0,0)+(2i+j)*d
上例中,a34对应着 sa[10]。
k=2*i+j=2*3+4=10
a21对应着 sa[5]
k=2*2+1=5
由此，我们称 sa[0..3*n-2]是阶三对角带状矩阵 A的压缩存储表示。
上述的各种特殊矩阵非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。
什么是稀疏矩阵？简单说，设矩阵 A中有 s个非零元素，若 s远远小于矩阵元素的总数（即
s≦ m× n），则称 A为稀疏矩阵。
4.3 稀疏矩阵例如，下列三元组表
((1,2,12)(1,3,9),(3,1,- 3),(3,6,14),(4,3,24),
(5,2,18),(6,1,15),(6,4,-7))
加上 (6,7)这一对行、列值便可作为下列矩阵 M的另一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。
0 12 9 0 0 0 0 0 0 -3 0 0 15
0 0 0 0 0 0 0 12 0 0 0 18 0
-3 0 0 0 0 14 0 9 0 0 24 0 0
0 0 24 0 0 0 0 0 0 0 0 0 –7
0 18 0 0 0 0 0 0 0 14 0 0 0
15 0 0 –7 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0
稀疏矩阵 M和 T
M=
T=
假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法 ——三元顺序表。
#define maxsize 10000
typedef int datatype;
typedef struct{
int i,j;
datatype v;
}triple;
一、三元组顺序表 转置
typedef struct{
triple data[maxsize];
int m,n,t;
}tripletable;
设 A为 tripletable型的结构变量，图 5.4中所示的稀疏矩阵的三元组的表示如下：
i j v
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
以矩阵的转置为例，说明在这种压缩存储结构上如何实现矩阵的运算。
一个 m× n的矩阵 A，它的转置 B是一个 n× m的矩阵，且 a[i][j]=b[j][i],0≦ i≦ m,0≦ j≦ n，
即 A的行是 B的列,A的列是 B的行。
将 A转置为 B，就是将 A的三元组表 a.data置换为表 B的三元组表 b.data，如果只是简单地交换
a.data中 i和 j的内容，那么得到的 b.data将是一个按列优先顺序存储的稀疏矩阵 B，要得到按行优先顺序存储的 b.data，就必须重新排列三元组的顺序。
由于 A的列是 B的行，因此，按 a.data的列序转置，所得到的转置矩阵 B的三元组表 b.data
必定是按行优先存放的。
按这种方法设计的算法，其基本思想是：对 A中的每一列 col(0≦ col≦ n-1)，通过从头至尾扫描三元表 a.data，找出所有列号等于 col的那些三元组，将它们的行号和列号互换后依次放入 b.data中，即可得到 B的按行优先的压缩存储表示。
i j v
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
Void transmatrix(tripletable a,tripletable b)
{
int p q col;
b.m=a.n;
b.n=a.m;
b.t=a.t;
if(b.t<=0)
printf(―A=0\n‖);
q=0;
for(col=1;col<=a.n;col++)
for(p=0;p<=a.t;p++)
if(a.data[p].j==col){
b.data[q].i=a.data[p].j;
b.data[q].j=a.data[p].i;
b.data[q].v=a.data[p].v;
q++;
}
}
分析这个算法，主要的工作是在 p和 col的两个循环中完成的，故算法的时间复杂度为
O(n*t)，即矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算法为：
for(col=0;col<=n-1;++col)
for(row=0;row<=m;++row)
t[col][row]=m[row][col];
其时间复杂度为 O(n*m)。当非零元素的个数
t和 m*n同数量级时，算法 transmatrix的时间复杂度为 O(n*n2)。
三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算是法的难度。因此，此算法仅适用于 t<=m*n的情况。
下面给出一种快速转置的算法，其算法思想为：对 A扫描一次，按 A第二列提供的列号一次确定位置装入 B的一个三元组。具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法的关键。
为了预先确定矩阵 M中的每一列的第一个非零元素在数组 B中应有的位置，需要先求得矩阵
M中的每一列中非零元素的个数。因为：矩阵
M中第一列的第一个非零元素在数组 B中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。
为此，需要设置两个一维数组 num[0..n]
和 cpot[0..n]
num[0..n]：统计 M中每列非零元素的个数，
num[col]的值可以由 A的第二列求得。
cpot[0..n]：由递推关系得出 M中的每列第一个非零元素在 B中的位置。
算法通过 cpot数组建立位置对应关系：
cpot[1]=1
cpot[i]=cpot[i-1]+num[i-1]
2<=i<=a.n
例如：图中的矩阵 M和相应的三元组 A可以求得 num[i]和 cpot[i]的值如下：
i 1 2 3 4 5 6 7
num[i] 2 2 2 1 0 1 0
cpot[i] 1 3 5 7 8 8 9
1 2 v
q …
A i j v 第一列元素个数 第二列元素个数第三列元素个数
num
cpot
q=cpot[i]
2 1 v
p
q
快速转置算法如下：
void fasttranstri(tritupletable b,tritupletable a){
int p,q,l,k;
int num[a.n],copt[a.n];
b.m=a.n; b.n=a.m; b.t=a.t;
if(b.t<=0)
printf(―a=0‖\n);
for(l=1;l<=a.n;++l)
num[l]=0;
for(k=1;k<=a.t;++k)
++num[a.data[k].j];
cpot[0]=1;
for(l=2; l<=a.t;++l)
cpot[l]=cpot[l-1]+num[l-1];
for(p=1;p<=a.t;++p){
col=a.data[p].j; q=cpot[l];
b.data[q].i=a.data[p].j;
b.data[q].j=a.data[p].i;
b.data[q].v=a.data[p].v;++cpot[l];
}
}
}
有时为了方便某些矩阵运算，我们在按行优先存储的三元组中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。当将行表作为三元组表的一个新增属性加以描述时，我们就得到了稀疏矩阵的另一种顺序存储结构：带行表的三元组表。
其类型描述如下：
二、带行表的三元组 乘法
#define maxrow 100
typedef struct{
triple data[maxsize];
int rpos[maxrow];
int n,m,t;
}rtripletable;
下面讨论两个稀疏矩阵相乘的例子，容易看出这种表示方法的优越性。
两个矩阵相乘的经典算法也是大家所熟悉的。设
Q=M*N 其中,M是 m1*n1矩阵,N是 m2*n2矩阵。
当 n1=m2时有：
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];
}
此算法的复杂度为 O(m1*n1*n2)。
当 M和 N是稀疏矩阵并用三元组表存储结构时，就不能套用上述算法。假设 M和 N分别为：
3 0 0 5
0 -1 0 0
2 0 0 0
M=
0 2
1 0
-2 4
0 0
N=
则 Q=M*N为：
0 6
-1 0
0 4
Q=
它们的三元组分别为：
i j v i j v i j v
1 1 3 1 2 2 1 2 6
1 4 5 2 1 1 2 1 -1
3 2 -1 3 1 -2 3 2 4
3 1 2 3 2 4 q.data
m.data n.data
稀疏矩阵相乘的基本思想是：对于 M中每个元素 M，找到 N 中所有满足条件的元素，求得和的乘积，而从式得知，乘积矩阵 Q中每个元素的值是个累加和，
这个乘积只是中的一部分。为了便于操作，应对每个元素设一累加和的变量，其初值为零，然后扫描数组 M，求得相应元素的乘积并累加到适当的求累计和的变量上。
void multsmatrix(rtripletable a,
rtripletable b,rtripletable c){
if(a.n!=b.m){ //不能相乘
printf(―error\n‖); exit(0);
}
c.m=a.m; c.n=b.n; c.t=0;
if(a.t*b.t!=0){
for(arow=1;arow<=a.m;++arow){
ctemp[arow]=0;
c.rpos[arow]=c.t+1;
for(p=a.rops[arow];p<a.rpos[arow+1];++p){
brow=a.data[p].j;
if(brow<b.t) t=b.rpos[brow+1]
else t=b.t+1;
for(q=b.rpos[brow]; q<t;++q){
ccol=n.data[q].j;
ctemp[ccol]+=a.data[p].v*b.data[q].v;
}
}
for(ccol=1;ccol<=c.n;++ccol)
if(ctemp[ccol]){
if(++c.t>maxsize)
exit(0);
c.data[c.t]={arow,ccol,ctemp[ccol]};
}
}
}
}
7600070015
00000180
00002400
01400003
0000000
00009120
M
M由 {(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),
(5,2,18),(6,1,15),(6,4,-7) } 和矩阵维数（ 6,7）唯一确定
稀疏矩阵
定义：非零元较零元少，且分布没有一定规律的矩阵
压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值稀疏矩阵 (其他讲解方式 )
稀疏矩阵的压缩存储方法
顺序存储结构
三元组表 #define M 20typedef struct node
{ int i,j;
int v;
}JD;
JD ma[M];
三元组表所需存储单元个数为 3(t+1)
其中 t为非零元个数
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
ma
i j v
0
1
2
3
4
5
6
7
8
ma[0].i,ma[0].j,ma[0].v分别存放矩阵行列维数和非零元个数行列下标 非零元值 7600070015
00000180
00002400
01400003
0000000
00009120
M
带辅助行向量的二元组表增加一个辅助数组 NRA[m+1],其物理意义是第 i行第一个非零元在二元组表中的起始地址（ m为行数）
显然有,POS[1]=1
POS[i]=POS[i-1]+第 i-1行非零元个数 (i?2)
0
1
2
3
4
5
6
POS
1
3
3
5
6
7
6 7 8
2 12
3 9
1 -3
6 14
3 24
2 18
1 15
4 -7
ma
j v
0
1
2
3
4
5
6
7
8
矩阵列数和非零元个数列下标和非零元值POS[0]不用或存矩阵行数二元组表需存储单元个数为 2(t+1)+m+1
7600070015
00000180
00002400
01400003
0000000
00009120
M
伪地址表示法伪地址：本元素在矩阵中（包括零元素）
按行优先顺序的相对位置
6 7
2 12
3 9
15 -3
20 14
24 24
30 18
36 15
39 -7
ma
addr v伪地址 非零元值矩阵行列维数0
1
2
3
4
5
6
7
8
伪地址表示法需存储单元个数为 2(t+1)
7600070015
00000180
00002400
01400003
0000000
00009120
M
求转置矩阵
问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表
问题分析一般矩阵转置算法：
for(col=0;col<n;col++)
for(row=0;row<m;row++)
n[col][row]=m[row][col];
T(n)=O(m?n)
7600070015
00000180
00002400
01400003
0000000
00009120
M
67000000
0001400
000000
700000
0024009
01800012
1500300
N
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
i j v
0
1
2
3
4
5
6
7
8
ma
i j v
7 6 8
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
0
1
2
3
4
5
6
7
8
mb
解决思路：只要做到
将矩阵行、列维数互换
将每个三元组中的 i和 j相互调换
重排三元组次序，使 mb中元素以 N的行 (M的列 )为主序方法一：按 M的列序转置即按 mb中三元组次序依次在 ma中找到相应的三元组进行转置。
为找到 M中每一列所有非零元素，需对其三元组表 ma从第一行起扫描一遍。由于 ma中以 M行序为主序,所以由此得到的恰是 mb
中应有的顺序
算法描述,
算法分析,T(n)=O(M的列数 n?非零元个数 t)
若 t 与 m?n同数量级，则 )()( 2nmOnT
Ch4_1.c
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
i j v
0
1
2
3
4
5
6
7
8 ma
7 6 8
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
i j v
0
1
2
3
4
5
6
7
8 mb
kp
p
p
p
p
p
p
p
k
k
k
k
p
p
p
p
p
p
p
p
col=1 col=2
方法二：快速转置即按 ma中三元组次序转置，转置结果放入 b中恰当位置此法关键是要预先确定 M中每一列第一个非零元在 mb中位置，
为确定这些位置，转置前应先求得 M的每一列中非零元个数实现：设两个数组
num[col]：表示矩阵 M中第 col列中非零元个数
cpot[col],指示 M中第 col列第一个非零元在 mb中位置显然有,cpot[1]=1;
cpot[col]=cpot[col-1]+num[col-1]; (2?col?ma[0].j)
1 3 5 7 8 8 9
col
num[col]
cpot[col]
1
2
2
2
3
2
4
1
5
0
6
1
7
0
7600070015
00000180
00002400
01400003
0000000
00009120
M
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
i j v
0
1
2
3
4
5
6
7
8 ma
i j v
0
1
2
3
4
5
6
7
8 mb
col
num[col]
cpot[col]
1
1
2
2
3
2
3
5
2
4
7
1
5
8
0
6
8
1
7
9
0
7 6 8
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
p
p
p
p
p
p
p
p
4 62 9
753
算法分析,T(n)=O(M的列数 n+非零元个数 t)
若 t 与 m?n同数量级，则 T(n)=O(m?n)
算法描述：
Ch4_2.c
链式存储结构
带行指针向量的单链表表示
每行的非零元用一个单链表存放
设置一个行指针数组，指向本行第一个非零元结点；若本行无非零元，则指针为空
表头结点与单链表结点类型定义typedef struct node{ int col;
int val;
struct node *link;
}JD;
typedef struct node *TD;
02000
00000
00021
00100
70003
A
^
1 3 5 7
3 -1
1 -1 2 -2
4 2 ^
^
^
^
需存储单元个数为 3t+m
链式存储结构
十字链表
设行指针数组和列指针数组，分别指向每行、
列第一个非零元
结点定义
typedef struct node
{ int row,col,val;
struct node *down,*right;
}JD;
row col val
down right
34008
000
450
003
A
1 1 3
4 1 8
2 2 5 2 3 4
^
^ ^
^
^ ^ ^
从键盘接收信息建立十字链表算法
算法分析,T(n)=o(t?s)
其中,t——非零元个数
s= max(m,n)
Ch4_3.c
令 q=NULL,p=rh[r-1],
（ 1） 寻找插入位置,当 p!=NULL且 c>p->col时,p和 q右移
（ 2）插入：
a、若 p==NULL且 q==NULL，即本行空,则 rh[r-1]==s;
b,若 p==NULL,q!=NULL,即走到行末，则 q->right=s
c,若 c==p->col,则修改 p->val
d,若 c<p->col且 q==NULL,则在 p之前插入 s,即 s是行链表中第一个结点，令 rh[r-1]=s; s->right=p;
e,若 c<p->col且 q!=NULL,则在 p之前插入 s，
即 s->right=p; q->right=s;
4 1 8
^ ^
2 3 4
^ ^
m=4,n=3
1,1,3
2,2,5
2,3,4
4,1,8
2,1,7
Ch4_3.c
1 1 3
^^
2 1 7
^ ^
2 2 5
^ ^
