[工学]C语言第5章课件

1、5.1 数组的类型定义5.3 稀疏矩阵的压缩存储 5.2 数组的顺序表示和实现5.4 广义表的类型定义5.5 广义表的表示方法5.6 广义表操作的递归函数5.7 本章小结5.8 习 题5.1 数组的类型定义 由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组：(a)a01a11am-1,1a0,n-1a1 ,n-1am-1 ,n-1a00a10am-1,0Amn=(b)Amn=（a00,a01,a0,n-1),(a10,a11,a1,n-1),(am-1,0 , am-1,1,am-1,n-

2、1)(c)typedef Elemtype array2mn;等价于：typedef Elemtype array1n;typedef array1 array2m; 一般地：多维数组的定义如下页所示：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 InitArray(&A, n, bound1, ., boundn) 操作结果：若维数 n 和各维长度合法

3、，构造相应的数组A，并返回OK。DestroyArray(&A)操作结果：销毁数组A。Value(A, &e, index1, ., indexn) 初始条件：A是n维数组，e为元素变量，随后是n 个下标值。 操作结果：若各下标不超界，则e赋值为所指定的A 的元素值，并返回OK。Assign(&A, e, index1, ., indexn) 初始条件：A是n维数组，e为元素变量，随后是n 个下标值。 操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。 数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。二维数组的抽

4、象定义:数据对象: D = aij | 0ib1-1, 0 jb2-1数据关系: R = ROW, COL ROW = | 0ib1-2, 0jb2-1 COL = | 0ib1-1, 0 jb2-25.2 数组的顺序表示和实现类型特点:1) 只有引用型操作，没有加工型操作;2) 数组是多维的结构，而存储空间是一个一维的结构。有两种顺序映象的方式:1)以行序为主序(低下标优先);/我们所选择的2)以列序为主序(高下标优先); 以“行序为主序”的存储映象a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L按行序为主序存放01n-1m*n-1n am-

5、1n-1 . am-11 am-10 . a1n-1 . a11 a10 a0n-1 . a01 a00 a00 a01 . a0n-1 a10 a11 . a1n-1 am-10 am-11 am-1n-1 .Loc(i,j)=Loc(0,0)+n*i+ j*L二维数组A中任一元素aij 的存储位置 LOC(i,j) = LOC(0,0) + (b2ij) L称为基地址或基址每个元素占L个存储单元已经存储的元素数LOC(j1,j2) = LOC(0,0) + (b2j1j2) LLOC(j1,j2,j2)=LOC(0,0,0)+(b2b3j1b3j2j3 )LLOC(j1, j2, ., j

6、n ) = LOC(0,0,.,0) + (b2 b3 bn j1+ b3 b4 bn j2+ +bn jn-1+jn) L 推广到一般情况，可得到 n 维数组数据元素存储位置的映象关系： LOC(j1, j2, ., jn ) = LOC(0,0,.,0) + (b2 b3 bn j1+ b3 bn j2+ b4 bnj3+ +bn-1 bn jn-2+bn jn-1+jn) L = LOC(0,0,.,0) + = LOC(0,0,.,0) +其中 cn = L，ci-1 = bi ci , 1 i n。 (c1, c2, c3, ., cn-1, cn )称为 n 维数组的映象函数(常量

7、)。数组元素的存储位置是其下标的线性函数cn = L， cn-1 = bnL= bncncn-2 = bn-1bnL= bn-1cn-1cn-3 = bn-2bn-1bnL= bn-2cn-2 c3 = b4b5 bnL= b4c4 c2= b3b4b5 bnL= b3c3c1= b2b3b4b5 bnL= b2c2 ci-1 = bi ci设 容易看出，数组元素的存储位置是其下标的线性函数，一旦确定了数组的各维的长度，ci 就是常数。由于计算各个元素存储位置的时间相等，所以存取数组中任一元素的时间也相等。我们称具有这一特点的存储结构为随机存储结构。下面是数组顺序存储表示和实现/-数组顺序存储

8、表示-#includestdarg.h / 标准头文件,提供一个类型va_list ,三个宏va_start/ va_arg 和va_end 的定义#define MAX_ARRAY_DIM 8 /假设数组的最大维数typedef structElemType *base;/存储数组元素的首地址(基址),由InitArray分配int dim; /数组的维数int *bounds; /存放数组维界的基地址,由InitArray分配int *constants; /存放映象函数常量基址,由InitArray分配 Array;Status InitArray(Array &A, int dim,)

