chap5_数组和广义表

1、1,第五章 数组和广义表,2,5.1 数组的类型定义,5.3 稀疏矩阵的压缩存储,5.2 数组的顺序表示和实现,5.4 广义表的类型定义,5.5 广义表的表示方法,5.6 广义表操作的递归函数,3,5.1 数组的类型定义,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,基本操作:,4,二维数组的定义:,数据对象: D = aij | 0ib1-1, 0 jb2-1 数

2、据关系: R = ROW, COL ROW = | 0ib1-2, 0jb2-1 COL = | 0ib1-1, 0 jb2-2,5,基本操作：,InitArray( 2) 数组是多维的结构，而存储空间是 一个一维的结构。,有两种顺序映象的方式: 1)以行序为主序(低下标优先); 2)以列序为主序(高下标优先);,11,例如：,称为基地址或基址。,以“行序为主序”的存储映象,二维数组A中任一元素ai,j 的存储位置 LOC(i,j) = LOC(0,0) + (b2ij),a0,1,a0,0,a0,2,a1,0,a1,1,a1,2,a0,1,a0,0,a0,2,a1,0,a1,1,a1,2,L

3、,L,12,推广到一般情况，可得到 n 维数组数据元素存储位置的映象关系,称为 n 维数组的映象函数。数组元素 的存储位置是其下标的线性函数,其中 cn = L，ci-1 = bi ci , 1 i n。,LOC(j1, j2, ., jn ) = LOC(0,0,.,0) + ci ji,i,=1,n,13,课堂练习,假设c语言中有二维数组A68，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置为1000，计算： （1）数组A的体积（即存储量） （2）数组A的最后一个元素a57的第一个字节的地址； （3）假设按行存储时，元素a14的第一个字节的地址； （4）假设按列存储时

4、，元素a47的第一个字节的地址。,14,（1）数组A的体积（即存储量） 解：存储量686288,（2）数组A的最后一个元素a57的第一个字节的地址； 解：LOC（ a57 ）100028861282,15,（3）假设按行存储时，元素a14的第一个字节的地址； 解：LOC(a14)LOC(a00)(81+4)6 1000721072,（4）假设按列存储时，元素a47的第一个字节的地址； 解：LOC(a47)LOC(a00)(67+4)6 10002761276,16,以常规方法，即以二维数组表示 高阶的稀疏矩阵时产生的问题:,1) 零值元素占了很大空间;,2) 计算中进行了很多和零值的运算， 遇

5、乘法，白乘；遇除法，还需判别除数 是否为零;,怎样才能解决这些问题？,5.3 矩阵的压缩存储,17,1) 尽可能少存或不存零值元素;,解决问题的原则:,2) 尽可能减少没有实际意义的运算;,3) 操作方便; 即: a.能尽可能快地找到与下标值(i,j)对应的元素; b.能尽可能快地找到同一行或同一列的非零值元;,18,1) 特殊矩阵 值相同的元素或零元素在矩阵中的分布有一定规率 例如: 三角矩阵 对角矩阵,2) 稀疏矩阵 非零元极少且在矩阵中随机出现,有两类矩阵：,19,三角矩阵,k=1+2+i+j,k=n+(n-1)+(n-i)+(j-i),特殊矩阵,20,三角矩阵 将Ann，把它的非0元按

