数据结构第五章：数组

Abstract: 数组。

5.1 多维数组

数组与广义表：数据元素仍为表。本章讨论多维数组的逻辑结构和存储结构、特殊矩阵、矩阵的压缩存储、广义表的逻辑结构和存储结构等。

5.1.1 数组的逻辑结构

数组：可看做是线性表的推广；数组作为一种数据结构其特点是结构中元素本身可具有的某种结构的数据，但属于同一数据类型。如：

• 一维数组可以看作一个线性表
• 二维数组可以看作“数据元素是一维数组”的一维数组
• 三维数组可以看作“数据元素是二维数组”的一维数组，依此类推

m 行n列的二维数组：

数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识，因此，在数组上不能做插入、删除数据元素的操作。通常在各种高级语言中数组一旦被定义，每一维的大小及上下界都不能改变。在数组中通常做下面两种操作：

• (1) 取值操作：给定一组下标，读其对应的数据元素。
• (2) 赋值操作：给定一组下标，存储或修改与其相对应的数据元素。

5.1.2 数组的内存映像

数组的存储表示：数组在内存被映象为向量，即用向量作为数组的一种存储结构，这是因为内存的地址空间是一维的，数组的行列固定后，通过一个映象函数，则可根据数组元素的下标得到它的存储地址。

对于一维数组：按下标顺序分配

对多维数组：要把它的元素映象存储在一维存储器中，一般有两种存储方式：

• 以行为主序的顺序存放：如BASIC、PASCAL、COBOL、C 等程序设计语言中用的是以行为主的顺序分配，即**一行分配完了接着分配下一行。
• 以列为主序（先列后行）的顺序存放：如FORTRAN 语言中，用的是以列为主序的分配顺序，即一列一列地分配。

以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，…，从右向左，最后是左下标。以列为主序分配的规律恰好相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，…，从左向右，最后是右下标。

如一个2×3 二维数组，逻辑结构可以用图1表示。以行为主序的内存映象如图2.1，分配顺序为：a11 ，a12 ，a13 ，a21 ，a22 ，a23 ; 以列为主序的分配顺序为：a11 ，a21 ，a12 ，a22 ，a13 ，a23 ; 它的内存映象如图2.2所示。

设有m×n 二维数组Amn，下面我们看按元素的下标求其地址的计算：
以“以行为主序”的分配为例：设数组的基址为LOC(a11)，每个数组元素占据p个地址单元，那么aij 的物理地址可用一线性寻址函数计算：

    LOC(aij) = LOC(a11) + ( (i-1)*n + j-1 ) * p

这是因为数组元素aij 的前面有i-1 行，每一行的元素个数为n，在第i 行中它的前面还有j-1 个数组元素。

在C 语言中，数组中每一维的下界定义为0，则：

    LOC(aij) = LOC(a00) + ( i*n + j ) * p

推广到一般的二维数组：A[c1..d1] [c2..d2]，则aij 的物理地址计算函数为：

    LOC(aij)=LOC(a c1 c2)+( (i- c1) *( d2 - c2 + 1)+ (j- c2) )*p

同理对于三维数组Amnp，即m×n×p 数组，对于数组元素aijk 其物理地址为：

    LOC(aijk)=LOC(a111)+( ( i-1) *n*p+ (j-1)*p +k-1)*p

推广到一般的三维数组：A[c1..d1] [c2..d2] [c3..d3]，则aijk 的物理地址为：

    LOC(i,j)=LOC(a c1 c2 c3)+( (i- c1) *( d2 - c2 + 1)* (d3- c3 + 1)+ (j- c2) *( d3- c3 + 1)+(k- c3))*p

三维数组的逻辑结构和以行为主序的分配示意图如图所示。

例：若矩阵Am×n 中存在某个元素aij 满足：aij 是第i 行中最小值且是第j 列中的最大值，则称该元素为矩阵A 的一个鞍点。试编写一个算法，找出A 中的所有鞍点。

基本思想：在矩阵A中求出每一行的最小值元素，然后判断该元素是否是它所在列的最大值，是则打印出，接着处理下一行。矩阵A用一个二维数组表示。

void saddle( int A[][], int m, int n )
/*m,n 是矩阵A 的行和列*/
{
	int i, j, min;
	for ( i = 0; i < m; i++ )               /*按行处理*/
	{
		min = A[i][0]
		      for ( j = 1; j < n; j++ )
			if ( A[i][j] < min )
				min = A[I][j];
		                                /*找第I 行最小值*/
		for ( j = 0; j < n; j++ )       /*检测该行中的每一个最小值是否是鞍点*/
			if ( A[I][j] == min )
			{
				k = j; p = 0;
				while ( p < m && A[p][j] < min )
					p++;
				if ( p >= m )
					printf( ＂ % d, % d, % d \ n ＂, i, k, min );
			} /* if */
	} /*for i*/
}

时间性能为O(m(n+mn))。

