第5章 数组和广义表.ppt
《第5章 数组和广义表.ppt》由会员分享,可在线阅读,更多相关《第5章 数组和广义表.ppt(97页珍藏版)》请在三一文库上搜索。
1、第五章 数组和广义表,5.1 数组的类型定义,5.3 稀疏矩阵的压缩存储,5.2 数组的顺序表示和实现,5.4 广义表的类型定义,5.5 广义表的表示方法,5.6 广义表操作的递归函数,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,基本操作:,二维数组的定义:,数据对象: D = aij | 0ib1-1, 0 jb2-1 数据关系: R = R
2、OW, COL ROW = | 0ib1-2, 0jb2-1 COL = | 0ib1-1, 0 jb2-2,基本操作:,InitArray(&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, index
3、1, ., indexn) 初始条件:A是n维数组,e为元素变量, 随后是n 个下标值。 操作结果:若各下标不超界,则e赋值为 所指定的A 的元素值,并返 回OK。,Assign(&A, e, index1, ., indexn) 初始条件:A是n维数组,e为元素变量, 随后是n 个下标值。 操作结果:若下标不超界,则将e的值赋 给所指定的A的元素,并返回 OK。,5.2 数组的顺序表示和实现,类型特点: 1) 只有引用型操作,没有加工型操作; 2) 数组是多维的结构,而存储空间是 一个一维的结构。,有两种顺序映象的方式: 1)以行序为主序(低下标优先); 2)以列序为主序(高下标优先)。,例
4、如:,称为基地址或基址。,以“行序为主序”的存储映象,二维数组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,L,推广到一般情况,可得到 n 维数组数据元素存储位置的映象关系,称为 n 维数组的映象函数。数组元素 的存储位置是其下标的线性函数。,其中 cn = L,ci-1 = bi ci , 1 i n。,LOC(j1, j2, ., jn ) = LOC(0,0,.,0) + ci ji,i,=1,n,假设 m 行 n 列的
5、矩阵含 t 个非零元素,则称 为稀疏因子。 通常认为 0.05 的矩阵为稀疏矩阵。,5.3 稀疏矩阵的压缩存储,何谓稀疏矩阵?,以常规方法,即以二维数组表示 高阶的稀疏矩阵时产生的问题:,1) 零值元素占了很大空间;,2) 计算中进行了很多和零值的运算, 遇除法,还需判别除数是否为零。,1) 尽可能少存或不存零值元素;,解决问题的原则:,2) 尽可能减少没有实际意义的运算;,3) 操作方便。 即: 能尽可能快地找到与 下标值(i,j)对应的元素, 能尽可能快地找到同 一行或同一列的非零值元。,1) 特殊矩阵 非零元在矩阵中的分布有一定规则 例如: 三角矩阵 对角矩阵,2) 随机稀疏矩阵 非零元
6、在矩阵中随机出现,有两类稀疏矩阵:,随机稀疏矩阵的压缩存储方法:,一、三元组顺序表,二、行逻辑联接的顺序表,三、 十字链表,#define MAXSIZE 12500 typedef struct int i, j; /该非零元的行下标和列下标 ElemType e; / 该非零元的值 Triple; / 三元组类型,一、三元组顺序表,typedef union Triple dataMAXSIZE + 1; int mu, nu, tu; TSMatrix; / 稀疏矩阵类型,如何求转置矩阵?,用常规的二维数组表示时的算法,其时间复杂度为: O(munu),for (col=1; col=n
7、u; +col) for (row=1; row=mu; +row) Tcolrow = Mrowcol;,用“三元组”表示时如何实现?,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,首先应该确定每一行的第一个非零元在三元组中的位置。,cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1;,Status FastTransposeSMatrix(TSMatrix M, TSMatrix / FastTranspose
8、SMatrix,转置矩阵元素,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,分析算法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; p=M.tu; +p) ,三元组顺序表又称有序的双下标法,它的特点是,非
9、零元在表中按行序有序存储,因此便于进行依行顺序处理的矩阵运算。然而,若需随机存取某一行中的非零元,则需从头开始进行查找。,二、行逻辑联接的顺序表,#define MAXMN 500 typedef struct Triple dataMAXSIZE + 1; int rposMAXMN + 1; int mu, nu, tu; RLSMatrix; / 行逻辑链接顺序表类型,修改前述的稀疏矩阵的结构定义,增加一个数据成员rpos,其值在稀疏矩阵的初始化函数中确定。,例如:给定一组下标,求矩阵的元素值,ElemType value(RLSMatrix M, int r, int c) p = M
10、.rposr; while (M.datap.i=r / value,矩阵乘法的精典算法: 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,
11、两个稀疏矩阵相乘(QMN) 的过程可大致描述如下:,Status MultSMatrix (RLSMatrix M, RLSMatrix N, RLSMatrix / MultSMatrix,ctemp = 0; / 当前行各元素累加器清零 Q.rposarow = Q.tu+1; for (p=M.rposarow; p MAXSIZE) return ERROR; Q.dataQ.tu = arow, ccol, ctempccol; / if,处理 的每一行,M,分析上述算法的时间复杂度,累加器ctemp初始化的时间复杂度为(M.muN.nu), 求Q的所有非零元的时间复杂度为(M.tu
12、N.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)。,三、 十字链表,3 0 0 5 0 -1 0 0 2 0 0 0,1,1,3,1,4,5,2,2,-1,3,1,2,5.4 广义表的类型定义,ADT Glist 数据对象:De
13、i | i=1,2,n; n0; eiAtomSet 或 eiGList, AtomSet为某个数据对象 数据关系: LR| ei-1 ,eiD, 2in ADT Glist,基本操作:,广义表是递归定义的线性结构,,LS = ( 1, 2, , n ) 其中:i 或为原子 或为广义表,例如: A = ( ) F = (d, (e) D = (a,(b,c), F) C = (A, D, F) B = (a, B) = (a, (a, (a, , ) ) ),广义表是一个多层次的线性结构,例如:,D=(E, F),其中: E=(a, (b, c) F=(d, (e),D,E,F,a,( ),d
14、,( ),b,c,e,广义表 LS = ( 1, 2, , n )的结构特点:,1) 广义表中的数据元素有相对次序;,2) 广义表的长度定义为最外层包含元素个数;,3) 广义表的深度定义为所含括弧的重数; 注意:“原子”的深度为 0 “空表”的深度为 1,4) 广义表可以共享;,5) 广义表可以是一个递归的表。 递归表的深度是无穷值,长度是有限值。,6) 任何一个非空广义表 LS = ( 1, 2, , n) 均可分解为 表头 Head(LS) = 1 和 表尾 Tail(LS) = ( 2, , n) 两部分。,例如: D = ( E, F ) = (a, (b, c),F ),Head(
15、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 ) ) = ( ), 结构的创建和销毁 InitGList(,基本操作, 状态函数 GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L);, 插入和
16、删除操作 InsertFirst_GL(, 遍历 Traverse_GL(L, Visit();,5.5 广义表的表示方法,通常采用头、尾指针的链表结构,表结点: 原子结点:,tag=1 hp tp,tag=0 data,1) 表头、表尾分析法:,构造存储结构的两种分析方法:,若表头为原子,则为,空表 ls=NIL,非空表 ls,tag=1,指向表头的指针,指向表尾的指针,tag=0 data,否则,依次类推。,L = ( a, ( x, y ), ( ( x ) ) ),a,( x, y ),( ),1,L,L = ( ),0 a,1,1,1,1,1,0 a,( ),x,2) 子表分析法:,
17、若子表为原子,则为,空表 ls=NIL,非空表,1,指向子表1 的指针,tag=0 data,否则,依次类推。,1,指向子表2 的指针,1,指向子表n 的指针,ls,例如:,a (x, y) (x),LS=( a, (x,y), (x) ),ls,5.6 广义表操作的递归函数,递归函数 一个含直接或间接调用本函数语句的函数被称之为递归函数,它必须满足以下两个条件:,1)在每一次调用自己时,必须是(在某 种意义上)更接近于解;,2)必须有一个终止处理或计算的准则。,例如: 梵塔的递归函数,void hanoi (int n, char x, char y, char z) if (n=1) mo
18、ve(x, 1, z); else hanoi(n-1, x, z, y); move(x, n, z); hanoi(n-1, y, x, z); ,二叉树的遍历,void PreOrderTraverse( BiTree T,void (Visit)(BiTree P) if (T) Visit(T-data); (PreOrderTraverse(T-lchild, Visit); (PreOrderTraverse(T-rchild, Visit); / PreOrderTraverse,一、分治法 (Divide and Conquer) (又称分割求解法),如何设计递归函数?,二、
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数组 广义
链接地址:https://www.31doc.com/p-2499258.html