9、/若维数 dim 和各维长度合法，构造相应的数组A，并返回OKif(dim MAX_ARRAY_DIM ) return ERROR;A.dim=dim;A.bounds=(int*)malloc(dim*sizeof(int);if(! A.bounds) exit(OVERFLOW);/若各维长度合法,则存入A.bounds,并求出元素总数elemtotalelemtotal=1;va_start(ap,dim);/ap为va_list类型,存放变长参数表信息的数组for(i=0;idim;i+) A.boundsi=va_arg(ap,int);/-基本操作的实现算法-if(A.boun

10、dsi=0;i-)A.constantsi= A.boundsi+1 *A.constantsi+1;return OK;/ InitArrayStatus DestroyArray(Array &A) /销毁数组Aif(!A.base) return ERROR;free(A.base);A.base=NULL;if(!A.bounds) return ERROR;free(A.bounds);A. bounds =NULL;if(!A.constants) return ERROR;free(A.constants);A. constants =NULL;return OK;/ Destr

11、oyArrayStatus Locate(Array A, va_list ap, int &off)/若ap所指下标合法,求出该下标对应元素在数组中的相对位置off=0;/最终off带回在存储该元素时已经存储的元素个数For(i=0;iA.dim;i+) ind=va_arg(ap,int); if (ind=A.boundsi) return(OVERFLOW); off+=A.constantsi*ind; return OK;/ LocateStatus Value(Array A, ElemType &e ,) /如果用VC实现/A是一数组，e为一元素变量，随后是n 个下标值。/A和

12、e换顺序 /若各下标不超界，则e赋值为所指定的A 的元素值，并返回OK。va_start(ap,e); / va_start(ap,A)if(result=Locate(A,ap,off)=0) return result;e=*(A.base+off);return OK;/ ValueStatus Assign(Array &A, ElemType e ,) va_start(ap,e); if(result=Locate(A,ap,off)=j k=j*(j-1)/2+i-1 当ij a11 a21 a22 a31 an1 annk=0 1 2 32、三角矩阵 以主对角线划分，三角矩阵有

13、上三角和下三角两种。上三角矩阵如图a所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图b所示。在大多数情况下，三角矩阵常数为零。 a00 a01 a 0 n-1 a00 c c c a11 a 1 n-1 a10 a11 c . . c c a n-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)上三角矩阵 (b)下三角矩阵 三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa0.n(n+1)/2中，其中c存放在向量的最后一个分量中。 上三角矩阵中，主对角线之上的第i

14、行(0i j 下三角矩阵的存储和对称矩阵类似，sak和aij对应关系是： i(i+1)/2+j ij n(n+1)/2 ij 3、对角矩阵 对角矩阵中，所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵， a00 a01 a10 a11 a12 a21 a22 a23 . . . 可用以行序为主序的 an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1 形式存储 图5.3 对角矩阵k= 什么是稀疏矩阵？简单说，设矩阵A中有t个非零元素，若t远远小于矩阵元素的总

15、数（即tmn），则称A为稀疏矩阵。定义稀疏因子:通常认为 0.05 的矩阵为稀疏矩阵。稀疏矩阵的压缩存储方法:三元组表示法 /三元组为：（行，列，值）5.3.2 稀疏矩阵例如，下列三元组表(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便可作为下列矩阵M的另一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。 0 12 9 0 0 0 0 0 0 3 0 0 15 0 0 0 0 0 0 0 12 0 0 0 18 0 -3 0 0 0 0 14 0 9 0

16、0 24 0 0 0 0 24 0 0 0 0 0 0 0 0 0 7 0 18 0 0 0 0 0 0 0 14 0 0 0 15 0 0 7 0 0 0 6 7 0 0 0 0 0 0图5.4 稀疏矩阵M和T 0 0 0 0 0 0M=T=转置7 6 #define MAXSIZE 12500 / 非零元素最大个数 typedef struct int i, j; /该非零元的行下标和列下标 ElemType e; / 该非零元的值 Triple; / 三元组类型1.三元组顺序表typedef struct Triple dataMAXSIZE + 1;/非零元三元组表中0号单元未用 in

17、t mu, nu, tu; /行、列及非零元个数 TSMatrix; / 稀疏矩阵类型i j e 1 2 12 1 3 9 3 1 -3 6 14 3 24 5 2 18 1 15 6 4 -7M.dataM.mu=6M.nu=7M.tu=8用常规的二维数组表示时的算法 其时间复杂度为: O(M.muM.nu) for (col=1; col=M.nu; +col) for (row=1; row=M.mu; +row) Tcolrow = Mrowcol;（1） 用三元组表示时转置运算的实现用三元组表示时如何实现？方法1：i j e 1 2 12 1 3 9 3 1 -3 6 14 3 24

18、 5 2 18 1 15 6 4 -7M.dataM.mu=6M.nu=7M.tu=8转置后得Ti j v 1 3 -31 6 15 2 1 12 2 5 18 3 1 9 4 24 6 -7 6 3 14T.dataT.mu=7T.nu=6T.tu=8Status TransposeSMattrix(TSMatrix M, TSMatrix &T)/采用三元组表存储表示，求稀疏矩阵的转置矩阵TT.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu) q=1; /q表示下一次找到的非零元在T.data中的下标for(col=1;col=M.nu;col+) for(p=1;

19、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; / TransposeSMattrix其时间复杂度为: O(M.nuM.tu)， 若 M.tu 与M.muM.nu同数量级 时，有O(M.tu M.nu2 )方法二：快速转置 其基本思想是对M.data仅扫描一遍，在扫描到每一个元素时将其放T.data的合适的位置上。cpot1=1;cpotcol=cpotcol-1+numcol-1; (2col M.nu)1357889col

20、numcolcpotcol122232415061701）根据M的mu、nu和tu 的值，对T的mu、nu和tu赋 相应的值；2）初始化数组num;3） 扫描M.data， 计算num的值；4）根据num的值，计算cpot的值；5）扫描M.data一遍，将非零元放在T.data的合适 的位置上。算法描述如下页所示：Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T)/采用三元组表存储表示，求稀疏矩阵的转置矩阵TT.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu) for(col=1;col=M.nu;col+) num

21、col=0;/ 0号单元不用for(t=1;col=M.tu;t+) +numM.datat.j;cpot1=1; /求第col列中第一个非零元在T.data中的序号for(col=2;col=M.nu;col+) cpotcol=coptcol-1+numcol-1;for(t=1;t=M.tu;t+) col=M.datat.j; q=cpotcol; T.dataq.i=M.datat.j; T.dataq.j=M.datat.i; T.dataq.e=M.datat.e; + cpotcol; return OK; / FastTransposeSMatrix 时间复杂度为：分析算法F

22、astTransposeSMatrix的时间复杂度：时间复杂度为: 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) 三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。2. 行逻辑链接的顺序表typedef struct Triple dataMAXSIZE + 1; /非零元三元组表 int rposMAX

