Ch_5_数组和广义表(数据结构)

1、1 线性结构线性结构中的中的数据元素数据元素都是非结都是非结构的构的原子类型原子类型，元素的值是不再分，元素的值是不再分解的。解的。 数组和广义表数组和广义表可以看成是线性表可以看成是线性表的扩展：表中的的扩展：表中的数据元素数据元素本身也是本身也是一个一个数据结构数据结构。5.1 数组的定义数组的定义5.3 矩阵的压缩存储矩阵的压缩存储 5.2 数组的顺序表示和实现数组的顺序表示和实现5.4 广义表的类型定义广义表的类型定义5.5 广义表的存储结构广义表的存储结构数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表 数组的定义和特点 定义mnmmnnnmaaaaaaaaaA.

2、212222111211 数组特点数组特点 数组结构固定数组结构固定 数据元素同构数据元素同构 数组运算数组运算 给定一组下标，存取相应的数据元素给定一组下标，存取相应的数据元素 给定一组下标，修改数据元素的值给定一组下标，修改数据元素的值( )( )( )( )( )( )( )( )( )5.1 数组的类型定义数组的类型定义5ADT 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,.

3、,n ADT Array 基本操作基本操作:6二维数组的定义二维数组的定义:数据对象数据对象: : D = aij | 0ib1-1, 0 jb2-1数据关系数据关系: : R = ROW, COL ROW = | 0ib1-2, 0jb2-1 COL = | 0ib1-1, 0 jb2-27基本操作基本操作：InitArray(&A, n, bound1, ., boundn)DestroyArray(&A)Value(A, &e, index1, ., indexn)Assign(&A, e, index1, ., indexn)8 InitArray(&a

4、mp;A, n, bound1, ., boundn) 操作结果：操作结果：若维数 n 和各维长度合法， 则构造相应的数组A，并 返回OK。9 DestroyArray(&A) 操作结果：操作结果：销毁数组A。10 Value(A, &e, index1, ., indexn) 初始条件：初始条件：A是n维数组，e为元素变量， 随后是n 个下标值。 操作结果：操作结果：若各下标不超界，则e赋值为 所指定的A 的元素值，并返 回OK。11 Assign(&A, e, index1, ., indexn) 初始条件：初始条件：A是n维数组，e为元素变量， 随后是n 个下标值

5、。 操作结果：操作结果：若下标不超界，则将e的值赋 给所指定的A的元素，并返回 OK。125.2 数组的顺序表示和实现数组的顺序表示和实现 类型特点类型特点:1) 只有引用型操作，没有加工型操作；2) 数组是多维的结构，而存储空间是 一个一维的结构。 有两种顺序映象的方式有两种顺序映象的方式:1)以行序为主序(低下标优先)；2)以列序为主序(高下标优先)。13例如：例如： 称为基地址基地址或基址。以以“行序为主序行序为主序”的存储映象的存储映象二维数组A中任一元素ai,j 的存储位置 LOC(i,j) = LOC(0,0) + (b2ij)a0,1a0,0a0,2a1,0a1,1a1,2a0,

6、1a0,0a0,2a1,0a1,1a1,2L L 14练习 二维数组A1218采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A97的地址为（ ） LOC(i,j) = LOC(0,0) + (b1ji)L42915例:设一本书有b1页,每页有b2行,b3列,现在统计,在j1页,j2行,j3列的字符之前一共有多少字符.j1*b2*b3+j2*b3+j30 jk bk -1三维数组三维数组16LOC(j1, j2, ., jn ) = LOC(0,0,.,0) +(j1*b2*bn + j2*b3*bn + + jn-1*bn +jn)*L推广到一般情况，可得

7、到 n 维数组数据元素存储位置的映象关系17 称为 n 维数组的映象函数。数组元素数组元素的存储位置是其下标的线性函数。的存储位置是其下标的线性函数。其中 cn = L，ci-1 = bi ci , 1 i n。LOC(j1, j2, ., jn ) = LOC(0,0,.,0) + ci ji i=1n压缩存储：压缩存储：为多个为多个值相同值相同的元素只的元素只分配一个分配一个存存储空间；对储空间；对零元不分配零元不分配空间。空间。目的：节省存储空间。目的：节省存储空间。基本概念基本概念特殊矩阵：特殊矩阵：值相同的元素值相同的元素或或零元零元在矩阵中的在矩阵中的分布有一定的规律。分布有一定的

