数据结构
North China Electric Power University
Data Structure
华北电力大学计算机科学与工程系
Dept,of Computer Science&Engineering of North China Electric Power University
第四章 数组和广义表
★ 数组的逻辑结构
★ 数组的顺序存储分配
★ 矩阵的压缩存储
North China Electric Power University
★ 稀疏矩阵
★ 广义表
★ 数组的逻辑结构
North China Electric Power University
华电 计算机系一个二维数组的类型定义如下：
其中 c,d设为 1，数组可表示为：
A:array[c..m,d..n] of ElemType
A=
a11 a12 … a 1n
a21 a22 … a 2n
… … … …
am1 am2 … a mn
它可以看成是由 m个行向量或
n个列向量组成的线性表。也即，
二维数组可以看成是一种推广的线性表，这种线性表的每一个数据元素本身也是一个线性表。
类似地，
一个三维数组可以看成是数据元素为二维数组的线性表一个 n维数组可视为其数据元素为 n-1维数组的线性表。
North China Electric Power University
华电计算机系
★ 数组的顺序存储分配一,一维数组 A[1:n]
a1 a2 a3 … an-1 an
Loc(ai) = Loc(a1) + (i-1)? k
A[1:n] = ( a1,a2,a3,…,an )
若已知每个元素占 k 个存储单元，并且知道第一个元素的存储地址 Loc(a1),则
North China Electric Power University
华电 计算机系二,二维数组 A[1:m,1:n]
a11 a12 a13 … … a1n
a21 a22 a23 … … a2n
A[1:m,1:n] = … …
… …
am1 am2 am3 … … amn
行序为主分配方式列序为主分配方式
North China Electric Power University
华电 计算机系
a11,,,a1n a21,,,a2n a31,,,aij,,,amn
第 1行 第 2行
……
a11 a12 a13 … … a1n
a21 a22 a23 … … a2n
A[1:m,1:n] = … …
… …
am1 am2 am3 … … amn
1,行序为主序分配方式
North China Electric Power University
华电 计算机系
a11 a12 a13 … … a1n
a21 a22 a23 … … a2n
a31 a32 a33 … … a3n
A[1:m,1:n] = … …
… … aij
… …
am1 am2 am3 … … amn
i-1 行若已知每个元素占 k个存储单元，并且知道第一个元素的存储地址 LOC(a11),则
Loc(aij) = Loc(a11) + (i?1)?n?k + (j?1)?k
= Loc(a11) + [ (i?1)?n+(j?1) ]?k
North China Electric Power University
华电 计算机系
a11,,,am1 a12,,,am2 a13,,,aij,,,amn
第 1列 第 2列
……
a11 a12 a13 … … a1n
a21 a22 a23 … … a2n
A[1:m,1:n]= … …
… …
am1 am2 am3 … … amn
2,列序为主序分配方式
North China Electric Power University
a11 a12 a13 … … a1n
a21 a22 a23 … … a2n
a31 a32 a33 … … a3n
A[1:m,1:n] = … …
… … aij
… …
am1 am2 am3 … … amn
j-1 列若已知每个元素占 k个存储单元，并且知道第一个元素的存储地址 LOC(a11),则
Loc(aij) = Loc(a11) + (j?1)?m?k + (i?1)?k
= Loc(a11) + [ (j?1)?m+(i?1) ]?k
North China Electric Power University
华电 计算机系
a11 a12 a13 … … a1n
a21 a22 a23 … … a2n
A = … …
… …
am1 am2 am3 … … amn
A[ 1:m,1:n ]
所谓 压缩存储 是指为多个值相同的元素,或者位置分布有规律的那些元素分配尽可能少的存储空间，而对 0元素一般情况下不分配存储空间。
传统做法
★ 矩阵的压缩存储
North China Electric Power University
华电 计算机系
a11 a12 a13 … … a1n
a21 a22 a23 … … a2n
a31 a32 a33 … … a3n
A[1:n,1:n] = … …
… …
an1 an2 an3 … … ann
传统做法,定义一个二维数组 A[ 1:n,1:n ]
一,对称矩阵的压缩存储一个 n 阶矩阵 A的元素满足性质
aij = aji 1≤i,j≤n
则称 矩阵 A为 n 阶对称矩阵。
North China Electric Power University
a11 a21 a22,..,..aij...,.,ann
k = 1 2 3,..,.,n*(n+1)/2
a11 a12 a13 … … a1n
a21 a22 a23 … … a2n
a31 a32 a33 … … a3n
A[1:n,1:n] = … …
… …
an1 an2 an3 … … ann
A中任意一元素 aij与 V[k] 之间存在对应关系,
k={ i?(i-1)/2+j 当 i≥ j时j?(j-1)/2+i 当 i < j时
V
North China Electric Power University
传统做法：定义一个二维数组 B[ 1:n,1:n ]
0元素
0元素二,对角矩阵的压缩存储若一个矩阵中，值非 0的元素对称地集中在主对角线两旁的一个带状区域中 (该区域之外的元素都为
0元素 )，称这样的矩阵为对角矩阵。
North China Electric Power University
华电 计算机系例,三对角矩阵的压缩存储
b11 b12
b21 b22 b23
b32 b33 b34
bn-1n
bnn-1 bnn
0元素
0元素非零元素的个数为 3n-2
B[1:n,1:n] =
North China Electric Power University
b11 b12 b21 bij...,..b22,..,..
k=1 2 3 4,..,.,3n-2
bnn
b11 b12
b21 b22 b23
b32 b33 b34
bn-1n
bnn-1 bn n
0元素
0元素
B中任一非零元素 bij 与 V[k] 之间存在对应关系：
k = 2? i + j – 2 i=[k/3]+1 j=k-2(i-1)
B[1:n,1:n] =
North China Electric Power University
华电 计算机系传统做法,定义一个二维数组 A[ 1:6,1:6 ]
一,什么是稀疏矩阵?
一个较大的矩阵中,零元素的个数相对于整个矩阵元素的总个数所占比例较大时,可以称该矩阵为一个稀疏矩阵 。
A =
15 0 0 22 0 -15
0 11 3 0 0 0
0 0 0 -6 0 0
0 0 0 0 0 0
91 0 0 0 0 0
0 0 28 0 0 0
★ 稀疏矩阵
North China Electric Power University
华电 计算机系三元组,( i,j,value )
例如,
（ 1,1,15）表示第 1行、第 1列、值为 15的元素。
（ 1,4,22）表示第 1行、第 4列、值为 22的元素。
（ 1,6,-15）表示第 1行、第 6列、值为 -15的元素。
15 0 0 22 0 -15
0 11 3 0 0 0
0 0 0 -6 0 0
0 0 0 0 0 0
91 0 0 0 0 0
0 0 28 0 0 0
二,稀疏矩阵的三元组表示
( m,n,t )
其中,m,n,t 分别表示稀疏矩阵的总的行数、
总的列数与非零元素的总个数。
North China Electric Power University
华电计算机系若一个 m?n阶稀疏矩阵具有 t个非零元素，则用 t+1个三元组来存储,其中第一个三元组分别用来给出稀疏矩阵的总行数 m、总列数 n 以及非零元素的总个数 t ；第二个三元组到第 t+1 个三元组按行序为主序的方式依次存储 t 个非零元素。
North China Electric Power University
A=
15 0 0 22 0 -15
0 11 3 0 0 0
0 0 0 -6 0 0
0 0 0 0 0 0
91 0 0 0 0 0
0 0 28 0 0 0
A[ 1:6,1:6 ]
6 6 8
1 1 15
1 4 22
1 6 -15
2 2 11
3 4 -6
2 3 3
5 1 91
6 3 28
B=
B[ 1:9,1:3 ]
华电计算机系
15 0 0 22 0 -15
0 11 3 0 0 0
0 0 0 -6 0 0
0 0 0 0 0 0
91 0 0 0 0 0
0 0 28 0 0 0
M=
15 0 0 0 91 0
0 11 0 0 0 0
0 3 0 0 0 28
22 0 -6 0 0 0
0 0 0 0 0 0
-15 0 0 0 0 0
N=
表示稀疏矩阵 M的三列的二维数组
1] 2] 3]
A[0,6 6 8
A[1,1 1 15
A[2,1 4 22
A[3,1 6 -15
A[4,2 2 11
A[5,2 3 3
A[6,3 4 -6
A[7,5 1 91
A[8,6 3 28
1] 2] 3]
B[0,6 6 8
B[1,1 1 15
B[2,1 5 91
B[3,2 2 11
B[4,3 2 3
B[5,3 6 28
B[6,4 1 22
B[7,4 3 -6
B[8,6 4 -15
表示稀疏矩阵 N的三列的二维数组
A= B=
North China Electric Power University
三,矩阵的转置
1)转置过程按照 B数组中元素的最终排列顺序进行由于矩阵 M的列经过转置后变为 N的行,所以可以按照 M的列序来转置,为了按顺序找到 M中的每一列的所有非 0元素,对数组 A从第一行起将每行的第二列扫描 n遍,每遍扫描分别找到矩阵 N的从第一行到第 n行的各行所有非 0元素,并产生 B数组相应的行。
Procedure transmat(A,B);
begin
(m,n,t):=(A[0,1],A[0,2],A[0,3]);
(B[0,1],[0,2],B[0,3]):=(n,m,t);
if t< >0 then
[ q:=1;
for col:=1 to n do
for p:=1 to t do
if A[p,2]=col then
[ B[q,1]:=A[p,2];
B[q,2]:=A[p,1];
B[q,3]:=A[p,3];
q:=q+1;
]
]
End;
North China Electric Power University
算法的评价
1.空间开销,3*(t+1)，当 t<1/3*(m*n)时，所需存储量比按矩形结构存储的二维数组要少。
2.时间开销,O(n*t)。常规矩阵的转置运算需要的时间为 O(n*m),
若非 0元素的个数 t与 m*n有相同的数量级时，算法 tranmat的运算量就达到了 O(m*n2)了，这时，虽然节省了一些存储空间，却浪费了大量的计算时间。
算法的改进之处：对 A数组的扫描存在着浪费现象，即 n次扫描中每次都要检查 t个元素，实际并不需要。因为：每次需要扫描的 A的元素在减少，凡在某遍扫描中已转置到 B中去的 A的元素以后就不需要在扫描了。
North China Electric Power University
2)B数组中元素的生成不是顺序的而是跳跃式的即转换按数组 A中行的顺序进行，但转换后的元素在 B中不是连续存放，而是将它放入它在 B中最终应占据的位置。
Num[1..n]:存放矩阵 N中各行非 0元素的个数 ;
Pot[1..n]:存放矩阵 N中各行第一个非 0元素在数组 B中应占的位置,
pot[1]=1
pot[j]=pot[j-1]+num[j-1] (2≤j≤n)
15 0 0 22 0 -15
0 11 3 0 0 0
0 0 0 -6 0 0
0 0 0 0 0 0
91 0 0 0 0 0
0 0 28 0 0 0
M=
j 1 2 3 4 5 6
Num[j] 2 1 2 2 0 1
Pot[j] 1 3 4 6 8 8
North China Electric Power University
Procedure fasttranmat(A,B);
Begin
(m,n,t):=(A[0,1],A[0,2],A[0,3]);
(B[0,1],B[0,2],B[0,3]):=(n,m,t);
if t< >0 then
[ for i:=1 to n do num[j]:=0;
for i:=1 to t do num[A[i,2]]:=num[A[i,2]]+1;
pot[1]:=1;
for j:=2 to n do pot[j]:=pot[j-1]+num[j-1];
for i:=1 to t do
[ k:=A[i,2];B[pot[k],1]:=A[i,2];B[pot[k],2]:=A[i,1];
B[pot[k],3]:=A[i,3];pot[k]:=pot[k]+1;]
]
End;
North China Electric Power University
四,矩阵的相乘
8 0 0 4
0 0 -2 0
3 -5 0 0
0 0 0 6
S=
0 0 7 0 -2
0 0 5 0 0
4 0 0 0 0
0 0 0 -3 0
R=
5 4 6
1 1 8
1 4 4
2 3 -2
3 1 3
3 2 -5
5 4 6
A= B=
4 5 5
1 3 7
1 5 -7
2 3 5
3 1 4
4 4 -3
由于两个稀疏矩阵的积并不一定仍是稀疏矩阵，故结果矩阵 c=s*r仍需采用通常的矩形结构的二维数组存储方式。
North China Electric Power University
在经典算法中，不管元素是否为 0都需要相乘，但实际上只有 S[i,k]和 R[k,j]均不为 0时，乘积才不为 0。因此，需在 A、
B中找出相应的各对元素 (即数组 A中第二列的值与数组 B中第一列的值相等的元素 )相乘即可。
为了得到非 0的乘积，对 A中每一行的元素 (i,k,Sik)，需要在 B中找到所有相应的元素 (k,j,Rkj),为了便于在 B中寻找 R中第
k行的第一个非 0元素，和前面类似，需设置两个数组 Num[1:n]
和 Pot[1:n]，其中 num[k]表示 R中第 k行非 0元素的个数； pot[k]
表示 R中第 k行第一个非 0元素在 B中的位置。
pot[1]=1
pot[j]=pot[j-1]+num[j-1] (2≤j≤n)
North China Electric Power University
Procedure matrix-multiplication(A,B,C);
Begin
(m,n,t1):=(A[0,1],A[0,2],A[0,3]);
if n=B[0,1] then (p,t2):=(B[0,2],B[0,3])
else [ Write(‘Incompatible matrix’);exit;]
if t1*t2=0 then exit; {乘积为 0矩阵 }
for i:=1 to m do
for j:=1 to p do C[i,j]:=0;
for i:=1 to n do num[i]:=0;
for i:=1 to t2 do num[B[i,1]]:=num[B[i,1]]+1;
pot[1]:=0;
for i:=2 to n+1 do pot[i]:=pot[i-1]+num[i-1];
for i:=1 to t1 do
[ k:=a[i,2];
for j:=pot[k] to pot[k+1]-1 do
C[A[i,1],B[j,2]]:=C[A[i,1],B[j,2]]+A[i,3]*B[j,3];]
End;
North China Electric Power University
North China Electric Power University
华电 计算机系若以行序为主序 依次将所有非零元素链接起来则可以得到如下所示的一个带头结点的循环链表：
例如,如下一个稀疏矩阵：
A = 4 0 0 20 3 0 0
5 0 -1 0
1 1 4 1 4 2 2 2 3 3 1 5 3 33 4 5 -1
A
北航 计算机系三,稀疏矩阵的 十字 链表表示
North China Electric Power University
^
(4),修改有关的边结点的 adjvex 域的内容。
华电计算机系为稀疏矩阵的每一行设置一个单独的循环链表，
同样为每一列设置一个单独的循环链表。 矩阵中每一个非零元素同时包含在两个循环链表中,即包含在它所在的行链表与所在的列链表中,即两个链表的交汇处 。
十字链表
North China Electric Power University
华电 计算机系对于一个 m?n的稀疏矩阵,分别建立
m个行的循环链表与 n个列的循环链表,每个非零元素用一个链结点存储,
其中,row,col,value 分别表示某个非零元素所在的行号、列号和元素的值； down 和 right 分别为向下与 向右指针，分别用来链接同一列中的与同一行中的所有非零元素对应的链结点。
链结点的构造为,
row col value
down right
North China Electric Power University
华电计算机系华电 计算机系一共设置 MAX( m,n )个头结点,
0 0
down right
对 m个行链表，分别设置 m个行链表表头结点。
表头结点的构造与链表中其他链结点一样,只是令
row与 col 的值分别为 0,right域指向相应行链表的第一个结链点。同理，对 n个列链表,分别设置 n个列链表表头结点 。 其中,令 row和 col的值分别为 0,down
域指向相应列链表的第一个链结点。
North China Electric Power University
华电 计算机系另外，再设置一个总的头结点 (如下所示 ),通过
value域 把所有表头结点也链接成一个循环链表。
m n value总头结点,
North China Electric Power University
B=
对于如下稀疏矩阵 B如下,
十字链表表示如下,
4 0 0 2
0 2 9 0
4 6 0 -5
North China Electric Power University
华电 计算机系
3 4 0 0 3 0 3 0 3 0
0 0 1 1 4 3 4 2
0 0 2 2 2 2 3 9
0 0
0 0 3 1 4 3 2 6 3 4 -5
0 0 0
1
HEAD
4 0 0 2
0 2 9 0
4 6 0 -5
★ 广义表
( a1,a2,a3,……,an-1,an )
若 ai 为不可再分割的原子元素,则称 ai 为 原子元素 ；
若 ai 为一个子表，则称 ai 为 表元素 。 这里,用小写字母表示原子元素，用大写字母表示表元素。
一,广义表的定义一个长度为 n≥ 0 的广义表是一个数据结构
LS = ( a1,a2,……,an-1,an )
其中,LS为广义表的名字,ai为表中元素； ai 可以是原子元素，也可以是一个子表。 n 为表的长 度，长度为 0 的表称为空表。
North China Electric Power University
A=( ); 长度为 0的空表。
B=(( )); 是以空表作为唯一元素的表，长度为 1。
C=(a,b);有两个元素 a,b长度为 2。
D=(a,(b,c)) ; 含有一个原子元素和一广义表，长度为 2。
E=(x,D,y) ; 长度为 3的广义表。
F=(a,F); 长度为 2的递归的广义表。
……
广义表的例子：
a b
a
b c
x y
a
b c
a
C D E
D
F
表元素原子元素
North China Electric Power University
列表可以是一个递归的表，即列表可以是本身的一个子表。
列表可以为其他表所共享。
列表的元素可以是子表,而子表的元素还可以是子表,… 。
结论 1
结论 2
结论 3
定义：一个表的深度是指表中所包含的括号的层数。
North China Electric Power University
一,广义表的存储
flag info link
其中,flag为标志位,令
1 表示本结点为表结点
0 表示本结点为原子结点当 flag=0时,info域存放相应原子元素的信息 ；
当 flag=1时,info域存放子表第一个元素对应的链结点的地址；
link域存放本元素同一层的下一个元素所在链接点的地址，
当本元素为所在层的最后一个元素时,link域为 nil。
flag={
广义表一般采用链式存储结构，链结点的构造可以为
North China Electric Power University
A=Nil
B=(( )) 1 ^ ^B
C=(a,b) 0 a 0 b ^
D=(a,(b,c))
C
0 aD
0 b 0 c ^
1 ^
E=(x,D,y) 0 xE 1
0 y ^
F=(a,F) 0 aF 1 ^
North China Electric Power University
多元多项式的广义表表示
P(x,y,z) = x10y3z2+2x8y3z2+3x8y2z2+x4y4z+6x2y4z+2yz
= ((x10+2x8)y3+3x8y2)z2+((x4+6x2)y4+2y)z
P(z) = Az2+Bz
A(x,y) = (x10+2x8)y3+3x8y2 B(x,y) = (x4+6x2)y4+2y
A(y) = Cy3+Dy2 B(y) = Ey4+Fy
C(x) = x10+2x8
D(x) = 3x8
E(x) = x4+6x2
F(x) = 2x0
华电 计算机系
North China Electric Power University
coef exp link
若链结点的构造设计为其中,coef 表示多项式的某一项的系数,
exp 表示多项式的某一项的指数,
link 为链接多项式中同一层各链结点的指针,
华电计算机系相当于 data域
North China Electric Power University
z 2
1 ^y 3 2 ^ y 4
x 3 8 ^
1 ^
P
6 2 ^1 4x 1 10 2 8 ^ x
x 2 0 ^
P(x,y,z) = x10y3z2+2x8y3z2+3x8y2z2+x4y4z+6x2y4z+2yz
= ((x10+2x8)y3+3x8y2)z2+((x4+6x2)y4+2y)z
该多项式的广义表的表示形式为：
华电 计算机系
North China Electric Power University
North China Electric Power University
North China Electric Power University
Data Structure
华北电力大学计算机科学与工程系
Dept,of Computer Science&Engineering of North China Electric Power University
第四章 数组和广义表
★ 数组的逻辑结构
★ 数组的顺序存储分配
★ 矩阵的压缩存储
North China Electric Power University
★ 稀疏矩阵
★ 广义表
★ 数组的逻辑结构
North China Electric Power University
华电 计算机系一个二维数组的类型定义如下：
其中 c,d设为 1，数组可表示为：
A:array[c..m,d..n] of ElemType
A=
a11 a12 … a 1n
a21 a22 … a 2n
… … … …
am1 am2 … a mn
它可以看成是由 m个行向量或
n个列向量组成的线性表。也即，
二维数组可以看成是一种推广的线性表，这种线性表的每一个数据元素本身也是一个线性表。
类似地，
一个三维数组可以看成是数据元素为二维数组的线性表一个 n维数组可视为其数据元素为 n-1维数组的线性表。
North China Electric Power University
华电计算机系
★ 数组的顺序存储分配一,一维数组 A[1:n]
a1 a2 a3 … an-1 an
Loc(ai) = Loc(a1) + (i-1)? k
A[1:n] = ( a1,a2,a3,…,an )
若已知每个元素占 k 个存储单元，并且知道第一个元素的存储地址 Loc(a1),则
North China Electric Power University
华电 计算机系二,二维数组 A[1:m,1:n]
a11 a12 a13 … … a1n
a21 a22 a23 … … a2n
A[1:m,1:n] = … …
… …
am1 am2 am3 … … amn
行序为主分配方式列序为主分配方式
North China Electric Power University
华电 计算机系
a11,,,a1n a21,,,a2n a31,,,aij,,,amn
第 1行 第 2行
……
a11 a12 a13 … … a1n
a21 a22 a23 … … a2n
A[1:m,1:n] = … …
… …
am1 am2 am3 … … amn
1,行序为主序分配方式
North China Electric Power University
华电 计算机系
a11 a12 a13 … … a1n
a21 a22 a23 … … a2n
a31 a32 a33 … … a3n
A[1:m,1:n] = … …
… … aij
… …
am1 am2 am3 … … amn
i-1 行若已知每个元素占 k个存储单元，并且知道第一个元素的存储地址 LOC(a11),则
Loc(aij) = Loc(a11) + (i?1)?n?k + (j?1)?k
= Loc(a11) + [ (i?1)?n+(j?1) ]?k
North China Electric Power University
华电 计算机系
a11,,,am1 a12,,,am2 a13,,,aij,,,amn
第 1列 第 2列
……
a11 a12 a13 … … a1n
a21 a22 a23 … … a2n
A[1:m,1:n]= … …
… …
am1 am2 am3 … … amn
2,列序为主序分配方式
North China Electric Power University
a11 a12 a13 … … a1n
a21 a22 a23 … … a2n
a31 a32 a33 … … a3n
A[1:m,1:n] = … …
… … aij
… …
am1 am2 am3 … … amn
j-1 列若已知每个元素占 k个存储单元，并且知道第一个元素的存储地址 LOC(a11),则
Loc(aij) = Loc(a11) + (j?1)?m?k + (i?1)?k
= Loc(a11) + [ (j?1)?m+(i?1) ]?k
North China Electric Power University
华电 计算机系
a11 a12 a13 … … a1n
a21 a22 a23 … … a2n
A = … …
… …
am1 am2 am3 … … amn
A[ 1:m,1:n ]
所谓 压缩存储 是指为多个值相同的元素,或者位置分布有规律的那些元素分配尽可能少的存储空间，而对 0元素一般情况下不分配存储空间。
传统做法
★ 矩阵的压缩存储
North China Electric Power University
华电 计算机系
a11 a12 a13 … … a1n
a21 a22 a23 … … a2n
a31 a32 a33 … … a3n
A[1:n,1:n] = … …
… …
an1 an2 an3 … … ann
传统做法,定义一个二维数组 A[ 1:n,1:n ]
一,对称矩阵的压缩存储一个 n 阶矩阵 A的元素满足性质
aij = aji 1≤i,j≤n
则称 矩阵 A为 n 阶对称矩阵。
North China Electric Power University
a11 a21 a22,..,..aij...,.,ann
k = 1 2 3,..,.,n*(n+1)/2
a11 a12 a13 … … a1n
a21 a22 a23 … … a2n
a31 a32 a33 … … a3n
A[1:n,1:n] = … …
… …
an1 an2 an3 … … ann
A中任意一元素 aij与 V[k] 之间存在对应关系,
k={ i?(i-1)/2+j 当 i≥ j时j?(j-1)/2+i 当 i < j时
V
North China Electric Power University
传统做法：定义一个二维数组 B[ 1:n,1:n ]
0元素
0元素二,对角矩阵的压缩存储若一个矩阵中，值非 0的元素对称地集中在主对角线两旁的一个带状区域中 (该区域之外的元素都为
0元素 )，称这样的矩阵为对角矩阵。
North China Electric Power University
华电 计算机系例,三对角矩阵的压缩存储
b11 b12
b21 b22 b23
b32 b33 b34
bn-1n
bnn-1 bnn
0元素
0元素非零元素的个数为 3n-2
B[1:n,1:n] =
North China Electric Power University
b11 b12 b21 bij...,..b22,..,..
k=1 2 3 4,..,.,3n-2
bnn
b11 b12
b21 b22 b23
b32 b33 b34
bn-1n
bnn-1 bn n
0元素
0元素
B中任一非零元素 bij 与 V[k] 之间存在对应关系：
k = 2? i + j – 2 i=[k/3]+1 j=k-2(i-1)
B[1:n,1:n] =
North China Electric Power University
华电 计算机系传统做法,定义一个二维数组 A[ 1:6,1:6 ]
一,什么是稀疏矩阵?
一个较大的矩阵中,零元素的个数相对于整个矩阵元素的总个数所占比例较大时,可以称该矩阵为一个稀疏矩阵 。
A =
15 0 0 22 0 -15
0 11 3 0 0 0
0 0 0 -6 0 0
0 0 0 0 0 0
91 0 0 0 0 0
0 0 28 0 0 0
★ 稀疏矩阵
North China Electric Power University
华电 计算机系三元组,( i,j,value )
例如,
（ 1,1,15）表示第 1行、第 1列、值为 15的元素。
（ 1,4,22）表示第 1行、第 4列、值为 22的元素。
（ 1,6,-15）表示第 1行、第 6列、值为 -15的元素。
15 0 0 22 0 -15
0 11 3 0 0 0
0 0 0 -6 0 0
0 0 0 0 0 0
91 0 0 0 0 0
0 0 28 0 0 0
二,稀疏矩阵的三元组表示
( m,n,t )
其中,m,n,t 分别表示稀疏矩阵的总的行数、
总的列数与非零元素的总个数。
North China Electric Power University
华电计算机系若一个 m?n阶稀疏矩阵具有 t个非零元素，则用 t+1个三元组来存储,其中第一个三元组分别用来给出稀疏矩阵的总行数 m、总列数 n 以及非零元素的总个数 t ；第二个三元组到第 t+1 个三元组按行序为主序的方式依次存储 t 个非零元素。
North China Electric Power University
A=
15 0 0 22 0 -15
0 11 3 0 0 0
0 0 0 -6 0 0
0 0 0 0 0 0
91 0 0 0 0 0
0 0 28 0 0 0
A[ 1:6,1:6 ]
6 6 8
1 1 15
1 4 22
1 6 -15
2 2 11
3 4 -6
2 3 3
5 1 91
6 3 28
B=
B[ 1:9,1:3 ]
华电计算机系
15 0 0 22 0 -15
0 11 3 0 0 0
0 0 0 -6 0 0
0 0 0 0 0 0
91 0 0 0 0 0
0 0 28 0 0 0
M=
15 0 0 0 91 0
0 11 0 0 0 0
0 3 0 0 0 28
22 0 -6 0 0 0
0 0 0 0 0 0
-15 0 0 0 0 0
N=
表示稀疏矩阵 M的三列的二维数组
1] 2] 3]
A[0,6 6 8
A[1,1 1 15
A[2,1 4 22
A[3,1 6 -15
A[4,2 2 11
A[5,2 3 3
A[6,3 4 -6
A[7,5 1 91
A[8,6 3 28
1] 2] 3]
B[0,6 6 8
B[1,1 1 15
B[2,1 5 91
B[3,2 2 11
B[4,3 2 3
B[5,3 6 28
B[6,4 1 22
B[7,4 3 -6
B[8,6 4 -15
表示稀疏矩阵 N的三列的二维数组
A= B=
North China Electric Power University
三,矩阵的转置
1)转置过程按照 B数组中元素的最终排列顺序进行由于矩阵 M的列经过转置后变为 N的行,所以可以按照 M的列序来转置,为了按顺序找到 M中的每一列的所有非 0元素,对数组 A从第一行起将每行的第二列扫描 n遍,每遍扫描分别找到矩阵 N的从第一行到第 n行的各行所有非 0元素,并产生 B数组相应的行。
Procedure transmat(A,B);
begin
(m,n,t):=(A[0,1],A[0,2],A[0,3]);
(B[0,1],[0,2],B[0,3]):=(n,m,t);
if t< >0 then
[ q:=1;
for col:=1 to n do
for p:=1 to t do
if A[p,2]=col then
[ B[q,1]:=A[p,2];
B[q,2]:=A[p,1];
B[q,3]:=A[p,3];
q:=q+1;
]
]
End;
North China Electric Power University
算法的评价
1.空间开销,3*(t+1)，当 t<1/3*(m*n)时，所需存储量比按矩形结构存储的二维数组要少。
2.时间开销,O(n*t)。常规矩阵的转置运算需要的时间为 O(n*m),
若非 0元素的个数 t与 m*n有相同的数量级时，算法 tranmat的运算量就达到了 O(m*n2)了，这时，虽然节省了一些存储空间，却浪费了大量的计算时间。
算法的改进之处：对 A数组的扫描存在着浪费现象，即 n次扫描中每次都要检查 t个元素，实际并不需要。因为：每次需要扫描的 A的元素在减少，凡在某遍扫描中已转置到 B中去的 A的元素以后就不需要在扫描了。
North China Electric Power University
2)B数组中元素的生成不是顺序的而是跳跃式的即转换按数组 A中行的顺序进行，但转换后的元素在 B中不是连续存放，而是将它放入它在 B中最终应占据的位置。
Num[1..n]:存放矩阵 N中各行非 0元素的个数 ;
Pot[1..n]:存放矩阵 N中各行第一个非 0元素在数组 B中应占的位置,
pot[1]=1
pot[j]=pot[j-1]+num[j-1] (2≤j≤n)
15 0 0 22 0 -15
0 11 3 0 0 0
0 0 0 -6 0 0
0 0 0 0 0 0
91 0 0 0 0 0
0 0 28 0 0 0
M=
j 1 2 3 4 5 6
Num[j] 2 1 2 2 0 1
Pot[j] 1 3 4 6 8 8
North China Electric Power University
Procedure fasttranmat(A,B);
Begin
(m,n,t):=(A[0,1],A[0,2],A[0,3]);
(B[0,1],B[0,2],B[0,3]):=(n,m,t);
if t< >0 then
[ for i:=1 to n do num[j]:=0;
for i:=1 to t do num[A[i,2]]:=num[A[i,2]]+1;
pot[1]:=1;
for j:=2 to n do pot[j]:=pot[j-1]+num[j-1];
for i:=1 to t do
[ k:=A[i,2];B[pot[k],1]:=A[i,2];B[pot[k],2]:=A[i,1];
B[pot[k],3]:=A[i,3];pot[k]:=pot[k]+1;]
]
End;
North China Electric Power University
四,矩阵的相乘
8 0 0 4
0 0 -2 0
3 -5 0 0
0 0 0 6
S=
0 0 7 0 -2
0 0 5 0 0
4 0 0 0 0
0 0 0 -3 0
R=
5 4 6
1 1 8
1 4 4
2 3 -2
3 1 3
3 2 -5
5 4 6
A= B=
4 5 5
1 3 7
1 5 -7
2 3 5
3 1 4
4 4 -3
由于两个稀疏矩阵的积并不一定仍是稀疏矩阵，故结果矩阵 c=s*r仍需采用通常的矩形结构的二维数组存储方式。
North China Electric Power University
在经典算法中，不管元素是否为 0都需要相乘，但实际上只有 S[i,k]和 R[k,j]均不为 0时，乘积才不为 0。因此，需在 A、
B中找出相应的各对元素 (即数组 A中第二列的值与数组 B中第一列的值相等的元素 )相乘即可。
为了得到非 0的乘积，对 A中每一行的元素 (i,k,Sik)，需要在 B中找到所有相应的元素 (k,j,Rkj),为了便于在 B中寻找 R中第
k行的第一个非 0元素，和前面类似，需设置两个数组 Num[1:n]
和 Pot[1:n]，其中 num[k]表示 R中第 k行非 0元素的个数； pot[k]
表示 R中第 k行第一个非 0元素在 B中的位置。
pot[1]=1
pot[j]=pot[j-1]+num[j-1] (2≤j≤n)
North China Electric Power University
Procedure matrix-multiplication(A,B,C);
Begin
(m,n,t1):=(A[0,1],A[0,2],A[0,3]);
if n=B[0,1] then (p,t2):=(B[0,2],B[0,3])
else [ Write(‘Incompatible matrix’);exit;]
if t1*t2=0 then exit; {乘积为 0矩阵 }
for i:=1 to m do
for j:=1 to p do C[i,j]:=0;
for i:=1 to n do num[i]:=0;
for i:=1 to t2 do num[B[i,1]]:=num[B[i,1]]+1;
pot[1]:=0;
for i:=2 to n+1 do pot[i]:=pot[i-1]+num[i-1];
for i:=1 to t1 do
[ k:=a[i,2];
for j:=pot[k] to pot[k+1]-1 do
C[A[i,1],B[j,2]]:=C[A[i,1],B[j,2]]+A[i,3]*B[j,3];]
End;
North China Electric Power University
North China Electric Power University
华电 计算机系若以行序为主序 依次将所有非零元素链接起来则可以得到如下所示的一个带头结点的循环链表：
例如,如下一个稀疏矩阵：
A = 4 0 0 20 3 0 0
5 0 -1 0
1 1 4 1 4 2 2 2 3 3 1 5 3 33 4 5 -1
A
北航 计算机系三,稀疏矩阵的 十字 链表表示
North China Electric Power University
^
(4),修改有关的边结点的 adjvex 域的内容。
华电计算机系为稀疏矩阵的每一行设置一个单独的循环链表，
同样为每一列设置一个单独的循环链表。 矩阵中每一个非零元素同时包含在两个循环链表中,即包含在它所在的行链表与所在的列链表中,即两个链表的交汇处 。
十字链表
North China Electric Power University
华电 计算机系对于一个 m?n的稀疏矩阵,分别建立
m个行的循环链表与 n个列的循环链表,每个非零元素用一个链结点存储,
其中,row,col,value 分别表示某个非零元素所在的行号、列号和元素的值； down 和 right 分别为向下与 向右指针，分别用来链接同一列中的与同一行中的所有非零元素对应的链结点。
链结点的构造为,
row col value
down right
North China Electric Power University
华电计算机系华电 计算机系一共设置 MAX( m,n )个头结点,
0 0
down right
对 m个行链表，分别设置 m个行链表表头结点。
表头结点的构造与链表中其他链结点一样,只是令
row与 col 的值分别为 0,right域指向相应行链表的第一个结链点。同理，对 n个列链表,分别设置 n个列链表表头结点 。 其中,令 row和 col的值分别为 0,down
域指向相应列链表的第一个链结点。
North China Electric Power University
华电 计算机系另外，再设置一个总的头结点 (如下所示 ),通过
value域 把所有表头结点也链接成一个循环链表。
m n value总头结点,
North China Electric Power University
B=
对于如下稀疏矩阵 B如下,
十字链表表示如下,
4 0 0 2
0 2 9 0
4 6 0 -5
North China Electric Power University
华电 计算机系
3 4 0 0 3 0 3 0 3 0
0 0 1 1 4 3 4 2
0 0 2 2 2 2 3 9
0 0
0 0 3 1 4 3 2 6 3 4 -5
0 0 0
1
HEAD
4 0 0 2
0 2 9 0
4 6 0 -5
★ 广义表
( a1,a2,a3,……,an-1,an )
若 ai 为不可再分割的原子元素,则称 ai 为 原子元素 ；
若 ai 为一个子表，则称 ai 为 表元素 。 这里,用小写字母表示原子元素，用大写字母表示表元素。
一,广义表的定义一个长度为 n≥ 0 的广义表是一个数据结构
LS = ( a1,a2,……,an-1,an )
其中,LS为广义表的名字,ai为表中元素； ai 可以是原子元素，也可以是一个子表。 n 为表的长 度，长度为 0 的表称为空表。
North China Electric Power University
A=( ); 长度为 0的空表。
B=(( )); 是以空表作为唯一元素的表，长度为 1。
C=(a,b);有两个元素 a,b长度为 2。
D=(a,(b,c)) ; 含有一个原子元素和一广义表，长度为 2。
E=(x,D,y) ; 长度为 3的广义表。
F=(a,F); 长度为 2的递归的广义表。
……
广义表的例子：
a b
a
b c
x y
a
b c
a
C D E
D
F
表元素原子元素
North China Electric Power University
列表可以是一个递归的表，即列表可以是本身的一个子表。
列表可以为其他表所共享。
列表的元素可以是子表,而子表的元素还可以是子表,… 。
结论 1
结论 2
结论 3
定义：一个表的深度是指表中所包含的括号的层数。
North China Electric Power University
一,广义表的存储
flag info link
其中,flag为标志位,令
1 表示本结点为表结点
0 表示本结点为原子结点当 flag=0时,info域存放相应原子元素的信息 ；
当 flag=1时,info域存放子表第一个元素对应的链结点的地址；
link域存放本元素同一层的下一个元素所在链接点的地址，
当本元素为所在层的最后一个元素时,link域为 nil。
flag={
广义表一般采用链式存储结构，链结点的构造可以为
North China Electric Power University
A=Nil
B=(( )) 1 ^ ^B
C=(a,b) 0 a 0 b ^
D=(a,(b,c))
C
0 aD
0 b 0 c ^
1 ^
E=(x,D,y) 0 xE 1
0 y ^
F=(a,F) 0 aF 1 ^
North China Electric Power University
多元多项式的广义表表示
P(x,y,z) = x10y3z2+2x8y3z2+3x8y2z2+x4y4z+6x2y4z+2yz
= ((x10+2x8)y3+3x8y2)z2+((x4+6x2)y4+2y)z
P(z) = Az2+Bz
A(x,y) = (x10+2x8)y3+3x8y2 B(x,y) = (x4+6x2)y4+2y
A(y) = Cy3+Dy2 B(y) = Ey4+Fy
C(x) = x10+2x8
D(x) = 3x8
E(x) = x4+6x2
F(x) = 2x0
华电 计算机系
North China Electric Power University
coef exp link
若链结点的构造设计为其中,coef 表示多项式的某一项的系数,
exp 表示多项式的某一项的指数,
link 为链接多项式中同一层各链结点的指针,
华电计算机系相当于 data域
North China Electric Power University
z 2
1 ^y 3 2 ^ y 4
x 3 8 ^
1 ^
P
6 2 ^1 4x 1 10 2 8 ^ x
x 2 0 ^
P(x,y,z) = x10y3z2+2x8y3z2+3x8y2z2+x4y4z+6x2y4z+2yz
= ((x10+2x8)y3+3x8y2)z2+((x4+6x2)y4+2y)z
该多项式的广义表的表示形式为：
华电 计算机系
North China Electric Power University
North China Electric Power University
