(一)、数组的定义
数组是一组偶对(下标值，数据元素值)的集合。二维数组对应着两个下标值，如此类推。
数组是由n(n>1)个具有相同数据类型的数据元素a1，a2，…，an组成的有序序列，且该序列必须存储在一块地址连续的存储单元中。
注：
偶对是一种基本的数据结构，用于将两个元素组合成一个单元。偶对通常用来表示一个二元关系即两个值之间的关联。具体来说，一个偶对通常包含以下两个部分：
第一个元素（First Element 或 Key）：偶对中的一个值，通常用来表示关系或映射中的键。
第二个元素（Second Element 或 Value）：偶对中的另一个值，通常用来表示与键相关联的数据或值。
1.数组的抽象数据类型定义
（1）抽象数据类型定义
ADT Array{
数据对象：ji= 0,1,…,bi-1 , 1,2, …,n ;
D = { aj1j2…jn | n>0称为数组的维数，bi是数组第i维的长度，ji是数组元素第i维的下标,aj1j2…jn∈ElemSet }
数据关系：R = {R1, R2, …, Rn}
Ri={<aj1j2 …ji…jn , aj1j2 …ji+1…jn>|0≦jk≦bk-1 ， 1≦k≦n且k≠i，0≦ji≦bi-2， aj1j2 …ji+1…jn∈D }
基本操作： ……
} ADT Array
n维数组中有b1b2 … bn个数据元素，每个数据元素都受到n维关系的约束。
（2）直观的n维数组
以二维数组为例讨论。将二维数组看成是一个定长的线性表，其每个元素又是一个定长的线性表。
设二维数组A=(aij)m*n，
则A=(α1，α2，…，αp) (p=m或n)
其中每个数据元素αj/ai
是一个列向量(线性表) ：αj =(a1j ，a2j ，…，amj) 1≦j≦n
或是一个行向量(线性表)：αi =(ai1 ，ai2 ，…，ain) 1≦i≦m
(二)、数组的顺序表示和实现
数组一般不做插入和删除操作，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。
二维数组是最简单的多维数组，存放(映射)到内存一维结构时的次序约定问题。主要有两种常见的约定方式：行优先和列优先。
1.数组的顺序存储方式
（1）行优先顺序(Row Major Order)：将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。行优先顺序是大多数编程语言（如C/C++）默认的存储方式。在这种方式中，二维数组的元素是按行顺序连续存储的。对二维数组，按行优先顺序存储的线性序列为：a11,a12,…,a1n, a21,a22,…a2n ,……, am1,am2,…,amn
（2）列优先顺序(Column Major Order)：将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，列优先顺序在Fortran等语言中是常见的存储方式。在这种方式中，二维数组的元素是按列顺序连续存储的。对二维数组，按列优先顺序存储的线性序列为：a11,a21,…,am1, a12,a22,…am2, ……, an1,an2,…,anm
例：假设一个3*3的n维数组。
设有二维数组A=(aij)m*n,有三维数组A=(aijk)m*p*n, 有n维数组aj1j2…jn
。若每个元素占用的存储单元数为l(个)，且LOC[a11]表示元素a11的首地址，即数组的首地址。
- 以“行优先顺序”存储二维数组中任一元素
Aij的(首)地址是：
LOC[aij]=LOC[a11]+[(i-1)*n +(j-1)]*l i=1,2, …,m j=1,2, …,n
- 以“行优先顺序”存储三维数组中任一元素
Aijk的(首)地址是：
LOC(aijk)=LOC[a111]+[(i-1)*n*p+(j-1)*p+(k-1)]*l
- 以“行优先顺序”存储n维数组中任一元素
aj1j2…jn的(首)地址是：
LOC[aj1j2…jn]=LOC[a11 …1]+[(b2*…*bn)*(j1-1)+ (b3*…*bn)*(j2-1)+ …
+ bn*(jn-1-1)+ (jn-1)] *l
- 以“列优先顺序”存储二维数组中任一元素
aij的(首)地址是：
LOC[aij]=LOC[a11]+[(j-1)*m+(i-1)]*l i=1,2, …,m j=1,2, …,n
(三)、矩阵的压缩存储
对于高阶矩阵，若其中非零元素呈某种规律分布或者矩阵中有大量的零元素，对这类矩阵进行压缩存储：
（1）多个相同的非零元素只分配一个存储空间；
（2）零元素不分配空间
1.特殊矩阵
特殊矩阵：是指非零元素或零元素的分布有一定规律的矩阵。
- 对称矩阵：若一个n阶方阵A=(aij)n*n中的元素满足性质：aij=aji 1≦i,j≦n 且i≠j则称A为对称矩阵
按“行优先顺序”存储下三角形(包括对角线)中的元素。
设用一维数组(向量)sa[0…n(n+1)/2]存储n阶对称矩阵，矩阵A中的元素的下标值（i,j）和向量sa[k]的下标值k之间的对应关系
若i≧j：
aij在下三角形中，元素aij保存在向量sa中时的下标值k之间的对应关系是： k=i*(i-1)/2+j i≧j
若i<j：
aij是在上三角矩阵中，元素aij保存在向量sa中时的下标值k之间的对应关系是：
k=j*(j-1)/2+i i<j
称sa[0…n(n+1)/2]为n阶对称矩阵A的压缩存储。
对称矩阵元素aij保存在向量sa中时的下标值k与（i,j）之间的对应关系如下：
- 三角矩阵：以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵的下三角（不包括主对角线）中的元素均为常数c(一般为0)。下三角矩阵正好相反，它的主对角线上方均为常数，
上三角矩阵元素aij保存在向量sa中时的下标值k与（i,j）之间的对应关系是
下三角矩阵元素ai j保存在向量sa中时的下标值k与（i,j）之间的对应关系是
- 对角矩阵：矩阵中，除了主对角线和主对角线上或下方若干条对角线上的元素之外，其余元素皆为零。
一个k对角矩阵(k为奇数)A是满足下述条件： 当|i-j|>(k-1)/2时， aij=0 。
以三对角矩阵为例讨论。当以按“行优先顺序”存储时， 第1行和第n行是2个非零
元素，其余每行的非零元素都要是3个，则需存储的元素个数为3n-2。
三对角矩阵压缩存储，非零元素aij的地址为：
LOC[aij] =LOC[a11] +[3*(i-1)-1+(j-i+1)]*l=LOC[a11]+(2*i+j-3)*l
称sa[0…3n-2]是n阶三对角矩阵A的压缩存储
2.稀疏矩阵
稀疏矩阵(Sparse Matrix)：设矩阵A是一个n*m的矩阵中有s个非零元素，设 δ=s/(n*m)，称δ为稀疏因子。如果某一矩阵的稀疏因子δ满足δ≦0.05时称为稀疏矩阵。
- 稀疏矩阵的压缩存储
对于稀疏矩阵，采用压缩存储方法时，只存储非0元素。必须存储非0元素的行下标值、列下标值、元素值。因此，一个三元组(i, j, aij)唯一确定稀疏矩阵的一个非零元素。
- 三元组顺序表：若以行序为主序，稀疏矩阵中所有非0元素的三元组，就可以得构成该稀疏矩阵的一个三元组顺序表。
a.三元组结点定义
#define MAX_SIZE 101
typedef int elemtype ;
typedef struct
{ int row ; /* 行下标 */
int col ; /* 列下标 */
elemtype value; /* 元素值 */
}Triple;
b.三元组顺序表定义
typedef struct
{ int rn ; /* 行数 */
int cn ; /* 列数 */
int tn ; /* 非0元素个数 */
Triple data[MAX_SIZE] ;
}TMatrix ;
3.转置矩阵
（1）转置矩阵的基本算法
① 将矩阵的行、列下标值交换。即将三元组表中的行、列位置值i 、j相互交换；
② 重排三元组表中元素的顺序。即交换后仍然是按行优先顺序排序的。
Comments NOTHING