第5章 数组和广义表
5.1 数 组
1.数组的基本概念
数组是一个元素可直接按序号寻址的线性表: 
a=(a0,a1,…,am -1) 
若ai(i=0,1,…,m -1)是简单元素,则a 是一维数组;当一维数组的每个元素ai本
身又是一个一维数组时,则一维数组扩充为二维数组。同样道理,当ai是一个二维数组时, 
则二维数组扩充为三维数组。以此类推,若ai是k-1维数组,则a 是k 维数组。
可以看出,在n 维数组中,每个元素受n 个线性关系的约束(n≥1),若它在第1~n 个
线性关系中的序号分别为i1,i2,…,in ,则称它的下标为i1,i2,…,in 。如果数组名为a, 
则记下标为i1,i2,…,in 的元素为ai1 ,i2 ,…,in 。
从上面的定义可以看出,如果一个n(n>0)维数组的第i 维长度为bi,则此数组中共含
有Πn 
i=1
bi个数据元素,每个元素都受n 个关系的约束,就其单个关系而言,这n 个关系都是线
性关系。
数组的基础操作如下: 
ElemType &operator()(int sub0,…) 
初始条件:数组已存在。
操作结果:重载函数运算符。
2.数组的顺序存储结构
设n 维数组共有m =Πn 
i=1 
( bi ) 个元素,数组存储的首地址为base,数组中的每个元素需
要size个存储单元,则整个数组共需m ·size个存储单元。为了存取数组中某个特定下标
的元素,必须确定下标为i1,i2,…,in 的元素的存储位置。实际上就是把下标i1,i2,…,in 
映射到[0,m -1]中的某个数Map(i1,i2,…,in ),使得该下标所对应的元素值存储在以
下位置: 
Loc(i1,i2,…,in)=base+ Map(i1,i2,…,in)·size 
其中,Loc(i1,i2,…,in)表示下标为i1,i2,…,in 的数组元素的存储地址。可见,如果已
经知道数组的首地址,要确定其他元素的存储位置,只需求出Map(i1,i2,…,in)即可。具
体如下: 
Map(i1,i2,…,in)=i1b2b3…bn +i2b3…bn + … +in-1bn +in 
= Σn-1 
j=1
ij Πn 
k=j+1
bk +in =Σn 
j=1
cjij 
·16·

进一步可得如下公式: 
Loc(i1,i2,…,in)=base+ (i1b2b3…bn +i2b3…bn + … +in-1bn +in)size 
=base+ Σn 
j=1
cjij·size 
其中,cn =1,cj-1=bjcj,1<j ≤n。
n 维数组a[b1][b2]…[bn]的列优先映射函数为
Map(i1,i2,…,in)=i1 +b1i2 + …+b1b2…bn-2in-1 +b1b2…bn-1in 
=i1 + Σn 
j=2 Πj-1 
k=1 
( bk )ij =Σn 
j=1
cjij 
Loc(i1,i2,…,in)=base+ (i1 +b1i2 + …+b1b2…bn-2in-1 +b1b2…bn-1in)size 
=base+ Σn 
j=1
cjijsize 
其中,c1=1,cj+1=bjcj,1≤i <n。
5.2 矩 阵
1.矩阵的定义和操作
矩阵与二维数组有很多相似之处,一般用如下的二维数组来描述一个m ×n 矩
阵am ×n : 
ElemTypea[m ][n]; 
矩阵中的元素a(i,j)对应于二维数组的元素a[i-1][j-1]。这种形式要求使用数
组的下标[][]来指定每个矩阵元素。这种变化降低了应用代码的可读性,也增加了出错的
概率。可以通过定义一个类Matrix来克服这个问题。在Matrix类中,将矩阵元素按照行
优先次序存储到一个一维数组elems中,另外通过重载函数运算符()实现使用(i,j)来指
定每个元素并且根据矩阵的约定,其行列下标值都是从1开始。
矩阵的基础操作如下: 
1)intGetRows()const 
初始条件:矩阵已存在。
操作结果:返回矩阵行数。
2)intGetCols()const 
初始条件:矩阵已存在。
操作结果:返回矩阵列数。
3)ElemType&operator()(inti,intj) 
初始条件:矩阵已存在。
操作结果:重载函数运算符。
2.特殊矩阵
如果值相同的元素或零元素在矩阵中按一定的规律分布,这样的矩阵称为特殊矩
阵,可以用特殊方法进行存储和处理,以便提高空间和时间效率。下面首先介绍相关的
·17·