23、MN + 1; /各行第一个非零元的位置表 int mu, nu, tu; RLSMatrix; / 行逻辑链接顺序表类型在行逻辑链接的顺序表表示稀疏矩阵时，一些操作的实现。（1）取值运算，给定一组下标，求矩阵的元素值void value(RLSMatrix M, int r, int c, ElemType &e) p = M.rposr; /第r行第一个非零元和位置while (p=M.tu&M.datap.i=r &M.datap.j c) p+; if (M.datap.i=r & M.datap.j=c) e= M.datap.e; else e=0 ; / valuefor (i=

24、1; i=m1; +i) for (j=1; j=n2; +j) Qij = 0; for (k=1; k=n1; +k) Qij += Mik * Nkj; 其时间复杂度为: O(m1n2n1)(2) 矩阵乘法运算:2.1 精典乘法运算算法：M=0 20-2 40 0 0 0 5 0 -1 0 02 0 0 0N=3 44 2Q=M N0 6 -1 0 0 4Q=3 21 0 0 0 1 0 0 01 0 0 0A=B=1 10 00 00 03 44 2C=A B1 1 1 1 1 1C=3 2M 、N和Q的三元组表示分别如下：i j e 1 31 4 5 2 -13 1 2i j e 2

25、 22 1 13 1 -23 2 4i j e 2 62 1 -13 2 4M.dataN.dataQ.dataQ(i,j)= Q初始化; if Q是非零矩阵 / 逐行求积 for (arow=1; arow=M.mu; +arow) / 处理M的每一行 ctemp = 0; / 累加器清零 计算Q中第arow行的积并存入ctemp 中； 将ctemp 中非零元压缩存储到Q.data； / for arow / if 基本思想：Status MultSMatrix (RLSMatrix M, RLSMatrix N, RLSMatrix &Q) /求矩阵乘积Q=M N ,采用行逻辑链接存储表示

