数据结构(C语言版)数组.ppt

《数据结构(C语言版)数组.ppt》由会员分享，可在线阅读，更多相关《数据结构(C语言版)数组.ppt（96页珍藏版）》请在三一办公上搜索。

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=ROW,COL ROW=|0ib1-2,0jb2-1 COL=|0ib1-

2、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,index1,.,indexn)初始条件：A是n维数组，e为元素变量，随后是n 个下标值。操作结果：若各下标不超界，则e赋值为 所指定的A 的

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

4、0,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 列的矩阵含 t 个非零元素，则称 为稀疏因子。通常认为 0.05 的矩阵为稀疏矩阵。,5.3 稀疏矩阵的压缩存储,何谓稀疏矩阵？,以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:,1)零值元素占了很大空

5、间;,2)计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。,1)尽可能少存或不存零值元素；,解决问题的原则:,2)尽可能减少没有实际意义的运算；,3)操作方便。即：能尽可能快地找到与 下标值(i，j)对应的元素，能尽可能快地找到同 一行或同一列的非零值元。,1)特殊矩阵 非零元在矩阵中的分布有一定规则 例如:三角矩阵 对角矩阵,2)随机稀疏矩阵 非零元在矩阵中随机出现,有两类稀疏矩阵：,随机稀疏矩阵的压缩存储方法:,一、三元组顺序表,二、行逻辑联接的顺序表,三、十字链表,#define MAXSIZE 12500 typedef struct int i,j;/该非零元的行下标和列

6、下标 ElemType e;/该非零元的值 Triple;/三元组类型,一、三元组顺序表,typedef union Triple dataMAXSIZE+1;int mu,nu,tu;TSMatrix;/稀疏矩阵类型,如何求转置矩阵？,用常规的二维数组表示时的算法,其时间复杂度为:O(munu),for(col=1;col=nu;+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,首先应该确定每一

7、行的第一个非零元在三元组中的位置。,cpot1=1;for(col=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-1;,Status FastTransposeSMatrix(TSMatrix M,TSMatrix/FastTransposeSMatrix,转置矩阵元素,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),f

8、or(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),三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。,二、行逻辑联接的顺序表,#define MAXMN 500 typedef struct Triple dataMAXSIZE+1;int rposMAXMN+1;int mu,nu,tu;RLSMatrix;/行逻辑链接顺序表类型,修改前述的稀疏矩阵的结构定义，

9、增加一个数据成员rpos，其值在稀疏矩阵的初始化函数中确定。,例如：给定一组下标，求矩阵的元素值,ElemType value(RLSMatrix M,int r,int c)p=M.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行的

10、积并存入ctemp 中；将ctemp 中非零元压缩存储到Q.data；/for arow/if,两个稀疏矩阵相乘（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.

11、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)。,三、十字链表,3 0 0 50-1 0 02 0 0 0,1,1,3,1,4,5,2,2,-1,3,1,2,5.4 广义表的类型定义,ADT Glist 数

12、据对象：Dei|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,(),b,c,e,广义表 LS=(1,2,n)的结构特点:,1)广义表中的数据元素有相对次序；,

13、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(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),H

14、ead(c)=c Tail(c)=(),结构的创建和销毁 InitGList(,基本操作,状态函数 GListLength(L);GListDepth(L);GListEmpty(L);GetHead(L);GetTail(L);,插入和删除操作 InsertFirst_GL(,遍历 Traverse_GL(L,Visit();,5.5 广义表的表示方法,通常采用头、尾指针的链表结构,表结点:原子结点：,tag=1 hp tp,tag=0 data,1)表头、表尾分析法：,构造存储结构的两种分析方法:,若表头为原子，则为,空表 ls=NIL,非空表 ls,tag=1,指向表头的指针,指向表尾的

15、指针,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)子表分析法：,若子表为原子，则为,空表 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)必

16、须有一个终止处理或计算的准则。,例如:梵塔的递归函数,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);,二叉树的遍历,void PreOrderTraverse(BiTree T,void(Visit)(BiTree P)if(T)Visit(T-data);(PreOrderTraverse(T-lchild,Visit);(PreOrderTraverse(T-rchild,Visit);/PreOrderTraverse,

17、一、分治法(Divide and Conquer)(又称分割求解法),如何设计递归函数？,二、后置递归法(Postponing the work),三、回溯法(Backtracking),对于一个输入规模为 n 的函数或问题，用某种方法把输入分割成 k(1kn)个子集，从而产生 l 个子问题，分别求解这 l 个问题，得出 l 个问题的子解，再用某种方法把它们组合成原来问题的解。若子问题还相当大，则可以反复使用分治法，直至最后所分得的子问题足够小，以至可以直接求解为止。,分治法的设计思想为:,在利用分治法求解时，所得子问题的类型常常和原问题相同，因而很自然地导致递归求解。,例如:,梵塔问题:Ha

18、noi(n,x,y,z),可递归求解 Hanoi(n-1,x,z,y),将 n 个盘分成两个子集(1至n-1 和 n)，从而产生下列三个子问题：,1)将1至n-1号盘从 x 轴移动至 y 轴；,3)将1至n-1号盘从y轴移动至z轴；,2)将 n号盘从 x 轴移动至 z 轴；,可递归求解 Hanoi(n-1,x,z,y),又如:,遍历二叉树:Traverse(BT),可递归求解 Traverse(LBT),将 n 个结点分成三个子集(根结点、左子树 和右子树)，从而产生下列三个子问题：,1)访问根结点；,3)遍历右子树;,2)遍历左子树；,可递归求解 Traverse(RBT),广义表从结构上可

