第四章 数组数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表
§ 4.1 数组的定义和特点
定义
mnmm
n
n
nm
aaa
aaa
aaa
A
......
...............
......
......
21
22221
11211
数组特点
数组结构固定
数据元素同构
数组运算
给定一组下标，存取相应的数据元素
给定一组下标，修改数据元素的值
( )
( )
( )
( )(
)
(
)
(
)
(
)
(
)
§ 4.2 数组的顺序存储结构
次序约定
以行序为主序
以列序为主序
a11 a12 …….,a 1n
a21 a22 …….,a 2n
am1 am2 …….,a mn
………………….
Loc( aij)=Loc(a11)+[(i-1)n+(j-1)]*l
按行序为主序存放
amn
…….,
am2
am1
……….
a2n
…….,
a22
a21
a1n
…….
a12
a110
1
n-1
m*n-1
n
按列序为主序存放 1
m-
m*n-1
m
……..
2n
1n
……….
m2
……..
12
m1
…….
21
a11 a12 …….,a1n
a21 a22 …….,a2n
am1 am2 …….,amn
………………….
Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l
§ 4.3 矩阵的压缩存储
对称矩阵
jiijj
jijiik
,12/)1(
12/)1(,
a11 a12 …,… ….,a1n
a21 a22 …….,……,a2n
an1 an2 …….,ann
…………………,
a11 a21 a22 a31 a32 an1 ann…..,…...
k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1
按行序为主序：
三角矩阵
a11 0 0 …….,0
a21 a22 0 …….,0
an1 an2 an3…….,ann
…………………,0
Loc(aij)=Loc(a11)+[( +(j-1)]*li(i-1)2
a11 a21 a22 a31 a32 an1 ann…..,…...
k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1
按行序为主序：
对角矩阵
a11 a12 0 ……………,0
a21 a22 a23 0 …………… 0
0 0 … an-1,n-2 an-1,n-1 an-1,n
0 0 … … an,n-1 ann.
0 a32 a33 a34 0 ……… 0
……………………………
Loc(aij)=Loc(a11)+2(i-1)+(j-1)
a11 a12 a21 a22 a23 ann-1 ann…..,…...
k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1
按行序为主序：
7600070015
00000180
00002400
01400003
0000000
00009120
M
M由 {(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),
(5,2,18),(6,1,15),(6,4,-7) } 和矩阵维数（ 6,7）唯一确定
稀疏矩阵
定义：非零元较零元少，且分布没有一定规律的矩阵
压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值
稀疏矩阵的压缩存储方法
顺序存储结构
三元组表 #define M 20typedef struct node
{ int i,j;
int v;
}JD;
JD ma[M];
三元组表所需存储单元个数为 3(t+1)
其中 t为非零元个数
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
ma
i j v
0
1
2
3
4
5
6
7
8
ma[0].i,ma[0].j,ma[0].v分别存放矩阵行列维数和非零元个数行列下标 非零元值 7600070015
00000180
00002400
01400003
0000000
00009120
M
带辅助行向量的二元组表增加一个辅助数组 NRA[m+1],其物理意义是第 i行第一个非零元在二元组表中的起始地址（ m为行数）
显然有,NRA[1]=1
NRA[i]=NRA[i-1]+第 i-1行非零元个数 (i?2)
0
1
2
3
4
5
6
NRA
1
3
3
5
6
7
6 7 8
2 12
3 9
1 -3
6 14
3 24
2 18
1 15
4 -7
ma
j v
0
1
2
3
4
5
6
7
8
矩阵列数和非零元个数列下标和非零元值NRA[0]不用或存矩阵行数二元组表需存储单元个数为 2(t+1)+m+1
7600070015
00000180
00002400
01400003
0000000
00009120
M
伪地址表示法伪地址：本元素在矩阵中（包括零元素再内）
按行优先顺序的相对位置
6 7
2 12
3 9
15 -3
20 14
24 24
30 18
36 15
39 -7
ma
addr v伪地址 非零元值矩阵行列维数0
1
2
3
4
5
6
7
8
伪地址表示法需存储单元个数为 2(t+1)
7600070015
00000180
00002400
01400003
0000000
00009120
M
求转置矩阵
问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表
问题分析一般矩阵转置算法：
for(col=0;col<n;col++)
for(row=0;row<m;row++)
n[col][row]=m[row][col];
T(n)=O(m?n)
7600070015
00000180
00002400
01400003
0000000
00009120
M
67000000
0001400
000000
700000
0024009
01800012
1500300
N
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
i j v
0
1
2
3
4
5
6
7
8
ma
i j v
7 6 8
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
0
1
2
3
4
5
6
7
8
mb
解决思路：只要做到
将矩阵行、列维数互换
将每个三元组中的 i和 j相互调换
重排三元组次序，使 mb中元素以 N的行 (M的列 )为主序方法一：按 M的列序转置即按 mb中三元组次序依次在 ma中找到相应的三元组进行转置。
为找到 M中每一列所有非零元素，需对其三元组表 ma从第一行起扫描一遍。由于 ma中以 M行序为主序,所以由此得到的恰是 mb
中应有的顺序
算法描述,
算法分析,T(n)=O(M的列数 n?非零元个数 t)
若 t 与 m?n同数量级，则 )()( 2nmOnT
Ch4_1.c
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
i j v
0
1
2
3
4
5
6
7
8 ma
7 6 8
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
i j v
0
1
2
3
4
5
6
7
8 mb
kp
p
p
p
p
p
p
p
k
k
k
k
p
p
p
p
p
p
p
p
col=1 col=2
方法二：快速转置即按 ma中三元组次序转置，转置结果放入 b中恰当位置此法关键是要预先确定 M中每一列第一个非零元在 mb中位置，
为确定这些位置，转置前应先求得 M的每一列中非零元个数实现：设两个数组
num[col]：表示矩阵 M中第 col列中非零元个数
cpot[col],指示 M中第 col列第一个非零元在 mb中位置显然有,cpot[1]=1;
cpot[col]=cpot[col-1]+num[col-1]; (2?col?ma[0].j)
1 3 5 7 8 8 9
col
num[col]
cpot[col]
1
2
2
2
3
2
4
1
5
0
6
1
7
0
7600070015
00000180
00002400
01400003
0000000
00009120
M
算法分析,T(n)=O(M的列数 n+非零元个数 t)
若 t 与 m?n同数量级，则 T(n)=O(m?n)
算法描述：
Ch4_2.c
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
i j v
0
1
2
3
4
5
6
7
8 ma
i j v
0
1
2
3
4
5
6
7
8 mb
col
num[col]
cpot[col]
1
1
2
2
3
2
3
5
2
4
7
1
5
8
0
6
8
1
7
9
0
7 6 8
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
p
p
p
p
p
p
p
p
4 62 9
753
链式存储结构
带行指针向量的单链表表示
每行的非零元用一个单链表存放
设置一个行指针数组，指向本行第一个非零元结点；
若本行无非零元，则指针为空
表头结点与单链表结点类型定义typedef struct node
{ int col;
int val;
struct node *link;
}JD;
typedef struct node *TD;
02000
00000
00021
00100
70003
A
^
1 3 5 7
3 -1
1 -1 2 -2
4 2 ^
^
^
^
需存储单元个数为 3t+m
十字链表
设行指针数组和列指针数组，分别指向每行、
列第一个非零元
结点定义
tpedef struct node
{ int row,col,val;
struct node *down,*right;
}JD;
row col val
down right
34008
000
450
003
A
1 1 3
4 1 8
2 2 5 2 3 4
^
^ ^
^
^ ^ ^
从键盘接收信息建立十字链表算法
算法分析,T(n)=o(t?s)
其中,t—— 非零元个数
s= max(m,n)
Ch4_3.c
令 q=NULL,p=rh[r-1],
（ 1） 寻找插入位置,当 p!=NULL且 c>p->col时,p和 q右移
（ 2）插入：
a、若 p==NULL且 q==NULL，即本行空,则 rh[r-1]==s;
b,若 p==NULL,q!=NULL,即走到行末，则 q->right=s
c,若 c==p->col,则修改 p->val
d,若 c<p->col且 q==NULL,则在 p之前插入 s,即 s是行链表中第一个结点，令 rh[r-1]=s; s->right=p;
e,若 c<p->col且 q!=NULL,则在 p之前插入 s，
即 s->right=p; q->right=s;
4 1 8
^ ^
2 3 4
^ ^
m=4,n=3
1,1,3
2,2,5
2,3,4
4,1,8
2,1,7
Ch4_3.c
1 1 3
^^
2 1 7
^ ^
2 2 5
^ ^
§ 4.1 数组的定义和特点
定义
mnmm
n
n
nm
aaa
aaa
aaa
A
......
...............
......
......
21
22221
11211
数组特点
数组结构固定
数据元素同构
数组运算
给定一组下标，存取相应的数据元素
给定一组下标，修改数据元素的值
( )
( )
( )
( )(
)
(
)
(
)
(
)
(
)
§ 4.2 数组的顺序存储结构
次序约定
以行序为主序
以列序为主序
a11 a12 …….,a 1n
a21 a22 …….,a 2n
am1 am2 …….,a mn
………………….
Loc( aij)=Loc(a11)+[(i-1)n+(j-1)]*l
按行序为主序存放
amn
…….,
am2
am1
……….
a2n
…….,
a22
a21
a1n
…….
a12
a110
1
n-1
m*n-1
n
按列序为主序存放 1
m-
m*n-1
m
……..
2n
1n
……….
m2
……..
12
m1
…….
21
a11 a12 …….,a1n
a21 a22 …….,a2n
am1 am2 …….,amn
………………….
Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l
§ 4.3 矩阵的压缩存储
对称矩阵
jiijj
jijiik
,12/)1(
12/)1(,
a11 a12 …,… ….,a1n
a21 a22 …….,……,a2n
an1 an2 …….,ann
…………………,
a11 a21 a22 a31 a32 an1 ann…..,…...
k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1
按行序为主序：
三角矩阵
a11 0 0 …….,0
a21 a22 0 …….,0
an1 an2 an3…….,ann
…………………,0
Loc(aij)=Loc(a11)+[( +(j-1)]*li(i-1)2
a11 a21 a22 a31 a32 an1 ann…..,…...
k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1
按行序为主序：
对角矩阵
a11 a12 0 ……………,0
a21 a22 a23 0 …………… 0
0 0 … an-1,n-2 an-1,n-1 an-1,n
0 0 … … an,n-1 ann.
0 a32 a33 a34 0 ……… 0
……………………………
Loc(aij)=Loc(a11)+2(i-1)+(j-1)
a11 a12 a21 a22 a23 ann-1 ann…..,…...
k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1
按行序为主序：
7600070015
00000180
00002400
01400003
0000000
00009120
M
M由 {(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),
(5,2,18),(6,1,15),(6,4,-7) } 和矩阵维数（ 6,7）唯一确定
稀疏矩阵
定义：非零元较零元少，且分布没有一定规律的矩阵
压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值
稀疏矩阵的压缩存储方法
顺序存储结构
三元组表 #define M 20typedef struct node
{ int i,j;
int v;
}JD;
JD ma[M];
三元组表所需存储单元个数为 3(t+1)
其中 t为非零元个数
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
ma
i j v
0
1
2
3
4
5
6
7
8
ma[0].i,ma[0].j,ma[0].v分别存放矩阵行列维数和非零元个数行列下标 非零元值 7600070015
00000180
00002400
01400003
0000000
00009120
M
带辅助行向量的二元组表增加一个辅助数组 NRA[m+1],其物理意义是第 i行第一个非零元在二元组表中的起始地址（ m为行数）
显然有,NRA[1]=1
NRA[i]=NRA[i-1]+第 i-1行非零元个数 (i?2)
0
1
2
3
4
5
6
NRA
1
3
3
5
6
7
6 7 8
2 12
3 9
1 -3
6 14
3 24
2 18
1 15
4 -7
ma
j v
0
1
2
3
4
5
6
7
8
矩阵列数和非零元个数列下标和非零元值NRA[0]不用或存矩阵行数二元组表需存储单元个数为 2(t+1)+m+1
7600070015
00000180
00002400
01400003
0000000
00009120
M
伪地址表示法伪地址：本元素在矩阵中（包括零元素再内）
按行优先顺序的相对位置
6 7
2 12
3 9
15 -3
20 14
24 24
30 18
36 15
39 -7
ma
addr v伪地址 非零元值矩阵行列维数0
1
2
3
4
5
6
7
8
伪地址表示法需存储单元个数为 2(t+1)
7600070015
00000180
00002400
01400003
0000000
00009120
M
求转置矩阵
问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表
问题分析一般矩阵转置算法：
for(col=0;col<n;col++)
for(row=0;row<m;row++)
n[col][row]=m[row][col];
T(n)=O(m?n)
7600070015
00000180
00002400
01400003
0000000
00009120
M
67000000
0001400
000000
700000
0024009
01800012
1500300
N
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
i j v
0
1
2
3
4
5
6
7
8
ma
i j v
7 6 8
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
0
1
2
3
4
5
6
7
8
mb
解决思路：只要做到
将矩阵行、列维数互换
将每个三元组中的 i和 j相互调换
重排三元组次序，使 mb中元素以 N的行 (M的列 )为主序方法一：按 M的列序转置即按 mb中三元组次序依次在 ma中找到相应的三元组进行转置。
为找到 M中每一列所有非零元素，需对其三元组表 ma从第一行起扫描一遍。由于 ma中以 M行序为主序,所以由此得到的恰是 mb
中应有的顺序
算法描述,
算法分析,T(n)=O(M的列数 n?非零元个数 t)
若 t 与 m?n同数量级，则 )()( 2nmOnT
Ch4_1.c
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
i j v
0
1
2
3
4
5
6
7
8 ma
7 6 8
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
i j v
0
1
2
3
4
5
6
7
8 mb
kp
p
p
p
p
p
p
p
k
k
k
k
p
p
p
p
p
p
p
p
col=1 col=2
方法二：快速转置即按 ma中三元组次序转置，转置结果放入 b中恰当位置此法关键是要预先确定 M中每一列第一个非零元在 mb中位置，
为确定这些位置，转置前应先求得 M的每一列中非零元个数实现：设两个数组
num[col]：表示矩阵 M中第 col列中非零元个数
cpot[col],指示 M中第 col列第一个非零元在 mb中位置显然有,cpot[1]=1;
cpot[col]=cpot[col-1]+num[col-1]; (2?col?ma[0].j)
1 3 5 7 8 8 9
col
num[col]
cpot[col]
1
2
2
2
3
2
4
1
5
0
6
1
7
0
7600070015
00000180
00002400
01400003
0000000
00009120
M
算法分析,T(n)=O(M的列数 n+非零元个数 t)
若 t 与 m?n同数量级，则 T(n)=O(m?n)
算法描述：
Ch4_2.c
6 7 8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
i j v
0
1
2
3
4
5
6
7
8 ma
i j v
0
1
2
3
4
5
6
7
8 mb
col
num[col]
cpot[col]
1
1
2
2
3
2
3
5
2
4
7
1
5
8
0
6
8
1
7
9
0
7 6 8
1 3 -3
1 6 15
2 1 12
2 5 18
3 1 9
3 4 24
4 6 -7
6 3 14
p
p
p
p
p
p
p
p
4 62 9
753
链式存储结构
带行指针向量的单链表表示
每行的非零元用一个单链表存放
设置一个行指针数组，指向本行第一个非零元结点；
若本行无非零元，则指针为空
表头结点与单链表结点类型定义typedef struct node
{ int col;
int val;
struct node *link;
}JD;
typedef struct node *TD;
02000
00000
00021
00100
70003
A
^
1 3 5 7
3 -1
1 -1 2 -2
4 2 ^
^
^
^
需存储单元个数为 3t+m
十字链表
设行指针数组和列指针数组，分别指向每行、
列第一个非零元
结点定义
tpedef struct node
{ int row,col,val;
struct node *down,*right;
}JD;
row col val
down right
34008
000
450
003
A
1 1 3
4 1 8
2 2 5 2 3 4
^
^ ^
^
^ ^ ^
从键盘接收信息建立十字链表算法
算法分析,T(n)=o(t?s)
其中,t—— 非零元个数
s= max(m,n)
Ch4_3.c
令 q=NULL,p=rh[r-1],
（ 1） 寻找插入位置,当 p!=NULL且 c>p->col时,p和 q右移
（ 2）插入：
a、若 p==NULL且 q==NULL，即本行空,则 rh[r-1]==s;
b,若 p==NULL,q!=NULL,即走到行末，则 q->right=s
c,若 c==p->col,则修改 p->val
d,若 c<p->col且 q==NULL,则在 p之前插入 s,即 s是行链表中第一个结点，令 rh[r-1]=s; s->right=p;
e,若 c<p->col且 q!=NULL,则在 p之前插入 s，
即 s->right=p; q->right=s;
4 1 8
^ ^
2 3 4
^ ^
m=4,n=3
1,1,3
2,2,5
2,3,4
4,1,8
2,1,7
Ch4_3.c
1 1 3
^^
2 1 7
^ ^
2 2 5
^ ^
