知识点

1.数组的顺序存储

一维数组：

一维数组可看成是一个线性表或一个向量，存储在一块连续的存储单元中，适合于随机查找。
一维数组记为A[n]或A=(a₀，al，…ai，…，an-1) ，一维数组中ai的存储地址LOC(ai)可由下式求出：

LOC(ai)=LOC(a₀)+i*L (0≤i<n)

二维数组

二维数组，又称矩阵(matrix)。每个元素又是一个定长的线性表（一维数组），都要受到两个关系即行关系和列关系的约束，也就是每个元素都同属于两个线性表。
例如，设A是一个有m行n列的二维数组，A可以看成由m个行向量组成的向量，也可以看由n个列向量组成的向量。

一个二维数组可以看作是每个数据元素类型相都同的一维数组。以此类推，任何多维数组都可以看作一个线性表，这时线性表中的每个数据元素也是一个线性表。多维数组是特殊的线性表，是线性表的推广。

应用：

步骤：(注意：数组的下标起始值为0的话，i=i-1,j=j-1;为1的话默认)

1. 以行序为主序：
   • Loc(i,j) = Loc(0,0) + (i×n+j)×L
2. 以列序为主序：
   • Loc(i,j) = Loc(0,0) + (j×m+i)×L

二维数组转一维数组
该表格包含下标从 1 开始和下标从 0 开始两种常见情况，二维数组设为m行n列（行范围A[i])，列范围A[*,j]，一维数组为B[k]。

存储方式	二维数组下标起始	一维数组下标起始	二维元素(A[i,j])对应一维下标k的公式
行优先	(i:1~ m, j:1 ~ n)	(k:1~ m×n)	(k=(i-1)×n + j)
行优先	(i:0 ~ m-1, j:0 ~ n-1)	(k:0~ m×n-1)	(k=i×n + j)
列优先	(i:1 ~ m, j:1~ n)	(k:1~ m×n)	(k=(j-1)×m + i)
列优先	(i:0 ~ m-1, j:0 ~ n-1)	(k:0~ m×n-1)	(k=j×m + i)

2.特殊矩阵的压缩存储

对称矩阵：

n阶对称矩阵 a_ij=a_ji

对称矩阵上下三角中的元素均为：n(n+1)/2

三元组存储稀疏矩阵：

还有一种方式来表示稀疏矩阵那就是：十字链表

练习题

一、 单选题

1.题目： 数组 A[0..4, -1..-3, 5..7] 中含有元素的个数（　　）。
A. 55
B. 45
C. 36
D. 16

2.题目： 一个二维数组 A[10][20] 按行存放于一个连续的存储空间中，A[0][0] 的存储地址是 200，每个数组元素占 1 个字节，则 A[6][2] 的地址为（　　）。
A. 226
B. 322
C. 341
D. 342

3.题目： 设有数组 A[i,j]，数组的每个元素长度为 3 字节，i 的值为 1 到 8，j 的值为 1 到 10，数组从内存首地址 A 开始顺序存放，当以列为主存放时，元素 A[5,8] 的存储首地址为（　　）。
A. BA + 141
B. BA + 180
C. BA + 222
D. BA + 225

4.题目： 多维数组实际上是由（　　）实现的。
A. 一维数组
B. 多项式
C. 三元组表
D. 简单变量

5.题目： 假设以行序为主序存储二维数组 A=array[1..100,1..100]，设每个数据元素占 2 个存储单元，基地址为 10，则 LOC[5,5] =（　　）。
A. 808
B. 818
C. 1010
D. 1020

6.题目： 对稀疏矩阵进行压缩存储的目的是（　　）。
A. 便于进行矩阵运算
B. 便于输入和输出
C. 节省存储空间
D. 降低运算的时间复杂度

7.题目： 稀疏矩阵常用的压缩存储方法有（　　）。
A. 二维数组
B. 三元组和散列表
C. 三元组和十字链表
D. 散列表和十字链表

8.题目： 设一个稀疏矩阵有 1000 行 850 列，其中有 1000 个非 0 元素。设每个整数占 2B，数据占 4B，则用三元组表存储该矩阵时所需字节数是（　　）。
A. 1000
B. 4000
C. 8000
D. 18000

9.题目： 一个稀疏矩阵采用压缩后，和直接采用二维数组存储相比会失去（　　）特性。
A. 顺序存储
B. 随机存取
C. 输入输出
D. 以上都不对

10.题目：直接采用二维数组存储相比采用压缩存储具有（）的特性。
A. 顺序存储
B. 随机存取
C. 输入输出
D. 以上都不对

11.题目：设有一个 $10\times 10$ 的对称矩阵 $A$A，采用压缩存储方式，以行序为主存储，$a_{00}$a00​ 为第一元素，其存储地址为1，每个元素占一个地址空间，$a_{74}$a74​ 的地址是33，则 $a_{47}$a47​ 的地址为（ ）。
A. 13
B. 32
C. 33
D. 40

12.题目：从（ ）复杂度的角度考虑，对稀疏矩阵进行压缩存储。
A. 时间
B. 时间和空间
C. 空间
D. 既不是时间也不是空间

13.题目：有一个 $100\times 90$ 的稀疏矩阵，非0元素有10个；设每个整型数占2个字节，则用三元组表示该矩阵时，所需的字节数是（ ）。
A. 60
B. 66
C. 18000
D. 33

二、填空题

1.题目： 通常采用 （1） 存储结构来存放数组。对二维数组可有两种存储方法：一种是以 （2） 为主序的存储方式，另一种是以 （3） 为主序的存储方式。