6、行优先，逐行、逐个存入 Bn*(n+1)/2中） 下三角矩阵中有Aij与Bk 的对应关系如下： k= i*(i+1)/2+j 0=(i,j)n 上三角矩阵中有Aij与Bk 的对应关系如下： k=i*(2*n-i+1)/2+j-i 0=(i,j)n,21,对称矩阵 满足性质：aijaji 0=j ,0=(i, j)=n （下三角） j*(j+1)/2+i 当ij, 0=(i, j)=n （上三角）,k,22,三对角矩阵 将其3条对角线上的元素存于数组B3n-2-1中，使得Bk Aij ，Aij与Bk 的对应关系如下(请推导）：,k = f（i, j）= ?,k2i+j |i-j|=1,k2+,3

7、(i-1)+,(j-i+1),2i+j,23,预习题,1.特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存储功能？为什么？ 2. 矩阵的一般转置算法的时间复杂度是多少？快速转置算法的时间复杂度是多少？ 3.使用带行逻辑链接的三元组顺序表完成矩阵相乘算法的时间复杂度是多少？,稀疏矩阵压缩存储后会失去随机存储功能。特殊矩阵由于压缩存储时是将其存储在一个线性数组向量bk中，矩阵元素下标i，j与它在向量中对应元素bk行下标k有一一对应关系，故还是随机存取的。而稀疏矩阵其压缩存储的方式是将其非零元素存储在一个三元组数组ak中，矩阵元素下标i，j与数组中对应元素ak行下标k无对应关系，故失去随机存储功能。,

8、一般转置算法：O(nutu) 快速转置算法：O(nu+tu),(mp(1+nMN) ，当M0.05 和N0.05及n 1000时， 相当于 O(mp)。,24,假设 m 行 n 列的矩阵含 t 个非零元素，则称 为稀疏因子 通常认为 0.05 的矩阵为稀疏矩阵,稀疏矩阵,25,稀疏矩阵的压缩存储方法:,一、三元组顺序表,二、行逻辑联接的顺序表,三、十字链表,26,#define MAXSIZE 12500 typedef struct int i, j; /该非零元的行下标和列下标 ElemType e; / 该非零元的值 Triple; / 三元组类型,一、三元组顺序表,typedef un

9、ion Triple dataMAXSIZE + 1; int mu, nu, tu; TSMatrix; / 稀疏矩阵类型,27,矩阵M：,三元组表（行优先）：,28,如何求转置矩阵？,M,T,将第i行j列元素变为第j行i列元素,29,用常规的二维数组表示时的算法,其时间复杂度为: O(munu),for (col=1; col=nu; +col) for (row=1; row=mu; +row) Tcolrow = Mrowcol;,30,用“三元组”表示时如何实现？,31,行列值互换,按行优先重排三元组次序,M,T,思路一,32,思路二,按照M.data中三元组的次序进行转置，并将转置

10、后置入T中恰当的位置。要找到这个恰当位置，必须预先知道M中每一列的非零元在T中的位置。,33,1 2 14,1 5 -5,2 2 -7,3 1 36,3 4 28,2 1 14,5 1 -5,2 2 -7,1 3 36,4 3 28,M,T,34,那么如何确定每一行的第一个非零元在三元组中的位置？,cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1;,M的第col列的第一个非零元转置后在T的位置,35,Status FastTransposeSMatrix(TSMatrix M, TSMatrix / Fa

11、stTransposeSMatrix,转置矩阵元素,36,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/第col列下一非零元的位置,37,分析算法FastTransposeSMatrix的时间复杂度：,时间复杂度为: O(M.nu+M.tu),for (col=1; col=M.nu; +col) for (t=1; t=M.tu; +t) for (col=2; col=M.nu; +col) for (p=1

12、; p=M.tu; +p) ,38,三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。,二、行逻辑联接的顺序表,39,为了便于随机存取任意一行的非零元，则需知道每一行的第一个非零元在三元组表的位置（位序）。因此，可以将此指示“行”信息的辅助数组固定在稀疏矩阵的三元组表结构里面。,40,#define MAXMN 500 typedef struct Triple dataMAXSIZE + 1; int rposMAXMN + 1; int mu, nu, tu; RLSMatr

13、ix; / 行逻辑链接顺序表类型,修改前述的稀疏矩阵的结构定义，增加一个数据成员rpos, 其值在稀疏矩阵的初始化函数中确定（目的是增加其随机存储特性）。,41,图4-6,（矩阵T）,42,例如：给定一组下标，求矩阵的元素值,ElemType value(RLSMatrix M, int r, int c) p = M.rposr; while (M.datap.i=r / value,时间复杂度为O（c） 接近于常数阶，具有一定随机存储特征,43,矩阵相乘,44,矩阵乘法的精典算法: for (i=1; i=m1; +i) for (j=1; j=n2; +j) Qij = 0; for (

14、k=1; k=n1; +k) Qij += Mik * Nkj; ,其时间复杂度为: O(m1n2n1),45,M中的j值和N中的i值相等的各对元素相乘即可,N,46,Q初始化; if Q是非零矩阵 / 逐行求积 for (arow=1;arow=M.mu;+arow) / 处理M的每一行 ctemp = 0; / 累加器清零 计算Q中第arow行的积并存入ctemp中； 将ctemp 中非零元压缩存储到Q.data； / for arow / if,两个带行逻辑三元组存储的稀疏矩阵相乘（QMN）的过程可大致描述如下：,47,Status MultSMatrix (RLSMatrix M, R

15、LSMatrix N, RLSMatrix / MultSMatrix,48,ctemp = 0; / 当前行各元素累加器清零 Q.rposarow = Q.tu+1; for (p=M.rposarow; p MAXSIZE) return ERROR; Q.dataQ.tu = arow, ccol, ctempccol; / 压缩存储该行非零元,处理 的每一行,M,49,分析上述算法的时间复杂度,累加器ctemp初始化的时间复杂度为(M.muN.nu)， 求Q的所有非零元的时间复杂度为(M.tuN.tu/N.mu)， 进行压缩存储的时间复杂度为(M.muN.nu)， 总的时间复杂度就是(

16、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)。,50,三、 十字链表,3 0 0 5 0 -1 0 0 2 0 0 0,1,1,3,1,4,5,2,2,-1,3,1,2,51,预习题,什么叫广义表？它和线性表有和相同和不同之处？ 什么叫广义表的表头、表尾、表长、表深？,广义表LS = ( 1, 2, , n )是递归

17、定义的线性结构， 其中：i 或为原子 或为广义表。而在线性表中i只能为原子。,当广义表LS = ( 1, 2, , n )非空，第一个元素1称为表头，剩余元素(2, , n )组成的子表称为表尾。 长度为最外层包含元素个数。深度为所含括弧的重数。,52,5.4 广义表的类型定义,ADT Glist 数据对象：Dei | i=1,2,.,n; n0; eiAtomSet 或 eiGList, AtomSet为某个数据对象 数据关系： LR| ei-1 ,eiD, 2in 基本操作: ADT Glist,53,广义表是递归定义的线性结构，,LS = ( 1, 2, , n ) 其中：i 或为原子

18、或为广义表,例如: A = ( ) F = (d, (e) D = (a,(b,c), F) C = (A, D, F) B = (a, B) = (a, (a, (a, , ) ) ),54,广义表是一个多层次的线性结构,例如：,D=(E, F),其中: E=(a, (b, c) F=(d, (e),D,E,F,a,( ),d,( ),b,c,e,55,广义表 LS = ( 1, 2, , n )的结构特点:,1) 广义表中的数据元素有相对次序;,2) 广义表的长度定义为最外层包含元素个数;,3) 广义表的深度定义为所含括弧的重数; 注意:“原子”的深度为 0 ; “空表”的深度为 1 。,

19、4) 广义表可以共享;,5) 广义表可以是一个递归的表; 递归表的深度是无穷值，长度是有限值。,56,6) 任何一个非空广义表 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)

20、) = b Tail( ( b, c) ) = ( c ),Head( ( c ) ) = c Tail( ( c ) ) = ( ),57, 结构的创建和销毁 InitGList(,基本操作, 状态函数 GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L);, 插入和删除操作 InsertFirst_GL(, 遍历 Traverse_GL(L, Visit();,58,5.5 广义表的表示方法 头、尾指针的链表结构 表结点: tag=1 hp tp 原子结点： tag=0 data,59,1) 空表 ls=

21、NIL 非空表 ls 1 表尾 表头,构造存储结构的两种分析方法:,若表头为原子，则为 0 data 否则，依次类推。,60,61,L=(a, (x, y), (x),L (x, y), (x) (x),1 1,a (x, y),62,广义表的头尾链表存储表示：,typedef enum ATOM, LIST ElemTag; / ATOM=0:原子, LIST=1:子表 typedef struct GLNode ElemTag tag; union AtomType atom; struct struct GLNode *hp, *tp; ptr; ; *GList,63,2) 空表 ls

22、 = NIL 非空表 LS=(1, 2, , n) ls 1 1 1 子表1 子表2 子表n 若子表为原子，则为 0 data 否则，依次类推。,64,例如:,a (x, y) (x),LS=( a, (x,y), (x) ),65,广义表的扩展线性链表存储表示：,typedef enum ATOM, LIST ElemTag; / ATOM=0:原子, LIST=1:子表 typedef struct GLNode ElemTag tag; union AtomType atom; struct GLNode *hp; ; struct GLNode *tp; *GList,66,课堂练习,

23、1.广义表C ( ( ( ( a ) , b ) ) ,( ( ( ) , y ) ) )，则C的长度为_，深度为_，tail( head( tail( C ) ) )_ 2.head(tail(head(a，b)，(c，d)=_,2,4,（）,b,67,3.已知下图为广义表的存储结构图，其结点结构如教材P109图5.8所示，写出下图表示的广义表：_,(x,(y),(),(),(z),68,5.6 m元多项式的表示*,P(x,y,z) = x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15,由于在m元多项式P中每一项的变元个数不确定及不均匀，因此不适合采用线

24、性表表示。,若改写为: P(x,y,z)=(x10+2x6)y3+3x5y2)z2+(x4+6x3)y4+2y)z+15,每个多项式都可看作是由一个变量加上若干个系数指数偶对组成。上述三元多项式可用以下广义表表示：,69,P=z(A,2),(B,1),(15,0) A=y(C,3),(D,2) C=x(1,10),(2,6) D=x(3,5) B=y(E,4),(F,1) E=x(1,4),(6,3) F=x(2,0),70,5.7 广义表的递归算法*,递归函数 一个含直接或间接调用本函数语 句的函数被称之为递归函数，它必须 满足以下两个条件:,1)在每一次调用自己时，必须是(在某 种意义上)

25、更接近于解; 2)必须有一个终止处理或计算的准则。,71,这一类问题可以借助算法设计 的一种方法分治法(分割求解) (Divide and Conquer)来求解,分治法的设计思想为: 对于一个输入规模为n的函数或问题， 用某种方法把输入分割成 k(1kn)个子集， 从而产生 l 个子问题，分别求解这 l 个问题， 得出 l 个问题的子解，再用某种方法把它们 组合成原来问题的解。若子问题还相当大， 则可以反复使用分治法，直至最后所分得 的子问题足够小，以至可以直接求解为止。,72,广义表从结构上可以分解成,广义表 = 表头 + 表尾,或者,广义表 = 子表1 + 子表2 + + 子表n,因此常

