github中有详尽代码可作参考

返回目录

数组的存储结构

• 一维数组

设一维数组为 $a[0,\cdots,n-1]$(即有 $n$个元素,下标从 $0$到 $n-1$),类型为 $ElemType$(长度为 $L$), $a_i$的存放地址为 $LOC(a_i)=LOC(a_0)+L\times i$ ,此处 $0 \le i \le n-1$;

如果询问是第 $j$个元素(从 $1$到 $n$,注意和下标的差别,与下标相差 $1$),此时第 $j$个元素的存放地址为 $LOC(a_{j-1})=LOC(a_0)+L\times (j-1)$,此处 $1\le j \le n$

• 二维数组

行优先(内存地址中一行一行的放,平常使用较多)

设二维数组为 $b[0,\cdots,n-1][0,\cdots,m-1]$(即有 $n\times m$个元素,行下标从 $0$到 $n-1$,列下标从 $0$到 $m-1$),类型为 $ElemType$(长度为 $L$), $a_{i,j}$的存放地址为 $LOC(a_{i,j})=LOC(a_{0,0})+(i \times m + j) \times L$,偏移量是 $\color{Red}{i\times m +j}$(说明前面有 $i$行,每行有 $m$个,当前行的第 $j$个)

列优先(内存地址中一列一列的放)

设二维数组为 $b[0,\cdots,n-1][0,\cdots,m-1]$(即有 $n\times m$个元素,行下标从 $0$到 $n-1$,列下标从 $0$到 $m-1$),类型为 $ElemType$(长度为 $L$), $a_{i,j}$的存放地址为 $LOC(a_{i,j})=LOC(a_{0,0})+(j \times n + i) \times L$,偏移量是 $\color{Red}{j\times n +i}$(说明前面有 $j$列,每列有 $n$个,当前列的第 $i$个)

计算公式: $\color{Orange}{LOC(a_{i,j})=LOC(第一个元素)+(a_{i,j}前面的元素个数)*每个元素所占用字节}$

特殊矩阵的压缩存储

对称矩阵

在 $n$阶矩阵 $A$中,任意一个元素 $a_{i,j}$,都有 $a_{i,j}=a_{j,i}$（ $1 \le i,j \le n$,注意此处不是下标),称为对称矩阵。它分为三个区域(分别是上三角区( $i < j$),下三角区 ( $i > j$)和主对角线 $i=j$),若要进行压缩,只需要存储上(或下)三角区和主对角线即可,压缩后的元素个数为 $\frac{n(n+1)}{2}$(假设以下三角区和主对角线为例,第一行需要存储 $1$个,第二行需要存储 $2$个,第 $i$行需要存储 $i$个,是个等差数列求和),将其映射成一维数组.

1.行优先且以下三角区和主对角线为核心

• 第一行 $1$个元素;
• 第二行 $2$个元素;
• $\cdots$;
• 第 $i-1$行 $i-1$个元素;
• 第 $i$行 $i$个元素.

若想求出对应的 $a_{i,j}$( $i \geq j$)的映射一维数组下标(此处下标是从 $0$开始的),先计算出 $a_{i,j}$前面有多少个元素(前 $i-1$行总共有 $\frac{(i-1+1)(i-1)}{2}=\frac{i(i-1)}{2}$个元素,第 $i$行有 $j-1$个元素);

若想求出对应的 $a_{i,j}$( $i < j$)的映射一维数组下标(此处下标是从 $0$开始的),先计算出 $a_{i,j}$前面有多少个元素(由于对称矩阵可看作是 $i,j$进行交换);

整理得:

2.行优先且以上三角区和主对角线为核心

• 第一行 $n$个元素;

• 第二行 $n-1$个元素;

• $\cdots$

• 第 $i-1$行 $n+1-(i-1)=n+2-i$个元素;

• 第 $i$行 $n+1-i$个元素.

若想求出对应的 $a_{i,j}$( $i \leq j$)的映射一维数组下标(此处下标是从 $0$开始的),先计算出 $a_{i,j}$前面有多少个元素(前 $i-1$行总共有 $\frac{(n+n+2-i)(i-1)}{2}=\frac{(2n-i+2)(i-1)}{2}$个元素,第 $i$行有 $j-i$个元素);

若想求出对应的 $a_{i,j}$( $i > j$)的映射一维数组下标(此处下标是从 $0$开始的),先计算出 $a_{i,j}$前面有多少个元素(由于对称矩阵原因可看作是 $i,j$进行交换);

整理得:

3.列优先且以下三角区和主对角线为核心

• 第一列 $n$个元素;
• 第二列 $n-1$个元素;

• $\cdots$

• 第 $j-1$列 $n+1-(j-1)=n+2-j$个元素;

• 第 $j$列 $n+1-j$个元素.

若想求出对应的 $a_{i,j}$( $i \geq j$)的映射一维数组下标(此处下标是从 $0$开始的),先计算出 $a_{i,j}$前面有多少个元素(前 $j-1$列总共有 $\frac{(n+n+2-j)(j-1)}{2}=\frac{(2n-j+2)(j-1)}{2}$个元素,第 $j$列有 $i-j$个元素);

