ADT Array { 数据对象： 数据对象：D＝{aj1,j2,...,ji ,...jN |aji=0,...,bi-1, i=1,2,..,N, 称 N(>0) 为数组的维数，bi为数组第 i 维的长度，ji为数组元素的第i维下标，aj1,...,jN ∈ElemSet } 数据关系： 数据关系：R＝{R1, R2, ..., RN} Ri＝{<aj1 ,...ji ,...jN , aj1 ,...,ji+1,...,jN > | 0≤jk≤bk-1, 1≤k≤N 且k i, 0≤ ≤bi-2, aj1,...,ji,...,jN, aj1,...j+1,...,jN∈D, i=2,...,N }
#define MAXSIZE 100 /* 非零元个数的最大值 */ typedef struct { int i,j; /* 行下标,列下标 */ ElemType e; /* 非零元素值 */ }Triple; typedef struct { Triple data[MAXSIZE+1]; /* 非零元三元组表,data[0]未用 */ int mu,nu,tu; /* 矩阵的行数、列数和非零元个数 */ }TSMatrix;
数组结构的定义： #define MAX_ROW_INDEX 10 #define MAX_COL_INDEX 10 typedef struct { ElemType item[MAX_ROW_INDEX][MAX_COL_INDEX] ; } ARRAY;
给数组元素赋值
void Assign(ARRAY *A,ElemType item,int index1,int index2) { if (index1<0||index1>=MAX_ROW_INDEX|| index2<0||index2>=MAX_COL_INDEX) exit(ERROR); else A->item[index1][index2]=item; }
a
00
（b）下三角矩阵
a
0 n −1
a
01
... ... ... c
a 00 a 10 ... a n − 10
c a 11 ... a n −11
... ... ... ...
c c ... a n −1 n −1
c ... c
a 11 ... c
a 1n −1 ... a
n −1n −1
图5-2 三角矩阵
3．对角矩阵 ． 若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全 为0，则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。 例如，图5-3为7×7的三对角矩阵（即有三条对角线上元素非0）。
wk.baidu.com
a00 a10 0 0 0 0 0
a01 a11 a 21 0 0 0 0
第五章 数组和广义表
从学习利用高级语言编制程序开始，数组是大家 惯用的存储批量数据的工具，前几章讨论的线性结构的 顺序存储结构也都是利用数组来描述的，那么数组本身 又是怎么实现的呢？ 本章的学习目的主要是了解数组类型的特点以及 在高级编程语言中的实现方法。 对于本章讨论的随机稀疏矩阵运算的各个算法主 要是理解问题的处理方法。
通常有两种顺序存储方式：
⑴行优先顺序——将数组元素按行排列，第i+1个行向 量紧接在第i个行向量后面。以二维数组为例，按行 优先顺序存储的线性序列为： a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn 在PASCAL、C语言中，数组就是按行优先顺序存储 的。 ⑵列优先顺序——将数组元素按列向量排列，第j+1个 列向量紧接在第j个列向量之后，A的m*n个元素按列 优先顺序存储的线性序列为： a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm 在FORTRAN语言中，数组就是按列优先顺序存储的。
5.2 数组的顺序表示和实现 由于计算机的内存结构是一维的，因此 用一维内存来表示多维数组，就必须按 某种次序将数组元素排成一列序列，然 后将这个线性序列存放在存储器中。 又由于对数组一般不做插入和删除操 作，也就是说，数组一旦建立，结构中 的元素个数和元素间的关系就不再发生 变化。因此，一般都是采用顺序存储的 方法来表示数组。
以上规则可以推广到多维数组的情况：优先 顺序可规定为先排最右的下标，从右到左， 最后排最左下标：列优先顺序与此相反，先 排最左下标，从左向右，最后排最右下标。
行序演示 列序演示
按上述两种方式顺序存储的序组，只要 知道开始结点的存放地址（即基地址）， 维数和每维的上、下界，以及每个数组元 素所占用的单元数，就可以将数组元素的 存放地址表示为其下标的线性函数。因此， 数组中的任一元素可以在相同的时间内存 取，即顺序存储的数组是一个随机存取结 构。
基本操作： 基本操作： InitArray(&A, n, bound1, ..., boundn) 操作结果：若维数 n 和各维长度合法，则构造相应的数组 A。 DestroyArray(&A) 初始条件：数组 A 已经存在。 操作结果：销毁数组 A。 Value(A, &e, index1, ..., indexn) 初始条件：A 是 n 维数组，e 为元素变量，随后是 n 个下标值。 操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回 OK。 Assign(&A, e, index1, ..., indexn) 初始条件：A 是 n 维数组，e 为元素变量，随后是 n 个下标值。 操作结果：若下标不超界，则将 e 的值赋给A中指定下标的元素。 } ADT Array
（a）一个下三角矩阵
0 1 2 3
4 5
6 7
… …
n(n+1) 2
-3
n(n+1) 2
-2
n(n+1) 2
-1
a00 a10 a11 a20 a21 a22 a30 a31 … …
an-1n-3
an-1n-2
an-1n-1
（b）下三角矩阵的压缩存储形式 矩阵及用下三角压缩存储 图5-4 对称
3．对角矩阵 ． 我们仅讨论三对角矩阵的压缩存储，五对角矩阵，七对角矩阵等 读者可以作类似分析。 在一个n×n的三对角矩阵中，只有n+n-1+n-1个非零元素，故只需 3n-2个存储单元即可，零元已不占用存储单元。 故可将n×n三对角矩阵A压缩存放到只有3n-2个存储单元的s向量中 ，假设仍按行优先顺序存放，
5.3 矩阵及其压缩存储
矩阵是一个二维数组，它是很多科学与工程计算问题中研究的数学对 象。矩阵可以用行优先或列优先方法顺序存放到内存中，但是，当矩 阵的阶数很大时将会占较多存储单元。而当里面的元素分布呈现某种 规律时，这时，从节约存储单元出发，可考虑若干元素共用一个存储 单元，即进行压缩存储。所谓压缩存储是指：为多个值相同的元素只 分配一个存储空间，值为零的元素不分配空间。但是压缩存储时，节 约了存储单元，但怎样在压缩后找到某元素呢？因此还必须给出压缩 前的下标和压缩后下标之间变换公式，才能使压缩存储变得有意义。
5.3.1 特殊矩阵
所谓特殊矩阵就是元素值的排列具有一定规律的矩阵。 常见的这类矩阵有：对称矩阵、下（上）三角矩阵、对角线矩阵等等。
1．对称矩阵 若一个n阶方阵A中元素满足下列条件： aij=aji 其中 0 ≤i, j≤n-1 ，则称A为对称矩阵。 例如，图5-1是一个3*3的对称矩阵。
1
A =
假设二维数组 R[m][n] 中每个数据元素占L个存储地址，并以 LOC(i,j) 表 示下标为 (i,j) 的数据元素的存储地址，则该数组中任何一对下标 (i,j) 对应 的数据元素在"以行为主"的顺序映象中的存储地址为： LOC(i,j) = LOC(0,0) + (ixn+j)xL 在"以列为主"的顺序映象中的存储地址为： LOC(i,j) = LOC(0,0) + (jxm+i)xL 其中 LOC(0,0) 是二维数组中第一个数据元素（下标为(0,0)）的存储 地址，称为数组的 "基地址" 或"基址"。
可以看成是由个行向量组成的向量，也可以看成是 个列向量组成的向量。 在C语言中，一个二维数组类型可以定义为其分 量类型为一维数组类型的一维数组类型，也就是说， typedef elemtype array2[m][n]; 等价于： typedef elemtype array1[n]; typedef array1 array2[m]; 同理，一个维数组类型可以定义为其数据元素为维 数组类型的一维序组类型。 数组一旦被定义，它的维数和维界就不再改变。 因此，除了结构的初始化和销毁之外，数组只有存 取元素和修改元素值的操作。
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.3.2 稀疏矩阵
0 0 3 0 −1 0 −1 − 2 0 0 0 0 0 0 0
0 7 0 0 0 0 0 0 2 0
在上节提到的特殊矩阵中，元素的分布呈现某种规律，故一定能 找到一种合适的方法，将它们进行压缩存放。但是，在实际应用中 ，我们还经常会遇到一类矩阵：其矩阵阶数很大，非零元个数较少 ，零元很多，但非零元的排列没有一定规律，我们称这一类矩阵为 稀疏矩阵。 按照压缩存储的概念，要存放稀疏矩阵的元素，由于没有某种规 律，除存放非零元的值外，还必须存储适当的辅助信息，才能迅速 确定一个非零元是矩阵中的哪一个位置上的元素。下面将介绍稀疏 矩阵的几种存储方法及一些算法的实现。
第m-1列
类似地，假设三维数组 R[p][m][n] 中每个数据元素占 L 个存储地址，并以 LOC(i,j,k) 表示下标为(i,j,k) 的数据元素的存储地址，则该数组中任何一对 下标(i,j,k) 对应的数据元素在"以行为主"的顺序映象中的存储地址为： LOC(i,j,k) = LOC(0,0,0) + (i×m×n + j×n+k)×L 那么以列为主的顺序映象中的存储地址为？
• 5.1 数组的定义 • 5.2 数组的顺序表示和实现（重要） • 5.3 矩阵的压缩存储 • 5.3.1 特殊矩阵（比较重要） • 5.3.2 稀疏矩阵（非常重要） • 5.4 广义表的定义 • 5.5 广义表的存储结构
数组和广义表可看成是一种特殊的线性表，其 特殊在于，表中的元素本身也是一种线性表。
0 a12 a 22 a32 0 0 0
0 0 a 23 a33 a 43 0 0
0 0 0 a34 a 44 a54 0
0 0 0 0 a 45 a55 a65
0 0 0 0 0 a56 a66
图5-3 一个7×7的三对角矩阵
5.3.2 压缩存储
a 00 a10 a 20 ... a n −10 a11 a 21 ... a n −11 a 22 ... a n −12 ... ... ... a n −1n −1
5.1 数组的定义
数组是我们最熟悉的数据类型，在早期的高级 语言中，数组是唯一可供使用的数据类型。由于 数组中各元素具有统一的类型，并且数组元素的 下标一般具有固定的上界和下界，因此，数组的 处理比其它复杂的结构更为简单。多维数组是向 量的推广。例如，二维数组： a11 a12 … a1n a21 a22 … a2n Amn= … … …… am1 am2 … amn
2 5 4
3 4 6
2 3
图5-1 一个对称矩阵
2．三角矩阵 ． （1）上三角矩阵 即矩阵上三角部分元素是随机的，而下三角部分元素全部相同（为某常数C）或 全为0，具体形式见图5-2（a）。 （2）下三角矩阵 即矩阵的下三角部分元素是随机的，而上三角部分元素全部相同（为某常数C） 或全为0，具体形式见图5-2（b）。 （a）上三角矩阵
稀疏矩阵的存储
1．三元组表 ． 在压缩存放稀疏矩阵的非零元同时，若还存放此非零元所在的行号和列号， 则称为三元组表法，即称稀疏矩阵可用三元组表进行压缩存储，但它是一种 顺序存储（按行优先顺序存放）。一个非零元有行号、列号、值，为一个三 元组，整个稀疏矩阵中非零元的三元组合起来称为三元组表。 此时，数据类型可描述如下：
a00 a0 1 ... a0,n 1
a10
a1 1
...
a1 ,n1
...
...
am1 ,0
am1 ,1
...
am-1,n 1
第0行
a00 a10 ... am-1,
0
第1行
a01 a11 ... am-1,
1
第m-1行
... ... a0,n-1 a1,n-1 ... am-1,n
-1
第0列
第1列