8、规律。(对称矩阵，三角矩阵，对称矩阵，三角矩阵，对角矩阵对角矩阵).反之反之,称为称为稀疏矩阵稀疏矩阵.5.3 矩阵的压缩存储矩阵的压缩存储5.3.1 特殊矩阵特殊矩阵对称矩阵对称矩阵对角矩阵对角矩阵三角矩阵三角矩阵 a11 a12 . . a1n a21 a22 . . a2n an1 an2 . ann . n阶对称矩阵：阶对称矩阵： aij=aji 1 i,j n对称矩阵的压缩存储对称矩阵的压缩存储a11 a21 a22 a31 a32 an1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 以行序为主序以行序为主序21问题： 假设以一维数组san(n+1)/2

9、作为n阶对称阵的存储结构，则sak和矩阵元素aij存在怎样的对应关系？jiijjjiji ik, 12/ ) 1(12/ ) 1(，下三角下三角上三角上三角2.以列序为主序存储以列序为主序存储上三角上三角中的元中的元1.以行序为主序存储以行序为主序存储下三角下三角中的元中的元 a11 0 0 . 0 a21 a22 0 . 0 an1 an2 an3. ann . 0Loc(aij)=Loc(a11)+ +(j-1) 设设L为为1 i(i-1)2a11 a21 a22 a31 a32 an1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：按行序为主序：

10、下（上）三角矩阵：下（上）三角矩阵：矩阵的上（下）三角中的元均为常数矩阵的上（下）三角中的元均为常数c或零的或零的n阶矩阵。阶矩阵。前面i-1行元素个数第i行元素个数 对角矩阵 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 假设假设 m 行行 n 列的矩阵含列的矩阵含 t 个非零元素，个非零元素，令令则称则称 为为稀疏因子稀疏因子。通常认为通常认为 0.05 的矩阵为稀疏矩阵。的矩阵为稀疏矩阵。nmt稀疏矩阵：稀疏矩阵：非零元较零元少非零元较零元少,且分布

11、且分布没有一定规律没有一定规律nmt5.3.2 稀疏矩阵稀疏矩阵26 以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题问题:1) 零值元素占了很大空间零值元素占了很大空间;2) 计算中进行了很多和零值的运算，计算中进行了很多和零值的运算， 遇除法，还需判别除数是否为零遇除法，还需判别除数是否为零。271) 尽可能少存或不存零值元素；解决问题的原则解决问题的原则:2) 尽可能减少没有实际意义的运算；3) 操作方便。 即： 能尽可能快地找到与 下标值(i，j)对应的元素， 能尽可能快地找到同 一行或同一列的非零值元。76000700150000018000002400014000030000

