特殊矩阵的压缩存储

1 数组

数组是一组偶对(下标值，数据元素值)的集合。在数组中，对于一组有意义的下标，都存在一个与其对应的值。一维数组对应着一个下标值，二维数组对应着两个下标值，如此类推。
数组是由 n(n>1)个具有相同数据类型的数据元素 $a_1,a_2,\cdots,a_n$ 组成的有序序列，且该序列必须存储在一块地址连续的存储单元中。
数组中的数据元素具有相同数据类型。
数组是一种随机存取结构，给定一组下标，就可以访问与其对应的数据元素。
数组中的数据元素个数是固定的。

计算机的内存结构是一维(线性)地址结构，对于多维数组，将其存放(映射)到内存一维结构时，有个次序约定问题。即必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放到内存中。
二维数组是最简单的多维数组，以此为例说明多维数组存放(映射)到内存一维结构时的次序约定问题。

对于 $A=(a_{ij})_{m\times n}$ ，通常有两种顺序存储方式
(1) 行优先顺序(Row Major Order) :将数组元素按行排列，第 i+1个行向量紧接在第 i 个行向量后面。对二维数组，按行优先顺序存储的线性序列为: $a_{11},a_{12},\cdots,a_{1n} , \cdots ,a_{m1},a_{m2},\cdots,a_{mn}$
PASCAL、C 是按行优先顺序存储的。
(2) 列优先顺序(Column Major Order) :将数组元素按列向量排列，第 j+1 个列向量紧接在第 j 个列向量之后，对二维数组，按列优先顺序存储的线性序列为:
$a_{11},a_{21},\cdots,a_{m1} , \cdots,a_{n1},a_{n2},\cdots,a_{nm}$
FORTRAN 是按列优先顺序存储的。

设有二维数组 $A=(a_{ij})_{m\times n}$ ，若每个元素占用的存储单元数为L个， $LOC[a_{11}]$ 表示元素 $a_{11}$ 的首地址，即数组的首地址
(1)以“行优先顺序”存储
第 1 行中的每个元素对应的(首)地址是: $LOC[a_{1j}]=LOC[a_{11}]+(j-1) \times L\space \space \space \space \space \space \space j=1,2, \cdots,n$
第 m 行中的每个元素对应的(首)地址是: $LOC[a_{mj}]=LOC[a_{11}]+(m-1)\times n\times L+(j-1) \times L\space \space \space \space \space \space \space j=1,2, \cdots,n$
(2)以“列优先顺序”存储
(1) 第 1 列中的每个元素对应的(首)地址是:
$LOC[a_{i1}]=LOC[a_{11}]+(i-1)\times L\space \space \space \space \space \space \space i=1,2, \cdots,m$
(3) 第 n 列中的每个元素对应的(首)地址是: $LOC[a_{in}]=LOC[a_{11}]+ (n-1)\times m\times L +(i-1)\times L\space \space \space \space \space \space \space i=1,2, ...,m$

2 特殊矩阵

特殊矩阵(对称矩阵，对角矩阵，三角矩阵)压缩存储:
多个相同的非零元素只分配一个元素值的存储空间；
零元素不分配空间。
(1)对称矩阵
对称矩阵的特点是:在一个 n 阶方阵中，有 $a_{ij}=a_{ji}$ ，其中 1≤i，j≤n，对称矩阵关于主对角线对称，因此只需存储上三角或下三角部分即可。
设有对称矩阵A[i][j]如下图示:

存储此二维数组，需要 n*n 个存储单元。若只对下三角部分以行为主序顺序存储到一个向量中去，在下三角中共有个元素，压缩存储后的结果如下:

以一维数组 sa[n(n+1)/2]作为 n 阶对称矩阵 A 的存储结构，则 sa[k]和矩阵元

a_{ij}

之间存在着一一对应的关系:

(2)三角矩阵
①下三角矩阵:
设有下三角矩阵 A[i][j]如下图所示:

在下三角矩阵中，主对角线以上的元素是一个常量。存完下三角中的元素之后，紧接着存储对角线上方的常量，因为是同一个常数，所以存一个即可，其压缩存储后如下图所示:

共存储了 n(n+1)/2 个元素，设存入向量 SA=[k]中，这种存储方式可节约个存储单元，K与 i,j 的对应关系为:

②上三角矩阵
设有上三角矩阵 A[i][j]如下图所示:

在上三角矩阵中, K 与 i,j 的对应关系为:

(3)对角矩阵
对角矩阵也称为带状矩阵,如下图所示:

三对角矩阵

