计算机组成与结构：DS and AL_Lecture5_GLIST

1、DATA STRUCTURES ANDALGORITHMSLecture Notes 5buptsseArrays and GLists5.1数组的类型定义5.3 矩阵的压缩存储 5.2 数组的顺序表示和实现5.4 广义表的类型定义5.5 广义表的存储结构ADT Array 数据对象： Daj1,j2, .,ji,jn| ji =0,.,bi -1, i=1,2,.,n 数据关系： RR1, R2, ., Rn Ri | 0 jk bk -1, 1 k n 且k i, 0 ji bi -2, i=2,.,n ADT Array 基本操作:5.1 数组的类型定义Operations：InitAr

2、ray(&A, n, bound1, ., boundn)DestroyArray(&A)Value(A, &e, index1, ., indexn)Assign(&A, e, index1, ., indexn)InitArray(&A, n, bound1, ., boundn) 操作结果：若维数 n 和各维长度合法， 则构造相应的数组A，并 返回OK。DestroyArray(&A) 操作结果：销毁数组A。 Value(A, &e, index1, ., indexn) 初始条件：A是n维数组，e为元素变量， 随后是n 个下标值。

3、 操作结果：若各下标不超界，则e赋值为 所指定的A 的元素值，并返 回OK。 Assign(&A, e, index1, ., indexn) 初始条件：A是n维数组，e为元素 变量，随后是n 个下标值。 操作结果：若下标不超界，则将e的 值赋给所指定的A的元 素，并返OK。二维数组的定义:数据对象: D = aij | 0ib1-1, 0 jb2-1数据关系: R = ROW, COL ROW = | 0ib1-1, 0jb2-2 COL = | 0ib1-2, 0 jb2-1二维数组的定义:111110111110100100.nmmmnnnmaaaaaaaaaA5.2 数组的顺序

4、表示和实现类型特点: （1） 只有引用型操作，没有加工型操作； （2） 数组是多维的结构，而存储空间是 一个一维的结构。有两种顺序映象的方式: （1）以行序为主序 （2）以列序为主序 a00 a01 a0n-1 a10 a11 a1n-1 am-10 am-11 am-1n-1 . 按行序为主序存放 am-1n-1 . am-11 am-10 . a1n -1 . a11 a10 a0n-1 . a01 a0001n-1m*n-1n 按列序为主序存放01m-1m*n-1m am-1n-1 . a1n-1 a0n-1 . am-11 . a11 a01 am-10 . a10 a00 a00 a

5、01 . a0n-1 a10 a11 . a1n-1 am-10 am-11 am-1n-1 .称为基地址或基址以“行序为主序”的存储映象:二维数组A中任一元素ai j 的存储位置 LOC(i,j) = LOC(0,0) + (nij) L 以“列序为主序”的存储映象:二维数组A中任一元素ai j 的存储位置 LOC(i,j) = LOC(0,0) + (mji) L 推广到一般情况，可得到 n 维数组数据元素存储位置的映象关系 称为 n 维数组的映象函数。数组元素的存储位置是其下标的线性函数。其中 cn = L，ci-1 = bi ci , 1 i n。LOC(j1, j2, ., jn )

6、 = LOC(0,0,.,0) + ci ji i=1n 特殊矩阵矩阵的压缩存储 稀疏矩阵 以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:(1) 零值元素占了很大空间;(2) 计算中进行了很多和零值的运算。(1) 尽可能少存或不存零值元素；解决问题的原则:(2) 尽可能减少没有实际意义的运算；(3) 操作方便。 即： 能尽可能快地找到与下标值(i，j)对应的元素， 能尽可能快地找到同一行或同一列的非零值元。特殊矩阵 特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。 对称矩阵元素满足条件 aij=aji 1=i , j=n的n阶矩阵。按行序为主序： a11 a12 . . a1n