若想求出对应的 $a_{i,j}$( $i < j$)的映射一维数组下标(此处下标是从 $0$开始的),先计算出 $a_{i,j}$前面有多少个元素(由于对称矩阵原因可看作是 $i,j$进行交换);

整理得:

4.列优先且以上三角区和主对角线为核心

• 第一列 $1$个元素;
• 第二列 $2$个元素;
• $\cdots$;
• 第 $j-1$列 $j-1$个元素;
• 第 $j$列 $j$个元素.

若想求出对应的 $a_{i,j}$( $i \leq j$)的映射一维数组下标(此处下标是从 $0$开始的),先计算出 $a_{i,j}$前面有多少个元素(前 $j-1$列总共有 $\frac{(j-1+1)(j-1)}{2}=\frac{j(j-1)}{2}$个元素,第 $j$列有 $i-1$个元素);

若想求出对应的 $a_{i,j}$( $i > j$)的映射一维数组下标(此处下标是从 $0$开始的),先计算出 $a_{i,j}$前面有多少个元素(由于对称矩阵可看作是 $i,j$进行交换);

整理得:

三角矩阵

三角矩阵分为两种,分别是上三角矩阵(下三角区的所有元素均为常量)和下三角矩阵(上三角区的所有元素均为常量),压缩无非是在对称矩阵压缩条件下再增加一个空间存储另一个区的常量,即压缩后的元素个数为 $\frac{n(n+1)}{2}+1$

• 下三角矩阵

可参考对称矩阵( $1$行优先, $3$列优先)的存储,此处直接给出结论,不作证明

• 上三角矩阵

可参考对称矩阵( $2$行优先, $4$列优先)的存储,此处直接给出结论,不作证明

三对角矩阵

对角矩阵又称为带状矩阵,是指在 $n\times n$的矩阵 $a$中,非零元素集中在主对角线及其两侧,共 $L$(奇数)条对角线的带状区域内,称为 $L$对角矩阵.故三对角矩阵就是 $3$条对角线的带状区域,可发现 当 $\left| i -j \right| > 1$,有 $a_{i,j}=0$,其中 $1\leq i,j \leq n$.压缩后的元素个数是 $3\times n -2$

此处用行优先作例子

• 第一行 $2$个元素;

• 第二行 $3$个元素;

• $\cdots$

• 第 $i-1$行有 $3$个元素;

若想求出对应的 $a_{i,j}$( $\left| i -j \right| \leq 1$)的映射一维数组下标(此处下标是从 $0$开始的),先计算出 $a_{i,j}$前面有多少个元素(前 $i-1$行总共有 $2+3\times (i-2)=3i-4$个元素,第 $i$行有 $j-1-i+2=j-i+1$个元素);

整理得:

特殊考虑第一行代入公式亦成立,即 $pos=2\times i +j -3$.

若已知 $pos$能否求出对应的 $i,j$, $i=\frac{(pos+1)}{3}+1$(可尝试代入 $a_{1,1},a_{1,2},a_{2,1}$体会),同理 $j$可通过上述公式求出 $j=pos-2\times i+3$

稀疏矩阵

设矩阵元素个数为 $m$ ,非零元素的个数为 $n$,其中非零元素极少,即 $n \ll m$,称为稀疏矩阵.只存储非零元素进行空间压缩

• 三元组(行标,列标,值) ——顺序存储

• 十字链表 ——链式存储

$i,j,value$分别代表非零元素所在的行号、列号和相应的元素值； $down$和 $right$分别称为向下指针和向右指针,分别用来链接同列中和同行中的下一个非零元素结点。

3.4.3

有一个 $n\times n$的对称矩阵 $A$，将其下三角部分按行存放在一维数组 $B$中，而 $A[0] [0]$存放于 $B[0]$中，则第 $i+1$行的对角元素 $A[i][i]$存放于 $B$中的()处.

A. $\color{Red}{\frac{(i+3)i}{2}}$

B. $\frac{(i+1)i}{2}$

C. $\frac{(2n-i+1)i}{2}$

D. $\frac{(2n-i-1)i}{2}$

计算 $A_{i,i}$(即矩阵第 $i+1$行的第 $i+1$个元素)前面的元素个数(矩阵前 $i$行共有 $\frac{(i+1)\times i}{2}$, 在矩阵第 $i+1$当前行有 $i$个元素,总共 $\frac{(i+1)\times i}{2}+i=\frac{i^2+3i}{2}=\frac{(i+3)\times i}{2}$)

3.4.4

在一个二维数组 $A$中，假设每个数组元素的长度为 $3$个存储单元，行下标 $i$为 $0 \sim 8$， 列下标 $j$为 $0 \sim 9$，从首地址 $SA$开始连续存放。在这种情况下，元素 $A[8][5]$的起始地址为().