在这种三对角矩阵中，所有非零元素都集中在以主对角线为中心的对角区域中，即除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零(或同一个常数 C)。
对角矩阵 A 也可以采用压缩存储，将三对角矩阵压缩到向量 SA[k]中去，按以行为主序，顺序的存储其非零元素，按其压缩规律，找到相应的映象函数。k与i,j的对应关系为:

3 稀疏矩阵

稀疏矩阵:设矩阵 A 是一个 n*m 的矩阵中有 s 个非零元素，设 δ=s/(n $\times$ m)，称δ为稀疏因子，如果某一矩阵的稀疏因子δ满足δ≦0.05 时称为稀疏矩阵。对于稀疏矩阵，采用压缩存储方法时，只存储非 0 元素。必须存储非 0 元素的行下标值、列下标值、元素值。

稀疏矩阵

一个三元组

(i, j, a_{ij})

唯一确定稀疏矩阵的一个非零元素。如上图的稀疏矩阵 A 的三元组线性表为:
( (1,2,12), (1,3,9), (3,1,-3), (3,8,4), (4,3,24), (5,2,18), (6,7,-7), (7,4,-6) )

(1)三元组顺序表
若以行序为主序，稀疏矩阵中所有非 0 元素的三元组，就可以得构成该稀疏矩阵的一个三元组顺序表。相应的数据结构定义如下:

#define MAX_SIZE 101
typedef int elemType;
typedef struct {//三元组结点定义
    int row;/* 行下标 */
    int col; /* 列下标 */
    elemType value;/* 元素值 */
} Triple;

typedef struct {//三元组顺序表定义
    int rn;/* 行数 */
    int cn;/* 列数 */
    int tn;/* 非0元素个数 */
    Triple data[MAX_SIZE];
} TMatrix;

(2)十字链表
对于稀疏矩阵，当非 0 元素的个数和位置在操作过程中变化较大时，采用链式存储结构表示比三元组的线性表更方便。
矩阵中非 0 元素的结点所含的域有:行、列、值、行指针(指向同一行的下一个非 0 元)、列指针(指向同一列的下一个非 0 元)。其次，十字交叉链表还有一个头结点，结点的结构如图所示。

十字链表结点定义

由定义知，稀疏矩阵中同一行的非 0 元素的由 right 指针域链接成一个行链表，由 down指针域链接成一个列链表。则每个非 0 元素既是某个行链表中的一个结点，同时又是某个列链表中的一个结点，所有的非 0 元素构成一个十字交叉的链表。称为十字链表。
此外，还可用两个一维数组分别存储行链表的头指针和列链表的头指针。

十字链表存储示意图

typedef struct Clnode {
    int row, col; /* 行号和列号 */
    elemType value; /* 元素值 */
    struct Clnode *down, *right;
} OLNode;/* 非 0 元素结点 */

typedef struct {
    int rn;/* 矩阵的行数 */
    int cn;/* 矩阵的列数 */
    int tn;/* 非0元素总数 */
    OLNode *rhead;
    OLNode *chead;
} CrossList;

4 广义表

广义表是线性表的推广和扩充，在人工智能领域中应用十分广泛。
把线性表定义为 n(n≧0 )个元素 a1, a2 ,..., an 的有穷序列，该序列中的所有元素具有相同的数据类型且只能是原子项(Atom)。所谓原子项可以是一个数或一个结构，是指结构上不可再分的。若放松对元素的这种限制，容许它们具有其自身结构，就产生了广义表的概念。
广义表(Lists，又称为列表 ):是由 n(n ≧0)个元素组成的有穷序列: LS= $(a_1,a_2,\cdots,a_n)$ 其中 $a_i$ 或者是原子项，或者是一个广义表。LS是广义表的名字，n 为它的长度。若 $a_i$ 是广义表，则称为 LS 的子表。习惯上:原子用小写字母，子表用大写字母。

若广义表 LS 非空时:
$a_1$ (表中第一个元素)称为表头; 其余元素组成的子表称为表尾; $(a_2，a_3,\cdots，a_n)$ 。广义表中所包含的元素(包括原子和子表)的个数称为表的长度。
广义表中括号的最大层数称为表深 (度)。
两个基本操作 GetHead() GetTail()。

广义表

树形表示法

广义表的重要结论:
(1) 广义表的元素可以是原子，也可以是子表，子表的元素又可以是子表， ...。即广义表是一个多层次的结构。
(2) 广义表可以被其它广义表所共享，也可以共享其它广义表。广义表共享其它广义表时通过表名引用。
(3) 广义表本身可以是一个递归表。
(4) 根据对表头、表尾的定义，任何一个非空广义表的表头可以是原子，也可以是子表，而表尾必定是广义表。