几个概念。

(1)方阵(squarematrix): 是行数和列数相同的矩阵。下面介绍的特殊矩阵都是
方阵
(
。
2)对称(矩阵:
a 
是一个对称矩阵当且仅当对于所有的
i 
和
j 
有a(

symmetric) i,j)= 
j,i), 5.

a(如图1.1(a)所示。


图1.1 特殊矩阵示例

5.
(3)三对角(rdagnl) 
a 
是一个三对角矩阵当且仅当|-i,j)0
tiioa矩阵:ij|>1 时有a(=
(或常数c), 如图1.1(所示。

5.b)

(4)下三角(oeraglr) 
a 
是一个下三角矩阵当且仅当i<
j 
时有a(=
lwrtinua矩阵:i,j)0 
(或常数c), 1(所示。

如图1.c)

5.
(5)上三角(pprtinua矩阵:i,j)0
ueraglr) 
a 
是一个上三角矩阵当且仅当i>
j 
时有a(=
(或常数c), 5.d)所示。

如图1.1(
特殊矩阵的基础操作如下
:
1)intGetOrder()const
初始条件:特殊矩阵已存在
。
操作结果:返回特殊矩阵阶数
。
2)ElemType&oprtr()(now,itcol)


eaoitrn
初始条件:特殊矩阵已存在
。
操作结果:重载函数运算符
。


3. 
稀疏矩阵
如一个矩阵中有许多元素为0,则称该矩阵为稀疏(sparse)矩阵。对每个非零元素,用
三元组(行号,列号,元素值)来表示,这样每个元素的信息就全部记录下来了。

各非零元素对应的三元组及其行列数可唯一确定一个稀疏矩阵。

稀疏矩阵具有如下的一些基本操作: 

1)intGetRows()const 

初始条件:稀疏矩阵已存在。

操作结果:返回稀疏矩阵行数。

2)intGetCols()const 

初始条件:稀疏矩阵已存在。

操作结果:返回稀疏矩阵列数。

3)intGetNum()const 

初始条件:稀疏矩阵已存在。

操作结果:返回稀疏矩阵非零元素个数。

·18· 


4)boolEmpty()const 

初始条件:稀疏矩阵已存在。

操作结果:如稀疏矩阵为空,则返回true,否则返回false。

5)bolStem(nncntEl

oeElitr,itc,osemType&v)
初始条件:稀疏矩阵已存在
。
操作结果:设置指定位置的元素值
。


6)boolGetElintr,inemType&v)

em(tc,El
初始条件:稀疏矩阵已存在
。
操作结果:求指定位置的元素值
。
稀疏矩阵包含三元组顺序表与十字链表两种存储结构,下面分别加以介绍
。


(1)三元组顺序表。以顺序表存储三元组表,可得到稀疏矩阵的顺序存储结构———三
元组顺序表。在三元组顺序表中,用三元组表表示稀疏矩阵时,为避免丢失信息,增设了一
个信息元组,形式如下:
(行数,列数,非零元素个数) 
将它作为三元组表的第一个元素。

*(2)十字链表:稀疏矩阵中的非零元素个数或位置在操作过程中经常发生变化时,就
不适合采用三元组顺序表来表示稀疏矩阵的非零元素了,这时可采用链式存储方式表示稀
疏矩阵。由于稀疏矩阵的链式存储表示最终形成了一个十字交叉的链表,所以这种存储结
构叫作十字链表。十字链表是一种特殊的链表,它不仅可以用来表示稀疏矩阵,事实上,一
切具有正交关系的结构,都可用十字链表存储。在此,我们基于稀疏矩阵来介绍十字链表的
相关内容。
在稀疏矩阵的十字链表表示中,每个非零元素对应十字
链表中的一个节点,各节点的结构如图1.2所示。

5.
节点中的row 、col、value分别记录各非零元素的行号、图1.2 十字链表节点结构
5.
列号和元素值,down 、right是两个指针,分别指向同一列和
同一行的下一个非零元素节点。这样,每个非零元素既是某个行链表中的一个节点,又是某
个列链表中的一个节点。

5.广义表
3 

1. 
基本概念
广义表通常简称为表,是由n(个表元素组成的有限序列,记作

n≥0)

GL=a1,
n 
其中,GL 为表名,n=
(a2,…,为表(a) ) 
i 
=1,2,…,

n 
为表的长度,0时为空表。ai 
元素(n), 简称为元
素,它可以是单个数据元素(称为原子元素,或简称为原子), 也可以是满足本定义的广义表
(称为子表元素,或简称为子表)。

广义表具有如下基本操作。

·19· 


1)GenListNode<ElemType>*First()const
初始条件:广义表已存在
。
操作结果:返回广义表的第一个元素
。