5.2 特殊矩阵的压缩存储—对称矩阵

矩阵结构：二维数组表示很恰当

对称矩阵：

• aij = aji，其中1≤i , j≤n；
• 关于对角线对称，故只需存储上三角或下三角即可
• 【压缩存储】节省存储资源：原来需要n*n 个存储单元，现在只需要n(n+1)/2 个存储单元了，节约了n(n-1)/2个存储单元

如何只存储下三角？

• 对下三角部分以行为主序顺序存储到一个向量中去，在下三角中共有n*(n+1)/2 个元素，因此，不失一般性，设存储到向量SA[n(n+1)/2]中，存储顺序可用下图示意，这样，原矩阵下三角中的某一个元素aij 则具体对应一个sak，下面的问题是要找到k 与i、j 之间的关系。

角中的元素aij，其特点是：i≥j 且1≤i≤n，存储到SA 中后，根据存储原则，它前面有i-1行，共有1+2+…+i-1=i(i-1)/2 个元素，而aij 又是它所在的行中的第j 个，所以在上面的排列顺序中，aij 是第i(i-1)/2+j 个元素，因此它在SA 中的下标k 与i、j 的关系为：

    k=i*(i-1)/2+j-1 (０≤k<n*(n+1)/2 )

若i<j，则aij 是上三角中的元素，因为aij=aji ，这样，访问上三角中的元素aij 时则去访问和它对应的下三角中的aji 即可，因此将上式中的行列下标交换就是上三角中的元素在SA 中的对应关系：

    k=j*(j-1)/2+i-1 (０≤k<n*(n+1)/2 )

综上所述，对于对称矩阵中的任意元素aij，若令I=max(i,j)，J=min(i,j)，则将上面两个式子综合起来得到：

     k=i*(i-1)/2+J-1

5.2 特殊矩阵的压缩存储—三角矩阵

1. 下三角矩阵

下三角矩阵：一共存储n*(n+1)+1 个元素，设存入向量：SA[n(n+1)+1]中，这种的存储方式可节约n(n-1)-1 个存储单元，sak 与aji 的对应关系为：

2.上三角矩阵

类似下三角，以行为主序顺序存储上三角部分，最后存储对角线下方的常量。对于第1 行，存储n 个元素，第2 行存储n-1 个元素，…，第p 行存储(n-p+1)个元素，aij 的前面有i-1 行，共存储：

个元素，而aij 是它所在的行中要存储的第（j-i+1）个；所以，它是上三角存储顺序中的第(i-1)(2n-i+2)/2+(j-i+1)个，因此它在SA中的下标为：k=(i-1)(2n-i+2)/2+j-i。综上， sak 与aji 的对应关系为：

5.2 特殊矩阵的压缩存储—带状矩阵

n 阶矩阵A 称为带状矩阵，如果存在最小正数m ，满足当∣i-j∣≥m 时，aij =0，这时称w=2n-1 为矩阵A 的带宽。如图是一个w=3(m=2)的带状矩阵。带状矩阵也称为对角矩阵。由图可看出，在这种矩阵中，所有非零元素都集中在以主对角线为中心的带状区域中，即除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零(或同一个常数c)。

带状矩阵A也可采用压缩存储：

压缩法1：将A压缩到一个n行w列的二维数组B中，如图，当某行非零元素的个数小于带宽w时，先存放非零元素后补零。则aij映射为b i’j’，映射关系为：

压缩法2：将带状矩阵压缩到向量C中，按以行为主序，顺序存储其非零元素。按其压缩规律，找到相应的映像函数。如当w = 3时，映像函数为：k = 2*i + j - 3；

5.3 稀疏矩阵—稀疏矩阵的三元组表存储

稀疏矩阵：有t个非零元素（t << mn）的mn矩阵。

解决的问题：很多科学管理及工程计算中，常会遇到阶数很高的大型稀疏矩阵。如果按常规分配方法，顺序分配在计算机内，相当浪费内存。

方法：用三元组仅存放非零元素，然后再按某种规律存储这些三元组，目的是节省存储空间。

三元组（i, j, v）:记下非零元素所在的行、列和值。

define SMAX 1024  /*一个足够大的数*/
typedef struct
{
        int i, j;  /*非零元素的行、列*/
        datatype v;  /*非零元素值*/
}SPNode; /*三元组类型*/
{
        int mu,nu,tu; /*矩阵的行、列及非零元素的个数*/
        SPNode data[SMAX];  /*三元组表*/
}SPMatrix;  /*三元组表的存储类型*/

下面讨论这种存储方式下的稀疏矩阵的两种运算：转置和相乘。

1.稀疏矩阵的转置

算法思路：
①A 的行、列转化成B 的列、行；
②在A.data 中依次找第一列的、第二列的、直到最后一列，并将找到的每个三元组的行、列交换后顺序存储到B.data 中即可。

