,数据结构,
第五章 数组和广义表第五章 数组和广义表第 2页内容和要求
● 内容和要求数组和广义表的概念,存储结构和矩阵的压缩 存储方法 。
要求对数组和广义表有较深刻的了解。掌握数组和广义表的概念，熟悉它们的存储结构及基本应用。
● 重点数组和广义表的存储特性,稀疏矩阵存储。
第五章 数组和广义表第 3页二维数组的逻辑结构数组和广义表可以看成是线性表在下述含义上的扩展,即线性表中的数据元素本身也是一个数据结构。
类似于线性表，一个二维数组的逻辑结构可形式地表示为
2-Array=(D,R) (5-1)
其中
D={aij|i=c1,c1+1,···,d1,j= c2,c2+1,···,d2,aij∈ D0}
R={Row,Col} //行关系，列关系
Row={<aij,ai,j+1>| c1≤i≤d1,c2≤j≤d2-1,aij,ai,j+1 ∈ D}
Col={<aij,ai+1,j>| c1≤i≤d1-1,c2≤j≤d2,aij,ai+1,j ∈ D}
D0为某个数据对象,c1,c2,d1,d2均为整数。
数组的逻辑结构第五章 数组和广义表第 4页若 c1=1,d1=m,c2=1,d2=n,则有
D={aij|i=1,2,···,m,j= 1,2,···,n,∈ D0}
R={Row,Col}
Row={<aij,ai,j+1>| i=1,2,···,m,j=1,2,···,n-1,aij,ai,j+1∈ D}
Col={<aij,ai+1,j>| i=1,2,···,m-1,j=1,2,···,n,aij,ai+1,j ∈ D}
记作 Am× n，即 A为 m行 n列的二维数组 (起始下标为 1)。
说明：
1) 用于二维数组的抽象可称之为矩阵，它是对向量的推广，其元素个数为 m× n个。
数组的逻辑结构
mnmm
n
n
nm
aaa
aaa
aaa
A
21
22221
11211
第五章 数组和广义表第 5页
2) 二维数组也可以看作是这样一个线性表,它的每一个数据元素是一个线性表 。从而对二维数组可以进行递归定义，即它是数据元素为一维数组的线性表。可把 Am× n看成是由 m个行向量所组成的向量（线性表），也可以看成是 n个列向量所组成的向量。
Am× n=(α1,α 2,···,α p) (p=m或 n)
若 α i为行向量,α i = (ai1,ai2,···,ain) 1≤i≤m
若 α j为列向量,α j = (a1j,a2j,···,amj) 1≤j≤n
数组的逻辑结构
3) 二维数组中的每个元素都属于 两个向 量,第 i行的行向量和第 j列的列向量（对元素 aij而言 ）。
4) 每个元素 aij有两个前趋结点 ai-1,j和 ai,j-1(2≤i≤m,2≤j≤n)，两个后继结点 ai+1,j和 ai,j+1(1≤i≤m-1,1≤j≤n-1)，其中 a11无前趋,amn无后继。边界上的结点 a1j(j=2,···,n),amj(j=1,···,n-1)和 ain(i=1,···,m-1)都只有一个后继结点或者只有一个前趋结点。
第五章 数组和广义表第 6页
n(n>2)维数组的逻辑结构
n维数组的逻辑结构的形式定义
)25(),( RDA rra yn
Daa
djc
iknkdjc
aaR
RRRR
dcDa
nnidccj
aD
RDA r r a yn
nini
nini
n
n
jjjjjj
iii
kkk
jjjjjji
n
iijjj
iiii
jjj
1
1,,
21
0,
1
,
11
11
21
21
,
1
1,
,
,,,
,
)0(,2,1,,,,
)25(),(
且均为整数和且其中说明：
1） n维数组的元素个数为 n1·n 2· ··· ·nn=? ni.
2） n维数组中每个数据元素都属于 n个向量（受 n个关系制约）
，除边界上的元素外，均可以有 n个前趋和 n个后继。
数组的逻辑结构第五章 数组和广义表第 7页
N维数组的递归定义
DAA
dic
AAAR
ARR
kAk
DAk
dicA
D
nkRDA r r a yK
k
i
k
i
knkkn
k
i
k
i
k
k
i
k
i
knkkn
k
i
k
kk
kk
kk
k
k
k
)(
1
)(
11
)(
1
)(
)(
)(
0
)(
11
)(
)(
)()(
,
,
1,1
,1
)35()1)(,(_
维数组是时时其中在这递归定义中，一个 k维数组是其数据元素为 k-1维数组的线性表,cn-k+1和 dn-k+1是第 k维下标的一对界偶。
n维数组是一种较复杂的数据结构，但它可以由简单的数据结构 —— 线性表辗转合成而得。
数组的逻辑结构第五章 数组和广义表第 8页数组的操作一个数组中所有的数据元素都必须属于同一数据类型。
对于数组，通常只有两种基本操作：
1）给定一组下标，存取相应的数据元素。
2）给定一组下标，修改相应数据元素中的某一个或几个数据项的值。
注,对于二维数组的抽象即矩阵，可包含取值、赋值和初始化等操作。编译程序用线性存储器来实现矩阵。
数组的逻辑结构第五章 数组和广义表第 9页数组的 顺序存储结构,用一组 连续的 存储单元顺序地存放数组中的诸数组元素。
数据元素的存放次序 问题,解决存储单元是一维结构，而数组是个多维结构的矛盾。
（指多维数组）
二维数组元素间次序的 排列方法,行优先与 列优先 序。
行优先序：按以行序为主序进行排列，就是把数组元素按行表次序、第 i+1行的元素紧跟在第 i行元素后面进行存储。
（列） （列）
（列） （ j+1列）
（ j列）
数组的顺序存储结构第五章 数组和广义表第 10页示例,w是一个 3*4的整数数组（起始下标从 1开始）。
设二维数组变量 w的诸数据组元素值如下表所示
1 2 3 4
1 0 -1 4 5
2 8 2 0 -3
3 -5 1 2 0
以 列序 为主序的存储方式 ——
列优先序以 行序 为主序的存储方式 ——
行优先序0
8
-5
-1
2
1
4
0
2
5
-3
0
第 1列第 2列第 3列第 4列
0
-1
4
5
8
2
0
-3
-5
1
2
0
第 1行第 2行第 3行
C,Pascal,BASIC,PL/1,COBOL等中采用FORTRAN中采用下面讨论的是按 行为主序 规则存储的情形。
数组的顺序存储结构第五章 数组和广义表第 11页同样，对于 n维数组也有上述两种不同的顺序存储方式,以左下标 为主序的存储方式和以 右下标 为主序的存储方式。
把 n维数组的元素按上述方式顺序存放在存储单元中，则每个元素的存储地址可以用一个公式计算出来，这个公式称为,地址公式,。
计算存储地址：对于 A[1..m,1..n]，设每个数组元素占 L个存储单元。
mnmm
n
n
aaa
aaa
aaa
A
21
22221
11211
i→
j
↓
aij
LOC[1,1]
↓
注,以左下标为主序，指主序变化最慢（实现时为最外层循环）
数组的顺序存储结构不同程序设计语言中数组的起始下标不完全相同,C语言起始下标为 0，
Pascal为 1，某些 4GL则允许定义起始下标。
第五章 数组和广义表第 12页记 a11的存储地址为 LOC[1,1]，它即是二维数组 A的起始存储位置，或称基地址（
首地址）,L为元素所占的单元数。
记 aij(1≤i≤m,1≤j≤n)的存储地址为 LOC[i,j]，
则
LOC[i,j]=LOC[1,1]+ [n*(i-1)+(j-1)]*L.
以二维数组为例，先讨论简化情况（ c1=1,d1=m,c2=1，
d2=n），再讨论一般情况（下标分别为 c1,d1,c2,d2）,
数组的顺序存储结构一般地，对于 A[c1..d1,c2..d2]，则有
Loc[i,j] = Loc[c1,c2] +
[(d2-c2+1)(i- c1)+(j- c2)]*L
其中 LOC[c1,c2]是二维数组 A的基地址。
C语言起始下标从 0开始，则
Loc[i,j] = Loc[0,0] + ( n*i + j ) * L
mnmm
n
n
aaa
aaa
aaa
A
21
22221
11211
i→
j
↓
aij
LOC[1,1]
↓
第五章 数组和广义表第 13页
LOC[j1,j2,j3]=LOC[c1,c2,c3]+[(d2-c2+1) (d3-c3+1)(j1-c1)+(d3-c3+1) (j2-c2)+ (j3-c3)]*L
对于三维数组 A[c1..d1,c2..d2,c3..d3]，设基地址为 LOC[c1,c2,c3],
则
.1)1(,3
31),1(
)(],,[
)]()1()([
],,[
3
1
3
1
3
1
321
33
2
1
3
1
321
kk
ik
kk
ik
i
i
iii
kk
i
ik
ii
cdi
icdl
cjcccL O C
lcjcdcj
cccL O C
令时当其中
数组的顺序存储结构第五章 数组和广义表第 14页上已推导出，对于三维数组 A[c1..d1,c2..d2,c3..d3]，
设基地址为 LOC[c1,c2,c3]，则
.1)1(,
1),1(
)55(),(
],,[],,[
],..,..,..[
.1)1(,3
31),1(
)(
],,[],,[
1
1
1
2121
2211
3
1
3
1
3
1
321321
kk
n
ik
kk
n
ik
i
n
i
iii
nn
nn
kk
ik
kk
ik
i
i
iii
cdni
nicdl
cj
cccL O CjjjL O C
dcdcdcAn
cdi
icdl
cj
cccL O CjjjL O C
时其中有维数组推广至时当其中
第五章 数组和广义表第 15页
mnmm
n
n
aaa
aaa
aaa
A
21
22221
11211
矩阵,在科学研究和工程计算中经常用到的一种数学工具，是研究的主要数学对象之一。
矩阵的存储,一般情况下，可用二维数组实现。
二维数组，通常也就称为矩阵，是数学上的一种重要数据结构。
m× n
矩阵压缩存储的概念第五章 数组和广义表第 16页矩阵的压缩存储,对于一些结构比较特殊的矩阵可采用压缩存储方式,即只存储矩阵中的部分元素而不丢失矩阵中任何信息的存储方式。同时，还需保证矩阵的各种运算能有效地进行。
在矩阵阶数很高且矩阵中有许多值 相同的元素 或 零元素 时，为多个值相同的元素分配一个存储空间，对零元素不分配空间，从而可以大量 节省存储空间 。
特殊矩阵,值相同的元素或零元素在矩阵中的分布有一定规律。
稀疏矩阵,矩阵中非零元素较之零元素要少得多，
且非零元素的分布没有一定规律。
矩阵压缩存储的概念第五章 数组和广义表第 17页所谓共享存储空间是指 aij与 aji 经计算后都指向同一个存储单元研究 对称矩阵,三角矩阵 （上三角矩阵、下三角矩阵）,对角矩阵 （三对角矩阵、带状矩阵）等特殊矩阵的压缩存储问题。
（ 1）对称矩阵的压缩存储定义 若一个 n阶矩阵（方阵） A中的元素满足下述性质
aij= aji (1≤i,j≤n)
则称 A为 n阶对称矩阵。
示例 一个 5阶对称矩阵
1 5 1 3 7
5 0 8 0 0
1 8 9 2 6
3 0 2 5 1
7 0 6 1 3
对称矩阵中的元素关于主对角线对称，故仅需存储矩阵中上三角或下三角中的元素，让每一对对称的元素 共享一个存储空间
。
特殊矩阵的压缩存储第五章 数组和广义表第 18页
1 5 1 3 7
5 0 8 0 0
1 8 9 2 6
3 0 2 5 1
7 0 6 1 3
a11
a21 a22
a31 a32 a33
a41 a42 a43 a44
a51 a52 a53 a54 a55
对称矩阵以行为主序存储下三角矩阵的元素
a11
a21 a22
a31 a32 a33
… …
… … …
an1 an2 an3 … ann
对称矩阵 Ann以行为主序存储下三角矩阵的元素,2
)1(
21
1
nn
ni
n
i
对于 An× n所对应的下三角矩阵中（见右下图），
第 i(1≤i≤n)行恰有 i个元素，
故元素总数为
aij
特殊矩阵的压缩存储第五章 数组和广义表第 19页设以一维数组 sa（ 1:n(n+1)/2）作为 n阶对称矩阵 A的存储结构，令 sa[k] aij，则有如下之一一对应关系?
)(
2
)1(
)1(321
jijii
jik
特殊矩阵的压缩存储
a11
a21 a22
a31 a32 a33
… …
… … …
an1 an2 an3 … amn
aij
第五章 数组和广义表第 20页由上述推导可得
)65(
,,
2
)1(
,,
2
)1(
,.
2
)1(
],[,,
.
2
)1(
],[,
不包括主对角线上三角当包括主对角线下三角当故有互换上式令则令当同理则令当
jii
jj
jij
ii
k
jii
jj
k
ksaaji
j
ii
k
ksaaji
ij
ij
特殊矩阵的压缩存储第五章 数组和广义表第 21页
（ 2）三角矩阵的压缩存储以主对角线划分，三角矩阵有上三角矩阵和下三角矩阵两种。
a11 a12 · · · a1n
c a22 · · · a2n
… …
c c … ann
a11 c · · · c
a21 a22 · · · c
… …
an1 an2 · · · ann
上三角矩阵 下三角矩阵在多数情况下，三角矩阵的常数 c为零。故可将三角矩阵表示为
a11 a12 · · · a1n
a22 · · · a2n
… …
ann
a11
a21 a22
… …
an1 an2 · · · ann
上三角矩阵 (c=0) 下三角矩阵 (c=0)
n阶三角矩阵 A的压缩存储 —— sa[1..n(n+1)/2+1],其中
n(n+1)/2个存储空间存放上（或下）三角矩阵的元素,1个存储空间存放常数 C。
特殊矩阵的压缩存储第五章 数组和广义表第 22页
a11 a12 … a 1n 第 1行 n个元素
a22 … a 2n 第 2行 n-1个元素
… … … 第 i-1行 n-i+2个元素
aii ··· aij … a in 第 i行 n-i+1个元素
… …
ann 第 n行 1个元素下三角矩阵的压缩存储和对称矩阵类似,sa[k]和 aij的对应关系是
)(
,
2
)1(
,
2
)1(
c
jii
jj
jij
ii
k
存储常数当当
上三角矩阵的压缩存储
.1)22(
2
1
1)2()1(
,
ijini
ijinnnk
ji
有时当
cjiji
jiijinik
存储常数当调换上式的当故可得
,,
,1)22(
2
1
（ 2）三角矩阵的压缩存储
特殊矩阵的压缩存储第五章 数组和广义表第 23页
（ 3）对角矩阵的压缩存储对角矩阵亦称带状矩阵，其特点是：所有的非零元素都集中在以主对角线为中心的带状区域中，即除了主对角线和分别位于主对角线上、下的若干条相同数目的次对角线上的元素外，其它的所有元素均为零。
示例三对角矩阵 五对角矩阵亦可用一个一维数组存储其带状区域内的元素，具体存储方法可以以行的顺序依次存放各个元素（与三角矩阵的存储方式类似）,也可以顺次存放各条对角线上的元素 。
8 3
4 5 7
6 6 2
2 7 1
4 7
6 2 8
7 2 3 7
3 6 4 2 5
7 7 8 5 0
4 1 4 7 9
8 0 5 0 3
1 7 4 5
5 7 2
特殊矩阵的压缩存储第五章 数组和广义表第 24页三对角矩阵的压缩存储 An*n—— sa(1:3n-2)
若令 aij=sa[k]，则易得
k=3(i-1)-1 + j-(i-1)+1
=2(i-1)+j,( -1? i - j? 1)
这就是三对角矩阵压缩存储的地址公式。
a11 a12
a21 a22 a23
a32 a33 a34
… …
… …
… …
an-1,n-2 an-1,n-1 an-1,n
an,n-1 ann
i→
j
↓
aij
问：如何用 k表示 i,j?
（课外作业 5.8(选作 )）
（ 2）三角矩阵的压缩存储
特殊矩阵的压缩存储第五章 数组和广义表第 25页定义 设矩阵 Am× n（不必为方阵）中有 S个非零元素，若
S<<(m× n)，则称 A为稀疏矩阵 (Sparse matrix).
示例
0 12 9 0 0 0 0
0 0 0 0 0 0 0
-3 0 0 0 0 14 0
0 0 24 0 0 0 0
0 18 0 0 0 0 0
15 0 0 -7 0 0 0
0 0 -3 0 0 15
12 0 0 0 18 0
9 0 0 24 0 0
0 0 0 0 0 -7
0 0 0 0 0 0
0 0 14 0 0 0
0 0 0 0 0 0
稀疏矩阵 M6× 7和 N7× 6
下面研究稀疏矩阵的逻辑结构、存储结构以及有关稀疏矩阵的运算
M=
N=
稀疏矩阵的压缩存储 —— 三元组表第五章 数组和广义表第 26页稀疏矩阵的压缩存储方法主要有两种
—— 三元组表与十字链表 。
三元组表的一般表示方法稀疏矩阵的非零元 三元组 (i,j,aij)
若将表示稀疏矩阵的非零元素的三元组按行优先（或列优先）的顺序排列（跳过零元素），则得到一个其结点均是三元组的线性表，称作三元组表 (List of 3-tuples).因此，三元组表是稀疏矩阵的 一种顺序存储结构 。以下假定三元组是按以行序为主序的顺序排列的。
采用三元组表，以一个一维数组来存储矩阵中的非零元素,数组中的每个元素都是一个记录,用以存放矩阵中一个非零元素的行、列位置及其元素值。另外,还必须存储该矩阵的行、列数以及非零元素的个数 。
稀疏矩阵的压缩存储 —— 三元组表第五章 数组和广义表第 27页
稀疏矩阵的压缩存储 —— 三元组表表示三元组的线性表的顺序存储结构
#define maxnum 1000 //大于非零元个数的某个常量
typedef struct {
int i,j;
elemtp v;
}tuple3;
typedef struct {
int mu,nu,tu; //mu:行值； nu:列值； tu:非空元个数
tuple3 data[maxnum+1];
}TSMatrix;
TSMatrix a,b;
注,data域中表示非零元的三元组是以行序为主序顺序排列的，
这样做有利于进行矩阵运算,data[0]未用 。
第五章 数组和广义表第 28页
0 12 9 0 0 0 0
0 0 0 0 0 0 0
-3 0 0 0 0 14 0
0 0 24 0 0 0 0
0 18 0 0 0 0 0
15 0 0 -7 0 0 0
示例 分别写出矩阵 M和 N的三元组表：
M=
0 0 -3 0 0 15
12 0 0 0 18 0
9 0 0 24 0 0
0 0 0 0 0 -7
0 0 14 0 0 0
0 0 0 0 0 0
N=
M6× 7 N7× 6
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
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 4 14
稀疏矩阵 M和它的三元组表 a.data 稀疏矩阵 N和它的三元组表 b.data
第五章 数组和广义表第 29页
1)求稀疏矩阵的转置矩阵
0 12 9 0 0 0 0
0 0 0 0 0 0 0
-3 0 0 0 0 14 0
0 0 24 0 0 0 0
0 18 0 0 0 0 0
15 0 0 -7 0 0 0
M=
0 0 -3 0 0 15
12 0 0 0 18 0
9 0 0 24 0 0
0 0 0 0 0 -7
0 0 0 0 0 0
0 0 14 0 0 0
0 0 0 0 0 0
N=
一般矩阵的转置算法
trans_mat( elemtp M[m][n],elemtp &N[n][m] )
{ for( int col = 1; col <= n; n++ )
for( int row = 1; row <= m; row++ )
N[col][row] = M[row][col];
} //trans_mat 时间复杂度 O(m× n).
定义 一个 m× n矩阵 M的转置矩阵 N是一个 n× m矩阵，且有
N(i,j)=M(j,i) (1≤i≤n,1≤j≤m)
示例 如下之矩阵 M,N互为转置矩阵
稀疏矩阵的压缩存储 —— 三元组表第五章 数组和广义表第 30页
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
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 4 14
以 M的行为主序依次排列
a.data
关健一步,求稀疏矩阵 M的转置矩阵 N的问题转化为：
如何由 a得到 b?
用三元组表实现稀疏矩阵的转置矩阵的算法思想
1）将矩阵的行、列值互相交换，即从 m行 n列改为 n行 m列；
2）将三元组中每个 i和 j互相交换；
3）重排三元组之间的次序。
i j v
2 1 12
3 1 9
1 3 -3
6 3 14
3 4 24
2 5 18
1 6 15
4 6 -7
将三元组中的每个
i和 j互相调换重排三元组之间的次序，以 N的行（ M的列）为主序依次排列
b.data
稀疏矩阵的压缩存储 —— 三元组表由于 M中 i从小到大排列，故转换 i,j后，
对 N中的 i而言，同样的 i其 j值必是从小到大顺序排列第五章 数组和广义表第 31页转置算法一：按照 a的列序进行转置对于原矩阵的每一列，逐个取其元素 (i,j,v)，交换 i,j的位置，并按顺序放置在转置矩阵三元组的当前位置上。
trans_sparmat( TSMatrix &b,TSMatrix a )
{/*a和 b分别表示 M和 N,N是 M的转置矩阵，现由 a求 b.程序中 p和 q分别指示 a.data
和 b.data中三元组的序号； col指示 M的列号（即 N的行号） */
b.mu=a.nu; b.nu=a.mu; b.tu=a.tu; //M*N → N*M
if( b.tu≠0 )
{q=1;
for( col=1; col <= a.nu; col++ ) //扫描 a.data a.nu遍
for( p=1; p <= a.tu; 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++;
}
}
} //trans_sparmat 算 法 5.1
时间复杂度 O(nu× tu),适用于 tu<<mu× nu的情况 。由 a直接导出 b,
稀疏矩阵的压缩存储 —— 三元组表第五章 数组和广义表第 32页转置算法二：按照 a的行序进行转置（快速转置）
[分析 ] 按三元组 a的顺序进行转置，将转置后的三元组置入 b中恰当的位置。若能预知 a中每一列（即 b中每一行）的第一个非零元素在 b中应有的位置，则对 a依次作转置时，便可直接放到 b中恰当的位置。
为确定这些位置，转置前应做
1）求 a中每一列非零元素个数，记为 num[col]；
2）求 a中每一列第一个非零元素在 b中的位置，记为 cpot[col]。
显然，有
cpot[1]=1
cpot[col]=cpot[col-1]+num[col-1] 2≤col≤a.nu (5-7)
col 1 2 3 4 5 6 7
num[col] 2 2 2 1 0 1 0
cpot[col] 1 3 5 7 8 8 9
矩阵 M的向量 cpot的值
稀疏矩阵的压缩存储 —— 三元组表第五章 数组和广义表第 33页快速转置算法
fast_transpos (TSMatrix &b,TSMatrix a)
{ //将三元组表 a表示的稀疏矩阵转置为三元组表 b表示的稀疏矩阵
b.mu = a.nu; b.nu = a.mu; b.tu = a.tu;
if( b.tu ≠ 0 ){
for( col = 1; col <= a.nu; col++ )
num[col] = 0; //初始化
for( t = 1; t <= a.tu; t++ )
num[a.data[t].j]++; //求 M中每一列非零元个数
cpot[1] = 1;
for( col = 2; col <= a.nu; col++ )
cpot[col] = cpot[col-1] + num[col-1];
//求第 col列中第一个非零元在 b.data中的序号
for( p = 1; p <= a.tu; p++ ) //转置
{ col = a.data[p].j; q = cpot[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;
cpot[col]++;
}
}
} //fast_transpos 算 法 5.2 时间复杂度 O(nu+tu),
稀疏矩阵的压缩存储 —— 三元组表第五章 数组和广义表第 34页
2) 稀疏矩阵的矩阵相乘对于一般矩阵，设 Mm1× n1,Nm2× n2 则当 n1=m2时有
Qm1× n2=Mm1× n1× Nm2× n2
经典算法
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).
对于用三元组表作存储结构的稀疏矩阵，如
3 0 0 5 0 2 0 6
0 -1 -2 0 1 0 3 -8
2 0 -1 0 -2 4 2 0
0 0
M= N= Q=
i j v
1 1 3
1 4 5
2 2 -1
2 3 -2
3 1 2
3 3 -1
a.data
i j v
1 2 2
2 1 1
3 1 -2
3 2 4
b.data
i j v
1 2 6
2 1 3
2 2 -8
3 1 2
c.data
稀疏矩阵的压缩存储 —— 三元组表第五章 数组和广义表第 35页稀疏矩阵的矩阵相乘算法
[分析 ] 分几点考虑
1）如何求 c的值？
为求 c.data中的一个值，需要在 a.data和 b.data中找到相应的各对元素（即 a.data中的 j(列 )值和 b.data中的 i(行 )值相等和各对元素）相乘。
为了得到非零的乘积,只要对 a.data[a.tu]中的每个元素
(i,k,M[i,k])(1≤i≤m1,1≤k≤n1),找到 b.data 中所有相应的元素
(k,j,N[k,j])(1≤k≤m2,1≤j≤n2)相乘即可 。
根据上述思想，可用手算方法实现由 a.data和 b.data求得 c.data：
i j v
1 1 3
1 4 5
2 2 -1
2 3 -2
3 1 2
3 3 -1
a.data
i j v
1 2 2
2 1 1
3 1 -2
3 2 4
b.data
i j v
1 2 6
2 1 3
2 2 -8
3 1 2
c.data
稀疏矩阵的压缩存储 —— 三元组表第五章 数组和广义表第 36页为了便于在 b.data中寻找 N中第 k行的所有非零元，特附设两个向量 num[1..m2]和 rpos[1..m2],num[1..m2]存放
N中各行非零元素的个数，而 rpos满足如下公式
rpos[1]=1
rpos[row]=rpos[row-1]+num[row-1]
(2≤row≤m2) (5-10)
矩阵 N的向量 num和 rpos的值如下表所示
row 1 2 3 4
num[row] 1 1 2 0
rpos[row] 1 2 3 5
稀疏矩阵的压缩存储 —— 三元组表
rpos[row]表示 N的第 row行中第一个非零元在 b.data中的序号第五章 数组和广义表第 37页
2）稀疏矩阵相乘的基本操作对于 a中每个元素 a.data[p](p=1,2,···,a.tu)，找到 b中所有满足条件
a.data[p].j= b.data[q].i的元素 b.data[q]，求得 a.data[p].v和
b.data[q].v的乘积，作为累计和 Q[i,j]中的一部分。为了便于操作，
应对每个元素设一累计和的数组变量 ctemp(1:c.nu)，其初值均为 0.
3）情况讨论
(a)两个稀疏矩阵相乘的乘积不一定是稀疏矩阵；
(b)即使每个分量值 M[i,k]× N[k,j]不为零，其累加值 Q[i,j]也可能为零。对于乘积矩阵中的零元，应不放入结果三元组表中；
(c)Q中元素的行（列）号和 M(N)中元素的行 (列 )号一致，而 a中元素是以 M的行号为主序，故可对 Q进行逐行处理。当求得 ctemp的一个非零累计和值时，连同行号、列号一起压缩存储到 c.data中去,
稀疏矩阵的压缩存储 —— 三元组表第五章 数组和广义表第 38页求稀疏矩阵乘积的算法
multiply_sparmat (TSMatrix a,TSMatrix b,TSMatrix &c)
{/*a和 b分别表示稀疏矩阵 M和 N，本算法求 c表示 M和 N的乘积 Q，
假设 a.nu=b.mu*/
if( a.tu*b.tu≠0 )
{for( row = 1; row <= b.mu; row++ )
num[row] = 0; //初始化
for( t=1; t <= b.tu; t++ )
num[b.data[t].i]++;
//求 N中每一行中非零元个数
rpos[1]=1;
for( row = 2; row <= b.mu+1; row++ )
rpos[row] = rpos[row-1]+num[row-1];
//rpos[row]指示 N中第 brow行第一个非零元在 b中的序号
c.mu = a.mu； //c的行数 =a的行数
c.nu = b.nu； //c的列数 =b的列数
c.tu = 0； //c的非零元个数 =0(初始化 )
稀疏矩阵的压缩存储 —— 三元组表第五章 数组和广义表第 39页
p=1； //三元组表 a的指示器初始值
do
crow=a.data[p].i; //crow指示当前处理的行号
for( k=1; k <= c.nu; k++ )
Ctemp[k]=0； //crow行至多有 c.nu个非零元，它们将由累加求和而得，
其初始值均设为 0
while((p≤a.tu) && (a.data[p].i==crow))
//对所有 crow行的 a中元素求乘积并累计到相应位置
{ brow = a.data[p].j; //brow指示 b.data[q]在 N中的行号
for( q = rpos[brow]; q <= rpos[brow+1]-1; q++ )
{ ccol=b.data[q].j; //ccol指示乘积元素在 Q中的列号
ctemp[ccol] += a.data[p].v * b.data[q].v;
}
p++;
};
for( ccol=1; ccol <= c.nu; ccol++ )
if( ctemp[ccol]≠0 )
{ c.tu++;
c.data[c.tu]=(crow,ccol,ctemp[ccol])
}
while( p>a.tu );
} //multiply_sparmat 算法 5.3
稀疏矩阵的压缩存储 —— 三元组表第五章 数组和广义表第 40页
稀疏矩阵的压缩存储 —— 三元组表示例,对于用三元组表作存储结构的稀疏矩阵，如
Q=M*N
3 0 0 5 0 2 0 6
0 -1 -2 0 1 0 3 -8
2 0 -1 0 -2 4 2 0
0 0
M= N= Q=
i j v
1 1 3
1 4 5
2 2 -1
2 3 -2
3 1 2
3 3 -1
a.data
i j v
1 2 2
2 1 1
3 1 -2
3 2 4
b.data
i j v
1 2 6
2 1 3
2 2 -8
3 1 2
c.data
while((p≤a.tu) && (a.data[p].i=crow))
//对所有 crow行的 a中元素求乘积并累计到相应位置
{ brow=a.data[p].j; //brow指示 b.data[q]在 N中的行号
for( q = rpos[brow]; q <= rpos[brow+1]-1; q++ )
{ ccol=b.data[q].j; //ccol指示乘积元素在 Q中的列号
ctemp[ccol] += a.data[p].v * b.data[q].v;
};
p++;
};
第五章 数组和广义表第 41页
a.mu=3,a.nu=4,b.mu=4,b.nu=2
a.tu=6 b.tu=4
for( row=1; row <= b.mu; row++ )
num[row]=0;
row 1 2 3 4
num[row] 0 0 0 0
for( t=1; t <= b.tu; t++ )
num[b.data[t].i]++;
row 1 2 3 4
num[row] 1 1 2 0
rpos[1]=1;
for( row=1; row <= b.mu+1; row++ )
rpos[row]=rpos[row-1]+num[row-1];
row 1 2 3 4 (5)
num[row] 1 1 2 0
rpos[row] 1 2 3 5 5
稀疏矩阵的压缩存储 —— 三元组表第五章 数组和广义表第 42页
c.mu=a.mu; //c.mu=4
c.nu=b.nu; //c.nu=2
c.tu=0;
i j v
1 1 3
1 4 5
2 2 -1
2 3 -2
3 1 2
3 3 -1
a.data
a.tu=6
i j v
1 2 2
2 1 1
3 1 -2
3 2 4
b.data
b.tu=4
i j v
c.data
c.tu=0 //初始
row 1 2 3 4 (5)
num[row] 1 1 2 0
rpos[row] 1 2 3 5 5
抄录前面已得内容第五章 数组和广义表第 43页
P=1; //三元组表 a的指示器初始值
do //第一次，当前 p=1
Crow=1,ctemp[1]=0,ctemp[2]=0,
while //No.1
brow=1,
for( q=1 TO 1 )
ccol=2,ctem[2]=0+3·2=6
p=1+1=2
while //No.2
brow=4,
for( q=5 TO 4 )
空操作
p=2+1=3 2 1
退出 while循环 (因为 a.data[p].i≠crow)
第五章 数组和广义表第 44页
ccol=1 TO 2
ccol=1,空操作（因为 ctem[ccol]=0）
ccol=2:
c.tu=0+1=1
c.data[1]=(1,2,6)
do //第二次，当前 p=3
crow=2,ctemp[1]=0,ctemp[2]=0
while //No.1
brow=2,
q=2 TO 2
q=2:ccol=1,ctemp[1]=0+(-1)·1=-1
p=3+1=4
while //No.2
brow=3,
q=3 TO 4
q=3:ccol=1,ctemp[1]=-1+(-2)(-2)=3
q=4:ccol=2,ctemp[2]=0+(-2)·4=-8
p=4+1=5 3 2
退出 while循环 (因为 a.data[p].i≠crow)
ccol=1 TO 2
ccol=1,c.tu=1+1=2,c.data[2]=(2,1,3)
ccol=2,c.tu=2+1=3,c.data[3]=(2,2,-8)
c.data
i j v
c.tu→ 1 2 6
c.data
i j v
1 2 6
2 1 3
c.tu→ 2 2 -8
第五章 数组和广义表第 45页
do //第三次，当前 p=5
crow=3,ctemp[1]=0,ctemp[2]=0
while //No.1
brow=1,
q=1 TO 1
q=1:ccol=2,ctemp[2]=0+2·2=4
p=5+1=6
while {No.2}
brow=3,
q=3 TO 4
q=3:ccol=1,ctemp[1]=0+(-1)·(-2)=2
q=4:ccol=2,ctemp[2]=4+(-1)·4=0
p=6+1=7 7 6
退出 while循环 (因为 p>a.tu)
ccol=1 TO 2
ccol=1,c.tu=3+1=4,c.data[4]=(3,1,2)
ccol=2,空操作（因为 ctemp[ccol]=0）
7 6
退出 while循环 (因为 p>a.tu)
运行结束，其结果为 i j v1 2 6
2 1 3
2 2 -8
c.tu→ 3 1 2
c.data
第五章 数组和广义表第 46页三元组表是用顺序方法来存储稀疏矩阵的非零元素，因此，当非零元素的位置或个数经常发生变化时
，三元组表就不适合用作稀疏矩阵的存储结构。
例如，欲做两个稀疏矩阵的相加运算
A =A+B；（将矩阵 B加到矩阵 A上）就会因为要在稀疏矩阵 A的三元组表中插入或删除结点而引起大量的结点移动。此时，若采用链表作为稀疏矩阵的存储结构则更为适宜。
稀疏矩阵的链接存储表示方法不止一种。
十字链表第五章 数组和广义表第 47页十字链表的一般表示形式结点的一般形式其中 row,col,val表示非零元的三元组，即非零元所在的行、列和值,down链域指向同列中下一个非零元素,right链域指向同行中下一个非零元素。
十字链表的形式描述
typedef struct matnode{
int row,col;
matnode *right,*down;
elemtype e;
} matnode,*matlist;
typedef struct {
matlist *chead,*rhead; //指针
int mu,nu,tu; //行、列、非零元个数
} CrossList;
row col val
down right
十字链表第五章 数组和广义表第 48页示例 设
3 0 0 5
0 -1 0 0
2 0 0 0,
则可给出如下之矩阵 M的十字链表结构
M=
十字链表第五章 数组和广义表第 49页
1 1 3 1 4 5
^ ^
2 2 -1
^ ^
3 1 2
^ ^
^m.chead
m.rhead
在稀疏矩阵的十字链表中
1） 同一行非零元素通过 right域链接成一个链表；
2） 同一列非零元素通过 down域链接成一个链表；
第五章 数组和广义表第 50页十字链表的另一形式描述
struct matnode{
int row,col;
matnode *right,*down;
union{
matnode *headnode;
elemtp element;
};
}
十字链表第五章 数组和广义表第 51页
3 4 0 0 0 0 0 0 0 0
0 0 1 1 3 1 4 5
0 0 2 2 -1
0 0 3 1 2
0 0
hm H
1 H2 H3 H4
H3
H1
H2
H4
j=1 2 3 4
(4)
3
2
i=1
3 0 0 5
0 -1 0 0
2 0 0 0
十字链表第五章 数组和广义表第 52页算法思想设 A`=A+B，则和矩阵 A`中的非零元 a`ij:
.0,;0,;0,,,
/
ijij
ijij
ijijijijijij
ij
ab
ba
baobaba
a
且均令 A A+B，并设 pa,pb分别指向 A和 B的十字链表中 同行 的两个结点，整个运算从矩阵的第一行起逐行进行。一共有四种情况：
1,pa,pb同列，且 pa->val+pb->val≠0，则有
pa->val=pa->val +pb->val;
2,pa,pb同列，且 pa->val+pb->val=0,则删除
pa所指结点 （需改变同一行中前一结点的 right域值，以及同一列中前一结点的 down域值；）
十字链表 —— 稀疏矩阵的相加第五章 数组和广义表第 53页
3,pa->col<pb->col，且 pa->col≠0，则将 pa
右移指向下一个位置；
4,pa->col>pb->col，或 pa->col=0，则需在
A的链表中插入一个值为 bij的新结点 。这里 pa-
>col=0表示 A的这一行中非零元素已处理完,或者这一行根本没有非零元素 。
十字链表 —— 稀疏矩阵的相加第五章 数组和广义表第 54页广义表的概念广义表 (Lists，又称列表 )是 线性表的推广 。在以前所述的线性表 (即 n≥0个元素 a1,a2,··,an的有限序列 )中，
线性表的元素仅限于诸如数、字符、记录等。若放松对表元素的这种限制，容许它们具有其 自身的结构,
这样就形成了广义表。
所谓广义表是指由零个或多个单个元素或子表所组成的有限序列。
广义表的逻辑结构第五章 数组和广义表第 55页广义表的定义定义 一个长度为 n(n≥0)的广义表是一种数据结构
Lists=(D,R)
其中
D={di|i=1,2,···,n,n≥0，且
di∈ D0或 di∈ Lists} (用到了递归 )
D0为某个数据对象
R={LR}
LR={<di-1,di> | di-1,di∈ D,2≤i≤n}
广义表一般记作
LS=(d1,d2,··dn)
其中 LS是广义表 (d1,d2,··dn)的名字,n为其表的长度。
若 di是个广义表，则称它为广义表 LS的子表。
广义表的逻辑结构第五章 数组和广义表第 56页广义表与线性表的比较广义表 线性表
LS=(d1,d2,···dn) L=(a1,a2,···an)
(1) 是线性表的推广
(2) di可以是单个元素（原子）,ai仅是单个元素也可以是广义表（子表）
(3) 表的长度为 n 表的长度为 n
(4) 表述上，凡是表则用大写字 表述上，各单个元素母表示，单个元素则用小写 无需区分大小写字母字母表示。一个表通常用圆括号括起来，用逗号分隔各个表元素
(5) 称第一个元素 d1为 LS的 表头 不如此区分表头与
(Head)，称其余元素组成的 表尾表 (d2,···dn)是 LS的 表尾 (Tail)
(6) 广义表的定义是一个递归的 线性表不是递归定定义 义的，而是递推
广义表的逻辑结构第五章 数组和广义表第 57页广义表的示例
(1) A=（ ） 空表，长度为 0
(2) B=（ e） 仅一个表元素 —— 原子 e，长度为 1
(3) C=（ a,(b,c,d)） 两个表元素，一个是原子 a，另一个是子表
(b,c,d)，表 c的长度为 2
(4) D=（ A,B,C） 三个表元素，均为子表，表 D的长度为 3，
将 A,B,C的内容代入，可得 D=（ ( ),(e),(a,(b,c,d))）
(5) E=(a,E) 两个表元素，一为原子，另一是子表（表 E本身），
表 E的长度为 2,表 E可表示成 E=（ a,(a,(a,(···)))）
请指出以下广义表的表元素、表头、表尾以及表的长度：
(6) F=（ ( )）
即 F=（ A）,表 F仅一个表元素 A=（ ）,表头、表尾均为空表（ ），表 F的长度为 1
(7) G=（ (r,s,t)）
若记 H=(r,s,t)，则 G=(H).故表 G仅一个表元素，即子表 H=(r,s,t),
表头是 H=(r,s,t)，表尾是空表，表 G的长度为 1。
第五章 数组和广义表第 58页有关广义表的几个结论
（ 1）广义表是一个多层次的结构，广义表中的表元素本身可以是一个子表，而子表的表元素还可以是子表,· · · · · ·。故可将广义表用图形形象地表示。比如，广义表
D=（ A,B,C） =（ ( ),(e),(a,(b,c,d))）的 图形表示如下
A B
D
C
c db
e a图 5.7 列表的图形表示纯表 —— 无元素共享的广义表
（无名）
注 1,圆圈表示子表 (列表 )，方块表示原子 (单元素 )。
注 2,这实际上对应了一棵树，称为纯 (树 )表
广义表的逻辑结构第五章 数组和广义表第 59页
（ 2）广义表 (子表 )可为其它广义表所 共享,即可直接引用子表名，比如设 K=(b,c,d),H=(K,a),G=(K,H)，则广义表 G可用如下之图形形象地表示
K
G
H
c db a
子表 K为广义表 G和 H所共享再入表 —— 有结点共享的广义表，亦称共享表
（ 3）广义表可以是一个 递归表,即广义表亦可以是其自身的一个子表，
比如 E=(a,E)，其图形表示如下子表名，比如
a
递归表 —— 有递归的广义表注,显然有线性表 属于 纯表 属于 共享表 (再入表 ) 属于 递归表
广义表的逻辑结构
E
第五章 数组和广义表第 60页广义表的若干基本操作
(1) 建立一个广义表 Create
(2) 在广义表中插入一个表元素 Insert
(3) 在广义表中删除一个表元素 Delete
(4) 判某表元素是否为单元素 (原子 )IsAtom
(5) 判 两个广义表是否相等 EqualLists
(6) 取广义表表头 Head
(7) 取广义表表尾 Tail
注,任何一个非空广义表，其表头可能是单元素，也可能是广义表 (子表 )，而其表尾必定为广义表。
B=(e) Head(B)=e,Tail(B)=( );
D=(A,B,C) Head(D)=A
Tail(D)=(B,C),继续分解
(B,C) Head((B,C))=B,Tail((B,C))=(C).
(C) Head((C))=C,Tail((C))=( ).
E=(a,E) Head(E)=a,Tail(E)=(E).
广义表的逻辑结构第五章 数组和广义表第 61页广义表的链式存储结构由于广义表中的元素不是同一类型，同时广义表又是一种递归的数据结构，因此难以用顺序结构表示，也很难为每个广义表分配固定大小的存储空间。所以其存储结构通常采用 链接存储结构,以链接存储方法来存储广义表，并称之为 广义链表
。
广义表的结点表示形式需要两种结构的结点,单元素 或 子表 。
单元素结点 —— 两个域：标志域和值域；
子表结点 —— 三个域：标志域、指示表头的指针和指示表尾的指针域。
广义表的存储结构第五章 数组和广义表第 62页广义表链式存储结构的形式定义在广义链表中有两种不同结构的结点：单元素结点和子表结点。因此在广义链表的存储结构中，结点的表示形式应是一个变体记录。故有
typedef enum { Atom,List } ElemTag;
typedef struct nodetype{
ElemTag tag;
union{
datatype data;
struct{ struct nodetype *hp,*tp } ptr;
}
} *GList;
tag=0 data tag=1 hp tp
单元素结点 子表结点图 5.8 列表的链表结点结构
广义表的存储结构第五章 数组和广义表第 63页广义表的链式存储结构示例示例
A=( ); B=(e); C=(a,(b,c,d));
D=(A,B,C); E=(a,E).
存储结构
A=NULL
1 ^ 1 1 ^B→
0 e 0 a 1 ^1 1
0 b 0 c 0 d
1 ^ 1 1 ^D→
1 1 ^E→
0 a
C→
图 5.9 广义表的存储结构示例
((b,c,d))
(B,C) (C)
广义表的存储结构
(c,d) (d)
第五章 数组和广义表第 64页
广义表的存储结构形式定义
typedef enum{ Atom,List } ElemTag;
typedef struct nodetype{
ElemTag tag;
union{
datatype data;
struct nodetype *hp
};
nodetype *tp;
} *GList;
tag=1 data
单元素结点 表结点
tag=0 hp tp
2) 广义表的另一种链式存储结构
tp
hp指向其表头
tp指向同一层的下一结点 (不是指向其表尾 )
第五章 数组和广义表第 65页
广义表的存储结构
1 ^ 1 ^B→
0 e 0 a 1 ^
0 b 0 c 0 d
1 ^
1 1 ^
D→ 1E→
C→
1 ^ ^A→
^
^
1 ^ 0 a 1 ^
示例,A=( ) B=(e) C=(a,(b,c,d)) D=(A,B,C) E=(a,E)
hp指向其表头
tp指向同一层的下一结点 (不是指向其表尾 )
2) 广义表的另一种链式存储结构广义表的表指针始终指向一个表节点（即使是空表）
第五章 数组和广义表第 66页示例 三元多项式
D(x,y,z) = x10y3z2 + 2x6y3z2 + 3x5y2z2 + x4y4z + 6x3y4z + 2yz + 15
由于 m(今 m=3)元多项式中每一项的变化数目不均匀，而每一变元均是重要信息，故不适于用线性表表示。
今改写 P(x,y,z):
P(x,y,z)=((x10+2x6)y3+3x5y2)z2+((x4+6x3)y4+2y)z+15
Az2+Bz+15z0
其中
A=(x10+2x6)y3+3x5y2 Cy3+Dy2
C=x10+2x6,D=3x5
B=(x4+6x3)y4+2y Ey4+Fy
E=x4+6x3,F=2x0
m元多项式的表示用广义表表示三元多项式 P
P=z((A,2),(B,1),(15,0))
A=y((C,3),(D,2))
C=x((1,10),(2,6)) D=x((3,5))
B=y((E,4),(F,1))
E=x((1,4),(6,3)) F=x((2,0))
第五章 数组和广义表第 67页结论 每一个多项式都可看作是由一个变量加上若干个系数指数偶对所组成。任何一个 m元多项式均可先分解出一个主变元，即它是主变元的多项式，随后再分解出第二个变元，即其系数又是第二个变元的多项式，如此类推
,从而可用广义表来表示 m元多项式 。广义表的 深度即为变元个数 。
P(x,y,z)=z((A,2),(B,1),(15,0))
=z((y((c,3),(D,2)),2),
(y((E,4),(F,1)),1),
(15,0))
=z((y((x((1,10),(2,6)),3),
(x((3,5)),2)),2),
(y((x((1,4),(6,3)),4),
(x((2,0)),1)),1),
(15,0))
m元多项式的表示第五章 数组和广义表第 68页以类似于广义表的第二种存储结构形式来表示 m元多项式的广义表的存储结构链表的结点结构
tag=0
单元素结点 表结点
tag=1 exp hp tpexp coef tp
形式定义
typedef struct MPNode{
ElemTag tag;
int exp; //指数
union{
float coef; //系数
struct MPNode *hp；
}
struct MPNode *tp;
} *MPList；
m元多项式的广义表的存储结构其中
exp：指数域,coef,系数域
hp：指向其系数子表
tp：指向同一层的下一结点第五章 数组和广义表第 69页
1 2 1 1 0 0 15 ^
头指针 P
图 5.12 三元多项式 P(x,y,z)的存储结构示意图
m元多项式的广义表的存储结构
A B
Z层
1 3 1 1 ^1 2 ^ 1 4 Y层
X层0 0 2 ^0 5 3 ^0 10 1
0 3 6 ^0 6 2 ^
0 4 1
在每一层上增设一个表头结点并利用 exp指示该层的变元
1 ^
1
1
1
1 11
z y x
Z
∩
1 ^3
多项式中变元的个数第五章 数组和广义表第 70页作为一种递归的数据结构，有关广义表的运算许多都是可以采用递归算法实现的，例如求广义表的深度，复制广义表，建立广义表存储结构等运算，以及对两个广义表判定是否相等等问题，均可使用递归实现。 这里假定广义表都是非递归表且无共享子表。
1）判定两个广义表是否相等条件,两个广义表 s与 t的长度相等，且每个元素 (单元表或子表 )均对应相等 。
思想,(1)当 s=NULL,t=NULL，则返回 true； (空表相等 )
(2)若均为数据域，则看其数据是否相等；
(3)若为子表，则递归调用。看表头、表尾。
(4)若表头相等，则看表尾。
广义表的递归算法第五章 数组和广义表第 71页
Status equal_lists( Glist s,Glist t) //头尾链表存储
{ eq = false; //初始假设两个广义表为不相等
if( s==NULL && t==NULL ) return true //两个空广义表相等
if( s≠NULL && t≠NULL ){ //若有一个为 NULL，则返回 eq为 false
if( s->tag == t->tag ) //若标志域不等，则返回 eq为 false
{ if( s->tag == 0 ) //单元素结点
{ if( s->data == t->data ) eq = true;
else eq = false; }
else { //广义表（子表）
eq = equal_lists( s->hp,t->hp ); //处理表头
if( eq ) eq = equal_lists( s->tp,t->tp ); //表尾
}
};
}
return(eq)
} //equal_lists
1）判定两个广义表是否相等
广义表的递归算法第五章 数组和广义表第 72页
2）求广义表的深度定义 广义表的深度系指广义表中括弧的重数。
定义
A=( ),DEPTH(A)=1 （但 DEPTH(a)=0）
B=(e),DEPTH(B)=1
C=(a,(b,c,d)) DEPTH(C)=2
D=(A,B,C)=（ ( ),(e),(a,(b,c,d))）则 DEPTH(D)=3
E=(a,E)=（ a,(a,(a,(···)))）
E是递归表，不在讨论之列广义表 LS=(α1,α2,···,αn)的深度 DEPTH(LS)的递归定义
ninD E P T HM a x
LS
LS
LSD E P T H
i 11) },({1
,0
,1
)(
为单元素时当为空表时当比如
DEPTH(D)=1+Max{DEPTH(A),DEPTH(B),DEPTH(C)}
DEPTH(A)=1
DEPTH(B)=1+Max{DEPTH(e)}=1+0=1
DEPTH(C)=1+Max{DEPTH(a),DEPTH((b,c,d))} =1+Max{0,1}=2
故 DEPTH(D)=1+Max{1,1,2}=3.
单元素第五章 数组和广义表第 73页求广义表深度的递归算法 (头尾链表存储 )
int depth_lists( Glist ls )
{ //求 ls为头指针的广义表的深度
if( ls == NULL ) return(1); //空表
if( ls->tag == 0 ) return(0); //单元素
max = 0; pp = ls;
while( pp ≠ NULL )
{ dep = depth_lists(pp->hp); //求 pp->hp为头指针的子表深度
if( dep > max ) max = dep;
pp = pp->tp
};
return( max + 1 );
} //depth_lists 算 法 5.5
广义表的递归算法
2）求广义表的深度第五章 数组和广义表第 74页
copy_lists( GList ls,GList &newls)
//复制广义表 ls的一个副本 newls
{ if( ls == NULL ){ //复制空表
newls = NULL; return；
}
newls = new( Glist ); newls->tag = ls->tag;
if( ls->tag == 0 )
newls->data = ls->data; //建单元素结点
else
{ copy_lists( ls->hp,newls->hp );
//复制广义表 ls->hp的一个副本 newls->hp
copy_lists( ls->tp,mewls->tp );
//复制广义表 ls->tp的一个副本 newls->tp
}
}; //copy_lists 算 法 5.6
3） 复制广义表算法思想：只要分别复制广义表的表头和表尾，然后合成即可。
复制广义表操作的递归定义 (设 LS是原表,NewLS是复制表 )：
(1) 基本项,InitGList( NewLS )，当 LS == NULL
(2) 归纳项,Copy(Head(LS)→Head(NewLS) //复制表头
Copy(Tail(LS)→Tail(NewLS) //复制表尾第五章 数组和广义表第 75页第五章 数组和广义表 小结内容提要
● 数组的逻辑结构特征及其存储方式
● 特殊矩阵和稀疏矩阵的压缩存储及操作
● 广义表的逻辑结构和存储结构学习要点
● 熟悉数组在以 行 为主序的存储结构中的地址计算方法
● 熟悉特殊矩阵在压缩存储时的下标变换
● 理解稀疏矩阵常用的两种压缩存储表示 (三元组表的十字链表 )的特点及适用范围，领会以三元组表表示的稀疏矩阵进行矩阵运算时的处理方法以及建立十字链表的算法
● 熟悉广义表的有关概念、表示方法以及存储结构，掌握广义表求表头、表尾的方法，理解广义表的基本应用
第五章 数组和广义表第五章 数组和广义表第 2页内容和要求
● 内容和要求数组和广义表的概念,存储结构和矩阵的压缩 存储方法 。
要求对数组和广义表有较深刻的了解。掌握数组和广义表的概念，熟悉它们的存储结构及基本应用。
● 重点数组和广义表的存储特性,稀疏矩阵存储。
第五章 数组和广义表第 3页二维数组的逻辑结构数组和广义表可以看成是线性表在下述含义上的扩展,即线性表中的数据元素本身也是一个数据结构。
类似于线性表，一个二维数组的逻辑结构可形式地表示为
2-Array=(D,R) (5-1)
其中
D={aij|i=c1,c1+1,···,d1,j= c2,c2+1,···,d2,aij∈ D0}
R={Row,Col} //行关系，列关系
Row={<aij,ai,j+1>| c1≤i≤d1,c2≤j≤d2-1,aij,ai,j+1 ∈ D}
Col={<aij,ai+1,j>| c1≤i≤d1-1,c2≤j≤d2,aij,ai+1,j ∈ D}
D0为某个数据对象,c1,c2,d1,d2均为整数。
数组的逻辑结构第五章 数组和广义表第 4页若 c1=1,d1=m,c2=1,d2=n,则有
D={aij|i=1,2,···,m,j= 1,2,···,n,∈ D0}
R={Row,Col}
Row={<aij,ai,j+1>| i=1,2,···,m,j=1,2,···,n-1,aij,ai,j+1∈ D}
Col={<aij,ai+1,j>| i=1,2,···,m-1,j=1,2,···,n,aij,ai+1,j ∈ D}
记作 Am× n，即 A为 m行 n列的二维数组 (起始下标为 1)。
说明：
1) 用于二维数组的抽象可称之为矩阵，它是对向量的推广，其元素个数为 m× n个。
数组的逻辑结构
mnmm
n
n
nm
aaa
aaa
aaa
A
21
22221
11211
第五章 数组和广义表第 5页
2) 二维数组也可以看作是这样一个线性表,它的每一个数据元素是一个线性表 。从而对二维数组可以进行递归定义，即它是数据元素为一维数组的线性表。可把 Am× n看成是由 m个行向量所组成的向量（线性表），也可以看成是 n个列向量所组成的向量。
Am× n=(α1,α 2,···,α p) (p=m或 n)
若 α i为行向量,α i = (ai1,ai2,···,ain) 1≤i≤m
若 α j为列向量,α j = (a1j,a2j,···,amj) 1≤j≤n
数组的逻辑结构
3) 二维数组中的每个元素都属于 两个向 量,第 i行的行向量和第 j列的列向量（对元素 aij而言 ）。
4) 每个元素 aij有两个前趋结点 ai-1,j和 ai,j-1(2≤i≤m,2≤j≤n)，两个后继结点 ai+1,j和 ai,j+1(1≤i≤m-1,1≤j≤n-1)，其中 a11无前趋,amn无后继。边界上的结点 a1j(j=2,···,n),amj(j=1,···,n-1)和 ain(i=1,···,m-1)都只有一个后继结点或者只有一个前趋结点。
第五章 数组和广义表第 6页
n(n>2)维数组的逻辑结构
n维数组的逻辑结构的形式定义
)25(),( RDA rra yn
Daa
djc
iknkdjc
aaR
RRRR
dcDa
nnidccj
aD
RDA r r a yn
nini
nini
n
n
jjjjjj
iii
kkk
jjjjjji
n
iijjj
iiii
jjj
1
1,,
21
0,
1
,
11
11
21
21
,
1
1,
,
,,,
,
)0(,2,1,,,,
)25(),(
且均为整数和且其中说明：
1） n维数组的元素个数为 n1·n 2· ··· ·nn=? ni.
2） n维数组中每个数据元素都属于 n个向量（受 n个关系制约）
，除边界上的元素外，均可以有 n个前趋和 n个后继。
数组的逻辑结构第五章 数组和广义表第 7页
N维数组的递归定义
DAA
dic
AAAR
ARR
kAk
DAk
dicA
D
nkRDA r r a yK
k
i
k
i
knkkn
k
i
k
i
k
k
i
k
i
knkkn
k
i
k
kk
kk
kk
k
k
k
)(
1
)(
11
)(
1
)(
)(
)(
0
)(
11
)(
)(
)()(
,
,
1,1
,1
)35()1)(,(_
维数组是时时其中在这递归定义中，一个 k维数组是其数据元素为 k-1维数组的线性表,cn-k+1和 dn-k+1是第 k维下标的一对界偶。
n维数组是一种较复杂的数据结构，但它可以由简单的数据结构 —— 线性表辗转合成而得。
数组的逻辑结构第五章 数组和广义表第 8页数组的操作一个数组中所有的数据元素都必须属于同一数据类型。
对于数组，通常只有两种基本操作：
1）给定一组下标，存取相应的数据元素。
2）给定一组下标，修改相应数据元素中的某一个或几个数据项的值。
注,对于二维数组的抽象即矩阵，可包含取值、赋值和初始化等操作。编译程序用线性存储器来实现矩阵。
数组的逻辑结构第五章 数组和广义表第 9页数组的 顺序存储结构,用一组 连续的 存储单元顺序地存放数组中的诸数组元素。
数据元素的存放次序 问题,解决存储单元是一维结构，而数组是个多维结构的矛盾。
（指多维数组）
二维数组元素间次序的 排列方法,行优先与 列优先 序。
行优先序：按以行序为主序进行排列，就是把数组元素按行表次序、第 i+1行的元素紧跟在第 i行元素后面进行存储。
（列） （列）
（列） （ j+1列）
（ j列）
数组的顺序存储结构第五章 数组和广义表第 10页示例,w是一个 3*4的整数数组（起始下标从 1开始）。
设二维数组变量 w的诸数据组元素值如下表所示
1 2 3 4
1 0 -1 4 5
2 8 2 0 -3
3 -5 1 2 0
以 列序 为主序的存储方式 ——
列优先序以 行序 为主序的存储方式 ——
行优先序0
8
-5
-1
2
1
4
0
2
5
-3
0
第 1列第 2列第 3列第 4列
0
-1
4
5
8
2
0
-3
-5
1
2
0
第 1行第 2行第 3行
C,Pascal,BASIC,PL/1,COBOL等中采用FORTRAN中采用下面讨论的是按 行为主序 规则存储的情形。
数组的顺序存储结构第五章 数组和广义表第 11页同样，对于 n维数组也有上述两种不同的顺序存储方式,以左下标 为主序的存储方式和以 右下标 为主序的存储方式。
把 n维数组的元素按上述方式顺序存放在存储单元中，则每个元素的存储地址可以用一个公式计算出来，这个公式称为,地址公式,。
计算存储地址：对于 A[1..m,1..n]，设每个数组元素占 L个存储单元。
mnmm
n
n
aaa
aaa
aaa
A
21
22221
11211
i→
j
↓
aij
LOC[1,1]
↓
注,以左下标为主序，指主序变化最慢（实现时为最外层循环）
数组的顺序存储结构不同程序设计语言中数组的起始下标不完全相同,C语言起始下标为 0，
Pascal为 1，某些 4GL则允许定义起始下标。
第五章 数组和广义表第 12页记 a11的存储地址为 LOC[1,1]，它即是二维数组 A的起始存储位置，或称基地址（
首地址）,L为元素所占的单元数。
记 aij(1≤i≤m,1≤j≤n)的存储地址为 LOC[i,j]，
则
LOC[i,j]=LOC[1,1]+ [n*(i-1)+(j-1)]*L.
以二维数组为例，先讨论简化情况（ c1=1,d1=m,c2=1，
d2=n），再讨论一般情况（下标分别为 c1,d1,c2,d2）,
数组的顺序存储结构一般地，对于 A[c1..d1,c2..d2]，则有
Loc[i,j] = Loc[c1,c2] +
[(d2-c2+1)(i- c1)+(j- c2)]*L
其中 LOC[c1,c2]是二维数组 A的基地址。
C语言起始下标从 0开始，则
Loc[i,j] = Loc[0,0] + ( n*i + j ) * L
mnmm
n
n
aaa
aaa
aaa
A
21
22221
11211
i→
j
↓
aij
LOC[1,1]
↓
第五章 数组和广义表第 13页
LOC[j1,j2,j3]=LOC[c1,c2,c3]+[(d2-c2+1) (d3-c3+1)(j1-c1)+(d3-c3+1) (j2-c2)+ (j3-c3)]*L
对于三维数组 A[c1..d1,c2..d2,c3..d3]，设基地址为 LOC[c1,c2,c3],
则
.1)1(,3
31),1(
)(],,[
)]()1()([
],,[
3
1
3
1
3
1
321
33
2
1
3
1
321
kk
ik
kk
ik
i
i
iii
kk
i
ik
ii
cdi
icdl
cjcccL O C
lcjcdcj
cccL O C
令时当其中
数组的顺序存储结构第五章 数组和广义表第 14页上已推导出，对于三维数组 A[c1..d1,c2..d2,c3..d3]，
设基地址为 LOC[c1,c2,c3]，则
.1)1(,
1),1(
)55(),(
],,[],,[
],..,..,..[
.1)1(,3
31),1(
)(
],,[],,[
1
1
1
2121
2211
3
1
3
1
3
1
321321
kk
n
ik
kk
n
ik
i
n
i
iii
nn
nn
kk
ik
kk
ik
i
i
iii
cdni
nicdl
cj
cccL O CjjjL O C
dcdcdcAn
cdi
icdl
cj
cccL O CjjjL O C
时其中有维数组推广至时当其中
第五章 数组和广义表第 15页
mnmm
n
n
aaa
aaa
aaa
A
21
22221
11211
矩阵,在科学研究和工程计算中经常用到的一种数学工具，是研究的主要数学对象之一。
矩阵的存储,一般情况下，可用二维数组实现。
二维数组，通常也就称为矩阵，是数学上的一种重要数据结构。
m× n
矩阵压缩存储的概念第五章 数组和广义表第 16页矩阵的压缩存储,对于一些结构比较特殊的矩阵可采用压缩存储方式,即只存储矩阵中的部分元素而不丢失矩阵中任何信息的存储方式。同时，还需保证矩阵的各种运算能有效地进行。
在矩阵阶数很高且矩阵中有许多值 相同的元素 或 零元素 时，为多个值相同的元素分配一个存储空间，对零元素不分配空间，从而可以大量 节省存储空间 。
特殊矩阵,值相同的元素或零元素在矩阵中的分布有一定规律。
稀疏矩阵,矩阵中非零元素较之零元素要少得多，
且非零元素的分布没有一定规律。
矩阵压缩存储的概念第五章 数组和广义表第 17页所谓共享存储空间是指 aij与 aji 经计算后都指向同一个存储单元研究 对称矩阵,三角矩阵 （上三角矩阵、下三角矩阵）,对角矩阵 （三对角矩阵、带状矩阵）等特殊矩阵的压缩存储问题。
（ 1）对称矩阵的压缩存储定义 若一个 n阶矩阵（方阵） A中的元素满足下述性质
aij= aji (1≤i,j≤n)
则称 A为 n阶对称矩阵。
示例 一个 5阶对称矩阵
1 5 1 3 7
5 0 8 0 0
1 8 9 2 6
3 0 2 5 1
7 0 6 1 3
对称矩阵中的元素关于主对角线对称，故仅需存储矩阵中上三角或下三角中的元素，让每一对对称的元素 共享一个存储空间
。
特殊矩阵的压缩存储第五章 数组和广义表第 18页
1 5 1 3 7
5 0 8 0 0
1 8 9 2 6
3 0 2 5 1
7 0 6 1 3
a11
a21 a22
a31 a32 a33
a41 a42 a43 a44
a51 a52 a53 a54 a55
对称矩阵以行为主序存储下三角矩阵的元素
a11
a21 a22
a31 a32 a33
… …
… … …
an1 an2 an3 … ann
对称矩阵 Ann以行为主序存储下三角矩阵的元素,2
)1(
21
1
nn
ni
n
i
对于 An× n所对应的下三角矩阵中（见右下图），
第 i(1≤i≤n)行恰有 i个元素，
故元素总数为
aij
特殊矩阵的压缩存储第五章 数组和广义表第 19页设以一维数组 sa（ 1:n(n+1)/2）作为 n阶对称矩阵 A的存储结构，令 sa[k] aij，则有如下之一一对应关系?
)(
2
)1(
)1(321
jijii
jik
特殊矩阵的压缩存储
a11
a21 a22
a31 a32 a33
… …
… … …
an1 an2 an3 … amn
aij
第五章 数组和广义表第 20页由上述推导可得
)65(
,,
2
)1(
,,
2
)1(
,.
2
)1(
],[,,
.
2
)1(
],[,
不包括主对角线上三角当包括主对角线下三角当故有互换上式令则令当同理则令当
jii
jj
jij
ii
k
jii
jj
k
ksaaji
j
ii
k
ksaaji
ij
ij
特殊矩阵的压缩存储第五章 数组和广义表第 21页
（ 2）三角矩阵的压缩存储以主对角线划分，三角矩阵有上三角矩阵和下三角矩阵两种。
a11 a12 · · · a1n
c a22 · · · a2n
… …
c c … ann
a11 c · · · c
a21 a22 · · · c
… …
an1 an2 · · · ann
上三角矩阵 下三角矩阵在多数情况下，三角矩阵的常数 c为零。故可将三角矩阵表示为
a11 a12 · · · a1n
a22 · · · a2n
… …
ann
a11
a21 a22
… …
an1 an2 · · · ann
上三角矩阵 (c=0) 下三角矩阵 (c=0)
n阶三角矩阵 A的压缩存储 —— sa[1..n(n+1)/2+1],其中
n(n+1)/2个存储空间存放上（或下）三角矩阵的元素,1个存储空间存放常数 C。
特殊矩阵的压缩存储第五章 数组和广义表第 22页
a11 a12 … a 1n 第 1行 n个元素
a22 … a 2n 第 2行 n-1个元素
… … … 第 i-1行 n-i+2个元素
aii ··· aij … a in 第 i行 n-i+1个元素
… …
ann 第 n行 1个元素下三角矩阵的压缩存储和对称矩阵类似,sa[k]和 aij的对应关系是
)(
,
2
)1(
,
2
)1(
c
jii
jj
jij
ii
k
存储常数当当
上三角矩阵的压缩存储
.1)22(
2
1
1)2()1(
,
ijini
ijinnnk
ji
有时当
cjiji
jiijinik
存储常数当调换上式的当故可得
,,
,1)22(
2
1
（ 2）三角矩阵的压缩存储
特殊矩阵的压缩存储第五章 数组和广义表第 23页
（ 3）对角矩阵的压缩存储对角矩阵亦称带状矩阵，其特点是：所有的非零元素都集中在以主对角线为中心的带状区域中，即除了主对角线和分别位于主对角线上、下的若干条相同数目的次对角线上的元素外，其它的所有元素均为零。
示例三对角矩阵 五对角矩阵亦可用一个一维数组存储其带状区域内的元素，具体存储方法可以以行的顺序依次存放各个元素（与三角矩阵的存储方式类似）,也可以顺次存放各条对角线上的元素 。
8 3
4 5 7
6 6 2
2 7 1
4 7
6 2 8
7 2 3 7
3 6 4 2 5
7 7 8 5 0
4 1 4 7 9
8 0 5 0 3
1 7 4 5
5 7 2
特殊矩阵的压缩存储第五章 数组和广义表第 24页三对角矩阵的压缩存储 An*n—— sa(1:3n-2)
若令 aij=sa[k]，则易得
k=3(i-1)-1 + j-(i-1)+1
=2(i-1)+j,( -1? i - j? 1)
这就是三对角矩阵压缩存储的地址公式。
a11 a12
a21 a22 a23
a32 a33 a34
… …
… …
… …
an-1,n-2 an-1,n-1 an-1,n
an,n-1 ann
i→
j
↓
aij
问：如何用 k表示 i,j?
（课外作业 5.8(选作 )）
（ 2）三角矩阵的压缩存储
特殊矩阵的压缩存储第五章 数组和广义表第 25页定义 设矩阵 Am× n（不必为方阵）中有 S个非零元素，若
S<<(m× n)，则称 A为稀疏矩阵 (Sparse matrix).
示例
0 12 9 0 0 0 0
0 0 0 0 0 0 0
-3 0 0 0 0 14 0
0 0 24 0 0 0 0
0 18 0 0 0 0 0
15 0 0 -7 0 0 0
0 0 -3 0 0 15
12 0 0 0 18 0
9 0 0 24 0 0
0 0 0 0 0 -7
0 0 0 0 0 0
0 0 14 0 0 0
0 0 0 0 0 0
稀疏矩阵 M6× 7和 N7× 6
下面研究稀疏矩阵的逻辑结构、存储结构以及有关稀疏矩阵的运算
M=
N=
稀疏矩阵的压缩存储 —— 三元组表第五章 数组和广义表第 26页稀疏矩阵的压缩存储方法主要有两种
—— 三元组表与十字链表 。
三元组表的一般表示方法稀疏矩阵的非零元 三元组 (i,j,aij)
若将表示稀疏矩阵的非零元素的三元组按行优先（或列优先）的顺序排列（跳过零元素），则得到一个其结点均是三元组的线性表，称作三元组表 (List of 3-tuples).因此，三元组表是稀疏矩阵的 一种顺序存储结构 。以下假定三元组是按以行序为主序的顺序排列的。
采用三元组表，以一个一维数组来存储矩阵中的非零元素,数组中的每个元素都是一个记录,用以存放矩阵中一个非零元素的行、列位置及其元素值。另外,还必须存储该矩阵的行、列数以及非零元素的个数 。
稀疏矩阵的压缩存储 —— 三元组表第五章 数组和广义表第 27页
稀疏矩阵的压缩存储 —— 三元组表表示三元组的线性表的顺序存储结构
#define maxnum 1000 //大于非零元个数的某个常量
typedef struct {
int i,j;
elemtp v;
}tuple3;
typedef struct {
int mu,nu,tu; //mu:行值； nu:列值； tu:非空元个数
tuple3 data[maxnum+1];
}TSMatrix;
TSMatrix a,b;
注,data域中表示非零元的三元组是以行序为主序顺序排列的，
这样做有利于进行矩阵运算,data[0]未用 。
第五章 数组和广义表第 28页
0 12 9 0 0 0 0
0 0 0 0 0 0 0
-3 0 0 0 0 14 0
0 0 24 0 0 0 0
0 18 0 0 0 0 0
15 0 0 -7 0 0 0
示例 分别写出矩阵 M和 N的三元组表：
M=
0 0 -3 0 0 15
12 0 0 0 18 0
9 0 0 24 0 0
0 0 0 0 0 -7
0 0 14 0 0 0
0 0 0 0 0 0
N=
M6× 7 N7× 6
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
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 4 14
稀疏矩阵 M和它的三元组表 a.data 稀疏矩阵 N和它的三元组表 b.data
第五章 数组和广义表第 29页
1)求稀疏矩阵的转置矩阵
0 12 9 0 0 0 0
0 0 0 0 0 0 0
-3 0 0 0 0 14 0
0 0 24 0 0 0 0
0 18 0 0 0 0 0
15 0 0 -7 0 0 0
M=
0 0 -3 0 0 15
12 0 0 0 18 0
9 0 0 24 0 0
0 0 0 0 0 -7
0 0 0 0 0 0
0 0 14 0 0 0
0 0 0 0 0 0
N=
一般矩阵的转置算法
trans_mat( elemtp M[m][n],elemtp &N[n][m] )
{ for( int col = 1; col <= n; n++ )
for( int row = 1; row <= m; row++ )
N[col][row] = M[row][col];
} //trans_mat 时间复杂度 O(m× n).
定义 一个 m× n矩阵 M的转置矩阵 N是一个 n× m矩阵，且有
N(i,j)=M(j,i) (1≤i≤n,1≤j≤m)
示例 如下之矩阵 M,N互为转置矩阵
稀疏矩阵的压缩存储 —— 三元组表第五章 数组和广义表第 30页
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
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 4 14
以 M的行为主序依次排列
a.data
关健一步,求稀疏矩阵 M的转置矩阵 N的问题转化为：
如何由 a得到 b?
用三元组表实现稀疏矩阵的转置矩阵的算法思想
1）将矩阵的行、列值互相交换，即从 m行 n列改为 n行 m列；
2）将三元组中每个 i和 j互相交换；
3）重排三元组之间的次序。
i j v
2 1 12
3 1 9
1 3 -3
6 3 14
3 4 24
2 5 18
1 6 15
4 6 -7
将三元组中的每个
i和 j互相调换重排三元组之间的次序，以 N的行（ M的列）为主序依次排列
b.data
稀疏矩阵的压缩存储 —— 三元组表由于 M中 i从小到大排列，故转换 i,j后，
对 N中的 i而言，同样的 i其 j值必是从小到大顺序排列第五章 数组和广义表第 31页转置算法一：按照 a的列序进行转置对于原矩阵的每一列，逐个取其元素 (i,j,v)，交换 i,j的位置，并按顺序放置在转置矩阵三元组的当前位置上。
trans_sparmat( TSMatrix &b,TSMatrix a )
{/*a和 b分别表示 M和 N,N是 M的转置矩阵，现由 a求 b.程序中 p和 q分别指示 a.data
和 b.data中三元组的序号； col指示 M的列号（即 N的行号） */
b.mu=a.nu; b.nu=a.mu; b.tu=a.tu; //M*N → N*M
if( b.tu≠0 )
{q=1;
for( col=1; col <= a.nu; col++ ) //扫描 a.data a.nu遍
for( p=1; p <= a.tu; 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++;
}
}
} //trans_sparmat 算 法 5.1
时间复杂度 O(nu× tu),适用于 tu<<mu× nu的情况 。由 a直接导出 b,
稀疏矩阵的压缩存储 —— 三元组表第五章 数组和广义表第 32页转置算法二：按照 a的行序进行转置（快速转置）
[分析 ] 按三元组 a的顺序进行转置，将转置后的三元组置入 b中恰当的位置。若能预知 a中每一列（即 b中每一行）的第一个非零元素在 b中应有的位置，则对 a依次作转置时，便可直接放到 b中恰当的位置。
为确定这些位置，转置前应做
1）求 a中每一列非零元素个数，记为 num[col]；
2）求 a中每一列第一个非零元素在 b中的位置，记为 cpot[col]。
显然，有
cpot[1]=1
cpot[col]=cpot[col-1]+num[col-1] 2≤col≤a.nu (5-7)
col 1 2 3 4 5 6 7
num[col] 2 2 2 1 0 1 0
cpot[col] 1 3 5 7 8 8 9
矩阵 M的向量 cpot的值
稀疏矩阵的压缩存储 —— 三元组表第五章 数组和广义表第 33页快速转置算法
fast_transpos (TSMatrix &b,TSMatrix a)
{ //将三元组表 a表示的稀疏矩阵转置为三元组表 b表示的稀疏矩阵
b.mu = a.nu; b.nu = a.mu; b.tu = a.tu;
if( b.tu ≠ 0 ){
for( col = 1; col <= a.nu; col++ )
num[col] = 0; //初始化
for( t = 1; t <= a.tu; t++ )
num[a.data[t].j]++; //求 M中每一列非零元个数
cpot[1] = 1;
for( col = 2; col <= a.nu; col++ )
cpot[col] = cpot[col-1] + num[col-1];
//求第 col列中第一个非零元在 b.data中的序号
for( p = 1; p <= a.tu; p++ ) //转置
{ col = a.data[p].j; q = cpot[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;
cpot[col]++;
}
}
} //fast_transpos 算 法 5.2 时间复杂度 O(nu+tu),
稀疏矩阵的压缩存储 —— 三元组表第五章 数组和广义表第 34页
2) 稀疏矩阵的矩阵相乘对于一般矩阵，设 Mm1× n1,Nm2× n2 则当 n1=m2时有
Qm1× n2=Mm1× n1× Nm2× n2
经典算法
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).
对于用三元组表作存储结构的稀疏矩阵，如
3 0 0 5 0 2 0 6
0 -1 -2 0 1 0 3 -8
2 0 -1 0 -2 4 2 0
0 0
M= N= Q=
i j v
1 1 3
1 4 5
2 2 -1
2 3 -2
3 1 2
3 3 -1
a.data
i j v
1 2 2
2 1 1
3 1 -2
3 2 4
b.data
i j v
1 2 6
2 1 3
2 2 -8
3 1 2
c.data
稀疏矩阵的压缩存储 —— 三元组表第五章 数组和广义表第 35页稀疏矩阵的矩阵相乘算法
[分析 ] 分几点考虑
1）如何求 c的值？
为求 c.data中的一个值，需要在 a.data和 b.data中找到相应的各对元素（即 a.data中的 j(列 )值和 b.data中的 i(行 )值相等和各对元素）相乘。
为了得到非零的乘积,只要对 a.data[a.tu]中的每个元素
(i,k,M[i,k])(1≤i≤m1,1≤k≤n1),找到 b.data 中所有相应的元素
(k,j,N[k,j])(1≤k≤m2,1≤j≤n2)相乘即可 。
根据上述思想，可用手算方法实现由 a.data和 b.data求得 c.data：
i j v
1 1 3
1 4 5
2 2 -1
2 3 -2
3 1 2
3 3 -1
a.data
i j v
1 2 2
2 1 1
3 1 -2
3 2 4
b.data
i j v
1 2 6
2 1 3
2 2 -8
3 1 2
c.data
稀疏矩阵的压缩存储 —— 三元组表第五章 数组和广义表第 36页为了便于在 b.data中寻找 N中第 k行的所有非零元，特附设两个向量 num[1..m2]和 rpos[1..m2],num[1..m2]存放
N中各行非零元素的个数，而 rpos满足如下公式
rpos[1]=1
rpos[row]=rpos[row-1]+num[row-1]
(2≤row≤m2) (5-10)
矩阵 N的向量 num和 rpos的值如下表所示
row 1 2 3 4
num[row] 1 1 2 0
rpos[row] 1 2 3 5
稀疏矩阵的压缩存储 —— 三元组表
rpos[row]表示 N的第 row行中第一个非零元在 b.data中的序号第五章 数组和广义表第 37页
2）稀疏矩阵相乘的基本操作对于 a中每个元素 a.data[p](p=1,2,···,a.tu)，找到 b中所有满足条件
a.data[p].j= b.data[q].i的元素 b.data[q]，求得 a.data[p].v和
b.data[q].v的乘积，作为累计和 Q[i,j]中的一部分。为了便于操作，
应对每个元素设一累计和的数组变量 ctemp(1:c.nu)，其初值均为 0.
3）情况讨论
(a)两个稀疏矩阵相乘的乘积不一定是稀疏矩阵；
(b)即使每个分量值 M[i,k]× N[k,j]不为零，其累加值 Q[i,j]也可能为零。对于乘积矩阵中的零元，应不放入结果三元组表中；
(c)Q中元素的行（列）号和 M(N)中元素的行 (列 )号一致，而 a中元素是以 M的行号为主序，故可对 Q进行逐行处理。当求得 ctemp的一个非零累计和值时，连同行号、列号一起压缩存储到 c.data中去,
稀疏矩阵的压缩存储 —— 三元组表第五章 数组和广义表第 38页求稀疏矩阵乘积的算法
multiply_sparmat (TSMatrix a,TSMatrix b,TSMatrix &c)
{/*a和 b分别表示稀疏矩阵 M和 N，本算法求 c表示 M和 N的乘积 Q，
假设 a.nu=b.mu*/
if( a.tu*b.tu≠0 )
{for( row = 1; row <= b.mu; row++ )
num[row] = 0; //初始化
for( t=1; t <= b.tu; t++ )
num[b.data[t].i]++;
//求 N中每一行中非零元个数
rpos[1]=1;
for( row = 2; row <= b.mu+1; row++ )
rpos[row] = rpos[row-1]+num[row-1];
//rpos[row]指示 N中第 brow行第一个非零元在 b中的序号
c.mu = a.mu； //c的行数 =a的行数
c.nu = b.nu； //c的列数 =b的列数
c.tu = 0； //c的非零元个数 =0(初始化 )
稀疏矩阵的压缩存储 —— 三元组表第五章 数组和广义表第 39页
p=1； //三元组表 a的指示器初始值
do
crow=a.data[p].i; //crow指示当前处理的行号
for( k=1; k <= c.nu; k++ )
Ctemp[k]=0； //crow行至多有 c.nu个非零元，它们将由累加求和而得，
其初始值均设为 0
while((p≤a.tu) && (a.data[p].i==crow))
//对所有 crow行的 a中元素求乘积并累计到相应位置
{ brow = a.data[p].j; //brow指示 b.data[q]在 N中的行号
for( q = rpos[brow]; q <= rpos[brow+1]-1; q++ )
{ ccol=b.data[q].j; //ccol指示乘积元素在 Q中的列号
ctemp[ccol] += a.data[p].v * b.data[q].v;
}
p++;
};
for( ccol=1; ccol <= c.nu; ccol++ )
if( ctemp[ccol]≠0 )
{ c.tu++;
c.data[c.tu]=(crow,ccol,ctemp[ccol])
}
while( p>a.tu );
} //multiply_sparmat 算法 5.3
稀疏矩阵的压缩存储 —— 三元组表第五章 数组和广义表第 40页
稀疏矩阵的压缩存储 —— 三元组表示例,对于用三元组表作存储结构的稀疏矩阵，如
Q=M*N
3 0 0 5 0 2 0 6
0 -1 -2 0 1 0 3 -8
2 0 -1 0 -2 4 2 0
0 0
M= N= Q=
i j v
1 1 3
1 4 5
2 2 -1
2 3 -2
3 1 2
3 3 -1
a.data
i j v
1 2 2
2 1 1
3 1 -2
3 2 4
b.data
i j v
1 2 6
2 1 3
2 2 -8
3 1 2
c.data
while((p≤a.tu) && (a.data[p].i=crow))
//对所有 crow行的 a中元素求乘积并累计到相应位置
{ brow=a.data[p].j; //brow指示 b.data[q]在 N中的行号
for( q = rpos[brow]; q <= rpos[brow+1]-1; q++ )
{ ccol=b.data[q].j; //ccol指示乘积元素在 Q中的列号
ctemp[ccol] += a.data[p].v * b.data[q].v;
};
p++;
};
第五章 数组和广义表第 41页
a.mu=3,a.nu=4,b.mu=4,b.nu=2
a.tu=6 b.tu=4
for( row=1; row <= b.mu; row++ )
num[row]=0;
row 1 2 3 4
num[row] 0 0 0 0
for( t=1; t <= b.tu; t++ )
num[b.data[t].i]++;
row 1 2 3 4
num[row] 1 1 2 0
rpos[1]=1;
for( row=1; row <= b.mu+1; row++ )
rpos[row]=rpos[row-1]+num[row-1];
row 1 2 3 4 (5)
num[row] 1 1 2 0
rpos[row] 1 2 3 5 5
稀疏矩阵的压缩存储 —— 三元组表第五章 数组和广义表第 42页
c.mu=a.mu; //c.mu=4
c.nu=b.nu; //c.nu=2
c.tu=0;
i j v
1 1 3
1 4 5
2 2 -1
2 3 -2
3 1 2
3 3 -1
a.data
a.tu=6
i j v
1 2 2
2 1 1
3 1 -2
3 2 4
b.data
b.tu=4
i j v
c.data
c.tu=0 //初始
row 1 2 3 4 (5)
num[row] 1 1 2 0
rpos[row] 1 2 3 5 5
抄录前面已得内容第五章 数组和广义表第 43页
P=1; //三元组表 a的指示器初始值
do //第一次，当前 p=1
Crow=1,ctemp[1]=0,ctemp[2]=0,
while //No.1
brow=1,
for( q=1 TO 1 )
ccol=2,ctem[2]=0+3·2=6
p=1+1=2
while //No.2
brow=4,
for( q=5 TO 4 )
空操作
p=2+1=3 2 1
退出 while循环 (因为 a.data[p].i≠crow)
第五章 数组和广义表第 44页
ccol=1 TO 2
ccol=1,空操作（因为 ctem[ccol]=0）
ccol=2:
c.tu=0+1=1
c.data[1]=(1,2,6)
do //第二次，当前 p=3
crow=2,ctemp[1]=0,ctemp[2]=0
while //No.1
brow=2,
q=2 TO 2
q=2:ccol=1,ctemp[1]=0+(-1)·1=-1
p=3+1=4
while //No.2
brow=3,
q=3 TO 4
q=3:ccol=1,ctemp[1]=-1+(-2)(-2)=3
q=4:ccol=2,ctemp[2]=0+(-2)·4=-8
p=4+1=5 3 2
退出 while循环 (因为 a.data[p].i≠crow)
ccol=1 TO 2
ccol=1,c.tu=1+1=2,c.data[2]=(2,1,3)
ccol=2,c.tu=2+1=3,c.data[3]=(2,2,-8)
c.data
i j v
c.tu→ 1 2 6
c.data
i j v
1 2 6
2 1 3
c.tu→ 2 2 -8
第五章 数组和广义表第 45页
do //第三次，当前 p=5
crow=3,ctemp[1]=0,ctemp[2]=0
while //No.1
brow=1,
q=1 TO 1
q=1:ccol=2,ctemp[2]=0+2·2=4
p=5+1=6
while {No.2}
brow=3,
q=3 TO 4
q=3:ccol=1,ctemp[1]=0+(-1)·(-2)=2
q=4:ccol=2,ctemp[2]=4+(-1)·4=0
p=6+1=7 7 6
退出 while循环 (因为 p>a.tu)
ccol=1 TO 2
ccol=1,c.tu=3+1=4,c.data[4]=(3,1,2)
ccol=2,空操作（因为 ctemp[ccol]=0）
7 6
退出 while循环 (因为 p>a.tu)
运行结束，其结果为 i j v1 2 6
2 1 3
2 2 -8
c.tu→ 3 1 2
c.data
第五章 数组和广义表第 46页三元组表是用顺序方法来存储稀疏矩阵的非零元素，因此，当非零元素的位置或个数经常发生变化时
，三元组表就不适合用作稀疏矩阵的存储结构。
例如，欲做两个稀疏矩阵的相加运算
A =A+B；（将矩阵 B加到矩阵 A上）就会因为要在稀疏矩阵 A的三元组表中插入或删除结点而引起大量的结点移动。此时，若采用链表作为稀疏矩阵的存储结构则更为适宜。
稀疏矩阵的链接存储表示方法不止一种。
十字链表第五章 数组和广义表第 47页十字链表的一般表示形式结点的一般形式其中 row,col,val表示非零元的三元组，即非零元所在的行、列和值,down链域指向同列中下一个非零元素,right链域指向同行中下一个非零元素。
十字链表的形式描述
typedef struct matnode{
int row,col;
matnode *right,*down;
elemtype e;
} matnode,*matlist;
typedef struct {
matlist *chead,*rhead; //指针
int mu,nu,tu; //行、列、非零元个数
} CrossList;
row col val
down right
十字链表第五章 数组和广义表第 48页示例 设
3 0 0 5
0 -1 0 0
2 0 0 0,
则可给出如下之矩阵 M的十字链表结构
M=
十字链表第五章 数组和广义表第 49页
1 1 3 1 4 5
^ ^
2 2 -1
^ ^
3 1 2
^ ^
^m.chead
m.rhead
在稀疏矩阵的十字链表中
1） 同一行非零元素通过 right域链接成一个链表；
2） 同一列非零元素通过 down域链接成一个链表；
第五章 数组和广义表第 50页十字链表的另一形式描述
struct matnode{
int row,col;
matnode *right,*down;
union{
matnode *headnode;
elemtp element;
};
}
十字链表第五章 数组和广义表第 51页
3 4 0 0 0 0 0 0 0 0
0 0 1 1 3 1 4 5
0 0 2 2 -1
0 0 3 1 2
0 0
hm H
1 H2 H3 H4
H3
H1
H2
H4
j=1 2 3 4
(4)
3
2
i=1
3 0 0 5
0 -1 0 0
2 0 0 0
十字链表第五章 数组和广义表第 52页算法思想设 A`=A+B，则和矩阵 A`中的非零元 a`ij:
.0,;0,;0,,,
/
ijij
ijij
ijijijijijij
ij
ab
ba
baobaba
a
且均令 A A+B，并设 pa,pb分别指向 A和 B的十字链表中 同行 的两个结点，整个运算从矩阵的第一行起逐行进行。一共有四种情况：
1,pa,pb同列，且 pa->val+pb->val≠0，则有
pa->val=pa->val +pb->val;
2,pa,pb同列，且 pa->val+pb->val=0,则删除
pa所指结点 （需改变同一行中前一结点的 right域值，以及同一列中前一结点的 down域值；）
十字链表 —— 稀疏矩阵的相加第五章 数组和广义表第 53页
3,pa->col<pb->col，且 pa->col≠0，则将 pa
右移指向下一个位置；
4,pa->col>pb->col，或 pa->col=0，则需在
A的链表中插入一个值为 bij的新结点 。这里 pa-
>col=0表示 A的这一行中非零元素已处理完,或者这一行根本没有非零元素 。
十字链表 —— 稀疏矩阵的相加第五章 数组和广义表第 54页广义表的概念广义表 (Lists，又称列表 )是 线性表的推广 。在以前所述的线性表 (即 n≥0个元素 a1,a2,··,an的有限序列 )中，
线性表的元素仅限于诸如数、字符、记录等。若放松对表元素的这种限制，容许它们具有其 自身的结构,
这样就形成了广义表。
所谓广义表是指由零个或多个单个元素或子表所组成的有限序列。
广义表的逻辑结构第五章 数组和广义表第 55页广义表的定义定义 一个长度为 n(n≥0)的广义表是一种数据结构
Lists=(D,R)
其中
D={di|i=1,2,···,n,n≥0，且
di∈ D0或 di∈ Lists} (用到了递归 )
D0为某个数据对象
R={LR}
LR={<di-1,di> | di-1,di∈ D,2≤i≤n}
广义表一般记作
LS=(d1,d2,··dn)
其中 LS是广义表 (d1,d2,··dn)的名字,n为其表的长度。
若 di是个广义表，则称它为广义表 LS的子表。
广义表的逻辑结构第五章 数组和广义表第 56页广义表与线性表的比较广义表 线性表
LS=(d1,d2,···dn) L=(a1,a2,···an)
(1) 是线性表的推广
(2) di可以是单个元素（原子）,ai仅是单个元素也可以是广义表（子表）
(3) 表的长度为 n 表的长度为 n
(4) 表述上，凡是表则用大写字 表述上，各单个元素母表示，单个元素则用小写 无需区分大小写字母字母表示。一个表通常用圆括号括起来，用逗号分隔各个表元素
(5) 称第一个元素 d1为 LS的 表头 不如此区分表头与
(Head)，称其余元素组成的 表尾表 (d2,···dn)是 LS的 表尾 (Tail)
(6) 广义表的定义是一个递归的 线性表不是递归定定义 义的，而是递推
广义表的逻辑结构第五章 数组和广义表第 57页广义表的示例
(1) A=（ ） 空表，长度为 0
(2) B=（ e） 仅一个表元素 —— 原子 e，长度为 1
(3) C=（ a,(b,c,d)） 两个表元素，一个是原子 a，另一个是子表
(b,c,d)，表 c的长度为 2
(4) D=（ A,B,C） 三个表元素，均为子表，表 D的长度为 3，
将 A,B,C的内容代入，可得 D=（ ( ),(e),(a,(b,c,d))）
(5) E=(a,E) 两个表元素，一为原子，另一是子表（表 E本身），
表 E的长度为 2,表 E可表示成 E=（ a,(a,(a,(···)))）
请指出以下广义表的表元素、表头、表尾以及表的长度：
(6) F=（ ( )）
即 F=（ A）,表 F仅一个表元素 A=（ ）,表头、表尾均为空表（ ），表 F的长度为 1
(7) G=（ (r,s,t)）
若记 H=(r,s,t)，则 G=(H).故表 G仅一个表元素，即子表 H=(r,s,t),
表头是 H=(r,s,t)，表尾是空表，表 G的长度为 1。
第五章 数组和广义表第 58页有关广义表的几个结论
（ 1）广义表是一个多层次的结构，广义表中的表元素本身可以是一个子表，而子表的表元素还可以是子表,· · · · · ·。故可将广义表用图形形象地表示。比如，广义表
D=（ A,B,C） =（ ( ),(e),(a,(b,c,d))）的 图形表示如下
A B
D
C
c db
e a图 5.7 列表的图形表示纯表 —— 无元素共享的广义表
（无名）
注 1,圆圈表示子表 (列表 )，方块表示原子 (单元素 )。
注 2,这实际上对应了一棵树，称为纯 (树 )表
广义表的逻辑结构第五章 数组和广义表第 59页
（ 2）广义表 (子表 )可为其它广义表所 共享,即可直接引用子表名，比如设 K=(b,c,d),H=(K,a),G=(K,H)，则广义表 G可用如下之图形形象地表示
K
G
H
c db a
子表 K为广义表 G和 H所共享再入表 —— 有结点共享的广义表，亦称共享表
（ 3）广义表可以是一个 递归表,即广义表亦可以是其自身的一个子表，
比如 E=(a,E)，其图形表示如下子表名，比如
a
递归表 —— 有递归的广义表注,显然有线性表 属于 纯表 属于 共享表 (再入表 ) 属于 递归表
广义表的逻辑结构
E
第五章 数组和广义表第 60页广义表的若干基本操作
(1) 建立一个广义表 Create
(2) 在广义表中插入一个表元素 Insert
(3) 在广义表中删除一个表元素 Delete
(4) 判某表元素是否为单元素 (原子 )IsAtom
(5) 判 两个广义表是否相等 EqualLists
(6) 取广义表表头 Head
(7) 取广义表表尾 Tail
注,任何一个非空广义表，其表头可能是单元素，也可能是广义表 (子表 )，而其表尾必定为广义表。
B=(e) Head(B)=e,Tail(B)=( );
D=(A,B,C) Head(D)=A
Tail(D)=(B,C),继续分解
(B,C) Head((B,C))=B,Tail((B,C))=(C).
(C) Head((C))=C,Tail((C))=( ).
E=(a,E) Head(E)=a,Tail(E)=(E).
广义表的逻辑结构第五章 数组和广义表第 61页广义表的链式存储结构由于广义表中的元素不是同一类型，同时广义表又是一种递归的数据结构，因此难以用顺序结构表示，也很难为每个广义表分配固定大小的存储空间。所以其存储结构通常采用 链接存储结构,以链接存储方法来存储广义表，并称之为 广义链表
。
广义表的结点表示形式需要两种结构的结点,单元素 或 子表 。
单元素结点 —— 两个域：标志域和值域；
子表结点 —— 三个域：标志域、指示表头的指针和指示表尾的指针域。
广义表的存储结构第五章 数组和广义表第 62页广义表链式存储结构的形式定义在广义链表中有两种不同结构的结点：单元素结点和子表结点。因此在广义链表的存储结构中，结点的表示形式应是一个变体记录。故有
typedef enum { Atom,List } ElemTag;
typedef struct nodetype{
ElemTag tag;
union{
datatype data;
struct{ struct nodetype *hp,*tp } ptr;
}
} *GList;
tag=0 data tag=1 hp tp
单元素结点 子表结点图 5.8 列表的链表结点结构
广义表的存储结构第五章 数组和广义表第 63页广义表的链式存储结构示例示例
A=( ); B=(e); C=(a,(b,c,d));
D=(A,B,C); E=(a,E).
存储结构
A=NULL
1 ^ 1 1 ^B→
0 e 0 a 1 ^1 1
0 b 0 c 0 d
1 ^ 1 1 ^D→
1 1 ^E→
0 a
C→
图 5.9 广义表的存储结构示例
((b,c,d))
(B,C) (C)
广义表的存储结构
(c,d) (d)
第五章 数组和广义表第 64页
广义表的存储结构形式定义
typedef enum{ Atom,List } ElemTag;
typedef struct nodetype{
ElemTag tag;
union{
datatype data;
struct nodetype *hp
};
nodetype *tp;
} *GList;
tag=1 data
单元素结点 表结点
tag=0 hp tp
2) 广义表的另一种链式存储结构
tp
hp指向其表头
tp指向同一层的下一结点 (不是指向其表尾 )
第五章 数组和广义表第 65页
广义表的存储结构
1 ^ 1 ^B→
0 e 0 a 1 ^
0 b 0 c 0 d
1 ^
1 1 ^
D→ 1E→
C→
1 ^ ^A→
^
^
1 ^ 0 a 1 ^
示例,A=( ) B=(e) C=(a,(b,c,d)) D=(A,B,C) E=(a,E)
hp指向其表头
tp指向同一层的下一结点 (不是指向其表尾 )
2) 广义表的另一种链式存储结构广义表的表指针始终指向一个表节点（即使是空表）
第五章 数组和广义表第 66页示例 三元多项式
D(x,y,z) = x10y3z2 + 2x6y3z2 + 3x5y2z2 + x4y4z + 6x3y4z + 2yz + 15
由于 m(今 m=3)元多项式中每一项的变化数目不均匀，而每一变元均是重要信息，故不适于用线性表表示。
今改写 P(x,y,z):
P(x,y,z)=((x10+2x6)y3+3x5y2)z2+((x4+6x3)y4+2y)z+15
Az2+Bz+15z0
其中
A=(x10+2x6)y3+3x5y2 Cy3+Dy2
C=x10+2x6,D=3x5
B=(x4+6x3)y4+2y Ey4+Fy
E=x4+6x3,F=2x0
m元多项式的表示用广义表表示三元多项式 P
P=z((A,2),(B,1),(15,0))
A=y((C,3),(D,2))
C=x((1,10),(2,6)) D=x((3,5))
B=y((E,4),(F,1))
E=x((1,4),(6,3)) F=x((2,0))
第五章 数组和广义表第 67页结论 每一个多项式都可看作是由一个变量加上若干个系数指数偶对所组成。任何一个 m元多项式均可先分解出一个主变元，即它是主变元的多项式，随后再分解出第二个变元，即其系数又是第二个变元的多项式，如此类推
,从而可用广义表来表示 m元多项式 。广义表的 深度即为变元个数 。
P(x,y,z)=z((A,2),(B,1),(15,0))
=z((y((c,3),(D,2)),2),
(y((E,4),(F,1)),1),
(15,0))
=z((y((x((1,10),(2,6)),3),
(x((3,5)),2)),2),
(y((x((1,4),(6,3)),4),
(x((2,0)),1)),1),
(15,0))
m元多项式的表示第五章 数组和广义表第 68页以类似于广义表的第二种存储结构形式来表示 m元多项式的广义表的存储结构链表的结点结构
tag=0
单元素结点 表结点
tag=1 exp hp tpexp coef tp
形式定义
typedef struct MPNode{
ElemTag tag;
int exp; //指数
union{
float coef; //系数
struct MPNode *hp；
}
struct MPNode *tp;
} *MPList；
m元多项式的广义表的存储结构其中
exp：指数域,coef,系数域
hp：指向其系数子表
tp：指向同一层的下一结点第五章 数组和广义表第 69页
1 2 1 1 0 0 15 ^
头指针 P
图 5.12 三元多项式 P(x,y,z)的存储结构示意图
m元多项式的广义表的存储结构
A B
Z层
1 3 1 1 ^1 2 ^ 1 4 Y层
X层0 0 2 ^0 5 3 ^0 10 1
0 3 6 ^0 6 2 ^
0 4 1
在每一层上增设一个表头结点并利用 exp指示该层的变元
1 ^
1
1
1
1 11
z y x
Z
∩
1 ^3
多项式中变元的个数第五章 数组和广义表第 70页作为一种递归的数据结构，有关广义表的运算许多都是可以采用递归算法实现的，例如求广义表的深度，复制广义表，建立广义表存储结构等运算，以及对两个广义表判定是否相等等问题，均可使用递归实现。 这里假定广义表都是非递归表且无共享子表。
1）判定两个广义表是否相等条件,两个广义表 s与 t的长度相等，且每个元素 (单元表或子表 )均对应相等 。
思想,(1)当 s=NULL,t=NULL，则返回 true； (空表相等 )
(2)若均为数据域，则看其数据是否相等；
(3)若为子表，则递归调用。看表头、表尾。
(4)若表头相等，则看表尾。
广义表的递归算法第五章 数组和广义表第 71页
Status equal_lists( Glist s,Glist t) //头尾链表存储
{ eq = false; //初始假设两个广义表为不相等
if( s==NULL && t==NULL ) return true //两个空广义表相等
if( s≠NULL && t≠NULL ){ //若有一个为 NULL，则返回 eq为 false
if( s->tag == t->tag ) //若标志域不等，则返回 eq为 false
{ if( s->tag == 0 ) //单元素结点
{ if( s->data == t->data ) eq = true;
else eq = false; }
else { //广义表（子表）
eq = equal_lists( s->hp,t->hp ); //处理表头
if( eq ) eq = equal_lists( s->tp,t->tp ); //表尾
}
};
}
return(eq)
} //equal_lists
1）判定两个广义表是否相等
广义表的递归算法第五章 数组和广义表第 72页
2）求广义表的深度定义 广义表的深度系指广义表中括弧的重数。
定义
A=( ),DEPTH(A)=1 （但 DEPTH(a)=0）
B=(e),DEPTH(B)=1
C=(a,(b,c,d)) DEPTH(C)=2
D=(A,B,C)=（ ( ),(e),(a,(b,c,d))）则 DEPTH(D)=3
E=(a,E)=（ a,(a,(a,(···)))）
E是递归表，不在讨论之列广义表 LS=(α1,α2,···,αn)的深度 DEPTH(LS)的递归定义
ninD E P T HM a x
LS
LS
LSD E P T H
i 11) },({1
,0
,1
)(
为单元素时当为空表时当比如
DEPTH(D)=1+Max{DEPTH(A),DEPTH(B),DEPTH(C)}
DEPTH(A)=1
DEPTH(B)=1+Max{DEPTH(e)}=1+0=1
DEPTH(C)=1+Max{DEPTH(a),DEPTH((b,c,d))} =1+Max{0,1}=2
故 DEPTH(D)=1+Max{1,1,2}=3.
单元素第五章 数组和广义表第 73页求广义表深度的递归算法 (头尾链表存储 )
int depth_lists( Glist ls )
{ //求 ls为头指针的广义表的深度
if( ls == NULL ) return(1); //空表
if( ls->tag == 0 ) return(0); //单元素
max = 0; pp = ls;
while( pp ≠ NULL )
{ dep = depth_lists(pp->hp); //求 pp->hp为头指针的子表深度
if( dep > max ) max = dep;
pp = pp->tp
};
return( max + 1 );
} //depth_lists 算 法 5.5
广义表的递归算法
2）求广义表的深度第五章 数组和广义表第 74页
copy_lists( GList ls,GList &newls)
//复制广义表 ls的一个副本 newls
{ if( ls == NULL ){ //复制空表
newls = NULL; return；
}
newls = new( Glist ); newls->tag = ls->tag;
if( ls->tag == 0 )
newls->data = ls->data; //建单元素结点
else
{ copy_lists( ls->hp,newls->hp );
//复制广义表 ls->hp的一个副本 newls->hp
copy_lists( ls->tp,mewls->tp );
//复制广义表 ls->tp的一个副本 newls->tp
}
}; //copy_lists 算 法 5.6
3） 复制广义表算法思想：只要分别复制广义表的表头和表尾，然后合成即可。
复制广义表操作的递归定义 (设 LS是原表,NewLS是复制表 )：
(1) 基本项,InitGList( NewLS )，当 LS == NULL
(2) 归纳项,Copy(Head(LS)→Head(NewLS) //复制表头
Copy(Tail(LS)→Tail(NewLS) //复制表尾第五章 数组和广义表第 75页第五章 数组和广义表 小结内容提要
● 数组的逻辑结构特征及其存储方式
● 特殊矩阵和稀疏矩阵的压缩存储及操作
● 广义表的逻辑结构和存储结构学习要点
● 熟悉数组在以 行 为主序的存储结构中的地址计算方法
● 熟悉特殊矩阵在压缩存储时的下标变换
● 理解稀疏矩阵常用的两种压缩存储表示 (三元组表的十字链表 )的特点及适用范围，领会以三元组表表示的稀疏矩阵进行矩阵运算时的处理方法以及建立十字链表的算法
● 熟悉广义表的有关概念、表示方法以及存储结构，掌握广义表求表头、表尾的方法，理解广义表的基本应用