26、 if (M.nu != N.mu) return ERROR; Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; /初始化Q，Q.tu表示现已存入Q中的非零元个数 if (M.tu*N.tu != 0) / Q是非零矩阵 for (arow=1; arow=M.mu; +arow) / 处理M的每一行 / for arow / if return OK; / MultSMatrixM=0 20-2 40 0 0 0 5 0 -1 0 02 0 0 0N=3 44 2Q=M N0 6 -1 0 0 4Q=3 2i j e 1 31 4 5 2 -13 1 2i j e 2

27、 22 1 13 1 -23 2 4i j e 2 62 1 -13 2 4M.dataN.dataQ.data ctemp = 0; / 当前行各元素累加器清零 Q.rposarow = Q.tu+1; /Q的第arow行在Q.data中的位置 if(arowM.mu) tp=M.rposarow+1; else tp=M.tu+1;for (p=M.rposarow; ptp;+p) /对当前行中每一个非零元 brow=M.datap.j; if (brow N.nu ) t = N.rposbrow+1; else t = N.tu+1 /t为本行最后一个非零元的下一位 for (q=N

28、.rposbrow; q t; +q) ccol = N.dataq.j; / 乘积元素在Q中列号 ctempccol += M.datap.e * N.dataq.e; / for q / 求得Q中第crow( =arow)行的非零元处理 的每一行Mfor (ccol=1; ccol MAXSIZE) return ERROR; Q.dataQ.tu = （arow, ccol, ctempccol）; / if分析上述算法的时间复杂度累加器ctemp初始化的时间复杂度为(M.muN.nu)，求Q的所有非零元的时间复杂度为(M.tuN.tu/N.mu)，进行压缩存储的时间复杂度为(M.muN

29、.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 i=i; p-j=j; p-e=e; /生成结点if( M.rheadi=NULL| M.rheadi-jj) /插在表头p-right=M.rheadi; M.rheadi=p; else /将p插在合适的位置上for(q=M.rheadi; q-right & q-right-jright); p-

30、right=q-right; q-right=p; /行插入，在q后if( M.cheadj=NULL| M.cheadj-ii) /插在表头 p-down=M.cheadj; M.rheadj=p; else /将p插在合适的位置上 for(q=M.cheadj; q-down & q-down-idown); p-down=q-down; q-down=p; /列插入，在q后return OK;/ CreatMatrix_OL3.2 十字链表存储时两矩阵相加运算算法void addMatrix(CrossList &A, CrossList B)/A=A+Bfor( row=1;rowjp

31、b-j:产生一个结点p；p所指结点 的值=pb所指结点的值；将p 插在pa的前面（pre的后面） 完成行插入；将p插在相应列 的适当位置上,pb后移；break; case pa-jj: pre=pa;pa=pa-right;break; case pa-j=pb-j: k=pa-e+pb-e; if( k) pa-e=k; pre=pa;pa=pa-right; pb=pb-right; else 在相应的行、列中，删除pa所指结点；pa、pb后 移；break; /switch /while /for/ addMatrix 5.4 广义表的类型定义ADT Glist 数据对象：Dei |

32、i=1,2,.,n; n0; eiAtomSet 或 eiGList, AtomSet为某个数据对象 数据关系： R1| ei-1 ,eiD, 2in 基本操作: P107 12 种基本操作 ADT Glist( a , ( b , c ) , ( d , ( e , f ) ) ,g ) 结构的创建和销毁 InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L); 状态函数 GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L);