void TransM1( SPMatrix *A )
{
	SPMatrix	*B;
	int		p, q, col;
	B	= malloc( sizeof(SPMatrix) );                   /*申请存储空间*/
	B->mu	= A->nu; B->nu = A->mu; B->tu = A->tu;/*稀疏矩阵的行、列、元素个数*/
	if ( B->tu > 0 )                                        /*有非零元素则转换*/
	{
		q = 0;
		for ( col = 1; col <= (A->nu); col++ )          /*按A 的列序转换*/
			for ( p = 1; p <= (A->tu); p++ )        /*扫描整个三元组表*/
				if ( A->data[p].j == 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;
					q++;
				}
		        /*if*/
	} /*if(B->tu>0)*/
	return(B);      /*返回的是转置矩阵的指针*/
} /*TransM1*/

分析该算法

• 其时间主要耗费在col 和p 的二重循环上，所以时间复杂性为O(n*t)，(设m、n 是原矩阵的行、列，t 是稀疏矩阵的非零元素个数)
• 显然当非零元素的个数t 和mn 同数量级时，算法的时间复杂度为O(mn2)
• 通常存储方式下矩阵转置算法相比，可能节约了一定量的存储空间，但算法的时间性能更差一些。

时间性能差的原因：反复搜索A表。若能直接确定A 中每一三元组在B 中的位置，则对A 的三元组表扫描一次即可。这是可以做到的，因为A 中第一列的第一个非零元素一定存储在B.data[1]，如果还知道第一列的非零元素的个数，那么第二列的第一个非零元素在B.data 中的位置便等于第一列的第一个非零元素在B.data 中的位置加上第一列的非零元素的个数，如此类推，因为A 中三元组的存放顺序是先行后列，对同一行来说，必定先遇到列号小的元素，这样只需扫描一遍A.data 即可。

根据这个想法，需引入两个向量来实现：num[n+1]和cpot[n+1]，num[col]表示矩阵A中第col 列的非零元素的个数（为了方便均从1 单元用起），cpot［col］初始值表示矩阵A中的第col 列的第一个非零元素在B.data 中的位置。于是cpot 的初始值为：

    cpot[1]=1；
    cpot[col]=cpot[col-1]+num[col-1]； 2≤col≤n

如矩阵A的num和cpot的值如下：

依次扫描A.data，当扫描到一个col 列元素时，直接将其存放在B.data 的cpot[col]位置上，cpot[col]加１，cpot[col]中始终是下一个col 列元素在B.data 中的位置。下面按以上思路改进转置算法如下：

SPMatrix * TransM2( SPMatrix *A )
{
	SPMatrix	*B;
	int		i, j, k;
	int		num[n + 1], cpot[n + 1];
	B	= malloc( sizeof(SPMatrix) );           /*申请存储空间*/
	B->mu	= A->nu; B->nu = A->mu; B->tu = A->tu;
/*稀疏矩阵的行、列、元素个数*/
	if ( B->tu > 0 )                                /*有非零元素则转换*/
	{
		for ( i = 1; i <= A->nu; i++ )
			num[i] = 0;
		for ( i = 1; i <= A->tu; i++ )          /*求矩阵A 中每一列非零元素的个数*/
		{
			j = A->data[i].j;
			num[j]++;
		}
		cpot[1] = 1;                            /*求矩阵A 中每一列第一个非零元素在B.data 中的位置*/
		for ( i = 2; i <= A->nu; i++ )
			cpot[i] = cpot[i - 1] + num[i - 1];
		for ( i = 1; i <= (A->tu); i++ )        /*扫描三元组表*/
		{
			j		= A->data[i].j; /*当前三元组的列号*/
			k		= cpot[j];      /*当前三元组在B.data 中的位置*/
			B->data[k].i	= A->data[i].j;
			B->data[k].j	= A->data[i].i;
			B->data[k].v	= A->data[i].v;
			cpot[j]++;
		} /*for i */
	} /*if (B->tu>0)*/
	return(B);                                      /*返回的是转置矩阵的指针*/
} /*TransM2*/

分析这个算法的时间复杂度：这个算法中有四个循环，分别执行n，t，n-1，t 次，在每个循环中，每次迭代的时间是一常量，因此总的计算量是O（n+t）。当然它所需要的存储空间比前一个算法多了两个向量。

2.稀疏矩阵的乘积

已知稀疏矩阵A(m1× n1)和B(m2× n2)，求乘积C(m1× n2)。稀疏矩阵A、B、C 及它们对应的三元组表A.data、B.data、C.data 如图所示。

a11 只有可能和B 中第1 行的非零元素相乘，a12 只有可能和B 中第2 行的非零元素相乘，…，而同一行的非零元是相邻存放的，所以求c11 和c12 同时进行：求a11b11 累加到c11，求a11b12 累加到c12，再求a12b21 累加到c11，再求a12b22 累加到c22.，…，当然只有aik 和bkj(列号与行号相等)且均不为零（三元组存在）时才相乘，并且累加到cij 当中去。

