第五章 多维数组和广义表
1 多维数组
2 多维数组的存储结构
3 特殊矩阵及其压缩存储
4 稀疏矩阵
5 广义表本章小结本章学习导读本章主要介绍多维数组的概念及在计算机中的存放,特殊矩阵的压缩存储及相应运算,广义表的概念和存储结构及其相关运算的实现 。 通过本章学习,要求掌握如下内容：
1,多维数组的定义及在计算机中的存储表示；
2,对称矩阵,三角矩阵,对角矩阵等特殊矩阵在计算机中的压缩存储表示及地址计算公式；
3,稀疏矩阵的三元组表示及转置算法实现；
4,稀疏矩阵的十字链表表示及相加算法实现；
5,广义表存储结构表示及基本运算 。
5.1 多维数组
5.1.1 多维数组的概念数组是大家都已经很熟悉的一种数据类型,几乎所有高级语言程序设计中都设定了数组类型 。 在此,我们仅简单地讨论数组的逻辑结构及在计算机内的存储方式
。
1,一维数组一维数组可以看成是一个线性表或一个向量 （ 第 2章已经介绍 ）,它在计算机内是存放在一块连续的存储单元中,适合于随机查找 。 这在第 2章的线性表的顺序存储结构中已经介绍 。
2,二维数组二维数组可以看成是向量的推广 。 例如,设 A是一个有 m行 n列的二维数组,则 A
可以表示为：
a 00 a 01 …… a 0n - 1
a 10 a 11 …… a 1n - 1
…………………………,
A=
a m - 1 0 a m - 1 1 …… a m - 1 n - 1
在此,可以将二维数组 A看成是由 m个行向量 [X0,X1,…,Xm-1]T组成,
其中,Xi=( ai0,ai1,…,,ain-1),0≤i≤m-1；也可以将二维数组 A看成是由 n
个列向量 [y0,y1,……,yn-1]组成,其中 yi=(a0i,a1i,…,.,am-1i),0≤i≤n-1。
由此可知二维数组中的每一个元素最多可有两个直接前驱和两个直接后继 （ 边界除外 ）,故是一种典型的非线性结构 。
3,多维数组同理,三维数组最多可有三个直接前驱和三个直接后继,三维以上数组可以作类似分析 。 因此,可以把三维以上的数组称为多维数组,多维数组可有多个直接前驱和多个直接后继,故多维数组是一种非线性结构 。
5.1.2 多维数组在计算机内的存放怎样将多维数组中元素存入到计算机内存中呢？ 由于计算机内存结构是一维的 （ 线性的 ）,因此,用一维内存存放多维数组就必须按某种次序将数组元素排成一个线性序列,然后将这个线性序列顺序存放在存储器中,具体实现方法在下一节介绍 。
5.2 多维数组的存储结构由于数组一般不作插入或删除操作,也就是说,一旦建立了数组,
则结构中的数组元素个数和元素之间的关系就不再发生变动,即它们的逻辑结构就固定下来了,不再发生变化 。 因此,采用顺序存储结构表示数组是顺理成章的事了 。 本章中,仅重点讨论二维数组的存储,三维及三维以上的数组可以作类似分析 。
多维数组的顺序存储有两种形式 。
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 特殊矩阵及其压缩存储矩阵是一个二维数组,它是很多科学与工程计算问题中研究的数学对象 。 矩阵可以用行优先或列优先方法顺序存放到内存中,但是,当矩阵的阶数很大时将会占较多存储单元 。 而当里面的元素分布呈现某种规律时,这时,从节约存储单元出发,可考虑若干元素共用一个存储单元,即进行压缩存储 。 所谓压缩存储是指：为多个值相同的元素只分配一个存储空间,值为零的元素不分配空间 。 但是压缩存储时,节约了存储单元,但怎样在压缩后找到某元素呢？ 因此还必须给出压缩前的下标和压缩后下标之间变换公式,才能使压缩存储变得有意义 。
1,对称矩阵若一个 n阶方阵 A中元素满足下列条件：
aij=aji 其中 0 ≤i,j≤n-1,则称 A为对称矩阵 。
例如,图 5-1是一个 3*3的对称矩阵 。
5.3.1 特殊矩阵
2,三角矩阵
（ 1） 上三角矩阵即矩阵上三角部分元素是随机的,而下三角部分元素全部相同 （ 为某常数 C） 或全为 0,具体形式见图 5-2（ a） 。
图 5-1 一个对称矩阵
A=
643
452
321
（ 2） 下三角矩阵即矩阵的下三角部分元素是随机的,而上三角部分元素全部相同 （ 为某常数 C）
或全为 0,具体形式见图 5-2（ b） 。
（ a） 上三角矩阵 （ b） 下三角矩阵图 5-2 三角矩阵
111110
1110
00
.,,
.,,.,,.,,.,,
.,,
.,,
nnnn aaa
caa
cca
11
1111
100100
.,,.,,.,,.,,
.,,
.,,
nn
n
n
accc
aac
aaa
3,对角矩阵若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中,区域外的值全为 0,则称为对角矩阵 。 常见的有三对角矩阵,五对角矩阵,七对角矩阵等 。
例如,图 5-3为 7× 7的三对角矩阵 （ 即有三条对角线上元素非 0） 。
图 5-3 一个 7× 7的三对角矩阵
6665
565554
454443
343332
232221
121110
0100
00000
0000
0000
0000
0000
0000
00000
aa
aaa
aaa
aaa
aaa
aaa
aa
5.3.2 压缩存储
11121110
222120
1110
00
...
...............
nnnnn
aaaa
aaa
aa
a
（ a）一个下三角矩阵
（ b）下三角矩阵的压缩存储形式矩阵及用下三角压缩存储图 5-4 对称
a 00 a 1 0 a 11 a 20 a 2 1 a 22 a 30 a 31 …… a n -1 n -3 a n -1 n -2 a n -1 n -1
0 1 2 3 4 5 6 7 …… 2 )1(?nn - 3 2 )1(?nn - 2 2 )1(?nn - 1
3,对角矩阵我们仅讨论三对角矩阵的压缩存储,五对角矩阵,七对角矩阵等读者可以作类似分析 。
在一个 n?n的三对角矩阵中,只有 n+n-1+n-1个非零元素,故只需
3n-2个存储单元即可,零元已不占用存储单元 。
故可将 n?n三对角矩阵 A压缩存放到只有 3n-2个存储单元的 s向量中
，假设仍按行优先顺序存放，
s[k]与 a[i][j]的对应关系为：
3i或 3j 当 i=j
k= 3i+1或 3j-2 当 i=j-1
3i-1 或 3j+2 当 i=j+1
5.4 稀疏矩阵在上节提到的特殊矩阵中,元素的分布呈现某种规律,故一定能找到一种合适的方法,将它们进行压缩存放 。 但是,在实际应用中
,我们还经常会遇到一类矩阵：其矩阵阶数很大,非零元个数较少
,零元很多,但非零元的排列没有一定规律,我们称这一类矩阵为稀疏矩阵 。
按照压缩存储的概念,要存放稀疏矩阵的元素,由于没有某种规律,除存放非零元的值外,还必须存储适当的辅助信息,才能迅速确定一个非零元是矩阵中的哪一个位置上的元素 。 下面将介绍稀疏矩阵的几种存储方法及一些算法的实现 。
5.4.1 稀疏矩阵的存储
1,三元组表在压缩存放稀疏矩阵的非零元同时,若还存放此非零元所在的行号和列号,
则称为三元组表法,即称稀疏矩阵可用三元组表进行压缩存储,但它是一种顺序存储 （ 按行优先顺序存放 ） 。 一个非零元有行号,列号,值,为一个三元组,整个稀疏矩阵中非零元的三元组合起来称为三元组表 。
此时,数据类型可描述如下：
#define maxsize 100 /*定义非零元的最大数目 */
struct node /*定义一个三元组 */
{
int i,j; /*非零元行,列号 */
int v; /*非零元值 */
};
struct sparmatrix /*定义稀疏矩阵 */
{
int rows,cols ; /*稀疏矩阵行,列数 */
int terms; /*稀疏矩阵非零元个数 */
node data [maxsize]; /*三元组表 */
};
2,带行指针的链表把具有相同行号的非零元用一个单链表连接起来,稀疏矩阵中的若干行组成若干个单链表,合起来称为带行指针的链表 。 例如,图 5-6的稀疏矩阵 M的带行指针的链表描述形式见图 5-9。
0 1 20
行指针
1 ^
3
4
5
2
0 2 9 ^
2 5 4 ^
5 3 -7 ^
2 0 -3 ^
3 2 24 ^
4 1 18 ^
5 0 15 ^
图 5-9 带行指针的链表
3,十字链表当稀疏矩阵中非零元的位置或个数经常变动时,三元组就不适合于作稀疏矩阵的存储结构,此时,采用链表作为存储结构更为恰当 。
十字链表为稀疏矩阵中的链接存储中的一种较好的存储方法,在该方法中,
每一个非零元用一个结点表示,结点中除了表示非零元所在的行,列和值的三元组 （ i,j,v） 外,还需增加两个链域：行指针域 （ rptr）,用来指向本行中下一个非零元素；列指针域 （ cptr）,用来指向本列中下一个非零元素 。 稀疏矩阵中同一行的非零元通过向右的 rptr指针链接成一个带表头结点的循环链表 。 同一列的非零元也通过 cptr指针链接成一个带表头结点的循环链表 。
因此,每个非零元既是第 i行循环链表中的一个结点,又是第 j列循环链表中的一个结点,相当于处在一个十字交叉路口,故称链表为十字链表 。
另外,为了运算方便,我们规定行,列循环链表的表头结点和表示非零元的结点一样,也定为五个域,且规定行,列,域值为 0(因此,为了使表头结点和表示非零元的表结点不发生混淆,三元组中,输入行和列的下标不能从 0
开始 !!!而必须从 1开始 ),并且将所有的行,列链表和头结点一起链成一个循环链表 。
在行 （ 列 ） 表头结点中,行,列域的值都为 0,故两组表头结点可以共用,
即第 i行链表和第 i列链表共用一个表头结点,这些表头结点本身又可以通过
V域 （ 非零元值域,但在表头结点中为 next,指向下一个表头结点 ） 相链接
。 另外,再增加一个附加结点 （ 由指针 hm指示,行,列域分别为稀疏矩阵的行,列数目 ）,附加结点指向第一个表头结点,则整个十字链表可由 hm
指针惟一确定 。
例如,图 5-6的稀疏矩阵 M的十字链表描述形式见图 5-10。
十字链表的数据类型描述如下：
struct linknode
{ int i,j;
struct linknode *cptr,*rptr;
union vnext /*定义一个共用体 */
{ int v; /*表结点使用 V域,表示非零元值 */
struct linknode next; /*表头结点使用 next域 */
} k; }
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的三元组表（有多少列，则扫描多少遍），这时算法描述如下：
#define maxsize 100
struct node
{
int i,j; /*定义三元组的行,列号 */
int v; /*三元组的值 */
};
struct sparmatrix
{
int rows,cols; /*稀疏矩阵的行,列数 */
int terms; /*稀疏矩阵的非零元个数 */
struct node data[maxsize]; /*存放稀疏矩阵的三元组表 */
};
void transpose(struct sparmatrix a)
{
struct sparmatrix b; /*b为 a的转置 */
int ano,bno=0,col,i;
b.rows=a.cols; b.cols=a.rows;
b.terms=a.terms;
if (b.terms>0)
{
for ( col=0; col<a.cols; col++) /*按列号扫描 */
for( 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;
for( i=0;i<a.terms;i++) /*输出转置后的三元组结果 */
printf("%5d%5d%5d\n",b.data[i].i,b.data[i].j,b.data[i].v);
}
void main()
{
int i;
struct sparmatrix a;
scanf("%d%d%d",&a.rows,&a.cols,&a.terms); /*输入稀疏矩阵的行,列数及非零元的个数 */
for( i=0;i<a.terms;i++)
scanf("%d%d%d",&a.data[i].i,&a.data[i].j,&a.data[i].v); /*输入转置前的稀疏矩阵的三元组 */
for(i=0;i<a.terms;i++)
printf("%5d%5d%5d\n",a.data[i].i,a.data[i].j,a.data[i].v); /*输出转置前的三元组结果 */
transpose( a); /*调用转置算法 */
}
分析这个算法,主要工作在 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[col]=pot[col-1]+num[col-1] 当 1≤col<a.cols
pot[0]=0
为了节省存储单元,记录每一列非零元个数的向量 num可直接放入 pot中,即上面的式子可以改为,pot[col]=pot[col-1]+pot[col],其中 1≤col<acols。
于是可用上面公式进行迭代,依次求出其他列的第一个非零元素转置后在 b.data
中的位置 pot[col]。 例如,对前面图 5-6给出的稀疏矩阵 M,有：
每一列的非零元个数为
pot[1]=2 第 0列非零元个数
pot[2]=2 第 1列非零元个数
pot[3]=2 第 2列非零元个数
pot[4]=1 第 3列非零元个数
pot[5]=0 第 4列非零元个数
pot[6]=1 第 5列非零元个数
pot[7]=0 第 6列非零元个数每一列的第一个非零元的位置为
pot[0]=0 第 0列第一个非零元位置
pot[1]=pot[0]+pot[1]=2第 1列第一个非零元位置
pot[2]=pot[1]+pot[2]=4第 2列第一个非零元位置
pot[3]=pot[2]+pot[3]=6第 3列第一个非零元位置
pot[4]=pot[3]+pot[4]=7第 4列第一个非零元位置
pot[5]=pot[4]+pot[5]=7第 5列第一个非零元位置
pot[6]=pot[5]+pot[6]=8第 6列第一个非零元位置则 M稀疏矩阵的转置矩阵 N的三元组表很容易写出 （ 见图 5-
8）,算法描述如下：
#define maxsize 100
struct node
{
int i,j;
int v;
};
struct sparmatrix
{
int rows,cols;
int terms;
struct node data[maxsize];
};
void fastrans(struct sparmatrix a)
{
struct sparmatrix b;
int pot[maxsize],col,ano,bno,t,i;
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( t=0;t<a.terms;t++) /*求出每一列的非零元个数 */
{
col=a.data[t].j;
pot[col+1]=pot[col+1]+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;
}
}
for( i=0;i<a.terms;i++)
printf("%d\t%d\t%d\n",b.data[i].i,b.data[i].j,b.data[i].v); /*输出转置后的三元组 */
}
void main()
{ struct sparmatrix a;
int i;
scanf("%d%d%d",&a.rows,&a.cols,&a.terms); /*输入稀疏矩阵的行,列数及非零元的个数 */
for( i=0;i<a.terms;i++)
printf("%d\t%d\t%d\n",b.data[i].i,b.data[i].j,b.data[i].v); /*输出转置后的三元组 */
}
void main()
{ struct sparmatrix a;
int i;
scanf("%d%d%d",&a.rows,&a.cols,&a.terms); /*输入稀疏矩阵的行,列数及非零元的个数 */
for( i=0;i<a.terms;i++)
scanf("%d%d%d",&a.data[i].i,&a.data[i].j,&a.data[i].v); /*输入转置前的三元组 */
for(i=0;i<a.terms;i++)
printf("%d\t%d\t%d\n",a.data[i].i,a.data[i].j,a.data[i].v); /*输出转置前的三元组 */
fastrans(a); /*调用快速转置算法 */
}
该算法比按列转置多用了辅助向量空间 pot,但它的时间为四个单循环,故总的时间复杂度为 O(a.cols+a.terms),比按列转置算法效率要高 。
2,稀疏矩阵的相加运算当稀疏矩阵用三元组表进行相加时,有可能出现非零元素的位置变动,这时候,不宜采用三元组表作存储结构,而应该采用十字链表较方便 。
（ 1） 十字链表的建立下面分两步讨论十字链表的建立算法：
第一步,建立表头的循环链表：
依次输入矩阵的行,列数和非零元素个数,m,n和 t。 由于行,列链表共享一组表头结点,因此,表头结点的个数应该是矩阵中行,列数中较大的一个 。 假设用 s 表示个数,即 s=max（ m,n） 。 依次建立总表头结点 （ 由 hm
指针指向 ） 和 s个行,列表头结点,并使用 next域使 s+1个头结点组成一个循环链表,总表头结点的行,列域分别为稀疏矩阵的行,列数目,s个表头结点的行列域分别为 0。 并且开始时,每一个行,列链表均是一个空的循环链表,即 s个行,列表头结点中的行,列指针域 rptr和 cptr均指向头结点本身 。
第二步,生成表中结点：
依次输入 t个非零元素的三元组 （ i,j,v）,生成一个结点,并将它插入到第 i
行链表和第 j列链表中的正确位置上,使第 i个行链表和第 j个列链表变成一个非空的循环链表 。
在十字链表的建立算法中,建表头结点,时间复杂度为 O(s),插入 t个非零元结点到相应的行,列链表的时间复杂度为 O（ t*s）,故算法的总的时间复杂度为 O(t*s)。
（ 2） 用十字链表实现稀疏矩阵相加运算假设原来有两个稀疏矩阵 A和 B,如何实现运算 A=A+B呢？ 假设原来 A
和 B都用十字链表作存储结构,现要求将 B中结点合并到 A中,合并后的结果有三种可能,1） 结果为 aij+bij； 2） aij（ bij=0） ； 3） bij（ aij=0）
。 由此可知当将 B加到 A中去时,对 A矩阵的十字链表来说,或者是改变结点的 v域值 （ aij+bij≠0）,或者不变 （ bij=0）,或者插入一个新结点 （ aij=0）,还可能是删除一个结点 （ aij+bij=0） 。
于是整个运算过程可以从矩阵的第一行起逐行进行 。 对每一行都从行表头出发分别找到 A和 B在该行中的第一个非零元结点后开始比较,然后按上述四种不同情况分别处理之 。 若 pa和 pb分别指向 A和 B的十字链表中行值相同的两个结点,则 4种情况描述为：
1） pa->j=pb->j 且 pa->k.v+pb->k.v≠0,则只要将 aij+bij的值送到 pa所指结点的值域中即可,其他所有域的值都不变化 。
2） pa->j=pb->j且 pa->k.v+pb->k.v=0,则需要在 A矩阵的链表中删除 pa所指的结点 。 这时,需改变同一行中前一结点的 rptr域值,以及同一列中前一结点的 cptr域值 。
3） pa->j<pb->j且 pa->j≠0,则只要将 pa指针往右推进一步,并重新加以比较即可 。
4） pa->j>pb->j或 pa->j=0,则需在 A矩阵的链表中插入 pb所指结点 。
下面将对矩阵 B加到矩阵 A上面的操作过程大致描述如下,
设 ha和 hb分别为表示矩阵 A和 B的十字链表的总表头； ca和 cb分别为指向 A
和 B的行链表的表头结点,其初始状态为,ca=ha->k.next ; cb=hb-
>k.next;
pa和 pb分别为指向 A和 B的链表中结点的指针 。 开始时,pa=ca->rptr;
pb=cb->rptr;然后按下列步骤执行：
① 当 ca->i=0时,重复执行 ②,③,④ 步,否则,算法结束；
② 当 pb->j≠0时,重复执行 ③ 步,否则转第 ④ 步；
③ 比较两个结点的列序号,分三种情形：
a,若 pa->j<pb->j 且 pa->j≠0,则令 pa指向本行下一结点,即 qa=pa; pa=pa-
>rptr; 转 ② 步 ;
b,若 pa->j>pb->j或 pa->j=0,则需在 A中插入一个结点 。 假设新结点的地址为 P,则 A的行表中指针变化为,qa->rptr=p;p->rptr=pa;
同样,A的列表中指针也应作相应改变,用 hl[j]指向本列中上一个结点,则
A的列表中指针变化为,p->cptr=hl[j]->cptr; hl[j]->cptr=p;转第 ② 步；
c,若 pa->j=pb->j,则将 B的值加上去,即 pa->k.v=pa->k.v+bp->k.v,此时若
pa->k.v≠0,则指针不变,否则,删除 A中该结点,于是行表中指针变为：
qa->rptr=pa->rptr; 同时,为了改变列表中的指针,需要先找同列中上一个结点,用 hl[j]表示,然后令 hl[j]->cptr=pa->cptr,转第 ② 步 。
④ 一行中元素处理完毕后,按着处理下一行,指针变化为,ca=ca->k.next;
cb=cb->k.next;转第 1)步 。
5.5 广义表
5.5.1 基本概念广义表是第 2章提到的线性表的推广 。 线性表中的元素仅限于原子项,即不可以再分,而广义表中的元素既可以是原子项,也可以是子表 （ 另一个线性表 ） 。
1,广义表的定义广义表是 n≥0个元素 a1,a2,…,an的有限序列，其中每一个 ai或者是原子，或者是一个子表。广义表通常记为 LS=(a1,a2,…,a n)，其中 LS为广义表的名字,n为广义表的长度,每一个 ai为广义表的元素。但在习惯中，一般用大写字母表示广义表
，小写字母表示原子。
2,广义表举例
（ 1） A=( ),A为空表,长度为 0。
（ 2） B=(a,（ b,c） ),B是长度为 2的广义表,第一项为原子,第二项为子表 。
（ 3） C=(x,y,z),C是长度为 3的广义表,每一项都是原子 。
（ 4） D=(B,C),D是长度为 2的广义表,每一项都是上面提到的子表 。
（ 5） 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。
4,广义表的深度一个广义表的深度是指该广义表展开后所含括号的层数 。
例如,A=(b,c)的深度为 1,B=(A,d)的深度为 2,C=(f,B,h)的深度为 3;
.
（ a） A=(b,c) （ b） B=(a,A) （ c） C=(A,B)
图 5-11 广义表用树或图来表示
BA
C
b ac
A
b c
B
a A
b c
5,广义表的分类
（ 1） 线性表：元素全部是原子的广义表 。
（ 2） 纯表：与树对应的广义表,见图 5-11的 (a)和 (b)
。
（ 3） 再入表：与图对应的广义表 (允许结点共享 ),见图 5-11的 (c)。
（ 4） 递归表：允许有递归关系的广义表,例如
E=(a,E)。
这四种表的关系满足：
递归表?再入表?纯表? 线性表
5.5.2 存储结构由于广义表的元素类型不一定相同,因此,难以用顺序结构存储表中元素,通常采用链接存储方法来存储广义表中元素,并称之为广义链表 。 常见的表示方法
1,单链表表示法即模仿线性表的单链表结构,每个原子结点只有一个链域 link,结点结构是：
其中 atom是标志域,若为 0,则表示为子表,若为 1,则表示为原子,
data/slink域用来存放原子值或子表的指针,link存放下一个元素的地址 。
数据类型描述如下：
#define elemtype char
struct node1
{ int atom;
struct node1 *link;
union
{
struct node1 *slink;
elemtype data;
} ds;
a t o m d a t a / s l i n k l i n k
例如,设 L=(a,b)
A=(x,L)=(x,(a,b))
B=(A,y)=((x,(a,b)),y)
C=(A,B)=((x,(a,b)),((x,(a,b)),y))
可用如图 5-12的结构描述广义表 C,设头指针为 hc。
用此方法存储有两个缺点：其一,在某一个表 (或子表 )中开始处插入或删除一个结点,修改的指针较多,耗费大量时间；其二,删除一个子表后,它的空间不能很好地回收 。
hc
A B
A
L
1 y ^
0 ^
0 ^
0
0
1 x
1 a 1 b ^
图 5-12 广义表的单链表表示法
2,双链表表示法每个结点含有两个指针及一个数据域,每个结点的结构如下：
其中,link1指向该结点子表,link2指向该结点后继 。
数据类型描述如下：
struct node2
{ elemtype data;
struct node2 *link1,*link2;
}
例如,对图 5-12用单链表表示的广义表 C,可用如图 5-13所示的双链表方法表示
。
图 5-13 广义表的双链表表示法
l i n k 1 d at a l i n k 2
hc
^ y ^
^ b ^
L ^
^ a
x
A
B ^A
5.5.3 基本运算广义表有许多运算,现仅介绍如下几种：
1,求广义表的深度 depth(LS)
假设广义表以刚才的单链表表示法作存储结构,则它的深度可以递归求出 。
即广义表的深度等于它的所有子表的最大深度加 1,设 dep表示任一子表的深度
,max表示所有子表中表的最大深度,则广义表的深度为,depth=max+1,算法描述如下：
int depth(struct node1 *LS)
{
int max=0,dep;
while(LS!=NULL)
{ if(LS->atom==0) //有子表
{ dep=depth(LS->ds.slink);
if(dep>max) max=dep;
}
LS=LS->link;
}
return max+1;
}
该算法的时间复杂度为 O(n)。
2,广义表的建立 creat(LS)
假设广义表以单链表的形式存储,广义表的元素类型 elemtype 为字符型 char,广义表由键盘输入,假定全部为字母,输入格式为：元素之间用逗号分隔,表元素的起止符号分别为左,右圆括号,空表在其圆括号内使用一个,#”字符表示,最后使用一个分号作为整个广义表的结束 。
本章小结
1,多维数组在计算机中有两种存放形式：行优先和列优先 。
2,行优先规则是左边下标变化最慢,右边下标变化最快,右边下标变化一遍,与之相邻的左边下标才变化一次 。
3,列优先规则是右边下标变化最慢,左边下标变化最快,左边下标变化一遍,与之相邻的右边下标才变化一次 。
4,对称矩阵关于主对角线对称 。 为节省存储单元,可以进行压缩存储,对角线以上的元素和对角线以下的元素可以共用存储单元,故 n?n
的对称矩阵只需 个存储单元即可 。
5,三角矩阵有上三角矩阵和下三角矩阵之分,为节省内存单元,可以采用压缩存储,n?n的三角矩阵进行压缩存储时,只需 +1个存储单元即可 。
6,稀疏矩阵的非零元排列无任何规律,为节省内存单元,进行压缩存储时,可以采用三元组表示方法,即存储非零元素的行号,列号和值 。 若干个非零元有若干个三元组,若干个三元组称为三元组表 。
7,广义表为线性表的推广,里面的元素可以为原子,也可以为子表
,故广义表的存储采用动态链表较方便 。
1,按行优先存储方式,写出三维数组 A[3][2][4]在内存中的排列顺序及地址计算公式 （ 假设每个数组元素占用 L个字节的内存单元,
a[0][0][0]的内存地址为 Loc(a[0][0][0])） 。
2,按列优先存储方式,写出三维数组 A[3][2][4]在内存中的排列顺序及地址计算公式 （ 假设每个数组元素占用 L个字节的内存单元,
a[0][0][0]的内存地址为 Loc(a[0][0][0])） 。,
3,设有上三角矩阵 An?n,它的下三角部分全为 0,将其上三角元素按行优先存储方式存入数组 B[m]中 (m足够大 ),使得 B[k]=a[i][j],且有
k=f1(i)+f2(j)+c。 试推出函数 f1,f2及常数 c（ 要求 f1和 f2中不含常数项
） 。
4,若矩阵 Am?n中的某个元素 A[i][j]是第 i行中的最小值,同时又是第 j
列中的最大值,则称此元素为该矩阵中的一个马鞍点 。 假设以二维数组存储矩阵 Am?n,试编写求出矩阵中所有马鞍点的算法,并分析你的算法在最坏情况下的时间复杂度 。
5,试写一个算法,查找十字链表中某一非零元素 x。
习题五
6,给定矩阵 A如下,写出它的三元组表和十字链表 。
7,对上题的矩阵,画出它的带行指针的链表,并给出算法来建立它 。
8,试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法 。
9,给定一个稀疏矩阵如下：
用快速转置实现该稀疏矩阵的转置,写出转置前后的三元组表及开始的每一列第一个非零元的位置 pot[col]的值 。
1 0 0 0 0
0 0 2 3 0
A = 0 4 0 0 5
0 0 0 0 0
0 0 0 0 6
0860078065
99000000
0000400
008833061
0000000
2008500
00700230
09000011?
10,广义表是线性结构还是非线性结构?为什么?
11,求下列广义表的运算的结果
（ 1） head((p,h,w))
（ 2） tail ((b,k,p,h))
（ 3） head(((a,b),(c,d)))
（ 4） tail (((b),(c,d)))
（ 5） head (tail(((a,b),(c,d))))
（ 6） tail (head (((a,b),(c,d))))
（ 7） head (tail (head(( (a,d),(c,d)))))
（ 8） tail (head (tail (((a,b),(c,d)))))
12,画出下列广义表的图形表示
（ 1） A(b,(A,a,C(A)),C(A))
（ 2） D(A( ),B(e),C(a,L(b,c,d)))
13,画出第 12题的广义表的单链表表示法和双链表表示法 。
1 多维数组
2 多维数组的存储结构
3 特殊矩阵及其压缩存储
4 稀疏矩阵
5 广义表本章小结本章学习导读本章主要介绍多维数组的概念及在计算机中的存放,特殊矩阵的压缩存储及相应运算,广义表的概念和存储结构及其相关运算的实现 。 通过本章学习,要求掌握如下内容：
1,多维数组的定义及在计算机中的存储表示；
2,对称矩阵,三角矩阵,对角矩阵等特殊矩阵在计算机中的压缩存储表示及地址计算公式；
3,稀疏矩阵的三元组表示及转置算法实现；
4,稀疏矩阵的十字链表表示及相加算法实现；
5,广义表存储结构表示及基本运算 。
5.1 多维数组
5.1.1 多维数组的概念数组是大家都已经很熟悉的一种数据类型,几乎所有高级语言程序设计中都设定了数组类型 。 在此,我们仅简单地讨论数组的逻辑结构及在计算机内的存储方式
。
1,一维数组一维数组可以看成是一个线性表或一个向量 （ 第 2章已经介绍 ）,它在计算机内是存放在一块连续的存储单元中,适合于随机查找 。 这在第 2章的线性表的顺序存储结构中已经介绍 。
2,二维数组二维数组可以看成是向量的推广 。 例如,设 A是一个有 m行 n列的二维数组,则 A
可以表示为：
a 00 a 01 …… a 0n - 1
a 10 a 11 …… a 1n - 1
…………………………,
A=
a m - 1 0 a m - 1 1 …… a m - 1 n - 1
在此,可以将二维数组 A看成是由 m个行向量 [X0,X1,…,Xm-1]T组成,
其中,Xi=( ai0,ai1,…,,ain-1),0≤i≤m-1；也可以将二维数组 A看成是由 n
个列向量 [y0,y1,……,yn-1]组成,其中 yi=(a0i,a1i,…,.,am-1i),0≤i≤n-1。
由此可知二维数组中的每一个元素最多可有两个直接前驱和两个直接后继 （ 边界除外 ）,故是一种典型的非线性结构 。
3,多维数组同理,三维数组最多可有三个直接前驱和三个直接后继,三维以上数组可以作类似分析 。 因此,可以把三维以上的数组称为多维数组,多维数组可有多个直接前驱和多个直接后继,故多维数组是一种非线性结构 。
5.1.2 多维数组在计算机内的存放怎样将多维数组中元素存入到计算机内存中呢？ 由于计算机内存结构是一维的 （ 线性的 ）,因此,用一维内存存放多维数组就必须按某种次序将数组元素排成一个线性序列,然后将这个线性序列顺序存放在存储器中,具体实现方法在下一节介绍 。
5.2 多维数组的存储结构由于数组一般不作插入或删除操作,也就是说,一旦建立了数组,
则结构中的数组元素个数和元素之间的关系就不再发生变动,即它们的逻辑结构就固定下来了,不再发生变化 。 因此,采用顺序存储结构表示数组是顺理成章的事了 。 本章中,仅重点讨论二维数组的存储,三维及三维以上的数组可以作类似分析 。
多维数组的顺序存储有两种形式 。
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 特殊矩阵及其压缩存储矩阵是一个二维数组,它是很多科学与工程计算问题中研究的数学对象 。 矩阵可以用行优先或列优先方法顺序存放到内存中,但是,当矩阵的阶数很大时将会占较多存储单元 。 而当里面的元素分布呈现某种规律时,这时,从节约存储单元出发,可考虑若干元素共用一个存储单元,即进行压缩存储 。 所谓压缩存储是指：为多个值相同的元素只分配一个存储空间,值为零的元素不分配空间 。 但是压缩存储时,节约了存储单元,但怎样在压缩后找到某元素呢？ 因此还必须给出压缩前的下标和压缩后下标之间变换公式,才能使压缩存储变得有意义 。
1,对称矩阵若一个 n阶方阵 A中元素满足下列条件：
aij=aji 其中 0 ≤i,j≤n-1,则称 A为对称矩阵 。
例如,图 5-1是一个 3*3的对称矩阵 。
5.3.1 特殊矩阵
2,三角矩阵
（ 1） 上三角矩阵即矩阵上三角部分元素是随机的,而下三角部分元素全部相同 （ 为某常数 C） 或全为 0,具体形式见图 5-2（ a） 。
图 5-1 一个对称矩阵
A=
643
452
321
（ 2） 下三角矩阵即矩阵的下三角部分元素是随机的,而上三角部分元素全部相同 （ 为某常数 C）
或全为 0,具体形式见图 5-2（ b） 。
（ a） 上三角矩阵 （ b） 下三角矩阵图 5-2 三角矩阵
111110
1110
00
.,,
.,,.,,.,,.,,
.,,
.,,
nnnn aaa
caa
cca
11
1111
100100
.,,.,,.,,.,,
.,,
.,,
nn
n
n
accc
aac
aaa
3,对角矩阵若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中,区域外的值全为 0,则称为对角矩阵 。 常见的有三对角矩阵,五对角矩阵,七对角矩阵等 。
例如,图 5-3为 7× 7的三对角矩阵 （ 即有三条对角线上元素非 0） 。
图 5-3 一个 7× 7的三对角矩阵
6665
565554
454443
343332
232221
121110
0100
00000
0000
0000
0000
0000
0000
00000
aa
aaa
aaa
aaa
aaa
aaa
aa
5.3.2 压缩存储
11121110
222120
1110
00
...
...............
nnnnn
aaaa
aaa
aa
a
（ a）一个下三角矩阵
（ b）下三角矩阵的压缩存储形式矩阵及用下三角压缩存储图 5-4 对称
a 00 a 1 0 a 11 a 20 a 2 1 a 22 a 30 a 31 …… a n -1 n -3 a n -1 n -2 a n -1 n -1
0 1 2 3 4 5 6 7 …… 2 )1(?nn - 3 2 )1(?nn - 2 2 )1(?nn - 1
3,对角矩阵我们仅讨论三对角矩阵的压缩存储,五对角矩阵,七对角矩阵等读者可以作类似分析 。
在一个 n?n的三对角矩阵中,只有 n+n-1+n-1个非零元素,故只需
3n-2个存储单元即可,零元已不占用存储单元 。
故可将 n?n三对角矩阵 A压缩存放到只有 3n-2个存储单元的 s向量中
，假设仍按行优先顺序存放，
s[k]与 a[i][j]的对应关系为：
3i或 3j 当 i=j
k= 3i+1或 3j-2 当 i=j-1
3i-1 或 3j+2 当 i=j+1
5.4 稀疏矩阵在上节提到的特殊矩阵中,元素的分布呈现某种规律,故一定能找到一种合适的方法,将它们进行压缩存放 。 但是,在实际应用中
,我们还经常会遇到一类矩阵：其矩阵阶数很大,非零元个数较少
,零元很多,但非零元的排列没有一定规律,我们称这一类矩阵为稀疏矩阵 。
按照压缩存储的概念,要存放稀疏矩阵的元素,由于没有某种规律,除存放非零元的值外,还必须存储适当的辅助信息,才能迅速确定一个非零元是矩阵中的哪一个位置上的元素 。 下面将介绍稀疏矩阵的几种存储方法及一些算法的实现 。
5.4.1 稀疏矩阵的存储
1,三元组表在压缩存放稀疏矩阵的非零元同时,若还存放此非零元所在的行号和列号,
则称为三元组表法,即称稀疏矩阵可用三元组表进行压缩存储,但它是一种顺序存储 （ 按行优先顺序存放 ） 。 一个非零元有行号,列号,值,为一个三元组,整个稀疏矩阵中非零元的三元组合起来称为三元组表 。
此时,数据类型可描述如下：
#define maxsize 100 /*定义非零元的最大数目 */
struct node /*定义一个三元组 */
{
int i,j; /*非零元行,列号 */
int v; /*非零元值 */
};
struct sparmatrix /*定义稀疏矩阵 */
{
int rows,cols ; /*稀疏矩阵行,列数 */
int terms; /*稀疏矩阵非零元个数 */
node data [maxsize]; /*三元组表 */
};
2,带行指针的链表把具有相同行号的非零元用一个单链表连接起来,稀疏矩阵中的若干行组成若干个单链表,合起来称为带行指针的链表 。 例如,图 5-6的稀疏矩阵 M的带行指针的链表描述形式见图 5-9。
0 1 20
行指针
1 ^
3
4
5
2
0 2 9 ^
2 5 4 ^
5 3 -7 ^
2 0 -3 ^
3 2 24 ^
4 1 18 ^
5 0 15 ^
图 5-9 带行指针的链表
3,十字链表当稀疏矩阵中非零元的位置或个数经常变动时,三元组就不适合于作稀疏矩阵的存储结构,此时,采用链表作为存储结构更为恰当 。
十字链表为稀疏矩阵中的链接存储中的一种较好的存储方法,在该方法中,
每一个非零元用一个结点表示,结点中除了表示非零元所在的行,列和值的三元组 （ i,j,v） 外,还需增加两个链域：行指针域 （ rptr）,用来指向本行中下一个非零元素；列指针域 （ cptr）,用来指向本列中下一个非零元素 。 稀疏矩阵中同一行的非零元通过向右的 rptr指针链接成一个带表头结点的循环链表 。 同一列的非零元也通过 cptr指针链接成一个带表头结点的循环链表 。
因此,每个非零元既是第 i行循环链表中的一个结点,又是第 j列循环链表中的一个结点,相当于处在一个十字交叉路口,故称链表为十字链表 。
另外,为了运算方便,我们规定行,列循环链表的表头结点和表示非零元的结点一样,也定为五个域,且规定行,列,域值为 0(因此,为了使表头结点和表示非零元的表结点不发生混淆,三元组中,输入行和列的下标不能从 0
开始 !!!而必须从 1开始 ),并且将所有的行,列链表和头结点一起链成一个循环链表 。
在行 （ 列 ） 表头结点中,行,列域的值都为 0,故两组表头结点可以共用,
即第 i行链表和第 i列链表共用一个表头结点,这些表头结点本身又可以通过
V域 （ 非零元值域,但在表头结点中为 next,指向下一个表头结点 ） 相链接
。 另外,再增加一个附加结点 （ 由指针 hm指示,行,列域分别为稀疏矩阵的行,列数目 ）,附加结点指向第一个表头结点,则整个十字链表可由 hm
指针惟一确定 。
例如,图 5-6的稀疏矩阵 M的十字链表描述形式见图 5-10。
十字链表的数据类型描述如下：
struct linknode
{ int i,j;
struct linknode *cptr,*rptr;
union vnext /*定义一个共用体 */
{ int v; /*表结点使用 V域,表示非零元值 */
struct linknode next; /*表头结点使用 next域 */
} k; }
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的三元组表（有多少列，则扫描多少遍），这时算法描述如下：
#define maxsize 100
struct node
{
int i,j; /*定义三元组的行,列号 */
int v; /*三元组的值 */
};
struct sparmatrix
{
int rows,cols; /*稀疏矩阵的行,列数 */
int terms; /*稀疏矩阵的非零元个数 */
struct node data[maxsize]; /*存放稀疏矩阵的三元组表 */
};
void transpose(struct sparmatrix a)
{
struct sparmatrix b; /*b为 a的转置 */
int ano,bno=0,col,i;
b.rows=a.cols; b.cols=a.rows;
b.terms=a.terms;
if (b.terms>0)
{
for ( col=0; col<a.cols; col++) /*按列号扫描 */
for( 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;
for( i=0;i<a.terms;i++) /*输出转置后的三元组结果 */
printf("%5d%5d%5d\n",b.data[i].i,b.data[i].j,b.data[i].v);
}
void main()
{
int i;
struct sparmatrix a;
scanf("%d%d%d",&a.rows,&a.cols,&a.terms); /*输入稀疏矩阵的行,列数及非零元的个数 */
for( i=0;i<a.terms;i++)
scanf("%d%d%d",&a.data[i].i,&a.data[i].j,&a.data[i].v); /*输入转置前的稀疏矩阵的三元组 */
for(i=0;i<a.terms;i++)
printf("%5d%5d%5d\n",a.data[i].i,a.data[i].j,a.data[i].v); /*输出转置前的三元组结果 */
transpose( a); /*调用转置算法 */
}
分析这个算法,主要工作在 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[col]=pot[col-1]+num[col-1] 当 1≤col<a.cols
pot[0]=0
为了节省存储单元,记录每一列非零元个数的向量 num可直接放入 pot中,即上面的式子可以改为,pot[col]=pot[col-1]+pot[col],其中 1≤col<acols。
于是可用上面公式进行迭代,依次求出其他列的第一个非零元素转置后在 b.data
中的位置 pot[col]。 例如,对前面图 5-6给出的稀疏矩阵 M,有：
每一列的非零元个数为
pot[1]=2 第 0列非零元个数
pot[2]=2 第 1列非零元个数
pot[3]=2 第 2列非零元个数
pot[4]=1 第 3列非零元个数
pot[5]=0 第 4列非零元个数
pot[6]=1 第 5列非零元个数
pot[7]=0 第 6列非零元个数每一列的第一个非零元的位置为
pot[0]=0 第 0列第一个非零元位置
pot[1]=pot[0]+pot[1]=2第 1列第一个非零元位置
pot[2]=pot[1]+pot[2]=4第 2列第一个非零元位置
pot[3]=pot[2]+pot[3]=6第 3列第一个非零元位置
pot[4]=pot[3]+pot[4]=7第 4列第一个非零元位置
pot[5]=pot[4]+pot[5]=7第 5列第一个非零元位置
pot[6]=pot[5]+pot[6]=8第 6列第一个非零元位置则 M稀疏矩阵的转置矩阵 N的三元组表很容易写出 （ 见图 5-
8）,算法描述如下：
#define maxsize 100
struct node
{
int i,j;
int v;
};
struct sparmatrix
{
int rows,cols;
int terms;
struct node data[maxsize];
};
void fastrans(struct sparmatrix a)
{
struct sparmatrix b;
int pot[maxsize],col,ano,bno,t,i;
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( t=0;t<a.terms;t++) /*求出每一列的非零元个数 */
{
col=a.data[t].j;
pot[col+1]=pot[col+1]+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;
}
}
for( i=0;i<a.terms;i++)
printf("%d\t%d\t%d\n",b.data[i].i,b.data[i].j,b.data[i].v); /*输出转置后的三元组 */
}
void main()
{ struct sparmatrix a;
int i;
scanf("%d%d%d",&a.rows,&a.cols,&a.terms); /*输入稀疏矩阵的行,列数及非零元的个数 */
for( i=0;i<a.terms;i++)
printf("%d\t%d\t%d\n",b.data[i].i,b.data[i].j,b.data[i].v); /*输出转置后的三元组 */
}
void main()
{ struct sparmatrix a;
int i;
scanf("%d%d%d",&a.rows,&a.cols,&a.terms); /*输入稀疏矩阵的行,列数及非零元的个数 */
for( i=0;i<a.terms;i++)
scanf("%d%d%d",&a.data[i].i,&a.data[i].j,&a.data[i].v); /*输入转置前的三元组 */
for(i=0;i<a.terms;i++)
printf("%d\t%d\t%d\n",a.data[i].i,a.data[i].j,a.data[i].v); /*输出转置前的三元组 */
fastrans(a); /*调用快速转置算法 */
}
该算法比按列转置多用了辅助向量空间 pot,但它的时间为四个单循环,故总的时间复杂度为 O(a.cols+a.terms),比按列转置算法效率要高 。
2,稀疏矩阵的相加运算当稀疏矩阵用三元组表进行相加时,有可能出现非零元素的位置变动,这时候,不宜采用三元组表作存储结构,而应该采用十字链表较方便 。
（ 1） 十字链表的建立下面分两步讨论十字链表的建立算法：
第一步,建立表头的循环链表：
依次输入矩阵的行,列数和非零元素个数,m,n和 t。 由于行,列链表共享一组表头结点,因此,表头结点的个数应该是矩阵中行,列数中较大的一个 。 假设用 s 表示个数,即 s=max（ m,n） 。 依次建立总表头结点 （ 由 hm
指针指向 ） 和 s个行,列表头结点,并使用 next域使 s+1个头结点组成一个循环链表,总表头结点的行,列域分别为稀疏矩阵的行,列数目,s个表头结点的行列域分别为 0。 并且开始时,每一个行,列链表均是一个空的循环链表,即 s个行,列表头结点中的行,列指针域 rptr和 cptr均指向头结点本身 。
第二步,生成表中结点：
依次输入 t个非零元素的三元组 （ i,j,v）,生成一个结点,并将它插入到第 i
行链表和第 j列链表中的正确位置上,使第 i个行链表和第 j个列链表变成一个非空的循环链表 。
在十字链表的建立算法中,建表头结点,时间复杂度为 O(s),插入 t个非零元结点到相应的行,列链表的时间复杂度为 O（ t*s）,故算法的总的时间复杂度为 O(t*s)。
（ 2） 用十字链表实现稀疏矩阵相加运算假设原来有两个稀疏矩阵 A和 B,如何实现运算 A=A+B呢？ 假设原来 A
和 B都用十字链表作存储结构,现要求将 B中结点合并到 A中,合并后的结果有三种可能,1） 结果为 aij+bij； 2） aij（ bij=0） ； 3） bij（ aij=0）
。 由此可知当将 B加到 A中去时,对 A矩阵的十字链表来说,或者是改变结点的 v域值 （ aij+bij≠0）,或者不变 （ bij=0）,或者插入一个新结点 （ aij=0）,还可能是删除一个结点 （ aij+bij=0） 。
于是整个运算过程可以从矩阵的第一行起逐行进行 。 对每一行都从行表头出发分别找到 A和 B在该行中的第一个非零元结点后开始比较,然后按上述四种不同情况分别处理之 。 若 pa和 pb分别指向 A和 B的十字链表中行值相同的两个结点,则 4种情况描述为：
1） pa->j=pb->j 且 pa->k.v+pb->k.v≠0,则只要将 aij+bij的值送到 pa所指结点的值域中即可,其他所有域的值都不变化 。
2） pa->j=pb->j且 pa->k.v+pb->k.v=0,则需要在 A矩阵的链表中删除 pa所指的结点 。 这时,需改变同一行中前一结点的 rptr域值,以及同一列中前一结点的 cptr域值 。
3） pa->j<pb->j且 pa->j≠0,则只要将 pa指针往右推进一步,并重新加以比较即可 。
4） pa->j>pb->j或 pa->j=0,则需在 A矩阵的链表中插入 pb所指结点 。
下面将对矩阵 B加到矩阵 A上面的操作过程大致描述如下,
设 ha和 hb分别为表示矩阵 A和 B的十字链表的总表头； ca和 cb分别为指向 A
和 B的行链表的表头结点,其初始状态为,ca=ha->k.next ; cb=hb-
>k.next;
pa和 pb分别为指向 A和 B的链表中结点的指针 。 开始时,pa=ca->rptr;
pb=cb->rptr;然后按下列步骤执行：
① 当 ca->i=0时,重复执行 ②,③,④ 步,否则,算法结束；
② 当 pb->j≠0时,重复执行 ③ 步,否则转第 ④ 步；
③ 比较两个结点的列序号,分三种情形：
a,若 pa->j<pb->j 且 pa->j≠0,则令 pa指向本行下一结点,即 qa=pa; pa=pa-
>rptr; 转 ② 步 ;
b,若 pa->j>pb->j或 pa->j=0,则需在 A中插入一个结点 。 假设新结点的地址为 P,则 A的行表中指针变化为,qa->rptr=p;p->rptr=pa;
同样,A的列表中指针也应作相应改变,用 hl[j]指向本列中上一个结点,则
A的列表中指针变化为,p->cptr=hl[j]->cptr; hl[j]->cptr=p;转第 ② 步；
c,若 pa->j=pb->j,则将 B的值加上去,即 pa->k.v=pa->k.v+bp->k.v,此时若
pa->k.v≠0,则指针不变,否则,删除 A中该结点,于是行表中指针变为：
qa->rptr=pa->rptr; 同时,为了改变列表中的指针,需要先找同列中上一个结点,用 hl[j]表示,然后令 hl[j]->cptr=pa->cptr,转第 ② 步 。
④ 一行中元素处理完毕后,按着处理下一行,指针变化为,ca=ca->k.next;
cb=cb->k.next;转第 1)步 。
5.5 广义表
5.5.1 基本概念广义表是第 2章提到的线性表的推广 。 线性表中的元素仅限于原子项,即不可以再分,而广义表中的元素既可以是原子项,也可以是子表 （ 另一个线性表 ） 。
1,广义表的定义广义表是 n≥0个元素 a1,a2,…,an的有限序列，其中每一个 ai或者是原子，或者是一个子表。广义表通常记为 LS=(a1,a2,…,a n)，其中 LS为广义表的名字,n为广义表的长度,每一个 ai为广义表的元素。但在习惯中，一般用大写字母表示广义表
，小写字母表示原子。
2,广义表举例
（ 1） A=( ),A为空表,长度为 0。
（ 2） B=(a,（ b,c） ),B是长度为 2的广义表,第一项为原子,第二项为子表 。
（ 3） C=(x,y,z),C是长度为 3的广义表,每一项都是原子 。
（ 4） D=(B,C),D是长度为 2的广义表,每一项都是上面提到的子表 。
（ 5） 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。
4,广义表的深度一个广义表的深度是指该广义表展开后所含括号的层数 。
例如,A=(b,c)的深度为 1,B=(A,d)的深度为 2,C=(f,B,h)的深度为 3;
.
（ a） A=(b,c) （ b） B=(a,A) （ c） C=(A,B)
图 5-11 广义表用树或图来表示
BA
C
b ac
A
b c
B
a A
b c
5,广义表的分类
（ 1） 线性表：元素全部是原子的广义表 。
（ 2） 纯表：与树对应的广义表,见图 5-11的 (a)和 (b)
。
（ 3） 再入表：与图对应的广义表 (允许结点共享 ),见图 5-11的 (c)。
（ 4） 递归表：允许有递归关系的广义表,例如
E=(a,E)。
这四种表的关系满足：
递归表?再入表?纯表? 线性表
5.5.2 存储结构由于广义表的元素类型不一定相同,因此,难以用顺序结构存储表中元素,通常采用链接存储方法来存储广义表中元素,并称之为广义链表 。 常见的表示方法
1,单链表表示法即模仿线性表的单链表结构,每个原子结点只有一个链域 link,结点结构是：
其中 atom是标志域,若为 0,则表示为子表,若为 1,则表示为原子,
data/slink域用来存放原子值或子表的指针,link存放下一个元素的地址 。
数据类型描述如下：
#define elemtype char
struct node1
{ int atom;
struct node1 *link;
union
{
struct node1 *slink;
elemtype data;
} ds;
a t o m d a t a / s l i n k l i n k
例如,设 L=(a,b)
A=(x,L)=(x,(a,b))
B=(A,y)=((x,(a,b)),y)
C=(A,B)=((x,(a,b)),((x,(a,b)),y))
可用如图 5-12的结构描述广义表 C,设头指针为 hc。
用此方法存储有两个缺点：其一,在某一个表 (或子表 )中开始处插入或删除一个结点,修改的指针较多,耗费大量时间；其二,删除一个子表后,它的空间不能很好地回收 。
hc
A B
A
L
1 y ^
0 ^
0 ^
0
0
1 x
1 a 1 b ^
图 5-12 广义表的单链表表示法
2,双链表表示法每个结点含有两个指针及一个数据域,每个结点的结构如下：
其中,link1指向该结点子表,link2指向该结点后继 。
数据类型描述如下：
struct node2
{ elemtype data;
struct node2 *link1,*link2;
}
例如,对图 5-12用单链表表示的广义表 C,可用如图 5-13所示的双链表方法表示
。
图 5-13 广义表的双链表表示法
l i n k 1 d at a l i n k 2
hc
^ y ^
^ b ^
L ^
^ a
x
A
B ^A
5.5.3 基本运算广义表有许多运算,现仅介绍如下几种：
1,求广义表的深度 depth(LS)
假设广义表以刚才的单链表表示法作存储结构,则它的深度可以递归求出 。
即广义表的深度等于它的所有子表的最大深度加 1,设 dep表示任一子表的深度
,max表示所有子表中表的最大深度,则广义表的深度为,depth=max+1,算法描述如下：
int depth(struct node1 *LS)
{
int max=0,dep;
while(LS!=NULL)
{ if(LS->atom==0) //有子表
{ dep=depth(LS->ds.slink);
if(dep>max) max=dep;
}
LS=LS->link;
}
return max+1;
}
该算法的时间复杂度为 O(n)。
2,广义表的建立 creat(LS)
假设广义表以单链表的形式存储,广义表的元素类型 elemtype 为字符型 char,广义表由键盘输入,假定全部为字母,输入格式为：元素之间用逗号分隔,表元素的起止符号分别为左,右圆括号,空表在其圆括号内使用一个,#”字符表示,最后使用一个分号作为整个广义表的结束 。
本章小结
1,多维数组在计算机中有两种存放形式：行优先和列优先 。
2,行优先规则是左边下标变化最慢,右边下标变化最快,右边下标变化一遍,与之相邻的左边下标才变化一次 。
3,列优先规则是右边下标变化最慢,左边下标变化最快,左边下标变化一遍,与之相邻的右边下标才变化一次 。
4,对称矩阵关于主对角线对称 。 为节省存储单元,可以进行压缩存储,对角线以上的元素和对角线以下的元素可以共用存储单元,故 n?n
的对称矩阵只需 个存储单元即可 。
5,三角矩阵有上三角矩阵和下三角矩阵之分,为节省内存单元,可以采用压缩存储,n?n的三角矩阵进行压缩存储时,只需 +1个存储单元即可 。
6,稀疏矩阵的非零元排列无任何规律,为节省内存单元,进行压缩存储时,可以采用三元组表示方法,即存储非零元素的行号,列号和值 。 若干个非零元有若干个三元组,若干个三元组称为三元组表 。
7,广义表为线性表的推广,里面的元素可以为原子,也可以为子表
,故广义表的存储采用动态链表较方便 。
1,按行优先存储方式,写出三维数组 A[3][2][4]在内存中的排列顺序及地址计算公式 （ 假设每个数组元素占用 L个字节的内存单元,
a[0][0][0]的内存地址为 Loc(a[0][0][0])） 。
2,按列优先存储方式,写出三维数组 A[3][2][4]在内存中的排列顺序及地址计算公式 （ 假设每个数组元素占用 L个字节的内存单元,
a[0][0][0]的内存地址为 Loc(a[0][0][0])） 。,
3,设有上三角矩阵 An?n,它的下三角部分全为 0,将其上三角元素按行优先存储方式存入数组 B[m]中 (m足够大 ),使得 B[k]=a[i][j],且有
k=f1(i)+f2(j)+c。 试推出函数 f1,f2及常数 c（ 要求 f1和 f2中不含常数项
） 。
4,若矩阵 Am?n中的某个元素 A[i][j]是第 i行中的最小值,同时又是第 j
列中的最大值,则称此元素为该矩阵中的一个马鞍点 。 假设以二维数组存储矩阵 Am?n,试编写求出矩阵中所有马鞍点的算法,并分析你的算法在最坏情况下的时间复杂度 。
5,试写一个算法,查找十字链表中某一非零元素 x。
习题五
6,给定矩阵 A如下,写出它的三元组表和十字链表 。
7,对上题的矩阵,画出它的带行指针的链表,并给出算法来建立它 。
8,试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法 。
9,给定一个稀疏矩阵如下：
用快速转置实现该稀疏矩阵的转置,写出转置前后的三元组表及开始的每一列第一个非零元的位置 pot[col]的值 。
1 0 0 0 0
0 0 2 3 0
A = 0 4 0 0 5
0 0 0 0 0
0 0 0 0 6
0860078065
99000000
0000400
008833061
0000000
2008500
00700230
09000011?
10,广义表是线性结构还是非线性结构?为什么?
11,求下列广义表的运算的结果
（ 1） head((p,h,w))
（ 2） tail ((b,k,p,h))
（ 3） head(((a,b),(c,d)))
（ 4） tail (((b),(c,d)))
（ 5） head (tail(((a,b),(c,d))))
（ 6） tail (head (((a,b),(c,d))))
（ 7） head (tail (head(( (a,d),(c,d)))))
（ 8） tail (head (tail (((a,b),(c,d)))))
12,画出下列广义表的图形表示
（ 1） A(b,(A,a,C(A)),C(A))
（ 2） D(A( ),B(e),C(a,L(b,c,d)))
13,画出第 12题的广义表的单链表表示法和双链表表示法 。
