1北京邮电大学自动化学院
第五章 数组和广义表
? 5.1 数组的定义
? 5.2 数组的顺序表示和实现
? 5.3 矩阵的压缩存储
? 5.3.1 特殊矩阵
? 5.3.2 稀疏矩阵
? 5.4 广义表的定义
? 5.5 广义表的存储结构
2北京邮电大学自动化学院
? 数组和广义表可看成是一种特殊的线性表,其特殊在于，表
中的所有元素本身也是一种线性表。
?
?
?
?
?
?
?
?
?
?
?
?
??
mnmm
n
n
nm
aaa
aaa
aaa
A
?
????
?
?
21
22221
11211
? 数组是我们最熟悉的数据类型，在早期的高级语言中，数组
是唯一可供使用的数据类型。由于数组中各元素具有统一的
类型，并且数组元素的下标一般具有固定的上界和下界，因
此，数组的处理比其它复杂的结构更为简单。多维数组是向
量的推广。例如，二维数组：
5.1 数组的定义
3北京邮电大学自动化学院
? 二维数组可以看成是由 行向量组成的向量,也可以看成是
列向量组成的向量 。
? 同样，可把三维数组看成是一个线性表，表中每一个数组
元素为一个二维数组。依次类推，可把 n维数组看成是一个
线性表，表中每一个数据元素是一个 n-1维数组。
? 数组的运算,数组一旦被定义，它的维数和维界就不再改
变。因此，除了结构的初始化和销毁之外,数组只有存取
元素和修改元素值的操作。
? 即给定一组下标，存取或修改相应的数组元素。
5.1 数组的定义
4北京邮电大学自动化学院
? 1、顺序存储结构
5.2 数组的顺序表示和实现
? 顺序存储结构,用一组地址连续的存储单元依次存放数据元
素，称为数组的顺序存储结构。
? 由于计算机的内存结构是一维的，因此用一维内存来表示多
维数组，就必须按某种次序将数组元素排成一列序列，然后
将这个线性序列存放在存储器中。
? 由于对数组一般不做插入和删除操作，也就是说，数组一旦
建立，结构中的元素个数和元素间的关系就不再发生变化。
因此,一般都是采用顺序存储的方法来表示数组。
5北京邮电大学自动化学院
? 通常有两种顺序存储方式：
2、顺序存储方式
? ⑴ 行优先顺序 —— 将数组元素按行排列，第 i+1个行向量紧接在
第 i个行向量后面。以二维数组为例，按行优先顺序存储的线性
序列为,a11,a12,…,a 1n,a21,a22,…a 2n,……,a m1,am2,…,a mn
? 在 PASCAL,C语言中，数组就是按行优先顺序存储的。
? ⑵ 列优先顺序 —— 将数组元素按列向量排列，第 j+1个列向量紧
接在第 j个列向量之后,A的 m*n个元素按列优先顺序存储的线
性序列为：
? a11,a21,…,a m1,a12,a22,…a m2,……,a 1n,a2n,…,a mn
? 在 FORTRAN语言中，数组就是按列优先顺序存储的。
6北京邮电大学自动化学院
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
按列序为主序存放
0
m-1
m*n-1
m
amn
…….,
a2n
a1n
……….
am2
…….,
a22
a12
am1
…….
a21
a11
a11 a12 …….,a1n
a21 a22 …….,a2n
am1 am2 …….,amn
………………….
Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l
7北京邮电大学自动化学院
? 以上规则推广到多维数组的情况,行优先顺序可规定为先排
最右的下标，从右到左，最后排最左下标 ；
3,n维数组
? 按上述两种方式顺序存储的数组，只要知道开始结点的存放
地址（即基地址）、维数和每维的上、下界，以及每个数组
元素所占用的单元数，就可以将数组元素的存放地址表示为
其下标的线性函数。因此,数组中的任一元素可以在相同的
时间内存取，即顺序存储的数组是一个随机存取结构。
? 列优先顺序与此相反，先排最左下标，从左向右，最后排最
右下标。
8北京邮电大学自动化学院
? 例如，二维数组 Amn按“行优先顺序”存储在内存中，假设
每个元素占用 d个存储单元。
4、地址公式
? 元素 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
9北京邮电大学自动化学院
? 上述讨论均是假设数组各维的下界是 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的地
址计算函数为：
4、地址公式
? LOC(aij)=LOC(ac1c2)+[(i-c1)*(d2-c2+1)+j-c2)]*d
? 例如，在 C语言中，数组各维下标的下界是 0，因此在 C语言
中，二维数组的地址计算公式为：
? LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d
10北京邮电大学自动化学院
? 在科学与工程计算问题中，矩阵是一种常用的数学对象，在
高级语言编制程序时，简单而又自然的方法，就是将一个矩
阵描述为一个二维数组。但是在矩阵中非零元素呈某种规律
分布或者矩阵中出现大量的零元素的情况下，看起来存储密
度仍为 1,但实际上占用了许多单元去存储重复的非零元素
或零元素,这对高阶矩阵会造成极大的浪费，为了节省存储
空间,我们可以对这类矩阵进行压缩存储。
5.3 矩阵的压缩存储
? 压缩存储,为多个相同的非零元素只分配一个存储空间；对
零元素不分配空间。
? 假若值相同的元素或零元素在矩阵中的分布有一定规律，则
我们称此类矩阵为 特殊矩阵 ；反之，称为 稀疏矩阵 。
11北京邮电大学自动化学院
? 1、对称矩阵
5.3.1 特殊矩阵
? 在一个 n阶方阵 A中，若元
素满足下述性质：
aij=aji 0≦ i,j≦ n-1
? 则称 A为对称矩阵 。如图 5.1便是一个 5阶对称矩阵。 对称矩
阵中的元素关于主对角线对称，故只要存储矩阵中上三角或
下三角中的元素，让每两个对称的元素共享一个存储空间，
这样，能节约近一半的存储空间。不失一般性，我们按“行
优先顺序”存储主对角线（包括对角线）以下的元素，其存
储形式如图所示：
a00 a01 …,… ….,a 0n-1
a10 a11 …….,……,a 1n-1
an-10 an-11 …….,a n-1n-1
…………………,
12北京邮电大学自动化学院
a00
a10 a 11
a20 a21 a23
………………..
an-1 0 a n-1 1 a n-1 2 …a n-1 n-1
a00 a01 …,… ….,a 0n-1
a10 a11 …….,……,a 1n-1
an-10 an-11 …….,a n-1n-1
…………………,
图 5.1 对称矩阵
? 在这个下三角矩阵中，第 i行恰有 i+1个元素，元素总数为：
(i+1)=n(n+1)/2。这样可将 n2个压缩到 n(n+1)/2个元的空间
中。
? 因此，我们可以按图中箭头所指的次序将这些元素存放在一
个向量 sa[0..n(n+1)/2-1]中。为了便于访问对称矩阵 A中的
元素，我们必须在 aij和 sa[k]之间找一个对应关系。
1、对称矩阵
13北京邮电大学自动化学院
? i≧ j，则 aij在下三角形中。 aij之前的 i行（从第 0行到第 i-1
行）一共有 1+2+…+i=i(i+1)/2 个元素，在第 i行上,aij之前
恰有 j个元素（即 ai0,ai1,ai2,…,a ij-1），因此有：
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
14北京邮电大学自动化学院
? 因此,aij的地址可用下列式计算：
? LOC(aij)=LOC(sa[k])
?=LOC(sa[0])+k*d=LOC(sa[0]+[I*(I+1)/2+J]*d）
a00 a10 a11 a20 …… an-1 0 …… an-1,n-1
? 有了上述的下标交换关系，对于任意给定一组下标 (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
15北京邮电大学自动化学院
? 以主对角线划分，三角矩阵有 上三角和下三角 两种。
2、三角矩阵
a00 a01 … a 0 n-1
c a11 … a 1 n-1
…………….,
c c … a n-1 n-1
(a)上三角矩阵
a00 c … c
a10 a11 … c
……………..
an-1 0 an-1 1 … a n-1 n-1
(b)下三角矩阵
图 5.2 三角矩阵
? 上三角矩阵 如图所示，它的下三角（不包括主对角线）中的
元素均为常数。
? 下三角矩阵 正好相反，它的主对角线上方均为常数，如图所
示。在大多数情况下，三角矩阵常数为零。
16北京邮电大学自动化学院
? 带状矩阵,在带状矩阵中，所有的非零元素集中在以主对角线
为中心的带状区域中，即除了主对角线和主对角线相邻两侧的
若干条对角线上的元素之外，其余元素皆为零。这个带状区域
若包含主对角线下面及上面各 d条对角线上的元素，那么，方
阵称为半带宽为 d的带状矩阵。设 n阶方阵 A是半带宽为 d的带
状矩阵，则当 |i-j|>d时,aij=0,2d+1称为带状矩阵的带宽。
3、带状矩阵
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
……………………………
17北京邮电大学自动化学院
? 非零元素仅出现在主对角上，紧邻主对角线上面的 d条对角线上
和紧邻主对角线下面的 d条对角线上。显然，当 ∣ i-j∣ >d时，元
素 aij=0。
? 对带状矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一
个向量中，并且也能找到每个非零元素和向量下标的对应关系。
? 对于 n阶半带宽为 d的带状矩阵，只需存放带状区域之内的
n(2d+1)-d(d+1)个非零元素。为了计算非零元素存放位置方便，
除第 1行和第 n行外，每行都当做有 2d+1个元素，若少于 2d+1
个，则添零补足。将带状矩阵存储在 [(2d+1)n-2d)]s个存储单元
中，元素 aij的地址公式为：
?LOC[i,j]=Loc[1,1]+[(i-1)(2d+1)+(j-i)]s
? (1?i?n,1?j?n,|i-j|?d)
18北京邮电大学自动化学院
? 上述的各种特殊矩阵，其非零元素的分布都是有规律的，因
此总能找到一种方法将它们压缩存储到一个向量中，并且一
般都能找到矩阵中的元素与该向量的对应关系，通过这个关
系，仍能对矩阵的元素进行随机存取。
5.3.2 稀疏矩阵
? 什么是稀疏矩阵？
? 精确点，设在的矩阵 A中，有 s个非零元素。令 e=s/(m*n)，
称 e为矩阵的稀疏因子。通常认为 e≦ 0.05时称之为稀疏矩
阵。
? 简单说，设矩阵 A中有 s个非零元素，若 s远远小于矩阵元素
的总数（即 s≦ m× n），则称 A为 稀疏矩阵。
19北京邮电大学自动化学院
? 在存储稀疏矩阵时，为了节省存储单元，很自然地想
到使用压缩存储方法。但由于非零元素的分布一般是
没有规律的，因此在存储非零元素的同时，还必须同
时记下它所在的行和列的位置（ i, j)。
1、三元顺序表
? 反之，一个三元组 (i, j, aij)唯一确定了矩阵 A的一个
非零元。因此,稀疏矩阵可由表示非零元的三元组及
其行列数唯一确定。
20北京邮电大学自动化学院
? 例如，下列三元组表 ((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的另一种描述。而由上述三元组表
的不同表示方法 可引出稀疏矩阵不同的压缩存储方法。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
000000
0001400
000000
700000
0024009
01800012
1500300
T
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
00070015
00000180
00002400
01400003
0000000
00009120
M
图 5.4 稀疏矩阵 M和 T
1、三元顺序表
21北京邮电大学自动化学院
#define M 20
typedef 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
2、稀疏矩阵的压缩存储方法
22北京邮电大学自动化学院
3、求转置矩阵
? 问题描述,已知一个稀疏矩阵的三元组表，求该
矩阵转置矩阵的三元组表。
? 解决思路：
? （ 1） 将矩阵行、列维数互换
? （ 2）将每个三元组中的 i和 j相互调换
? （ 3）重排三元组次序，使 mb中元素以 T的行 (M的
列 )为主序
23北京邮电大学自动化学院
7600070015
00000180
00002400
01400003
0000000
00009120
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?M
67000000
0001400
000000
700000
0024009
01800012
1500300
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?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
i j v
0
1
2
3
4
5
6
7
8
m
a
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
m
b
24北京邮电大学自动化学院
? 一个 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，就必须重新排列三元
组的顺序。
25北京邮电大学自动化学院
? 由于 A的列是 B的行，因此，按 a.data的列序转置，所得
到的转置矩阵 B的三元组表 b.data必定是按行优先存放
的。
? 按这种方法设计的算法,其基本思想是,对 A中的每一
列 col(0≦ col≦ n-1)，通过从头至尾扫描三元表
a.data，找出所有列号等于 col的那些三元组，将它们的
行号和列号互换后依次放入 b.data中，即可得到 B的按行
优先的压缩存储表示。
方法一
26北京邮电大学自动化学院
? Status Transmatrix ( TSMatrix M,TSMatrix &T)
? {T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;
? if (T.tu){ q=1;
? for ( col=1;col<=M.nu;col++)
? for(p=1; p<=M.tu; p++)
? if(M.data[p].j==col){
? T.data[q].i=M.data[p].j;
? T.data[q].j=M.data[p].i;
? T.data[q].e=M.data[p].e;
? q++; } return OK; } //TransposeSMatrix
27北京邮电大学自动化学院
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
方法一
28北京邮电大学自动化学院
? 分析这个算法，主要的工作是在 p和 col的两个循环中完成
的，故算法的时间复杂度为 O(n*t)，即矩阵的列数和非零
元的个数的乘积成正比。而一般传统矩阵的转置算法为：
? for(col=1;col<=nu;++col)
? for(row=1;row<=mu;++row)
? t[col][row]=m[row][col];
? 时间复杂度为 O(n*m)。当非零元素的个数 t和 m*n同数量
级时，算法 transmatrix的时间复杂度为 O(m*n2)。
? 三元组顺序表虽然节省了存储空间，但时间复杂度比一般
矩阵转置的算法还要复杂，同时还有可能增加算法的难
度。 因此，此算法仅适用于 t<=m*n的情况。
方法一
29北京邮电大学自动化学院
? 按照 a.data中三元组的次序进行转置，并将转置后的三元组置
入 b中的恰当位置。
方法 2：快速转置算法
? 如果能预先确定矩阵 M中每一列（即 T中每一行）的第一个非
零元素在 b.data中应有的位置，那么在对 a.data中的三元组一
次作转置时，便可直接放到 b.data中恰当位置上去。
? 为了确定这些位置，在转置前，应先求得 M的每一列中非零元的
个数，进而求得每一列的第一个非零元在 b.data中应有的位置。
? 快速转置算法的思想,对 A扫描一次，按 A第二列提供的列号
一次确定装入 B的一个三元组的位置。具体实施如下：一遍扫
描先确定三元组的位置关系，二次扫描由位置关系装入三元
组。可见,位置关系是此种算法的关键。
30北京邮电大学自动化学院
? 实现：需要附设 num和 cpot两个数组。
? num[col]：表示矩阵 M中第 col列中非零元个数 ；
? cpot[col],指示 M中第 col列第一个非零元在 mb中位置
? 显然有：
? cpot[1]=1;
? cpot[col]=cpot[col-1]+num[col-1]; (2?col ?a.nu)
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
方法 2：快速转置算法
31北京邮电大学自动化学院
快速转置算法
? Status FastTransmatrix ( TSMatrix M,TSMatrix &T)
? {
? T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;
? if (T.tu){
? for ( col=1; col<=M.nu; ++col) num[col]=0;
? for (t=1;t<=M.tu;++t) ++num[M.data[t].j];
? // 求 M中每一列含非零元个数
? cpot[1]=1;//求第 col列中第 1个非零元素在 b.data中的序
号。
32北京邮电大学自动化学院
快速转置算法
? for (col=2;col<=M.nu;++col)
? cpot[col]=cpot[col-1]+num[col-1];
? for(p=1; p<=M.tu; p++)
? { col=M.data[p].j;q=cpot[col];
? } //if
? return OK; }//FastTransposeSMatrix
? T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i;
? T.data[q].e=M.data[p].e; ++cpot[col]; } //for
33北京邮电大学自动化学院
? 这个算法仅比前一个算法多用了两个辅助数组。
快速转置算法分析
? 从时间上看，算法中有四个并列的单循环，循环次数分别
为 nu和 tu，因而总的时间复杂度为 O（ nu＋ tu）。
? 在 M的非零元素个数 tu和 mu× nu等数量级时，其时间复
杂度为 O（ mu× nu），和经典算法的时间复杂度相同。
34北京邮电大学自动化学院
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
35北京邮电大学自动化学院
? tpedef struct OLNode
? {int i,j; ElemType e;
? struct OLNode *down,*right;}OLNode; *OLink;
i j e
down right
? 在链表中，每个非零元素可用一个含 5个域的结点表示，
right域用以链接同一行中下一个非零元素,down域用以
链接同一列中下一个非零元素。
4、十字链表
? 同一行的非零元素通过 right域链接成一个线性表，同一列
的非零元素通过 down域链接成一个线性表,每个非零元
素既是某行链表中的一个结点，又是某个列链表中的一个
结点,整个矩阵构成了一个十字交叉的链表，故称这样的
存储结构为 十字链表,可用两个分别存储行链表的头指针
和列链表的头指针的一维数组表示。
36北京邮电大学自动化学院
1 1 3
4 1 8
2 2 5 2 3 4
^
^ ^
^
^ ^ ^
34008
000
450
003
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?A
4、十字链表
37北京邮电大学自动化学院
例题：两个矩阵相加
? 假设两个矩阵相加后的结果为 A’，则和矩阵 A’中的非零元 aij’
只可能有三种情况,
? aij+bij
? 由此，当将 B加到 A上去时，对 A矩阵的十字链表来说：
? 改变接点的 e值（ aij+bij?0）
? aij (bij=0)
? bij (aij=0)
? 不变 (bij=0)
? 插入一个新结点 (aij=0)
38北京邮电大学自动化学院
? 还有一种情况是：和 A矩阵中的某个非零元相对应，和
矩阵 A’中是零元，即对 A的操作是删除一个接点
（ aij+bij=0）。
? 由此，整个运算过程可从矩阵的第一行起逐行进行。
对每一行都从表头出发分别找到 A和 B在该行中的第一
个非零元结点后，开始比较，然后按上述四种不同情
况分别处理。
例题：两个矩阵相加
39北京邮电大学自动化学院
? 广义表（ Lists，又称列表）是线性表的推广 。在第 2章中，
我们把线性表定义为 n?0个元素 a1,a2,a3,…,a n的有限序列。
线性表的元素仅限于原子项,原子是作为结构上不可分割的
成分，它可以是一个数或一个结构，若放松对表元素的这种
限制，容许它们具有其自身结构，这样就产生了广义表的概
念。
5.4 广义表的定义
? 广义表 是 n(n?0)个元素 a1,a2,a3,…,a n的有限序列，其中 ai或
者是原子项，或者是一个广义表。通常记作 LS=
（ a1,a2,a3,…,a n)。 LS是广义表的名字,n为它的长度。若 ai
是广义表，则称它为 LS的子表。
40北京邮电大学自动化学院
? 通常用圆括号将广义表括起来，用逗号分隔其中的元素。为
了区别原子和广义表,书写时用大写字母表示广义表，用小
写字母表示原子。 若广义表 LS（ n>=1) 非空，则 a1是 LS的
表头，其余元素组成的表 (a1,a2,…a n)称为 LS的表尾。
5.4 广义表的定义
? 显然广义表是递归定义的，这是因为在定义广义表时又用到
了广义表的概念。广义表的例子如下：
? （ 1） A=（） —— A是一个空表，其长度为零。
? （ 2） B=（ e） —— 表 B只有一个原子 e,B的长度为 1。
? （ 3） C=（ a,(b,c,d))—— 表 C的长度为 2，两个元素分别为原
子 a和子表 (b,c,d)。
? （ 4） D=（ A,B,C） —— 表 D的长度为 3，三个元素都是广义
表。显然，将子表的值代入后，则有 D=(( ),(e),(a,(b,c,d)))。
41北京邮电大学自动化学院
? （ 5） E=（ a,E） —— 这是一个递归的表，它的长度为 2,E
相当于一个无限的广义表 E=(a,(a,(a,(a,…)))),
? 例如,D=(E,F)
? 其中,
? E=(a,(b,c))
? F=(d,(e))
D
E F
a ( ) d ( )
b c e
5.4 广义表的定义
? 从上述定义和例子可推出广义表的三个重要结论：
? （ 1）广义表的元素可以是子表，而子表的元素还可以是子
表。 由此，广义表是一个多层次的结构，可以用图形象地表
示。
42北京邮电大学自动化学院
? （ 2）广义表可为其它表所共享。 例如在上述例（ 4）中，
广义表 A,B,C为 D的子表，则在 D中可以不必列出子表的
值，而是通过子表的名称来引用。
5.4 广义表的定义
? （ 3）广义表的递归性。
? 综上所述,广义表不仅是线性表的推广，也是树的推广。
? 广义表中所含括弧的重数称为表的深度,表中元素的层数
就是包括该元素的括弧重数。例如：
? F（ a,b，（ c，（ d）））。其中，单元素 a,b在第一
层,d在第三层，广义表的深度为 3。
43北京邮电大学自动化学院
? 由于广义表 (a1,a2,a3,…a n)中的数据元素可以具有不同的结
构，（或是原子，或是广义表），因此,难以用顺序存储
结构表示，通常采用链式存储结构,每个数据元素可用一
个结点表示。
tag=1 hp tp tag=0 atom表结点 原子结点
? 由于广义表中有两种数据元素，原子或广义表，因此，需
要两种结构的结点,一种是表结点，一种是原子结点 。 下
面介绍两种广义表的链式存储结构。
? 表结点由三个域组成,标志域、指示表头的指针域和指示
表尾的指针域；
? 而原子域只需两个域,标志域和值域 。
5.4 广义表的定义
44北京邮电大学自动化学院
L = ( a,( x,y ),( ( x ) ) )a ( x,y ) ( )
1
L
0 a
1 1
1
1
1
0 x
?
?
?
( )x
45北京邮电大学自动化学院
B C
D
E
1
0 e
1 1
0 a
1 1 1
1
0 a
1
1
0 d0 c0 b
1 1
? 广义表的存储结构示例
? （ 1） A=（）
? （ 2） B=（ e）
? （ 3） C=（ a,（ b,c,d））
? （ 4） D=（ A,B,C）
? （ 5） E=（ a,E）
46北京邮电大学自动化学院
5.5 m元多项式的表示
? 1、一元多项式
? 一个多项式可以一个长度为 m且每个数据元素有两个数据
项（系数项和指数项）的线性表来表示。
? 2,m元多项式
? 一个 m元多项式的每一项，最多有个 m变元，如果用线性
表来表示，则每个数据元素需要 m+1个数据项，以存储一
个系数值和 m个指数值。将产生两个问题：
? 造成浪费
? 线性表中结点大小不一样
47北京邮电大学自动化学院
? 因此，对于 m 元多项式中每一项的变化数目不均匀性和变
元信息的重要性，故不适于线性表表示。例如：
152632),,( 43442252362310 ??????? yzzyxzyxzyxzyxzyxzyxP
15)2)6(()3)2((),,( 4342253610 ??????? zyyxxzyxyxxzyxP
02 15 zBzAz ??
? 上式是变元 Z的多项式，即
? 其中,A和 B本身又是一个（ x,y）的二元多项式,15是 Z的零
次项的系数。
? 进一步考察 A(x,y)，又可把它看成是 y的多项式。
? Cy3+Dy2，而其中 C和 D为 x的一元多项式。循环以往，每个多
项式都可看作是由一个变量加上若干个系数指数偶对组成。
5.5 m元多项式的表示
48北京邮电大学自动化学院
? 任何一个 m 元多项式都可如此做,先分解出一个主变元，随
后再分解出第二个变元，等等 。由此，一个 m元的多项式首先
是它的主变元的多项式，而其系数又是第二变元的多项式，由
此，可用广义表来表示 m元多项式。例如上述三元多项式可用
下式的广义表表示，广义表的深度即为变元个数。
15)2)6(()3)2((),,( 4342253610 ??????? zyyxxzyxyxxzyxP
? P=Z（（ A,2），（ B,1），（ 15,0））
? 我们在广义表的括号之前加一个变元，以示各层的变元。
? A=y((C,3),(D,2)) B=y((E,4),(F,1))
? C=x((1,10),(2,6)) D=x((3,5))
? E=x((1,4),(6,3)) F=x((2,0))
5.5 m元多项式的表示
49北京邮电大学自动化学院
? 可以类似广义表的第二种存储结构来定义表示 m元多项式的
广义表的存储结构。链表的结点结构为：
? exp为指数域,coef为系数域,hp指向其系数子表,tp指
向同一层的下一个结点。
? 在每一层上增设一个表头结点，并利用 exp指示该层的变
元，可用一维数组存储多项式中所有变元，故 exp域存储
的是该变元在一维数组中的下标。
? 头指针 p所指表结点中 exp的值 3为多项式中变元的个数。
P112页的图为三元多项式 P(x,y,z)的存储结构示意图。
tphptag=1 exp tpcoeftag=0 exp
表结点 原子结点
5.5 m元多项式的表示
50北京邮电大学自动化学院
? 1,了解数组的两种存储表示方法，并掌握数组在以行为
主的存储结构中的地址计算方法。
第五章 思考题
? 2,掌握对特殊矩阵进行压缩存储时的下标变换公式。
? 3,了解稀疏矩阵的两类压缩存储方法的特点和适用范
围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的
处理方法。
? 4,掌握广义表的结构特点及其存储表示方法，读者可根
据自己的习惯熟练掌握任意一种结构的链表，学会对非
空广义表进行分解的两种分析方法：即可将一个非空广
义表分解为表头和表尾两部分或者分解为 n个子表。
51北京邮电大学自动化学院
第五章 作业
? 一、选择题
? 1、一维数组和线性表的区别是 A 。
? （ A）前者长度固定，后者长度可变 （ B）后者长度固定，前者长度可变
（ C）两者长度均固定 （ D）两者长度均可变
? 2、数组 A中，每个元素 A的长度为 3个字节，行下标 i从 1到 8，
列下标 j从 1到 10，从首地址 SA开始连续存放在存储器内，该数
组按行存放时，元素 A[8][5]的起始地址为 C 。
? （ A） SA+141 （ B） SA+144
? （ C） SA+222 （ D） SA+225
52北京邮电大学自动化学院
? 3、设有一个 10阶的对称矩阵，采用压缩存储方式，以行序
为主存储,a1,1为第一个元素，其存储地址为 1，每个元素占 1
个地址空间，则 a8,5的地址为 D 。
? （ A） 13 （ B） 33 （ C） 18 （ D） 40
? 二、填空题
? 1、广义表（ a，（ a,b）,d,e，（（ I,j）,k））表的长
度是 5,深度是 3 。
第五章 作业
第五章 数组和广义表
? 5.1 数组的定义
? 5.2 数组的顺序表示和实现
? 5.3 矩阵的压缩存储
? 5.3.1 特殊矩阵
? 5.3.2 稀疏矩阵
? 5.4 广义表的定义
? 5.5 广义表的存储结构
2北京邮电大学自动化学院
? 数组和广义表可看成是一种特殊的线性表,其特殊在于，表
中的所有元素本身也是一种线性表。
?
?
?
?
?
?
?
?
?
?
?
?
??
mnmm
n
n
nm
aaa
aaa
aaa
A
?
????
?
?
21
22221
11211
? 数组是我们最熟悉的数据类型，在早期的高级语言中，数组
是唯一可供使用的数据类型。由于数组中各元素具有统一的
类型，并且数组元素的下标一般具有固定的上界和下界，因
此，数组的处理比其它复杂的结构更为简单。多维数组是向
量的推广。例如，二维数组：
5.1 数组的定义
3北京邮电大学自动化学院
? 二维数组可以看成是由 行向量组成的向量,也可以看成是
列向量组成的向量 。
? 同样，可把三维数组看成是一个线性表，表中每一个数组
元素为一个二维数组。依次类推，可把 n维数组看成是一个
线性表，表中每一个数据元素是一个 n-1维数组。
? 数组的运算,数组一旦被定义，它的维数和维界就不再改
变。因此，除了结构的初始化和销毁之外,数组只有存取
元素和修改元素值的操作。
? 即给定一组下标，存取或修改相应的数组元素。
5.1 数组的定义
4北京邮电大学自动化学院
? 1、顺序存储结构
5.2 数组的顺序表示和实现
? 顺序存储结构,用一组地址连续的存储单元依次存放数据元
素，称为数组的顺序存储结构。
? 由于计算机的内存结构是一维的，因此用一维内存来表示多
维数组，就必须按某种次序将数组元素排成一列序列，然后
将这个线性序列存放在存储器中。
? 由于对数组一般不做插入和删除操作，也就是说，数组一旦
建立，结构中的元素个数和元素间的关系就不再发生变化。
因此,一般都是采用顺序存储的方法来表示数组。
5北京邮电大学自动化学院
? 通常有两种顺序存储方式：
2、顺序存储方式
? ⑴ 行优先顺序 —— 将数组元素按行排列，第 i+1个行向量紧接在
第 i个行向量后面。以二维数组为例，按行优先顺序存储的线性
序列为,a11,a12,…,a 1n,a21,a22,…a 2n,……,a m1,am2,…,a mn
? 在 PASCAL,C语言中，数组就是按行优先顺序存储的。
? ⑵ 列优先顺序 —— 将数组元素按列向量排列，第 j+1个列向量紧
接在第 j个列向量之后,A的 m*n个元素按列优先顺序存储的线
性序列为：
? a11,a21,…,a m1,a12,a22,…a m2,……,a 1n,a2n,…,a mn
? 在 FORTRAN语言中，数组就是按列优先顺序存储的。
6北京邮电大学自动化学院
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
按列序为主序存放
0
m-1
m*n-1
m
amn
…….,
a2n
a1n
……….
am2
…….,
a22
a12
am1
…….
a21
a11
a11 a12 …….,a1n
a21 a22 …….,a2n
am1 am2 …….,amn
………………….
Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l
7北京邮电大学自动化学院
? 以上规则推广到多维数组的情况,行优先顺序可规定为先排
最右的下标，从右到左，最后排最左下标 ；
3,n维数组
? 按上述两种方式顺序存储的数组，只要知道开始结点的存放
地址（即基地址）、维数和每维的上、下界，以及每个数组
元素所占用的单元数，就可以将数组元素的存放地址表示为
其下标的线性函数。因此,数组中的任一元素可以在相同的
时间内存取，即顺序存储的数组是一个随机存取结构。
? 列优先顺序与此相反，先排最左下标，从左向右，最后排最
右下标。
8北京邮电大学自动化学院
? 例如，二维数组 Amn按“行优先顺序”存储在内存中，假设
每个元素占用 d个存储单元。
4、地址公式
? 元素 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
9北京邮电大学自动化学院
? 上述讨论均是假设数组各维的下界是 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的地
址计算函数为：
4、地址公式
? LOC(aij)=LOC(ac1c2)+[(i-c1)*(d2-c2+1)+j-c2)]*d
? 例如，在 C语言中，数组各维下标的下界是 0，因此在 C语言
中，二维数组的地址计算公式为：
? LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d
10北京邮电大学自动化学院
? 在科学与工程计算问题中，矩阵是一种常用的数学对象，在
高级语言编制程序时，简单而又自然的方法，就是将一个矩
阵描述为一个二维数组。但是在矩阵中非零元素呈某种规律
分布或者矩阵中出现大量的零元素的情况下，看起来存储密
度仍为 1,但实际上占用了许多单元去存储重复的非零元素
或零元素,这对高阶矩阵会造成极大的浪费，为了节省存储
空间,我们可以对这类矩阵进行压缩存储。
5.3 矩阵的压缩存储
? 压缩存储,为多个相同的非零元素只分配一个存储空间；对
零元素不分配空间。
? 假若值相同的元素或零元素在矩阵中的分布有一定规律，则
我们称此类矩阵为 特殊矩阵 ；反之，称为 稀疏矩阵 。
11北京邮电大学自动化学院
? 1、对称矩阵
5.3.1 特殊矩阵
? 在一个 n阶方阵 A中，若元
素满足下述性质：
aij=aji 0≦ i,j≦ n-1
? 则称 A为对称矩阵 。如图 5.1便是一个 5阶对称矩阵。 对称矩
阵中的元素关于主对角线对称，故只要存储矩阵中上三角或
下三角中的元素，让每两个对称的元素共享一个存储空间，
这样，能节约近一半的存储空间。不失一般性，我们按“行
优先顺序”存储主对角线（包括对角线）以下的元素，其存
储形式如图所示：
a00 a01 …,… ….,a 0n-1
a10 a11 …….,……,a 1n-1
an-10 an-11 …….,a n-1n-1
…………………,
12北京邮电大学自动化学院
a00
a10 a 11
a20 a21 a23
………………..
an-1 0 a n-1 1 a n-1 2 …a n-1 n-1
a00 a01 …,… ….,a 0n-1
a10 a11 …….,……,a 1n-1
an-10 an-11 …….,a n-1n-1
…………………,
图 5.1 对称矩阵
? 在这个下三角矩阵中，第 i行恰有 i+1个元素，元素总数为：
(i+1)=n(n+1)/2。这样可将 n2个压缩到 n(n+1)/2个元的空间
中。
? 因此，我们可以按图中箭头所指的次序将这些元素存放在一
个向量 sa[0..n(n+1)/2-1]中。为了便于访问对称矩阵 A中的
元素，我们必须在 aij和 sa[k]之间找一个对应关系。
1、对称矩阵
13北京邮电大学自动化学院
? i≧ j，则 aij在下三角形中。 aij之前的 i行（从第 0行到第 i-1
行）一共有 1+2+…+i=i(i+1)/2 个元素，在第 i行上,aij之前
恰有 j个元素（即 ai0,ai1,ai2,…,a ij-1），因此有：
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
14北京邮电大学自动化学院
? 因此,aij的地址可用下列式计算：
? LOC(aij)=LOC(sa[k])
?=LOC(sa[0])+k*d=LOC(sa[0]+[I*(I+1)/2+J]*d）
a00 a10 a11 a20 …… an-1 0 …… an-1,n-1
? 有了上述的下标交换关系，对于任意给定一组下标 (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
15北京邮电大学自动化学院
? 以主对角线划分，三角矩阵有 上三角和下三角 两种。
2、三角矩阵
a00 a01 … a 0 n-1
c a11 … a 1 n-1
…………….,
c c … a n-1 n-1
(a)上三角矩阵
a00 c … c
a10 a11 … c
……………..
an-1 0 an-1 1 … a n-1 n-1
(b)下三角矩阵
图 5.2 三角矩阵
? 上三角矩阵 如图所示，它的下三角（不包括主对角线）中的
元素均为常数。
? 下三角矩阵 正好相反，它的主对角线上方均为常数，如图所
示。在大多数情况下，三角矩阵常数为零。
16北京邮电大学自动化学院
? 带状矩阵,在带状矩阵中，所有的非零元素集中在以主对角线
为中心的带状区域中，即除了主对角线和主对角线相邻两侧的
若干条对角线上的元素之外，其余元素皆为零。这个带状区域
若包含主对角线下面及上面各 d条对角线上的元素，那么，方
阵称为半带宽为 d的带状矩阵。设 n阶方阵 A是半带宽为 d的带
状矩阵，则当 |i-j|>d时,aij=0,2d+1称为带状矩阵的带宽。
3、带状矩阵
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
……………………………
17北京邮电大学自动化学院
? 非零元素仅出现在主对角上，紧邻主对角线上面的 d条对角线上
和紧邻主对角线下面的 d条对角线上。显然，当 ∣ i-j∣ >d时，元
素 aij=0。
? 对带状矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一
个向量中，并且也能找到每个非零元素和向量下标的对应关系。
? 对于 n阶半带宽为 d的带状矩阵，只需存放带状区域之内的
n(2d+1)-d(d+1)个非零元素。为了计算非零元素存放位置方便，
除第 1行和第 n行外，每行都当做有 2d+1个元素，若少于 2d+1
个，则添零补足。将带状矩阵存储在 [(2d+1)n-2d)]s个存储单元
中，元素 aij的地址公式为：
?LOC[i,j]=Loc[1,1]+[(i-1)(2d+1)+(j-i)]s
? (1?i?n,1?j?n,|i-j|?d)
18北京邮电大学自动化学院
? 上述的各种特殊矩阵，其非零元素的分布都是有规律的，因
此总能找到一种方法将它们压缩存储到一个向量中，并且一
般都能找到矩阵中的元素与该向量的对应关系，通过这个关
系，仍能对矩阵的元素进行随机存取。
5.3.2 稀疏矩阵
? 什么是稀疏矩阵？
? 精确点，设在的矩阵 A中，有 s个非零元素。令 e=s/(m*n)，
称 e为矩阵的稀疏因子。通常认为 e≦ 0.05时称之为稀疏矩
阵。
? 简单说，设矩阵 A中有 s个非零元素，若 s远远小于矩阵元素
的总数（即 s≦ m× n），则称 A为 稀疏矩阵。
19北京邮电大学自动化学院
? 在存储稀疏矩阵时，为了节省存储单元，很自然地想
到使用压缩存储方法。但由于非零元素的分布一般是
没有规律的，因此在存储非零元素的同时，还必须同
时记下它所在的行和列的位置（ i, j)。
1、三元顺序表
? 反之，一个三元组 (i, j, aij)唯一确定了矩阵 A的一个
非零元。因此,稀疏矩阵可由表示非零元的三元组及
其行列数唯一确定。
20北京邮电大学自动化学院
? 例如，下列三元组表 ((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的另一种描述。而由上述三元组表
的不同表示方法 可引出稀疏矩阵不同的压缩存储方法。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
000000
0001400
000000
700000
0024009
01800012
1500300
T
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
00070015
00000180
00002400
01400003
0000000
00009120
M
图 5.4 稀疏矩阵 M和 T
1、三元顺序表
21北京邮电大学自动化学院
#define M 20
typedef 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
2、稀疏矩阵的压缩存储方法
22北京邮电大学自动化学院
3、求转置矩阵
? 问题描述,已知一个稀疏矩阵的三元组表，求该
矩阵转置矩阵的三元组表。
? 解决思路：
? （ 1） 将矩阵行、列维数互换
? （ 2）将每个三元组中的 i和 j相互调换
? （ 3）重排三元组次序，使 mb中元素以 T的行 (M的
列 )为主序
23北京邮电大学自动化学院
7600070015
00000180
00002400
01400003
0000000
00009120
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?M
67000000
0001400
000000
700000
0024009
01800012
1500300
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?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
i j v
0
1
2
3
4
5
6
7
8
m
a
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
m
b
24北京邮电大学自动化学院
? 一个 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，就必须重新排列三元
组的顺序。
25北京邮电大学自动化学院
? 由于 A的列是 B的行，因此，按 a.data的列序转置，所得
到的转置矩阵 B的三元组表 b.data必定是按行优先存放
的。
? 按这种方法设计的算法,其基本思想是,对 A中的每一
列 col(0≦ col≦ n-1)，通过从头至尾扫描三元表
a.data，找出所有列号等于 col的那些三元组，将它们的
行号和列号互换后依次放入 b.data中，即可得到 B的按行
优先的压缩存储表示。
方法一
26北京邮电大学自动化学院
? Status Transmatrix ( TSMatrix M,TSMatrix &T)
? {T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;
? if (T.tu){ q=1;
? for ( col=1;col<=M.nu;col++)
? for(p=1; p<=M.tu; p++)
? if(M.data[p].j==col){
? T.data[q].i=M.data[p].j;
? T.data[q].j=M.data[p].i;
? T.data[q].e=M.data[p].e;
? q++; } return OK; } //TransposeSMatrix
27北京邮电大学自动化学院
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
方法一
28北京邮电大学自动化学院
? 分析这个算法，主要的工作是在 p和 col的两个循环中完成
的，故算法的时间复杂度为 O(n*t)，即矩阵的列数和非零
元的个数的乘积成正比。而一般传统矩阵的转置算法为：
? for(col=1;col<=nu;++col)
? for(row=1;row<=mu;++row)
? t[col][row]=m[row][col];
? 时间复杂度为 O(n*m)。当非零元素的个数 t和 m*n同数量
级时，算法 transmatrix的时间复杂度为 O(m*n2)。
? 三元组顺序表虽然节省了存储空间，但时间复杂度比一般
矩阵转置的算法还要复杂，同时还有可能增加算法的难
度。 因此，此算法仅适用于 t<=m*n的情况。
方法一
29北京邮电大学自动化学院
? 按照 a.data中三元组的次序进行转置，并将转置后的三元组置
入 b中的恰当位置。
方法 2：快速转置算法
? 如果能预先确定矩阵 M中每一列（即 T中每一行）的第一个非
零元素在 b.data中应有的位置，那么在对 a.data中的三元组一
次作转置时，便可直接放到 b.data中恰当位置上去。
? 为了确定这些位置，在转置前，应先求得 M的每一列中非零元的
个数，进而求得每一列的第一个非零元在 b.data中应有的位置。
? 快速转置算法的思想,对 A扫描一次，按 A第二列提供的列号
一次确定装入 B的一个三元组的位置。具体实施如下：一遍扫
描先确定三元组的位置关系，二次扫描由位置关系装入三元
组。可见,位置关系是此种算法的关键。
30北京邮电大学自动化学院
? 实现：需要附设 num和 cpot两个数组。
? num[col]：表示矩阵 M中第 col列中非零元个数 ；
? cpot[col],指示 M中第 col列第一个非零元在 mb中位置
? 显然有：
? cpot[1]=1;
? cpot[col]=cpot[col-1]+num[col-1]; (2?col ?a.nu)
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
方法 2：快速转置算法
31北京邮电大学自动化学院
快速转置算法
? Status FastTransmatrix ( TSMatrix M,TSMatrix &T)
? {
? T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;
? if (T.tu){
? for ( col=1; col<=M.nu; ++col) num[col]=0;
? for (t=1;t<=M.tu;++t) ++num[M.data[t].j];
? // 求 M中每一列含非零元个数
? cpot[1]=1;//求第 col列中第 1个非零元素在 b.data中的序
号。
32北京邮电大学自动化学院
快速转置算法
? for (col=2;col<=M.nu;++col)
? cpot[col]=cpot[col-1]+num[col-1];
? for(p=1; p<=M.tu; p++)
? { col=M.data[p].j;q=cpot[col];
? } //if
? return OK; }//FastTransposeSMatrix
? T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i;
? T.data[q].e=M.data[p].e; ++cpot[col]; } //for
33北京邮电大学自动化学院
? 这个算法仅比前一个算法多用了两个辅助数组。
快速转置算法分析
? 从时间上看，算法中有四个并列的单循环，循环次数分别
为 nu和 tu，因而总的时间复杂度为 O（ nu＋ tu）。
? 在 M的非零元素个数 tu和 mu× nu等数量级时，其时间复
杂度为 O（ mu× nu），和经典算法的时间复杂度相同。
34北京邮电大学自动化学院
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
35北京邮电大学自动化学院
? tpedef struct OLNode
? {int i,j; ElemType e;
? struct OLNode *down,*right;}OLNode; *OLink;
i j e
down right
? 在链表中，每个非零元素可用一个含 5个域的结点表示，
right域用以链接同一行中下一个非零元素,down域用以
链接同一列中下一个非零元素。
4、十字链表
? 同一行的非零元素通过 right域链接成一个线性表，同一列
的非零元素通过 down域链接成一个线性表,每个非零元
素既是某行链表中的一个结点，又是某个列链表中的一个
结点,整个矩阵构成了一个十字交叉的链表，故称这样的
存储结构为 十字链表,可用两个分别存储行链表的头指针
和列链表的头指针的一维数组表示。
36北京邮电大学自动化学院
1 1 3
4 1 8
2 2 5 2 3 4
^
^ ^
^
^ ^ ^
34008
000
450
003
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?A
4、十字链表
37北京邮电大学自动化学院
例题：两个矩阵相加
? 假设两个矩阵相加后的结果为 A’，则和矩阵 A’中的非零元 aij’
只可能有三种情况,
? aij+bij
? 由此，当将 B加到 A上去时，对 A矩阵的十字链表来说：
? 改变接点的 e值（ aij+bij?0）
? aij (bij=0)
? bij (aij=0)
? 不变 (bij=0)
? 插入一个新结点 (aij=0)
38北京邮电大学自动化学院
? 还有一种情况是：和 A矩阵中的某个非零元相对应，和
矩阵 A’中是零元，即对 A的操作是删除一个接点
（ aij+bij=0）。
? 由此，整个运算过程可从矩阵的第一行起逐行进行。
对每一行都从表头出发分别找到 A和 B在该行中的第一
个非零元结点后，开始比较，然后按上述四种不同情
况分别处理。
例题：两个矩阵相加
39北京邮电大学自动化学院
? 广义表（ Lists，又称列表）是线性表的推广 。在第 2章中，
我们把线性表定义为 n?0个元素 a1,a2,a3,…,a n的有限序列。
线性表的元素仅限于原子项,原子是作为结构上不可分割的
成分，它可以是一个数或一个结构，若放松对表元素的这种
限制，容许它们具有其自身结构，这样就产生了广义表的概
念。
5.4 广义表的定义
? 广义表 是 n(n?0)个元素 a1,a2,a3,…,a n的有限序列，其中 ai或
者是原子项，或者是一个广义表。通常记作 LS=
（ a1,a2,a3,…,a n)。 LS是广义表的名字,n为它的长度。若 ai
是广义表，则称它为 LS的子表。
40北京邮电大学自动化学院
? 通常用圆括号将广义表括起来，用逗号分隔其中的元素。为
了区别原子和广义表,书写时用大写字母表示广义表，用小
写字母表示原子。 若广义表 LS（ n>=1) 非空，则 a1是 LS的
表头，其余元素组成的表 (a1,a2,…a n)称为 LS的表尾。
5.4 广义表的定义
? 显然广义表是递归定义的，这是因为在定义广义表时又用到
了广义表的概念。广义表的例子如下：
? （ 1） A=（） —— A是一个空表，其长度为零。
? （ 2） B=（ e） —— 表 B只有一个原子 e,B的长度为 1。
? （ 3） C=（ a,(b,c,d))—— 表 C的长度为 2，两个元素分别为原
子 a和子表 (b,c,d)。
? （ 4） D=（ A,B,C） —— 表 D的长度为 3，三个元素都是广义
表。显然，将子表的值代入后，则有 D=(( ),(e),(a,(b,c,d)))。
41北京邮电大学自动化学院
? （ 5） E=（ a,E） —— 这是一个递归的表，它的长度为 2,E
相当于一个无限的广义表 E=(a,(a,(a,(a,…)))),
? 例如,D=(E,F)
? 其中,
? E=(a,(b,c))
? F=(d,(e))
D
E F
a ( ) d ( )
b c e
5.4 广义表的定义
? 从上述定义和例子可推出广义表的三个重要结论：
? （ 1）广义表的元素可以是子表，而子表的元素还可以是子
表。 由此，广义表是一个多层次的结构，可以用图形象地表
示。
42北京邮电大学自动化学院
? （ 2）广义表可为其它表所共享。 例如在上述例（ 4）中，
广义表 A,B,C为 D的子表，则在 D中可以不必列出子表的
值，而是通过子表的名称来引用。
5.4 广义表的定义
? （ 3）广义表的递归性。
? 综上所述,广义表不仅是线性表的推广，也是树的推广。
? 广义表中所含括弧的重数称为表的深度,表中元素的层数
就是包括该元素的括弧重数。例如：
? F（ a,b，（ c，（ d）））。其中，单元素 a,b在第一
层,d在第三层，广义表的深度为 3。
43北京邮电大学自动化学院
? 由于广义表 (a1,a2,a3,…a n)中的数据元素可以具有不同的结
构，（或是原子，或是广义表），因此,难以用顺序存储
结构表示，通常采用链式存储结构,每个数据元素可用一
个结点表示。
tag=1 hp tp tag=0 atom表结点 原子结点
? 由于广义表中有两种数据元素，原子或广义表，因此，需
要两种结构的结点,一种是表结点，一种是原子结点 。 下
面介绍两种广义表的链式存储结构。
? 表结点由三个域组成,标志域、指示表头的指针域和指示
表尾的指针域；
? 而原子域只需两个域,标志域和值域 。
5.4 广义表的定义
44北京邮电大学自动化学院
L = ( a,( x,y ),( ( x ) ) )a ( x,y ) ( )
1
L
0 a
1 1
1
1
1
0 x
?
?
?
( )x
45北京邮电大学自动化学院
B C
D
E
1
0 e
1 1
0 a
1 1 1
1
0 a
1
1
0 d0 c0 b
1 1
? 广义表的存储结构示例
? （ 1） A=（）
? （ 2） B=（ e）
? （ 3） C=（ a,（ b,c,d））
? （ 4） D=（ A,B,C）
? （ 5） E=（ a,E）
46北京邮电大学自动化学院
5.5 m元多项式的表示
? 1、一元多项式
? 一个多项式可以一个长度为 m且每个数据元素有两个数据
项（系数项和指数项）的线性表来表示。
? 2,m元多项式
? 一个 m元多项式的每一项，最多有个 m变元，如果用线性
表来表示，则每个数据元素需要 m+1个数据项，以存储一
个系数值和 m个指数值。将产生两个问题：
? 造成浪费
? 线性表中结点大小不一样
47北京邮电大学自动化学院
? 因此，对于 m 元多项式中每一项的变化数目不均匀性和变
元信息的重要性，故不适于线性表表示。例如：
152632),,( 43442252362310 ??????? yzzyxzyxzyxzyxzyxzyxP
15)2)6(()3)2((),,( 4342253610 ??????? zyyxxzyxyxxzyxP
02 15 zBzAz ??
? 上式是变元 Z的多项式，即
? 其中,A和 B本身又是一个（ x,y）的二元多项式,15是 Z的零
次项的系数。
? 进一步考察 A(x,y)，又可把它看成是 y的多项式。
? Cy3+Dy2，而其中 C和 D为 x的一元多项式。循环以往，每个多
项式都可看作是由一个变量加上若干个系数指数偶对组成。
5.5 m元多项式的表示
48北京邮电大学自动化学院
? 任何一个 m 元多项式都可如此做,先分解出一个主变元，随
后再分解出第二个变元，等等 。由此，一个 m元的多项式首先
是它的主变元的多项式，而其系数又是第二变元的多项式，由
此，可用广义表来表示 m元多项式。例如上述三元多项式可用
下式的广义表表示，广义表的深度即为变元个数。
15)2)6(()3)2((),,( 4342253610 ??????? zyyxxzyxyxxzyxP
? P=Z（（ A,2），（ B,1），（ 15,0））
? 我们在广义表的括号之前加一个变元，以示各层的变元。
? A=y((C,3),(D,2)) B=y((E,4),(F,1))
? C=x((1,10),(2,6)) D=x((3,5))
? E=x((1,4),(6,3)) F=x((2,0))
5.5 m元多项式的表示
49北京邮电大学自动化学院
? 可以类似广义表的第二种存储结构来定义表示 m元多项式的
广义表的存储结构。链表的结点结构为：
? exp为指数域,coef为系数域,hp指向其系数子表,tp指
向同一层的下一个结点。
? 在每一层上增设一个表头结点，并利用 exp指示该层的变
元，可用一维数组存储多项式中所有变元，故 exp域存储
的是该变元在一维数组中的下标。
? 头指针 p所指表结点中 exp的值 3为多项式中变元的个数。
P112页的图为三元多项式 P(x,y,z)的存储结构示意图。
tphptag=1 exp tpcoeftag=0 exp
表结点 原子结点
5.5 m元多项式的表示
50北京邮电大学自动化学院
? 1,了解数组的两种存储表示方法，并掌握数组在以行为
主的存储结构中的地址计算方法。
第五章 思考题
? 2,掌握对特殊矩阵进行压缩存储时的下标变换公式。
? 3,了解稀疏矩阵的两类压缩存储方法的特点和适用范
围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的
处理方法。
? 4,掌握广义表的结构特点及其存储表示方法，读者可根
据自己的习惯熟练掌握任意一种结构的链表，学会对非
空广义表进行分解的两种分析方法：即可将一个非空广
义表分解为表头和表尾两部分或者分解为 n个子表。
51北京邮电大学自动化学院
第五章 作业
? 一、选择题
? 1、一维数组和线性表的区别是 A 。
? （ A）前者长度固定，后者长度可变 （ B）后者长度固定，前者长度可变
（ C）两者长度均固定 （ D）两者长度均可变
? 2、数组 A中，每个元素 A的长度为 3个字节，行下标 i从 1到 8，
列下标 j从 1到 10，从首地址 SA开始连续存放在存储器内，该数
组按行存放时，元素 A[8][5]的起始地址为 C 。
? （ A） SA+141 （ B） SA+144
? （ C） SA+222 （ D） SA+225
52北京邮电大学自动化学院
? 3、设有一个 10阶的对称矩阵，采用压缩存储方式，以行序
为主存储,a1,1为第一个元素，其存储地址为 1，每个元素占 1
个地址空间，则 a8,5的地址为 D 。
? （ A） 13 （ B） 33 （ C） 18 （ D） 40
? 二、填空题
? 1、广义表（ a，（ a,b）,d,e，（（ I,j）,k））表的长
度是 5,深度是 3 。
第五章 作业