A. $SA+141$

B. $SA+144$

C. $SA+222$

D. $\color{Red}{SA+255}$

二维数组 $A$(有 $9$行, $10$列),套公式 $LOC(a_{i,j})=LOC(a_{0,0})+(i \times m + j) \times L$,代入得 $LOC(a_{8,5})=SA+(8\times 10+5)\times 3=SA+255$

3.4.5

将三对角矩阵 $A[1, \cdots ,100][1, \cdots ,100]$按行优先存入一维数组 $B[1,\cdots,298]$中， $A$中元素 $A[66][65]$在数组 $B$中的位置 $k$为().

A. $198$

B. $\color{Red}{195}$

C. $197$

D. $196$

注意 $B$数组下标是从 $1$开始的,套用三对角矩阵的结论(适用于 $B$数组下标从 $0$开始), $pos=2\times i +j -3$,故 $k=pos+1=2\times i + j -2$,代入得: $2\times 66 +65-2=132+63=195$.

3.4.6

若将 $n$阶上三角矩阵 $A$按列优先级压缩存放在一维数组 $B[1,\cdots,\frac{n(n+1)}{2}+1]$中，则存放到 $B[k]$中的非零元素 $a_{i,j}$ ( $1\leq i,j \leq n$)的下标 $i$、 $j$与 $k$的对应关系是().

A. $\frac{i(i+1)}{2}+j$

B. $\frac{i(i-1)}{2}+j-1$

C. $\color{Red}{\frac{j(j-1)}{2}+i}$

D. $\frac{j(j-1)}{2}+i-1$

套上三角矩阵结论和k=pos+1思想

最终结果为 $pos=\frac{j(j-1)}{2}+i-1$, $k=pos+1=\frac{j(j-1)}{2}+i$

3.4.7

若将 $n$阶下三角矩阵 $A$按列优先级压缩存放在一维数组 $B[1,\cdots,\frac{n(n+1)}{2}+1]$中，则存放到 $B[k]$中的非零元素 $a_{i,j}$ ( $1\leq i,j \leq n$)的下标 $i$、 $j$与 $k$的对应关系是().

A. $\frac{(j-1)(2n-j+1)}{2}+i-j$

B. $\color{Red}{\frac{(j-1)(2n-j+2)}{2}+i-j+1}$

C. $\frac{(j-1)(2n-j+2)}{2}+i-j$

D. $\frac{(j-1)(2n-j+1)}{2}+i-j-1$

套下三角矩阵结论和k=pos+1思想

最终结果为 $pos=\frac{(2n-j+2)(j-1)}{2}+i-j$, $k=pos+1=\frac{(2n-j+2)(j-1)}{2}+i-j+1$

3.4.8

2016统考真题：有一个 $100$阶的三对角矩阵 $M$，其元素 $m_{i,j}$ ( $1\leq i,j \leq 100$),按行优先依次压缩存入下标从 $0$开始的一维数组 $N$中。元素 $m_{30,30}$在 $N$中的下标是().

A. $86$

B. $\color{Red}{87}$

C. $88$

D. $89$

套三对角矩阵公式 $pos=2\times i+j-3=2\times 30+30-3=87$.

3.4.10

2018统考真题：设有一个 $12\times 12$的对称矩阵 $M$,将其上三角部分的元素 $m_{i,j}$( $1\leq i \leq j \leq 12$)按行优先存入 $C$语言的一维数组 $N$中，元素 $m_{6,6}$在 $N$中的下标是() .

A. $\color{Red}{50}$

B. $51$

C. $55$

D. $66$

由于 $m_{6,6}$位于上三角区,套对称矩阵公式得 $pos=\frac{(2n-i+2)(i-1)}{2}+j-i=\frac{20\times 5}{2}=50$

3.4.11

2020统考真题：设有一个 $10\times 10$的对称矩阵 $M$,将其上三角部分的元素 $m_{i,j}$( $1\leq i \leq j \leq 10$)按列优先存入 $C$语言的一维数组 $N$中，元素 $m_{7,2}$在 $N$中的下标是() .

A. $15$

B. $16$

C. $\color{Red}{22}$

D. $23$

由于 $m_{7,2}$位于下三角区,套对称矩阵公式得 $pos=\frac{i(i-1)}{2}+j-1=\frac{7\times 6}{2}+1=22$

3.4.12

已知二维数组 $A$按行优先方法存储，每个元素占用 $1$个存储单元，起始地址 $A[0][0]$为 $100$，若元素 $A[3][3]$的存储地址是 $220$，则元素 $A[5][5]$的存储地址是？

A. $295$

B. $\color{Red}{300}$

C. $301$

D. $306$

由该公式 $LOC(a_{i,j})=LOC(a_{0,0})+(i \times m + j) \times L$得: $LOC(a_{3,3})=220=100+(3\times m+3)\times 1$

解得: $m=39$

因此可求出： $LOC(a_{5,5})==100+(5\times 39+5)\times 1=100+200=300$