第三章 栈、队列和数组

小题考频：23
大题考频：4

3.4 数组和特殊矩阵

难度：☆☆☆

知识总览

3.4.1~3.4.4_特殊矩阵的压缩存储

3.4.1~3.4.4_特殊矩阵的压缩存储

一维数组的存储结构

各数组元素大小相同，且物理上连续存放。

数组元素a[i]的存放地址= LOC + i * sizeof(ElemType) (0 ≤ i < 10)

注：除非题目特别说明，否则数组下标默认从0开始（注意审题！）

从1开始就变成 i - 1

二维数组的存储结构

放到内存当中时有两种存储方法：

1. 行优先，一行一行存；

M行N列的二维数组b[M][N]中，若按行优先存储，则

b[i][j]的存储地址= LOC + (i*N + j) * sizeof(ElemType)

b[i][j]存储地址 = 起始地址LOC ➕ [行号 ✖ 每一行有多少个数据元素 + 列号](即前面有多少元素) ✖ 数据元素大小(前面的总数据元素大小)

2. 列优先，一列一列存

M行N列的二维数组b[M][N]中，若按列优先存储，则

b[i][j]的存储地址= LOC + ( j*M+ i ) * sizeof(ElemType)

b[i][j]存储地址 = 起始地址LOC ➕ [列号 ✖ 每一列有多少个数据元素 + 行号](即前面有多少元素) ✖ 数据元素大小(前面的总数据元素大小)

普通矩阵的存储

• 对于普通矩阵可以用二维数组存储

注意：描述矩阵元素时，行、列号通常从1开始；
而描述数组时通常下标从0开始

• 某些特殊矩阵可以压缩存储空间

对称矩阵的压缩存储

若n阶方阵中任意一个元素ai,ja_{i,j}ai,j​都有ai,j=aj,ia_{i,j} = a_{j,i}ai,j​=aj,i​，
则该矩阵为对称矩阵

普通存储：n*n二维数组

压缩存储策略：只存储主对角线+下三角区
（或主对角线+上三角区）

策略：只存储主对角线+下三角区

• 按行优先原则将各元素存入一维数组中。

思考：

• Q①：数组大小应为多少?
  A①：(1+n)*n/2

第B[?]个元素下标为[(1+n)*n/2] - 1

• Q②：站在程序员的角度，对称矩阵压
  缩存储后怎样才能方便使用？
  A②：可以实现一个“映射”函数
  矩阵下标 -> 一维数组下标

通过矩阵元素下标来访问元素

如何实现：
对于下三角区(i < j)：

   矩阵下标   ->  一维数组下标
ai,j(i≥j)a_{i,j} (i≥j)ai,j​(i≥j) -> $B[k]$

Key：按行优先的原则，ai,ja_{i,j}ai,j​是第几个元素？

$[1+2+\cdot \cdot \cdot +(i-1)]+j$ -> 第i(i−1)2+j\\frac{i\\left( i-1 \\right)}{2}+j2i(i−1)​+j个元素

                               -> 数组下标：k=i(i−1)2+j−1k=\\frac{i\\left( i-1 \\right)}{2}+j-1k=2i(i−1)​+j−1

对于上三角区(i ≤ j)：

ai,j=aj,ia_{i,j} = a_{j,i}ai,j​=aj,i​（对称矩阵性质）