19、以分解成,广义表=表头+表尾,或者,广义表=子表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,tag=1,hp tp,ptr,表结点,例一 求广义表的深度,例二 复制广义表,例三 创建广义

20、表的存储结构,广义表的深度=Max 子表的深度+1,例一 求广义表的深度,可以直接求解的两种简单情况为：空表的深度=1 原子的深度=0,将广义表分解成 n 个子表，分别(递归)求得每个子表的深度，,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;if(L-tag=ATOM)return 0;,1,1,1,L,for(max=0,pp=L

21、;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=NIL 则 newls=NIL否则 构造结点 newls,由 表头ls-ptr.hp 复制得 newhp 由 表尾 ls-ptr.tp 复制得 newtp 并使 ne

22、wls-ptr.hp=newhp,newls-ptr.tp=newtp,复制求广义表的算法描述如下:,Status CopyGList(Glist/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,语句 CopyGList(T-ptr.hp,L-ptr.hp);等价于 CopyGList(newhp,L-ptr.tp);T-ptr.hp=newhp;,例三 创建广义表的存储结

23、构,对应广义表的不同定义方法相应地有不同的创建存储结构的算法。,假设以字符串 S=(1,2,n)的形式定义广义表 L，建立相应的存储结构。,由于S中的每个子串i定义 L 的一个子表，从而产生 n 个子问题，即分别由这 n个子串(递归)建立 n 个子表，再组合成一个广义表。,可以直接求解的两种简单情况为：由串()建立的广义表是空表；由单字符建立的子表只是一个原子结点。,如何由子表组合成一个广义表？,首先分析广义表和子表在存储结构中的关系。,先看第一个子表和广义表的关系:,1,L,指向广义表的头指针,指向第一个子表的头指针,再看相邻两个子表之间的关系:,1,1,指向第i+1个子表的头指针,指向第i

24、个子表的头指针,可见，两者之间通过表结点相链接。,若 S=()则 L=NIL；否则，构造第一个表结点*L，并从串S中分解出第一个子串1，对应创建第一个子广义表 L-ptr.hp；若剩余串非空，则构造第二个表结点 L-ptr.tp，并从串S中分解出第二个子串 2，对应创建第二个子广义表；依次类推，直至剩余串为空串止。,void CreateGList(Glist/脱去串S的外层括弧/else,由sub中所含n个子串建立n个子表;,do sever(sub,hsub);/分离出子表串hsub=i if(!StrEmpty(sub)p-ptr.tp=(Glist)malloc(sizeof(GLNo

25、de);/建下一个子表的表结点*(p-ptr.tp)p=p-ptr.tp;while(!StrEmpty(sub);p-ptr.tp=NULL;/表尾为空表,创建由串hsub定义的广义表p-ptr.hp;,if(StrLength(hsub)=1)p-ptr.hp=(GList)malloc(sizeof(GLNode);p-ptr.hp-tag=ATOM;p-ptr.hp-atom=hsub;/创建单原子结点else CreateGList(p-ptr.hp,hsub);/递归建广义表,后置递归的设计思想为:,递归的终结状态是，当前的问题可以直接求解，对原问题而言，则是已走到了求解的最后一步

26、。,链表是可以如此求解的一个典型例子。例如：编写“删除单链表中所有值为x 的数据元素”的算法。,1)单链表是一种顺序结构，必须从第一个结点起，逐个检查每个结点的数据元素；,分析:,2)从另一角度看，链表又是一个递归结构，若 L 是线性链表(a1,a2,an)的头指针，则 L-next是线性链表(a2,an)的头指针。,a1,a2,a3,an,L,例如:,a1,a2,a3,an,L,a1,a2,a3,an,L,已知下列链表,1)“a1=x”，则 L 仍为删除 x 后的链表头指针,2)“a1x”，则余下问题是考虑以 L-next 为头指针的链表,a1,L-next,L-next=p-next,p=

27、L-next,void delete(LinkList/delete,删除广义表中所有元素为x的原子结点,分析:比较广义表和线性表的结构特点：,相似处：都是链表结构。,不同处：1)广义表的数据元素可能还是个 广义表；2)删除时，不仅要删除原子结点，还需要删除相应的表结点。,void Delete_GL(Glist/考察第一个子表 if(head-tag=Atom)&(head-atom=x)/删除原子项 x的情况 else/第一项没有被删除的情况/Delete_GL,p=L;L=L-ptr.tp;/修改指针free(head);/释放原子结点free(p);/释放表结点Delete_GL(L,

28、x);/递归处理剩余表项,1,L,0 x,1,p,L,head,if(head-tag=LIST)/该项为广义表 Delete_GL(head,x);Delete_GL(L-ptr.tp,x);/递归处理剩余表项,1,L,0 a,1,1,head,L-ptr.tp,回溯法是一种“穷举”方法。其基本思想为：,假设问题的解为 n 元组(x1,x2,xn)，其中 xi 取值于集合 Si。n 元组的子组(x1,x2,xi)(in)称为部分解，应满足一定的约束条件。对于已求得的部分解(x1,x2,xi)，若在添加 xi+1Si+1 之后仍然满足约束条件，则得到一个新的部分解(x1,x2,xi+1),之后

29、继续添加 xi+2Si+2 并检查之。,例一、皇后问题求解,设四皇后问题的解为(x1,x2,x3,x4),其中：xi(i=1,2,3,4)Si=1,2,3,4约束条件为：其中任意两个xi 和xj不能位于棋盘的同行、同列及同对角线。,按回溯法的定义，皇后问题求解过程为：解的初始值为空；首先添加 x1=1,之后添加满足条件的 x2=3，由于对所有的 x31,2,3,4都不能找到满足约束条件的部分解(x1,x2,x3),则回溯到部分解(x1),重新添加满足约束条件的x2=4,依次类推。,void Trial(int i,int n)/进入本函数时，在nn棋盘前i-1行已放置了互不攻/击的i-1个棋子

30、。现从第 i 行起继续为后续棋子选择/满足约束条件的位置。当求得(in)的一个合法布局/时，输出之。if(in)输出棋盘的当前布局;else for(j=1;j=n;+j)在第 i 行第 j 列放置一个棋子;if(当前布局合法)Trial(i+1,n);移去第 i 行第 j 列的棋子;/trial,回溯法求解的算法一般形式：,void B(int i,int n)/假设已求得满足约束条件的部分解(x1,.,xi-1)，本函/数从 xi 起继续搜索，直到求得整个解(x1,x2,xn)。if(in)else while(!Empty(Si)从 Si 中取 xi 的一个值 viSi;if(x1,x2

31、,xi)满足约束条件 B(i+1,n);/继续求下一个部分解 从 Si 中删除值 vi;/B,综合几点：1.对于含有递归特性的问题，最好设计递归形式的算法。但也不要单纯追求形式，应在算法设计的分析过程中“就事论事”。例如，在利用分割求解设计算法时，子问题和原问题的性质相同；或者，问题的当前一步解决之后，余下的问题和原问题性质相同，则自然导致递归求解。,2.实现递归函数，目前必须利用“栈”。一个递归函数必定能改写为利用栈实现的非递归函数；反之，一个用栈实现的非递归函数可以改写为递归函数。需要注意的是递归函数递归层次的深度决定所需存储量的大小。,3.分析递归算法的工具是递归树，从递归树上可以得到递

32、归函数的各种相关信息。例如：递归树的深度即为递归函数的递归深度；递归树上的结点数目恰为函数中的主要操作重复进行的次数；若递归树蜕化为单支树或者递归树中含有很多相同的结点，则表明该递归函数不适用。,例如:n=3的梵塔算法中主要操作move的执行次数可以利用下列递归树进行分析:,move(3,a,b,c),move(2,a,c,b),move(2,b,a,c),move(1,a,b,c),move(1,c,a,b),move(1,b,c,a),move(1,a,b,c),上图递归树的中序序列即为圆盘的移动操作序列。,又如:求n!的递归函数的递归树已退化为一个单枝树;而计算斐波那契递归函数的递归树中

33、有很多重复出现的结点。,n,n-1,1,0,。,F5,F4,F3,F3,F2,F2,F1,F1,F0,F1,F0,。,4.递归函数中的尾递归容易消除。例如：先序遍历二叉树可以改写为：void PreOrderTraverse(BiTree T)While(T)Visit(T-data);PreOrderTraverse(T-lchild);T=T-rchild;/PreOrderTraverse,void delete(LinkList,又如:,void delete(LinkList,可改写为,5.可以用递归方程来表述递归函数的 时间性能。例如:假设解n个圆盘的梵塔的执行 时间为T(n)则递归方程为：T(n)=2T(n-1)+C，初始条件为：T(0)=0,1.了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。2.掌握对特殊矩阵进行压缩存储时的下标变换公式。3.了解稀疏矩阵的两类压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。,4.掌握广义表的结构特点及其存储表示方法，读者可根据自己的习惯熟练掌握任意一种结构的链表，学会对非空广义表进行分解的两种分析方法：即可将一个非空广义表分解为表头和表尾两部分或者分解为n个子表。5.学习利用分治法的算法设计思想编制递归算法的方法。,