1
第 5章 数组和稀疏矩阵
5.1 数组
5.2 稀疏矩阵本章小结
2
5.1 数组数组是 n(n＞ 1)个相同类型数据元素 a1,a2,…,a n
构成的有限序列,且该有限序列存储在一块地址连续的内存单元中。
an……ai……a2a1
设每个数据元素占用 k个存储单元,则任一数据元素 ai的存储地址 LOC(ai)就可由以下公式求出：
LOC(ai)=LOC(a1)+(i-1)*k (0≤i≤n)
随机存取
数组的定义,
一维数组,An=(a1 a2 … a i … a n)
3
二维数组：
1,11,10,1
1,11110
1,00100
......
...............
......
......
nmmm
n
n
nm
aaa
aaa
aaa
A
( )
( )
( )
( )
(
)
(
)
(
)
(
)
(
)
可以看成是由 m个行向量组成的线性表，即数组可表示为：
同样地，也可以将数组看成是由 n个列向量组成的线性表。
每个数据元素 αi相当于一个一维数组。
),.,,,,.,,,,( 110 miAm
其中,),...,,...,,( 1,10 niijiii aaaa?
4
..................
...............
.........
...............
..................
.........
,1
1,,1,
,1
1,00100
ji
jijiji
ji
n
nm
a
aaa
a
aaa
A
从逻辑角度来看：数组中的每个元素 aij均属于两个向量：第 i行上的行向量和第 j列上的列向量。
除周边元素外，每个元素均有两个直接前驱和两个直接后继。
5
m维数组 看作二维数组的推广，其每个元素均属于 m个向量，即受到 m个关系的约束，最多可以有 m个直接前驱和 m个直接后继。
M维数组：
110?mnnnA …
6
1,数组中的数据元素数据固定 。 一旦定义了一个数组,其数据元素数目不再有增减的变化 。
2,数组中的数据元素具有相同的数据类型 。
3,数组中的每个数据元素都和一组惟一的下标值对应 。
4,数组是一种随机存储结构 。 可随机存取数组中的任意数据元素 。
数组的特点,
7
1,给定下标,存取相应的数据元素 。
2,给定下标,修改相应的数据元素 。
数组的基本运算,
对于不作删除和插入操作的数据，应该采用哪种类型的物理结构呢？
8
计算机内存：一维结构数组结构：多维结构 次序约定以 行序 为主序的存储方式以 列序 为主序的存储方式
数组的存储,（采用顺序存储结构）
一维数组,An=(a1 a2 … a i … a n)
Loc(ai)=Loc(a1)+ (i-1)*k
其中,Loc(a1)是 a1的存储地址
k表示每个数据元素占用的存储单元多维数组,Amⅹ n
9
a00 a01 …….,a 0,n-1
a10 a11 …….,a 1,n-1
am-1,0 am-1,1 … a m-1,n-1
………………….
以行序为主序存放
am-1,n-1
…….,
am-1,1
am-1,0
……….
a1,n-1
…….,
a12
a10
a0,n-1
…….
a01
a000
1
n-1
m*n-1
n
K
Loc( aij)=Loc(a00)+(i*n+j)*K
10
以列序为主序存放
0
1
m-1
m*n-1
m
am-1,n-1
…….,
a1,n-1
a0,n-1
……….
am-1,1
…….,
a11
a01
am-1,0
…….
a10
a00
a00 a01 …….,a0,n-1
a10 a11 …….,a1,n-1
am-1,0 am-1,1 …… am-1,n-1
……………………
Loc(aij)=Loc(a00)+ (j*m+i)*K
K
11
例：设有二维数组 A[0..9,0..19]，其每个元素占两个字节，第一个元素的存储地址为 100，若按行优先顺序存储，则元素 A[6,6]的存储地址为,按列优先顺序存储，元素 A[6,6]的存储地址为 。
352
232
解：按行优先存储：
Loc(a66)=Loc(a00)+(i*n+j)*K
=100+（ 6*20+6） *2
=352
按列优先存储：
Loc(a66)=Loc(a00)+(j*m+i)*K
=100+(6*10+6)*2
=232
12
采用顺序存储，不需要移动数据元素，我们可以做的操作有：
求长度? 遍历数组
插入数组元素? 删除数组元素不能做的操作有：
取数组元素? 修改数组元素
13
139
325
951
A 139325951
按行优先存储
100
005
001
B 100005001
按行优先存储有许多重复元素有许多零元素
特殊矩阵的压缩存储,
为什么要研究压缩存储 (目标 )？它研究的对象及主要形式是什么？如何进行压缩存储？
14
研究对象：矩阵阶数高、许多元素相同、
大量零元素的二维矩阵。
目标：节省存储空间
压缩存储：为多个值相同的元只分配一个存储空间；对零元素不分配空间。
特殊矩阵主要形式（分类研究）：
15
(1)特殊矩阵指非零元素或零元素的分布有一定规律的矩阵。
(2)特殊矩阵的主要形式
a.对称矩阵 ;b.对角矩阵等 (注,特殊矩阵均为方阵,即行数 =列数的矩阵 )
(3)特殊矩阵的压缩存储利用特殊矩阵自身元素的分布规律,使多个相同的非零元素共享同一个存储单元,对零元素不分配存储空间,从而达到节省存储空间之目的。
16
1,对称矩阵的压缩存储
(1)对称矩阵的定义：
若一个 n阶方阵 A[n][n]中的元素满足 ai,j=aj,j
(0≤i,j≤n-1),则称其为 n阶对称矩阵 。
如矩阵
A=
1 1 0
1 2 3
0 3 6
是个对称矩阵。
17
(2)对称矩阵元素分布的规律：
元素关于主对角元素对称 。
即上三角元素 ai,j与下三角元素 aj,i
相等 。
(3)对称矩阵的压缩存储思路：
仅存储上三角元素 (ai,j i≤j)
或仅存储下三角元素 (ai,j i≥j)
(4) 对称矩 A[n][n]下 (或上 )三角元素个数为
1+2+3+,…,+n=n(n+1)/2
1,对称矩阵的压缩存储
A=
1 1 0
1 2 3
0 3 6
18
(5)对称矩阵 A压缩为一维数组 B的算法
1,对称矩阵的压缩存储
A=
a0,0 a0,1 … a 0,n-1
a1,0 a1,1 … a 1,n-1
… … … …
an-1,0 an-1,1 … a n-1,n-1
B=[b0,b1,…,b n(n+1)/2-1]
仅存储下三角元素 (ai,j i≥j)
19
压缩算法 (供参考 )
void CompA(int b[],int *a,int n)
{
int i,j,k=0;
for(i=0;i<=n-1;i++)
for(j=0;j<=i;j++)
{
b[k]=*(a+i*n+j);
k++;
}
}
A=
a0,0 a0,1 … a 0,n-1
a1,0 a1,1 … a 1,n-1
… … … …
an-1,0 an-1,1 … a n-1,n-1
B=[b0,b1,…,b n(n+1)/2-1]
//*(a+i*n+j)相当于 a[i,j]
20
A=
a0,0 a0,1 … a 0,n-1
a1,0 a1,1 … a 1,n-1
… … … …
an-1,0 an-1,1 … a n-1,n-1
(6)将压缩后的一维数组 B解压为对称矩阵 A
B=[b0,b1,…,b n(n+1)/2-1]
bk ai,j?
21
关键是要找出一维数组下标 k与二维对称数组下标 i,j之间的关系 ！
容易证明,k与 i,j间满足如下对应关系,(p130)
(i*(i+1))/2+j 当 i≥j
(j*(j+1))/2+i 当 i<j
k=
22
解压缩算法 (供参考 )
void DeCompA(int b[],int a[N][N],int n)
{
int i,j,k;
for(i=0;i<=n-1;i++)
for(j=0;j<=n-1;j++)
{
if(i>=j)
k=(i*(i+1))/2+j;
else
k=(j*(j+1))/2+i;
a[i][j]=b[k];
}
}
23
2,对角矩阵的压缩存储
(1)对角矩阵的定义：
若一个 n阶方阵 A[n][n]满足其所有非零元素都集中在以主对角线为中心的带状区域中,则称其为对角矩阵 。 如以下矩阵 A是个对角矩阵
A=
3 4 5 0 0 0
2 3 4 5 0 0
1 2 3 4 5 0
0 1 2 3 4 4
0 0 1 2 3 4
0 0 0 1 2 3
并称该对角矩阵的半带宽为 2；
带宽为 2× 2+1=5
2条对角线主对角线
24
2,对角矩阵的压缩存储
(1)对角矩阵的定义：
若一个 n阶方阵 A[n][n]满足其所有非零元素都集中在以主对解线为中心的带状区域中,则称其为对角矩阵 。 如以下矩阵 A是个对角矩阵
A=
a0,0 a0,1 a0,2 … 0 0
a1,0 a1,1 a1,2 … 0 0
… … … ak,k … …
0 0 … … an-2,n-2 an-1,n-1
则称该对角矩阵的半带宽为 b；
带宽为 2× b+1
对于 b=1的 对角矩阵称为三对角矩阵。
本节仅讨论三对角矩阵的压缩存储。
b条对角线
b条对角线三对角矩阵示意图
25
0 1 2 3 4 5
0 0 0 0 0
1 0 0 0
2 0 0 0
3 0 0 0
4 0 0 0
5 0 0 0 0
ji
问题：如何确定对角矩阵中所有非零元素的行下标与列下标？
26
0 1 2 3 4 5
0
1
2
3
4
5
ji
Lmain:i-j=0
LA1:i-j=-1
LA2:i-j=-2
LA3:i-j=-3
LA4:i-j=-4
结论,若对角矩阵 A的半带宽为 b,只要 |i-j|≤ b,ai.j必处于以对主对角线为中心的带状区域内,即 ai.j≠0 。
27
(2)对角矩阵非零元素的分布规律：
对于半带宽为 b的对角矩阵
,其满足 | i-j |≤b的元素 ai,j≠0；
(3)对角矩阵的压缩存储思路,使用 对角矩阵非零元素的分布规律 仅存储非零元素
(4)n阶三对角矩阵非零元素的个数,
3(n-2)+4
即可将一个占用 n2存储空间的三对角矩阵 A压缩为仅占用存储空间为 3(n-2)+4的一维数组 B。
0 1 2 3 4 5
0 0 0 0 0
1 0 0 0
2 0 0 0
3 0 0 0
4 0 0 0
5 0 0 0 0
ji
28
3,三对角矩阵的压缩算法三对角矩阵非零元素的分布规律：
所有满足 | i-j |≤1
的元素 ai,j≠0；
0 1 2 3 4 5
0 0 0 0 0
1 0 0 0
2 0 0 0
3 0 0 0
4 0 0 0
5 0 0 0 0
ji
29
3,三对角矩阵的压缩算法
void CompDiag(int b[],int Da[N][N],int n)
{
int i,j,k=0;
for(i=0;i<=n-1;i++)
for(j=0;j<=n-1;j++)
{
if(abs(i-j)<=1)
{
b[k]=Da[i][j] ;
k++;
}
}
}
算法描述,
将一个 n× n阶三对角矩阵 Da压缩为一维数组 b
//仅存储非零元素
30
B=[b0,b1,…,b 3(n-2)+4-1]
An× n=
a0,0 a0,1 a0,2 … 0 0
a1,0 a1,1 a1,2 … 0 0
… … … ak,k … …
0 0 … … an-2,n-2 an-1,n-1
关键之处：
找出一维数组下标 k(0≤k≤3(n-2)+4-1)与三对角矩阵下标 i,j间的对应关系！
bk ai,j?
问题：将压缩后的一维数组 B解压为一个三对角矩阵 A？
31
分析,
a.第 0行与第 n-1行都只有 2个非零元素、其余各行均有 3个非零元素 ;
b.对任一非零元素 ai,j (i≠0),
它前面共有 i行,由于第 0行只有
2个非零元素,因而它前面共存储了 2+3(i-1)=2i+i-1个非零元素,
若 ai,j为本行的第 1个非零元素必有 j=i-1,即 k=2i+j,若 ai,j为本行的第 2个非零元素,则有 j=i,
此时 k=2+3(i-1)+1=2i+i=2i+j,若 ai,j为本行的第 3个非零元素必有 j=i+1,此时 k=2+3(i-1)+2=2i+i+1=2i+j。
综上所述,不论 ai,j是本行第几个非零元素总有,
k=2i+j (课本 p131)
0 1 2 3 4 5
0 0 0 0 0
1 0 0 0
2 0 0 0
3 0 0 0
4 0 0 0
5 0 0 0 0
ji
32
4,将一维数组解压为三对角矩阵算法
void DeCompDiag(int b[],int a[N][N],int n)
{
int i,j,k=0;
for(i=0;i<=n-1;i++)
for(j=0;j<=n-1;j++)
{
if(abs(i-j)<=1 && k==2*i+j)
{
a[i][j]=b[k];
if(k<=3*(n-2)+4-1)
k++;
}
else a[i][j]=0;
}
}
算法描述,将一维数组 b解压为一个 n× n阶三对角矩阵 a
//恢复零元素
//恢复非零元素
33
什么是稀疏矩阵？采用 A[rows][cols]这种简单的表示方法有什么问题吗？
组 织 角 色
5.2 稀疏矩阵 (sparse Matrix)
34
所谓稀疏矩阵是指矩阵中含有大量的零元，
且非零元的分布没有任何规律。
组 织 角 色
35
究竟大量是多少呢？
组 织 角 色
36
一个阶数较大的矩阵中当非零元个数除 s以矩阵总个数 t
的商 δ≤0.05时。如一个
100× 100的矩阵中只包含 100
个非零元就是一个稀疏矩阵。
组 织 角 色
37
啊！如果采用以前的存储结构会浪费 10000-
100个空间单元！但是，
对这种矩阵的讨论有多大意思呢？
组织角色
38
有很大意义，因为在数学分析中经常会碰到稀疏矩阵。
组 织 角 色
39
唉！，那就必须寻找另一种更为有效的存储方法了。
组 织 角 色
40
5.2.1 稀疏矩阵的三元组表示稀疏矩阵的压缩存储方法是只存储非零元素 。
由于稀疏矩阵中非零元素的分布没有任何规律,
所以在存储非零元素时还必须同时存储该非零元素所对应的行下标和列下标 。 这样稀疏矩阵中的每一个非零元素需由一个三元组 (i,j,ai,j)惟一确定,稀疏矩阵中的所有非零元素构成三元组线性表 。
注意,稀疏矩阵采用三元组表示之后，对三元组我们即可采用顺序存储结构，也可采用链式存储结构 。
41
假设有一个 6× 7阶稀疏矩阵 A(为图示方便,我们所取的行列数都很小 ),A中元素如下图所示 。 则对应的三元组线性表为：
((0,2,1),(1,1,2),(2,0,3),(3,3,5),
(4,4,6),(5,5,7),(5,6,4))
4700000
0060000
0005000
0000003
0000020
0000100
76
A
一个稀疏矩阵 A
42
稀疏矩阵压缩存储原则：
只存矩阵的行列维数和每个非零元的行列下标及其值，即稀疏矩阵可由表示非零元 aij的三元组 (i,j,aij)及其行列数和非零元总数唯一确定。
76
00070015
00000180
00002400
01400003
0000000
00009120
((0,1,12),(0,2,9),(2,0,- 3),
(2,5,14),(3,2,24),(4,1,18),
(5,0,15),(5,3,-7))和 （ 6,7,8）
43
一,三元组顺序表
#define M 6 //稀疏矩阵总行数
#define N 7 //
typedef int ElemType;
typedef struct
{ int r;//非零元素的行号
int c;//非零元素的列号
ElemType d;//非零元素 ai,j的值
} TupNode;//三元组定义
typedef struct
{ int rows;//稀疏矩阵总行数
int cols;//稀疏矩阵总列数
int nums;//稀疏矩阵非零元素个数
TupNode data[Maxsize];//三元组数据域
}TSMatrix;//三元组线性表定义
r c d
0
1
2
3
Maxsize-1
三元组线性表 t
的 data域结构
4
5
6
7
… … …
………
8
… … …
TSMatrix t;
44
0
025
000
300
001
M
行下标 列下标 值
0 1
1 2 3
3 0
3 1 2三元组三元组表如定义：
TSMatrix *M;
M->data
M->data[2]
M->data[2].r
M->data[2].d
5
45
void CreateMat(TSMatrix &t,ElemType A[M][N])
{ int i,j; t.rows=M; t.cols=N; t.nums=0;
for(i=0;i<M;i++)
{ for(j=0;j<N;j++)
if(A[i][j]!=0)
{ t.data[t.nums].r=i;
t.data[t.nums].c=j;
t.data[t.nums].d=A[i][j];
t.nums++;
}
}
}
r c d
0
1
2
3
4
5
6
7
0 2 1
1 1 2
2 2 1
2 0 3
1.从一个二维矩阵创建其三元组
A4× 4=
0 0 1 0
0 2 0 0
3 0 1 0
0 0 0 0
设 M=4,N=4已定义为全局常量调用语句为 CreateMat(t,A);
三元组线性表 t
的 data域
46
2.三元组元素赋值先在三元组 t中找到适当的位置 k,将 k～ t.nums个元素后移一位,将指定元素 x插入到 t.data[k]处。
算法如下：
int Value(TSMatrix &t,ElemType x,int rs,int cs)
{ int i,k=0;
if (rs>=t.rows || cs>=t.cols) return 0;
while (k<t.nums && rs>t.data[k].r)
k++ /*查找行 */
while (k<t.nums &&rs>=t.data[k].r&& cs>t.data[k].c)
k++; /*查找列 */
47
if (t.data[k].r==rs && t.data[k].c==cs)
t.data[k].d=x; /*存在这样的元素
else /*不存在这样的元素时插入一个元素 */
{ for (i=t.nums-1;i>=k;i--) /*元素后移 */
{ t.data[i+1].r=t.data[i].r;
t.data[i+1].c=t.data[i].c;
t.data[i+1].d=t.data[i].d;
}
t.data[k].r=rs;t.data[k].c=cs;t.data[k].d=x;
t.nums++;
}
return 1;
}
已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表。
－－将矩阵的行列值相互交换
－－将每个三元组中的 r和 c相互调换
－－重排三元组之间的次序（行序）
213
503
321
100
M的三元组表 ma
312
231
530
100
N的三元组表 nb
34
025
000
300
001
M
43
0030
2000
5001
N
3.求转置矩阵：
43
0030
2000
5001
N
34
025
000
300
001
M
方法,按 M的列序转置，即按 N中三元组次序依次在 M
中找到相应的三元组进行转置。
213
503
321
100
M的三元组表 ma
312
231
530
100
N的三元组表 nb
怎样找出每一列的非零元 为找到 M中每一列所有非零元素，需对其三元组表 ma从第一个元素起扫描一遍。
213
503
321
100
M的三元组表 ma
312
231
530
100
N的三元组表 nb
扫描过程：
设,p,q分别为指向 ma,nb中三元组的序号扫描一列（列号为 col）的过程
for(p=0;p<M->nums;p++)
if(M->data[p].c==col)
{N->data[q].r=M->data[p].c;
N->data[q].c=M->data[p].r;
N->data[q].d=M->data[p].d;
q++;}
p
p
q
34
025
000
300
001
M
213
503
321
100
M的三元组表 ma
312
231
530
100
N的三元组表 nb
p
p
完整的扫描过程
q=0;
for(v=0;v<M->cols;v++) //扫描 M中的每一列
for(p=0;p<M->nums;p++)
if(M->data[p].c==col)
{N->data[q].r=M->data[p].c;
N->data[q].c=M->data[p].r;
N->data[q].d=M->data[p].d;
q++;
}
完整算法 p134
34
025
000
300
001
M
52
算法分析,算法的 主要工作是在 p和 col的两个循环中完成的，故算法的时间复杂度为 O(nums*cols)，
即与矩阵的列数和非零元的个数的乘积成正比。
而一般传统矩阵的转置算法为：
for(col=1;col<=cols;++col)
for(row=1;row<=rows;++row)
t[col][row]=m[row][col];
其时间复杂度为 O(cols*rows)。当非零元素的个数
nums和 rows*cols同数量级时，算法 TranTat的时间复杂度为 O(rows*cols2)。
53
例 5.3 采用三元组存储稀疏矩阵，设计两个稀疏矩阵相加的运算算法。
书中算法只考虑了两个稀疏矩阵 (假设 A和 B)
中非零元个数相等的情况，至于非零元个数不相等时，该如何处理没有考虑。
大家把稀疏矩阵 A中非零元个数小于 B中非零元个数和稀疏矩阵 A中非零元个数大于 B中非零元个数时这两种情况在程序中加以说明。
54
二,十字链表十字链表为稀疏矩阵的每一行设置一个单独链表,同时也为每一列设置一个单独链表。
在链表中，每个非零元素用一个含有五个域的结点表示，其中 i,j和 v三个域分别表示该非零元所在的行、列和非零元的值，行指针域 right用来指向本行下一非零元；列指针域 down用来指向本列中下一非零元。
55
#define M 3 //稀疏矩阵行数
#define N 4 //稀疏矩阵列数
#define Max ((M)>(N)? (M):(N)) //取 M,N中的最大者
typedef int ElemType;
typedef struct mtxn
{ int row;//存放非零元素的行号
int col;//存放非零元素的列号
struct mtxn *right,*down;//向右,下指针
union
{ ElemType value;
struct mtxn *link;
} tag;
} MatNode;
down right
row col (link/value)十字链表数据结构定义 tag
1 0 0 2
0 0 3 0
0 0 0 4
B3× 4=
如何构造稀疏矩 B的十字链表表示?
56
1.从一个二维矩建立其十字链表表示
void CreateMat(MatNode *&mh,ElemType a[M][N])
{
int i,j;
MatNode *h[Max],*p,*q,*r;
mh=(MatNode *)malloc(sizeof(MatNode));
mh->row=M;mh->col=N;
r=mh;
1 0 0 2
0 0 3 0
0 0 0 4
B3× 4=
mh
34
头结点
r
a.建立头结点
57
1.从一个二维矩建立其十字链表表示
for(i=0;i<Max;i++)
{
h[i]=(MatNode *)malloc(sizeof(MatNode));
h[i]->down=h[i]->right=h[i];//表明现为空表
h[i]->row=h[i]->col=-1;//设置行列表头标志
r->tag.link=h[i];//将各行列表头连接成一链表
r=h[i];
}
r->tag.link=mh; 1 0 0 20 0 3 0
0 0 0 4
B3× 4=
b.建立行列表头
mh
34 -1-1 -1-1 -1-1 -1-1
h[0] h[1] h[2] h[3]头结点
r
58
1.从一个二维矩建立其十字链表表示
1 0 0 2
0 0 3 0
0 0 0 4
B3× 4=
c.等效于十字链表
mh
34 -1-1 -1-1 -1-1 -1-1
h[0] h[1] h[2] h[3]头结点
r
-1-1
-1-1
-1-1
-1-1
h[0]
h[1]
h[2]
h[3]
59
1.从一个二维矩建立其十字链表表示
1 0 0 2
0 0 3 0
0 0 0 4
B3× 4=
mh
34 -1-1 -1-1 -1-1 -1-1
h[0] h[1] h[2] h[3]头结点
-1-1
-1-1
-1-1
-1-1
h[0]
h[1]
h[2]
h[3]
00 1
pq
q
30 2
p
q
q
20 3
pq
q q
q
32 4
p
q
d.插入非零元素
60
压缩存储的关键问题（总结）
选定有效的存储结构（尽可能的节省空间）
基于选定的存储结构，如何有效地访问数组元素，
即根据元素下标找出其值。
基于选定的存储结构，如何实现数组的各种操作。
61
本章小结本章基本学习要点如下：
(1)理解数组和一般线性表之间的差异。
(2)重点掌握数组的顺序存储结构和元素地址计算方法。
(3)掌握各种特殊矩阵如对称矩阵、上、下三角矩阵和对角矩阵的压缩存储方法。
(4)掌握稀疏矩阵的顺序存储结构 (三元组顺序表 )以及基本运算实现算法。
(5)灵活运用数组这种数据结构解决一些综合应用问题。
62
作业题教材中 p113习题 3,5和 6。
第 5章 数组和稀疏矩阵
5.1 数组
5.2 稀疏矩阵本章小结
2
5.1 数组数组是 n(n＞ 1)个相同类型数据元素 a1,a2,…,a n
构成的有限序列,且该有限序列存储在一块地址连续的内存单元中。
an……ai……a2a1
设每个数据元素占用 k个存储单元,则任一数据元素 ai的存储地址 LOC(ai)就可由以下公式求出：
LOC(ai)=LOC(a1)+(i-1)*k (0≤i≤n)
随机存取
数组的定义,
一维数组,An=(a1 a2 … a i … a n)
3
二维数组：
1,11,10,1
1,11110
1,00100
......
...............
......
......
nmmm
n
n
nm
aaa
aaa
aaa
A
( )
( )
( )
( )
(
)
(
)
(
)
(
)
(
)
可以看成是由 m个行向量组成的线性表，即数组可表示为：
同样地，也可以将数组看成是由 n个列向量组成的线性表。
每个数据元素 αi相当于一个一维数组。
),.,,,,.,,,,( 110 miAm
其中,),...,,...,,( 1,10 niijiii aaaa?
4
..................
...............
.........
...............
..................
.........
,1
1,,1,
,1
1,00100
ji
jijiji
ji
n
nm
a
aaa
a
aaa
A
从逻辑角度来看：数组中的每个元素 aij均属于两个向量：第 i行上的行向量和第 j列上的列向量。
除周边元素外，每个元素均有两个直接前驱和两个直接后继。
5
m维数组 看作二维数组的推广，其每个元素均属于 m个向量，即受到 m个关系的约束，最多可以有 m个直接前驱和 m个直接后继。
M维数组：
110?mnnnA …
6
1,数组中的数据元素数据固定 。 一旦定义了一个数组,其数据元素数目不再有增减的变化 。
2,数组中的数据元素具有相同的数据类型 。
3,数组中的每个数据元素都和一组惟一的下标值对应 。
4,数组是一种随机存储结构 。 可随机存取数组中的任意数据元素 。
数组的特点,
7
1,给定下标,存取相应的数据元素 。
2,给定下标,修改相应的数据元素 。
数组的基本运算,
对于不作删除和插入操作的数据，应该采用哪种类型的物理结构呢？
8
计算机内存：一维结构数组结构：多维结构 次序约定以 行序 为主序的存储方式以 列序 为主序的存储方式
数组的存储,（采用顺序存储结构）
一维数组,An=(a1 a2 … a i … a n)
Loc(ai)=Loc(a1)+ (i-1)*k
其中,Loc(a1)是 a1的存储地址
k表示每个数据元素占用的存储单元多维数组,Amⅹ n
9
a00 a01 …….,a 0,n-1
a10 a11 …….,a 1,n-1
am-1,0 am-1,1 … a m-1,n-1
………………….
以行序为主序存放
am-1,n-1
…….,
am-1,1
am-1,0
……….
a1,n-1
…….,
a12
a10
a0,n-1
…….
a01
a000
1
n-1
m*n-1
n
K
Loc( aij)=Loc(a00)+(i*n+j)*K
10
以列序为主序存放
0
1
m-1
m*n-1
m
am-1,n-1
…….,
a1,n-1
a0,n-1
……….
am-1,1
…….,
a11
a01
am-1,0
…….
a10
a00
a00 a01 …….,a0,n-1
a10 a11 …….,a1,n-1
am-1,0 am-1,1 …… am-1,n-1
……………………
Loc(aij)=Loc(a00)+ (j*m+i)*K
K
11
例：设有二维数组 A[0..9,0..19]，其每个元素占两个字节，第一个元素的存储地址为 100，若按行优先顺序存储，则元素 A[6,6]的存储地址为,按列优先顺序存储，元素 A[6,6]的存储地址为 。
352
232
解：按行优先存储：
Loc(a66)=Loc(a00)+(i*n+j)*K
=100+（ 6*20+6） *2
=352
按列优先存储：
Loc(a66)=Loc(a00)+(j*m+i)*K
=100+(6*10+6)*2
=232
12
采用顺序存储，不需要移动数据元素，我们可以做的操作有：
求长度? 遍历数组
插入数组元素? 删除数组元素不能做的操作有：
取数组元素? 修改数组元素
13
139
325
951
A 139325951
按行优先存储
100
005
001
B 100005001
按行优先存储有许多重复元素有许多零元素
特殊矩阵的压缩存储,
为什么要研究压缩存储 (目标 )？它研究的对象及主要形式是什么？如何进行压缩存储？
14
研究对象：矩阵阶数高、许多元素相同、
大量零元素的二维矩阵。
目标：节省存储空间
压缩存储：为多个值相同的元只分配一个存储空间；对零元素不分配空间。
特殊矩阵主要形式（分类研究）：
15
(1)特殊矩阵指非零元素或零元素的分布有一定规律的矩阵。
(2)特殊矩阵的主要形式
a.对称矩阵 ;b.对角矩阵等 (注,特殊矩阵均为方阵,即行数 =列数的矩阵 )
(3)特殊矩阵的压缩存储利用特殊矩阵自身元素的分布规律,使多个相同的非零元素共享同一个存储单元,对零元素不分配存储空间,从而达到节省存储空间之目的。
16
1,对称矩阵的压缩存储
(1)对称矩阵的定义：
若一个 n阶方阵 A[n][n]中的元素满足 ai,j=aj,j
(0≤i,j≤n-1),则称其为 n阶对称矩阵 。
如矩阵
A=
1 1 0
1 2 3
0 3 6
是个对称矩阵。
17
(2)对称矩阵元素分布的规律：
元素关于主对角元素对称 。
即上三角元素 ai,j与下三角元素 aj,i
相等 。
(3)对称矩阵的压缩存储思路：
仅存储上三角元素 (ai,j i≤j)
或仅存储下三角元素 (ai,j i≥j)
(4) 对称矩 A[n][n]下 (或上 )三角元素个数为
1+2+3+,…,+n=n(n+1)/2
1,对称矩阵的压缩存储
A=
1 1 0
1 2 3
0 3 6
18
(5)对称矩阵 A压缩为一维数组 B的算法
1,对称矩阵的压缩存储
A=
a0,0 a0,1 … a 0,n-1
a1,0 a1,1 … a 1,n-1
… … … …
an-1,0 an-1,1 … a n-1,n-1
B=[b0,b1,…,b n(n+1)/2-1]
仅存储下三角元素 (ai,j i≥j)
19
压缩算法 (供参考 )
void CompA(int b[],int *a,int n)
{
int i,j,k=0;
for(i=0;i<=n-1;i++)
for(j=0;j<=i;j++)
{
b[k]=*(a+i*n+j);
k++;
}
}
A=
a0,0 a0,1 … a 0,n-1
a1,0 a1,1 … a 1,n-1
… … … …
an-1,0 an-1,1 … a n-1,n-1
B=[b0,b1,…,b n(n+1)/2-1]
//*(a+i*n+j)相当于 a[i,j]
20
A=
a0,0 a0,1 … a 0,n-1
a1,0 a1,1 … a 1,n-1
… … … …
an-1,0 an-1,1 … a n-1,n-1
(6)将压缩后的一维数组 B解压为对称矩阵 A
B=[b0,b1,…,b n(n+1)/2-1]
bk ai,j?
21
关键是要找出一维数组下标 k与二维对称数组下标 i,j之间的关系 ！
容易证明,k与 i,j间满足如下对应关系,(p130)
(i*(i+1))/2+j 当 i≥j
(j*(j+1))/2+i 当 i<j
k=
22
解压缩算法 (供参考 )
void DeCompA(int b[],int a[N][N],int n)
{
int i,j,k;
for(i=0;i<=n-1;i++)
for(j=0;j<=n-1;j++)
{
if(i>=j)
k=(i*(i+1))/2+j;
else
k=(j*(j+1))/2+i;
a[i][j]=b[k];
}
}
23
2,对角矩阵的压缩存储
(1)对角矩阵的定义：
若一个 n阶方阵 A[n][n]满足其所有非零元素都集中在以主对角线为中心的带状区域中,则称其为对角矩阵 。 如以下矩阵 A是个对角矩阵
A=
3 4 5 0 0 0
2 3 4 5 0 0
1 2 3 4 5 0
0 1 2 3 4 4
0 0 1 2 3 4
0 0 0 1 2 3
并称该对角矩阵的半带宽为 2；
带宽为 2× 2+1=5
2条对角线主对角线
24
2,对角矩阵的压缩存储
(1)对角矩阵的定义：
若一个 n阶方阵 A[n][n]满足其所有非零元素都集中在以主对解线为中心的带状区域中,则称其为对角矩阵 。 如以下矩阵 A是个对角矩阵
A=
a0,0 a0,1 a0,2 … 0 0
a1,0 a1,1 a1,2 … 0 0
… … … ak,k … …
0 0 … … an-2,n-2 an-1,n-1
则称该对角矩阵的半带宽为 b；
带宽为 2× b+1
对于 b=1的 对角矩阵称为三对角矩阵。
本节仅讨论三对角矩阵的压缩存储。
b条对角线
b条对角线三对角矩阵示意图
25
0 1 2 3 4 5
0 0 0 0 0
1 0 0 0
2 0 0 0
3 0 0 0
4 0 0 0
5 0 0 0 0
ji
问题：如何确定对角矩阵中所有非零元素的行下标与列下标？
26
0 1 2 3 4 5
0
1
2
3
4
5
ji
Lmain:i-j=0
LA1:i-j=-1
LA2:i-j=-2
LA3:i-j=-3
LA4:i-j=-4
结论,若对角矩阵 A的半带宽为 b,只要 |i-j|≤ b,ai.j必处于以对主对角线为中心的带状区域内,即 ai.j≠0 。
27
(2)对角矩阵非零元素的分布规律：
对于半带宽为 b的对角矩阵
,其满足 | i-j |≤b的元素 ai,j≠0；
(3)对角矩阵的压缩存储思路,使用 对角矩阵非零元素的分布规律 仅存储非零元素
(4)n阶三对角矩阵非零元素的个数,
3(n-2)+4
即可将一个占用 n2存储空间的三对角矩阵 A压缩为仅占用存储空间为 3(n-2)+4的一维数组 B。
0 1 2 3 4 5
0 0 0 0 0
1 0 0 0
2 0 0 0
3 0 0 0
4 0 0 0
5 0 0 0 0
ji
28
3,三对角矩阵的压缩算法三对角矩阵非零元素的分布规律：
所有满足 | i-j |≤1
的元素 ai,j≠0；
0 1 2 3 4 5
0 0 0 0 0
1 0 0 0
2 0 0 0
3 0 0 0
4 0 0 0
5 0 0 0 0
ji
29
3,三对角矩阵的压缩算法
void CompDiag(int b[],int Da[N][N],int n)
{
int i,j,k=0;
for(i=0;i<=n-1;i++)
for(j=0;j<=n-1;j++)
{
if(abs(i-j)<=1)
{
b[k]=Da[i][j] ;
k++;
}
}
}
算法描述,
将一个 n× n阶三对角矩阵 Da压缩为一维数组 b
//仅存储非零元素
30
B=[b0,b1,…,b 3(n-2)+4-1]
An× n=
a0,0 a0,1 a0,2 … 0 0
a1,0 a1,1 a1,2 … 0 0
… … … ak,k … …
0 0 … … an-2,n-2 an-1,n-1
关键之处：
找出一维数组下标 k(0≤k≤3(n-2)+4-1)与三对角矩阵下标 i,j间的对应关系！
bk ai,j?
问题：将压缩后的一维数组 B解压为一个三对角矩阵 A？
31
分析,
a.第 0行与第 n-1行都只有 2个非零元素、其余各行均有 3个非零元素 ;
b.对任一非零元素 ai,j (i≠0),
它前面共有 i行,由于第 0行只有
2个非零元素,因而它前面共存储了 2+3(i-1)=2i+i-1个非零元素,
若 ai,j为本行的第 1个非零元素必有 j=i-1,即 k=2i+j,若 ai,j为本行的第 2个非零元素,则有 j=i,
此时 k=2+3(i-1)+1=2i+i=2i+j,若 ai,j为本行的第 3个非零元素必有 j=i+1,此时 k=2+3(i-1)+2=2i+i+1=2i+j。
综上所述,不论 ai,j是本行第几个非零元素总有,
k=2i+j (课本 p131)
0 1 2 3 4 5
0 0 0 0 0
1 0 0 0
2 0 0 0
3 0 0 0
4 0 0 0
5 0 0 0 0
ji
32
4,将一维数组解压为三对角矩阵算法
void DeCompDiag(int b[],int a[N][N],int n)
{
int i,j,k=0;
for(i=0;i<=n-1;i++)
for(j=0;j<=n-1;j++)
{
if(abs(i-j)<=1 && k==2*i+j)
{
a[i][j]=b[k];
if(k<=3*(n-2)+4-1)
k++;
}
else a[i][j]=0;
}
}
算法描述,将一维数组 b解压为一个 n× n阶三对角矩阵 a
//恢复零元素
//恢复非零元素
33
什么是稀疏矩阵？采用 A[rows][cols]这种简单的表示方法有什么问题吗？
组 织 角 色
5.2 稀疏矩阵 (sparse Matrix)
34
所谓稀疏矩阵是指矩阵中含有大量的零元，
且非零元的分布没有任何规律。
组 织 角 色
35
究竟大量是多少呢？
组 织 角 色
36
一个阶数较大的矩阵中当非零元个数除 s以矩阵总个数 t
的商 δ≤0.05时。如一个
100× 100的矩阵中只包含 100
个非零元就是一个稀疏矩阵。
组 织 角 色
37
啊！如果采用以前的存储结构会浪费 10000-
100个空间单元！但是，
对这种矩阵的讨论有多大意思呢？
组织角色
38
有很大意义，因为在数学分析中经常会碰到稀疏矩阵。
组 织 角 色
39
唉！，那就必须寻找另一种更为有效的存储方法了。
组 织 角 色
40
5.2.1 稀疏矩阵的三元组表示稀疏矩阵的压缩存储方法是只存储非零元素 。
由于稀疏矩阵中非零元素的分布没有任何规律,
所以在存储非零元素时还必须同时存储该非零元素所对应的行下标和列下标 。 这样稀疏矩阵中的每一个非零元素需由一个三元组 (i,j,ai,j)惟一确定,稀疏矩阵中的所有非零元素构成三元组线性表 。
注意,稀疏矩阵采用三元组表示之后，对三元组我们即可采用顺序存储结构，也可采用链式存储结构 。
41
假设有一个 6× 7阶稀疏矩阵 A(为图示方便,我们所取的行列数都很小 ),A中元素如下图所示 。 则对应的三元组线性表为：
((0,2,1),(1,1,2),(2,0,3),(3,3,5),
(4,4,6),(5,5,7),(5,6,4))
4700000
0060000
0005000
0000003
0000020
0000100
76
A
一个稀疏矩阵 A
42
稀疏矩阵压缩存储原则：
只存矩阵的行列维数和每个非零元的行列下标及其值，即稀疏矩阵可由表示非零元 aij的三元组 (i,j,aij)及其行列数和非零元总数唯一确定。
76
00070015
00000180
00002400
01400003
0000000
00009120
((0,1,12),(0,2,9),(2,0,- 3),
(2,5,14),(3,2,24),(4,1,18),
(5,0,15),(5,3,-7))和 （ 6,7,8）
43
一,三元组顺序表
#define M 6 //稀疏矩阵总行数
#define N 7 //
typedef int ElemType;
typedef struct
{ int r;//非零元素的行号
int c;//非零元素的列号
ElemType d;//非零元素 ai,j的值
} TupNode;//三元组定义
typedef struct
{ int rows;//稀疏矩阵总行数
int cols;//稀疏矩阵总列数
int nums;//稀疏矩阵非零元素个数
TupNode data[Maxsize];//三元组数据域
}TSMatrix;//三元组线性表定义
r c d
0
1
2
3
Maxsize-1
三元组线性表 t
的 data域结构
4
5
6
7
… … …
………
8
… … …
TSMatrix t;
44
0
025
000
300
001
M
行下标 列下标 值
0 1
1 2 3
3 0
3 1 2三元组三元组表如定义：
TSMatrix *M;
M->data
M->data[2]
M->data[2].r
M->data[2].d
5
45
void CreateMat(TSMatrix &t,ElemType A[M][N])
{ int i,j; t.rows=M; t.cols=N; t.nums=0;
for(i=0;i<M;i++)
{ for(j=0;j<N;j++)
if(A[i][j]!=0)
{ t.data[t.nums].r=i;
t.data[t.nums].c=j;
t.data[t.nums].d=A[i][j];
t.nums++;
}
}
}
r c d
0
1
2
3
4
5
6
7
0 2 1
1 1 2
2 2 1
2 0 3
1.从一个二维矩阵创建其三元组
A4× 4=
0 0 1 0
0 2 0 0
3 0 1 0
0 0 0 0
设 M=4,N=4已定义为全局常量调用语句为 CreateMat(t,A);
三元组线性表 t
的 data域
46
2.三元组元素赋值先在三元组 t中找到适当的位置 k,将 k～ t.nums个元素后移一位,将指定元素 x插入到 t.data[k]处。
算法如下：
int Value(TSMatrix &t,ElemType x,int rs,int cs)
{ int i,k=0;
if (rs>=t.rows || cs>=t.cols) return 0;
while (k<t.nums && rs>t.data[k].r)
k++ /*查找行 */
while (k<t.nums &&rs>=t.data[k].r&& cs>t.data[k].c)
k++; /*查找列 */
47
if (t.data[k].r==rs && t.data[k].c==cs)
t.data[k].d=x; /*存在这样的元素
else /*不存在这样的元素时插入一个元素 */
{ for (i=t.nums-1;i>=k;i--) /*元素后移 */
{ t.data[i+1].r=t.data[i].r;
t.data[i+1].c=t.data[i].c;
t.data[i+1].d=t.data[i].d;
}
t.data[k].r=rs;t.data[k].c=cs;t.data[k].d=x;
t.nums++;
}
return 1;
}
已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表。
－－将矩阵的行列值相互交换
－－将每个三元组中的 r和 c相互调换
－－重排三元组之间的次序（行序）
213
503
321
100
M的三元组表 ma
312
231
530
100
N的三元组表 nb
34
025
000
300
001
M
43
0030
2000
5001
N
3.求转置矩阵：
43
0030
2000
5001
N
34
025
000
300
001
M
方法,按 M的列序转置，即按 N中三元组次序依次在 M
中找到相应的三元组进行转置。
213
503
321
100
M的三元组表 ma
312
231
530
100
N的三元组表 nb
怎样找出每一列的非零元 为找到 M中每一列所有非零元素，需对其三元组表 ma从第一个元素起扫描一遍。
213
503
321
100
M的三元组表 ma
312
231
530
100
N的三元组表 nb
扫描过程：
设,p,q分别为指向 ma,nb中三元组的序号扫描一列（列号为 col）的过程
for(p=0;p<M->nums;p++)
if(M->data[p].c==col)
{N->data[q].r=M->data[p].c;
N->data[q].c=M->data[p].r;
N->data[q].d=M->data[p].d;
q++;}
p
p
q
34
025
000
300
001
M
213
503
321
100
M的三元组表 ma
312
231
530
100
N的三元组表 nb
p
p
完整的扫描过程
q=0;
for(v=0;v<M->cols;v++) //扫描 M中的每一列
for(p=0;p<M->nums;p++)
if(M->data[p].c==col)
{N->data[q].r=M->data[p].c;
N->data[q].c=M->data[p].r;
N->data[q].d=M->data[p].d;
q++;
}
完整算法 p134
34
025
000
300
001
M
52
算法分析,算法的 主要工作是在 p和 col的两个循环中完成的，故算法的时间复杂度为 O(nums*cols)，
即与矩阵的列数和非零元的个数的乘积成正比。
而一般传统矩阵的转置算法为：
for(col=1;col<=cols;++col)
for(row=1;row<=rows;++row)
t[col][row]=m[row][col];
其时间复杂度为 O(cols*rows)。当非零元素的个数
nums和 rows*cols同数量级时，算法 TranTat的时间复杂度为 O(rows*cols2)。
53
例 5.3 采用三元组存储稀疏矩阵，设计两个稀疏矩阵相加的运算算法。
书中算法只考虑了两个稀疏矩阵 (假设 A和 B)
中非零元个数相等的情况，至于非零元个数不相等时，该如何处理没有考虑。
大家把稀疏矩阵 A中非零元个数小于 B中非零元个数和稀疏矩阵 A中非零元个数大于 B中非零元个数时这两种情况在程序中加以说明。
54
二,十字链表十字链表为稀疏矩阵的每一行设置一个单独链表,同时也为每一列设置一个单独链表。
在链表中，每个非零元素用一个含有五个域的结点表示，其中 i,j和 v三个域分别表示该非零元所在的行、列和非零元的值，行指针域 right用来指向本行下一非零元；列指针域 down用来指向本列中下一非零元。
55
#define M 3 //稀疏矩阵行数
#define N 4 //稀疏矩阵列数
#define Max ((M)>(N)? (M):(N)) //取 M,N中的最大者
typedef int ElemType;
typedef struct mtxn
{ int row;//存放非零元素的行号
int col;//存放非零元素的列号
struct mtxn *right,*down;//向右,下指针
union
{ ElemType value;
struct mtxn *link;
} tag;
} MatNode;
down right
row col (link/value)十字链表数据结构定义 tag
1 0 0 2
0 0 3 0
0 0 0 4
B3× 4=
如何构造稀疏矩 B的十字链表表示?
56
1.从一个二维矩建立其十字链表表示
void CreateMat(MatNode *&mh,ElemType a[M][N])
{
int i,j;
MatNode *h[Max],*p,*q,*r;
mh=(MatNode *)malloc(sizeof(MatNode));
mh->row=M;mh->col=N;
r=mh;
1 0 0 2
0 0 3 0
0 0 0 4
B3× 4=
mh
34
头结点
r
a.建立头结点
57
1.从一个二维矩建立其十字链表表示
for(i=0;i<Max;i++)
{
h[i]=(MatNode *)malloc(sizeof(MatNode));
h[i]->down=h[i]->right=h[i];//表明现为空表
h[i]->row=h[i]->col=-1;//设置行列表头标志
r->tag.link=h[i];//将各行列表头连接成一链表
r=h[i];
}
r->tag.link=mh; 1 0 0 20 0 3 0
0 0 0 4
B3× 4=
b.建立行列表头
mh
34 -1-1 -1-1 -1-1 -1-1
h[0] h[1] h[2] h[3]头结点
r
58
1.从一个二维矩建立其十字链表表示
1 0 0 2
0 0 3 0
0 0 0 4
B3× 4=
c.等效于十字链表
mh
34 -1-1 -1-1 -1-1 -1-1
h[0] h[1] h[2] h[3]头结点
r
-1-1
-1-1
-1-1
-1-1
h[0]
h[1]
h[2]
h[3]
59
1.从一个二维矩建立其十字链表表示
1 0 0 2
0 0 3 0
0 0 0 4
B3× 4=
mh
34 -1-1 -1-1 -1-1 -1-1
h[0] h[1] h[2] h[3]头结点
-1-1
-1-1
-1-1
-1-1
h[0]
h[1]
h[2]
h[3]
00 1
pq
q
30 2
p
q
q
20 3
pq
q q
q
32 4
p
q
d.插入非零元素
60
压缩存储的关键问题（总结）
选定有效的存储结构（尽可能的节省空间）
基于选定的存储结构，如何有效地访问数组元素，
即根据元素下标找出其值。
基于选定的存储结构，如何实现数组的各种操作。
61
本章小结本章基本学习要点如下：
(1)理解数组和一般线性表之间的差异。
(2)重点掌握数组的顺序存储结构和元素地址计算方法。
(3)掌握各种特殊矩阵如对称矩阵、上、下三角矩阵和对角矩阵的压缩存储方法。
(4)掌握稀疏矩阵的顺序存储结构 (三元组顺序表 )以及基本运算实现算法。
(5)灵活运用数组这种数据结构解决一些综合应用问题。
62
作业题教材中 p113习题 3,5和 6。
