3.4.3 矩阵的压缩存储.md

↩返回主页

⬅上一节 / 下一节➡

---

3.4.3 矩阵的压缩存储

  学过线性代数的同学都不会对矩阵太陌生。

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

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

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

  下面会介绍三种特殊矩阵的压缩存储方式：对称矩阵、上下三角矩阵、对角矩阵。

• 对称矩阵

  • 定义：若对一个 n 阶方阵 A[1...n][1...n] 中的任意元素 a_i,j 都有 a_i,j = a_j,i（i≤i, j≤n），则称其为对称矩阵。
  
  

  • 结论：由于上三角区完全等同于下三角区，所以我们只需存储主对角线和下三角区即可。

    • 原先存放数组存储单元大小：A[n][n]

    • 现在存放数组存储单元大小：B[n(n+1)/2]

  • 常考题：a_i,j 的数组下标 k？

    • 注意，若题没特殊说明，均是默认 按行优先

    • 上三角（i≥j）：i(i-1)/2 + j-1

    • 下三角（i<\j）：j(i-1)/2 + i-1

• 三角矩阵

  • 定义：若对一个 n 阶方阵 A[1...n][1...n] 中的上（下）三角区元素均为同一常量，则称为下（上）三角矩阵。
  
  

  • 若同一常量在上三角，则我们称这个矩阵为下三角矩阵；反之，同一常量在下三角，则称为上三角矩阵。我们要存放非同一常量的所以元素。

  • 结论：我们只需存储非同一常量的上（下）三角即可，并且要增加一个数组的存储单元用于存放常量值 c，一般增添在末尾。

    • 存放数组存储单元大小：B[n(n+1)/2 + 1]

  • 常考题：a_i,j 的数组下标 k（注意，若题没特殊说明，均是默认按行优先）？

    • 下三角矩阵

      上三角（i≥j）：i(i-1)/2 + j-1

      下三角（i<\j）：n(n+1)/2（以 n 确定的常量）

    • 上三角矩阵

      上三角（i>j）：n(n+1)/2（以 n 确定的常量）

      下三角（i≤j）：(i-1)(2n-i+2)/2 + (j-i)

• 三对角矩阵

  • 定义：若对一个 n 阶方阵 A[1...n][1...n] 中的任意元素 a_i,j，当 |i-j|>1，有 a_i,j=0（1≤i, j≤n），则称为三对角矩阵。
  
  

  • 结论：我们只需存放主对角线上的三斜行元素。

  • 常考题（注意，若题没特殊说明，均是默认按行优先）

    • a_i,j 的数组下标 k？

      k = 3*(i-1)-1+j-i+1+1-1 = 2i+j-3

    • 若 k 已知，求 i，j？

      i = (k+1)/3 + 1 的向下取整

      j = k-2i+3

💡 题型

  xxx

单项选择题

1. xxxx（ ）

   A. xxx
   B. XX
   C. Xx
   D. xX
   
   

   查看解析

   答案：x

---

返回顶部⤴

-- 完 --