[工学]C语言第5章.ppt

5.1 数组的类型定义,5.3 稀疏矩阵的压缩存储,5.2 数组的顺序表示和实现,5.4 广义表的类型定义,5.5 广义表的表示方法,5.6 广义表操作的递归函数 5.7 本章小结 5.8 习 题,5.1 数组的类型定义,由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组：,(a),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 和各维长度合法，构造相应的数组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。,数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。,二维数组的抽象定义:,数据对象: D = aij | 0ib1-1, 0 jb2-1 数据关系: R = ROW, COL ROW = | 0ib1-2, 0jb2-1 COL = | 0ib1-1, 0 jb2-2,5.2 数组的顺序表示和实现,类型特点: 1) 只有引用型操作，没有加工型操作; 2) 数组是多维的结构，而存储空间是一个一维的结构。,有两种顺序映象的方式: 1)以行序为主序(低下标优先);/我们所选择的 2)以列序为主序(高下标优先);,以“行序为主序”的存储映象,二维数组A中任一元素aij 的存储位置 LOC(i,j) = LOC(0,0) + (b2ij) L,称为基地址或基址,每个元素占L个存储单元,已经存储的元素数,LOC(j1,j2) = LOC(0,0) + (b2j1j2) L,LOC(j1,j2,j2)=LOC(0,0,0)+(b2b3j1b3j2j3 )L,LOC(j1, j2, ., jn ) = LOC(0,0,.,0) + (b2 b3 bn j1+ b3 b4 bn j2+ +bn jn-1+jn) L,推广到一般情况，可得到 n 维数组数据元素存储位置的映象关系：,其中 cn = L，ci-1 = bi ci , 1 i n。,(c1, c2, c3, ., cn-1, cn )称为 n 维数组的映象函数(常量)。数组元素的存储位置是其下标的线性函数,cn = L， cn-1 = bnL= bncn cn-2 = bn-1bnL= bn-1cn-1 cn-3 = bn-2bn-1bnL= bn-2cn-2 c3 = b4b5 bnL= b4c4 c2= b3b4b5 bnL= b3c3 c1= b2b3b4b5 bnL= b2c2 ci-1 = bi ci,设,容易看出，数组元素的存储位置是其下标的线性函数，一旦确定了数组的各维的长度，ci 就是常数。由于计算各个元素存储位置的时间相等，所以存取数组中任一元素的时间也相等。我们称具有这一特点的存储结构为随机存储结构。,下面是数组顺序存储表示和实现,/-数组顺序存储表示- #include“stdarg.h “ / 标准头文件,提供一个类型va_list ,三个宏va_start / va_arg 和va_end 的定义 #define MAX_ARRAY_DIM 8 /假设数组的最大维数 typedef struct ElemType *base;/存储数组元素的首地址(基址),由InitArray分配 int dim; /数组的维数 int *bounds; /存放数组维界的基地址,由InitArray分配 int *constants; /存放映象函数常量基址,由InitArray分配 Array;,Status InitArray(Array ,/-基本操作的实现算法-,if(A.boundsi=0;i-) A.constantsi= A.boundsi+1 *A.constantsi+1; return OK; / InitArray,Status DestroyArray(Array / DestroyArray,Status Locate(Array A, va_list ap, int / Locate,Status Value(Array A, ElemType &e ,) /如果用VC实现,/A是一数组，e为一元素变量，随后是n 个下标值。/A和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; / Value,Status Assign(Array &A, ElemType e ,),va_start(ap,e); if(result=Locate(A,ap,off)=0) return result; *(A.base+off)=e; return OK; / Assign,5.3 矩阵的压缩存储,5.3.1 特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。 1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji 1i,jn 则称A为对称矩阵。如下页图便是一个5阶对称矩阵。 对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先顺序”存储主对角线（包括,对角线）以下的元素，其存储形式如图所示：,1 5 1 3 7 a11 5 0 8 0 0 a21 a 22 1 8 9 2 6 a31 a32 a33 3 0 2 5 1 7 0 6 1 3 an1 a n2 an3 a nn 在这个下三角矩阵中，第i行恰有i个元素，元素总数为：n(n+1)/2 因此，我们可以按从上到下、从左到右将这些元素存放在一个向量sa0n(n+1)/2-1中。为了便于访问对称矩阵A中的元素，我们必须在aij和sak之间找一个对应关系。,若ij，则ai j在下三角形中。 ai j之前的i-1行共有1+2+i-1=i(i-1)/2个元素，在第i行上， ai j之前包括第j个共有j个元素（即ai1,ai2,ai3,aij-1），因此有：(/-1是因sa下标从0开始) k=i*(i-1)/2+j1 当i=j k=j*(j-1)/2+i-1 当ij,k=0 1 2 3,三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa0n(n+1)/2中，其中c存放在向量的最后一个分量中。 上三角矩阵中，主对角线之上的第i行(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远远小于矩阵元素的总数（即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 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 0,M=,T=,转置,7 6,#define MAXSIZE 12500 / 非零元素最大个数 typedef struct int i, j; /该非零元的行下标和列下标 ElemType e; / 该非零元的值 Triple; / 三元组类型,1.三元组顺序表,typedef struct Triple dataMAXSIZE + 1;/非零元三元组表中0号单元未用 int mu, nu, tu; /行、列及非零元个数 TSMatrix; / 稀疏矩阵类型,方法1：,转置后 得T,Status TransposeSMattrix(TSMatrix M, TSMatrix / 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),1）根据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) /采用三元组表存储表示，求稀疏矩阵的转置矩阵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;/ 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 时间复杂度为：,分析算法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) ,三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。,2. 行逻辑链接的顺序表,typedef struct Triple dataMAXSIZE + 1; /非零元三元组表 int rposMAXMN + 1; /各行第一个非零元的位置表 int mu, nu, tu; RLSMatrix; / 行逻辑链接顺序表类型,在行逻辑链接的顺序表表示稀疏矩阵时，一些操作的实现。,（1）取值运算，给定一组下标，求矩阵的元素值,void value(RLSMatrix M, int r, int c, ElemType / 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),(2) 矩阵乘法运算:,2.1 精典乘法运算算法：,M 、N和Q的三元组表示分别如下：,Q(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 / MultSMatrix,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.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,分析上述算法的时间复杂度,累加器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)。,/-稀疏矩阵的十字链表存储表示- typedef struct OLNode int i , j; Elemtype e; struct OLNode *right ,*down; OLNode , *OLink; Typedef struct OLink *rhead, *chead; /行和列链表头指针向量基址 int mu,nu,tu; CrossList;,3.十字链表,M.mu=3; M.nu=4; M.tu=4;,3.1 创建一个稀疏矩阵的十字链表存储结构 基本思想:创建一个稀疏矩阵M的十字链表存储结构的过程就是给M的5个域赋确切值的过程。 1）输入M的行m、列n和非零元的个数t； 2）申请存储行、列链表头指针的存储空间； 3）建立m+n个空链表； 4）输入一个非零元的(行，列，值）； 5）产生一个结点p；并给其i,j,e赋相应值； 6）将p插在相应行的适当位置上； 7）将p插在相应列的适当位置上； 8）重复4）、5）、6）、7）步，直到非零元输入完为止。,Status CreatMatrix_OL(CrossList scanf(&i,&j,&e) ) /按任意次 序输入非零元；,if(!(p=(OLNode*)malloc(sizeof(OLNode) exit(OVERFLOWER); p-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 else /将p插在合适的位置上,for(q=M.cheadj; q-down / CreatMatrix_OL,3.2 十字链表存储时两矩阵相加运算算法 void addMatrix(CrossList ,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 | 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(, 状态函数 GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L);, 插入和删除操作 InsertFirst_GL(, 遍历 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 , C )=( ( ) , ( e ), ( a , ( b , c , d ) ),任何一个非空广义表 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) 通常采用头、尾指针的链表结构,/-广义表的头尾链表存储表示- 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,2）广义表的扩展线性链表存储结构,typedef enum ATOM, LIST ElemTag ; / typedef struct GLNode ElemTag tag;/公共部分，用于区分原子结点和表结点 union H AtomType atom ; /atom是原子结点的值域 struct GLNode *hp; H; / 表结点的表头指针 struct GLNode *tp; /相当于线性链表的next，指向下一个 /元素结点 GLNode,*Glist ;/广义表类型,A = ( ) B= ( e ) C = ( a , ( b , c , d ) ) D=( A , B , C ),5.6 m元多项式的表示：P 110-112 自学！,5.7 广义表的递归算法,递归函数 一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件:,1)在每一次调用自己时，必须是(在某种意义上)更接近于解;,2)必须有一个终止处理或计算的准则。,例如: 梵塔的递归函数,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(1kn)个子集，从而产生 l 个子问题，分别求解这 l 个问题，得出 l 个问题的子解，再用某种方法把它们组合成原来问题的解。若子问题还相当大，则可以反复使用分治法，直至最后所分得的子问题足够小，以至可以直接求解为止。,分治法的设计思想为:,在利用分治法求解时，所得子问题的类型常常和原问题相同，因而很自然地导致递归求解,例如:焚塔问题: Hanoi(n, x, y, z),将 n 个盘分成两个子集(1至n-1 和 n )，从而产生下列三个子问题:,1) 将1至n-1号盘从 x 轴移动至 y 轴;,3) 将1至n-1号盘从y轴移动至z轴;,2) 将 n号盘从 x 轴移动至 z 轴;,广义表从结构上可以分解成：,广义表 = 表头 + 表尾,或者,广义表 = 子表1 + 子表2 + + 子表n,因此常利用分治法求解之。 算法设计中的关键问题是，如何将 l 个子问题的解组合成原问题的解。,广义表的头、尾链表存储表示：,typedef enum ATOM, LIST ElemTag; / ATOM=0:原子, LIST=1:子表 typedef struct GLNode ElemTag tag; / 标志域 union AtomType atom; / 原子结点的数据域 struct struct GLNode *hp, *tp; ptr; ; *GList,例一 求广义表的深度,例二 复制广义表,例三 创建广义表的存储结构,例1: 求广义表的深度,设广义表LS为：LS = ( 1, 2, , n ) 则LS的深度定义为： 0 当LS为原子时 DEPTH（LS）= 1 当LS为空表时 1+ Max DEPTH（i） n1 1in,在按数学式子写递归算法时，一定不要怀疑它的正确性！,int GlistDepth(Glist L) / 返回指针L所指的广义表的深度 for (max=0, pp=L; pp; pp=pp-ptr.tp) dep = GlistDepth(pp-ptr.hp); if (dep max) max = dep; return max + 1; / GlistDepth,if (!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; ,例如:,pp,pp-ptr.hp,pp,pp,pp-ptr.hp,pp-ptr.hp,例二 复制广义表,新的广义表由新的表头和表尾构成。,可以直接求解的两种简单情况为: 空表复制求得的新表自然也是空表; 原子结点可以直接复制求得。,将广义表分解成表头和表尾两部分，分别(递归)复制求得新的表头和表尾，,若 LS= NULL 则 NEWLS=NULL 否则 产生结点 NEWLS 和LS相同，即若LS为元素结点，则直接将LS的值赋给NEWLS，否则为表结点，则完成下列工作： 将表头LS-ptr.hp 复制到NEWLS -ptr.hp 将表尾 LS-ptr.tp 复制到NEWLS -ptr.tp,复制求广义表的算法描述如下:,Status CopyGList(GList / CopyGList,分别复制表头和表尾,CopyGList(T-ptr.hp, L-ptr.hp); / 复制求得表头T-ptr.hp的一个副本L-ptr.hp CopyGList(T-ptr.tp, L-ptr.tp); / 复制求得表尾T-ptr.tp 的一个副本L-ptr.tp,例三 创建广义表的存