数组的压缩存储（数据结构学习笔记）

淡淡的烟草味﹌ 2022-12-28 04:21 333阅读 0赞

### 文章目录 ###

*  数组
 *   *  数组的存储结构
     *   *  一维数组的存储结构
         *  二维数组的存储结构
         *  一、二维数组按行优先存放
         *  二、二维数组按列优先存放
     *  特殊矩阵的压缩存储
     *   *  一、对称矩阵的压缩存储
         *  二、上、下三角矩阵的压缩存储
         *   *  上三角矩阵
             *  下三角矩阵
             *  三、对角矩阵的压缩存储

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

# 数组 #

## 数组的存储结构 ##

在设计数组的存储结构时，通常将数组的所有元素存储到存储器的一块地址连续的内存单元中，即数组特别适合采用顺序存储结构来存储。

### 一维数组的存储结构 ###

对于一维数组(a1,a2,···,ai,···,an),按元素顺序存储到一块地址连续的内存单元中，假设第一个元素a1的存储地址用LOC(a1)表示，每个元素占用k个存储单元，则任一数组元素ai的存储地址LOC(ai)可用以下公式求出：

> LOC(ai) = LOC(a1) + ( i - 1 ) \* k (i>=2&&i<=n)

### 二维数组的存储结构 ###

对于一个m行n列的二维数组A\[m\]\[n\]：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]

### 一、二维数组按行优先存放 ###

即先存储第1行，紧接着存储第2行······依此类推，最后存储第m行

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 1]

最终的存储示意图：

![在这里插入图片描述][20201214165346490.png]

按照行优存放时，任一一个元素a\[i\]\[j\]的存储地址可以得出：  
（假设第一个元素a\[1\]\[1\]的存储地址为LOC(a\[1\]\[1\])表示，每个元素占用k个存储单元）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 2]

> LOC(a\[i\]\[j\]) = LOC(a\[1\]\[1\]) + \[( i - 1) \* n + ( j - 1 )\] \* k

### 二、二维数组按列优先存放 ###

即先存储第1列，紧接着存储第2列······依此类推，最后存储第m列  
同理如“按行优先存放的推导过程”

按照列优存放时，任一一个元素a\[i\]\[j\]的存储地址可以得出：  
（假设第一个元素a\[1\]\[1\]的存储地址为LOC(a\[1\]\[1\])表示，每个元素占用k个存储单元）

> LOC(a\[i\]\[j\]) = LOC(a\[1\]\[1\]) + \[( j - 1 ) \* m + ( i - 1 )\] \* k

## 特殊矩阵的压缩存储 ##

### 一、对称矩阵的压缩存储 ###

若一个n阶方阵A\[n\]\[n\]中的元素满足a\[i\]\[j\]=a\[j\]\[i\]（0≤i，j≤n-1），则称其为n阶**对称矩阵**。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 3]

以行序为主序存储其下三角+主对角线的元素。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 4]

下三角+主对角线的元素存储的下标k与二维数组中的下标i,j的对应关系：

![在这里插入图片描述][2020121416540812.png]

上三角的元素存储（上三角元素值与下三角值对称相等）：

![在这里插入图片描述][20201214165412487.png]

整个对称矩阵的压缩存储：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 5]

### 二、上、下三角矩阵的压缩存储 ###

#### 上三角矩阵 ####

上三角矩阵的特点是：下三角为一个固定的常数c。

![在这里插入图片描述][20201214165422139.png]

上三角的压缩存储示意图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 6]

上三角+主对角线的元素存储的下标k与二维数组中的下标i,j的对应关系：

![在这里插入图片描述][20201214165432160.png]

#### 下三角矩阵 ####

下三角矩阵的特点是：上三角为一个固定的常数c。

![在这里插入图片描述][20201214165438356.png]

上三角的压缩存储示意图：

![14][]

上三角+主对角线的元素存储的下标k与二维数组中的下标i,j的对应关系：

![在这里插入图片描述][20201214165449718.png]

#### 三、对角矩阵的压缩存储 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 7]

对称矩阵的压缩存储示意图以及对应关系：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 8]

*  学习数据结构教程（第五版）——李春葆教授主编
 *  图片来源于MOOC，数据结构——武汉大学——李春葆教授
 *  （如若侵权可联系QQ删除）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]: /images/20221120/fa4e8a5e716f4ba8920598876f27192a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 1]: /images/20221120/29e457fe8cb645e5ad258d78b186e2a9.png
[20201214165346490.png]: https://img-blog.csdnimg.cn/20201214165346490.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201214165351758.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201214165359197.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201214165403350.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70
[2020121416540812.png]: https://img-blog.csdnimg.cn/2020121416540812.png
[20201214165412487.png]: https://img-blog.csdnimg.cn/20201214165412487.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20201214165416568.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70
[20201214165422139.png]: https://img-blog.csdnimg.cn/20201214165422139.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20201214165427677.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70
[20201214165432160.png]: https://img-blog.csdnimg.cn/20201214165432160.png
[20201214165438356.png]: https://img-blog.csdnimg.cn/20201214165438356.png
[14]: https://img-blog.csdnimg.cn/20201214165442698.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70
[20201214165449718.png]: https://img-blog.csdnimg.cn/20201214165449718.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20201214165454270.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20201214165459430.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70