2.题目： 稀疏矩阵的压缩方法是只存储 （1） 元素，常用的方法是 （2） 表示法。

3.题目： 对稀疏矩阵进行三元组表示时，需要存储多少个元素？（见图片，图中矩阵有 4 个非零元素）

4.题目： 已知稀疏矩阵如下（假设行列下标均从 0 开始），试写出该稀疏矩阵的三元组表示时第二行的数据（数据直接无空格）。
（矩阵示例中第二行：行下标 1，列下标 2，元素值 3）

5.题目： 在稀疏矩阵的存储中，三元组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 （1） 、 （2） 和 （3） 。

6.题目：将一个 $A[\mathrm{0..9}\text{，}\mathrm{0..9}]$A[0..9，0..9] 的三对角矩阵，按行优先存入一维数组 $B[\mathrm{0..27}]$B[0..27] 中，$A$A 中元素 $A_{5,6}$A5,6​（即该元素下标 $i=5,j=6$i=5,j=6），在 $B$B 数组中的下标为 ____。

7.题目：数组 A 中，每个元素A[i,j]的长度均为 32个二进制位，行下标从-1~9, 列下标从 1 ~11, 从首地址S 开始连续存放在主存储器中， 主存储器字长为 16 位。求：

• 心存放该数组 所需多少单元？
• 存放数组第4列所有元素至少需多少单元？
• 数组按行存放时， 元素A[7,4]的起始地址是多少？
• 数组按列存放时， 元素 A[4, 7]的起始地址是多少？

答案解析

一、 单选题解析

1.B -要清楚下标的表示，0..4就是下标从0到4，是5页（面），同理，数组有3行，有3列，所以共有5*3*3=45个元素

2.B -以行序为主，则LOC[6,2]=[(6-0)*20+(2-0)]*1+base=122+200。一是注意行主序，二是注意下标的开始值默认是0。

3.B -以列序为主，则LOC[5,8]=[（8-1）8+(5-1)]3+BA=BA+180。一是注意列主序，二是注意下标的开始值

4.A -多维数组都可以看成是一个一维数组，比如二维数组可以看成是一个一维数组，而里面的每个元素又都是一个一维数组

5.B -行优先地址：10 + [(5-1)×100+(5-1)]×2 = 818。

6.C -稀疏矩阵中非0元素较少，为节省存储空间，我们只存储其中的非0元素。

7.C -稀疏矩阵常用的压缩存储方法有稀疏矩阵常用的压缩存储方法两种。

8.C –
三元组表法存储稀疏矩阵中的非0元素，该题中有1000个非0元素，每个元素是一个三元组，包含行号、列号和元素值，行号、列号都是整数，占4个字节，元素值占4个字节，也就是每个三元组占8个字节，1000个非0元素共占8000个字节。

9.B
-二维数组可以用行下标和列下标快速定位到一个元素，即随机存取，但压缩存储后，只存储其中的非0元素，每个元素通过三元组存储在新的一维数组中，没法快速定位到其中的一个元素，即失去了原有随机存取的特性

10.B
-二维数组可以用行下标和列下标快速定位到一个元素，即随机存取，但压缩存储后，只存储其中的非0元素。每个元素通过三元组存储在新的一维数组中，没法快速定位到其中的一个元素，即失去了原有随机存取的特性。

11.C
– a74​ 应处于矩阵下三角，前面是7行，一共有 $7\times (7+1)\mathrm{/}2=28$7×(7+1)/2=28 个元素，再看本行，$a_{74}$a74​ 前面有4个元素，所以 $a_{74}$a74​ 前面一共有 $28+4=32$28+4=32 个元素，地址为 $32\times 1+1=33$32×1+1=33。由于是对称矩阵，$a_{47}=a_{74}$a47​=a74​，所以 $a_{47}$a47​ 的地址也是 33。

12.C -对稀疏矩阵进行压缩存储从空间复杂度的角度，为了节省存储空间。

13.B -三元组存储总字节：10×(2+2+2)+3×2=66B。

二、填空题解析

1.答案：
(1) 顺序 (2) 行 (3) 列
解析：数组里的元素个数一般比较固定，少有插入或删除操作，所以选择顺序存储比较适合。二维数组的存储一种是行主序，即一行一行的存储，一种是列主序，即一列一列的存储。

2.答案：
(1) 非零
(2) 三元组
解析：稀疏矩阵中0元素较多，为节省存储空间，所以我们只存储其中的非0元素；常用的方法是三元组法，存元素的行下标、列下标以及元素值，即所谓的三元组。

3.答案： 4
解析：稀疏矩阵进行三元组表示时只存储其中的非0元素。

4.答案：123
解析：第二行只有一个非0元素，行下标为1，列下标为2，元素值为3，所以三元组为123

5.答案：
(1) 行
(2) 列
(3) 值

6.答案：16
解析：矩阵的下标是从0开始的，$A_{5,6}$A5,6​ 之前有 $5-0=5$5−0=5 行，由三对角阵的特点第1行2个元素，后续每行3个元素，所以前5行共 $3\times 4+2=14$3×4+2=14 个元素，$A_{5,6}$A5,6​ 这一行该元素之前有 $A_{5,4}\text{、}{A}_{5,5}$A5,4​、A5,5​ 两个元素，所以 $A_{5,6}$A5,6​ 前面一共 $14+2=16$14+2=16 个元素，$B$B 数组下标是从0开始的，所以最终下标为 16。

7.答案：
(1) 242
(2) 22
(3) S+182
(4) S+142