7、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 jiijjjijiik, 12/ ) 1(12/ ) 1(，三角矩阵按行序为主序：Loc( aij)=Loc(a11)+ i*(i-1)/2 +(j-1)*L a11 0 0 . 0 a21 a22 0 . 0 an1 an2 an3. ann . 0a11 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

8、 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 .a11 a12 a21 a22 a23 ann-1 ann k=0 1 2 3 4 3(n-1) 按行序为主序：稀疏矩阵 假设 m 行 n 列的矩阵含 t 个非零元素，则称 为稀疏因子。 通常认为 0.05 的矩阵为稀疏矩阵。nmt稀疏矩阵的压缩存储方法:一、三元组顺序表二、行逻辑链接的顺序表三、 十字链表 #define MAXSIZE 12500 typedef struct int i, j; /该非零元的行下标和列下标 Elem

9、Type e; / 该非零元的值 Triple; / 三元组类型一、三元组顺序表typedef union Triple dataMAXSIZE + 1; int mu, nu, tu; /mu:行数，nu:列数，非零元个数 TSMatrix; / 稀疏矩阵类型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 e 0 1 2 3 4 5 6 7 87600070015000001800000240001400003000000000009120M76000700150000018000002400014000030

10、00000000009120M6700000000014000000007000000024009018000121500300NT如何求转置矩阵？用常规的二维数组表示时的算法 其时间复杂度为: O(munu) for (col=1; col=nu; +col) for (row=1; row=mu; +row) Tcolrow = Mrowcol;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 e0 1 2 3 4 5 6 7 8i j e7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3

11、1 9 3 4 24 4 6 -7 6 3 14 0 1 2 3 4 5 6 7 8?M.dataT.data解决思路： 只要做到 将矩阵行、列值互换； 将每个三元组中的i和j相互调换； 重排三元组次序，使T.data中元素以T的行(M的列)为主序方法一：按M的列序转置 按T.data中三元组次序依次在M.data中找到相应的三元组进行转置，即按照矩阵M的列序来进行置换。 为找到M中每一列所有非零元素，需对其三元组表M.data从第一行起扫描一遍。由于M.data中以M行序为主序，所以由此得到的恰是T.data中应有的顺序。6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4

12、3 24 5 2 18 6 1 15 6 4 -7 i j e0 1 2 3 4 5 6 7 8M.data7 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 e0 1 2 3 4 5 6 7 8T.dataqppppppppqqqqppppppppcol=1col=2Status TransposeSMatix(TSMatrix M,TSMatrix &T) /采用三元组表存储表示，求稀疏矩阵M的转置矩阵T。 T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; If (T.tu) q=1; f

13、or (col=1; col=M.nu; +col) for (p=1; p=M.tu; +p) If (M.datap.j = col) T.dataq.i = M.datap.j; T.dataq.j = M.datap.i; T.dataq.e = M.datap.e; +q; return OK;/TransposeSMatrixT(n)=O(nu*tu)T(n)=O(mu*nu2)方法二：快速转置 按M.data中三元组次序转置，转置结果放入T.data中恰当位置。 此法关键是要预先确定M中每一列第一个非零元在T.data中位置，为确定这些位置，转置前应先求得M的每一列中非零元个数。

14、实现：设两个数组numcol：表示矩阵M中第col列中非零元个数cpotcol：指示M中第col列第一个非零元在T.data中位置显然有：cpot1=1;cpotcol=cpotcol-1+numcol-1; (2col M.nu)7600070015000001800000240001400003000000000009120M6 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 e 0 1 2 3 4 5 6 7 8for (col=1; col=M.nu; +col) numcol = 0;for (t=1; t

15、=M.tu; +t) +numM.datat.j;cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1; Col 1 2 3 4 5 6 7numcolcpotcolt1t1t1t1t2t2t2t10 01 3 5 7 8 8 96 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 e0 1 2 3 4 5 6 7 8M.datai j e0 1 2 3 4 5 6 7 8T.datacolnumcolcpotcol112232352

16、4715806817907 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 pppppppp46297536 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 e0 1 2 3 4 5 6 7 8M.datai j e0 1 2 3 4 5 6 7 8T.datacolnumcolcpotcol1122323524715806817907 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

17、14 pppppppp4629753Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) for (col=1; col=M.nu; +col) numcol = 0; for (t=1; t=M.tu; +t) +numM.datat.j; cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1; for (p=1; p=M.tu; +p) / 转置矩阵

18、元素 col = M.datap.j; q = cpotcol; T.dataq.i =M.datap.j; T.dataq.j =M.datap.i; T.dataq.e =M.datap.e; +cpotcol; / for / if return OK; / FastTransposeSMatrixT(n)=O(nu+tu)T(n)=O(mu*nu) 三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。 #define MAXMN 500 typedef struct Tri

19、ple dataMAXSIZE + 1; /非零元三元组表 int rposMAXMN + 1; /各行第一个非零元的位置表 int mu, nu, tu; RLSMatrix; / 行逻辑链接顺序表类型二、行逻辑链接的顺序表000200105003M=00420120N=400160Q=Q = M N 1 1 3 1 4 5 i j e1 2 3 4 3 1 2 2 2 -1M.data 1 2 2 2 1 1 i j e 1 2 3 4 3 2 4 3 1 -2N.data 2 1 -1 i j e 1 2 3 4 Q.dataparow 1 2 3 ropsarow 1 3 4brow

