data structure

矩阵在计算机图形学 、工程计算中占有举足轻重的地位 。在数据结构中考虑的是如何用最小的内存空间来存储同样的一组数据 。所以 ,我们不研究矩阵及其运算等 ,而把精力放在如何将矩阵更有效地存储在内存中 ,并能方便地提取矩阵中的元素 。

1. 数组的定义

数组是由 n 个相同类型的数据构成的有限序列 。

数组和线性表的关系 :数组是线性表的推广 。一维数组可以视为一个线性表 ;二维数组可以视为元素是线性表的线性表 。

数组一旦被定义,其维数和维界就不再改变 。因此,除结构的初始化和销毁外 ,数组只会有存取元素和修改元素的操作 。

2. 数组的存储结构

C 语言提供了数组数据类型 ,一个数组的所有元素在内存中占用一段连续的存储空间 ,C 语言按行分布 。二维数组其实也是一段连续的存储空间 ,一行一行地拼接而成 。

3. 矩阵的压缩存储

压缩存储 :指为多个值相同的元素只分配一个存储空间 ,对零元素不分配存储空间 。其目的是为了节省存储空间。

特殊矩阵 :指具有许多相同矩阵元素或零元素 ,并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵 。常见的特殊矩阵有对称矩阵 、上(下)三角矩阵 、对角矩阵等 。

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

3.1 对称矩阵

n 阶方阵且 a_ij = a_ji

若采用二维矩阵存储,浪费几乎一半空间,所以将其存放到一维数组 B[n(n+1)/2] 中 。

第一行 :1 个元素 (a_11)

第二行 :2 个元素 (a_21 ,a_22)

一直到第 n 行 。

k=i(i-1)/2+j-1(或 j(j-1)/2+i-1 ,利用对称性即可)

3.2 三角矩阵

上三角(或下三角)均为同一变量 ,那么除去上三角(或下三角)的部分还是按对称矩阵的方式存储 ,多一个存储单元存储上三角的那个常量 (B[n(n+1)/2] 存放常量)。

3.3 三对角矩阵

对角矩阵也称带状矩阵 。所有非零元素都集中在以主对角线为中心的 3 条对角线的区域 ,其他区域的元素都为零。

可采用压缩存储,按行优先存储即可 。由于 |i-j|<1 ,前面 i-1 行有 3i-3 个元素 ,自身是本行的 j-i+1 个元素 ,存储结构从零开始 ,得到 k=2i+y-3 。

3.4 稀疏矩阵

矩阵元素分布无规律 ,但是非零个数特别少(n 个) ,则利用 3×n 的二维数组存储,每行存储元素的坐标和大小。只不过压缩后便失去了随机存取特性 。