数据类型 变量名称[行数][列数]在C中，二维数组类型可以定义为一维数组类型（其组件类型为一维数组类型），即
typedef elemtype array2[m][n];相当于：
typedef elemtype array1[n];
typedef elemtype array2[m];三维数组：如果二维数组中的元素也是一维数组，则称为三维数组。
n维数组：如果n-1维数组中的元素也是一维数组结构，则称为n维数组。
结论：线性列表结构是数组结构的特例，数组结构是线性列表结构的扩展。
数组的特点：结构固定——定义后，维度和维度边界不会改变
数组的基本操作：除了结构体的初始化和销毁之外，只有取元素和修改元素值的操作。
数组的抽象数据类型定义
ADT数组{
数据对象：
=0,...,
,i=1,2,...,n,
D={
| n(>0) 称为数组的维数，
是数组第 i 维的长度，
是数组元素的第i维下标，
ε }
数据关系：R={R1,R2,...Rn}
里={<
> |
0≤
≤
, 1 ≤ k ≤ n 且 k ≠ i ,
0≤
≤
ε D, i = 2,...,n }
基本操作：
（＆一个，，...，）
运算结果：如果维数n及各维长度合法，则构造对应的数组A并返回OK。
＆A
操作结果：销毁数组A
值(A,&e,,...,)
初始条件：A是一个n维数组，e是一个元素变量，后面是n个下标值
运算结果：若各下标均未超出范围，则将A的指定元素的值赋给e，返回OK。
(&A,e,,...,)
初始条件：A是一个n维数组，e是一个元素变量，后面是n个下标值
操作结果：如果下标没有超出范围，则将e的值赋给A的指定元素，并返回OK。
}ADT数组
二维数组
n=2，维度为2，二维数组
b1：第 1 维长度 b2：第 2 维长度
：第一个维度下标是
，第二维下标为
数据对象：D={
| 0≤
≤
,0≤
≤
数据关系：R={ ROW , COL }
行={| 0≤
≤
,0≤
≤
颜色={ | 0≤
≤
,0≤
≤
储存方法
数组的特点：结构固定——维数和维数界限保持不变
数组的基本操作：初始化、销毁、获取元素、修改元素值。 一般不进行插入或删除操作。 因此，一般采用顺序存储结构来表示数组。
顺序存储
数组可以是多维的，但存储数据元素的内存单元地址是一维的，因此在存储数组结构之前需要将多维关系映射为一维关系。
一维数组
二维数组
两种顺序存储方式：
序列：A[m][n]
A=(
)( p=m 或 n )
1 ≤ i ≤ m，行主序
1 ≤ j≤ n 列序为主序
行顺序为主顺序
假设数组的起始存储位置为LOC(0,0)。 每个元素需要L个元素单元来存储。 数组元素a[i][j]的存储位置为：LOC(i,j)=LOC(0,0)+ (n*i+j)*L [n*i+j为所有元素的个数在a[i][j]前面]
列主序
三维数组
存储在页/行/列中，按页优先顺序
a[m1][m2][m3] 每个维度的元素个数为m1,m2,m3
下标i1、i2、i3的数组元素的存储位置：
LOC(i1,i2,i3)=a+i1*m2*m3+i2*m3+i3 a 是指针，*L 不需要
i1*m2*m3：前i1页的元素总数
i2*m3：i1页第i2行元素总数
i3：i2行之前的i3列中的元素数量
n 维数组
特殊矩阵的压缩存储
矩阵：m行n列，由m*n个元素组成的列表。
矩阵的常规存储：将矩阵描述为二维数组
矩阵的一般存储特性：
不适合常规存储的矩阵：有很多相同值的元素，并且以某种规则的方式分布； 有很多零元素
矩阵的压缩存储：多个相同的非零元素只分配一个存储空间； 没有为零个元素分配空间
压缩存储：如果多个数据元素的值相同，则只会分配一个元素值的存储空间，零个元素不会占用存储空间。
可压缩矩阵：一些特殊矩阵，如：对称矩阵、对角矩阵、三角矩阵、稀疏矩阵
稀疏矩阵：矩阵中非零元素的数量很少（一般小于5%）
对称矩阵
特点：在n*n矩阵a中，满足
( 1 ≤ i,j ≤ n )
存储方式：只存储下（或上）三角形（包括主对角线）的数据元素，共占用n*(n+1)/2个元素空间
三角矩阵
特点：对角线以下（或以上）（不包括对角线）的所有数据元素均为常数C
存储方式：重复元素C共享一个元素存储空间，共占用n*(n+1)/2+1个元素。
对角矩阵（带状矩阵）
特点：在n*n方阵中，所有非零元素都集中在以对角线为中心的条形区域内，区域外的值全部为0，称为对角矩阵。 常见的有三对角矩阵、五对角矩阵、七对角矩阵……
存储方式：对角顺序存储
稀疏矩阵
假设m*n矩阵中有t个非零元素，令δ=t/(m*n)，当δ≤0.05时，称为稀疏矩阵
三元组 (i,j,
) 唯一确定矩阵的非零元素
压缩存储原理：存储矩阵各非零元素的值、行列位置以及行列数
三元组的不同表示方法可以决定稀疏矩阵不同的压缩存储方法
顺序存储-三重顺序表
为了更可靠的描述，通常会添加“总体”信息：即总行数、总列数和非零元素总数。
三重序列表也称为有序双下标法。
三重序列表的优点：非零元素在表中按行顺序存储，因此可以方便地进行按行顺序处理的矩阵运算。
三重序列表的缺点：不能随机访问。 如果按行号访问一行中的非零元素，则需要从头开始查找。
链接存储——交叉链表
优点：能够灵活插入运算产生的新的非零元素，删除运算产生的新的零元素，实现矩阵的各种运算
在交叉链表中，矩阵的每个非零元素都由一个节点表示。 节点除了(row, col, value)之外，还有两个字段：
交叉链表中节点的结构示意图：