12、00000009120MM由由(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）唯一确定）唯一确定 稀疏矩阵稀疏矩阵 压缩存储原则：只存矩阵的行列维数和每个非零元的压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值行列下标及其值29知识回顾2011-10-11 （10） 数组的定义 特殊矩阵的压缩 稀疏矩阵的压缩30稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法:一、三元组顺序表一、三元组顺序表二、行逻辑链接的顺序表二、行逻辑链接的顺序表三、三、 十

13、字链表十字链表31 #define MAXSIZE 12500 typedef struct int i, j; /该非零元的行下标和列下标 ElemType e; / 该非零元的值 Triple; / 三元组类型三元组类型一、三元组顺序表一、三元组顺序表typedef union Triple dataMAXSIZE + 1; int mu, nu, tu; / 矩阵行数、列数和非零元个数矩阵行数、列数和非零元个数 TSMatrix; / 稀疏矩阵类型稀疏矩阵类型32稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法 三元组顺序表三元组顺序表6 7 8 1 2 12 1 3 9 3 1 -3 3

14、6 14 4 3 24 5 2 18 6 1 15 6 4 -7 M.datai j v0 1 2 3 4 5 6 7 8m.data0 分分别存放别存放矩阵行数，矩阵行数，列数和非零列数和非零元个数元个数行列下标非零元值7600070015000001800000240001400003000000000009120M33如何求转置矩阵？如何求转置矩阵？028003600070500140005280000007143600 a b34用常规的二维数组表示时的算法 其时间复杂度为其时间复杂度为: O(munu) for (col=1; col=nu; +col) for (row=1; ro

15、w=mu; +row) Tcolrow = Mrowcol;35用“三元组”表示时如何实现？ 矩阵的行列值互换 下标i，j互换 重排次序36 按照b.data中三元组的次序依次在a.data中找到相应的三元组进行转置。 即：按照矩阵a的列序来进行转置。方法方法1：1 2 141 5 -52 2 -73 1 363 4 282 1 145 1 -52 2 -71 3 364 3 28方法方法1：Status TransposeSMatrix(TSMatrix M, TSMatrix &T) T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; /求出求出T的行数，

16、列数，非零元个数的行数，列数，非零元个数 if (T.tu) /存在非零元存在非零元 q=1; /q是非零元在是非零元在T的三元组中的序号的三元组中的序号, T中第中第q个非零元个非零元 for (col=1; col=M.nu; +col) for(p=1; p=M.tu; +p) if(M.datap.j=col)/每个三元组的每个三元组的i i和和j j互换互换 T.dataq.i = M.datap.j; T.dataq.j = M.datap.i; T.dataq.e= M.datap.e; +q;Return OK;/TransposeSMatrix39算法分析：算法分析： 时间复

17、杂度：O(nu.tu) 一般算法复杂度：O(mu.nu) 若tu和mu.nu是同一数量级，则O(mu.nu2)因此，此算法仅适用于tumu.nu如果能预先确定矩阵如果能预先确定矩阵M中每一列中每一列（即（即T中每一行）中每一行）的第一个非零元在的第一个非零元在三元组中的位置，则转置时，便可三元组中的位置，则转置时，便可直接放到恰当位置。直接放到恰当位置。方法方法2：转置前，应先求得转置前，应先求得M的每一列中非零的每一列中非零元个数，进而求得每一列第一个非零元个数，进而求得每一列第一个非零元在转置阵元在转置阵T.data中应有的位置。中应有的位置。cpot1 = 1cpotcol = cpot

18、col-1 + numcol-1附设两个向量附设两个向量:num和和cpot. numcol：表示矩阵：表示矩阵M中第中第col列中非列中非零元的个数零元的个数 cpotcol：指示：指示M中第中第col列的第一个列的第一个非零元在非零元在T.data中的恰当位置中的恰当位置,显然有显然有42 首先应该确定每一列的第一个非零元在三元组中的位置。1 2 151 5 -52 2 -73 1 363 4 28 col12345Numpos12011Cpotcol12445 cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + num

19、col-1;1 2 141 5 -52 2 -73 1 363 4 282 1 145 1 -52 2 -71 3 364 3 28矩阵的向量矩阵的向量cpot的值的值Status 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;/求求M中每一列含非零元的个数中每

20、一列含非零元的个数 cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1; / 求第求第col列第一个非零元在三元组中的序号列第一个非零元在三元组中的序号 cpot1 = 1cpotcol = cpotcol-1 + numcol-1for (p=1; p=M.tu; +p) col = M.datap.j; /对每个非零元，求他们的列坐标对每个非零元，求他们的列坐标jq = cpotcol; /求第求第col列第一个非零元在三元组中的序号列第一个非零元在三元组中的序号T.dataq.i = M.datap.

21、j; T.dataq.j = M.datap.i;/三元组中的三元组中的i, j互换互换T.dataq.e = M.datap.e; /非零元赋值非零元赋值 +cpotcol;/求同一列下一个非零元的序号求同一列下一个非零元的序号，更新更新cpot /for / ifreturn OK; /FastTransposeSMatrix col 1 2 3 4 5 Numcol 1 2 0 1 1 Cpotcol 1 2 4 4 5 02800360007050014046 分析算法FastTransposeSMatrix的时间复杂度：时间复杂度为时间复杂度为: : O(M.nu+M.tu)for

22、(col=1; col=M.nu; +col) for (t=1; t=M.tu; +t) for (col=2; col=M.nu; +col) for (p=1; p=M.tu; +p) 非零元在表中按行序有序存储，因非零元在表中按行序有序存储，因此此便于进行依行顺序处理的矩阵运便于进行依行顺序处理的矩阵运算算。然而，。然而，若需按行号存取某一行若需按行号存取某一行中的非零元，则需从头开始进行查中的非零元，则需从头开始进行查找找。三元组顺序表三元组顺序表(有序的双下标法有序的双下标法)特点特点:typedef struct Triple dataMAXSIZE + 1; /非零元三元组表非

23、零元三元组表int rposMAXRC + 1; /各行第一个非零元的位置表各行第一个非零元的位置表int mu, nu, tu; /矩阵的行数、列数、非零元个数矩阵的行数、列数、非零元个数 RLSMatrix; / 行逻辑链接的顺序表类型行逻辑链接的顺序表类型 为了便于为了便于随机存取任意一行随机存取任意一行的非零元，需知的非零元，需知道每一行的第一个非零元在三元组表中的位置，道每一行的第一个非零元在三元组表中的位置，修改前述的稀疏矩阵的结构定义，增加一个数修改前述的稀疏矩阵的结构定义，增加一个数据成员据成员rpos。二、行逻辑链接的顺序表二、行逻辑链接的顺序表（带行链接信息的三元组表）（带

24、行链接信息的三元组表）49例如：给定一组下标，求矩阵的元素值ElemType value(RLSMatrix M, int r, int c) p = M.rposr; while (M.datap.i=r &M.datap.j c) p+; if (M.datap.i=r & M.datap.j=c) return M.datap.e; else return 0; / value矩阵乘法的经典算法矩阵乘法的经典算法: for (i=1; i=m1; +i) for (j=1; j=n2; +j) Qij = 0; for (k=1; k=n1; +k) Qij += Mik

25、 * Nkj; 其时间复杂度为其时间复杂度为: O(m1n2n1)00020010500300420120400160M*NQ(i,j)= M(i,k)*N(k,j)n1k=11 i m11 j n2经典算法中，不论经典算法中，不论M(i,k)和和N(k,j)的值的值是否为零，都要进行一次乘法运算是否为零，都要进行一次乘法运算 在对稀疏矩阵进行运算时，应免去这种无效操作换句话说，为求Q的值，只需在M.data和N.data中找到对应的各对元素（即M.data中的j值和N.data中的i值相等的各对元素）相乘即可。53 Q初始化； if Q是非零矩阵 / 逐行求积 for (arow=1; ar

26、ow=M.mu; +arow) / 处理M的每一行 ctemp = 0; / 累加器清零 计算Q中第arow行的积并存入ctemp 中； 将ctemp 中非零元压缩存储到Q.data； / for arow / if 两个稀疏矩阵相乘（两个稀疏矩阵相乘（Q M N） 的过程可大致描述如下：的过程可大致描述如下：5400020010500300420120400160M*N55Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix &Q) if (M.nu != N.mu) return ERROR; Q.mu = M.mu; Q.n