为了运算方便，设一个累加器：datatype temp[n+1]；用来存放当前行中cij 的值，当前行中所有元素全部算出之后，再存放到C.data 中去。

为了便于B.data 中寻找B 中的第k 行第一个非零元素，与前面类似，在此需引入num和rpot 两个向量。num[k]表示矩阵B 中第k 行的非零元素的个数；rpot[k]表示第k 行的第一个非零元素在B.data 中的位置。于是有

            rpot[1]=1
            rpot[k]=rpot[k-1]+num[k-1] 2≤k≤n

矩阵B的num和rpot值：

稀疏矩阵的乘法运算的粗略步骤如下：

1.初始化：清理一些单元，准备按行顺序存放乘积矩阵；

2.求B的num，rpot；

3.做矩阵乘法：将A.data 中三元组的列值与B.data 中三元组的行值相等的非零元素相乘，并将具有相同下标的乘积元素相加。

SPMatrix *MulSMatrix( SPMatrix *A, SPMatrix *B )
/*稀疏矩阵A(m1× n1)和B(m2× n2) 用三元组表存储，求A×B */
{
	SPMatrix	*C;                                     /* 乘积矩阵的指针*/
	int		p, q, i, j, k, r;
	datatype	temp[n + 1];
	int		num[B->nu + 1], rpot[B->nu + 1];
	if ( A->nu != B->mu )
		return(NULL);                                   /*A 的列与B 的行不相等*/
	C	= malloc( sizeof(SPMatrix) );                   /*申请C 矩阵的存储空间*/
	C->mu	= A->mu; C->nu = B->nu;
	if ( A->tu * B->tu == 0 )
	{
		C->tu = 0; return(C);
	}
	for ( i = 1; i <= B->mu; i++ )
		num[i] = 0;                                     /*求矩阵B 中每一行非零元素的个数*/
	for ( k = 1; k <= B->tu; k++ )
	{
		i = B->data[k].i;
		num[i]++;
	}
	rpot[1] = 1;                                            /*求矩阵B 中每一行第一个非零元素在B.data 中的位置*/
	for ( i = 2; i <= B->mu; i++ )
		rpot[i] = rpot[i - 1] + num[i - 1];
	r	= 0;                                            /*当前C 中非零元素的个数*/
	p	= 1;                                            /*指示A.data 中当前非零元素的位置*/
	for ( i = 1; i <= A->mu; i++ )
	{
		for ( j = 1; j <= B->nu; j++ )
			temp[j] = 0;                            /*cij 的累加器初始化*/
		while ( A->data[p].i == i )
			.                                       /*求第i 行的*/
			{ k = A->data[p].j;                     /*A 中当前非零元的列号*/
			  if ( k < B->mu )
				  t = rpot[k + 1];
			  else t = B->tu + 1;                   /*确定B 中第k 行的非零元素在B.data 中的下限位置*/
			  for ( q = rpot[k]; q < t; q++; )      /* B 中第k 行的每一个非零元素*/
			  {
				  j		= B->data[q].j;
				  temp[j]	+= A->data[p].v * B->data[q].v
			  }
			  p++; } /* while */
			for ( j = 1; j <= B->nu; j++ )
				if ( temp[j] )
				{
					r++;;
					C->data[r] = { i, j, temp[j] };
				}
	}       /*for i*/
	C->tu = r;
	return(C);
}               /* MulSMatrix */

分析上述算法的时间性能如下：

• （1）求num 的时间复杂度为O(B->nu+B->tu)；
• （2）求rpot 时间复杂度为O(B->mu)；
• （3）求temp 时间复杂度为O(A->mu*B->nu)；
• （4）求C的所有非零元素的时间复杂度为O(A->tu*B->tu/B->mu)；
• （5）压缩存储时间复杂度为O(A->muB->nu)；所以总的时间复杂度为O(A->muB->nu+(A->tu*B->tu)/B->nu)。

5.3 稀疏矩阵—稀疏矩阵的十字链表存储

三元组：稀疏矩阵顺序存储

• 不便性：在做一些操作（如加法、乘法）时，非零项数目及非零元素的位置会发生变化，这时这种表示十分不便

十字链表：稀疏矩阵的一种链式存储结构，它同样具备链式存储的特点，因此，在某些情况下，采用十字链表表示稀疏矩阵很方便。

一个稀疏矩阵的十字链表：

基本思想：对每个非零元素存储为一个结点，结点由5个域组成，其结构如图。其中：row域存储非零元素的行号，col域存储列号，v域存储本元素的值，right、down是2个指针域。

