3.4数组和特殊矩阵
易错点:
- 存储位置,上三角or下三角
- 行优先,列优先
- 矩阵元素下标从1or 0开始
- 数组元素下标从1 or 0 开始
做题可以用特殊值代入法检验
3.4.1数组的定义
数组是由n个相同类型的数据元素构成的有序序列
数组是线性表的推广,一个数组可以视为一个线性表
数组一旦被定义,其长度不会再改变,所以数组只会有存取元素和修改元素的操作
3.4.2数组的存储结构
多维数组
有两种映射方法:按行优先和按列优先
按行优先
M行N列二维数组b[M][N]中
i*N表示前i-1行一个有多少个元素
i*N+j表示前i-1行的元素个数+第i行的元素个数
b[i][j]的存储地址=LOC+(i*N)+j*sizeof(elemType)
按列优先
M行N列二维数组b[M][N]中
j*M表示前j-1列一个有多少个元素
j*N+i表示前j-1列的元素个数+第j列的元素个数
b[i][j]的存储地址=LOC+(j*M)+i*sizeof(elemType)
3.4.3特殊矩阵的压缩存储
※描述矩阵时,行号列号从1开始,数组通常下标从0开始,具体看题目给出条件
压缩矩阵:多个值相同的元素只分配一个存储空间
1.对称矩阵
下三角区+主对角线按行优先存储
数组大小:n(n+1)/2-----1+2+3+...+n
元素下标之间的对应关系:
i>=j:前i-1行+第i行的第几个=1+2+3+...+(i-1)+(j-1)
下三角区+主对角线按列优先存储
k=n+(n-1)+...+(n-j+2)+(i-j+1) i>=j
2.三角矩阵
除了主线和下三角元素其他都相同
数组长度=n(n+1)/2+1 下三角与主线的长度=1+2+3+..+(n) 单独存储常数的位置 +1
按行优先+下三角区
按行优先+上三角区
3.三对角矩阵
当|i-j|>1时,aij=0为三对角矩阵
存储元素个数=3n-2
元素下标间的关系为k=2i+j-3
3.4.4稀疏矩阵
1.将非零元素及其对应的行和列构成一个三元组
稀疏矩阵压缩存储后只能遍历,不可随机存储
struc{
int i;//行
int j;//列
int vslue;//值
}
2.十字链表存储--略