2)GenListNode<ElemType>*Next(GenListNode<ElemType>*elemPtr)const 
初始条件:广义表已存在,elemPtr指向广义表的元素。
操作结果:返回elemPtr指向的广义表元素的后继。

3)boolEmpty()const
初始条件:广义表已存在
。
操作结果:如广义表为空,则返回true,否则返回false
。


4)voidPush(constElemType&e)
初始条件:广义表已存在
。
操作结果:将原子元素
e 
作为表头加入广义表最前面
。


5)voidPush(GenList<ElemType>&subList)
初始条件:广义表已存在
。
操作结果:将子表subList作为表头加入广义表最前面
。


6)intDepth()const
初始条件:广义表已存在
。
操作结果:返回广义表的深度
。


*2. 
广义表的存储结构
广义表的链式存储可以有多种形式,具体使用时,应根据具体问题的要求选择不同的存
储结构。下面给出一种常用的借助引用数的链式存储结构———引用数法广义表。在这种方
法中,每个表节点由3个成员组成,如图1.3所示。

5.
图1.3 引用数法广义表节点结构

5.
上面引用数法广义表节点结构中,nextLink用于存储指向后继节点的指针,这样将广
义表的各元素连接成一个链表,为方便起见还在链表的前面加上头节点,这样广义表的节点
可分3种类型。

(1)头节点,用标志tg=HEAD 标识,f用于存储引用数,子表的引用数表示能访问
are
此子表的广义表或指针个数。

(2)原子节点,用标志tag=ATOM 标识,原子元素用原子节点存储,atom 用于存储原
子元素的值。
·20· 


(3)表节点,用标志tag=LIST 
标识,subLink用于存储指向子表头节点的指针。
这种存储结构的广义表具有如下特点。
(1)广义表中的所有表,不论是哪一层的子表,都带有一个头节点,空表也不例外,其优
点是便于操作。特别是当一个广义表被其他表共享的时候,如果要删除这个表中的第一个
元素,则需删除此元素对应的节点。如果广义表的存储中不带表头节点,则必须检测所有的
子表节点,逐一修改那些指向被删节点的指针,这样修改既费时,又容易发生遗漏。如果所
有广义表都带有表头节点,在删除表中第一个表元素所在节点时,由于头节点不会发生变
化,从而也就不用修改任何指向该子表的指针。
(2)表中节点的层次分明。所有位于同一层的表元素,在其存储表示中也在同一层。
(3)可以很容易计算出表的长度。从头节点开始,沿nextLink链能够找到的节点个数
即为表的长度。
在释放广义表节点时,如直接在物理上释放广义表节点,这时由于广义表具有元素共享
性,可能还有其他广义表要引用被释放广义表的节点,因此在逻辑上释放广义表并不表示一
定要在物理上释放节点。为了判断是否能在物理上释放一个广义表节点,可用“引用数”识
别,引用数就是能访问广义表的广义表或指针个数。由于头节点的数据成分是空闲的,正好
用来存放引用数。在释放广义表时,首先让引用数自减1,如果引用数为0,则在物理上释放
节点。

虽然用头节点和引用数解决了表共享的释放问题,但对于递归表,引用数不会为0,这
样就无法实现释放递归表的目的,因此如果不改变思想,递归表会出现问题;进而可以这样
来解决释放广义表的问题,建立一个全局广义表使用空间表对象,专门用于收集指向广义表
中节点的指针,用析构函数在程序结束时统一释放所有广义表节点,这样实现时,不再需要
引用数,头节点的数据部分为空,这样的广义表称为使用空间法广义表。

·21
·