稀疏矩阵中每一行的非零元素结点按其列号从小到大顺序由right 域链成一个带表头结点的循环行链表，同样每一列中的非零元素按其行号从小到大顺序由down 域也链成一个带表头结点的循环列链表。即每个非零元素aij 既是第i 行循环链表中的一个结点，又是第j 列循环链表中的一个结点。行链表、列链表的头结点的row 域和col 域置0。每一列链表的表头结点的down 域指向该列链表的第一个元素结点，每一行链表的表头结点的right域指向该行表的第一个元素结点。由于各行、列链表头结点的row 域、col 域和v 域均为零，行链表头结点只用right 指针域，列链表头结点只用right 指针域，故这两组表头结点可以合用，也就是说对于第i 行的链表和第i 列的链表可以共用同一个头结点。为了方便地找到每一行或每一列，将每行（列）的这些头结点们链接起来，因为头结点的值域空闲，所以用头结点的值域作为连接各头结点的链域，即第i 行（列）的头结点的值域指向第i+1行（列）的头结点，… ，形成一个循环表。这个循环表又有一个头结点，这就是最后的总头结点，指针HA 指向它。总头结点的row 和col 域存储原矩阵的行数和列数。

因为非零元素结点的值域是datatype 类型，在表头结点中需要一个指针类型，为了使整个结构的结点一致，我们规定表头结点和其它结点有同样的结构，因此该域用一个联合来表示；改进后的结点结构如图。

综上，结点的结构定义如下:

typedef struct node
{ int row, col;
struct node *down , *right;
union v_next
{ datatype v;
struct node *next;
}
} MNode，*MLink;

基于这种存储结构的稀疏矩阵的运算:

1.建立稀疏矩阵A 的十字链表:

首先输入的信息是：m（A 的行数），n（A 的列数），r（非零项的数目），紧跟着输入的是r 个形如（i,j,aij）的三元组。

算法的设计思想是：首先建立每行（每列）只有头结点的空链表，并建立起这些头结点拉成的循环链表；然后每输入一个三元组（i，j，aij），则将其结点按其列号的大小插入到第i 个行链表中去，同时也按其行号的大小将该结点插入到第j 个列链表中去。在算法中将利用一个辅助数组MNode *hd[s+1]; 其中s=max(m , n) , hd [i]指向第i 行(第i 列)链表的头结点。这样做可以在建立链表时随机的访问任何一行（列），为建表带来方便。

算法如下：

MLink CreatMLink( ) /* 返回十字链表的头指针*/
｛
MLink H;
Mnode *p,*q,*hd[s+1];
int i,j,m,n,t;
datatype v;
scanf(“%d,%,%d”,&m,&n,&t);
H=malloc(sizeof(MNode)); /*申请总头结点*/
H->row=m; H->col=n;
hd[0]=H;
for(i=1; i<S; i++)
{ p=malloc(sizeof(MNode)); /*申请第i 个头结点*/
p->row=0; p->col=0;
p->right=p; p->down=p;
hd[i]=p;
hd[i-1]->v_next.next=p;
}
hd[S]->v_next.next=H; /*将头结点们形成循环链表*/
for (k=1;k<=t;k++)
{ scanf (“%d,%d,%d”,&i,&j,&v); /*输入一个三元组，设值为int*/
p=malloc(sizeof(MNode));
p->row=i ; p->col=j; p->v_next.v=v
/*以下是将*p 插入到第i 行链表中去，且按列号有序*/
q=hd[i];
while ( q->right!=hd[i] && (q->right->col)<j ) /*按列号找位置*/
q=q->right;
p->right=q->right; /*插入*/
q->right=p;
/*以下是将*p 插入到第j 行链表中去，且按行号有序*/
q=hd[i];
while ( q->down!=hd[j] && (q->down->row)<i ) /*按行号找位置*/
q=q->down;
p-> down =q-> down; /*插入*/
q-> down =p;
} /*for k*/
return H;
} /* CreatMLink */

上述算法中，建立头结点循环链表时间复杂度为O(S)，插入每个结点到相应的行表和列表的时间复杂度是O(tS)，这是因为每个结点插入时都要在链表中寻找插入位置，所以**总的时间复杂度为O(tS)。该算法对三元组的输入顺序没有要求。如果我们输入三元组时是按以行为主序（或列）输入的，则每次将新结点插入到链表的尾部的，改进算法后，时间复杂度为O(S+t)**。

2.两个十字链表表示的稀疏矩阵的加法

已知两个稀疏矩阵A 和B，分别采用十字链表存储，计算C=A+B，C 也采用十字链表方式存储，并且在A 的基础上形成C。

由矩阵的加法规则知，只有A 和B 行列对应相等，二者才能相加。C 中的非零元素cij 只可能有３种情况：或者是aij+bij，或者是aij (bij=0)，或者是bij (aij=0)，因此当B 加到A 上时，对A 十字链表的当前结点来说，对应下列四种情况：或者改变结点的值（aij+bij≠０），或者不变（bij＝０），或者插入一个新结点（aij＝０），还可能是删除一个结点（aij+bij＝０）。整个运算从矩阵的第一行起逐行进行。对每一行都从行表的头结点出发，分别找到A 和B 在该行中的第一个非零元素结点后开始比较，然后按４种不同情况分别处理。设pa和pb 分别指向A 和B 的十字链表中行号相同的两个结点，４种情况如下：

