扫码获取更多资源

●矩阵的压缩存储

矩阵即二维数组，是很多科学与工程计算问题中研究的数学对象。在数据结构中，研究 者感兴趣的不是矩阵本身，而是如何存储矩阵中的元素，使矩阵的各种运算能够有效地进 行。通常，在使用高级语言编制程序时都是用二维数组来存储矩阵元素。然而，在数值分析 中经常会出现有些阶数很高的矩阵，且矩阵中非零元素呈现某种规律分布，或矩阵中有许多 值相同的元素或零元素。为了节省存储空间，可以对这类矩阵进行压缩存储，即为多个值相 同的非零元素只分配一个存储空间，且对零元素不分配存储空间。

●特殊矩阵的压缩存储

非零元素或零元素分布具有一定规律的矩阵称为特殊矩阵(Especial Matrix) 0常见特 殊矩阵有三种：对称矩阵、三角矩阵和对角矩阵。

对称矩阵

在一个n阶矩阵A中，如果元素满足ajj = aji(O〈i,j〈n—1),则称A为n阶对称矩阵。 图5-5给岀了一个5阶对称矩阵。

因为对称矩阵中的元素关于主对角线是对称的，所以只要存储 矩阵中上 三角和下三角中每两个对称的元素共享一个存储空间，这 样就能节约近一半的存储空间。 块连续的存储单元中，适合于随机查找。

对称矩阵的地址计算

如果矩阵中的每个元素占L个存储单元，那么根据式(5-7),对称矩阵的下标变换公式 由式(5-8)表示：

三角矩阵

按主对角线划分，三角矩阵分为上三角矩阵和下三角矩阵两种。下三角(不包括对角 线)中的元素均为常数c或零的n阶矩阵称为上三角矩阵。上三角(不包括对角线)中的元 素均为常数c或零的n阶矩阵称为下三角矩阵。图5-7(a)给出了一个5阶上三角矩阵， 图5-7(b)给出了一个5阶下三角矩阵。

三角矩阵按主对角线进行划分,其压缩存储与对称矩阵类似，不同之处仅在于除了存储 主对角线一边三角中的元素以外，还要存储对角线另一边三角的常数co这样原来需要nX n个存储单元，现在只需要nX(n+l)/2 + l个存储单元,节约了近一半的存储单元。

对角矩阵

在一个n阶矩阵中，所有的非零元素集中在以主对角线为中心的带状区域中，除了主对 角线(a”，0WiWn—1)和主对角线相邻两侧的若干条对角 线3港+1,0WiWn—2； ai+]」，0 Wn—2)上的元素之外，其 余元素皆为零的矩阵称为n阶对角矩阵。由此可知，一个 w对角线矩阵(w为奇数)A满足：如果|i-j|>(w-l)/ 2,则元素au=0。图5-9给出了一个3对角5阶矩阵。

存储方式

首先将一个n阶的w对角矩阵转换为一个n行w列的nXw矩阵(如图5-10(a)),在该矩阵中共有(wX n-(w2 -1)/4)个非零元素及(v/ —1)/ 4个零元素；然后将这些元素按行优先依次存储到一维数组SA[nXw]中(如图5-10(b))o 图5-10给出了一个5阶3对角矩阵压缩存储的示意图。

联系我们：