特殊矩阵的压缩存储

r囧r小猫 2023-02-27 12:28 3阅读 0赞

压缩存储：指多个值相同的元素只分配一个存储空间， 对零元素不分配存储空间。

特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。

特殊矩阵的压缩存储：找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布、值相同的多个矩阵元素压缩存储到一个存储空间上。

--------------------

# 1 对称矩阵 #

若对一个n阶方阵A\[1...n\]\[1...n\]中的任意元素![a\_\{i,j\}][a_i_j]都有![a\_\{i,j\}=a\_\{j,i\}][a_i_j_a_j_i](1≤i，j≤n),则称其为对称矩阵。![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1][] 行优先，以这样的次序存放元素

![20200717190159721.png][]

# 2 三角矩阵 #

三角矩阵若对一个n阶方阵A\[1...n\]\[1...n\]中上(下)三角区元素均为同一常量，则称为下(上)三角矩阵。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2][]

存放需要![\\frac\{n(n+1))\}\{2\}+1][frac_n_n_1_2_1]个位置。

# 3 三对角矩阵 #

若对一个n阶方阵A中的任意元素aij,当|i - j|>1,有aij=0 (1≤i，j≤n) ,则称为三对角矩阵。![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 3][]

# 4 稀疏矩阵 #

矩阵元素个数s相对于矩阵中非零元素的个数t来说非常多，即s> >t的矩阵称为稀疏矩阵。![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 4][]

稀疏矩阵用三元组存储，已经不能用简单的下标来实现访问，所以已经失去了随机访问的功能。

--------------------

例题：[https://www.nowcoder.com/questionTerminal/ebfca69857c34601ab795ee2725ba45c?toCommentId=86623][https_www.nowcoder.com_questionTerminal_ebfca69857c34601ab795ee2725ba45c_toCommentId_86623]

特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？为什么？

答：特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元素分配单元（对值相同元素只分配一个单元），将非零元素存储在向量中，元素的下标i和j和该元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小（t＜＜m\*n），且分布没有规律。用十字链表作存储结构自然失去了随机存取的功能。即使用三元组表的顺序存储结构，存取下标为i和j的元素时，要扫描三元组表，下标不同的元素，存取时间也不同，最好情况下存取时间为O(1)，最差情况下是O(n)，因此也失去了随机存取的功能。

[a_i_j]: https://private.codecogs.com/gif.latex?a_%7Bi%2Cj%7D
[a_i_j_a_j_i]: https://private.codecogs.com/gif.latex?a_%7Bi%2Cj%7D%3Da_%7Bj%2Ci%7D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70]: /images/20230209/bcefc3af73534adab64e31d9fd5a49ed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1]: /images/20230209/72e10503809f49ad8385b1d62c60315e.png
[20200717190159721.png]: https://img-blog.csdnimg.cn/20200717190159721.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200717212734985.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5,size_16,color_FFFFFF,t_70
[frac_n_n_1_2_1]: https://private.codecogs.com/gif.latex?%5Cfrac%7Bn%28n&plus;1%29%29%7D%7B2%7D&plus;1
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200717221122901.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200717223842558.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5,size_16,color_FFFFFF,t_70
[https_www.nowcoder.com_questionTerminal_ebfca69857c34601ab795ee2725ba45c_toCommentId_86623]: https://www.nowcoder.com/questionTerminal/ebfca69857c34601ab795ee2725ba45c?toCommentId=86623