关键问题
如何确定一维数组的大小？ = 所需空间
如何确定矩阵元素在一维数组中的位 1 置？从而保证对矩阵元素的随机存取 2
Aij的位置 = 该元素前的元素个数 3 3
12345
4
23456
5
4
34567
5
45678
6
56789
7
…
1 . 对称矩阵
1
1 2 3 4 5 如何确定一维数组的大小？ 2
8
9
程序员试题
2019-1 对矩阵压缩存储的主要目的是__(5)__。 (5) A．方便运算 B．节省存储空间
C．降低计算复杂度 D．提高运算速度
2019 将一个三对角矩阵A[l..100，1..100]中的元素按行 存储在一维数组B[l..298]中，矩阵A中的元素A[66,65]在 数组B中的下标为___(4)___。
行指针
029000 0 1^
000000 2
-3 0 0 0 0 4 3 0 0 24 0 0 0 4
5
0 18 0 0 0 0
0 12
2 0 -3 ^ 3 2 24 ^ 4 1 18 ^ 5 0 15 ^
0 29^ 2 54^
5 3 -7 ^
15 0 0 -7 0 0
3.十字链表
i
j Val/Next
a a m-1 0 m-1 1 ……
a m-1 n-1
内存
a0
0 …
a0
n
a1
0
… a1
n
…
假设数组各维的下界是1,按“行优先顺序”存储,假 设每个元素占用d个存储单元。
二维数组Amn， aij的地址计算函数为： LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*d
三维数组Amnp，aijk的地址计算函数为： LOC(aijk)=LOC(a111)+[(i-1)*n*p+(j-1)*p +(k-1)]*d
多维数组
把三维以上的数组称为多维数组， 可有多个直接前驱和多个直接后继 是一种非线性结构。
在C语言中的描述
typedef int datatype;
datatype array1[N];
datatype array2[M][N];
datatype array3[X][Y][Z];
数组一旦被定义，它的维数和维界就不再改 变。因此，数组只有存取元素和修改元素值的 操作。
压缩存储的办法： 只存非零元素。
所需空间：与非零元素的个数和 存储方式有关。
5.2.2 特殊矩阵的压缩存储
矩阵类型 对称矩阵 三角矩阵 对角矩阵
压缩的基本思想：
只存有用的元素 由用二维数组改为用一维数组来存放
说明：
按C语言中规定，下标从0开始 不失一般性，按“行优先顺序”存储
5.2 多维数组的存储
考虑问题的基本出发点：
计算机的内存结构是一维的。因此用一维内存来存多 维数组，就必须按某种次序将数组元素排成线性序列。
数组一旦建立，结构中的元素个数和元素间的关系就 不再发生变化。因此，一般都是采用顺序存储的方法 来表示数组。
两种顺序存储方式
行优先顺序——将数组元素按行排列
32 6
思想一：直接交换a.data中i和j的内容
问题：b.data是一个按列优先顺序存储的稀疏矩阵B
0 2 0 0 Aij=Bji 0 7
056
250
700
060
2.利用三元组表实现转置
120 030 040 006
Aij=Bji
1000 2340 0006
M=4 N=2
i j Aij
T=5
00 1
01 2
11 3
21 4
32 6
M=2 N=4
i j Bij
T=5 0 0 1
01 2
11 3
21 4
23456 34567
N n(n1) 2
3 3 4
4 5 6 7 8 设：存放下三角阵中的元素， 5
5 6 7 8 9 则：如何确定元素Aij在一维 4
数组中的位置？
5
6
i(i1)j 2
当ij,Aij在下三角阵中
Loc(A ) ij
j( j1)i 2
当ij,Aij在上三角阵中 (根据AijAji)
为了节省存储空间， 我们可以对这类矩阵进行压缩 存储。
5.2.1 几种常见的特殊矩阵
对称矩阵
12345 23456
在一个n阶方阵A中，若元素满足下
述性质：aij=aji 0≦i,j≦n-1，则称A 为对称矩阵。
34567 45678 56789
特征：元素关于主对角线对称
压缩存储的办法： 只存矩阵中上三角或下三角中
如何计算数组元素的地址？
按上述两种方式顺序存储的序组，只要知道：
开始结点的存放地址（即基地址）， 维数 每维的上、下界 每个数组元素所占用的单元数，
就可以将数组元素的存放地址表示为其下标的线性函 数。因此，数组中的任一元素可以在相同的时间内存 取，即顺序存储的数组是一个随机存取结构。
如何计算数组元素的地址？ 内存
最基本的原理
Ai1…in的起始地 址
=
第一个元素 的起始地址
〸
该元素前面 的元素个数
╳
单位 长度
程序员试题
2019-1
对于二维数组a[0…4,1…5]，设每个元素占1个存储单
元，且以行为主序存储，则元素a[2,1]相对于数组空
间起始地址的偏移量是___(40)___。
(40)A．5
B．10
C．15
所有的非零元素集中在以主对角线 为中心的带状区域中，
即除了主对角线和主对角线相邻两 侧的若干条对角线上的元素之外， 其余元素皆为零。
压缩存储的办法： 只存对角线上的元素。
存三对角矩阵所需的空间：
N3n2
稀疏矩阵
12005 03000 04000 00600 00080
特征：只有少量非零元素，且非 零元素的分布没有规律。
(6): A.210 (7): A.0 (8): A.Xd+24 (9): A.Xd+29 (10):A.Xd+186
B.240
C.288
B.6
C.94
B.Xd+72 C.Xd+78
B.Xd+77 C.Xd+83
B.Xd+234 C.Xd+270
D.294 D.100
D.Xd+144 D.Xd+147
在PASCAL、C语言中，数组就是按行优先顺序存储的。
列优先顺序——将数组元素按列向量排列
在FORTRAN语言中，数组就是按列优先顺序存储的。
推广到多维数组的情况：
行优先顺序：先排最右下标，从右到左，最后排最左下标 列优先顺序：先排最左下标，从左向右，最后排最右下标。
计算机如何实现数组元素的随机存取？
(4) A．195 B．196 C．197 D．198
5.2.3 稀疏矩阵的压缩存储 顺序存储：三元组表 链式存储：十字链表
1.三元组表存稀疏矩阵
12005
03000 M=5
04000
N=5
T=7
00600
00080
考虑：
只存非零元素
一个非零元素的必需信息有： (i, j, aij)
记录一个稀疏矩阵的必需信息有： 行数M，列数N，非零元素个数T
D.Xd+276
(6)C (7)D (8)B (9)B (10)D
5.2 矩阵的压缩存储
在编程时，简单而又自然的方法，是将矩阵描述为 一个二维数组。矩阵在这种存储表示之下，可以对 其元素进行随机存取。
但是在一些特殊矩阵中，非零元素呈某种规律分布 或者矩阵中有大量的零元素，如果仍用二维数组存， 会造成极大的浪费，尤其是处理高阶矩阵的时候。
D．25
2019
设数组a[3..16，5..20]的元素以列为主序存放，每个元素 占用两个存储单元，则数组元素a[i,j](3≤i≤16，5≤j≤20)的 地址计算公式为___(11)___。
(11)A．a-118+2i+28j
B．a-116+2i+28j
C．a-144+2i+28j
D．a-146+2i+28j
i j Aij 00 1 01 2 04 5 11 3 21 4 32 6 43 8
三元组表的C语言描述
#define maxsize 10000
typedef int datatype; typedef struct{ /*三元组结点*/
i jV
int i,j;
datatype v;
}TriTupleNode;
有一个直接前驱和一个直接后继
二维数组
二维数组可以看成是向量的推广。
有两个直接前驱和两个直接后继
a 00
a 01
……
a 0n-1
a 10
a 11
……
a 1n-1
………………………….
A=
a m -1 0
a m -1 1 … …
a m -1 n-1
三维数组 最多可有三个直接前驱和三个直接后继
的元素。
所需空间：Nn1(i1)n(n1)
i0
2
三角矩阵
12345 03456 00567 00078 00009
12345 43456 44567 44478 44449
10000 23000 36500 47970 58129
14444 23444 36544 47974 58129