数组和特殊矩阵的压缩存储

目录

一、数组的相关概念

二、数组的抽象数据类型定义

三、数组的顺序存储结构

四、特殊矩阵的压缩存储

五、稀疏矩阵的顺序存储方法——三元组存储

六、稀疏矩阵的链式存储方法——十字链表

---

一、数组的相关概念

1、声明格式：数据类型 变量名称[行数] [列数]

例:int num[5] [8]

在C语言中，一个二维数组类型也可以定义为一维数组类型(其分量类型为一维数组类型)。

2、三维数组:若二维数组中的元素又是一个一维数组，则称作三维数组。

n维数组:若n-1维数组中的元素又是一个一维数组结构，则称作n维数组。

3、结论：线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展。

4、数组特点:结构固定——定义后，维数和维界不再改变。

二、数组的抽象数据类型定义

1、数组的基本操作:除了结构的初始化和销毁之外，只有取元素和修改元素值的操作。

2、基本操作：

(1) InitArray (&A,n, bound1, ...boundn)                                       //构造数组A

(2) DestroyArray (&A)                                                                //销毁数组A

(3) Value(A, &e,index1,...,indexn)                                             //取数组元素值

(4) Assign (A, &e,index1,...,indexn)                                        //给数组元素赋值

三、数组的顺序存储结构

1、因为：数组特点:结构固定维数和维界不变。数组基本操作:初始化、销毁、取元素、修改元素值，一般不做插入和删除操作。

所以：一般都是采用顺序存储结构来表示数组。

注意:数组可以是多维的，但存储数据元素的内存单元地址是一维的， 因此，在存储数组结构之前，需要解决将多维关系映射到一维关系的问题。

2、两种顺序存储方式：①以行序为主序（低下标优先）②以列序为主序（高下标优先）

例如：以行序为主序：设数组开始存储位置LOC( 0, 0 )，存储每个元素需要L个存储单元则数组元素a[i][j]的存储位置是: LOC( i, j)= LOC(0,0)+(n*i+j)*L。(n为每一行所含有的元素个数，n*i+j表示在a[i][j]前面所有元素个数）。

四、特殊矩阵的压缩存储

1.压缩存储的定义：若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。

2.能够压缩的矩阵：一些特殊矩阵，如:对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。

3.稀疏矩阵：矩阵中非零元素的个数较少(一般小于5%)。

4、压缩存储的原则：存各非零元的值、行列位置和矩阵的行列数。

五、稀疏矩阵的顺序存储方法——三元组存储

1、三元组（i,j,Aij）可以唯一确定矩阵的一个非零元素。

2、三元组顺序表的优点:非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。

3、三元组顺序表的缺点:不能随机存取，若按行号存取某一行中的非零元，则需从头开始进行查找。

六、稀疏矩阵的链式存储方法——十字链表

1、优点:它能够灵活地插入因运算而产生的新的非零元素,删除因运算而产生的新的零元素,实现矩阵的各种运算。

2、在十字链表中，矩阵的每一个非零元素用一个结点表示，该结点除了(row, col, value) 以外，还要有两个域:

①right:用于链接同一行中的下一个非零元素;

②down:用以链接同一列中的下一个非零元素。

3、十字链表中结点的结构示意图