第五章 数组和广义表
一维数组具有线性表的结构，但操作简单，一般不进行插入和删除操作，只定义给定下标读取元素和修改元素的操作
二维数组中，每个数据元素对应一对数组下标，在行方向上和列方向上都存在一个线性关系，即存在两个前驱（前件）和两个后继（后件）。也可看作是以线性表为数据元素的线性表。
n维数组中，每个数据元素对应 n个下标，受 n个关系的制约，其中任一个关系都是线性关系。可看作是数据元素为 n-1维数组的一维数组。
因此，多维数组和广义表是对线性表的扩展：线性表中的数据元素本身又是一个多层次的线性表。
5.1 数组的定义
5.2 数组的顺序表示和实现
5.3 矩阵的压缩存储
5.1 数组的定义
ADT Array{
数据对象,ji=0,…,b i-1,i=1,2,…,n,
D={aj1j2…jn | n(>0)称为数组的维数,bi是数组第 i维的长度,ji是数组元素的第 i维下标,aj1j2…jn ∈ElemSet}
数据关系,R={R1,R2,…,Rn}
Ri={<aj1…ji…jn,aj1…ji+1…jn >| 0≤j k≤b k-1,1≤k≤n
且 k≠i,0≤j i≤b i-2,
aj1…ji…jn,aj1…ji+1…jn ∈D,i=2,…n}
基本操作：
InitArray(&A,n,bound1,…,boundn)
DestroyArray(&A)
Value(A,&e,index1,…,indexn)
Assign(&A,e,index1,…,indexn)
}ADT Array
5.2 数组的顺序表示
多维数组用一维的存储单元存放需约定次序。
PASCAL和 C语言是以行序为主序,FORTRAN以列序为主序。
给定维数和各维长度，数组的存储空间确定。
二维数组中任一元素 aij的存储地址,
Loc(i,j)=Loc(0,0)+(b2*i+j)*L
n维数组：教材 p93
Loc（ j1,j2,…,jn)=Loc(0,0,…,0)+ ∑ciji
其中 cn=L,ci-1=bi*ci,1<i≤n
类型定义
#include <stdarg.h>
#define MAX_ARRAY_DIM 8
typedef struct{
ElemType *base;
int dim;
int *bounds;
int *constants;
}Array;
5.3 矩阵的压缩存储
矩阵一般可用二维数组实现，特殊矩阵采用压缩存储。
压缩存储：为多个值相同的元只分配一个存储空间，
对零元不分配空间。
特殊矩阵：值相同的元素或者零元素在矩阵中的分布有一定规律
稀疏矩阵：非零元较零元少，且分布没有一定规律的矩阵
5.3.1,特殊矩阵
对称矩阵,aij=aji 1≤i,j≤n
压缩存储方法：为每一对对称元分配一个存储空间
将下三角的元素，按行存储到一维数组 sa中
共有 n(n+1)/2个存储单元，
aij在一维数组中的位置 k为,i(i-1)/2+j-1 当 i>=j 否则 j(j-1)/2+i-1
三角矩阵,上（下）三角中的元均为常数 c或 0
压缩存储方法：同上，只存储上（下）三角元素。
下三角,k=i*(i-1)/2+j-1
上三角,k=(2n-i)(i-1)/2+j-1 (按行 )
k=j(j-1)/2+i-1 （按列）
注意,k从零开始,i,j从 1开始
对角矩阵：所有非零元都集中在以主对角线为中心的带状区域中。
压缩方法：压缩存储到一维数组 sa[ ]中，三对角矩阵有 3n-2个元素。
k=2*i+j-3
5.3.2,稀疏矩阵
1,三元组的表示
稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。
t个非零元,t/(m*n)称为稀疏因子 <0.05
用三元组 (i,j,aij)存储行和列的位置，及非零元数值。
0000015
00390170
000000
0006022
2800000
0000110
0910000
B
00002800
00000091
03900000
0006000
017000110
150022000
A
6776
（ 1）稀疏矩阵 (Sparse Matrix)
行数 m = 6,列数 n = 7,非零元素个数 t = 6
0000015
00390170
000000
0006022
2800000
0000110
0910000
B
00002800
00000091
03900000
0006000
017000110
150022000
A
67
76
稀疏矩阵转置矩阵用三元组表表示的稀疏矩阵及其转置行行
(( rr oo ww ))
列列
(( cc oo ll ))
值值
(( vv aa ll uu ee ))
行行
(( rr oo ww ))
列列
(( cc oo ll ))
值值
(( vv aa ll uu ee ))
[0] 11 44 22 22 [0] 11 55 99 11
[1] 11 77 11 55 [1] 22 22 11 11
[2] 22 22 11 11 [2] 33 66 22 88
[3] 22 66 11 77 [3] 44 11 22 22
[4] 33 44 -- 66 [4] 44 33 -- 66
[5] 44 66 33 99 [5] 66 22 11 77
[6] 55 11 99 11 [6] 66 44 33 99
[7] 66 33 22 88 [7] 77 11 11 66
（ 2） 三元组顺序表
#define MAXSIZE 12500 //非零元个数最大值
typedef struct {
int i,j; //行下标和列下标
ElemType e;
} Triple;
typedef struct{
Triple data[MAXSIZE+1]; //非零元三元组表
int mu,nu,tu; //行数、列数、非零元个数
}TSMatrix;
TSMatrix a,b;
所需空间,3*tu+3 若 > mu * nu,则不必用三元组表示
mu,nu,tu
(3)三元组表稀疏矩阵的转置运算
方法：按照 b.data中的三元组的次序，
即 M的列序，依次在 a.data中找到相应的三元组进行转置。
步骤：从 k=1开始依 次扫描找寻所有列号为 k的项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。
其时间复杂度为 O ( a.nu* a.tu )。
例：若矩阵有 200行,200列,10,000个非零元素，总共有 2,000,000次处理。
稀疏矩阵的转置 (算法 5.1)
Status TransposeSMatrix(TSMatrix M,TSMatrix &T)
{ int q,col,p;
T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;
if (T.tu)
{ q=1;
for (col=1;col<=T.mu;++col)
for(p=1;p<=M.tu;++p)
if (M.data[p].j==col)
{ T.data[q].i=M.data[p].j;
T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e;
++q;
}
}
return OK;
}
快速转置算法
方法：按 a.data中三元组的次序进行转置，并将转置后的三元组置入 b中恰当的位置。
建立辅助数组 num和 cpot,num[col]表示矩阵第 col
列中非零元的个数,cpot[col]指示第 col列的第一个非零元素在 b.data中的恰当位置。
按行扫描矩阵三元组表，根据某项的列号，确定它转置后的行号，查 cpot表，按查到的位置直接将该项存入转置三元组表中。
转置时间复杂度为 O(nu+tu+nu+tu)=O(tu)。若矩阵有 200列,10000个非零元素，总共需 10000次处理。
cpot[1]=1
cpot[col]=cpot[col-1]+num[col-1]
col 1 2 3 4 5 6 7
语 义
num
[col]
2 2 2 1 0 1 0 矩阵 A 各列非零元素个数
cpot
[col]
1 3 5 7 8 8 9 矩阵 B 各行开始存放位置稀疏矩阵的快速转置 (算法 5.2)
Status FastTransposeSMatrix(TSMatrix M,TSMatrix &T)
{ T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;
if (T.tu)
{ for (col=1;col<=M.nu;++col) num[col]=0;
for (t=1;t<=M.tu;++t) ++num[M.data[t].j];
cpot[1]=1;
for (col=2;col<=M.nu;++col)
cpot[col]=cpot[col-1]+num[col-1];
for (p=1;p<=M.tu;++p)
{ col=M.data[p].j; q=cpot[col];
T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e; ++cpot[col];
}
}
return OK;
}
2,十字链表
当矩阵中非零元素的 个数 和 位置 经过运算后 变化较大 时，就不宜采用顺序存储结构，而应采用 链式存储结构 来表示三元组。
稀疏矩阵的链接表示采用十字链表,行链表 与 列链表 十字交叉。
行链表与列链表都是 带表头结点的循环链表 。用表头结点表征是第几行，第几列。
元素结点
right—— 指向同一行中下一个非零元素的指针（向右域）
down—— 指向同一列中下一个非零元素的指针（向下域）
表头结点
行表头结点
列表头结点
next用于表示头结点的链接
row col val
down right
col=0 next
right
row=0 next
down
由于行、列表头结点互相不冲突，所以可以合并起来：
总表头结点：
row=0 col=0 next
down right
row col next
类型定义：
typedef struct {
int i,j; //非零元的行下标和列下标
ElemType e;
}Triple;
typedef struct OLNode{ //元素结点
union { Triple triple; OLNode *next};
struct OLNode *right,*down;
//该非零元所在行表和列表的后继链域
}OLNode,*OLink;
OLink M；
稀疏矩阵的十字链表表示的示例
需要辅助结点作链表的表头，同时每个结点要增加两个指针域，所以只有在矩阵较大和较稀疏时才能起到节省空间的效果。
分别用两个一维数组存储行链表的头指针和列链表的头指针，可加快访问速度。
十字链表的类型定义
typedef struct OLNode{ //元素结点
int i,j; //非零元的行和列下标
ElemType e;
struct OLNode *right,*down;
//该非零元所在行表和列表的后继链域
} OLNode,*OLink;
typedef struct {
OLink *rhead,*chead;
//行和列链表头指针数组
int mu,nu,tu;
} CrossList;
十字链表的建立 (算法 5.4)
自学
一维数组具有线性表的结构，但操作简单，一般不进行插入和删除操作，只定义给定下标读取元素和修改元素的操作
二维数组中，每个数据元素对应一对数组下标，在行方向上和列方向上都存在一个线性关系，即存在两个前驱（前件）和两个后继（后件）。也可看作是以线性表为数据元素的线性表。
n维数组中，每个数据元素对应 n个下标，受 n个关系的制约，其中任一个关系都是线性关系。可看作是数据元素为 n-1维数组的一维数组。
因此，多维数组和广义表是对线性表的扩展：线性表中的数据元素本身又是一个多层次的线性表。
5.1 数组的定义
5.2 数组的顺序表示和实现
5.3 矩阵的压缩存储
5.1 数组的定义
ADT Array{
数据对象,ji=0,…,b i-1,i=1,2,…,n,
D={aj1j2…jn | n(>0)称为数组的维数,bi是数组第 i维的长度,ji是数组元素的第 i维下标,aj1j2…jn ∈ElemSet}
数据关系,R={R1,R2,…,Rn}
Ri={<aj1…ji…jn,aj1…ji+1…jn >| 0≤j k≤b k-1,1≤k≤n
且 k≠i,0≤j i≤b i-2,
aj1…ji…jn,aj1…ji+1…jn ∈D,i=2,…n}
基本操作：
InitArray(&A,n,bound1,…,boundn)
DestroyArray(&A)
Value(A,&e,index1,…,indexn)
Assign(&A,e,index1,…,indexn)
}ADT Array
5.2 数组的顺序表示
多维数组用一维的存储单元存放需约定次序。
PASCAL和 C语言是以行序为主序,FORTRAN以列序为主序。
给定维数和各维长度，数组的存储空间确定。
二维数组中任一元素 aij的存储地址,
Loc(i,j)=Loc(0,0)+(b2*i+j)*L
n维数组：教材 p93
Loc（ j1,j2,…,jn)=Loc(0,0,…,0)+ ∑ciji
其中 cn=L,ci-1=bi*ci,1<i≤n
类型定义
#include <stdarg.h>
#define MAX_ARRAY_DIM 8
typedef struct{
ElemType *base;
int dim;
int *bounds;
int *constants;
}Array;
5.3 矩阵的压缩存储
矩阵一般可用二维数组实现，特殊矩阵采用压缩存储。
压缩存储：为多个值相同的元只分配一个存储空间，
对零元不分配空间。
特殊矩阵：值相同的元素或者零元素在矩阵中的分布有一定规律
稀疏矩阵：非零元较零元少，且分布没有一定规律的矩阵
5.3.1,特殊矩阵
对称矩阵,aij=aji 1≤i,j≤n
压缩存储方法：为每一对对称元分配一个存储空间
将下三角的元素，按行存储到一维数组 sa中
共有 n(n+1)/2个存储单元，
aij在一维数组中的位置 k为,i(i-1)/2+j-1 当 i>=j 否则 j(j-1)/2+i-1
三角矩阵,上（下）三角中的元均为常数 c或 0
压缩存储方法：同上，只存储上（下）三角元素。
下三角,k=i*(i-1)/2+j-1
上三角,k=(2n-i)(i-1)/2+j-1 (按行 )
k=j(j-1)/2+i-1 （按列）
注意,k从零开始,i,j从 1开始
对角矩阵：所有非零元都集中在以主对角线为中心的带状区域中。
压缩方法：压缩存储到一维数组 sa[ ]中，三对角矩阵有 3n-2个元素。
k=2*i+j-3
5.3.2,稀疏矩阵
1,三元组的表示
稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。
t个非零元,t/(m*n)称为稀疏因子 <0.05
用三元组 (i,j,aij)存储行和列的位置，及非零元数值。
0000015
00390170
000000
0006022
2800000
0000110
0910000
B
00002800
00000091
03900000
0006000
017000110
150022000
A
6776
（ 1）稀疏矩阵 (Sparse Matrix)
行数 m = 6,列数 n = 7,非零元素个数 t = 6
0000015
00390170
000000
0006022
2800000
0000110
0910000
B
00002800
00000091
03900000
0006000
017000110
150022000
A
67
76
稀疏矩阵转置矩阵用三元组表表示的稀疏矩阵及其转置行行
(( rr oo ww ))
列列
(( cc oo ll ))
值值
(( vv aa ll uu ee ))
行行
(( rr oo ww ))
列列
(( cc oo ll ))
值值
(( vv aa ll uu ee ))
[0] 11 44 22 22 [0] 11 55 99 11
[1] 11 77 11 55 [1] 22 22 11 11
[2] 22 22 11 11 [2] 33 66 22 88
[3] 22 66 11 77 [3] 44 11 22 22
[4] 33 44 -- 66 [4] 44 33 -- 66
[5] 44 66 33 99 [5] 66 22 11 77
[6] 55 11 99 11 [6] 66 44 33 99
[7] 66 33 22 88 [7] 77 11 11 66
（ 2） 三元组顺序表
#define MAXSIZE 12500 //非零元个数最大值
typedef struct {
int i,j; //行下标和列下标
ElemType e;
} Triple;
typedef struct{
Triple data[MAXSIZE+1]; //非零元三元组表
int mu,nu,tu; //行数、列数、非零元个数
}TSMatrix;
TSMatrix a,b;
所需空间,3*tu+3 若 > mu * nu,则不必用三元组表示
mu,nu,tu
(3)三元组表稀疏矩阵的转置运算
方法：按照 b.data中的三元组的次序，
即 M的列序，依次在 a.data中找到相应的三元组进行转置。
步骤：从 k=1开始依 次扫描找寻所有列号为 k的项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。
其时间复杂度为 O ( a.nu* a.tu )。
例：若矩阵有 200行,200列,10,000个非零元素，总共有 2,000,000次处理。
稀疏矩阵的转置 (算法 5.1)
Status TransposeSMatrix(TSMatrix M,TSMatrix &T)
{ int q,col,p;
T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;
if (T.tu)
{ q=1;
for (col=1;col<=T.mu;++col)
for(p=1;p<=M.tu;++p)
if (M.data[p].j==col)
{ T.data[q].i=M.data[p].j;
T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e;
++q;
}
}
return OK;
}
快速转置算法
方法：按 a.data中三元组的次序进行转置，并将转置后的三元组置入 b中恰当的位置。
建立辅助数组 num和 cpot,num[col]表示矩阵第 col
列中非零元的个数,cpot[col]指示第 col列的第一个非零元素在 b.data中的恰当位置。
按行扫描矩阵三元组表，根据某项的列号，确定它转置后的行号，查 cpot表，按查到的位置直接将该项存入转置三元组表中。
转置时间复杂度为 O(nu+tu+nu+tu)=O(tu)。若矩阵有 200列,10000个非零元素，总共需 10000次处理。
cpot[1]=1
cpot[col]=cpot[col-1]+num[col-1]
col 1 2 3 4 5 6 7
语 义
num
[col]
2 2 2 1 0 1 0 矩阵 A 各列非零元素个数
cpot
[col]
1 3 5 7 8 8 9 矩阵 B 各行开始存放位置稀疏矩阵的快速转置 (算法 5.2)
Status FastTransposeSMatrix(TSMatrix M,TSMatrix &T)
{ T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;
if (T.tu)
{ for (col=1;col<=M.nu;++col) num[col]=0;
for (t=1;t<=M.tu;++t) ++num[M.data[t].j];
cpot[1]=1;
for (col=2;col<=M.nu;++col)
cpot[col]=cpot[col-1]+num[col-1];
for (p=1;p<=M.tu;++p)
{ col=M.data[p].j; q=cpot[col];
T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e; ++cpot[col];
}
}
return OK;
}
2,十字链表
当矩阵中非零元素的 个数 和 位置 经过运算后 变化较大 时，就不宜采用顺序存储结构，而应采用 链式存储结构 来表示三元组。
稀疏矩阵的链接表示采用十字链表,行链表 与 列链表 十字交叉。
行链表与列链表都是 带表头结点的循环链表 。用表头结点表征是第几行，第几列。
元素结点
right—— 指向同一行中下一个非零元素的指针（向右域）
down—— 指向同一列中下一个非零元素的指针（向下域）
表头结点
行表头结点
列表头结点
next用于表示头结点的链接
row col val
down right
col=0 next
right
row=0 next
down
由于行、列表头结点互相不冲突，所以可以合并起来：
总表头结点：
row=0 col=0 next
down right
row col next
类型定义：
typedef struct {
int i,j; //非零元的行下标和列下标
ElemType e;
}Triple;
typedef struct OLNode{ //元素结点
union { Triple triple; OLNode *next};
struct OLNode *right,*down;
//该非零元所在行表和列表的后继链域
}OLNode,*OLink;
OLink M；
稀疏矩阵的十字链表表示的示例
需要辅助结点作链表的表头，同时每个结点要增加两个指针域，所以只有在矩阵较大和较稀疏时才能起到节省空间的效果。
分别用两个一维数组存储行链表的头指针和列链表的头指针，可加快访问速度。
十字链表的类型定义
typedef struct OLNode{ //元素结点
int i,j; //非零元的行和列下标
ElemType e;
struct OLNode *right,*down;
//该非零元所在行表和列表的后继链域
} OLNode,*OLink;
typedef struct {
OLink *rhead,*chead;
//行和列链表头指针数组
int mu,nu,tu;
} CrossList;
十字链表的建立 (算法 5.4)
自学
