第 5章多维数组和广义表
数据结构（ C++描述）
5.5 广义表
5.1多维数组
5.2多维数组的存储结构
5.3 特殊矩阵及其压缩存储
5.4 稀疏矩阵
退出
目录
5.1多维数组
5.1.1多维数组的概念
1,一维数组
一维数组可以看成是一个线性表或一个向量 （ 第
二章已经介绍 ）, 它在计算机内是存放在一块连
续的存储单元中, 适合于随机查找 。 这在第二章
的线性表的顺序存储结构中已经介绍 。
2,二维数组
二维数组可以看成是向量的推广。
a 00 a 01 …… a 0n - 1
a 10 a 11 …… a 1n - 1
…………………………,
a m - 1 0 a m - 1 1 …… a m - 1 n - 1
A=
例如, 设 A是一个有 m行 n列的二维数组, 则 A可以
表示为：
在此，可以将二维数组 A看成是由 m个行向量 [X0，
X1,…, Xm-1]T组成，其中,Xi=( ai0,ai1,….,a in-1)，
0≤i≤m-1；也可以将二维数组 A看成是由 n个列向量 [y0,
y1,……,y n-1]组成，其中 yi=(a0i,a1i,…..,a m-1i),0≤i≤n-1。
由此可知二维数组中的每一个元素 最多可有二个直接
前驱和两个直接后继 （ 边界除外 ）, 故是一种典型的
非线性结构 。
3,多维数组
同理, 三维数组最多可有三个直接前驱和三个直接后继,
三维以上数组可以作类似分析 。 因此, 可以把三维以上的
数组称为多维数组, 多维数组可有多个直接前驱和多个直
接后继, 故多维数组是一种非线性结构 。
5.1.2 多维数组在计算机内的存放
怎样将多维数组中元素存入到计算机内存中呢？由于
计算机内存结构是一维的（线性的），因此，用一维
内存存放多维数组就必须按某种次序将数组元素排成
一个线性序列，然后将这个线性序列顺序存放在存储
器中
5.2多维数组的存储结构
由于数组一般不作插入或删除操作, 也就是说, 一旦建
立了数组, 则结构中的数组元素个数和元素之间的关系
就不再发生变动, 即它们的逻辑结构就固定下来了, 不
再发生变化 。 因此, 采用顺序存储结构表示数组是顺理
成章的事了 。 本章中, 仅重点讨论二维数组的存储, 三
维及三维以上的数组可以作类似分析 。
多维数组的顺序存储有两种形式：
5.2.1 行优先顺序
1．存放规则
行优先顺序也称为低下标优先或左边下标优先于右边下
标 。 具体实现时, 按行号从小到大的顺序, 先将第一行
中元素全部存放好, 再存放第二行元素, 第三行元素,
依次类推 ……
在 BASIC语言, PASCAL语言, C/C++语言等高级语言
程序设计中, 都是按行优先顺序存放的 。 例如, 对刚才
的 Am× n二维数组, 可用如下形式存放到内存,a00，
a01,… a0n-1,a10,a11,...,a1 n-1,…, am-1 0, am-1 1,…,
am-1 n-1。 即二维数组按行优先存放到内存后, 变成了一
个线性序列 （ 线性表 ） 。
因此，可以得出多维数组按行优先存放到内存的规律：
最左边下标变化最慢，最右边下标变化最快，右边下
标变化一遍，与之相邻的左边下标才变化一次。因此，
在算法中，最左边下标可以看成是外循环，最右边下
标可以看成是最内循环。
2．地址计算
由于多维数组在内存中排列成一个线性序列, 因此, 若
知道第一个元素的内存地址, 如何求得其它元素的内存
地址？ 我们可以将它们的地址排列看成是一个等差数列,
假设每个元素占 l个字节, 元素 aij 的存储地址应为第一个
元素的地址加上排在 aij 前面的元素所占用的单元数, 而
aij 的前面有 i行 (0~i-1)共 i× n个元素, 而本行前面又有 j个
元素, 故 aij的前面一共有 i× n+j个元素, 设 a00的内存地
址为 LOC(a00), 则 aij 的内存地址按等差数列计算为
LOC(aij)=LOC(a00)+ （ i× n+j ） × l 。 同理, 三维数组
Am× n× p 按 行 优 先 存 放 的 地 址 计 算 公 式 为,
LOC(aijk)=LOC(a000)+(i× n× p+j× p+k)× l。
5.2.2 列优先顺序
1,存放规则
列优先顺序也称为高下标优先或右边下标优先于左边下
标。具体实现时，按列号从小到大的顺序，先将第一列
中元素全部存放好，再存放第二列元素，第三列元素，
依次类推 ……
在 FORTRAN语言程序设计中, 数组是按列优先顺序存
放的 。 例如, 对前面提到的 Am× n二维数组, 可以按如下
的形式存放到内存,a00,a10…, am-10,a01,a11,…,
am-1 1,…, a0 m-1,a1m-1,...,am-1 n-1。 即二维数组按列
优先存放到内存后, 也变成了一个线性序列 （ 线性表 ） 。
因此, 可以得出多维数组按列优先存放到内存的规律：
最右边下标变化最慢, 最左边下标变化最快, 左边下
标变化一遍, 与之相邻的右边下标才变化一次 。 因此,
在算法中, 最右边下标可以看成是外循环, 最左边下
标可以看成是最内循环 。
2．地址计算
同样与行优先存放类似, 若知道第一个元素的内存地址,
则同样可以求得按列优存放的某一元素 aij的地址 。
对二维数组有,LOC(aij)=LOC(a00)+(j× m+i)× l
对三维数组有：
LOC(aijk)=LOC(a000)+(k× m× n+j× m+i)× l
5.3 特殊矩阵及其压缩存储
5.3.1 特殊矩阵
若一个 n阶方阵 A中元素满足下列条件：
aij=aji 其中 0 ≤i,j≤n-1, 则称 A为对称
矩阵 。
例如, 图 5-1是一个 3*3的对称矩阵 。
A=
643
452
321
图 5 - 1 一个对称矩阵
1．对称矩阵
2．三角矩阵
（ 1） 上三角矩阵
即矩阵上三角部分元素是随机的，而下三角部分元
素全部相同（为某常数 C）或全为 0，具体形式见
图 5-2(a)。
（ 2） 下三角矩阵
即矩阵的下三角部分元素是随机的，而上三角部
分元素全部相同（为某常数 C）或全为 0，具体形
式见图 5-2(b)。
111110
1110
00
.,,
.,,.,,.,,.,,
.,,
.,,
???? nnnn
aaa
caa
cca
( a) 上三角矩阵 （ b ）下三角矩阵
11
1111
100100
.,,.,,.,,.,,
.,,
.,,
??
?
?
nn
n
n
accc
aac
aaa
图 5 - 2 三角矩阵
3．对角矩阵
若矩阵中所有非零元素都集中在以主对角线为中
心的带状区域中, 区域外的值全为 0,则称为对角
矩阵 。 常见的有三对角矩阵, 五对角矩阵, 七对
角矩阵等 。
例如，图 5-3为 7?7的三对角矩阵（即有三条对角
线上元素非 0）。
6665
565554
454443
343332
232221
121110
0100
00000
0000
0000
0000
0000
0000
00000
aa
aaa
aaa
aaa
aaa
aaa
aa
图 5 - 3 一个 7 ? 7 的三对角矩阵
5.3.2 压缩存储
1．对称矩阵
若矩阵 An?n是对称的, 对称的两个元素可以共用一个存
储单元, 这样, 原来 n 阶方阵需 n2个存储单元, 若采用
压缩存储, 仅需 n(n+1)/2个存贮单元, 将近节约一半存
贮单元, 这就是实现压缩的好处 。 但是, 将 n阶对称方
阵存放到一个向量空间 s[0]到 s[ -1] 中,
我们怎样找到 s[k]与 a[i][j]的一一对称应关系呢？ 使我们
在 s[k]中直接找到 a[i][j]。
2 )1( ?nn
我们仅以行优先存放分两种方式讨论：
（ 1） 只存放下三角部分
由于对称矩阵关于主对角线对称, 故我们只需存放主
对角线及主对角线以下的元素 。 这时, a[0][0]存入
s[0],a[1][0] 存入 s[1],a[1][1]存入 s[2],…, 具体参
见图 5-4。 这时 s[k]与 a[i][j]的对应关系为：
i(i+1)/2+j 当 i≥j
k=
j(j+1)/2+i 当 i<j
上面的对应关系读者很容易推出：当 i≥j 时, aij在下三角
部分中, aij前面有 i行, 共有 1+2+3+… +i个元素, 而 aij是
第 i行的第 j个元素, 即有 k=1+2+3+…- +i+j=i(i+1)/2+j；当
i<j时, aij在上三角部分中, 但与 aji对称, 故只需在下三角
部分中找 aij即可, 故只需将 i与 j交换即可, 即 k=j(j+1)/2+i。
11121110
222120
1110
00
...
...............
????? nnnnn
aaaa
aaa
aa
a
( a ) 一个下三角矩阵
a 00 a 10 a 11 a 20 a 21 a 22 a 30 a 31 … … a n - 1n - 3 a n - 1n - 2 a n - 1n - 1
0 1 2 3 4 5 6 7 ……
2
)1( ?nn
- 3
2
)1( ?nn
- 2
2
)1( ?nn
- 1
( b ) 下三角矩阵的压缩存储形式
图 5 - 4 对称矩阵及用下三角压缩存储
(2) 只存放上三角部分
对于对称阵, 除了用下三角形式存放外, 还可以用上
三角形式存放, 这时 a[0][0]存入 s[0],a[0][1]存入 s[1]，
a[0][2]存入 s[2],…, 具体参见图 5-5。 这时 s[k]与 a[i][j]
的对应关系可以按下面方法推出：
当 i≤j时, aij在上三角部分中, 前面共有 i行, 共有 n+n-
1+… +n-(i-1)=i*n- 个元素, 而 aij是本行第 j-i个元素,
故 k=i*n- +j-i,当 i>j时, 交换 i与 j即可 。 故 s[k]与 a[i][j]
的对应关系为：
2 )1( ?ii
2 )1( ?ii
i*n- +j-i 当 i≤j
k=
j*n- +i-j 当 i>j
2 )1( ?ii
2 )1( ?jj
11
1222
111211
10020100
...............
...
...
...
??
?
?
?
nn
n
n
n
a
aa
aaa
aaaa
(a ) 一个上三角矩阵
a 00 a 01 a 02 a 03 a 04 a 05 a 06 a 07 … … a n - 2n - 2 a n - 2n - 1 a n - 1n - 1
0 1 2 3 4 5 6 7 …… 2
)1( ?nn
- 3 2
)1( ?nn
- 2 2
)1( ?nn
- 1
(b ) 上三角矩阵的压缩存储形式
图 5 - 5 对称矩阵及用上三角压缩存储
2．三角矩阵
（ 1） 下三角矩阵
下三角矩阵的压缩存放与对称矩阵用下三角形式存放
类似, 但必须多一个存储单元存放上三角部分元素,
使用的存储单元数目为 n(n+1)/2+1。 故可以将 n?n的下
三角矩阵压缩存放到只有 n(n+1)/2+1个存储单元的向量
中, 假设仍按行优先存放, 这时 s[k]与 a[i][j]的对应关系
为：
i(i+1)/2+j i≥j
k=
n(n+1)/2 i<j
(2)上三角矩阵
和下三角矩阵的存储类似，共需 n(n+1)/2+1个存贮单
元，假设仍按行优先顺序存放，这时 s[k]与 a[i][j]的对
应关系为：
i*n-i(i-1)/2 +j-i 当 i≤j
k=
n(n+1)/2 i>j
3,对角矩阵
我们仅讨论三对角矩阵的压缩存贮, 五对角矩阵, 七
对角矩阵等读者可以作类似分析 。
在一个 n?n的三对角矩阵中, 只有 n+n-1+n-1个非零元
素, 故只需 3n-2个存储单元即可, 零元已不占用存储
单元 。
故可将 n?n三对角矩阵 A压缩存放到只有 3n-2个存储单
元的 s向量中, 假设仍按行优先顺序存放, 则：
s[k]与 a[i][j]的对应关系为：
3i-1 当 i=j+1
k= 3i 当 i=j
3i+1 当 i=j-1
5.4 稀疏矩阵
在上节提到的特殊矩阵中, 元素的分布呈现某种规
律, 故一定能找到一种合适的方法, 将它们进行压
缩存放 。 但是, 在实际应用中, 我们还经常会遇到
一类矩阵：其矩阵阶数很大, 非零元个数较少, 零
元很多, 但非零元的排列没有一定规律, 我们称这
一类矩阵为稀疏矩阵 。
按照压缩存储的概念，要存放稀疏矩阵的元素，由于
没有某种规律，除存放非零元的值外，还必须存贮适
当的辅助信息，才能迅速确定一个非零元是矩阵中的
哪一个位置上的元素。下面将介绍稀疏矩阵的几种存
储方法及一些算法的实现。
5.4.1 稀疏矩阵的存储
1,三元组表
在压缩存放稀疏矩阵的非零元同时, 若还存放此非零元
所在的行号和列号, 则称为三元组表法, 即称稀疏矩阵
可用三元组表进行压缩存储, 但它是一种顺序存贮 （ 按
行优先顺序存放 ） 。 一个非零元有行号, 列号, 值, 为
一个三元组, 整个稀疏矩阵中非零元的三元组合起来称
为三元组表 。
此时, 数据类型可描述如下：
const int maxsize=100;//定义非零元的最大数目
struct node //定义一个三元组
{ int i,j; //非零元行, 列号
int v; //非零元值
};
struct sparmatrix //定义稀疏矩阵
{ int rows,cols ; //稀疏矩阵行, 列数
int terms; //稀疏矩阵非零元个数
node data [maxsize]; //三元组表
};
00070015
00000180
00002400
01400003
0000000
00009120
?
?
图 5 - 6 稀疏矩阵 M
000000
0001400
000000
700000
0024009
01800012
1500300
?
?
图 5 - 7 稀疏矩阵 N （ M 的转置）
稀疏矩阵 M和 N的三元组表见图 5-8。
图 5 - 8 稀疏矩阵 M 和 N 的三元组
M 的三元组表
i j v
0 1 12
0 2 9
2 0 – 3
2 5 14
3 2 24
4 1 18
5 0 15
5 3 – 7
N 的三元组表
i j v
0 2 - 3
0 5 15
1 0 12
1 4 18
2 0 9
2 3 24
3 5 - 7
5 2 14
2．带行指针的链表
把具有相同行号的非零元用一个单链表连接起来, 稀
疏矩阵中的若干行组成若干个单链表, 合起来称为带
行指针的链表 。 例如, 图 5-6 的稀疏矩阵 M的带行指针
的链表描述形式见图 5-9。
4 1 18 ^
0 1 12 0 2 9 ^
2 0 - 3 2 5 14 ^
3 2 24 ^
5 0 15 5 3 - 7 ^
0
行指针
1
3
4
5
2
图 5 - 9 带行指针的链表
3．十字链表
当稀疏矩阵中非零元的位置或个数经常变动时, 三元组
就不适合于作稀疏矩阵的存储结构, 此时, 采用链表作
为存储结构更为恰当 。
十字链表为稀疏矩阵中的链接存储中的一种较好的存储
方法, 在该方法中, 每一个非零元用一个结点表示, 结
点中除了表示非零元所在的行, 列和值的三元组 (i,j,v)外,
还需增加两个链域：行指针域 (rptr),用来指向本行中下
一个非零元素；列指针域 (cptr), 用来指向本列中下一个
非零元素 。 稀疏矩阵中同一行的非零元通过向右的 rptr指
针链接成一个带表头结点的循环链表 。 同一列的非零元
也通过 cptr指针链接成一个带表头结点的循链链表 。 因此,
每个非零元既是第 i行循环链表中的一个结点, 又是第 j列
循环链表中的一个结点, 相当于处在一个十字交叉路口,
故称链表为十字链表 。
另外, 为了运算方便, 我们规定行, 列循环链表的表头
结点和表示非零元的结点一样, 也定为五个域, 且规定
行, 列, 域值为 0,并且将所有的行, 列链表和头结点
一起链成一个循环链表 。
在行 (列 )表头结点中, 行, 列域的值都为 0,故两组表
头结点可以共用, 即第 i行链表和第 i列链表共用一个表
头结点, 这些表头结点本身又可以通过 V域 (非零元值域,
但在表头结点中为 next,指向下一个表头结点 )相链接 。
另外, 再增加一个附加结点 (由指针 hm指示, 行, 列域
分别为稀疏矩阵的行, 列数目 ),附加结点指向第一个
表头结点, 则整个十字链表可由 hm指针唯一确定 。
十字链表的数据类型描述如下：
struct linknode
{ int i,j;
linknode *cptr,*rptr;
union vnext //定义一个共用体
{ int v; //表结点使用 V域,表示非零元值
linknode *next; / /表头结点使用 next域
} k; }
例如，图 5-6 的稀疏矩阵 M的十字链表描述形式见图 5-10。
6 7
0 0 0 0
0 0
0 0 0 0 0 0
0 0
hm
0 1 12
0 2 9 0 0
0 0
0 0 2 0 - 3
2 5 14
0 0 3 2 24
0 0 4 1 18
0 0 5 0 15
5 3 - 7
图 5 - 10 稀疏矩阵的十字链表
5.4.2 稀疏矩阵的运算
1．稀疏矩阵的转置运算
转置是矩阵中最简单的一种运算 。 对于一个 m?n的矩阵
A,它的转置 B是一个 n?m 的, 且 B[i][j]=A[j][i]，
0≤i<n,0≤j<m。 例如, 图 5-6给出的 M矩阵和图 5-7给出的
N矩阵互为转置矩阵 。
在三元组表表示的稀疏矩阵中，怎样求得它的转置呢?从
转置的性质知道，将 A转置为 B，就是将 A的三元组表
a.data变为 B的三元组表 b.data，这时可以将 a.data中 i和 j 的
值互换，则得到的 b.data是一个按列优先顺序排列的三元
组表，再将它的顺序适当调整，变成行优先排列，即得到
转置矩阵 B。下面将用两种方法处理：
（ 1） 按照 A的列序进行转置
由于 A的列即为 B的行, 在 a.data中, 按列扫描, 则得
到的 b.data必按行优先存放 。 但为了找到 A的每一列中
所有的非零的元素, 每次都必须从头到尾扫描 A的三
元组表 (有多少列, 则扫描多少遍 ),这时算法描述如
下：
void transpose(sparmatrix a,sparmatrix b)
{b.rows=a.cols; b.cols=a.rows;
b.terms=a.terms;
if (b.terms>0){int bno=0;
for (int col=0; col<a.cols; col++)//按列号扫描
for(int ano=0;ano<a.terms;ano++)//对三元组表扫描
if (a.data[ano].j==col) //进行转置
{ b.data[bno].j=a.data[ano].i;
b.data[bno].i=a.data[ano].j;
b.data[bno].v=a.data[ano].v;
bno++;}}}
分析这个算法, 主要工作在 col和 ano二重循环上, 故
算法的时间复杂度为 O(a.cols*a.terms)。 而通常的 m?n
阶矩阵转置算法可描述为：
for(col=0; col<n; col++)
for (row=0;row<m;row++)
b[col][row]=a[row][col];
它的时间复杂度为 o(m?n)。 而一般的稀疏矩阵中非零
元个数 a.terms远大于行数 m,故压缩存贮时, 进行转
置运算, 虽然节省了存贮单元, 但增大了时间复杂度,
故此算法仅适应于 a.terns<<a.rows? a.cols的情形 。
（ 2） 按照 A的行序进行转置
即按 a.data中三元组的次序进行转置, 并将转置后的三
元组放入 b中恰当的位置 。 若能在转置前求出矩阵 A的
每一列 col(即 B中每一行 )的第一个非零元转置后在
b.data中的正确位置 pot[col](0≤col<a.cols),那么在对
a.data的三元组依次作转置时, 只要将三元组按列号 col
放置到 b.data[pot[col]]中, 之后将 pot[col]内容加 1,以
指示第 col列的下一个非零元的正确位置 。 为了求得位
置向量 pot,只要先求出 A的每一列中非零元个数
num[col],然后利用下面公式：
pot[0]=0
pot[col]=pot[col-1]+num[col-1] 当 1≤col<a.cols
算法描述如下：
void fastrans(sparmatrix a,sparmatrix b)
{ int pot[100],col,ano,bno;
b.rows=a.cols; b.cols=a.rows;b.terms=a.terms;
if (b.terms>0)
{ for(col=0;col<a.cols;col++) pot[col]=0;
for(int t=0;t<a.terms;t++) //求出每一列的非零元个数
{ col=a.data[t].j; pot[col+1]=pot[col+1]++; }
pot[0]=0;
for(col=1;col<a.cols;col++) //求出每一列的第一
个非零元在转置后的位置
pot[col]=pot[col-1]+pot[col];
for( ano=0;ano<a.terms;ano++) //转置
{ col=a.data[ano].j; bno=pot[col];
b.data[bno].j=a.data[ano].i;
b.data[bno].i=a.data[ano].j;
b.data[bno].v=a.data[ano].v;
pot[col]=pot[col]+1;}}
}
该算法比按列转置多用了辅助向量空间 pot,但它的时
间为四个单循环, 故 总 的 时 间 复 杂 度 为
O(a.cols+a.terms),比按列转置算法效率要高 。
2,稀疏矩阵的相加运算
当稀疏矩阵用三元组表进行相加时，有可能出现非零元
素的位置变动，这时候，不宜采用三元组表作存储结构，
而应该采用十字链表较方便。
5.5 广义表
5.5.1基本概念
广义表是第二章提到的线性表的推广。线性表中的元素
仅限于原子项，即不可以再分，而广义表中的元素既可
以是原子项，也可以是子表 (另一个线性表 )。
1,广义表的定义
广义表是 n≥0个元素 a1,a2,…, an的有限序列, 其中每
一个 ai或者是原子, 或者是一个子表 。 广义表通常记为
LS=(a1,a2,…,an),其中 LS为广义表的名字, n为广义表的
长度, 每一个 ai为广义表的元素 。 但在习惯中, 一般用
大写字母表示广义表, 小写字母表示原子 。
2．广义表举例
(1) A=( ),A为空表, 长度为 0。
(2) B=(a,（ b,c） ),B是长度为 2的广义表, 第一项为原
子, 第二项为子表 。
(3) C=(x,y,z) C是长度为 3的广义表, 每一项都是原
子 。
D=(B,C), D是长度为 2的广义表, 每一项都是上面提
到的子表 。
E=(a,E) 是长度为 2的广义表, 第一项为原子, 第二项为
它本身 。
3．广义表的表示方法
(1) 用 LS=(a1,a2,…, an)形式, 其中每一个 ai为原子或
广义表
例如,A=(b,c)
B=(a,A)
E=(a,E)
都是广义表 。
（ 2） 将广义表中所有子表写到原子形式, 并利用圆括号
嵌套
例如, 上面提到的广义表 A,B,C可以描述为：
A(b,c)
B(a,A(b,c))
E(a,E(a,E（ … ） ))
(3) 将广义表用树和图来描述
上面提到的广义表 A,B,C的描述见图 5-11。
B A
C
b a c
A
b
c
B
a A
b c
(a ) A =(b,c) (b) B=( a,A ) (c ) C =(A,B )
图 5 - 11 广义表用树或图来表示
4．广义表的深度
一个广义表的深度是指该广义表展开后所含括号的层数 。
例如, A=(b,c)的深度为 1,B=(A,d)的深度为 2,C=(f,B,h)
的深度为 3。
5．广义表的分类
（ 1） 线性表：元素全部是原子的广义表 。
（ 2） 纯表,与树对应的广义表, 见图 5-11的 (a)和 (b)。
（ 3） 再入表, 与图对应的广义表 (允许结点共享 ),见图
5-11的 (c)。
（ 4） 递归表：允许有递归关系的广义表, 例如 E=(a,E)。
这四种表的关系满足：
递归表 ?再入表 ? 纯表 ? 线性表
5.5.2存储结构
由于广义表的元素类型不一定相同, 因此, 难以用顺序
结构存储表中元素, 通常采用链接存储方法来存储广义
表中元素, 并称之为广义链表 。 常见的表示方法有：
1．单链表表示法
即模仿线性表的单链表结构, 每个原子结点只有一个链
域 link,结点结构是：
at om da ta /sl in k li nk
可用如图 5-12的结构描述广义表
C=(A,B)=((x,(a,b)),((x,(a,b)),y)),设头指针为 hc。
0 0 ^
0 1 y ^
1 x 0 ^
1 a 1 b ^
hc
A B
A
L
图 5 - 12 广义表的单链表表示法
2,双链表表示法
每个结点含有两个指针及一个数据域，每个结点的结
构如下：
l i n k 1 d at a l i n k 2
例如，对图 5-12用单链表表示的广义表 C，可用图
5-13的双链表方法表示。
A B ^
A ^ y ^
x L ^
^ a ^ b ^
hc
图 5 - 13 广义表的双链表表示法
5.5.3 基本运算
广义表有许多运算，现仅介绍如下几种：
1.求广义表的深度 depth(LS)
假设广义表以刚才的单链表表示法作存储结构, 则它
的深度可以递归求出 。 即广义表的深度等于它的所有
子表的最大深度加 1,设 dep表示任一子表的深度,
max表示所有子表中表的最大深度, 则广义表的深度
为,depth=max+1,算法描述如下：
int depth(node *LS)
{ int max=0;
while(LS!=NULL)
{ if(LS->atom==0) //有子表
{ int dep=depth(LS->slink);
if(dep>max) max=dep;}
LS=LS->link;
}
return max+1;}
该算法的时间复杂度为 O(n)。
2.广义表的建立 creat(LS)
假设广义表以单链表的形式存储, 广义表的元素类型
elemtype 为字符型 char,广义表由键盘输入, 假定全部
为字母, 输入格式为：元素之间用逗号分隔, 表元素
的起止符号分别为左, 右圆括号, 空表在其圆括号内
使用一个, #”字符表示, 最后使用一个分号作为整个
广义表的结束 。
例如，给定一个广义表如下,LS=(a,( ),b,c (d,(e) ) )，则
从键盘输入的数据为,(a,(#),b,c(d,(e)));↙,其中 ↙ 表示
回车换行。具体算法描述如下：
void creat(node *LS)
{ char ch; cin>>ch;
if(ch=='#') LS=NULL;
else if(ch=='(')
{LS=new node;
LS->atom=0; creat(LS->slink);}
else { LS=new node;
LS->atom=1; LS->data=ch; }
cin>>ch; if(LS==NULL);
else if(ch==',') creat(LS->link);
else if((ch==')')||(ch==';'))LS->link=NULL;}
该算法的时间复杂度为 O(n)。
3.输出广义表 print(LS)
void print(node *LS)
{ if(LS->atom==0)
{cout<<'(';
if(LS->slink==NULL) cout<<'#';
else print(LS->slink); }
else cout<<LS->data;
if(LS->atom==0) cout<<')';
if(LS->link!=NULL)
{ cout<<','; print(LS->link);}}
该算法的时间复杂度为 O(n)。
4．取表头运算 head
若广义表 LS=(a1,a2,…, an),则 head(LS)=a1 。
取表头运算得到的结果可以是原子, 也可以是一个
子表 。
例如, head((a1,a2,a3,a4))=a1,
head(((a1,a2),(a3,a4),a5))=(a1,a2)。
5,取表尾运算 tail
若广义表 LS=(a1,a2,…, an),则 tail(LS)=(a2,a3,…,
an)。
即取表尾运算得到的结果是除表头以外的所有元素, 取
表尾运算得到的结果一定是一个子表 。
值得注意的是广义表 ( )和 (())是不同的，前者为空表，长
度为 0，后者的长度为 1，可得到表头、表尾均为空表，
即 head((( )))=( ),tail((( )))=( )。
数据结构（ C++描述）
5.5 广义表
5.1多维数组
5.2多维数组的存储结构
5.3 特殊矩阵及其压缩存储
5.4 稀疏矩阵
退出
目录
5.1多维数组
5.1.1多维数组的概念
1,一维数组
一维数组可以看成是一个线性表或一个向量 （ 第
二章已经介绍 ）, 它在计算机内是存放在一块连
续的存储单元中, 适合于随机查找 。 这在第二章
的线性表的顺序存储结构中已经介绍 。
2,二维数组
二维数组可以看成是向量的推广。
a 00 a 01 …… a 0n - 1
a 10 a 11 …… a 1n - 1
…………………………,
a m - 1 0 a m - 1 1 …… a m - 1 n - 1
A=
例如, 设 A是一个有 m行 n列的二维数组, 则 A可以
表示为：
在此，可以将二维数组 A看成是由 m个行向量 [X0，
X1,…, Xm-1]T组成，其中,Xi=( ai0,ai1,….,a in-1)，
0≤i≤m-1；也可以将二维数组 A看成是由 n个列向量 [y0,
y1,……,y n-1]组成，其中 yi=(a0i,a1i,…..,a m-1i),0≤i≤n-1。
由此可知二维数组中的每一个元素 最多可有二个直接
前驱和两个直接后继 （ 边界除外 ）, 故是一种典型的
非线性结构 。
3,多维数组
同理, 三维数组最多可有三个直接前驱和三个直接后继,
三维以上数组可以作类似分析 。 因此, 可以把三维以上的
数组称为多维数组, 多维数组可有多个直接前驱和多个直
接后继, 故多维数组是一种非线性结构 。
5.1.2 多维数组在计算机内的存放
怎样将多维数组中元素存入到计算机内存中呢？由于
计算机内存结构是一维的（线性的），因此，用一维
内存存放多维数组就必须按某种次序将数组元素排成
一个线性序列，然后将这个线性序列顺序存放在存储
器中
5.2多维数组的存储结构
由于数组一般不作插入或删除操作, 也就是说, 一旦建
立了数组, 则结构中的数组元素个数和元素之间的关系
就不再发生变动, 即它们的逻辑结构就固定下来了, 不
再发生变化 。 因此, 采用顺序存储结构表示数组是顺理
成章的事了 。 本章中, 仅重点讨论二维数组的存储, 三
维及三维以上的数组可以作类似分析 。
多维数组的顺序存储有两种形式：
5.2.1 行优先顺序
1．存放规则
行优先顺序也称为低下标优先或左边下标优先于右边下
标 。 具体实现时, 按行号从小到大的顺序, 先将第一行
中元素全部存放好, 再存放第二行元素, 第三行元素,
依次类推 ……
在 BASIC语言, PASCAL语言, C/C++语言等高级语言
程序设计中, 都是按行优先顺序存放的 。 例如, 对刚才
的 Am× n二维数组, 可用如下形式存放到内存,a00，
a01,… a0n-1,a10,a11,...,a1 n-1,…, am-1 0, am-1 1,…,
am-1 n-1。 即二维数组按行优先存放到内存后, 变成了一
个线性序列 （ 线性表 ） 。
因此，可以得出多维数组按行优先存放到内存的规律：
最左边下标变化最慢，最右边下标变化最快，右边下
标变化一遍，与之相邻的左边下标才变化一次。因此，
在算法中，最左边下标可以看成是外循环，最右边下
标可以看成是最内循环。
2．地址计算
由于多维数组在内存中排列成一个线性序列, 因此, 若
知道第一个元素的内存地址, 如何求得其它元素的内存
地址？ 我们可以将它们的地址排列看成是一个等差数列,
假设每个元素占 l个字节, 元素 aij 的存储地址应为第一个
元素的地址加上排在 aij 前面的元素所占用的单元数, 而
aij 的前面有 i行 (0~i-1)共 i× n个元素, 而本行前面又有 j个
元素, 故 aij的前面一共有 i× n+j个元素, 设 a00的内存地
址为 LOC(a00), 则 aij 的内存地址按等差数列计算为
LOC(aij)=LOC(a00)+ （ i× n+j ） × l 。 同理, 三维数组
Am× n× p 按 行 优 先 存 放 的 地 址 计 算 公 式 为,
LOC(aijk)=LOC(a000)+(i× n× p+j× p+k)× l。
5.2.2 列优先顺序
1,存放规则
列优先顺序也称为高下标优先或右边下标优先于左边下
标。具体实现时，按列号从小到大的顺序，先将第一列
中元素全部存放好，再存放第二列元素，第三列元素，
依次类推 ……
在 FORTRAN语言程序设计中, 数组是按列优先顺序存
放的 。 例如, 对前面提到的 Am× n二维数组, 可以按如下
的形式存放到内存,a00,a10…, am-10,a01,a11,…,
am-1 1,…, a0 m-1,a1m-1,...,am-1 n-1。 即二维数组按列
优先存放到内存后, 也变成了一个线性序列 （ 线性表 ） 。
因此, 可以得出多维数组按列优先存放到内存的规律：
最右边下标变化最慢, 最左边下标变化最快, 左边下
标变化一遍, 与之相邻的右边下标才变化一次 。 因此,
在算法中, 最右边下标可以看成是外循环, 最左边下
标可以看成是最内循环 。
2．地址计算
同样与行优先存放类似, 若知道第一个元素的内存地址,
则同样可以求得按列优存放的某一元素 aij的地址 。
对二维数组有,LOC(aij)=LOC(a00)+(j× m+i)× l
对三维数组有：
LOC(aijk)=LOC(a000)+(k× m× n+j× m+i)× l
5.3 特殊矩阵及其压缩存储
5.3.1 特殊矩阵
若一个 n阶方阵 A中元素满足下列条件：
aij=aji 其中 0 ≤i,j≤n-1, 则称 A为对称
矩阵 。
例如, 图 5-1是一个 3*3的对称矩阵 。
A=
643
452
321
图 5 - 1 一个对称矩阵
1．对称矩阵
2．三角矩阵
（ 1） 上三角矩阵
即矩阵上三角部分元素是随机的，而下三角部分元
素全部相同（为某常数 C）或全为 0，具体形式见
图 5-2(a)。
（ 2） 下三角矩阵
即矩阵的下三角部分元素是随机的，而上三角部
分元素全部相同（为某常数 C）或全为 0，具体形
式见图 5-2(b)。
111110
1110
00
.,,
.,,.,,.,,.,,
.,,
.,,
???? nnnn
aaa
caa
cca
( a) 上三角矩阵 （ b ）下三角矩阵
11
1111
100100
.,,.,,.,,.,,
.,,
.,,
??
?
?
nn
n
n
accc
aac
aaa
图 5 - 2 三角矩阵
3．对角矩阵
若矩阵中所有非零元素都集中在以主对角线为中
心的带状区域中, 区域外的值全为 0,则称为对角
矩阵 。 常见的有三对角矩阵, 五对角矩阵, 七对
角矩阵等 。
例如，图 5-3为 7?7的三对角矩阵（即有三条对角
线上元素非 0）。
6665
565554
454443
343332
232221
121110
0100
00000
0000
0000
0000
0000
0000
00000
aa
aaa
aaa
aaa
aaa
aaa
aa
图 5 - 3 一个 7 ? 7 的三对角矩阵
5.3.2 压缩存储
1．对称矩阵
若矩阵 An?n是对称的, 对称的两个元素可以共用一个存
储单元, 这样, 原来 n 阶方阵需 n2个存储单元, 若采用
压缩存储, 仅需 n(n+1)/2个存贮单元, 将近节约一半存
贮单元, 这就是实现压缩的好处 。 但是, 将 n阶对称方
阵存放到一个向量空间 s[0]到 s[ -1] 中,
我们怎样找到 s[k]与 a[i][j]的一一对称应关系呢？ 使我们
在 s[k]中直接找到 a[i][j]。
2 )1( ?nn
我们仅以行优先存放分两种方式讨论：
（ 1） 只存放下三角部分
由于对称矩阵关于主对角线对称, 故我们只需存放主
对角线及主对角线以下的元素 。 这时, a[0][0]存入
s[0],a[1][0] 存入 s[1],a[1][1]存入 s[2],…, 具体参
见图 5-4。 这时 s[k]与 a[i][j]的对应关系为：
i(i+1)/2+j 当 i≥j
k=
j(j+1)/2+i 当 i<j
上面的对应关系读者很容易推出：当 i≥j 时, aij在下三角
部分中, aij前面有 i行, 共有 1+2+3+… +i个元素, 而 aij是
第 i行的第 j个元素, 即有 k=1+2+3+…- +i+j=i(i+1)/2+j；当
i<j时, aij在上三角部分中, 但与 aji对称, 故只需在下三角
部分中找 aij即可, 故只需将 i与 j交换即可, 即 k=j(j+1)/2+i。
11121110
222120
1110
00
...
...............
????? nnnnn
aaaa
aaa
aa
a
( a ) 一个下三角矩阵
a 00 a 10 a 11 a 20 a 21 a 22 a 30 a 31 … … a n - 1n - 3 a n - 1n - 2 a n - 1n - 1
0 1 2 3 4 5 6 7 ……
2
)1( ?nn
- 3
2
)1( ?nn
- 2
2
)1( ?nn
- 1
( b ) 下三角矩阵的压缩存储形式
图 5 - 4 对称矩阵及用下三角压缩存储
(2) 只存放上三角部分
对于对称阵, 除了用下三角形式存放外, 还可以用上
三角形式存放, 这时 a[0][0]存入 s[0],a[0][1]存入 s[1]，
a[0][2]存入 s[2],…, 具体参见图 5-5。 这时 s[k]与 a[i][j]
的对应关系可以按下面方法推出：
当 i≤j时, aij在上三角部分中, 前面共有 i行, 共有 n+n-
1+… +n-(i-1)=i*n- 个元素, 而 aij是本行第 j-i个元素,
故 k=i*n- +j-i,当 i>j时, 交换 i与 j即可 。 故 s[k]与 a[i][j]
的对应关系为：
2 )1( ?ii
2 )1( ?ii
i*n- +j-i 当 i≤j
k=
j*n- +i-j 当 i>j
2 )1( ?ii
2 )1( ?jj
11
1222
111211
10020100
...............
...
...
...
??
?
?
?
nn
n
n
n
a
aa
aaa
aaaa
(a ) 一个上三角矩阵
a 00 a 01 a 02 a 03 a 04 a 05 a 06 a 07 … … a n - 2n - 2 a n - 2n - 1 a n - 1n - 1
0 1 2 3 4 5 6 7 …… 2
)1( ?nn
- 3 2
)1( ?nn
- 2 2
)1( ?nn
- 1
(b ) 上三角矩阵的压缩存储形式
图 5 - 5 对称矩阵及用上三角压缩存储
2．三角矩阵
（ 1） 下三角矩阵
下三角矩阵的压缩存放与对称矩阵用下三角形式存放
类似, 但必须多一个存储单元存放上三角部分元素,
使用的存储单元数目为 n(n+1)/2+1。 故可以将 n?n的下
三角矩阵压缩存放到只有 n(n+1)/2+1个存储单元的向量
中, 假设仍按行优先存放, 这时 s[k]与 a[i][j]的对应关系
为：
i(i+1)/2+j i≥j
k=
n(n+1)/2 i<j
(2)上三角矩阵
和下三角矩阵的存储类似，共需 n(n+1)/2+1个存贮单
元，假设仍按行优先顺序存放，这时 s[k]与 a[i][j]的对
应关系为：
i*n-i(i-1)/2 +j-i 当 i≤j
k=
n(n+1)/2 i>j
3,对角矩阵
我们仅讨论三对角矩阵的压缩存贮, 五对角矩阵, 七
对角矩阵等读者可以作类似分析 。
在一个 n?n的三对角矩阵中, 只有 n+n-1+n-1个非零元
素, 故只需 3n-2个存储单元即可, 零元已不占用存储
单元 。
故可将 n?n三对角矩阵 A压缩存放到只有 3n-2个存储单
元的 s向量中, 假设仍按行优先顺序存放, 则：
s[k]与 a[i][j]的对应关系为：
3i-1 当 i=j+1
k= 3i 当 i=j
3i+1 当 i=j-1
5.4 稀疏矩阵
在上节提到的特殊矩阵中, 元素的分布呈现某种规
律, 故一定能找到一种合适的方法, 将它们进行压
缩存放 。 但是, 在实际应用中, 我们还经常会遇到
一类矩阵：其矩阵阶数很大, 非零元个数较少, 零
元很多, 但非零元的排列没有一定规律, 我们称这
一类矩阵为稀疏矩阵 。
按照压缩存储的概念，要存放稀疏矩阵的元素，由于
没有某种规律，除存放非零元的值外，还必须存贮适
当的辅助信息，才能迅速确定一个非零元是矩阵中的
哪一个位置上的元素。下面将介绍稀疏矩阵的几种存
储方法及一些算法的实现。
5.4.1 稀疏矩阵的存储
1,三元组表
在压缩存放稀疏矩阵的非零元同时, 若还存放此非零元
所在的行号和列号, 则称为三元组表法, 即称稀疏矩阵
可用三元组表进行压缩存储, 但它是一种顺序存贮 （ 按
行优先顺序存放 ） 。 一个非零元有行号, 列号, 值, 为
一个三元组, 整个稀疏矩阵中非零元的三元组合起来称
为三元组表 。
此时, 数据类型可描述如下：
const int maxsize=100;//定义非零元的最大数目
struct node //定义一个三元组
{ int i,j; //非零元行, 列号
int v; //非零元值
};
struct sparmatrix //定义稀疏矩阵
{ int rows,cols ; //稀疏矩阵行, 列数
int terms; //稀疏矩阵非零元个数
node data [maxsize]; //三元组表
};
00070015
00000180
00002400
01400003
0000000
00009120
?
?
图 5 - 6 稀疏矩阵 M
000000
0001400
000000
700000
0024009
01800012
1500300
?
?
图 5 - 7 稀疏矩阵 N （ M 的转置）
稀疏矩阵 M和 N的三元组表见图 5-8。
图 5 - 8 稀疏矩阵 M 和 N 的三元组
M 的三元组表
i j v
0 1 12
0 2 9
2 0 – 3
2 5 14
3 2 24
4 1 18
5 0 15
5 3 – 7
N 的三元组表
i j v
0 2 - 3
0 5 15
1 0 12
1 4 18
2 0 9
2 3 24
3 5 - 7
5 2 14
2．带行指针的链表
把具有相同行号的非零元用一个单链表连接起来, 稀
疏矩阵中的若干行组成若干个单链表, 合起来称为带
行指针的链表 。 例如, 图 5-6 的稀疏矩阵 M的带行指针
的链表描述形式见图 5-9。
4 1 18 ^
0 1 12 0 2 9 ^
2 0 - 3 2 5 14 ^
3 2 24 ^
5 0 15 5 3 - 7 ^
0
行指针
1
3
4
5
2
图 5 - 9 带行指针的链表
3．十字链表
当稀疏矩阵中非零元的位置或个数经常变动时, 三元组
就不适合于作稀疏矩阵的存储结构, 此时, 采用链表作
为存储结构更为恰当 。
十字链表为稀疏矩阵中的链接存储中的一种较好的存储
方法, 在该方法中, 每一个非零元用一个结点表示, 结
点中除了表示非零元所在的行, 列和值的三元组 (i,j,v)外,
还需增加两个链域：行指针域 (rptr),用来指向本行中下
一个非零元素；列指针域 (cptr), 用来指向本列中下一个
非零元素 。 稀疏矩阵中同一行的非零元通过向右的 rptr指
针链接成一个带表头结点的循环链表 。 同一列的非零元
也通过 cptr指针链接成一个带表头结点的循链链表 。 因此,
每个非零元既是第 i行循环链表中的一个结点, 又是第 j列
循环链表中的一个结点, 相当于处在一个十字交叉路口,
故称链表为十字链表 。
另外, 为了运算方便, 我们规定行, 列循环链表的表头
结点和表示非零元的结点一样, 也定为五个域, 且规定
行, 列, 域值为 0,并且将所有的行, 列链表和头结点
一起链成一个循环链表 。
在行 (列 )表头结点中, 行, 列域的值都为 0,故两组表
头结点可以共用, 即第 i行链表和第 i列链表共用一个表
头结点, 这些表头结点本身又可以通过 V域 (非零元值域,
但在表头结点中为 next,指向下一个表头结点 )相链接 。
另外, 再增加一个附加结点 (由指针 hm指示, 行, 列域
分别为稀疏矩阵的行, 列数目 ),附加结点指向第一个
表头结点, 则整个十字链表可由 hm指针唯一确定 。
十字链表的数据类型描述如下：
struct linknode
{ int i,j;
linknode *cptr,*rptr;
union vnext //定义一个共用体
{ int v; //表结点使用 V域,表示非零元值
linknode *next; / /表头结点使用 next域
} k; }
例如，图 5-6 的稀疏矩阵 M的十字链表描述形式见图 5-10。
6 7
0 0 0 0
0 0
0 0 0 0 0 0
0 0
hm
0 1 12
0 2 9 0 0
0 0
0 0 2 0 - 3
2 5 14
0 0 3 2 24
0 0 4 1 18
0 0 5 0 15
5 3 - 7
图 5 - 10 稀疏矩阵的十字链表
5.4.2 稀疏矩阵的运算
1．稀疏矩阵的转置运算
转置是矩阵中最简单的一种运算 。 对于一个 m?n的矩阵
A,它的转置 B是一个 n?m 的, 且 B[i][j]=A[j][i]，
0≤i<n,0≤j<m。 例如, 图 5-6给出的 M矩阵和图 5-7给出的
N矩阵互为转置矩阵 。
在三元组表表示的稀疏矩阵中，怎样求得它的转置呢?从
转置的性质知道，将 A转置为 B，就是将 A的三元组表
a.data变为 B的三元组表 b.data，这时可以将 a.data中 i和 j 的
值互换，则得到的 b.data是一个按列优先顺序排列的三元
组表，再将它的顺序适当调整，变成行优先排列，即得到
转置矩阵 B。下面将用两种方法处理：
（ 1） 按照 A的列序进行转置
由于 A的列即为 B的行, 在 a.data中, 按列扫描, 则得
到的 b.data必按行优先存放 。 但为了找到 A的每一列中
所有的非零的元素, 每次都必须从头到尾扫描 A的三
元组表 (有多少列, 则扫描多少遍 ),这时算法描述如
下：
void transpose(sparmatrix a,sparmatrix b)
{b.rows=a.cols; b.cols=a.rows;
b.terms=a.terms;
if (b.terms>0){int bno=0;
for (int col=0; col<a.cols; col++)//按列号扫描
for(int ano=0;ano<a.terms;ano++)//对三元组表扫描
if (a.data[ano].j==col) //进行转置
{ b.data[bno].j=a.data[ano].i;
b.data[bno].i=a.data[ano].j;
b.data[bno].v=a.data[ano].v;
bno++;}}}
分析这个算法, 主要工作在 col和 ano二重循环上, 故
算法的时间复杂度为 O(a.cols*a.terms)。 而通常的 m?n
阶矩阵转置算法可描述为：
for(col=0; col<n; col++)
for (row=0;row<m;row++)
b[col][row]=a[row][col];
它的时间复杂度为 o(m?n)。 而一般的稀疏矩阵中非零
元个数 a.terms远大于行数 m,故压缩存贮时, 进行转
置运算, 虽然节省了存贮单元, 但增大了时间复杂度,
故此算法仅适应于 a.terns<<a.rows? a.cols的情形 。
（ 2） 按照 A的行序进行转置
即按 a.data中三元组的次序进行转置, 并将转置后的三
元组放入 b中恰当的位置 。 若能在转置前求出矩阵 A的
每一列 col(即 B中每一行 )的第一个非零元转置后在
b.data中的正确位置 pot[col](0≤col<a.cols),那么在对
a.data的三元组依次作转置时, 只要将三元组按列号 col
放置到 b.data[pot[col]]中, 之后将 pot[col]内容加 1,以
指示第 col列的下一个非零元的正确位置 。 为了求得位
置向量 pot,只要先求出 A的每一列中非零元个数
num[col],然后利用下面公式：
pot[0]=0
pot[col]=pot[col-1]+num[col-1] 当 1≤col<a.cols
算法描述如下：
void fastrans(sparmatrix a,sparmatrix b)
{ int pot[100],col,ano,bno;
b.rows=a.cols; b.cols=a.rows;b.terms=a.terms;
if (b.terms>0)
{ for(col=0;col<a.cols;col++) pot[col]=0;
for(int t=0;t<a.terms;t++) //求出每一列的非零元个数
{ col=a.data[t].j; pot[col+1]=pot[col+1]++; }
pot[0]=0;
for(col=1;col<a.cols;col++) //求出每一列的第一
个非零元在转置后的位置
pot[col]=pot[col-1]+pot[col];
for( ano=0;ano<a.terms;ano++) //转置
{ col=a.data[ano].j; bno=pot[col];
b.data[bno].j=a.data[ano].i;
b.data[bno].i=a.data[ano].j;
b.data[bno].v=a.data[ano].v;
pot[col]=pot[col]+1;}}
}
该算法比按列转置多用了辅助向量空间 pot,但它的时
间为四个单循环, 故 总 的 时 间 复 杂 度 为
O(a.cols+a.terms),比按列转置算法效率要高 。
2,稀疏矩阵的相加运算
当稀疏矩阵用三元组表进行相加时，有可能出现非零元
素的位置变动，这时候，不宜采用三元组表作存储结构，
而应该采用十字链表较方便。
5.5 广义表
5.5.1基本概念
广义表是第二章提到的线性表的推广。线性表中的元素
仅限于原子项，即不可以再分，而广义表中的元素既可
以是原子项，也可以是子表 (另一个线性表 )。
1,广义表的定义
广义表是 n≥0个元素 a1,a2,…, an的有限序列, 其中每
一个 ai或者是原子, 或者是一个子表 。 广义表通常记为
LS=(a1,a2,…,an),其中 LS为广义表的名字, n为广义表的
长度, 每一个 ai为广义表的元素 。 但在习惯中, 一般用
大写字母表示广义表, 小写字母表示原子 。
2．广义表举例
(1) A=( ),A为空表, 长度为 0。
(2) B=(a,（ b,c） ),B是长度为 2的广义表, 第一项为原
子, 第二项为子表 。
(3) C=(x,y,z) C是长度为 3的广义表, 每一项都是原
子 。
D=(B,C), D是长度为 2的广义表, 每一项都是上面提
到的子表 。
E=(a,E) 是长度为 2的广义表, 第一项为原子, 第二项为
它本身 。
3．广义表的表示方法
(1) 用 LS=(a1,a2,…, an)形式, 其中每一个 ai为原子或
广义表
例如,A=(b,c)
B=(a,A)
E=(a,E)
都是广义表 。
（ 2） 将广义表中所有子表写到原子形式, 并利用圆括号
嵌套
例如, 上面提到的广义表 A,B,C可以描述为：
A(b,c)
B(a,A(b,c))
E(a,E(a,E（ … ） ))
(3) 将广义表用树和图来描述
上面提到的广义表 A,B,C的描述见图 5-11。
B A
C
b a c
A
b
c
B
a A
b c
(a ) A =(b,c) (b) B=( a,A ) (c ) C =(A,B )
图 5 - 11 广义表用树或图来表示
4．广义表的深度
一个广义表的深度是指该广义表展开后所含括号的层数 。
例如, A=(b,c)的深度为 1,B=(A,d)的深度为 2,C=(f,B,h)
的深度为 3。
5．广义表的分类
（ 1） 线性表：元素全部是原子的广义表 。
（ 2） 纯表,与树对应的广义表, 见图 5-11的 (a)和 (b)。
（ 3） 再入表, 与图对应的广义表 (允许结点共享 ),见图
5-11的 (c)。
（ 4） 递归表：允许有递归关系的广义表, 例如 E=(a,E)。
这四种表的关系满足：
递归表 ?再入表 ? 纯表 ? 线性表
5.5.2存储结构
由于广义表的元素类型不一定相同, 因此, 难以用顺序
结构存储表中元素, 通常采用链接存储方法来存储广义
表中元素, 并称之为广义链表 。 常见的表示方法有：
1．单链表表示法
即模仿线性表的单链表结构, 每个原子结点只有一个链
域 link,结点结构是：
at om da ta /sl in k li nk
可用如图 5-12的结构描述广义表
C=(A,B)=((x,(a,b)),((x,(a,b)),y)),设头指针为 hc。
0 0 ^
0 1 y ^
1 x 0 ^
1 a 1 b ^
hc
A B
A
L
图 5 - 12 广义表的单链表表示法
2,双链表表示法
每个结点含有两个指针及一个数据域，每个结点的结
构如下：
l i n k 1 d at a l i n k 2
例如，对图 5-12用单链表表示的广义表 C，可用图
5-13的双链表方法表示。
A B ^
A ^ y ^
x L ^
^ a ^ b ^
hc
图 5 - 13 广义表的双链表表示法
5.5.3 基本运算
广义表有许多运算，现仅介绍如下几种：
1.求广义表的深度 depth(LS)
假设广义表以刚才的单链表表示法作存储结构, 则它
的深度可以递归求出 。 即广义表的深度等于它的所有
子表的最大深度加 1,设 dep表示任一子表的深度,
max表示所有子表中表的最大深度, 则广义表的深度
为,depth=max+1,算法描述如下：
int depth(node *LS)
{ int max=0;
while(LS!=NULL)
{ if(LS->atom==0) //有子表
{ int dep=depth(LS->slink);
if(dep>max) max=dep;}
LS=LS->link;
}
return max+1;}
该算法的时间复杂度为 O(n)。
2.广义表的建立 creat(LS)
假设广义表以单链表的形式存储, 广义表的元素类型
elemtype 为字符型 char,广义表由键盘输入, 假定全部
为字母, 输入格式为：元素之间用逗号分隔, 表元素
的起止符号分别为左, 右圆括号, 空表在其圆括号内
使用一个, #”字符表示, 最后使用一个分号作为整个
广义表的结束 。
例如，给定一个广义表如下,LS=(a,( ),b,c (d,(e) ) )，则
从键盘输入的数据为,(a,(#),b,c(d,(e)));↙,其中 ↙ 表示
回车换行。具体算法描述如下：
void creat(node *LS)
{ char ch; cin>>ch;
if(ch=='#') LS=NULL;
else if(ch=='(')
{LS=new node;
LS->atom=0; creat(LS->slink);}
else { LS=new node;
LS->atom=1; LS->data=ch; }
cin>>ch; if(LS==NULL);
else if(ch==',') creat(LS->link);
else if((ch==')')||(ch==';'))LS->link=NULL;}
该算法的时间复杂度为 O(n)。
3.输出广义表 print(LS)
void print(node *LS)
{ if(LS->atom==0)
{cout<<'(';
if(LS->slink==NULL) cout<<'#';
else print(LS->slink); }
else cout<<LS->data;
if(LS->atom==0) cout<<')';
if(LS->link!=NULL)
{ cout<<','; print(LS->link);}}
该算法的时间复杂度为 O(n)。
4．取表头运算 head
若广义表 LS=(a1,a2,…, an),则 head(LS)=a1 。
取表头运算得到的结果可以是原子, 也可以是一个
子表 。
例如, head((a1,a2,a3,a4))=a1,
head(((a1,a2),(a3,a4),a5))=(a1,a2)。
5,取表尾运算 tail
若广义表 LS=(a1,a2,…, an),则 tail(LS)=(a2,a3,…,
an)。
即取表尾运算得到的结果是除表头以外的所有元素, 取
表尾运算得到的结果一定是一个子表 。
值得注意的是广义表 ( )和 (())是不同的，前者为空表，长
度为 0，后者的长度为 1，可得到表头、表尾均为空表，
即 head((( )))=( ),tail((( )))=( )。