(1) 若pa->col=pb->col 且pa->v+pb->v≠0，则只要用aij+bij 的值改写pa 所指结点的值域即可。

(2) 若pa->col=pb->col 且pa->v+pb->v=0，则需要在矩阵A 的十字链表中删除pa 所指结点，此时需改变该行链表中前趋结点的right 域，以及该列链表中前趋结点的down 域。

(3) 若pa->col < pb->col 且pa->col≠0（即不是表头结点），则只需要将pa 指针向右推进一步，并继续进行比较。

(4) 若pa->col > pb->col 或pa->col＝0（即是表头结点），则需要在矩阵A 的十字链表中插入一个pb 所指结点。

由前面建立十字链表算法知，总表头结点的行列域存放的是矩阵的行和列，而各行（列）链表的头结点其行列域值为零，当然各非零元素结点的行列域其值不会为零，下面分析的4 种情况利用了这些信息来判断是否为表头结点。

//十字链表表示的稀疏矩阵相加

MLink AddMat (Ha,Hb)
MLink Ha,Hb;
{ Mnode *p,*q,*pa,*pb,*ca,*cb,*《中国知识付费行业发展白皮书2016》;
if (Ha->row!=Hb->row || Ha->col!=Hb->col) return NULL;
ca=Ha->v_next.next; /*ca 初始指向A 矩阵中第一行表头结点*/
cb=Hb->v_next.next; /*cb 初始指向B 矩阵中第一行表头结点*/
do { pa=ca->right; /*pa 指向A 矩阵当前行中第一个结点*/
《中国知识付费行业发展白皮书2016》=ca; /*《中国知识付费行业发展白皮书2016》 是pa 的前驱*/
pb=cb->right; /*pb 指向B 矩阵当前行中第一个结点*/
while (pb->col!=0) /*当前行没有处理完*/
{
if (pa->col < pb->col && pa->col !=0 ) /*第三种情况*/
{ 《中国知识付费行业发展白皮书2016》=pa;
pa=pa->right;
}
else
if (pa->col > pb->col || pa->col ==0 ) /*第四种情况*/
{p=malloc(sizeof(MNode));
p->row=pb->row; p->col=pb->col; p->v=pb->v;
p->right=pa;《中国知识付费行业发展白皮书2016》->right=p; /* 新结点插入*pa 的前面*/
pa=p;
/*新结点还要插到列链表的合适位置，先找位置，再插入*/
q=Find_JH(Ha,p->col); /*从列链表的头结点找起*/
while(q->down->row!=0 && q->down->row<p->row)
q=q->down;
p->down=q->down; /*插在*q 的后面*/
q->down=p;
pb=pb->right;
} /* if */
else /*第一、二种情况*/
{x= pa->v_next.v+ pb->v_next.v;
if (x==0) /*第二种情况*/
{ 《中国知识付费行业发展白皮书2016》->right=pa->right; ./*从行链中删除*/
/*还要从列链中删除，找*pa 的列前驱结点*/
q= Find_JH (Ha,pa->col); /*从列链表的头结点找起*/
while ( q->down->row < pa->row )
q=q->down;
q->down=pa->down;
free (pa);
pa=《中国知识付费行业发展白皮书2016》;
} /*if (x==0)*/
else /*第一种情况*/
{ pa->v_next.v=x;
《中国知识付费行业发展白皮书2016》=pa;
}
pa=pa->right;
pb=pb->right;
}
} /*while*/
ca=ca->v_next.next; /*ca 指向A 中下一行的表头结点*/
cb=cb->v_next.next; /*cb 指向B 中下一行的表头结点*/
} while (ca->row==0) /*当还有未处理完的行则继续*/
return Ha;
}

为了保持算法的层次，在上面的算法，用到了一个函数findjH。函数Mlink Find_JH(MLink H, int j)的功能是：返回十字链表H 中第j 列链表的头结点指针，很简单。

5.4 广义表—广义表的定义和基本运算

广义表：线性表的推广。也称列表（Lists，用复数形式以示与统称的表List 的区别）

1.广义表的定义和性质

线性表是由n 个数据元素组成的有限序列。其中每个组成元素被限定为单元素，有时这种限制需要拓宽。例如，中国举办的某体育项目国际邀请赛，参赛队清单可采用如下的表示形式：
（俄罗斯，巴西，（国家，河北，四川），古巴，美国，（），日本）

在这个拓宽了的线性表中，韩国队应排在美国队的后面，但由于某种原因未参加，成为空表。国家队、河北队、四川队均作为东道主的参赛队参加，构成一个小的线性表，成为原线性表的一个数据项。这种拓宽了的线性表就是广义表。

