第5章数组和广义表

数组和广义表是线性表的推广,表中的数据元素本身也可以是一个数据结构。本章介
绍数组和广义表的定义、存储结构与算法实现。

5.数组的基本概念
1 

5.1 
数组的定义与特点
1.
1.数组的定义
数据结构中讨论的数组(aray)不同于高级语言中的数组。高级语言中数组是一种数
据类型,而且只有顺序结构。本章所讨论的数组是一种数据结构,既可以是顺序结构,也可
以是链式结构,用户可根据需要选择。

数组A=(a1,an-1)由一组名字相同、下标不同的变量构成。若ai 
(0≤i≤

a0,a2,…,
n-1)是同类型的元素,则
A 
是一维数组。若ai(0≤i<n)是同类型的定长线性表,则
A 
是
多维数组。
在C++语言中,一个二维数组可以用其分量一维数组来定义。同样,一个三维数组可
以用其数据元素为二维数组的线性表来定义,以此类推,可得到
n 
维数组的递归定义。

2.数组的特点
在数组中,对于一组有意义的下标都存在一个与其相对应的值。这种下标与值一一对
应的关系是数组的特点。
一维数组的每个数组元素只有一个下标,每个元素ai(1≤i≤n-2)有唯一一个直接前
趋结点ai-1和唯一一个直接后继结点ai+1 a0 没有直接前趋结点,an

继结点。
。其中,1没有直接后

二维数组的每个数组元素有两个下标,每个元素aij 
受到两个关系(行关系和列关系)的
约束。aij(1≤i≤m-1≤j≤n-有两个直接前趋结点aj--
j 
,

2,2) i,1和ai1,两个直接后继结
点ai,。其中,称为开始结点;1,称为终端

j+1和ai+1,a00没有前趋结点, am-1没有后继结点,

jn

结点。可
以把二维数组中的元素aij 
看成是属于两个线性表的,即第
i 
行的线性表Ai 
和第
j 
列的线性表Bj 
。例如,2所示。
如图5.

一个m×n 
的二维数组可以看成是
m 
行的一维数组,1所示; 
也可看成是
n 
列的一维数组,如图5.

因此,二维数组是一个数据元素值为一维数组的线性表。

以此类推,一个m×n×l 
的三维数组中,每个元素属于3个线性表,每个元素最多有3 
个直接前趋和3个直接后继。
例如,一个数组元素aj1,j3, aj1-j2,aj1,1,aj1,j3-其直接后

j2,其直接前趋为:1,j3,j2-j3,j2,1; 
继为:j3,j3,。

aj1+1,aj1,aj1,j3+1

j2,j2+1,j2,


图5.

1 用
m 
行的一维数组表示m×n 
的二维数组


图5.

2 用
n 
列的一维数组表示m×n 
的二维数组

进一步,一个
n 
维数组可以看成是由若干个n-1维数组组成的线性表,在
n 
维数组
A 

中每个元素aj1,j2,…,(1)属于
n 
个线性表,每个元素最多有
n 
个直接前趋和
n 
个直接后继。
例如,数组元素aj1,j,其直接前趋为:1,jn 
,j2-j,…,j2,…,
n 
-其

jn 
0≤ji≤n

j2,…,
n 
aj1-j2,…,aj1,1,…,
n 
aj1,j1; 

直接后继为:aj1+1,jaj1,jn 
aj1,j。

j2,…,
n 
,j2+1,…,,…,j2,…,
n 
+1 

1.数组的存储结构
5.2 

1. 
一维数组的顺序存储
在计算机中,如果用一批连续的存储单元来表示数组,则称为数组的顺序存储结构。
C++语言中数组的顺序分配允许有两种方法:静态存储分配和动态存储分配,简称静态数
组和动态数组。

(1)静态数组:是指数组大小在程序中预先给出、在
程序编译时建立的数组。程序运行期间,数组大小是静态
的,不能改变的。
(2)动态数组:是指在程序执行过程中动态建立和撤
销的数组。
数组是采用计算地址的方法来实现的。一维数组的
地址计算公式和顺序表的元素分配一样。
如图5.对一个有
n 
个数据元素的一维数组,

3所示,
oa0)设a0 是下标为0的数组元素,Lc(是a0 的存储地址, 
L 
是每个数据元素所需的存储单元,则数组中任一数据元
素a的存储地址Lai)的计算函数为

