数据结构Chap.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第七章 图,1,7.1,抽象数据类型图的定义,7.2,图的存储表示,7.3,图的遍历,7.4,最小生成树,7.5,两点之间的最短路径问题,7.6,拓扑排序,2,图,是由一个,顶点集,V,和一个,弧集,R,构成的数据结构。,Graph=(V,R),其中，,R,|v,wV,且,P(v,w),表示从,v,到,w,的一条弧，并称,v,为,弧,尾，,w,为,弧,头。,谓词,P(v,w),定义了弧,的意义或信息。,图的结构定义:,3,由于“弧”是有方向的，因此称由顶点集和弧集构成的图为,有向图,。,E,A,C,B,D,例如,:,G,1,=(V,1,VR,1,),其中,V,1,=A,B,C,D,E,VR,1,=,4,若,VR,必有,VR,则称,(v,w),为顶点,v,和顶点,w,之间存在一条,边,。,B,C,A,F,E,D,由顶点集和边集构成的图称作,无向图,。,例如,:,G,2,=(V,2,VR,2,),V,2,=A,B,C,D,E,F,VR,2,=(,A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F),5,名词和术语,网、子图,完全图,、,稀疏图、稠密图,邻接点、度、入度、出度,路径、路径长度、简单路径,、,简单回路,连通图、连通分量、,强连通图、强连通分量,生成树、生成森林,6,A,B,E,C,F,A,E,F,B,C,设图,G=(V,VR),和图,G,=(V,VR),且,VV,VRVR,则称,G,为,G,的,子图,。,15,9,7,21,11,3,2,弧或边带权的图分别称作,有向网,或,无向网,。,7,假设图中有,n,个顶点，,e,条边，则,含有,e=n(n-1)/2,条边的无向图称作,完全图,;,含有,e=n(n-1),条弧的有向图称作,有向完全图,;,若边或弧的个数,enlogn,，则称作,稀疏图,，,否则称作,稠密图,。,8,对于无向图,假若顶点,v,和顶点,w,之间存在一条边，则称顶点,v,和,w,互为,邻接点,，,称,边,(v,w),依附于,顶点,v,和,w,或,和顶点,v,和,w,相,关联,。,和顶点,v,关联的,边的数目,定义为顶点,v,的,度,。,例如,:,ID(B)=3,ID(A)=2,A,C,D,F,E,B,右侧图中,9,顶点的,出度,:,以顶点,v,为弧尾的弧的数目,;,A,B,E,C,F,对有向图来说,，,顶点的,入度,:,以顶点,v,为弧头的弧的数目,。,顶点的,度,(,TD,)=,出度,(,OD,)+,入度,(,ID,),例如,:,ID(B)=2,OD(B)=1,TD(B)=3,由于弧有方向性，则有,入度,和,出度,之分,10,设图,G=(V,VR),中有一个顶点序列,u=v,i,0,v,i,1,v,i,m,=w,中,，,(v,i,j-1,v,i,j,),VR 1jm,则称从顶点,u,到顶点,w,之间存在一条,路径,。,路径上,边的数目,称作,路径长度,。,有向图的,路径也是,有向的。,A,B,E,C,F,如,:,从,A,到,F,长度为,3,的路径,A,B,C,F,简单路径,:,指序列中,顶点不重复,出现的路径。,例如：,A,E,C,F,回路,:,首尾顶点相同的路径。,例如：,A,E,C,F,B,C,F,A,简单回路,:,中间顶点不重,的回路。,例如：,A,E,C,F,A,11,若,无向,图,G,中任意两个顶点之间都有路径相通,，,则称此图为,连通图,;,若无向图为非连通图，则图中各个极大连通子图称作此图的,连通分量,。,B,A,C,D,F,E,B,A,C,D,F,E,12,若任意两个顶点之间都存在一条有向路径，则称此有向图为,强连通图,。,A,B,E,C,F,A,B,E,C,F,对有向图，,否则，其各个强连通子图称作它的,强连通分量,。,13,假设一个连通图有,n,个顶点和,e,条边，其中,n-1,条边和,n,个顶点构成一个极小连通子图，称该极小连通子图为此连通图的,生成树,。,对非连通图，则称由各个连通分量的生成树的集合为此非连通图的,生成森林,。,B,A,C,D,F,E,14,2、非连通图的深度优先搜索遍历,B,C,D,E,A,(1)普里姆算法(Prim),从图中某个顶点出发游历图，访遍,若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。,typedef struct ArcNode /弧的定义,4，13（E不做），15,设在 n 个城市之间建立通讯网,则要连通 n 个城市最少需要修建 n-1条线路，现要拿出最节省经费的通讯网建设方案。,深度相同时，存储结构b先于cde,f先于g,e先于h。,C5 高级语言程序设计 C2,有向无环图,简称 DAG(directed acycline graph),它可以表示一个工程或系统的流程图,也可以表示学生的选课关系。,本次上机为加分内容，非必查项目。,F F F F F F F F F,深度优先搜索的邻接表实现,TD(Vi)=ID(Vi)+OD(Vi),7.2,图的存储表示,一、,图的数组,(,邻接矩阵,),存储表示,二、图的邻接表存储表示,15,1.,无向图的邻接矩阵存储表示,定义,:,矩阵的元素为,一维数组：,二维数组：,用于存储顶点信息。,用于存储图中顶点之间,关联关系,邻接矩阵,Ai,j=,若（,v,i,v,j,）,VR,0,反之,对,称,矩,阵,C,B,A,D,E,0,1,0,1,0,C,0,0,0,1,B,0,1,1,0,A,0,1,0,A,0,0,1,B,0,1,E,1,0,D,0,1,C,E,D,无向图,TD(Vi),：,第,i,行,非零元素的个数，或,第,i,列,非零元素的个数,16,2.,有向图的邻接矩阵存储表示,定义,:,矩阵的元素为,一维数组：,二维数组：,用于存储顶点信息。,用于存储图中顶点之间,关联关系,邻接矩阵,Ai,j=,若,VR,0,反之,非,对,称,矩,阵,0,0,0,1,C,0,0,0,B,0,1,0,A,1,0,A,0,0,B,0,D,1,C,D,B,A,C,D,有向图,OD(Vi),：,第,i,行,非零元素的个数，,ID(Vi):,第,i,列,非零元素的个数,17,3.,网的邻接矩阵存储表示,定义,:,矩阵的元素为,一维数组：,二维数组：,用于存储顶点信息。,用于存储图中顶点之间,关联关系,邻接矩阵,0,若,i=j,对,称,矩,阵,无向网,B,A,E,F,D,C,19,4,33,21,11,14,6,5,6,16,Ai,j=,0,其他,若,或（,v,i,v,j,),VR,w,ij,C,B,A,A,B,D,C,D,F,E,E,F,6,0,5,6,0,16,16,0,6,5,0,6,19,21,11,4,14,14,11,21,19,4,33,0,0,33,18,Typedef enumDG,DN,UDG,UDN GraphKind,typedef struct,ArcNode,/,弧的定义,VRType adj;/,VRType,是顶点关系类型。,/,对无权图，用,1,或,0,表示相邻否；,/,对带权图，则为权值类型。,InfoType *info;,/,该弧相关信息的指针,ArcNode;,邻接矩阵的,C,语言类型描述,19,typedef struct /,图的定义,VertexType vexsMAX_VERTEX_NUM;,/,顶点信息,ArcNode arcsMAX_VERTEX_NUM,MAX_VERTEX_NUM;,/,弧的信息,int,vexnum,arcnum;/,顶点数，弧数,GraphKind kind;/,图的种类标志,AdjMatrix;,邻接矩阵的,C,语言类型描述,20,二,.,图的邻接表存储表示,1,A,2 5,2,B,1 5 6,3,C,4 6,4,D,3 6,5,E,1,2,6,F,2,3 4,B,A,C,D,F,E,无向图,边关联两个顶点，故每条边对应两个边结点。,adjvex nextarc,边,(,弧,),顶点,data firstarc,21,有向图的邻接表,1 4,2,3,0 1,2,0 1 2 3 4,A,B,C,D,E,A,B,E,C,D,可见，在有向图的邻接表中不易找到指向该顶点的弧,弧结点记录的是,以该顶点为,尾,的弧,22,A,B,E,C,D,有向图的逆邻接表,A,B,C,D,E,3,0,3,4,2,0,0,1,2,3,4,弧结点记录的是,以该顶点为头的弧,在有向图的逆邻接表中不易找到该顶点发出的弧。,23,A,B,C,D,E,15,3,7,21,11,9,2,有向网,E,D,C,B,A,2,15,3,3,4,2,1,11,3,21,5,9,2,7,有向网的邻接表,边,(,弧,),顶点,data farc,adjv,info nextarc,24,邻接表存储结构,C,语言类型描述,#define MAX_V 20,typedef enum,DG,DN,UDG,UDN,GraphKind;,typedef struct ArcNode,int adjvex;,OtherInfo info;,struct ArcNode *nextarc;,ArcNode;,/*,弧的类型*,/,C5 高级语言程序设计 C2,一、求某顶点到其余各点的最短路径,int adjvex;,TD(Vi)=ID(Vi)+OD(Vi),OtherInfo info;,用于存储图中顶点之间关联关系,顶点的入度:以顶点v为弧头的弧的数目。,（1）初始U=u0(u0V),TE=；,C1 高等数学,3 C 1 4,邻接矩阵的C语言类型描述,一、图的数组(邻接矩阵)存储表示,假设distk表示当前所求得的从源点到顶点k的最短路径,for(vi=0;viadjvex),DFS,（,g,p-adjvex,）；,p=p-nextarc,；,1,A 2 3 4 5 6,2,B 1 5 6,3,C 1 4,4,D 1 3,5,E 1 2,6,F 1 2,2,、非连通图的深度优先搜索遍历,首先将图中每个顶点的访问标志设为,false,之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，调用,DFS,进行深度优先搜索遍历，否则继续检查下一顶点。,36,2,、非连通图的深度优先搜索遍历,首先将图中每个顶点的访问标志设为,false,之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，调用,DFS,进行深度优先搜索遍历，否则继续检查下一顶点。,void TraverseGraph(GNODE g),for(vi=0;vivexnum;vi+),visitedvi=FALSE;,/*,标志数组初始化*,/,for(vi=0;vi,w,1,V,-,w,2,V,-,w,8,的路径长度为,1,；,V,-,w,7,V,-,w,3,V,-,w,5,的,路径长度为,2,；,V,-,w,6,V,-,w,4,的路径长度为,3,。,w,1,V,w,2,w,7,w,6,w,3,w,8,w,5,w,4,广度优先遍历类似于树的按层次遍历,41,F F F F F F F F F,V,0,w,1,w,8,w,3,w,7,w,6,w,2,w,5,w,4,w,1,V,0,w,2,w,7,w,6,w,3,w,8,w,5,w,4,v,0,w,1,w,2,w,8,w,7,w,3,w,5,w,6,w,4,v,0,w,1,w,2,w,8,w,7,w,3,w,5,w,6,w,4,visited,queue,T,T,T,T,T,T,T,T,T,0 1 2 3 4 5 6 7 8,A,D,G,B,E,H,C,F,I,1,4,6,5,7,8,2,3,访问序列为：,A,、,B,、,E,、,D,、,C,、,G,、,F,、,H,、,I,。,43,2,、非连通图的广度优先搜索遍历,首先将图中每个顶点的访问标志设为,FALSE,之后检查图中每个顶点：,如果未被访问，则以该顶点为起始点，调用,BFS,进行广度优先搜索遍历；否则继续检查下一顶点；,直至图中所有顶点都被访问到为止。,44,1,、,生成树,连通图的,极小连通子图,称为图的,生成树,显然顶点数为,n,的连通图,生成树边数为,n-1,。,非连通图,对每个连通分量,通过遍历可得到一棵生成树。各个连通分量的生成树可组成非连通图的,生成树森林,。,从连通图中某一顶点出发遍历图时,图中所有的顶点加上遍历时经过的边所构成的,子图,T,恰好就是一棵生成树,7.4,最小生成树,45,深度优先生成树,/,森林,a,c,h,d,e,k,f,b,g,c,h,k,f,e,d,a,b,g,46,广度优先生成树,/,森林,a,b,c,h,d,e,k,f,g,47,2,、最小生成树,问题：,设在,n,个城市之间建立通讯网,则要连通,n,个城市最少需要修建,n-1,条线路，,现要拿出最节省经费的通讯网建设方案,。,假设无向图的每条边表示两城市之间一条线路,权值表示修建费用,则该问题归结为求权值之和最小的,生成树,问题。,48,算法二：（克鲁斯卡尔算法）,算法一：（普里姆算法）,尽可能选取权值小的边，但不能构成回路。,选取,n-1,条恰当的边以连接网的,n,个顶点。,最小生成树的要解决的两个问题：,49,取图中任意一个顶点,v,作为生成树的根，之后往生成树上,添加新的顶点,w,。,w,满足条件：,在待添加的顶点,w,和已经在生成树上的顶点集,V,之间必定存在一条边，并且,该边的权值在所有连通顶点,V,（集合）和,w,之间的边中取值最小,。,之后继续往生成树上添加顶点，直至生成树上含有,n,个顶点为止。,普里姆算法的基本思想,:,50,在生成树的构造过程中，图中,n,个顶点分属两个集合：,已落在生成树上的顶点集,U,和尚未落在生成树上的顶点集,V-U,，则应,在所有连通,U,中顶点和,V-U,中顶点的边中选取权值最小的边,。,U,V-U,51,(1),普里姆算法,(,Prim,),设,N=(V,E),是连通网，,prim,算法步骤为：,（,1,）初始,U=u,0,(u,0,V),TE=,；,（,2,）在所有,uU,vV-U,的边中选一条代,价最小的边,（,u,0,，,v,0,）,并入集合,TE,，,同时将,v,0,并入,U,；,（,3,）重复（,2,）,直到,U=V,TE,含有,n-1,条边,。,此时,T=(V,TE),为,N,的最小生成树。,52,a,b,c,d,e,g,f,19,5,14,18,27,16,8,21,3,12,7,例如,:,a,e,d,c,b,g,f,14,8,5,3,16,21,所得生成树权值和,=14+8+3+5+16+21=67,53,连通网用,带权的邻接矩阵,表示,并,设置两个,辅助数组,closest,，,lowcost,，,对当前,V,U,集中的每个顶点，记录和顶点集,U,中顶点相连接的代价最小的边,.,2.,普里姆算法的基本思想,:,lowcost,/*,边的权值*,/,closest,/*U,集中的顶点序号*,/,mincost(u,v)|uU,vV-U,lowcostv=,0 vU,closestv,存放,U,中与,v,最近的顶点序号。,辅助数组,54,A,1,A,5,A,0,6,A,A,B,C,D,E,F,4,F,2,C,5,C,6,C,C,F,3,B,B,D,E,A,E,A,F,B,D,C,6,5,3,6,6,4,2,5,1,5,E,A,F,B,D,C,5,3,4,1,2,0,0,0,0,0,对,称,矩,阵,C,B,A,A,B,D,C,D,F,E,E,F,5,0,5,1,0,6,5,6,0,5,1,5,0,5,4,6,3,2,6,3,2,4,6,0,0,6,2.,普里姆算法的基本思想,:,55,具体做法,:,先构造一个,只含,n,个顶点的子图,SG,，然后从权值最小的边开始，若它的添加不使,SG,中产生回路，则在,SG,上加上这条边，如此重复，直至加上,n-1,条边为止。,考虑问题的出发点,:,为使生成树上,边的权值之和达到最小,，则应使生成树中每一条边的权值尽可能地小。,3.,克鲁斯卡尔算法的基本思想：,56,3.,克鲁斯卡尔算法的基本思想,1.,所有的边按权值从小到大排序,5,(B,C),B,A,E,F,D,C,19,18,33,21,11,14,6,5,6,16,B,A,E,F,D,C,18,11,6,5,16,6,(B,D),6,(C,D),11,(B,E),14,(D,E),16,(A,B),18,(D,F),19,(A,F),21,(A,E),33,(E,F),2.,顶点集合状态,:,3.,最小生成树边的集合：,所得生成树权值和,=5+6+11+16+18=56,(B,C),(B,D),(B,E),(A,B),(D,F),A,B,C,D,E,F,B,C,B,C,D,B,C,D,E,B,C,D,E,A,B,C,D,E,A,F,57,B,A,E,G,D,C,19,18,33,21,11,14,6,5,6,16,B,A,E,G,D,C,19,18,33,21,11,14,6,5,6,16,B,A,E,G,D,C,18,11,6,5,16,B,A,E,G,D,C,18,11,5,6,16,图的生成树不唯一，从不同的顶点出发进行遍历，可以得到不同的生成树。,即使从相同的顶点出发，,在选择最小边时，可能有多条同样的边可选,，此时任选其一。,最小生成树不唯一,:,58,普里姆算法,克鲁斯卡尔算法,时间复杂度,O(n,2,),O(eloge),稠密图,稀疏图,算法名,适应范围,比较两种算法,59,7.5,两点之间的 最短路径问题,求从某个顶点到其余各点的最短路径,60,每一对顶点之间的最短路径,带权有向图,0,5,1,2,3,4,100,30,60,10,10,5,50,20,最短路径 长度,（,v0,，,v2,）,10,（,v0,，,v4,）,30,（,v0,，,v4,，,v3,）,50,（,v0,v4,v3,v5)60,v0v1,无,一、求某顶点到其余各点的最短路径,依,最短路径的长度,递增的次序,逐个产生各最短路径。,1,、迪杰斯特拉,(,Dijkstra),算法基本思想,:,设有带权的有向图,D=(V,E),，,D,中的边权为,W(e),。已知源点为,v,0,，求,v,0,到其它各顶点的最短路径。,62,源点,v,1,假设图中所示为从源点到其余各点之间的最短路径,则在这些路径中,必然存在一条,长度最短,者,v,2,1),第一条,(,长度最短的,),最短路径的特点：,在这条路径上，,必定只含一条弧,并且这条弧的,权值最小。,(,设为,v,0,v,i,),63,2),下一条,(,长度次短的,),最短路径的特点：,它只可能有两种情况：或者是,直接从源点到该点,v,j,(,只含一条弧,);,或者是,从源点经过顶点,v,i,再到达,v,j,(,由两条弧组成,),。,3),再下一条长度次短的,最短路径特点:,它可能有两种情况：或者是,直接从源点到该点,(,只含一条弧,),；或者是,从源点经过顶点,v,i,、,v,j,再到达该顶点,(,由多条弧组成,),。,其余依次类推,64,假设,distk,表示,当前所求得的从源点到顶点,k,的最短路径,则一般情况下，,distk=,或者,=,+,2,、迪杰斯特拉算法的实现,65,一、存储结构,1,、带权,邻接矩阵,cost,：,用,costi,，,j,表示弧,vi,，,vj,上的权。,2,、顶点分为两组：,S,，,V-S,，,S,中存放,已求得最短路径,的终点的集合。,3,、辅助一维数组,dist,：,disti,表示源点到,vi,的最短路径长度,66,二、最短路径,1,、第一条最短路径,distj=mindisti|v,i,V-S,最短路径（,v,，,v,j,），,S=S v,j,2,、修改,V-S,中顶点的,dist,值,disti=mindisti,，,distj+costj,，,i vi V-S,3,、下一条最短路径,distj=min disti|viV-S,4,、,v,j,并入集合,S,，重复,2,，,3,，直到,v,出发,可以到达的所有顶点都包含在,S,中。,67,最短路径 长度,（,v0,v2,）,10,（,v0,v4,）,30,（,v0,v4,v3,）,50,（,v0,v4,v3,v5)60,v0v1,无,终点,disti,集合,S,V,1,V,2,V,3,V,4,V,5,1,2,3,4,5,5,2,4,100,30,60,10,10,5,50,20,3,1,0,/,/,/,/,0,2,4,3,5,1,60,(V,0,V,4,V,3,V,5,),/,/,/,0,2,4,3,5,90,(V,0,V,4,V,5,),/,50,(V,0,V,4,V,3,),/,0,2,4,3,100,(V,0,V,5,),30,(V,0,V,4,),60,(V,0,V,2,V,3,),/,0,2,4,100,(V,0,V,5,),30,(V,0,V,4,),10,(V,0,V,2,),0,2,68,0,7.6,拓扑排序,69,有向无环图,简称,DAG(directed acycline graph),它可以表示一个工程或系统的流程图,也可以表示学生的选课关系。,这样的有向图,必须是无环,的,才能保证工程顺利进行,而判定有向图是否,无环,较复杂，为此采用,拓扑排序或逆拓扑排序,的方法验证之。,70,用顶点表示,活动,，用弧表示活动间的,优先关系,的有向无环图，称为,顶点表示活动的网,(Activity On Vertex Network),简称,AOV-,网,。,如下页的课程关系表，若用顶点表示课程，弧表示先决条件，则课程关系可用一个有向无环图表示。,71,C,1,高等数学,C,2,程序设计基础,C,3,离散数学,C,1,C,2,C,4,数据结构,C,3,C,2,C,5,高级语言程序设计,C,2,C,6,编译方法,C,5,C,4,C,7,操作系统,C,4,C,9,C,8,普通物理,C,1,C,9,计算机原理,C,8,课程代号,课程名称,先修课程,例如：,计算机专业学生的学习就是一个工程,72,学生课程学习工程图,C,1,C,8,C,2,C,3,C,9,C,6,C,7,C,4,C,5,73,何谓“拓扑排序”？,对有向图进行如下操作,:,按照,AOV,网给出的次序关系，将图中顶点排成一个线性序列，对于,AOV,网中没有限定次序关系的顶点，则可以人为加上任意的次序关系。,74,由此所得顶点的线性序列称之为,拓扑有序序列,例如：对于下列有向图,B,D,A,C,可求得,拓扑有序序列,：,A B C D,或,A C B D,75,B,D,A,C,反之，对于下列有向图,不能求得它的拓扑有序序列。,因为图中存在一个回路,B,C,D,如何进行拓扑排序？,1.,从有向图中选取一个,没有前驱,的顶点，并输出之,;,重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。,所有顶点已输出，,拓扑排序完成，说明,图中不存在有向回路,或,剩余的顶点入度都不为,0,（此时图中有环,，拓扑排序不能进行下去）。,2.,从有向图中,删去此顶点以及所有以它为弧尾的弧,;,76,a,b,c,g,h,d,f,e,a,b,h,c,d,g,f,e,在算法中需要用定量的描述替代定性的概念,没有前驱的顶点,入度为零的顶点,删除顶点及以它为尾的弧,弧头顶点的入度减,1,77,5,4,3,2,1,6,2,2,2,2,0,0,2,3,2,3,5,4,4,5,In link,1,1,1,1,三、拓扑排序算法描述,1,6,4,2,5,3,拓扑序列：,0,0,0,0,1,2,3,0,栈,6,1,6,1,4,5,3,2,4,5,3,2,78,如何进行逆拓扑排序？,.,从有向图中选取一个,没有后继,的顶点,(,出度为,0,的顶点,),，并输出之；,.,从有向图中,删去此顶点以及所有以它为头的弧；,重复上述两步，直至图中不存在没有后继的顶点,所有顶点已输出，逆拓扑排序完成，说明图中不存在有向回路,或,剩余的顶点出度都不为,0,（此时图中有环，逆拓扑排序不能进行下去）,。,7.6,逆拓扑排序,79,C,D,A,G,F,B,H,E,E,F,H,G,B,D,C,A,没有后继的顶点,出度为零的顶点,删除顶点及以它为头的弧,弧尾顶点的出度减,1,在算法中需要用定量的描述替代定性的概念,逆拓扑排序例如：,80,第四次上机,目的：熟悉图的遍历,内容：,P247 实习题1,要求：,本次上机为加分内容，非必查项目。,81,作业,P244,1，2，14,P245,4，13（E不做），15,82,用,Prim,算法从顶点,A,开始，手工构造最小生成树。,用,Kruskal,算法手工构造最小生成树,B,A,E,F,G,D,C,18,27,21,16,14,12,8,7,5,3,19,补充作业,作业：,P169,1,，,2,，,3,，,7,，,11,，,13,83,用,Prim,算法从顶点,A,开始，手工构造最小生成树。,用,Kruskal,算法手工构造最小生成树,B,A,E,F,G,D,C,18,27,21,16,14,12,8,7,5,3,19,补充作业,作业：,P169,11 ,13,84,