第五章 数组和特殊矩阵 数组及其存储结构 特殊矩阵的压缩存储 对称矩阵的压缩存储 三角矩阵的压缩存储
对角矩阵的压缩存储 稀疏矩阵的压缩存储 数组的定义 数组是n(n>=)个相同数据类型数据元素构成的有限序列。
数组可分为一维数组和多维数组。一维数组可看成是一种线性表。 二维数组及多维数组可以看成是线性表的推广，其中二维数组（或称矩阵）
可以看成是这样一个线性表：它的每个数据元素也是一个线性表。 5.1 数组及其存储对数组的操作主要是存取数组元素，即向某个数组元素
存入数据和获取某个数组元素中的数据。数组的存储结构数组是一种随机存储结构(顺序存储)一维数组LOC ( i ) = LOC ( i
-1 ) + l =α+ il 二维数组(矩阵) 三维数组(书)行向量 下标 i 页向量
下标 i列向量 下标 j 行向量 下标 j 列向量
下标 k二维数组通常有两种顺序存储方式：（1）行优先顺序: 将数组元素按行排列 （2）列优先顺序: 将数组元素按列排列 行优
先 LOC ( j, k ) = a + ( j m + k ) l5.2 特殊矩阵的压缩存储1、对称矩阵 在一个n
阶方阵A中，若元素满足下述性质：则称A为对称矩阵。对称矩阵中的元素关于主对角线对称，故只需要存储矩阵的上三角或下三角矩阵，这样可以
节约大约一半的空间。在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为：a00a10 a11a20 a21 a22...
....an-1,0 ........ an-1,n-1将这些元素存放在一个向量sa[n(n+1)/2]中。为了便于访问方阵A
中的元素，必须在aij和sa[k]之间建立一个对应关系。若aij在下三角矩阵中，则有：若aij在上三角矩阵中，则有：2、三角矩阵以
主对角线划分，三角矩阵有上三角和下三角两种：在多数情况下，三角矩阵的常数c为0。三角矩阵中的重复元素c可共享一个存储空间，其余的元
素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa[n(n+1)/2+1]中，其中c存放到向量的最后一个分量上。上三角
矩阵中，aij和sa[k]之间的对应关系为：下三角矩阵中，aij和sa[k]之间的对应关系为：3、对角矩阵对角矩阵中，所有非0元素
都集中在以主对角线为中心的带状区域中。对角矩阵的压缩存储方法将位于以主对角线为中心的带状区域中的非零元素按某种顺序（如按行优先顺序
、按列优先顺序或按对角线的顺序）压缩存储到一个一维数组中。 找每个非0元素和向量下标的对应关系举例:将三对角矩阵A中的非零元
素按“行优先顺序”存放到数组sa[3n?2]中。三对角矩阵A中，除第一行和最后一行只有两个非零元素外，其他每行中均有三个非零元素，
可知矩阵中位于aij之前的非零元素共有i行，共包含3i?1个非零元素，且aij所在的第i行前面还有j?(i?1)个非零元素。因此可
推出，sa[k]与三对角矩阵中的元素aij存在的对应关系为 k = 3i?1+j?(i?1) = 2i+j4
稀疏矩阵的压缩存储 如果一个矩阵的非0元素个数远远小于矩阵元 素的总数，则称这个矩阵为稀疏矩阵。一般来说，稀疏矩阵非0元素的
分布是无规律的。因此，在存储非0元素的同时，还要存储适当的辅助信息，才能迅速确定某一指定非0元素的位置。 稀疏矩阵常用的压缩存储方
式： 三元组表 十字链表(1)三元组表 若将表示稀疏矩阵的非0元素的三元组按行优先顺序排列，则
可得到一个其结点均是三元组的线性表，这个顺序存储结构就称为三元组表。 非0元素的 行号,
列号, 值templatestruct Trip
le{ int r, c; //行下标与列下标 T elem; //元素值};template s T>class SparseMatrix{ vector> triList; //三元组表 int row
s, cols, num; //行数、列数和非零元素个数public: SparseMatrix( ); //无参构造函数
SparseMatrix(Triple tlist, int rs, int cs, int n); //构造函数 vo
id trans(SparseMatrix& B); //矩阵转置运算 SparseMatrix& plus(SparseMa
trix& B); SparseMatrix& mult(SparseMatrix& B); void print();
//打印矩阵信息 };朴素转置算法templatevoid SparseMatrix::trans(S
parseMatrix& B){ B.rows=cols; B.cols=rows; B.num=num; if (n
um==0) return; q = 0; for (col=0; col for (p=0; p List[q].r=triList[p].c; B.triList[q].c=triList[p].r; B.triList[
q].elem=triList[p].elem; ++q; }}(2)十字链表 当非0元素的位置和个数经常发生
变化时，三元组表就不适合做稀疏矩阵的存储结构。因此，采用链接形式的存储结构更为恰当。 十字链表是稀疏矩阵链接形式存储
结构的一种（当然还有其它形式）。在该方法中每一个非0元素用一个结点表示，结点中除了表示非0元素的行、列和值的三元组外，还增加了两个
链域：行指针域，用来指向本行中下一个非0元素；列指针域，用来指向本列中下一个非0元素。 十字链表中的结点结构 举例
templatestruct CrossNode{ int r, c; //非零元素所在的行号和列号 T el
em; CrossNode right, down;};templateclass CrossMatrix{
vector> rheads, cheads; int rows, cols, num;
行数、列数和元素个数public: CrossMatrix(); //无参构造函数 CrossMatrix(int r, in
t c, int n); //构造函数 void trans(CrossMatrix& B); //矩阵转置 CrossM
atrix& plus(CrossMatrix& B); //加法 CrossMatrix& mult(CrossMatrix& B); //乘法 void print(); //打印矩阵信息 };本 章 小 结 （1）掌握多维数组的概念与顺序存储方法。（2）掌握对称矩阵、三角矩阵、对角矩阵这三种特殊矩阵的压缩存储方法，并掌握矩阵元素和压缩为一维数组元素之间的对应关系。（3）掌握稀疏矩阵的概念与两种压缩存储方法：三元组顺序表法和十字链表法 |
|