所以可以推导出：
k={i(i−1)2+j−1,i⩾j(下三角区和主对角线元素)j(j−1)2+i−1,i<j(上三角区元素ai,j=aj,i)k=\\begin{cases} \\frac{i\\left( i-1 \\right)}{2}+j-1,& i\\geqslant j\\left( \\text{下三角区和主对角线元素} \\right)\\\\ \\frac{j\\left( j-1 \\right)}{2}+i-1,& i<j\\left( \\text{上三角区元素}a_{i,j}=a_{j,i} \\right)\\\\ \\end{cases} k={2i(i−1)​+j−1,2j(j−1)​+i−1,​i⩾j(下三角区和主对角线元素)i<j(上三角区元素ai,j​=aj,i​)​

• 按列优先原则将各元素存入一维数组中。

   矩阵下标   ->  一维数组下标
ai,j(i<j)a_{i,j} (i<j)ai,j​(i<j) -> $B[k]$

ai,j=aj,ia_{i,j} = a_{j,i}ai,j​=aj,i​（对称矩阵性质）

ai,ja_{i,j}ai,j​的第j列之前应该还有(1 ~ j - 1)列，第一列n个元素，第二列n-1个元素……把每一列元素加起来，再加上行号i-列号j找到在这一列之前还有多少元素。

ai,ja_{i,j}ai,j​是第几个元素？

$\left[n+\left(n-1\right)+\cdots +\left(n-j+2\right)\right]+\left(i-j\right)+1$

• 出题方法：
  

三角矩阵的压缩存储

策略：下三角矩阵

下三角矩阵：除了主对角线和下三角区，其余的元素都相同

压缩存储策略：按行优先原则将橙色区元素存入一维数组中。并在最后一个位置存储常量c

相比对称矩阵，存储同阶的三角矩阵需要多一个存储单元存储常量c

   矩阵下标   ->  一维数组下标
ai,j(i≥j)a_{i,j} (i≥j)ai,j​(i≥j) -> $B[k]$

Key：按行优先的原则，ai,ja_{i,j}ai,j​是第几个元素？
k={i(i−1)2+j−1,i⩾j(下三角区和主对角线元素)n(n+1)2,i<j(上三角区元素常量c)k=\\begin{cases} \\frac{i\\left( i-1 \\right)}{2}+j-1,& i\\geqslant j\\left( \\text{下三角区和主对角线元素} \\right)\\\\ \\frac{n\\left( n+1 \\right)}{2},& i<j\\left( \\text{上三角区元素常量}c \\right)\\\\ \\end{cases} k={2i(i−1)​+j−1,2n(n+1)​,​i⩾j(下三角区和主对角线元素)i<j(上三角区元素常量c)​

策略：下三角矩阵

上三角矩阵：除了主对角线和上三角区，其余的元素都相同

压缩存储策略：按行优先原则将绿色区元素存入一维数组中。并在最后一个位置存储常量c

   矩阵下标   ->  一维数组下标
ai,j(i≤j)a_{i,j} (i≤j)ai,j​(i≤j) -> $B[k]$

Key：按行优先的原则，ai,ja_{i,j}ai,j​是第几个元素？

k={(i−1)(2n−i+2)2+(j−i),i⩽j(下三角区和主对角线元素)n(n+1)2,i>j(上三角区元素常量c)k=\\begin{cases} \\frac{\\left( i-1 \\right) \\left( 2n-i+2 \\right)}{2}+\\left( j-i \\right) ,& i\\leqslant j\\left( \\text{下三角区和主对角线元素} \\right)\\\\ \\frac{n\\left( n+1 \\right)}{2},& i>j\\left( \\text{上三角区元素常量}c \\right)\\\\ \\end{cases} k={2(i−1)(2n−i+2)​+(j−i),2n(n+1)​,​i⩽j(下三角区和主对角线元素)i>j(上三角区元素常量c)​

三对角矩阵的压缩存储

三对角矩阵，又称带状矩阵：
当$|i-j|>1$时，有ai,j=0（1≤i,j≤n）a_{i,j} = 0 （1≤ i, j ≤n）ai,j​=0（1≤i,j≤n）

主对角线相邻，非0元素；与主对角线的差值大于1，都是0

         矩阵下标       ->  一维数组下标
ai,j(∣i−j∣≤1)a_{i,j} (|i - j|≤1)ai,j​(∣i−j∣≤1) -> $B[k]$

压缩存储策略：
按行优先（或列优先）原则，只存储带状部分
第一行和最后一行有两个元素，其他行都是三个元素

Key：按行优先的原则，ai,j是第几个元素？

前$i-1$行共$3(i-1)-1$个元素
ai,ja_{i,j}ai,j​是$i$行第$j-i+2$个元素
ai,ja_{i,j}ai,j​是第$2i+j-2$个元素
$$\to k=2i+j-3$$

数组下标从0开始

Q：
A：

稀疏矩阵的压缩存储

稀疏矩阵：非零元素远远少于矩阵元素的个数

策略一：顺序存储

顺序存储——三元组<行，列，值>

想要访问其中的某一个元素，只能顺序的依次扫描每个元素，失去随机存 取特性

策略二：十字链表法

知识回顾与重要考点

3.4.1~3.4.4_特殊矩阵的压缩存储