27、u = 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; / MultSMatrix56 ctemp = 0; Q.rposarow = Q.tu+1; if (arowM.mu) tp=M.rposarow+1; else tp=M.tu+1; for (p=M.rposarow; ptp;+p) /对当前行中每一个非零元 brow=M.datap.j; /找到对应元素在N中的行号 if (brow N.mu ) t

28、= N.rposbrow+1; else t = N.tu+1 /t为该行最后一个元素的序号+1 for (q=N.rposbrow; q t; +q) ccol = N.dataq.j; / 乘积元素在Q中列号 ctempccol += M.datap.e * N.dataq.e; / for q / 求得Q中第crow( =arow)行的非零元 for (ccol=1; ccol MAXSIZE) return ERROR; Q.dataQ.tu = arow, ccol, ctempccol; / if处理 的每一行M0002001050030042012040016011314522-

29、131212221131-232412621-132458分析上述算法的时间复杂度分析上述算法的时间复杂度累加器ctemp初始化的时间复杂度为(M.muN.nu)，求Q的所有非零元的时间复杂度为(M.tuN.tu/N.mu)，进行压缩存储的时间复杂度为(M.muN.nu)，总的时间复杂度就是总的时间复杂度就是 (M.mu N.nu+M.tu N.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 i=i; p-j

30、=j; p-e=e;/生成结点生成结点if(M.rheadi=NULL) M.rheadi=p;else/寻查在行表中的插入位置寻查在行表中的插入位置for(q=M.rheadi;(q-right)&q-right-jright);p-right=q-right;q-right=p;/完成行插入完成行插入if(M.cheadj=NULL)M.cheadj=p;else/寻查在列表中的插入位置寻查在列表中的插入位置for(q=M.cheadj;(q-down)&q-down-idown);p-down=q-down;q-down=p; /完成列插入完成列插入Return OK:

31、矩阵矩阵B加到矩阵加到矩阵A上的运算上的运算(自学自学)假设两个矩阵相加后的结果为假设两个矩阵相加后的结果为A，则和矩阵，则和矩阵A中的非中的非零元零元aij只能有三种情况只能有三种情况:(1)bij(aij=0时时)；(2)aij(bij=0时时)；(3)aij+bij； 由此，当将由此，当将B加到加到A上去时，对上去时，对A矩阵的十字链表来矩阵的十字链表来说，或者插入一个新的结点，或者不变，或者是改变说，或者插入一个新的结点，或者不变，或者是改变结点的结点的val域值还有一种可能，和矩阵域值还有一种可能，和矩阵A中的某个非中的某个非零元相对应，和矩阵零元相对应，和矩阵A中是零元，即对中是零

32、元，即对A的操作是删除的操作是删除一个结点一个结点(aij+bij =0). 由此，整个运算过程可从矩阵的第一行起逐行进由此，整个运算过程可从矩阵的第一行起逐行进行对每一行都从行表头出发分别行对每一行都从行表头出发分别A和和B在该行中的第在该行中的第一个非零元结点后开始比较，按上述种情况分别处一个非零元结点后开始比较，按上述种情况分别处理理 假设非空指针假设非空指针 pa和和 pb分别指向矩阵分别指向矩阵A和和B中行值相同的两中行值相同的两个结点，个结点，pa = NULL 表明矩阵表明矩阵A在该行中没有非零元，则上在该行中没有非零元，则上述四种情况的处理过程为：述四种情况的处理过程为：1）若

33、）若pa=NULL或或pa-j pb-j，则需要在，则需要在A矩阵的链表中插矩阵的链表中插入一个值为入一个值为bij的结点。此时，需改变同一行中前一结点的的结点。此时，需改变同一行中前一结点的right域值，以及同一列中前一结点的域值，以及同一列中前一结点的down域值。域值。2) 若若pa-j j，则只要将，则只要将pa指针往右推进一步。指针往右推进一步。3) 若若pa-j = pb-j且且pa-epb-e !=0，则只要将，则只要将ai,jbi,j 的值的值送到送到pa所指结点的所指结点的e域即可，其它所有域的值都不变。域即可，其它所有域的值都不变。4) 若若pa-j = pb-j且且pa