广义表（Generalized Lists）是n（n≥0）个数据元素a1，a2，…，ai，…，an 的有序序列，一般记作：

    ls＝（a1，a2，…，ai，…，an）

其中：ls 是广义表的名称，n 是它的长度。每个ai（1≤i≤n）是ls 的成员，它可以是单个元素，也可以是一个广义表，分别称为广义表ls 的单元素和子表。当广义表ls 非空时，称第一个元素a1 为ls 的表头（head），称其余元素组成的表（a2，…，ai，…，an）为ls 的表尾（tail）。显然，广义表的定义是递归的。

通常用大写字母表示广义表，用小写字母表示单个数据元素，广义表用括号括起来，括号内的数据元素用逗号分隔开。下面是一些广义表的例子：

A ＝（）
B ＝（e）
C ＝（a，（b，c，d））
D ＝（A，B，C）
E ＝（a，E）
F ＝（（））

2.广义表的性质

⑴广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表，…。

⑵广义表可以是递归的表。广义表的定义并没有限制元素的递归，即广义表也可以是其自身的子表。例如表E 就是一个递归的表。

⑶广义表可以为其他表所共享。例如，表A、表B、表C 是表D 的共享子表。在D中可以不必列出子表的值，而用子表的名称来引用。

广义表可以看成是线性表的推广，线性表是广义表的特例/子集。

广义表的结构相当灵活，在某种前提下，它可以兼容线性表、数组、树和有向图等各种常用的数据结构。

当二维数组的每行（或每列）作为子表处理时，二维数组即为一个广义表。另外，树和有向图也可以用广义表来表示。由于广义表不仅集中了线性表、数组、树和有向图等常见数据结构的特点，而且可有效地利用存储空间，因此在计算机的许多应用领域都有成功使用广义表的实例。

3.广义表基本运算

重要基本操作：

• 取头Head
• 取尾Tail

对于任意一个非空的列表，其表头可能是单元素也可能是列表，而表尾必为列表。

Head(B) = e Tail(B) = ()
Head（C）＝ a Tail（C）＝（（b，c，d））
Head（D）＝ A Tail（D）＝（B，C）
Head（E）＝ a Tail（E）＝（E）
Head（F）＝（） Tail（F）＝（）

此外，在广义表上可以定义与线性表类似的一些操作，如建立、插入、删除、拆开、连接、复制、遍历等。

CreateLists(ls)：根据广义表的书写形式创建一个广义表ls。
IsEmpty(ls)：若广义表ls 空，则返回True；否则返回False。
Length(ls)：求广义表ls 的长度。
Depth(ls)：求广义表ls 的深度。
Locate(ls，x)：在广义表ls 中查找数据元素x。
Merge(ls1，ls2)：以ls1 为头、ls2 为尾建立广义表。
CopyGList(ls1，ls2)：复制广义表，即按ls1 建立广义表ls2。
Head(ls)：返回广义表ls 的头部。
Tail(ls)：返回广义表的尾部。

5.4 广义表—广义表的存储

• 广义表的数据远古三结构不同，故很难用顺序存储结构表示
• 链式存储结构分配较灵活，易于解决广义表的共享与递归问题，故通常采用链式存储结构来存储广义表，其中每个数据元素可用一个结点表示

按结点形式的不同，广义表的链式存储结构又可以分为不同的两种存储方式。一种称为头尾表示法，另一种称为孩子兄弟表示法。

1.头尾表示法

• 若广义表不空，则可分解为表头 + 表尾
• 一对确定的表头和表尾可唯一确定一个广义表

由于广义表中的数据元素既可能是列表也可能是单元素，相应地在头尾表示法中结点的结构形式有两种：

• 一种是表结点，用以表示列表；
• 另一种是元素结点，用以表示单元素。

在表结点中应该包括一个指向表头的指针和指向表尾的指针；而在元素结点中应该包括所表示单元素的元素值。为了区分这两类结点，在结点中还要设置一个标志域，如果标志为1，则表示该结点为表结点；如果标志为0，则表示该结点为元素结点。其形式定义说明如下：

typedef enum {ATOM, LIST} Elemtag; /*ATOM=0：单元素；LIST=1：子表*/
typedef struct GLNode {
        Elemtag tag; /*标志域，用于区分元素结点和表结点*/
        union { /*元素结点和表结点的联合部分*/
        datatype data; /*data 是元素结点的值域*/
struct {
        struct GLNode *hp, *tp
}ptr; /*ptr 是表结点的指针域，ptr.hp 和ptr.tp 分别*/
/*指向表头和表尾*/
            };
}*GList; /*广义表类型*/

头尾表示法的结点形式:

对于前面所列举的广义表A、B、C、D、E、F，若采用头尾表示法的存储方式，其存储结构如图所示。

从上述存储结构示例中可以看出，采用头尾表示法容易分清列表中单元素或子表所在的层次。例如，在广义表D 中，单元素a 和e 在同一层次上，而单元素b、c、d 在同一层次上且比a 和e 低一层，子表B 和C 在同一层次上。另外，最高层的表结点的个数即为广义表的长度。例如，在广义表D 的最高层有三个表结点，其广义表的长度为3。