i(0≤i≤n-1) oc(
Loai)=Lc(1 图5.3 一维数组顺序存储示意图

c(oa0)+i×L, 0≤i≤n


116 

C++语言中内置的数组是符合上述定义的数据结构,因此在这里使用它来存储一维数
组。这种情况下,不需要显性地对数据元素的存储地址进行管理。

2. 
二维数组的顺序存储
对一个
m 
行
n 
列的二维数组,由于计算机的存储单元都是一维的,就有一个二维向一
维映射的问题。对二维数组可有两种存储方式:一种是行主序(rowmajororder)存储,即
一行存完后再存放下一行;另一种是列主序(columnmajororder)存储,即一列存完后再存
放下一列
4
。
(c)
4(a) 0…1,4(b)

例如,图5.的二维数组A[0…2], 其行主序存储如图5.所示,其列主序存
储如图5.所示。


图5.

4 二维数组顺序存储示意

C++语言中的数组元素是行主序的存放方法。设a00 是行列下标均为0的数组元素, 
Loa00) 
L 
是每个数据元素所需的存储单元。数组元素aij 
前已存放了i

c(是a00 的存储地址,
行,即已存放了i×n 
个数据元素,占用了i×n×L 
个存储单元;在第
i 
行上,数组元素aij 
前
已存放了
j 
列,即已存放了
j 
个数据元素,占用了j×L 
个存储单元,所以数组元素aij 
(0≤ 

i≤m-0≤j≤n-oaij

1,1)的存储地址Lc()为上述3个部分之和。因此,数组中任一数据
元素aij 
的存储地址Lc(j)的计算函数为

oaiLoaij)=Loi×n+j)×L, 0≤i≤m-0≤j≤n

c(c(1,

a00)+(1 
在列主序存储中,数组元素地址的计算函数可仿照行主序的计算函数推导出来。C+
+ 
语言中数组的各维下界均固定为0,而其他语言不一定为0,因此计算公式略有变化。
由于在二维数组中涉及行和列的定义,因此不难由此联想到矩阵的概念。

5.特殊矩阵的压缩存储
2 

矩阵(matrix)运算是许多科学和工程计算中经常遇到的问题。通常用二维数组来存储
矩阵数据元素。利用矩阵元素在一维数组中的地址计算函数就可以快速地访问矩阵中的每
个元素。

实际应用中常常会遇到一些阶数很高的矩阵,它们有许多值相同的元素或零元素,且值

相同的元素或零元素的分布有一定的规律,这种分布有一定规律的矩阵称为特殊矩阵。常

117 

见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵。

特殊矩阵可以进行压缩存储。所谓压缩存储,就是为多个值相同的元素只分配一个存
储空间,且对零元素不分配空间。

1. 
对称矩阵的压缩存储
若一个
n 
阶矩阵
A 
中的数据元素满足aij 
=aji(0≤i≤n-1,0≤j≤n-1), 则称其为
n 
阶对称矩阵。

由于对称矩阵中的数据元素以主对角线为中线对称,因此在存储时可只存储对称矩阵
中上三角或下三角的数据元素,即让对称的数据元素共享一个存储空间,这样就可将n2 个
数据元素压缩存储到n(
5(

n+1)/2个数据元素空间中。
如图5.5所示,不失一般性,以存储的是对称矩阵(见图5.a)) 的下三角(包括对角线) 
的数据元素(见图5.b)) 图5.c)

5(为例进行讨论, 5(为对称矩阵的一维数组压缩存储。


图5.

5 对称矩阵及其下三角存储

可用一维数组sa[n(-作为
n 
阶对称矩阵
A 
的存储结构,

0…n+1)/21] 使得
n 
阶对称
矩阵
A 
中的所有下三角(包括对角线)的数据元素对应不同的存储单元,所有上三角(不包
括对角线)的数据元素对应下三角的相应存储单元。设aij 
为
n 
阶对称矩阵中
i 
行
j 
列的数
据元素,
则aij 
a的下标序号。
j 
之前的
i 
行共有i(aij 

k 
为一维数组s

(1)若i≥j, 在下三角中。aii+1)/2个元素,在第
i 
行上,
之前有
j 
个元素。aij 
和sk]
i+1)/2+j, 0≤k<n(
a[之间的对应关系是
k=i(n+1)/2 

(2)若i<j,则aij 
在上三角中。因为aij 
=aji,所以只要交换上述对应关系式中的
i 
和
j,即可得到aij 
和sk]
k=j(+i
即
, n+1)/2 
a[之间的对应关系, 
j+1)/20≤k<n(

2. 
三角矩阵的压缩存储
当一个方阵的主对角线上方或下方的所有元素皆为常数时,该矩阵称为三角矩阵。以

主对角线划分,三角矩阵有上三角和下三角两种。如图5.a) 上三角矩阵的下三角

(不包括主对角线)中的元素均为常数。下三角矩阵正好相反,它的主对角线上方均为常数, 

如图5.b) 三角矩阵常数为零。