34、-epb-e = 0，则需要在，则需要在A矩阵的链矩阵的链表中删除表中删除pa所指的结点。此时，需改变同一行中前一结点的所指的结点。此时，需改变同一行中前一结点的right域值，以及同一列中前一结点的域值，以及同一列中前一结点的down域值。域值。bij(aij=0)aij(bij=0)68知识回顾稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法:一、三元组顺序表一、三元组顺序表二、行逻辑链接的顺序表二、行逻辑链接的顺序表三、三、 十字链表十字链表2011-10-14(12)695.4 广义表的类型定义广义表的类型定义ADT Glist 数据对象数据对象：Dei | i=1,2,.,n; n0;

35、eiAtomSet 或 eiGList, AtomSet为某个数据对象 数据关系：数据关系： LR| ei-1 ,eiD, 2in ADT Glist基本操作基本操作:70广义表是递归递归定义的线性结构线性结构， LS = ( 1, 2, , n )其中：i 或为原子 或为广义表例如例如: A = ( ) F = (d, (e) D = (a,(b,c), F) C = (A, D, F) B = (a, B) = (a, (a, (a, , ) ) )71广义表是一个多层次多层次的线性结构线性结构例如：例如：D=(E, F)其中: E=(a, (b, c) F=(d, (e)DEFa( )

36、d( )bce72广义表广义表 LS = ( 1, 2, , n )的结构特点的结构特点:1) 广义表中的数据元素有相对次序次序；2) 广义表的长度长度定义为最外层包含元素个数；3) 广义表的深度深度定义为所含括弧的重数； 注意：“原子”的深度为 0 “空表”的深度为 1 4) 广义表可以共享共享；5) 广义表可以是一个递归递归的表。 递归表的深度是无穷值，长度是有限值。736) 任何一个非空广义表非空广义表 LS = ( 1, 2, , n) 均可分解为 表头表头 Head(LS) = 1 和 表尾表尾 Tail(LS) = ( 2, , n) 两部分。例如例如: D = ( E, F ) = (a, (b, c)，F )Head( D ) = E Tail( D ) = ( F )Head( E ) = a Tail( E ) = ( ( b, c) )Head( ( b, c) ) = ( b, c) Tail( ( b, c) ) = ( )Head( ( b, c) ) = b Tail( ( b, c) ) = ( c )Head( ( c ) ) = c Tail( ( c ) ) = ( )74 结构的创建和销毁结构的创建和销毁 InitGLis