第 6章 数组与广义表数组的定义及其基本操作数组的顺序存储结构矩阵的压缩存储广义表的概念广义表的存储结构表示广义表的运算数组的定义数组,由一组类型相同的数据元素构成的有限序列，
且该有限序列存储在一块地址连续的内存单元中。
一维数组,数组只有一个下标。
二维数组,数组元素都含有两个下标,形如：
二维数组与一维数组的关系,一个二维数组看成是每个数据元素都是相同类型的一维数组的一维数组。
实例,m行 n列的二维数组，可以看成是一个线形表
A=(a1,a2,…,a p) (p=m 或 n) 即：
数组的性质：
数组中的数据元素数目固定。
数组中的数据元素具有相同的数据类型。
数组中的每个数据元素都和一组唯一的下标值对应。
数组是一种随机存储结构，可随机存取数组中的任意数据元素。
随机存,给定一组下标，存一个数据元素到该组下标对应的内存单元中。
随机取,从给定的一组下标所对应的内存单元中取出一个数据元素。
数组的基本操作数组的顺序存储结构数组的顺序存储结构,将数组元素顺序地存放在一片连续的存储单元中 。
二维数组有两种存储方式,以列序为主序（ column
major order）的存储方式，如图 6-2(a)所示和以行序为主序（ row major order）的存储方式，如图 6-2(b)
所示。
地址计算,以行序为主序的存储方式为例：
推广到 n维数组,
LOC[i,j]=LOC[0,0]+(b2?i+j)?L
A0 (1)
A1(1)
An-1 (1)
以列序为主序 以行序为主序数组的顺序存储表示和实现的算法：
typedef struct
{
ElemType *base; /*数组元素初始地址，由初始化操作实现 */
int dim; /*数组的维数 */
int *bounds; /*数组各维的长度，也由初始化操作实现 */
int *const ; /*数组的映象函数常量的初始地址，由初始化操作实现 */
} ;
数组的初始化算法：
Status InitialArray(Array &A,int Adim)
/*如果维数 Adim和数组各维的长度 bounds合法，构造相应的数组 A，并返回 OK值 */
{ /*如果维数 Adim不合法，返回值为 error */
if (Adim<1||Adim> MAXDIM)
return error ;
A.dim=Adim;
A.bounds=(int* )malloc(Adim*sizeof(int));
if (!A.bounds)
exit (overflow);
/*如果各维长度合法，则存入 A.bounds，并求出 A的元素总数 totalnum*/
totalnum=1;
va_start(ap,Adim); /*ap为存放变长参数表信息的数组，
其类型为 va_list*/
for(i=0;i<Adim;++i)
{
A.bounds[i]=va_arg(ap,int);
if(A.bounds[i]<0)
return (underflow);
totalnum* = A.bounds[i];
}
va_end(ap);
A.base=(ElemType*)malloc(dim*sizeof(ElemType));
if(!A.base) exit(overflow);
/*求映象函数的常，把结果存入 A.const [i-1],i=1,…,Adim*/
A.const=(int*)malloc(dim*sizeof(int));
if(!A.const) exit(overflow);
A.const [Adim-1]=1; /*指针的增减以元素的大小为单位 */
for(i=Adim-2;i>=0,i--)
A.const [i]=A.bounds[i+1]*A.const [i+1];
return OK;
}
矩阵的压缩存储特殊矩阵,具有许多相同的元素或者零元素且这些元素在矩阵中的分布有一定的规律的矩阵。
稀疏矩阵,一个矩阵中的非零元素远远少于零元素的矩阵。
压缩存储,是指为多个值相同的元素只分配一个存储空间，而对零元素不分配存储空间，必须能够体现矩阵的逻辑结构。
特殊矩阵的压缩存储对称矩阵的压缩存储：
对称矩阵,若一个 n阶矩阵 A中的元素满足下述关系，
aij=aji 1≤i,j≤n,形如：
对称矩阵存储方式（以行序为主序最为实例）：
以一维数组 one[n(n+1)/2]作为 n阶对称矩阵 A的存储结构，则 one[k]和矩阵中的元素 aij之间存在着下述一一对应的关系：
数据元素和 k之间的关系：
三角矩阵的压缩存储：
上三角矩阵,一个 n阶方阵，它的主对角线的左下方元素均为零元素的矩阵，即当 i>j时,aij=0,其地址 k的计算公式：
下三角矩阵,一个 n阶方阵，它的主对角线的右上方元素均为零元素的矩阵。即当 i<j时,aij=0。
实例：
对角矩阵的压缩存储：
对角矩阵,所有的非零元均集中在以对角线为中心的带状区域中的 n阶方阵。
稀疏矩阵的压缩存储稀疏矩阵,一个阶数较大的矩阵中的非零元素个数相对于矩阵元素的总个数十分小时，形如：
三元组顺序表：
概念,对稀疏矩阵，把它的每个非零元素表示为三元组，并按行号的递增排列，则构成稀疏矩阵的三元组线性表。
三元组顺序表的存储结构定义,
#define MAXSIZE 256 /*矩阵中非零元素个数的最大值
*/
typedef struct
{ int i; /*矩阵元素中非零元的行下标 */
int j; /* 矩阵元素中非零元的列下标 */
ElemType e; /*矩阵元素的值 */
}Triple; /*三元组的定义 */
typedef struct
{ int mu ; /*矩阵的行数 */
int nu ; /*矩阵的列数 */
int tu ; /*矩阵的非零元素个数 */
Triple data[MAXSIZE+1]; /*data为非零元三元组表，
data[0]没有用 */
}Tabletype ; /*三元组顺序表的定义 */
矩阵运算：
矩阵转置运算：
概念,对于一个 m× n 的矩阵 M，它的转置矩阵 N是一个 n× m的矩阵，且 N(i,j)=M(j,i),1≤i≤n,
1≤j≤m,形如：
实现步骤：
将矩阵的行列值相互交换。
将每个三元组中的 i和 j相互调换。
重新排列三元组之间的顺序便可实现矩阵的转置。
稀疏矩阵转置运算的解决方法：
第一种解决方法,是按照 b.data中的三元组的次序，依次在
a.data中找到相应的三元组，然后进行转置。
第二种解决方法,按照 a.data中三元组的次序进行转置，然后将转置后的三元组置入 b中恰当的位置 ；为确定位置，在转置前，应求出 M中每一列中非零元素的个数，和每一列的第一个非零元在 b.data中应有的位置；用 num[col]表示矩阵 M中第 col列中非零元素的个数,cpot[col]表示 M中第 col列的第一个非零元素在 b.data中的正确位置，得出下面一组公式：
cpot[1]=1;
cpot[col]=cpot[col-1]+num[col-1] 2≤col≤a.nu
矩阵相乘运算：
概念,已知 M是 m1× n1的矩阵,N是 m2× n2的矩阵，
当 n1=m2时，定义矩阵 M和 N的乘积为,Q=M× N,Q
是 m1× n2的矩阵。
算法：
for(i=1;i<=m1;i++)
for(j=1;j<=n2;j++)
{
Q[i][j]=0;
for(k=1;k<=n1;k++)
Q[i][j]+=M[i][k]× N[k][j];
}
算法的时间复杂度,O(m1× n1× n2)。
稀疏矩阵乘法的解决方法：
第一种情况,为求 c(即 Q)的值，只需在 a.data(即
M.data) 和 b.data（即 N.data）中找到相应的各对元素，即 a.data中的 j值和 b.data中的 i值相等的各对元素相乘。
为在 b.data 中寻找矩阵 N中第 k行的所有非零元，
附设一个向量 rpos[1..m2];(1)求出矩阵 N中各行的非零元的个数 num[1..m2],(2)求得 N中各行的第一个非零元在 b.data中的位置，则有：
rpos[1]=1
rpos[col]=rpos[col-1]+num[col-1] 2≤col<b.mu
第二种情况,对稀疏矩阵相乘，可按如下步骤来操作：
对 a中每个非零元素 a.data[p](p=1,2,…,a.tu),在
b中找到所有满足条件 a.data[p].j=b.data[q].i的元素 b.data[q]。
求出 a.data[p].e和 b.data[q].e的乘积。
为了便于操作，可以对每一元素增加一个存储累计和的变量，设其初始值为零，然后对数组 a进行扫描，求得相应元素的乘积之后，并累加到适当的求累计和的变量上。
十字链表：
概念,每个非零元素用一个结点表示，此结点有五个域，
其中 i,j和 e三个域分别表示该非零元所在的行、列和非零元的值,right域用来指示同一行中的下一个非零元素，
down域用来指示同一列中的下一个非零元素。行指针域将稀疏矩阵中同一行上的非零元素链接成一个线性链表，列指针将稀疏矩阵中同一列上的非零元素链接成一个线性链表，每一个非零元既是某个行链表上的一个结点，同时又是某个列链表上的一个结点，整个矩阵构成了一个十字交叉的链表，这样的存储结构为十字链表。
实例：
十字链表说明：
typedef struct Node
{
int i； /*非零元的行下标＊ /
int j; /*非零元的列下标 */
Elemtype e; /*非零元的数据元素值 */
struct Node *right; /*非零元所在行表的后继链域 */
struct Node *down; /*非零元所在列表的后继链域 */
}* OLink;
typedef struct Node OLNode;
typedef struct
{
OLink *rhead;/*用于存放行表的头指针 */
OLink *chead;/*用于存放列表的头指针 */
int mu; /*表示矩阵的行数的个数 */
int nu; /*表示矩阵的列数 */
int tu; /*表示矩阵中非零元的个数 */
}CrossList;
广义表的概念广义表,是线性表的一种推广和扩充,允许元素具有独立的类型结构。
广义表一般记作：
LS=(d1,d2,…,d n)
其中,LS是广义表的名称。
n是它的长度。
di可为单个元素，也可为广义表，
分别称为广义 LS的单元素和子表。
当广义表 LS非空时,d1称为 LS的 表头,其余元素组成的表（ d2,d3,…,dn ）称作 LS的 表尾 。
广义表实例：
A=（） — A是一个空表，其长度为零。
B=（ e） — 广义表 B只有一个单元素 e,B的长度为 1。
C=（ a,( b,c ) ) — 广义表 C的长度为 2，两个元素分别为单元素 a和子表（ b,c）。
D=（ A,B,C） — 广义表 D长度为 3，三个元素都是子表。将子表的值代入后，有
D=( ( ),( e ),( a,( b,c ) ) )。
L=( a,L ) — 一个递归的表，它的长度为 2，
第一个元素是单元素，第二个元素是 L自身，
展开后,L相当于一个无限的广义表，即
L=( a,( a,( a,… ) ) ) 。
广义表的重要特点：
广义表的元素可以是子表，而子表的元素还可以是子表。
广义表可用其它广义表来表示。
广义表可以是一个递归的表。
广义表的存储结构表示两种表示结点的结构：
广义表的头尾链存储表示：
结点：
元素结点,用以表示单元素。
表结点,用以表示广义表。
实例：
广义表的扩展线性链表存储表示：
存储结构：
实例：
广义表的运算基本运算,取表头 head(Ls)，取表尾 tail(Ls)。
实例：
head(L)=a,tail(L)=(b)
head(B)=A,tail(B)=(y)
由于 tail(L)是非空表，可继续分解得到：
head(tail(L))=b,tail(tail(L))=()
且该有限序列存储在一块地址连续的内存单元中。
一维数组,数组只有一个下标。
二维数组,数组元素都含有两个下标,形如：
二维数组与一维数组的关系,一个二维数组看成是每个数据元素都是相同类型的一维数组的一维数组。
实例,m行 n列的二维数组，可以看成是一个线形表
A=(a1,a2,…,a p) (p=m 或 n) 即：
数组的性质：
数组中的数据元素数目固定。
数组中的数据元素具有相同的数据类型。
数组中的每个数据元素都和一组唯一的下标值对应。
数组是一种随机存储结构，可随机存取数组中的任意数据元素。
随机存,给定一组下标，存一个数据元素到该组下标对应的内存单元中。
随机取,从给定的一组下标所对应的内存单元中取出一个数据元素。
数组的基本操作数组的顺序存储结构数组的顺序存储结构,将数组元素顺序地存放在一片连续的存储单元中 。
二维数组有两种存储方式,以列序为主序（ column
major order）的存储方式，如图 6-2(a)所示和以行序为主序（ row major order）的存储方式，如图 6-2(b)
所示。
地址计算,以行序为主序的存储方式为例：
推广到 n维数组,
LOC[i,j]=LOC[0,0]+(b2?i+j)?L
A0 (1)
A1(1)
An-1 (1)
以列序为主序 以行序为主序数组的顺序存储表示和实现的算法：
typedef struct
{
ElemType *base; /*数组元素初始地址，由初始化操作实现 */
int dim; /*数组的维数 */
int *bounds; /*数组各维的长度，也由初始化操作实现 */
int *const ; /*数组的映象函数常量的初始地址，由初始化操作实现 */
} ;
数组的初始化算法：
Status InitialArray(Array &A,int Adim)
/*如果维数 Adim和数组各维的长度 bounds合法，构造相应的数组 A，并返回 OK值 */
{ /*如果维数 Adim不合法，返回值为 error */
if (Adim<1||Adim> MAXDIM)
return error ;
A.dim=Adim;
A.bounds=(int* )malloc(Adim*sizeof(int));
if (!A.bounds)
exit (overflow);
/*如果各维长度合法，则存入 A.bounds，并求出 A的元素总数 totalnum*/
totalnum=1;
va_start(ap,Adim); /*ap为存放变长参数表信息的数组，
其类型为 va_list*/
for(i=0;i<Adim;++i)
{
A.bounds[i]=va_arg(ap,int);
if(A.bounds[i]<0)
return (underflow);
totalnum* = A.bounds[i];
}
va_end(ap);
A.base=(ElemType*)malloc(dim*sizeof(ElemType));
if(!A.base) exit(overflow);
/*求映象函数的常，把结果存入 A.const [i-1],i=1,…,Adim*/
A.const=(int*)malloc(dim*sizeof(int));
if(!A.const) exit(overflow);
A.const [Adim-1]=1; /*指针的增减以元素的大小为单位 */
for(i=Adim-2;i>=0,i--)
A.const [i]=A.bounds[i+1]*A.const [i+1];
return OK;
}
矩阵的压缩存储特殊矩阵,具有许多相同的元素或者零元素且这些元素在矩阵中的分布有一定的规律的矩阵。
稀疏矩阵,一个矩阵中的非零元素远远少于零元素的矩阵。
压缩存储,是指为多个值相同的元素只分配一个存储空间，而对零元素不分配存储空间，必须能够体现矩阵的逻辑结构。
特殊矩阵的压缩存储对称矩阵的压缩存储：
对称矩阵,若一个 n阶矩阵 A中的元素满足下述关系，
aij=aji 1≤i,j≤n,形如：
对称矩阵存储方式（以行序为主序最为实例）：
以一维数组 one[n(n+1)/2]作为 n阶对称矩阵 A的存储结构，则 one[k]和矩阵中的元素 aij之间存在着下述一一对应的关系：
数据元素和 k之间的关系：
三角矩阵的压缩存储：
上三角矩阵,一个 n阶方阵，它的主对角线的左下方元素均为零元素的矩阵，即当 i>j时,aij=0,其地址 k的计算公式：
下三角矩阵,一个 n阶方阵，它的主对角线的右上方元素均为零元素的矩阵。即当 i<j时,aij=0。
实例：
对角矩阵的压缩存储：
对角矩阵,所有的非零元均集中在以对角线为中心的带状区域中的 n阶方阵。
稀疏矩阵的压缩存储稀疏矩阵,一个阶数较大的矩阵中的非零元素个数相对于矩阵元素的总个数十分小时，形如：
三元组顺序表：
概念,对稀疏矩阵，把它的每个非零元素表示为三元组，并按行号的递增排列，则构成稀疏矩阵的三元组线性表。
三元组顺序表的存储结构定义,
#define MAXSIZE 256 /*矩阵中非零元素个数的最大值
*/
typedef struct
{ int i; /*矩阵元素中非零元的行下标 */
int j; /* 矩阵元素中非零元的列下标 */
ElemType e; /*矩阵元素的值 */
}Triple; /*三元组的定义 */
typedef struct
{ int mu ; /*矩阵的行数 */
int nu ; /*矩阵的列数 */
int tu ; /*矩阵的非零元素个数 */
Triple data[MAXSIZE+1]; /*data为非零元三元组表，
data[0]没有用 */
}Tabletype ; /*三元组顺序表的定义 */
矩阵运算：
矩阵转置运算：
概念,对于一个 m× n 的矩阵 M，它的转置矩阵 N是一个 n× m的矩阵，且 N(i,j)=M(j,i),1≤i≤n,
1≤j≤m,形如：
实现步骤：
将矩阵的行列值相互交换。
将每个三元组中的 i和 j相互调换。
重新排列三元组之间的顺序便可实现矩阵的转置。
稀疏矩阵转置运算的解决方法：
第一种解决方法,是按照 b.data中的三元组的次序，依次在
a.data中找到相应的三元组，然后进行转置。
第二种解决方法,按照 a.data中三元组的次序进行转置，然后将转置后的三元组置入 b中恰当的位置 ；为确定位置，在转置前，应求出 M中每一列中非零元素的个数，和每一列的第一个非零元在 b.data中应有的位置；用 num[col]表示矩阵 M中第 col列中非零元素的个数,cpot[col]表示 M中第 col列的第一个非零元素在 b.data中的正确位置，得出下面一组公式：
cpot[1]=1;
cpot[col]=cpot[col-1]+num[col-1] 2≤col≤a.nu
矩阵相乘运算：
概念,已知 M是 m1× n1的矩阵,N是 m2× n2的矩阵，
当 n1=m2时，定义矩阵 M和 N的乘积为,Q=M× N,Q
是 m1× n2的矩阵。
算法：
for(i=1;i<=m1;i++)
for(j=1;j<=n2;j++)
{
Q[i][j]=0;
for(k=1;k<=n1;k++)
Q[i][j]+=M[i][k]× N[k][j];
}
算法的时间复杂度,O(m1× n1× n2)。
稀疏矩阵乘法的解决方法：
第一种情况,为求 c(即 Q)的值，只需在 a.data(即
M.data) 和 b.data（即 N.data）中找到相应的各对元素，即 a.data中的 j值和 b.data中的 i值相等的各对元素相乘。
为在 b.data 中寻找矩阵 N中第 k行的所有非零元，
附设一个向量 rpos[1..m2];(1)求出矩阵 N中各行的非零元的个数 num[1..m2],(2)求得 N中各行的第一个非零元在 b.data中的位置，则有：
rpos[1]=1
rpos[col]=rpos[col-1]+num[col-1] 2≤col<b.mu
第二种情况,对稀疏矩阵相乘，可按如下步骤来操作：
对 a中每个非零元素 a.data[p](p=1,2,…,a.tu),在
b中找到所有满足条件 a.data[p].j=b.data[q].i的元素 b.data[q]。
求出 a.data[p].e和 b.data[q].e的乘积。
为了便于操作，可以对每一元素增加一个存储累计和的变量，设其初始值为零，然后对数组 a进行扫描，求得相应元素的乘积之后，并累加到适当的求累计和的变量上。
十字链表：
概念,每个非零元素用一个结点表示，此结点有五个域，
其中 i,j和 e三个域分别表示该非零元所在的行、列和非零元的值,right域用来指示同一行中的下一个非零元素，
down域用来指示同一列中的下一个非零元素。行指针域将稀疏矩阵中同一行上的非零元素链接成一个线性链表，列指针将稀疏矩阵中同一列上的非零元素链接成一个线性链表，每一个非零元既是某个行链表上的一个结点，同时又是某个列链表上的一个结点，整个矩阵构成了一个十字交叉的链表，这样的存储结构为十字链表。
实例：
十字链表说明：
typedef struct Node
{
int i； /*非零元的行下标＊ /
int j; /*非零元的列下标 */
Elemtype e; /*非零元的数据元素值 */
struct Node *right; /*非零元所在行表的后继链域 */
struct Node *down; /*非零元所在列表的后继链域 */
}* OLink;
typedef struct Node OLNode;
typedef struct
{
OLink *rhead;/*用于存放行表的头指针 */
OLink *chead;/*用于存放列表的头指针 */
int mu; /*表示矩阵的行数的个数 */
int nu; /*表示矩阵的列数 */
int tu; /*表示矩阵中非零元的个数 */
}CrossList;
广义表的概念广义表,是线性表的一种推广和扩充,允许元素具有独立的类型结构。
广义表一般记作：
LS=(d1,d2,…,d n)
其中,LS是广义表的名称。
n是它的长度。
di可为单个元素，也可为广义表，
分别称为广义 LS的单元素和子表。
当广义表 LS非空时,d1称为 LS的 表头,其余元素组成的表（ d2,d3,…,dn ）称作 LS的 表尾 。
广义表实例：
A=（） — A是一个空表，其长度为零。
B=（ e） — 广义表 B只有一个单元素 e,B的长度为 1。
C=（ a,( b,c ) ) — 广义表 C的长度为 2，两个元素分别为单元素 a和子表（ b,c）。
D=（ A,B,C） — 广义表 D长度为 3，三个元素都是子表。将子表的值代入后，有
D=( ( ),( e ),( a,( b,c ) ) )。
L=( a,L ) — 一个递归的表，它的长度为 2，
第一个元素是单元素，第二个元素是 L自身，
展开后,L相当于一个无限的广义表，即
L=( a,( a,( a,… ) ) ) 。
广义表的重要特点：
广义表的元素可以是子表，而子表的元素还可以是子表。
广义表可用其它广义表来表示。
广义表可以是一个递归的表。
广义表的存储结构表示两种表示结点的结构：
广义表的头尾链存储表示：
结点：
元素结点,用以表示单元素。
表结点,用以表示广义表。
实例：
广义表的扩展线性链表存储表示：
存储结构：
实例：
广义表的运算基本运算,取表头 head(Ls)，取表尾 tail(Ls)。
实例：
head(L)=a,tail(L)=(b)
head(B)=A,tail(B)=(y)
由于 tail(L)是非空表，可继续分解得到：
head(tail(L))=b,tail(tail(L))=()
