目录
1.一维数组的存储结构
2.二维数组的存储结构
3.普通矩阵的存储
4.特殊矩阵的压缩存储
（1）对称矩阵
（2）三角矩阵
（3）三对角矩阵
（4）稀疏矩阵的压缩存储
1.一维数组的存储结构
一维数组的定义如下：
ElemType a[10];
各数组元素大小相同，且物理上连续存放。
数组元素a[i]的存放地址=LOC+i*sizeof(ElemType)。
注:除非题目特别说明，否则数组下标默认从0开始，若题目提醒下标从1开始，则存放地址为
LOC+（i-1）*sizeof(ElemType)。
2.二维数组的存储结构
二维数组定义如下：
ElemType b[2][4];
由于内存的存储空间是连续的，线性的，所以把二维数组放到内存中，有两种存放方式，行优先存放（一行一行地存）和列优先存放（一列一列地存）。
M行N列的二维数组 b[M][N]中，若按行优先存储，则
b[i][j]的存储地址 = LOC+(i*N+j)*sizeof(ElemType)
若按列优先存储，则
存储地址 = LOC+(j*M+i)*sizeof(ElemType)
3.普通矩阵的存储
普通矩阵可用二维数组存储，描述矩阵元素时，行、列号通常从1开始；而描述数组时通常下标从0开始。
4.特殊矩阵的压缩存储
（1）对称矩阵
若n阶方阵中任意一个元素 都有 ，则该矩阵为对称矩阵。
对称矩阵进行普通存储：n*n二维数组，压缩存储：只存储主对角线+下三角区。
按行优先原则将各元素存入一维数组中。
存储结构如下:
可以看到，第一行有1个元素，第二行有2个元素，第三行有3个元素，以此类推，第n行有n个元素，所以总共有1+2+3.....+n个元素，数组大小为
那么怎么通过矩阵下标映射到一维数组的下标呢？
例如，按行优先的原则，是第几个元素？
第一行有1个元素，第二行有2个元素，以此类推，第i-1行就有i-1个元素，所以是第
个元素，即
个元素，由于数组下标是从0开始，所以
的数组下标为k=
。
若要得到上三角某个元素，那么可以根据，转换为,进而得到与下三角相同的存放规律。
进而其一维数组下标为：
总结：
按照列优先原则进行存储，是第几个元素？
如上图所示，第1列有n个元素，第2列有n-1个元素，第j-1列有n-j+2个元素。
技巧：1+n=n+1，2+(n-1)=n+1,(n-1)+(n-j+2)=n+1
第j列有多少元素，用（行号 - 列号+1）即可，可以自己验算一下。
所以是第
个元素
默认从0开始的话，数组下标在上面的基础上减1即可：
由等差数列易得：
所以的下标为：
（2）三角矩阵
下三角矩阵：除了主对角线和下三角区，其余的元素都相同。
压缩存储：按行优先原则将橙色区元素存入一维数组中。并在最后一个位置存储常量c。
所以一维数组的长度：(1+2+3.....n)+1
若按照行优先的原则，是第几个元素：
下三角和对称矩阵的运算一样，对于上三角，由于上三角每个元素都是一样的，所以映射到一维数组的最后一个元素，即B[
]
上三角矩阵：除了主对角线和上三角区，其余的元素都相同。
按照行优先原则，是第几个元素？
第1行到第i-1行有
第i行有j-i+1个元素：列号(j)-行号(i)得到该元素在第i行的前面有多少元素。
所以是第
个元素。
其数组下标为：
由等差数列的求和公式易得：
要访问下三角区的话同理，直接映射到一维数组的最后一个位置。
总结:
（3）三对角矩阵
三对角矩阵，又称带状矩阵：当|i-j|>1时，有=0(1≤i，j≤n)，通俗点来讲就是，主对角线元素及其上下左右的元素不为0，其余元素的值全为0。
压缩存储：按行优先(或列优先)原则，只存储带状部分。
可以观察到，带状矩阵除了第一行和最后一行是两个元素，其余行都是三个元素。所以要存储的元素个数为：3*n-2
若默认数组下标从0开始，那么最后一个元素的数组下标就为：B[3n-3]
那么按行优先的原则，是第几个元素?
前 i-1 行共 3(i-1)-1 个元素。
是第i行的 j-i+2 个元素。
那么将两个数加起来：是第 2i+j-2个元素
为什么有j-i+2呢？
由上三角矩阵我们可以分析得，的元素在第i行的前面有j-i个元素，例如,前面就有：
2-1=1个元素。
对比这里，把三角形往前挪一个位置，可以得到相同的在第i行的前面的元素的个数，所以在第i行，前面有j-i+1个元素，那么加上它本身是第i行第j-i+2个元素。
我是这么理解的，不管怎么理解，只要自己理解就可以啦~
有些人也会有疑问，是第i行的 j-i+2 个元素针对第一行就不对呀？其实结合前 i-1 行共 3(i-1)-1 个元素，针对第一行计算得到-1，再加上j-i+2 也是对的结果。
例如：
根据式子3(i-1)-1， 前i-1(0)行有-1个元素，再根据式子：是第i行的 j-i+2 个元素，得到
2-1+2=3个元素，那么最后两者相加3+(-1)=2，得到的也是正确的结果，也就是是第2个元素。
那么第k+1个元素，在第几行?第几列?
前 i-1 行共 3(i-1)-1个元素
前 i 行共 3 i-1 个元素
显然，3(i-1)-1< k+1 ≤ 3i-1
不等式解出来为：
，且
因为i是行号，一定是正整数，将这个式子向上取整，即 i=
，就可以满足i"刚好"大于等于某一行。
王道书中的逻辑：第k+1个元素前有k个元素，并且k满足3(i-1)-1 ≤ k ＜ 3i-1
不等式解出来为：
，且
将这个式子向下取整，即 i=
，即可满足i“刚好”小于等于某一行。
由于我们之前讲到过是第 2i+j-2个元素，其下标默认从0开始，就是2i+j-3，所以：k=2i+j-3，所以我们就可以从 k 和 i 推出j的值了。
（4）稀疏矩阵的压缩存储
稀疏矩阵就是非零元素远远少于矩阵元素的个数。
压缩存储：
1.顺序存储---三元组<行，列，值>，这里存储的值都是稀疏矩阵中的非0元素。
注：此处行、列标从1开始
若用这种方式存储稀疏矩阵，想要访问其中的某个元素，只能顺序依次扫描三元组，会失去随机存取的特性。
2.链式存储---十字链表法。如图所示，向下域down指向第j列的第一个元素，向右域 right,指向第i行的第一个元素。
每个非0元素会对应一个结点，这个结点包括该非0元素所在的行，列以及对应的值；还会包含两个指针，第一个指针指向同列的下一个元素，第二个指针指向同行的下一个元素。可以看图自己分析一下。
例如：该结点第一个指针为空，表示该列没有非0元素了；第二个结点指向了同行的下一个元素，即5。
以上公式不建议死记硬背，充分理解之后，考场上也可以推出来的。文章来源：https://www.toymoban.com/news/detail-860973.html
公式是没有错的，附上了自己的理解，如果哪个公式不懂可以评论区或私信我，如果哪里理解错误，可以评论区纠正，若有更好的方法，可以在评论区分享出来！谢谢佬们💖💖💖文章来源地址https://www.toymoban.com/news/detail-860973.html
到了这里，关于数据结构（五）----特殊矩阵的压缩存储的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