33、 插入和删除操作 InsertFirst_GL(&L, e); DeleteFirst_GL(&L, &e); 遍历 Traverse_GL(L, Visit();广义表是递归定义的线性结构，可以形式的写为：LS = ( 1, 2, , n )其中：i或为原子或为广义表例如: A = ( ) B= ( e ) C = ( a , ( b , c , d ) ) D=( A , B , C ) E=( a , E ) 相当于一个无限的列表 ( a , ( a , ( a ,) ) )基本概念：原子、子表、表长、空表、表头、表尾、表的深度广义表是一个多层次的线性结构例如： D=( A , B ,

34、C )=( ( ) , ( e ), ( a , ( b , c , d ) )ACaeBbcdD 任何一个非空广义表 LS = ( 1, 2, , n ) 均可分解为 表头 Head(LS) = 1和表尾 Tail(LS) = (2, , n ) 两部分例如：F=( ( a , b ) , c, ( d ) ) Head(F)= ( a , b ) , Tail(F)=( c , ( d ) ) Head(Head(F)=a;Tail (Head(F)=( b )5.5 广义表的存储结构1) 通常采用头、尾指针的链表结构表结点:tag=1 hp tptag=0 atom原子结点：/-广义表的

35、头尾链表存储表示-typedef enum ATOM, LIST ElemTag ;/typedef struct GLNode ElemTag tag;/公共部分，用于区分原子结点和表结点 union H /atom是原子结点的值域，AtomType 由用户定义 AtomType atom ; struct struct GLNode *hp,*tp; ptr; H;/ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾GLNode, *Glist ;/广义表类型空表 LS = NULL非空表 LStag=1 指向表头的指针指向表尾的指针若表头为原子，则为tag=0 atom

36、否则，依次类推。A = ( ) B= ( e ) C = ( a , ( b , c , d ) ) D=( A , B , C )A=NULLB 1 0 e 1 1 1 1 10 a0 b 0 d0 cC 1 1 1 D2）广义表的扩展线性链表存储结构typedef enum ATOM, LIST ElemTag ; /typedef struct GLNode ElemTag tag;/公共部分，用于区分原子结点和表结点 union H AtomType atom ; /atom是原子结点的值域 struct GLNode *hp; H; / 表结点的表头指针struct GLNode *

37、tp; /相当于线性链表的next，指向下一个 /元素结点 GLNode,*Glist ;/广义表类型原子结点：tag=1 hp tptag=0 atom tp表结点:A = ( ) B= ( e ) C = ( a , ( b , c , d ) ) D=( A , B , C )A 1 B 1 0 e 1 1 1 D 1C 1 1 0 d 0 a 0 b 0 c 5.6 m元多项式的表示：P 110-112 自学！5.7 广义表的递归算法递归函数 一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件:1)在每一次调用自己时，必须是(在某种意义上)更接近于解;2)必须

38、有一个终止处理或计算的准则。例如: 梵塔的递归函数void hanoi (int n, char x, char y, char z) if (n=1) move(x, 1, z); else hanoi(n-1, x, z, y); move(x, n, z); hanoi(n-1, y, x, z); / hanoi 求阶乘算法：n!=n*(n-1)! int fact(int n ) if (n=0 ) return 1; else return n*fact(n-1); / fact 对于一个输入规模为 n 的函数或问题，用某种方法把输入分割成 k(1ptr.tp) dep = Gli

39、stDepth(pp-ptr.hp); if (dep max) max = dep; return max + 1; / GlistDepthif (!L) return 1; /L为空表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; 例如:pppp-ptr.hppppppp-ptr.hppp-ptr.hp 1 1 1 L例二 复制广义表新的广义表由新的表头和表尾构成。可以直接求解的两种简单情况为: 空表复制

40、求得的新表自然也是空表; 原子结点可以直接复制求得。 将广义表分解成表头和表尾两部分，分别(递归)复制求得新的表头和表尾，若 LS= NULL 则 NEWLS=NULL否则 产生结点 NEWLS 和LS相同，即若LS为元素结点，则直接将LS的值赋给NEWLS，否则为表结点，则完成下列工作：将表头LS-ptr.hp 复制到NEWLS -ptr.hp 将表尾 LS-ptr.tp 复制到NEWLS -ptr.tp复制求广义表的算法描述如下:Status CopyGList(GList &T, GList L) /采用头尾链表存储结构，由广义表L复制得到广义表T if (!L) T = NULL; /

41、 复制空表 else if ( !(T = （Glist)(malloc(sizeof( GLNode) ) exit(OVERFLOW); / 建表结点 T-tag = L-tag; if (L-tag = ATOM) T-atom = L-atom; / 复制单原子结点 else / else return OK; / CopyGList 分别复制表头和表尾CopyGList(T-ptr.hp, L-ptr.hp); / 复制求得表头T-ptr.hp的一个副本L-ptr.hpCopyGList(T-ptr.tp, L-ptr.tp); / 复制求得表尾T-ptr.tp 的一个副本L-ptr.tp例三 创建广义表的存储结构 对应广义表的不同存储结构，相应地有不同的创建存储结构的算法。下面以扩展线性链表存储结构为例： 假设以字符串 S = (1, 2, , n )