.··························································
·· 第5 章 chapter5
数组和广义表
数组是人们已经非常熟悉的一种数据类型,几乎所有的计算机高级程序设计语言都
支持数组这种数据类型,它的特点是数组中的数据元素都具有相同的数据类型,不同的
元素通过下标来区别。本章主要讨论数组的逻辑结构、几种特殊矩阵的压缩存储以及广
义表的存储与操作。
【本章学习要求】
掌握:数组的基本概念、数组的存储结构特点以及数组元素存储地址的计算。
掌握:特殊矩阵的压缩存储技术,如对称矩阵、三角矩阵、对角矩阵等的压缩存储。
掌握:稀疏矩阵的压缩存储方法———三元组表和十字链表。
掌握:广义表的基本定义和概念,理解广义表的递归性。
了解:广义表的存储特点和基本操作算法。
5.1 案例导引
数组是程序设计中非常重要的存储形式,它可以将分散的数据按要求存放到一起,
为数据的进一步处理提供方便,下面看几个案例。
【案例5.1】 图的保存。
利用二维数组形式(常称为邻接矩阵,详见第7章),可以很方便地将一个图的信息
保存下来,如图5.1(a)所示的无向图,用1表示有边相连,0表示没有直接边相连,则对应
的邻接矩阵如图5.1(b)所示。
图5.1 无向图及其对应的邻接矩阵
◆
136
数据结构（
C
语言版）(第
2
版·微课版)
2】
【案例5.图像的保存。
数字图像数据可以用矩阵来表示,因此可以采用矩阵理论和矩阵算法对数字图像进
行分析和处理。由于数字图像可以表示为矩阵的形式,所以在计算机数字图像处理程序
中,通常用二维数组来存放图像数据。
二维数组的行对应图像的高,二维数组的列对应图像的宽,二维数组的元素对应图
像的像素,二维数组元素的值就是像素的灰度值。采用二维数组来存储数字图像,符合
二维图像的行列特性,同时便于程序的寻址操作,使得计算机图像编程十分方便。
数字图像一般有二值图像、灰度图像、彩色图像之分。其中二值图像按名字来理解
只有两个值,0和1,1代表白, 而1表示前景。其保存也相
0代表黑,或者说0表示背景,
对简单,每个像素只需要1b 就可以完整存储信息。灰度图像是二值图像的进化版本,是
彩色图像的退化版,也就是灰度图像保存的信息没有彩色图像多,但比二值图像多,灰度
图像只包含一个通道的信息,而彩色图像通常包含3个通道的信息。灰度图像是每个像
素只有一个采样颜色的图像,这类图像通常显示为从最暗的黑色到最亮的白色的灰度,
用于显示的灰度图像通常用每个采样像素8b 的非线性尺度来保存,这样可以有256 级灰
度。彩色图像,每个像素通常是由红(R)、绿(G)、蓝(B)三个分量来表示的,每个分量值介于
(255 )。图5.a) 32×32 像素), 2(和图5.c)
0,2(是原始人脸图像(图5.b) 2(分别是对应的二值
图像和灰度图像。图5.3所示是二值图像对应的矩阵,图5.
4所示是灰度图像对应的矩阵。
图5.原始图像及其转换
2
【案例5.图像卷积操作。
3】
近年来,深度学习非常热门,而深度学习的网络结构要用到卷积操作。卷积的基本
性质是将一个核与一个离散的单位脉冲进行卷积,在脉冲的位置上得到一个核的拷贝。
在图像处理中,卷积操作是提取图像特征的一种方法,5所示。经过卷积操作的过
如图5.
滤器可以提取到图像的轮廓特征。
图5.6所示的卷积过程就是卷积核不停在原图上进行滑动(左上角开始), 每次滑动
移动1格,然后再利用原图与卷积核上的数值进行计算得到缩略图矩阵(卷积特征)的数
据。当卷积窗口滑动到某一位置时,窗口中的输入子数组与卷积核数组按元素相乘并求
卷积特征)6中的输出数组(
和,得到输出数组( 中相应位置的元素。图5.卷积特征)的第
一个元素(左上角)4的计算过程为1×1+0×1+1×1+0×0+1×1+0×1+1×0+
0×0+1×1=4。
◆
第
5
章 数组和广义表137
图5.二值图像对应的矩阵
3
图5.灰度图像对应的矩阵
4
◆
138
数据结构（
C
语言版）(第
2
版·微课版)
图5.图像特征提取
5
图5.特征提取过程
6
4】
【案例5.本科生导师制问题。
在高校的教学改革中,有很多学校实行了本科生导师制。一个班级的学生被分给几
个老师,每个老师带领多个学生,如果老师还带研究生,那么研究生也可以直接负责本
科生。
本科生导师制问题中的数据元素具有如下形式。
(1)导师带研究生:( 导师,(( 研究生1,( 本科生1,…, 本科生m)),… ))。
(2)导师不带研究生:( 导师,( 本科生1,…, 本科生m))。
例如:
(章老师,(( 李强,( 王集山,武义军,刘秀)), 张红卫,程昌义,姜和利)) 表示章老师指
导6名本科生和一名叫李强的研究生,其中有3个本科生(王集山,武义军,刘秀)由研究
生李强负责指导。
(李老师,( 齐珊珊,黄凯,刘树发,陈海星)) 表示李老师指导4名本科生,没有指导研
究生。
读者可以思考这两个数据信息表与前面所学的线性表有什么不同? 如果不用这种
信息表,利用线性表能把导师制中导师与本科生以及导师与研究生之间的逻辑关系表达
出来吗? 这种信息表就是本章要介绍的广义表,表中每个元素可以是类似线性表中的元
素(原子项), 又可以是嵌套的线性表。这种数据结构在数据处理中有广泛的应用。
第◆5 章 数组和广义表1 39
5.2 数 组
5.2.1 数组的定义
简单地讲,数组是由n(n≥1)个相同类型数据元素a0,a1,…,an-1组成的有限序列,
且该有限序列存储在一块地址连续的内存单元中,因而数组是顺序存储结构。
对于一个一维数组,一旦a0 的存储地址Loc(a0)确定,每个数据元素的存储单元数
k 确定,则任一数据元素ai 的存储地址Loc(ai)可由以下公式求出:
Loc(ai)=Loc(a0)+i×k (0≤i <n) (5.1)
对于二维数组,可将其转化为一维数组来考虑。例如图5.7为一个m 行n 列的二维
数组,可以看成一个线性表
A =(b0,b1,…,bn-1)
其中每个数据元素bi=(a0i,a1i,…,am -1,i)(0≤i <n)。
Am ×n =
a00 a01 a02 … a0,n-1
a10 a11 a12 … a1,n-1
. . . .
am -1,0 am -1,1 am -1,2 … am -1,n-1
é
.
êêêê
ù
.
úúúú
图5.7 二维数组示例
显然,二维数组同样满足数组的定义。一个二维数组可以看作是每个数据元素都是
相同类型的一维数组的一维数组。以此类推,一个三维数组可以看作是一个每个数据元
素都是相同类型的二维数组的一维数组,等等。
因此,数组具有以下特点:
(1)数组中的数据元素具有相同的数据类型。
(2)数组是一种随机存储结构,可以根据给定的一组下标直接访问对应的数组
元素。
(3)一旦建立了数组,则数组中的数据元素个数和元素之间的关系就不再发生
变化。
5.2.2 数组的内存映像
一维数组是用内存中一段连续的存储空间进行存储的,它的存储结构关系为式(5.1)。
由于计算机的内存结构是一维的,因此用一维内存来表示多维数组,就必须按某种次序
将数组元素排成一个序列,然后将这个线性序列存放在存储器中。对于二维数组,其存
储可按行或列的次序用一组连续存储单元存放数组中的数组元素。如在C、PASCAL、
BASIC等多数程序语言中,采用的是按行序为主序的存储结构,图5.7所示的二维数组
可表示为图5.8(a),即先存储第1行,然后紧接着存储第2行,最后存储第m 行。而在
FORTRAN等少数程序语言中,采用的是以列序为主序的存储方式,图5.7所示的二维数组
可表示为图5.8(b),即先存储第1列,然后紧接着存储第2列,最后存储第n 列。
1 40 ◆数据结构（C 语言版）(第2 版·微课版)
图5.8 二维数组的两种存储形式
在一个以行序为主序的计算机系统中,当二维数组第一个数据元素a00的存储地址
为Loc(a00),假定每个数据元素占k 个存储单元,则该二维数组中任一数据元素的存储
地址可由下式确定:
Loc(aij)=Loc(a00)+ (i×n +j)×k (5.2)
同理,可计算出更高维数组的数据元素存储位置的计算公式。
5.3 特殊矩阵的压缩存储
矩阵运算是许多科学和工程计算问题中常常遇到的问题,在用高级程序设计语言编
制程序求解矩阵问题时,一般都是用二维数组来存储矩阵元素。在实际应用中,常常出
现有许多值相同的元素或有许多零元素,且分布有一定规律的矩阵,一般称为特殊矩阵。
为了节省存储空间,可以对这类特殊矩阵进行压缩存储,即多个相同的非零元素只分配
一个存储空间;对零元素不分配空间。本节讨论这些特殊矩阵的压缩存储。
5.3.1 对称矩阵
在一个n 阶方阵A 中,若所有元素满足下述性质:
aij =aji 0≤i,j ≤n -1
则称A 为对称矩阵。
由于对称矩阵中的元素关于主对角线对称,因而只要存储矩阵中上三角或下三角中
的元素,让每两个对称的元素共享一个存储空间,这样就可以将n2 个元素压缩存储到
n(n+1)/2个元素的空间中,能节约近一半的存储空间。假定按“行优先顺序”存储主对
角线(包括对角线)以下的元素。
第◆5 章 数组和广义表1 41
假设以一维数组sa[n(n+1)/2]作为n 阶对称矩阵A 的存储结构,则A 中任一元素
aij和sa[k]之间存在如下对应关系:
k =
i(i+1)
2 +j i ≥j
j(j+1)
2 +i i <j
ì
.
í
..
..
(5.3)
由此,称一维数组sa[n(n+1)/2]为n 阶对称矩阵A 的存储结构。其存储对应关系
如图5.9所示。
图5.9 对称矩阵的压缩存储
5.3.2 三角矩阵
以主对角线划分,三角矩阵有上三角和下三角两种。所谓n 阶下(上)三角矩阵是指
矩阵的上(下)三角(不包括主对角线)中的元素均为常数或零的n 阶方阵。可以采用和
对称矩阵类似的压缩存储方法来存储。三角矩阵中的重复元素c可共享一个存储空间,
其余的元素正好有n(n+1)/2个,可以用一维数组sa[n(n+1)/2+1]作为n 阶下(上)
三角矩阵A 的存储结构,其中常量c存放在数组的最后一个单元中,当A 为下三角矩阵
时,任一元素aij和sa[k]之间存在式(5.4)的对应关系。
k =
i(i+1)
2 +j i ≥j
n(n +1)
2 i <j
ì
.
í
..
..
(5.4)
5.3.3 稀疏矩阵
什么是稀疏矩阵? 简单说,设矩阵Amn 中有s 个非零元素,若s 远远小于矩阵元素的
总数(即s<<m ×n),则称A 为稀疏矩阵。令e=s/(m ×n),称e 为矩阵的稀疏因子。
当用数组存储稀疏矩阵中元素时,仅有少部分的空间被利用,造成空间浪费。为节省存
储空间,可以采用一种压缩的存储方法来表示稀疏矩阵的内容。由于非零元素的分布一
般是没有规律的,因此在存储非零元素的同时,还必须同时记下元素所在的行和列的位
置(row,col)。由于a00位于矩阵的第1行第1列,因此,稀疏矩阵A 中的任一非零元素
aij可由一个三元组(i+1,j+1,aij)唯一确定。
1.三元组表
假设非零元素的三元组是以按行优先的顺序排列,一个稀疏矩阵就可转换成用一个
对应的线性顺序表来表示,其中每个元素由一个上述的三元组构成,该线性表称为三元
组表,记为(i,j,v)。其类型说明如下:
1 42 ◆数据结构（C 语言版）(第2 版·微课版)
#define MAXSIZE 1000
typedef struct {
int i, j; /*非零元素的行、列号*/
DataType v; /*非零元素的值*/
}triple;
typedef struct {
triple data[MAXSIZE]; /*非零元素的三元组表*/
int m,n,t; /*稀疏矩阵的行数、列数和非零元素的个数*/
}tripletable;
下面以矩阵的转置为例,说明在这种压缩存储结构上如何实现矩阵的运算。
一个m×n 的矩阵A,它的转置B 是一个n×m 的矩阵,且a[i][j]=b[j][i],即A 的行
是B 的列,A 的列是B 的行。例如图5.10(a)中稀疏矩阵A 及其转置矩阵B 可用图5.10(b)
所示的三元组表示。
图5.10 稀疏矩阵的三元组表示
将A 转置为B,就是将A 的三元组表a.data置换为B 的三元组表b.data,如果只是
简单地交换a.data中i 和j 的内容,那么得到的b.data将是一个按列优先顺序存储的稀
疏矩阵B,要得到按行优先顺序存储的b.data,就必须重新排列三元组的顺序。有如下两
种方法来进行处理。
(1)第一种方法(跳着找,顺着存)。
由于A 的列是B 的行,因此按a.data的列序转置,所得到的转置矩阵B 的三元组表
b.data必定是按行优先存放的。按这种方法设计的算法,其基本思想是对A 中的每一列
col(1≤col≤n),通过从头至尾扫描三元表a.data,找出所有列号等于col的那些三元组,
将它们的行号和列号互换后依次放入b.data中,即可得到B 的按行优先的压缩存储
表示。具
体算法如下。
【算法5.1】
tripletable transmatrix(tripletable a)
{ /*将稀疏矩阵a 转置,结果通过函数名返回*/
tripletable b;
int p,q,col;
第◆5 章 数组和广义表1 43
b.m=a.n; /*矩阵b 的行数等于矩阵a 的列数*/
b.n=a.m; /*矩阵b 的列数等于矩阵a 的行数*/
b.t=a.t; /*矩阵b 的非零元素数等于矩阵a 的非零元素数*/
if(b.t) /*把a 中每一个非零元素转换到b 中相应位置*/
{ q=0;
for(col=1;col<=a.n;col++) /*按列号扫描*/
for(p=0;p<a.t;p++) /*在数据中找列号为col 的三元组*/
if(a.data[p].j==col)
{ b.data[q].i=col; /*新三元组的行号/*
b.data[q].j=a.data[p].i; /*新三元组的列号/*
b.data[q].v=a.data[p].v; /*新三元组的值/*
q++;
}
}
return(b);
}
上述算法主要工作是在p和col的两重循环中完成的,故算法的时间复杂度为
O(a.n×a.t),即与矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算
法为
for(col=0;col<n;++col)
for(row=0;row<m;++row)
b[col][row]=a[row][col];
其时间复杂度为O(n×m )。当非零元素的个数t 和m ×n 同数量级时,算法transmatrix
的时间复杂度为O(m ×n2),因此上述稀疏矩阵转置算法的时间大于非压缩存储的矩阵
转置的时间。三元组顺序表虽然节省了存储空间,但时间复杂度比一般矩阵转置的算法
大,同时还有可能增加算法的难度。因此,此算法仅适用于t<<m ×n 的情况。
(2)第二种方法(顺着找,跳着存)。
第一种方法中重复比较的次数比较多,为了节省时间,需要确定矩阵A 中每一列第
一个非零元素在B 中应存储的位置,为了确定这个位置,在转置前应求得矩阵A 中的每
列非零元素的个数。其算法思想为对A 扫描一次,按A 第二列提供的列号一次确定位
置装入B 的三元组中。具体实施方法如下:一遍扫描先确定三元组的位置关系,二次扫
描由位置关系装入三元组。可见,位置关系是此种算法的关键。
为此需要附设两个一维数组num 和pot,num[j]表示矩阵A 中的第j 列非零元素
个数,pot[j]表示A 矩阵中第j 列下一个非零元素在B 中应存放的位置(初值为该列第
一个非零元素在B 中应存放的位置)。显然有:
pot[1]=0
pot[j]=pot[j-1]+num[j-1] 2≤j ≤a.n
例如,矩阵A 的num 和pot的数组元素值如表5.1所示。
1 44 ◆数据结构（C 语言版）(第2 版·微课版)
表5.1 矩阵A 的向量num 和pot的值
j 1 2 3 4 5
num[j] 1 2 0 1 1
pot[j] 0 1 3 3 4
快速转置算法如下。
【算法5.2】
tripletable fasttranstri(tripletable a)
{ /*将稀疏矩阵a 做快速转置,结果通过函数名返回*/
tripletable b;
int p,q,col,k;
int num[a.n+1], pot[a.n+1]; /*建立辅助数组*/
b.m=a.n; b.n=a.m; b.t=a.t;
if(b.t)
{ for(col=1;col<=a.n;++col) /*对数组num 初始化*/
num[col]=0;
for(k=0;k<a.t;++k) /*计算a 中每一列含非零元素的个数*/
++num[a.data[k].j];
pot[1]=0; /*计算a 中第col 列中第一个非零元素在b 中的序号*/
for(col=2;col<=a.n;++col)
pot[col]=pot[col-1]+num[col-1];
for(p=0;p<a.t;++p)/*把a 中每一个非零元素插入b 中的相应位置*/
{ col=a.data[p].j;
q=pot[col];
b.data[q].i=a.data[p].j;
b.data[q].j=a.data[p].i;
b.data[q].v=a.data[p].v;
++pot[col];
}
}
return(b);
}
该算法虽然多用了两个辅助向量空间,但它的时间复杂度为O(a.n+a.t),比第一种
方法要好。
2.十字链表存储
三元组表是用顺序方法来存储稀疏矩阵中的非零元素,当非零元素的位置或个数经
常变化时,三元组表就不适合做稀疏矩阵的存储结构。例如,两矩阵做加操作时,会改变
非零元素的个数,如用三元组表表示矩阵时,元素的插入和删除会导致大量的结点移动。
此时,采用链式存储结构更为合适。