第5章 数组和广义表
数组和广义表可以看成线性表的一种推广,即表中的数据元素本身也可以是线性结构。
本章将讨论数组的基本概念和存储结构、特殊矩阵和稀疏矩阵的压缩存储以及广义表的定
义和存储结构。
5.1 数 组
5.1.1 数组的基本概念
数组是由n(n≥1)个相同类型的数据元素构成的有限序列,其逻辑表示如下:
a =(a0,a1,…,an-1)
若ai(i=0,1,…,n-1)是简单元素,则a 是一维数组;当一维数组的每个元素ai本身
又是一个一维数组时,则一维数组扩充为二维数组。同理,二维数组的每个元素本身又是一
个一维数组时,则二维数组扩充为三维数组。以此类推,若ai是n-1维数组,则a 是n 维
数组。在n 维数组中,每个元素受n(n≥1)个线性关系的约束,它在n 个线性关系中的序号
i1,i2,…,in ,称为该元素的下标。如果数组名为a,则记下标为i1,i2,…,in 的元素
为ai1i2…in 。
数组可以看成线性表的推广,数组的特点是数据元素本身可以具有某种结构,但属于同
一类型。例如,一维数组可以看作一个线性表,二维数组可以看作数据元素是线性表的线性
表。如图5-1中所示的二维数组,可以看成一个线性表
A = a0,a1,…,( ap ) (p =m -1或n -1)
其中每个数据元素是一个列向量形式的线性表,如图5-1(b)所示,或者是一个行向量形式
的线性表,如图5-1(c)所示。
图5-1 二维数组示例
数组一旦被定义,它的维数和维界就不再改变。因此,数组除了初始化和销毁之外,通
常只有以下两种操作。
(1)读操作:给定一组下标,读取相应的数据元素。
·98·
(2)写操作:给定一组下标,存储或修改相应的数据元素。
下面给出数组的抽象数据类型定义。
ADT Array
{
数据对象:
D ={aj 1 j 2 …j n |ji =0,1,…bi -1, i =1,2,…n ,bi 为第i 维的长度}
数据关系:
R ={r 1,r 2,…,rn }
ri ={<aj 1 …ji …jn ,aj 1 …ji +1 …jn >|0≤jk ≤bk -1,1≤k ≤n 且k ≠i ,0≤ji ≤bi - 2,i = 2,3,…,
n }
基本操作:
InitArrary()
操作结果: 初始化数组,即为数组分配空间。
DistroyArrary()
初始条件: 数组已存在。
操作结果: 销毁数组。
Value(&e , index1, index2, …, indexn )
初始条件: n 维数组已存在。
操作结果: 若下标不越界,则将所指定的数组元素的值赋值给e 。
Assign(e , index1, index2, …, indexn )
初始条件: n 维数组已存在。
操作结果: 若下标不越界,则将e 的值赋值给所指定的数组元素。
}
5.1.2 数组的存储结构
由于很少对数组进行插入和删除操作,也就是说,一旦建立了数组,其元素个数和元素
之间的关系就不再发生变动,因此,采用顺序存储结构表示数组比较合适。
1.一维数组的存储结构
对于一维数组(a0,a1,…,an-1),按元素顺序存储到一块地址连续的内存单元中。假设
第一个元素a0的存储地址用LOC(a0)表示,每个元素占用L 个存储单元,则任一数组元素
ai的存储地址LOC(ai)都可由式(5-1)求出:
LOC(ai)=LOC(a0)+i×L (1≤i ≤n -1) (5-1)
2.多维数组的存储结构
由于内存单元是一维的结构,而多维数组是多维的结构,因此,采用顺序存储结构存储
多维数组时需要将多维结构映射到一维结构。常用的映射方法有两种:以行序为主序(即
按行优先)和以列序为主序(即按列优先)。C++中的数组就是按行优先存储的。
对于二维数组,按行优先存储的基本思想是:先行后列,先存储行号较小的元素,行号
相同者先存储列号较小的元素,如图5-2(b)所示。假设第一个元素a00 的存储地址用
LOC(a00)表示,每个元素占用L 个存储单元,则二维数组中任一元素aij 的存储地址
LOC(aij)可由式5-2确定。
LOCai( j ) =LOC(a00 ) + (n ×i+j) ×L (5-2)
·99·
图5-2 二维数组的两种存储方式
按列优先存储的基本思想是:先列后行,先存储列号较小的元素,列号相同者先存储行号
较小的元素,如图5-2(c)所示。二维数组中任一元素aij 的存储地址LOC(aij)可由式(5-3)
确定。
LOCai( j ) =LOC(a00 ) + (m ×j+i) ×L (5-3)
对于三维数组和更高维数组,按行优先存储的思想是:最右边的下标先变化,即最右下
标从小到大,循环一遍后,右边第二个下标再变化,……,以此类推,最后是最左下标。按列
优先存储的思想是:最左边的下标先变化,即最左下标从小到大循环一遍后,左边第二个下
标再变化,……,依此类推,最后是最右下标。
由以上讨论可知,数组无论是按行优先存储,还是按列优先存储,都可以在O(1)的时间
内计算出指定元素的存储地址,因此,存取数组中任一元素的时间都相等,即数组是一种随
机存取结构。
5.2 矩 阵
矩阵是很多科学与工程计算问题中研究的数学对象,在高级语言程序设计中,矩阵用二
维数组表示。但是,在数值分析中经常出现一些阶数很高的矩阵,同时矩阵中有很多相同的
元素或零元素。为了节省存储空间,可以对这类矩阵进行压缩存储,即为多个值相同的元素
只分配一个存储空间,对零元素不分配存储空间。
5.2.1 特殊矩阵的压缩存储
特殊矩阵是指值相同的元素或零元素在矩阵中的分布有一定规律的矩阵。特殊矩阵的
主要形式有对称矩阵、三角矩阵和对角矩阵,它们都是方阵,即行数和列数相同。
1.对称矩阵
若一个n 阶方阵A 中的元素满足下述性质:
·100·
二维数组的
存储
1≤i,
则称
A
为
n
阶对称矩阵。例如,图5-3所示(i) 为一个5阶对称矩阵。
对称矩阵中的元素是按主对角线对称的,即上三角部分和
下三角部分中的对应元素相等,因此,在存储时可以只存储主对
角线加上三角部分的元素,或主对角线加下三角部分的元素。
这样,一个
n
阶对称矩阵只需要n(节约了
近一半的存储空间。
n+1)/2个存储单元,
假设采用按行优先方式,将主对角线加下三角部分的元素图5-3 对称矩阵
存储到一个具有n(n+1)/2个存储单元的一维数组sa中,如
图5-4所示。矩阵
A
中的元素aij
存储在数组元素sa[k]中,如何根据
i
和
j
确定下标
k
的值?
aij
=ajj
≤
n
图5-4 对称矩阵的压缩存储
(1)若aij
是矩阵
A
中主对角线或下三角部分的元素,则有i≥j。元素aij
的前面共存
储了i-1行,第1行有1个元素,第2行有2个元素,……, 第i-1行有i-1个元素,这i1行共有1+2+…+i-1i(-1)/2个元素;第
i
行中,元素aij
的前面共存储j-1个元
=i
素。因此,元素ai的前面共存储了i(1)/2+j-1个元素,在数组sa中的下标
k
为
ji-aij
i-1)k=i(
2 +j-1
(2)若aij
是矩阵
A
中上三角部分的元素,则有i<j。aij
的值等于aji,元素aji
是矩阵
下三角部分的元素,它存放在下标为j(1)/2+i-1的位置,即
j-1)k=j(
2 +i-1
综合两种情况,得到
k
与i、
j
的关系如下:
j
·101·
k =
i(i-1)
2 +j-1 i ≥j
j(j-1)
2 +i-1 i <j
ì
.
í
..
..
(5-4)
对称矩阵的类模板的声明及实现如下所示。
//类模板的声明
template<typename T>
class SymmetricMatrix
{p
rotected:
T *sa; //存储矩阵元素
int n; //对称矩阵阶数
public:
SymmetricMatrix(int n); //构造一个n 阶对称矩阵
~SymmetricMatrix(); //析构函数
T &operator()(int i, int j); //重载()运算符
};
//类模板的实现
template <typename T>
SymmetricMatrix<T>::SymmetricMatrix(int n) //构造函数,n 为矩阵的阶数
{
if (n<1)
throw "阶数无效!";
this->n=n;
sa=new T[n*(n+1)/2]; //为一维数组sa 分配存储空间
}t
emplate <typename T>
SymmetricMatrix<T>::~SymmetricMatrix() //析构函数
{
delete []sa;
}t
emplate <typename T>
T &SymmetricMatrix<T>::operator()(int i, int j) //重载()运算符
{
if (i<1 || i>n || j<1 || j>n)
throw "下标越界!";
if (i>=j) //元素在主对角线或下三角中
return sa[i*(i-1)/2+j-1];
else //元素在上三角中
return sa[j*(j-1)/2+i-1];
}
定义对称矩阵类SymmetricMatrix后,在程序中就可以使用它定义对称矩阵的对象,
通过括号运算符访问矩阵中的数据元素。
#include <iostream>
·102·
#include "symmetric_matrix.h"
using namespace std;
void main()
{
try
{
int i, j, n, tmp;
cout<<"请输入矩阵的阶数: "<<endl;
cin>>n;
SymmetricMatrix<int>a(n); //定义一个n 阶对称矩阵
for (i=1; i<=n; i++) //输入数据
{
cout<<"请输入矩阵的第"<<i<<"行数据: "<<endl;
for (j=1; j<=n; j++)
{
cin>>tmp;
a(i, j)=tmp;
}
}
for (i=1; i<=n; i++) //显示对称矩阵
{
for (j=1; j<=n; j++)
cout<<a(i, j)<<"\t";
cout<<endl;
}
}
catch (char *error)
{
cout<<error<<endl;
}
}
2.三角矩阵
三角矩阵有上三角矩阵和下三角矩阵两种。上三角矩阵是指矩阵下三角部分中的元素
均为常数c 的n 阶方阵。下三角矩阵是指矩阵上三角部分中的元素均为常数c 的n 阶方
阵,有时c=0。例如,图5-5中的A1 为上三角矩阵,A2 为下三角矩阵。
图5-5 三角矩阵
·103·
对上三角矩阵进行压缩存储时,除了存储主对角线和上三角中的元素外,再加一个存储
常数c 的空间。因此,上三角矩阵可以用一个具有n(n+1)/2+1个存储单元的一维数组
存储,常数c 存储在数组最后的位置。
若aij是矩阵A 中主对角线或上三角部分的元素,则有i≤j。在按行优先的存储方式
下,元素aij的前面共存储了i-1行,第1行有n 个元素,第2行有n-1个元素,……,第
i-1行有n-i+2个元素,这i-1行共有:
n + (n -1)+ … + n -( i+2) = (i-1)(2n -i+2)
2
个元素;第i 行中,元素aij 的前面共存储了j-i 个元素。因此,元素aij 的前面共存储了
(i-1)(2n-i+2)/2+j-i 个元素,所以,元素aij在数组中的下标k 为
k = (i-1)(2n -i+2)
2 +j-i
若aij是矩阵A 中下三角部分的元素,则有i>j,其值为常数c,存储在数组的最后一个
位置,下标为n(n+1)/2。
综上,得到k 与i、j 的关系如下:
k =
(i-1)(2n -i+2)
2 +j-i i ≤j
n(n +1)
2 i >j
ì
.
í
..
..
(5-5)
对下三角矩阵进行压缩存储时,除了存储主对角线和下三角中的元素外,再加一个存储
常数c 的空间。同上三角矩阵一样,下三角矩阵也可以用一个具有n(n+1)/2+1个存储
单元的一维数组存储,常数c 存储在数组的最后位置。
采用类似对称矩阵的推导过程,得到k 与i、j 的关系如下:
k =
i(i-1)
2 +j-1 i ≥j
n(n +1)
2 i <j
ì
.
í
..
..
(5-6)
3.对角矩阵
在对角矩阵中,所有非零元素都集中在以主对角线为中心的带状区域,除了主对角线和
图5-6 对角矩阵
若干条次对角线的元素外,其他元素都为零。例如,图5-6所示
为一个对角矩阵。对这种矩阵,也可按某个原则(以行为主,或
以对角线的顺序)将其压缩存储到一维数组中。
以上讨论的对称矩阵、三角矩阵和对角矩阵的压缩存储方
法是把有一定分布规律的、值相同的数据元素压缩存储到一个
连续的存储空间中,这样的压缩存储只需在算法中按公式做映
射即可实现特殊矩阵元素的随机存取。
5.2.2 稀疏矩阵的压缩存储
如果一个矩阵中的非零元素个数远远小于矩阵元素的总数,且非零元素的分布无一定
规律,则称之为稀疏矩阵。在稀疏矩阵和稠密矩阵之间没有一个精确的界限,可以用稀疏因
·104·
子描述矩阵的稀疏程度。设一个m 行n 列的矩阵中有t 个非零元素,则稀疏因子δ=
t/(m ×n)。通常,在δ<0.5时,就可以认为矩阵是稀疏的。
当稀疏矩阵的阶很高时,其中零元素会很多,如果用一个二维数组直接存储稀疏矩阵,
将存储大量零元素,造成存储空间的浪费。但如果不存储零元素,而只存储非零元素,元素
的存储顺序又不能反映它们的逻辑关系,因此需要显示地指出每个元素在原矩阵中的逻辑
位置。一种直观、常用的方法是对每个非零元素用三元组(行号,列号,元素值)表示。三元
组的结构定义如下:
template<typename T>
struct Element
{
int row, col; //非零元素的行下标与列下标
T value; //非零元素的值
};
将稀疏矩阵的非零元素对应的三元组所构成的集合,按行优先排成一个线性表,称为三
元组表,则稀疏矩阵的压缩存储转化为三元组表的存储。例如,图5-7所示稀疏矩阵A 的三
元组表为((1,2,6),(2,4,3),(3,5,4),(5,1,1),(5,3,5),(6,4,7))。
稀疏矩阵采用三元组表存储,一定程度上节省了存储空间,但也丧失了随机存取
特性。
1.三元组顺序表
以顺序表存储三元组表,可得到稀疏矩阵的顺序存储结构———三元组顺序表。例如,
图5-7所示稀疏矩阵的三元组顺序表如图5-8所示。
图5-7 稀疏矩阵
图5-8 稀疏矩阵A 的三元组顺序表
三元组顺序表的类模板定义及实现如下,成员变量实现三元组顺序表的存储结构,其中
数组elems用于存储非零元素的三元组,maxSize为数组的长度,即稀疏矩阵中非零元素的
最大个数,rows和cols分别存储稀疏矩阵的行数和列数,num 存储稀疏矩阵中非零元素的
实际个数;成员函数实现稀疏矩阵的基本操作,包括返回稀疏矩阵的行数或列数,返回或设
置元素的值等。
//三元组顺序表类模板的定义
template<typename T>
·105·
class SparseMatrix
{
protected:
Element<T>*elems; //存储稀疏矩阵的三元组表
int rows, cols, num; //行数、列数及非零元素的个数
int maxSize; //非零元素的最大个数
public:
SparseMatrix(int rs, int cs, int size); //构造函数
~SparseMatrix(); //析构函数
int GetRows(); //返回稀疏矩阵的行数
int GetColumns(); //返回稀疏矩阵的列数
int GetNum() ; //返回稀疏矩阵非零元素的个数
bool SetElem(int r, int c, T v); //设置指定位置的元素值
bool GetElem(int r, int c, T &v); //返回指定位置的元素值
};
//三元组顺序表类模板的实现
template <typename T>
SparseMatrix<T>::SparseMatrix(int rs, int cs, int size)
//构造函数,rs、cs、size 分别表示行数、列数和非零元素的最大个数
{
if (rs<1 || cs<1)
throw "行数或列数无效!";
maxSize=size;
rows=rs;
cols=cs;
num=0;
elems=new Element<T>[maxSize];
}
template <typename T>
SparseMatrix<T>::~SparseMatrix() //析构函数
{
delete []elems;
}
template <typename T>
int SparseMatrix<T>::GetRows() //返回稀疏矩阵的行数
{
return rows;
}
template <typename T> //返回稀疏矩阵的列数
int SparseMatrix<T>::GetColums()
{
return cols;
·106·
}
template <typename T> //返回非零元素的个数
int SparseMatrix<T>::GetNum()
{
return num;
}
template <typename T>
bool SparseMatrix<T>::SetElem(int r, int c, T v)
{
int i=0, j;
if (r<1 || r>rows || c<1 || c>cols) //下标越界
return false;
while (i<num && r<elems[i].row) //查找第r 行的第一个非零元素
i++;
while (i<num && r==elems[i].row && c<elems[i].col)//查找第r 行第c 列的元素
i++;
if (elems[i].row==r && elems[i].col==c) //找到
{
if (v!=0) //若v≠0,则修改元素值
elems[i].value=v;
else //若v=0,则删除三元组
{
for (j=i+1; j<num; j++) //前移元素
elems[j-1]=elems[j];
num--; //非零元素个数减1
}
return true;
}
else if (v!=0) //若未找到,则将元素插入三元组表
{
if (num>=maxSize)
return false;
else
{
for (j=num-1; j>=i; j--) //后移元素
elems[j+1]=elems[j];
elems[i].row=r; //插入元素
elems[i].col=c;
elems[i].value=v;
num++; //非零元素个数增1
}
}
·107·