三角矩阵可以用一维数组
6(所示。在大多数情况下
sa[0,
…n(n+1)/2]存储,将常量存入第一个或最后一个存储
6(所示, 

118 

图5.

6 三角矩阵

单元。

3.对角矩阵的压缩存储
设矩阵
A 
为
n 
阶方阵。序列(0≤i≤n-称为
A 
的主对角线。所有的非零元素集

ai 
,1) 
中在以主对角线为中心的带状区域中,即除了主对角线和主对角线相邻两侧的若干条对角
线上的元素之外,其余元素皆为零的矩阵为对角矩阵。

图5.a) 其非零元素仅出现在主对角

7(是一个带宽为3的对角矩阵及其顺序结构存储
,
ai 
,0≤i≤n-i+1,


线上(1),紧邻主对角线上面的那条对角线上(2)和紧邻主对

ai,0≤i≤nai+1,i,0≤i≤n-i-
j 
=

角线下面的那条对角线上(2)。当|j|>1时,元素ai0。
由此可知,一个带宽为d(的对角矩阵
A 
是满足下述条件的矩阵:若|i-j|> 
d-ij=
不失一般性,对角矩阵可按行优先顺序或对角线的顺序,将其压缩存储到一个一维数组

(1)/2,则元素a0。
d 
为奇数) 
7(为行主序的一维数组压
中,并且也能找到每个非零元素和数组下标的对应关系。图5.b) 
缩存储。若采用行优先顺序,则存储带宽为
d 
的对角矩阵中非零元素aj 
的地址公式为
Loc()=Loc(-1+(i+(d-1)/2)(i) 

aija00)+d×ij


图5.

7 对角矩阵及其压缩存储

4.稀疏矩阵
设m×n 
的矩阵
A 
中有
s 
个非零元素,若
s 
远远小于矩阵元素的总数,则称
A 
为稀疏矩
阵。令e=s/(称
e 
为矩阵的稀疏因子。通常认为e≤0.

m×n), 05时为稀疏矩阵。
稀疏矩阵中非零元素的分布一般是没有规律的,因此在存储非零元素的同时,还必须同
时记下它所在的行和列的位置(j)。

i,
稀疏矩阵中每个非零元素和它对应的行下标和列下标构成一个三元组。三元组的结构

119 

如图5.其中i,aij 
表示非零元素的值。

8所示, 
j 
分别表示非零元素的行号和列号,


图5.

8 三元组的结点结构
一个三元组(j,)可以唯一确定矩阵
A 
的一个非零元素。稀疏矩阵可由表示非零

i,aij
元素的三元组及其行列数唯一确定。


图5..aa

9 稀疏矩阵
M 
及其三元组表adt

例如,图5.a) 其中只有6个非零元素。6个三元组

9(所示的稀疏矩阵
M 
有42 个元素,
(1,3,9),(1,5,-7),(3,1,8),(4,3,-2),(5,2,5),(6,6,3)表示该矩阵的6个非零元素。
若以行主序将这6个三元组排列起来,再加上一个表示矩阵
M 
的行数、列数及非零元素的
个数的特殊三元组(6,7,6), 则所形成的三元组表就能唯一确定稀疏矩阵
M 
,如图5.b) 
所示。
9(

三元组表可用顺序表存储,也可用链表存储。用顺序表存储的三元组表称为三元组顺
序表,用链表存储的三元组表称为三元组链表。

对于稀疏矩阵,三元组表存储结构对存储空间的需求量比通常的方法少得多。例如, 
m×n 
的矩阵
M 
,非零元的个数为num,若用三元组表来表示,在每个元素占一个存储单元
的情况下,只需要3×(num+1)个存储单元(包括特殊三元组所占用的3个单元); 若用传
统的二维数组表示,则需要m×n 
个存储单元。当矩阵越大、越稀疏时,三元组存储方式的
优越性就越明显。

5.矩阵的算法实现
3 

矩阵最常用的操作有矩阵加、矩阵减、矩阵乘、矩阵转置、矩阵求逆、矩阵行列式等。在

掌握线性表的基本操作的基础上,这些操作都不难实现。但是,稀疏矩阵的快速转置算法思

想巧妙,性能优良。因此,下面仅以稀疏矩阵的快速转置算法为例进行算法实现。

一个m×n 
的矩阵
M 
,它的转置矩阵
T 
是一个n×m 
的矩阵,且Tij 
=Mji,其中,0≤i≤ 
n-1,0≤j≤m-1。

在这里沿用上面介绍的三元组的方式存储矩阵。

明确了存储方式后,就不难进行相应的存储结构的定义。

120 

121 
三元组的定义如下。 
1. template<typename T> 
2. struct Triple { 
3. int i, j; //非零元素的行下标和列下标
4. T elem; 
5. }; 
矩阵类的定义如下。 
1. template<typename T> 
2. struct Matrix { 
3. int row, col; 
4. int num; 
5. Triple<T>*data; 
6. 
7. Matrix(int r, int c, int n) : row(r), col(c), num(n) { 
8. data =new Triple<T>[num +1]; //非零三元组表,data[0]未用
9. } 
10. 
11. ~Matrix() { delete[]data; } 
12. }; 
上述的两段代码共同构成了矩阵的头文件。
1.算法功能
采用三元组表存储矩阵,由矩阵M 的三元组表a.data求得其转置矩阵T 的三元组表
b.data,实现矩阵M 的转置。
2.算法思路
(1)预先确定矩阵M 中每一列,即转置矩阵T 中每一行的第一个非零元素在b.data中
的位置。为此,需事先求得矩阵M 的每一列中非零元素的个数。可设置两个数组num 
[col]和cpot[col],分别存放矩阵M 中每一列的非零元素个数和每一列第一个非零元素在
b.data中的位置,即
● M 中的列变量用col表示。
● num[col]存放M 中第col列中非零元素个数。
● cpot[col]存放M 中第col列的第一个非零元素在b.data中的位置。
于是有
cpot[1]=1 
{cpot[col]=cpot[col-1]+num[col-1], 2≤col≤a.col 
(2)按照a.data中三元组的次序进行转置。对于扫描到的a.data中的当前元素,利用
其列信息,即可在cpot[col]中直接查出它在b.data中的最终存放位置。
转置后的元素不连续存放,直接按照cpot[col]的结果将其放到b.data中最终的位置
上。同时,修改该列的cpot[col]为cpot[col]+1,为该列的下一个元素的存放做好准备。这
样既可避免元素移动,又只需对a.data扫描一次即可实现矩阵的转置。

3. 
实例描述
稀疏矩阵
M 
的三元组表a.a如图5.a)所示,其中,ow 为行号,l为列号,
为值。求该矩阵的稀疏矩阵T。
dat10(rcovalue 

(1)首先将num[col]和cpot[col]初始化,数组元素清零。
图5.

10 矩阵
M 
的快速转置过程

(2)扫描矩阵
M 
的三元组表a.a,计算nl]的值,如图5.b)所示。
datum[co10(
第一个元素(1,3,9), 列号为3,num[3]=1;
第二个元素(1,5,-7), 列号为5,num[5]=1;
第三个元素(3,1,8), 列号为1,num[1]=1;
第四个元素(4,3,-2), 列号为3,num[3]=2;
第五个元素(5,2,5), 列号为2,num[2]=1;
第六个元素(6,6,3), 列号为6,num[6]=1
。


poco10(

(3)计算ct[l]的值,如图5.b)所示
。
cpot[1]=1;
cpot[2]=cpot[1]+num[1]=1+1=2;
cpot[3]=cpot[2]+num[2]=2+1=3;
cpot[4]=cpot[3]+num[3]=3+2=5;
cpot[5]=cpot[4]+num[4]=5+0=5;
cpot[6]=cpot[5]+num[5]=5+1=6;
cpot[7]=cpot[6]+num[6]=6+1=7
。
(4)扫描矩阵
M 
的三元组表adt生成转置矩阵
T 
的三元组表bdt如图510(所示。
.aa, .aa, .c) 
第一个元素(1,3,9)列号为3,t[3]3,转置后的元素(3,1,9)是b.a中的第3个
元素,并修改cpot[3]=4; 
cpo=dat
第二个元素(7), 列号为5,转置后的元素(是b.a中的

1,5,-cpot[5]=5, 5,1,-7) dat
第5个元素,并修改cpot[5]=6; 
第三个元素,(3,8), 列号为1,pt[=1,转置后的元素(3,8)是b.aa中的第1

1,co1]1,dt

122 

123 
个元素,并修改cpot[1]=2; 
第四个元素(4,3,-2),列号为3,cpot[3]=4,转置后的元素(3,4,-2)是b.data中的
第4个元素,并修改cpot[3]=5; 
第五个元素(5,2,5),列号为2,cpot[2]=2,转置后的元素(2,5,5)是b.data中的第2 
个元素,并修改cpot[2]=3; 
第六个元素(6,6,3),列号为6,cpot[6]=6,转置后的元素(6,6,3)是b.data中的第6 
个元素,并修改cpot[6]=7。
只需要扫描一遍矩阵M 的三元组表a.data,而且不需要元素的移动,即可生成转置矩
阵T 的三元组表b.data。
4.参考程序
定义文件中的主程序如下。 
1. #include "Matrix.h" 
2. #include <iostream> 
3. using namespace std; 
4. 
5. void create_Matrix(Matrix<int>&M) 
6. { 
7. cout <<"请按照行优先顺序输入稀疏矩阵" 
8. <<M.num <<"个非零元素信息:\n"; 
9. for (int k =1; k <=M.num; k++) 
10. { 
11. cout <<"第" <<k <<"个元素的行标、列标以及元素的值:"; 
12. cin >>M.data[k].i >>M.data[k].j >>M.data[k].elem; 
13. } 
14. cout <<endl; 
15. } 
16. 
17. //采用三元组表存储表示,求稀疏矩阵M 的转置矩阵T 
18. Matrix<int>FastTranspose_Matrix(Matrix<int>&M) 
19. { 
20. Matrix<int> T(M.col, M.row, M.num); 
21. if (M.num ==0) 
22. return T; 
23. int *num =new int[M.col +1](); 
24. int *cpot =new int[M.col +1](); 
25. 
26. //计算num[col]的值
27. for (int t =1; t <=M.num; t++) 
28. num[M.data[t].j]++; 
29. //计算cpot[col]的值
30. cpot[1] =1; 
31. for (int col =2; col <=M.col; col++) 
32. cpot[col] =cpot[col -1] +num[col -1];

124 
33. //扫描矩阵M 的三元组表a.data,生成转置矩阵T 的三元组表b.data 
34. for (int p =1; p <=M.num; p++) 
35. { 
36. int q =cpot[M.data[p].j]; 
37. T.data[q].i =M.data[p].j; 
38. T.data[q].j =M.data[p].i; 
39. T.data[q].elem =M.data[p].elem; 
40. cpot[q]++; 
41. } 
42. 
43. delete[] num; 
44. delete[] cpot; 
45. return T; 
46. } 
47. 
48. void print_Matrix(Matrix<int>&M) 
49. { 
50. cout <<"共有" <<M.num <<"个非零元素:\n"; 
51. 
52. int t =1; 
53. cout <<"稀疏矩阵为:\n"; 
54. for (int p =1; p <=M.row; p++) 
55. { 
56. for (int q =1; q <=M.col; q++) 
57. //打印非零元素
58. if (M.data[t].i ==p && M.data[t].j ==q) 
59. printf("%5d", M.data[t++].elem); 
60. else //打印零元素
61. printf("%5d", 0); 
62. cout <<endl; 
63. } 
64. 
65. cout <<"\n 稀疏矩阵三元组顺序表为:\n"; 
66. printf("%5c%5c%5c\n", 'i', 'j', 'v'); 
67. for (int k =1; k <=M.num; k++) 
68. printf("%5d%5d%5d\n", 
69. M.data[k].i, M.data[k].j, M.data[k].elem); 
70. } 
71. 
72. int main() 
73. { 
74. int r, c, n; 
75. cout <<"输入稀疏矩阵行数与列数:"; 
76. cin >>r >>c; 
77. cout <<"输入稀疏矩阵非零元素个数:";