第５章 数组与广义表第
５
章数组与广义表一、数组
数组的定义
– 数组是以同型元素为数据元素的线性表。
– 数组以下标作为元素的标识，通过下标访问各个元素。
多维数组
– 多维数组是以同型线性表为数据元素的线性表。
– 这里的同型指得是具有相同元素类型和相同的表长。
第
５
章数组与广义表
M[0][0][0]
M[0][3][2]
M[0]
M[1]
M[2]
M[3]
M[0][3]
以一个 3维数组 M[4][5][3]为例，如下图所示：
第
５
章数组与广义表一、数组
多维数组的实现
–用一维顺序结构线性表实现多维数组
struct Array
{
ElemType *buffer; // 数据区
int dims; // 维数
int *L; // 各维长度
};
第
５
章数组与广义表设一 3维数组 A[4][2][3]，
存贮在一个顺序线性表 S中，
结构如下所示：
0 1 2 3 4 5 6 7,.,22 23
A000 A001 A002 A010 A011 A012 A100 A101,.,A311 A312
A312A311A310
A302A301A300
A212A211A210
A202A201A200
A112A111A110
A102A101A100
A012A011A010
A002A001A000
A312A311A310
A302A301A300
A212A211A210
A202A201A200
A112A111A110
A102A101A100
A012A011A010
A002A001A000
第
５
章数组与广义表一、数组
一维下标与多维下标之间的换算
– 设多维数组 A(l0,l1,..,ln-1)，存贮在一个顺序线性表 S中。
从一维下标换算到多维下标
– S(i)? A(i0,i1,..,in-1)
从多维下标换算到一维下标
– A(i0,i1,..,in-1)? S(i)
第
５
章数组与广义表一、数组
多维数组的基本操作
–初始化和撤销
–按下标访问元素 A( i0,i1,i2,.,in-1 )
第
５
章数组与广义表二、稀疏矩阵
定义
– 含有较多零元的矩阵称为稀疏矩阵。
稀疏矩阵的压缩存贮
– 只存贮非零元，以减少存贮空间。
001000
703000
040000
000020
110500
第
５
章数组与广义表二、稀疏矩阵
特殊矩阵
–非零元的分布非常有规律。
–将非零元存贮于一维空间中，根据非零元的分布规律建立矩阵行列与一维下标之间的映射关系。
第
５
章数组与广义表?
1,12,11.10,1
222120
1110
00
0
00
000
nnnnn
aaaa
aaa
aa
a

0 1 2 3 4 5,.,n(n+1)/2-1
a00 a10 a11 a20 a21 a22,.,an-1,n-1
以三角阵为例：
i
j
jijiijiI n d e x 2 )1(),(
第
５
章数组与广义表二、稀疏矩阵
三元组法
080000
000000
2511000
007000
050020
row col data
0 0 1 2
1 0 4 5
2 1 3 7
3 2 3 11
4 2 4 5
5 2 5 2
6 4 4 8
mu:5
nu:6
tu:7
第
５
章数组与广义表二、稀疏矩阵
三元组法
–矩阵转置
080000
000000
2511000
007000
050020
00200
80505
001170
00000
00002
00000
第
５
章数组与广义表
080000
000000
2511000
007000
050020 row col data
0 0 1 2
1 0 4 5
2 1 3 7
3 2 3 11
4 2 4 5
5 2 5 2
6 4 4 8
mu:5
nu:6
tu:7
00200
80505
001170
00000
00002
00000
row col data
0 1 0 2
1 3 1 7
2 3 2 11
3 4 0 5
4 4 2 5
5 4 4 8
6 5 2 2
mu:6
nu:5
tu:7
第
５
章数组与广义表
row col data
0 0 1 2
1 0 4 5
2 1 3 7
3 2 3 11
4 2 4 5
5 2 5 2
6 4 4 8
row col data
0 1 0 2
1 3 1 7
2 3 2 11
3 4 0 5
4 4 2 5
5 4 4 8
6 5 2 2
rpos
0 0
1 0
2 1
3 1
4 3
5 6
rsum
0 0
1 1
2 0
3 2
4 3
5 1
方法 1：先转置复制，再排序方法 2：对目标矩阵逐行扫描方法 3：用行向量指导转置第
５
章数组与广义表二、稀疏矩阵
带行向量的三元组法
080000
000000
2511000
007000
050020
row col data
0 0 1 2
1 0 4 5
2 1 3 7
3 2 3 11
4 2 4 5
5 2 5 2
6 4 4 8
mu:5
nu:6
tu:7
rpos
0 0
1 2
2 3
3 3
4 6
第
５
章数组与广义表二、稀疏矩阵
带行向量的三元组法
– 矩阵乘法
pmpnnm CBA

n
k
kjikij bac
1
第
５
章数组与广义表

ninii
n
k
kiki babababac?2211
1
mpmm
p
p
npnn
p
p
mnmm
n
n
ccc
ccc
ccc
bbb
bbb
bbb
aaa
aaa
aaa



21
22221
11211
21
22221
11211
21
22221
11211
mpmm
p
p
npnn
p
p
mnmm
n
n
ccc
ccc
ccc
bbb
bbb
bbb
aaa
aaa
aaa



21
22221
11211
21
22221
11211
21
22221
11211
+++

n
k
kjikij bac
1
第
５
章数组与广义表
ipii
npnn
p
p
inii ccc
bbb
bbb
bbb
aaa?

21
21
22221
11211
21?




ipii
npnnin
pi
pi
ccc
bbba
bbba
bbba
21
21
222212
112111

n
k
kiki bac
1
第
５
章数组与广义表二、稀疏矩阵
十字链表法
080000
000000
2511000
007000
050020
∧∧
543210
4
3
2
1
0
∧
∧
∧2 ∧5
∧7
∧
11
∧
∧2
∧
∧8
5
第
５
章数组与广义表三,广义表
广义表的定义
– 广义表
– 子表
– 原子
– 广义表的深度
((a),(b,()),((c,d),e),f,())
() (())
第
５
章数组与广义表三,广义表
广义表的实现
–头尾链表法
表头
表尾第
５
章数组与广义表
((a),(b,(c)),e)
((a),(b,(c)),e)1
1 ∧ 1
0 a 1 1 ∧
0 e0 b 1 ∧
1 ∧
0 c
(a)
((b,(c)),e)
(b,(c)) (e)
((c))
(c)
第
５
章数组与广义表
() (())
∧
1 ∧ ∧
((),())
((),())1 ∧
1 ∧ ∧ (())
第
５
章数组与广义表三,广义表
广义表的实现
–扩展线性表法第
５
章数组与广义表
((a),(b,(c)),e)1 1 0 e
∧
1 ∧0 b
0 c ∧
0 a ∧
()
(())
((),())
∧
1 ∧ ∧
1 ∧ ∧1 ∧
第
５
章数组与广义表三,广义表
广义表的运算
–广义表的深度
–广义表的复制