20、1 2 3 4ropsbrow 1 2 3 5ccol 1 2ctempt1tpq6p 1 2 6tpp2tq-1tp =5p1tq4 3 2 412121223-431-142-2433 1 2 3 4 M.Data i j ePQ N.Data i j e Q.Data12121223-431-142-2433 1 2 3 4 M.Data i j ePQ N.Data i j e Q.Data 12121223-431-142-2433 1 2 3 4 M.Data i j ePQ N.Data i j e Q.Data 12121223-431-142-2433 1 2 3 4 M.D

21、ata i j ePQ N.Data i j e Q.Data 12121223-431-142-2433 1 2 3 4 M.Data i j ePQ N.Data i j e Q.Data 12121223-431-142-2433 1 2 3 4 M.Data i j ePQ N.Data i j e Q.Data12121223-431-142-2433 1 2 3 4 M.Data i j ePQ N.Data i j e Q.Data 8+-3=512121223-431-142-2433 1 2 3 4 M.Data i j ePQ N.Data i j e Q.Data矩阵乘法

22、的精典算法: for (i=1; i=m1; +i) for (j=1; j=n2; +j) Qij = 0; for (k=1; k=n1; +k) Qij += Mik * Nkj; 其时间复杂度为: O(m1n2n1) Q初始化； if Q是非零矩阵 / 逐行求积 for (arow=1; arow=M.mu; +arow) / 处理M的每一行 ctemp = 0; / 累加器清零 计算Q中第arow行的积并存入ctemp 中； 将ctemp 中非零元压缩存储到Q.data； / for arow / if 两个稀疏矩阵相乘（QMN） 的过程可大致描述如下： Status MultSMa

23、trix (RLSMatrix M, RLSMatrix N, RLSMatrix &Q) if (M.nu != N.mu) return ERROR; Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; if (M.tu*N.tu != 0) / Q是非零矩阵 for (arow=1; arow=M.mu; +arow) / 处理M的每一行 / for arow / if return OK; / MultSMatrix ctemp = 0; / 当前行各元素累加器清零 Q.rposarow = Q.tu+1; if (arowM.mu) tp= M.rposa

24、row+1; else tp= M.tu+1; for (p=M.rposarow; ptp ;+p) brow=M.datap.j; if (brow N.mu ) t = N.rposbrow+1; else t = N.tu+1 for (q=N.rposbrow; q t; +q) ccol = N.dataq.j; / 乘积元素在Q中列号 ctempccol += M.datap.e * N.dataq.e; / 求得Q中第crow( =arow)行的非零元 for (ccol=1; ccol MAXSIZE) return ERROR; Q.dataQ.tu = arow, cco

25、l, ctempccol; / if处理 的每一行M分析上述算法的时间复杂度:累加器ctemp初始化的时间复杂度为(M.muN.nu)，求Q的所有非零元的时间复杂度为(M.tuN.tu/N.mu)，进行压缩存储的时间复杂度为(M.muN.nu)，总的时间复杂度就是(M.muN.nu+M.tuN.tu/N.mu)。若M是m行n列的稀疏矩阵，N是n行p列的稀疏矩阵，则M中非零元的个数 M.tu = Mmn， N中非零元的个数 N.tu = Nnp，相乘算法的时间复杂度就是 (mp(1+nMN) ，当M0.05 和N0.05及 n 1000时，相乘算法的时间复杂度就相当于 (mp)。三、 十字链表M

26、.cheadM.rhead3 0 0 50 -1 0 02 0 0 01 1 31 4 52 2-13 1 2 5.4 广义表的类型定义ADT Glist 数据对象：Dei | i=1,2,.,n; n0; eiAtomSet 或 eiGList, AtomSet为某个数据对象 数据关系： LR| ei-1 ,eiD, 2in ADT Glist 基本操作:广义表是递归定义的线性结构， LS = ( 1, 2, , n )其中：i 或为原子 或为广义表例如: A = ( ) /空表，长度为零 E=（e) /E表只有一个原子e，长度为1 F = (d, (e) /列表F的长度为2 D = (a,

27、(b,c), F) /列表F的长度为2 C = (A, D, F) /列表F的长度为3 B = (a, B) = (a, (a, (a, , ) ) ) 习惯将大写字母表示广义表的名称，小写字母表示原子。广义表是一个多层次的线性结构例如：D=(E, F)其中: E=(a, (b, c) F=(d, (e)DEFa( ) d( )bce广义表 LS = ( 1, 2, , n )的结构特点:1) 广义表中的数据元素有相对次序；2) 广义表的长度定义为最外层包含元素个数；3) 广义表的深度定义为所含括弧的重数； 注意：“原子”的深度为 0 “空表”的深度为 1 4) 广义表可以共享；5) 广义表可以是一个递归的表。 递归表的深度是无穷值，长度是有限值。 任何一个非空广义表 LS = ( 1, 2, , n) 均可分解为 表头 Head(LS) = 1 和 表尾 Tail(LS) = ( 2, , n