2.孩子兄弟表示法

在孩子兄弟表示法中，也有两种结点形式：

• 一种是有孩子结点，用以表示列表；
• 另一种是无孩子结点，用以表示单元素。

在有孩子结点中包括一个指向第一个孩子（长子）的指针和一个指向兄弟的指针；而在无孩子结点中包括一个指向兄弟的指针和该元素的元素值。为了能区分这两类结点，在结点中还要设置一个标志域。如果标志为1，则表示该结点为有孩子结点；如果标志为0，则表示该结点为无孩子结点。其形式定义说明如下：

typedef enum {ATOM, LIST} Elemtag; /*ATOM=0：单元素；LIST=1：子表*/
typedef struct GLENode {
Elemtag tag; /*标志域，用于区分元素结点和表结点*/
union { /*元素结点和表结点的联合部分*/
datatype data; /*元素结点的值域*/
struct GLENode *hp; /*表结点的表头指针*/
};
struct GLENode *tp; /*指向下一个结点*/
}*EGList; /*广义表类型*/

孩子兄弟表示法的结点形式：

对于前面所列举的广义表A、B、C、D、E、F，若采用孩子兄弟表示法的存储方式，其存储结构如图所示。

采用孩子兄弟表示法时，表达式中的左括号“（”对应存储表示中的tag=1 的结点，且最高层结点的tp 域必为NULL。

5.4 广义表—广义表基本操作的实现

以头尾表示法存储广义表，讨论广义表的有关操作的实现。由于广义表的定义是递归的，因此相应的算法一般也都是递归的。

⒈广义表的取头、取尾

GList Head(GList ls)
{
if ls->tag = = 1
then p = ls->hp;
return p;
}
算法5.6

GList Tail(GList ls)
{
if ls->tag = = 1
then p = ls->tp;
return p;
}
算法5.7

⒉建立广义表的存储结构

int Create(GList *ls, char * S)
{ Glist p; char *sub;
if StrEmpty(S) *ls = NULL;
else {
if (!(*ls = (GList)malloc(sizeof(GLNode)))) return 0;
if (StrLength(S) = = 1) {
(*ls)->tag = 0;
(*ls)->data = S;
}
else {
(*ls)->tag = 1;
p = *ls;
hsub =SubStr(S,2,StrLength(S)-2);
do {
sever(sub,hsub);
Create(&(p->ptr.hp), sub);
q = p;
if (!StrEmpty(sub)){
if (!(p = (GList)malloc(sizeof(GLNode)))) return 0;;
p->tag = 1;
q->ptr.tp = p;
}
}while (!StrEmpty(sub));
q->ptr.tp = NULL;
}
}
return 1;
}
算法5.8

int sever(char *str, char *hstr)
{
int n = StrLength(str);
i= 1; k = 0;
for (i = 1, k = 0; i <= n || k != 0; ++i)
{
ch=SubStr(str,i,1);
if (ch = = '(') ++k;
else if (ch = = ')') --k;
}
if (i <= n)
{
hstr =SubStr(str,1,i-2);
str= SubStr(str,i,n-i+1);
}
else {
StrCopy(hstr,str);
ClearStr(str);
}
}
算法5.9

⒊以表头、表尾建立广义表

int Merge(GList ls1,GList ls2, Glist *ls)
{
if (!(*ls = (GList)malloc(sizeof(GLNode)))) return 0;
*ls->tag = 1;
*ls->hp = ls1;
*ls->tp = ls2;
return 1;
}
算法5.10

⒋求广义表的深度

int Depth(GList ls)
{
if (!ls)
return 1; /*空表深度为1*/
if (ls->tag = = 0)
return 0; /*单元素深度为0*/
for (max = 0,p = ls; p; p = p->ptr.tp) {
dep = Depth(p->ptr.hp); /*求以p->ptr.hp 尾头指针的子表深度*/
if (dep > max) max = dep;
}
return max+1; /*非空表的深度是各元素的深度的最大值加1*/
}
算法5.11

⒌复制广义表

int CopyGList(GList ls1, GList *ls2)
{
if (!ls1) *ls2 = NULL; /*复制空表*/
else {
if (!(*ls2 = (Glist)malloc(sizeof(Glnode)))) return 0; /*建表结点*/
(*ls2)->tag = ls1->tag;
if (ls1->tag = = 0) (*ls2)->data = ls1->data; /*复制单元素*/
else {
CopyGList(&((*ls2)->ptr.hp), ls1->ptr.hp); /*复制广义表ls1->ptr.hp 的一个副本*/
CopyGList(&((*ls2)->ptr.tp) , ls1->ptr.tp); /*复制广义表ls1->ptr.tp 的一个副本*/
}
}
return 1;
}
算法5.12