,数据结构,
第五章
数据结构
tjm
第五章 数组
5.1 数组的定义
5.2 数组的顺序表示和实现
5.3 矩阵的压缩存储
5.3.1 特殊矩阵
5.3.2 稀疏矩阵
数据结构
tjm
数组可看成是一种特殊的线性表，其特殊在于,表
中的元素本身也是一种线性表 。
5.1 数组的定义
多维数组是向量（一维数组）的推广。
例如，二维数组：
a00 a01 … a0,n-1
a10 a11 … a1,n-1
… … … …
am-1,0 am-1,1 … am-1,n-1
Amn=
数组的抽象类型定义参见 P90。
数据结构
tjm
在 C语言中，一个二维数组类型可以定义为其分量类
型为一维数组类型的一维数组类型，也就是说，
typedef ElemType Array2[m][n];
等价于：
typedef ElemType Array1[n];
typedef Array1 Array2[m];
数组一旦被定义，它的维数和维界就不再改变。
因此，除了结构的初始化和销毁之外，数组的基本
操作只有 存取元素和修改元素值的操作 。
数据结构
tjm
5.2 数组的顺序表示和实现
由于计算机的内存结构是一维的，因此用一维内
存来表示多维数组，就必须按某种次序将数组元
素排成一个序列，然后将这个线性序列存放在存
储器中。
又由于对数组一般不做插入和删除操作，也就
是说，数组一旦建立，结构中的元素个数和元素
间的关系就不再发生变化。因此，一般都是采用
顺序存储 的方法来表示数组。
通常有两种顺序存储方式：
低下标优先
高下标优先
数据结构
tjm
对二维数组而言：
⑴ 以行序为主序 —— 将数组元素按行排列，第 i+1个行
向量紧接在第 i个行向量后面。
在 C语言中，数组就是按行优先顺序存储的。
⑵ 以列序为主序 —— 将数组元素按列排列，第 i+1个列
向量紧接在第 i个列向量后面。
在 FORTRAN语言中，数组就是按列优先顺序存储的。
只要知道开始结点的存放地址（即基地址），维数和
每维的上、下界，以及每个数组元素所占用的单元
数，就可以将数组元素的存放地址表示为其下标的
线性函数。因此，数组中的任一元素可以在相同的
时间内存取，即 顺序存储的数组是一个随机存取结
构 。
数据结构
tjm
一维数组
LOC ( i ) = LOC ( i -1 ) + l =α+ i*l
数组元素存储地址的计算：
数据结构
tjm
二维数组
行优先 LOC ( i,j )
= α + ( i * n + j ) * l
a00 a01 … a0,n-1
a10 a11 … a1,n-1
… … … …
am-1,0 am-1,1 … am-1,n-1
Amn=
数据结构
tjm
LOC ( j1,j2,…,jn ) = α +
( j1*b2*b3*…*bn + j2*b3*b4*…*bn
+ ……+ jn-1*bn + jn ) * l
各维元素个数为 b1,b2,b3,…,bn
下标为 j1,jj,j3,…,jn 的数组元素的存储地址：
最后的公式参见 P93
n维数组
数据结构
tjm
5.3 矩阵的压缩存储
高级语言编制程序时，常将一个矩阵描述为一个
二维数组。这种存储表示可以对元素随机存取，
各种矩阵运算也非常简单。
矩阵中非零元素呈某种规律分布或者矩阵中出现
大量的零元素 的情况下，存储空间大量浪费。
当一个矩阵中的元素有很多都是零时，零元素的
个数远大于非零元素，则称该矩阵为稀疏矩阵。
矩阵的压缩存储 —— 为多个相同的非零元素只分
配一个存储空间；对零元素不分配空间。
数据结构
tjm
5.3.1 特殊矩阵
—— 非零元素或零元素的分布有一定规律的矩阵。
1、对称矩阵
在一个 n阶方阵 A中，若元素满足下述性质：
aij=aji 0≦ i,j≦ n-1
则称 A为对称矩阵。
只要存储矩阵中上三角或下三角中的元素，让每两
个对称的元素共享一个存储空间，这样，能节约近
一半的存储空间。
例如，存下三角阵。
数据结构
tjm
下三角阵 sa[k]的下标 k和 aij的对应关系是：
i*(i+1)/2+j 当 i≧ j
j*(j+1)/2+i 当 i<jk=
在下三角矩阵中，第 i行恰有 i+1个元素，元素总数
为,n(n+1)/2
因此，可将这些元素存放在一个向量
sa[0..n(n+1)/2-1]中。为了便于访问对称矩阵
A中的元素，我们必须在 aij和 sa[k]之间找一个对应
关系。
a00 a10 a11 a20 …… …… …… an-1,n-1
k=0 1 2 3 …,n(n+1)/2 -1
数据结构
tjm
2、三角矩阵
上三角或下三角。
a00 a01 … a 0,n-1 a00 c … c
c a11 … a 1,n-1 a10 a11 … c
…… …………….,………… …….
c c … a n-1,n-1 an-1,0 an-1,1 … a n-1,n-1
(a)上三角矩阵 (b)下三角矩阵
数据结构
tjm
上三角阵 sa[k]的下标 k和 aij的对应关系是：
i(2n-i+1)/2+j-i 当 i≦ j
n(n+1)/2 当 i>jk=
下三角矩阵的存储和对称矩阵类似,sa[k]的下
标 k和 aij的 对应关系是：
i(i+1)/2+j 当 i≧ j
n(n+1)/2 当 i<jk=
数据结构
tjm
3、对角矩阵（带状矩阵）
对角矩阵中，所有的非零元素集中在以主对角线
为中心的带状区域中，即除了主对角线和主对角线
相邻两侧的若干条对角线上的元素之外，其余元素
皆为零。
主对角线
上面的带
下面的带
数据结构
tjm
对角矩阵可按行为主序或对角线的顺序，将其压
缩存储到一个向量中，并且也能找到每个非零元
素和向量下标的对应关系。
例：三对角矩阵
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
数据结构
tjm
如果按行为主序来存储，除第 0行和第 n-1行是 2
个元素外，每行的非零元素都是 3个，因此，需存
储的元素个数为 3n-2。 sa[0..3n-1]
a00 a01 a10 a11 a12 a21 ………….,a n-1 n-1
K=0 1 2 3 4 5 … … …… 3n -1
数组 sa中的元素 sa[k]与三对角带状矩阵中
的元素 aij存在一一对应关系，在 aij之前有 i行,共
有 3*i-1个非零元素，在第 i行，有 j-i+1个非零
元素。
故 sa[k]的下标 k和 aij的对应关系是,
k = 3*i-1+(j-i+1) =2*i+j
数据结构
tjm
压缩存储原则：只存矩阵的行列数和每个非零元
的行列下标及其值。例如,M由矩阵行列数
（ 6,7）和三元组 表 （ (1,2,12),(1,3,9),
(3,1,-3),(3,6,14),(4,3,24),(5,2,18),
(6,1,15),(6,4,-7) ）唯一确定。
5.3.2 稀疏矩阵
7600070015
00000180
00002400
01400003
0000000
00009120
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?M
数据结构
tjm
一、三元组顺序表
以顺序存储结构来表示三元组表。
#define MAXSIZE 12500
typedef struct
{ int i,j;
ElemType e;
}Triple;
typedef struct
{
Triple data[MAXSIZE+1];
int mu,nu,tu;
}TSMatrix;
数据结构
tjm
求转置矩阵
问题描述：已知一个稀疏矩阵的三元组表，
求该矩阵的转置矩阵的三元组表。
例如,
7600070015
00000180
00002400
01400003
0000000
00009120
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?M
67
000000
0001400
000000
700000
0024009
01800012
1500300
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?N
数据结构
tjm
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
M.data
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
N.data
i j v
思路：
1)将矩阵行、列数互换
2)将每个三元组中的 i和 j相互调换
3)重排三元组次序，使 N.data中元素以 N的行 (M的列 )
为主序
三元组表 M的 mu,nu,tu的值分别为,6,7,8
三元组表 N的 mu,nu,tu的值分别为,7,6,8
数据结构
tjm
方法一,即按 N.data中三元组次序依次在 M.data
中找到相应的三元组进行转置。
为找到 M中每一列所有非零元素，需对其三元组表
M.data从第一行起扫描一遍。由于 M.data中以
M行序为主序,所以由此得到的恰是 N.data中应
有的顺序 。
数据结构
tjm
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 e
1
2
3
4
5
6
7
8
M.data
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 e
1
2
3
4
5
6
7
8
N.data
qp
p
p
p
p
p
p
p
q
q
q
q
p
p
p
p
p
p
p
p
col=1 col=2
算法示意：
数据结构
tjm
而一般传统矩阵的转置算法为：
for(col=0;col<=n-1;++col)
for(row=0;row<=m;++row)
t[col][row]=m[row][col];
其时间复杂度为 O(n*m)。
时间复杂度分析,T(n)=O(nu?tu),nu为 矩
阵 M的列数,tu为非零元个 数。
若 tu与 m?n同数量级
)()( 2nmOnT ??
算法参见 P99
三元组顺序表虽节省存储空间，但时间复杂度比一
般矩阵转置的算法还要复杂，同时还有可能增加算
法的难度。因此，此算法仅适用于 t<=m*n的情况。
数据结构
tjm
方法二,快速转置的算法。
算法思想为,按 M.data中三元组次序转置，转置
结果放入 N.data中恰当位置 。
此法关键是要预先确定 M中每一列第一个非零元在
N.data中位置，为确定这些位置，转置前应先求
得 M的每一列中非零元个数 。实现：设两个数组：
num[col]：表示矩阵 M中第 col列中非零元个数。
cpot[col],指示 M中第 col列第一个非零元在
N.data中的位置。
cpot[1]=1;
cpot[col]=cpot[col-1]+num[col-1]; (2?col ?M.nu)
则,
数据结构
tjm
快速转置算法参见 P100
时间复杂度分析,T(n)=O(nu+tu),nu为 矩阵 M的列
数,tu为非零元个 数。
若 tu与 m?n同数量级，则 )()( nmOnT ??
76
00070015
00000180
00002400
01400003
0000000
00009120
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?M
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
数据结构
tjm
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 e
1
2
3
4
5
6
7
8
M.data
i j e
1
2
3
4
5
6
7
8
N.data
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
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
数据结构
tjm
二、行逻辑链接的顺序表（带行表的三元组表）
有时为了方便某些矩阵运算，我们在按行存储的三
元组中，加入一个行表来记录稀疏矩阵中每行的非
零元素在三元组表中的起始位置。当将行表作为三
元组表的一个新增属性加以描述时，我们就得到了
稀疏矩阵的另一种顺序存储结构：带行表的三元组
表。其类型描述如下：
typedef struct
{ Triple data[MAXSIZE+1];
int rpos[MAXRC+1];
int mu,nu,tu;
}RLSMatrix;
数据结构
tjm
两个矩阵相乘的经典算法,
若设 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)。
数据结构
tjm
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=
例如 M和 N分别为：
数据结构
tjm
M和 N的三元组、和分别为：
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和 N是稀疏矩阵并用三元组表存储结构时，
经典算法不再适用。
数据结构
tjm
稀疏矩阵相乘的 基本思想 是：
对于 M中每个元素 M.data[p]，找到 N 中所有
满足条件 M.data[p].j==N.data[q].i的元素
N.data[q]，求得 M.data[p].e和
N.data[q].e的乘积，而从求乘积的式子得知，
乘积矩阵 Q中每个元素的值是个累加和，这个乘
积 M.data[p].e * N.data[q].e只是其中的
一部分。为了便于操作，应对每个元素设一累加
和的变量，其初值为零，然后扫描三元组表 M，
求得相应元素的乘积并累加到适当的累加器上。
算法参见 P102
数据结构
tjm
row col val
down right
34008
000
450
003
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?A
1 1 3
4 1 8
2 2 5 2 3 4
^
^ ^
^
^ ^ ^
链式存储结构（十字链表）
设行指针数组和列指针数组，分别指向每行、列第一
个非零元。
结点：
数据结构
tjm
广义表也称为列表，是线性表的一种扩展。 记
作,LS=(d1,d2,.,,,,,dn)
其中 di既可以是单个元素，也可以是广义表。
说明, 1）广义表的定义是一个递归定义，因为
在描述广义表时又用到了广义表；
2）在线性表中数据元素是单个元素，而在广义
表中,元素可以是单个元素,称为单元素 (原子 )，
也可以是广义表，称为广义表的子表；
3） n 是广义表长度；
5.4 广义表的定义
什么是广义表
数据结构
tjm
4）广义表示例,
A = ( ) 空表，表长为 0；
B = (a,(b,c,d)) 表长为 2，两个元素分别为 a 和子表
（ b,c,d)；
C = (e) C中只有一个元素 e，表长为 1；
D = (A,B,C,f ) D 的表长为 4，它的前三个元素 A,B，
C 为广义表,第四个是单元素；
E=( a,E ) 递归表。
5）若广义表不空，则可分成表头和表尾，反之，一对表头
和表尾可唯一确定广义表。
对非空广义表：称第一个元素为 表头,其余元素组成的表称
为 表尾 。
广义表最重要的两个基本操作,1） 取表头； 2） 取表尾。
数据结构
tjm
例如：
B = (a,(b,c,d)) 表头,a,表尾 ((b,c,d))
即 HEAD（ B） =a,TAIL(B)=((b,c,d))
C = (e) 表头,e 表尾 ( )
D = (A,B,C,f ) 表头,A 表尾 (B,C,f )
运算可以嵌套，如：
HEAD（ TAIL（ B）） = (b,c,d)
TAIL(TAIL(B))=( )
广义表的元素之间除了存在次序关系外，还存在层次
关系。如,D
A B C
f
a e
b c d
数据结构
tjm
由于广义表中数据元素可以具有不同结构，故难以用顺
序结构表示广义表。通常采用链表存储方式。
单元素结点
tag=0 data tp
5.5 广义表的存储结构
如何设定链表结点？
广义表中的数据元素可能为单元素 (原子 )或子表，由此
需要两种结点：一种是表结点，用以表示广义表；一种
是单元素结点，用以表示单元素（原子）。
表结点
tag=1 hp tp
数据结构
tjm
广义表的存储结构示例, A =（）,B =(a,(b,c,d)),C = (e),
D = (A,B,C,f ),E = (a,E)
∧1A ∧
∧1C
∧0 e 0 ∧
B 1
1
0 c
∧0 a
D
1
1 ∧
∧
0 b d
∧ 1 0 ∧1 f
E
1
1 ∧0 a
∧
∧
∧
∧
∧
∧ ∧
∧
数据结构
tjm
广义表 LS = ( ?1,?2,?3,?4,…,?n )
depth ( LS ) 的递归定义：
基本项, depth ( LS ) = 1 当 LS 为空表时
depth ( LS ) = 0 当 LS 为原子时
归纳项, depth ( LS ) = 1 + Max {depth( ?i )}
其中,1 <= i <= n,n >= 1
广义表是递归结构，故许多操作可以用递归算法实现。
5.7 广义表的递归算法
求广义表的深度
广义表的深度 =广义表中括号重数
例,A=（）,B = (e), C = (a,(b,c,d)), D = (A,B,C)
depth(A)=1 depth(B)=1 depth(C)=2 depth(D)=3
算法 参见 P114算法 5.5
第五章
数据结构
tjm
第五章 数组
5.1 数组的定义
5.2 数组的顺序表示和实现
5.3 矩阵的压缩存储
5.3.1 特殊矩阵
5.3.2 稀疏矩阵
数据结构
tjm
数组可看成是一种特殊的线性表，其特殊在于,表
中的元素本身也是一种线性表 。
5.1 数组的定义
多维数组是向量（一维数组）的推广。
例如，二维数组：
a00 a01 … a0,n-1
a10 a11 … a1,n-1
… … … …
am-1,0 am-1,1 … am-1,n-1
Amn=
数组的抽象类型定义参见 P90。
数据结构
tjm
在 C语言中，一个二维数组类型可以定义为其分量类
型为一维数组类型的一维数组类型，也就是说，
typedef ElemType Array2[m][n];
等价于：
typedef ElemType Array1[n];
typedef Array1 Array2[m];
数组一旦被定义，它的维数和维界就不再改变。
因此，除了结构的初始化和销毁之外，数组的基本
操作只有 存取元素和修改元素值的操作 。
数据结构
tjm
5.2 数组的顺序表示和实现
由于计算机的内存结构是一维的，因此用一维内
存来表示多维数组，就必须按某种次序将数组元
素排成一个序列，然后将这个线性序列存放在存
储器中。
又由于对数组一般不做插入和删除操作，也就
是说，数组一旦建立，结构中的元素个数和元素
间的关系就不再发生变化。因此，一般都是采用
顺序存储 的方法来表示数组。
通常有两种顺序存储方式：
低下标优先
高下标优先
数据结构
tjm
对二维数组而言：
⑴ 以行序为主序 —— 将数组元素按行排列，第 i+1个行
向量紧接在第 i个行向量后面。
在 C语言中，数组就是按行优先顺序存储的。
⑵ 以列序为主序 —— 将数组元素按列排列，第 i+1个列
向量紧接在第 i个列向量后面。
在 FORTRAN语言中，数组就是按列优先顺序存储的。
只要知道开始结点的存放地址（即基地址），维数和
每维的上、下界，以及每个数组元素所占用的单元
数，就可以将数组元素的存放地址表示为其下标的
线性函数。因此，数组中的任一元素可以在相同的
时间内存取，即 顺序存储的数组是一个随机存取结
构 。
数据结构
tjm
一维数组
LOC ( i ) = LOC ( i -1 ) + l =α+ i*l
数组元素存储地址的计算：
数据结构
tjm
二维数组
行优先 LOC ( i,j )
= α + ( i * n + j ) * l
a00 a01 … a0,n-1
a10 a11 … a1,n-1
… … … …
am-1,0 am-1,1 … am-1,n-1
Amn=
数据结构
tjm
LOC ( j1,j2,…,jn ) = α +
( j1*b2*b3*…*bn + j2*b3*b4*…*bn
+ ……+ jn-1*bn + jn ) * l
各维元素个数为 b1,b2,b3,…,bn
下标为 j1,jj,j3,…,jn 的数组元素的存储地址：
最后的公式参见 P93
n维数组
数据结构
tjm
5.3 矩阵的压缩存储
高级语言编制程序时，常将一个矩阵描述为一个
二维数组。这种存储表示可以对元素随机存取，
各种矩阵运算也非常简单。
矩阵中非零元素呈某种规律分布或者矩阵中出现
大量的零元素 的情况下，存储空间大量浪费。
当一个矩阵中的元素有很多都是零时，零元素的
个数远大于非零元素，则称该矩阵为稀疏矩阵。
矩阵的压缩存储 —— 为多个相同的非零元素只分
配一个存储空间；对零元素不分配空间。
数据结构
tjm
5.3.1 特殊矩阵
—— 非零元素或零元素的分布有一定规律的矩阵。
1、对称矩阵
在一个 n阶方阵 A中，若元素满足下述性质：
aij=aji 0≦ i,j≦ n-1
则称 A为对称矩阵。
只要存储矩阵中上三角或下三角中的元素，让每两
个对称的元素共享一个存储空间，这样，能节约近
一半的存储空间。
例如，存下三角阵。
数据结构
tjm
下三角阵 sa[k]的下标 k和 aij的对应关系是：
i*(i+1)/2+j 当 i≧ j
j*(j+1)/2+i 当 i<jk=
在下三角矩阵中，第 i行恰有 i+1个元素，元素总数
为,n(n+1)/2
因此，可将这些元素存放在一个向量
sa[0..n(n+1)/2-1]中。为了便于访问对称矩阵
A中的元素，我们必须在 aij和 sa[k]之间找一个对应
关系。
a00 a10 a11 a20 …… …… …… an-1,n-1
k=0 1 2 3 …,n(n+1)/2 -1
数据结构
tjm
2、三角矩阵
上三角或下三角。
a00 a01 … a 0,n-1 a00 c … c
c a11 … a 1,n-1 a10 a11 … c
…… …………….,………… …….
c c … a n-1,n-1 an-1,0 an-1,1 … a n-1,n-1
(a)上三角矩阵 (b)下三角矩阵
数据结构
tjm
上三角阵 sa[k]的下标 k和 aij的对应关系是：
i(2n-i+1)/2+j-i 当 i≦ j
n(n+1)/2 当 i>jk=
下三角矩阵的存储和对称矩阵类似,sa[k]的下
标 k和 aij的 对应关系是：
i(i+1)/2+j 当 i≧ j
n(n+1)/2 当 i<jk=
数据结构
tjm
3、对角矩阵（带状矩阵）
对角矩阵中，所有的非零元素集中在以主对角线
为中心的带状区域中，即除了主对角线和主对角线
相邻两侧的若干条对角线上的元素之外，其余元素
皆为零。
主对角线
上面的带
下面的带
数据结构
tjm
对角矩阵可按行为主序或对角线的顺序，将其压
缩存储到一个向量中，并且也能找到每个非零元
素和向量下标的对应关系。
例：三对角矩阵
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
数据结构
tjm
如果按行为主序来存储，除第 0行和第 n-1行是 2
个元素外，每行的非零元素都是 3个，因此，需存
储的元素个数为 3n-2。 sa[0..3n-1]
a00 a01 a10 a11 a12 a21 ………….,a n-1 n-1
K=0 1 2 3 4 5 … … …… 3n -1
数组 sa中的元素 sa[k]与三对角带状矩阵中
的元素 aij存在一一对应关系，在 aij之前有 i行,共
有 3*i-1个非零元素，在第 i行，有 j-i+1个非零
元素。
故 sa[k]的下标 k和 aij的对应关系是,
k = 3*i-1+(j-i+1) =2*i+j
数据结构
tjm
压缩存储原则：只存矩阵的行列数和每个非零元
的行列下标及其值。例如,M由矩阵行列数
（ 6,7）和三元组 表 （ (1,2,12),(1,3,9),
(3,1,-3),(3,6,14),(4,3,24),(5,2,18),
(6,1,15),(6,4,-7) ）唯一确定。
5.3.2 稀疏矩阵
7600070015
00000180
00002400
01400003
0000000
00009120
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?M
数据结构
tjm
一、三元组顺序表
以顺序存储结构来表示三元组表。
#define MAXSIZE 12500
typedef struct
{ int i,j;
ElemType e;
}Triple;
typedef struct
{
Triple data[MAXSIZE+1];
int mu,nu,tu;
}TSMatrix;
数据结构
tjm
求转置矩阵
问题描述：已知一个稀疏矩阵的三元组表，
求该矩阵的转置矩阵的三元组表。
例如,
7600070015
00000180
00002400
01400003
0000000
00009120
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?M
67
000000
0001400
000000
700000
0024009
01800012
1500300
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?N
数据结构
tjm
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
M.data
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
N.data
i j v
思路：
1)将矩阵行、列数互换
2)将每个三元组中的 i和 j相互调换
3)重排三元组次序，使 N.data中元素以 N的行 (M的列 )
为主序
三元组表 M的 mu,nu,tu的值分别为,6,7,8
三元组表 N的 mu,nu,tu的值分别为,7,6,8
数据结构
tjm
方法一,即按 N.data中三元组次序依次在 M.data
中找到相应的三元组进行转置。
为找到 M中每一列所有非零元素，需对其三元组表
M.data从第一行起扫描一遍。由于 M.data中以
M行序为主序,所以由此得到的恰是 N.data中应
有的顺序 。
数据结构
tjm
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 e
1
2
3
4
5
6
7
8
M.data
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 e
1
2
3
4
5
6
7
8
N.data
qp
p
p
p
p
p
p
p
q
q
q
q
p
p
p
p
p
p
p
p
col=1 col=2
算法示意：
数据结构
tjm
而一般传统矩阵的转置算法为：
for(col=0;col<=n-1;++col)
for(row=0;row<=m;++row)
t[col][row]=m[row][col];
其时间复杂度为 O(n*m)。
时间复杂度分析,T(n)=O(nu?tu),nu为 矩
阵 M的列数,tu为非零元个 数。
若 tu与 m?n同数量级
)()( 2nmOnT ??
算法参见 P99
三元组顺序表虽节省存储空间，但时间复杂度比一
般矩阵转置的算法还要复杂，同时还有可能增加算
法的难度。因此，此算法仅适用于 t<=m*n的情况。
数据结构
tjm
方法二,快速转置的算法。
算法思想为,按 M.data中三元组次序转置，转置
结果放入 N.data中恰当位置 。
此法关键是要预先确定 M中每一列第一个非零元在
N.data中位置，为确定这些位置，转置前应先求
得 M的每一列中非零元个数 。实现：设两个数组：
num[col]：表示矩阵 M中第 col列中非零元个数。
cpot[col],指示 M中第 col列第一个非零元在
N.data中的位置。
cpot[1]=1;
cpot[col]=cpot[col-1]+num[col-1]; (2?col ?M.nu)
则,
数据结构
tjm
快速转置算法参见 P100
时间复杂度分析,T(n)=O(nu+tu),nu为 矩阵 M的列
数,tu为非零元个 数。
若 tu与 m?n同数量级，则 )()( nmOnT ??
76
00070015
00000180
00002400
01400003
0000000
00009120
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?M
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
数据结构
tjm
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 e
1
2
3
4
5
6
7
8
M.data
i j e
1
2
3
4
5
6
7
8
N.data
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
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
数据结构
tjm
二、行逻辑链接的顺序表（带行表的三元组表）
有时为了方便某些矩阵运算，我们在按行存储的三
元组中，加入一个行表来记录稀疏矩阵中每行的非
零元素在三元组表中的起始位置。当将行表作为三
元组表的一个新增属性加以描述时，我们就得到了
稀疏矩阵的另一种顺序存储结构：带行表的三元组
表。其类型描述如下：
typedef struct
{ Triple data[MAXSIZE+1];
int rpos[MAXRC+1];
int mu,nu,tu;
}RLSMatrix;
数据结构
tjm
两个矩阵相乘的经典算法,
若设 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)。
数据结构
tjm
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=
例如 M和 N分别为：
数据结构
tjm
M和 N的三元组、和分别为：
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和 N是稀疏矩阵并用三元组表存储结构时，
经典算法不再适用。
数据结构
tjm
稀疏矩阵相乘的 基本思想 是：
对于 M中每个元素 M.data[p]，找到 N 中所有
满足条件 M.data[p].j==N.data[q].i的元素
N.data[q]，求得 M.data[p].e和
N.data[q].e的乘积，而从求乘积的式子得知，
乘积矩阵 Q中每个元素的值是个累加和，这个乘
积 M.data[p].e * N.data[q].e只是其中的
一部分。为了便于操作，应对每个元素设一累加
和的变量，其初值为零，然后扫描三元组表 M，
求得相应元素的乘积并累加到适当的累加器上。
算法参见 P102
数据结构
tjm
row col val
down right
34008
000
450
003
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?A
1 1 3
4 1 8
2 2 5 2 3 4
^
^ ^
^
^ ^ ^
链式存储结构（十字链表）
设行指针数组和列指针数组，分别指向每行、列第一
个非零元。
结点：
数据结构
tjm
广义表也称为列表，是线性表的一种扩展。 记
作,LS=(d1,d2,.,,,,,dn)
其中 di既可以是单个元素，也可以是广义表。
说明, 1）广义表的定义是一个递归定义，因为
在描述广义表时又用到了广义表；
2）在线性表中数据元素是单个元素，而在广义
表中,元素可以是单个元素,称为单元素 (原子 )，
也可以是广义表，称为广义表的子表；
3） n 是广义表长度；
5.4 广义表的定义
什么是广义表
数据结构
tjm
4）广义表示例,
A = ( ) 空表，表长为 0；
B = (a,(b,c,d)) 表长为 2，两个元素分别为 a 和子表
（ b,c,d)；
C = (e) C中只有一个元素 e，表长为 1；
D = (A,B,C,f ) D 的表长为 4，它的前三个元素 A,B，
C 为广义表,第四个是单元素；
E=( a,E ) 递归表。
5）若广义表不空，则可分成表头和表尾，反之，一对表头
和表尾可唯一确定广义表。
对非空广义表：称第一个元素为 表头,其余元素组成的表称
为 表尾 。
广义表最重要的两个基本操作,1） 取表头； 2） 取表尾。
数据结构
tjm
例如：
B = (a,(b,c,d)) 表头,a,表尾 ((b,c,d))
即 HEAD（ B） =a,TAIL(B)=((b,c,d))
C = (e) 表头,e 表尾 ( )
D = (A,B,C,f ) 表头,A 表尾 (B,C,f )
运算可以嵌套，如：
HEAD（ TAIL（ B）） = (b,c,d)
TAIL(TAIL(B))=( )
广义表的元素之间除了存在次序关系外，还存在层次
关系。如,D
A B C
f
a e
b c d
数据结构
tjm
由于广义表中数据元素可以具有不同结构，故难以用顺
序结构表示广义表。通常采用链表存储方式。
单元素结点
tag=0 data tp
5.5 广义表的存储结构
如何设定链表结点？
广义表中的数据元素可能为单元素 (原子 )或子表，由此
需要两种结点：一种是表结点，用以表示广义表；一种
是单元素结点，用以表示单元素（原子）。
表结点
tag=1 hp tp
数据结构
tjm
广义表的存储结构示例, A =（）,B =(a,(b,c,d)),C = (e),
D = (A,B,C,f ),E = (a,E)
∧1A ∧
∧1C
∧0 e 0 ∧
B 1
1
0 c
∧0 a
D
1
1 ∧
∧
0 b d
∧ 1 0 ∧1 f
E
1
1 ∧0 a
∧
∧
∧
∧
∧
∧ ∧
∧
数据结构
tjm
广义表 LS = ( ?1,?2,?3,?4,…,?n )
depth ( LS ) 的递归定义：
基本项, depth ( LS ) = 1 当 LS 为空表时
depth ( LS ) = 0 当 LS 为原子时
归纳项, depth ( LS ) = 1 + Max {depth( ?i )}
其中,1 <= i <= n,n >= 1
广义表是递归结构，故许多操作可以用递归算法实现。
5.7 广义表的递归算法
求广义表的深度
广义表的深度 =广义表中括号重数
例,A=（）,B = (e), C = (a,(b,c,d)), D = (A,B,C)
depth(A)=1 depth(B)=1 depth(C)=2 depth(D)=3
算法 参见 P114算法 5.5