26、利用分治法求解。,73,下面采用广义表的头尾链表存储表示：,typedef enum ATOM, LIST ElemTag; / ATOM=0:原子, LIST=1:子表 typedef struct GLNode ElemTag tag; union AtomType atom; struct struct GLNode *hp, *tp; ptr; ; *GList,74,例一 求广义表的深度,例二 复制广义表,例三 创建广义表的存储结构,75,广义表的深度=Max 子表的深度 +1,例一 求广义表的深度,空表的深度 = 1 原子的深度 = 0,76,int GlistDepth(Glis

27、t L) if (!L) return 1; if (L-tag = ATOM) return 0; for (max=0, pp=L; pp; pp=pp-ptr.tp) dep = GlistDepth(pp-ptr.hp); if (dep max) max = dep; return max + 1; / GlistDepth,77,若 ls= NIL 则 newls = NIL 否则 由 表头ls.hp 复制得 newhp 由 表尾 ls.tp 复制得 newtp 构造结点 newls, 并使 newls.hp = newhp, newls.tp = newtp,例二 复制广义表,7

28、8,Status CopyGList(Glist / CopyGList,79,例三 创建广义表的存储结构,根据 LS = (1, 2, , n ) 建广义表 ls 若 LS = ( ) 则 ls = NIL 否则 构造表结点 ls 分解出第一个子串1, 对应建广义表的 表头 ls.hp 若剩余串非空，则构造表尾结点 ls.tp 分解出第二个子串2, 对应建广义表 依次类推，直至剩余串为空串止,80,void CreateGList(Glist / else ,重复建n个子表,81,sever(sub, hsub); / 分离出子表串hsub=i if (StrLength(hsub)=1) p-ptr.hp=(GList)malloc(size