严蔚敏版数据结构(C语言版)参考答案第七,九章

第七章图7.14StatusBuild_AdjList(ALGraph&G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表{InitALGraph(G);scanf(%d,&v);if(v0)returnERROR;//顶点数不能为负G.vexnum=v;scanf(%d,&a);if(a0)returnERROR;//边数不能为负G.arcnum=a;for(m=0;mv;m++)G.vertices[m].data=getchar();//输入各顶点的符号for(m=1;m=a;m++){t=getchar();h=getchar();//t为弧尾,h为弧头if((i=LocateVex(G,t))0)returnERROR;if((j=LocateVex(G,h))0)returnERROR;//顶点未找到p=(ArcNode*)malloc(sizeof(ArcNode));if(!G.vertices.[i].firstarc)G.vertices[i].firstarc=p;else{for(q=G.vertices[i].firstarc;q-nextarc;q=q-nextarc);q-nextarc=p;}p-adjvex=j;p-nextarc=NULL;}//whilereturnOK;}//Build_AdjList7.15//本题中的图G均为有向无权图,其余情况容易由此写出StatusInsert_Vex(MGraph&G,charv)//在邻接矩阵表示的图G上插入顶点v{if(G.vexnum+1)MAX_VERTEX_NUMreturnINFEASIBLE;G.vexs[++G.vexnum]=v;returnOK;}//Insert_VexStatusInsert_Arc(MGraph&G,charv,charw)//在邻接矩阵表示的图G上插入边(v,w){if((i=LocateVex(G,v))0)returnERROR;if((j=LocateVex(G,w))0)returnERROR;if(i==j)returnERROR;if(!G.arcs[i][j].adj){G.arcs[i][j].adj=1;G.arcnum++;}returnOK;}//Insert_ArcStatusDelete_Vex(MGraph&G,charv)//在邻接矩阵表示的图G上删除顶点v{n=G.vexnum;if((m=LocateVex(G,v))0)returnERROR;G.vexs[m]-G.vexs[n];//将待删除顶点交换到最后一个顶点for(i=0;in;i++){G.arcs[i][m]=G.arcs[i][n];G.arcs[m][i]=G.arcs[n][i];//将边的关系随之交换}G.arcs[m][m].adj=0;G.vexnum--;returnOK;}//Delete_Vex分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂,而伴随着大量元素的移动,时间复杂度也会大大增加.StatusDelete_Arc(MGraph&G,charv,charw)//在邻接矩阵表示的图G上删除边(v,w){if((i=LocateVex(G,v))0)returnERROR;if((j=LocateVex(G,w))0)returnERROR;if(G.arcs[i][j].adj){G.arcs[i][j].adj=0;G.arcnum--;}returnOK;}//Delete_Arc7.16//为节省篇幅,本题只给出Insert_Arc算法.其余算法请自行写出.StatusInsert_Arc(ALGraph&G,charv,charw)//在邻接表表示的图G上插入边(v,w){if((i=LocateVex(G,v))0)returnERROR;if((j=LocateVex(G,w))0)returnERROR;p=(ArcNode*)malloc(sizeof(ArcNode));p-adjvex=j;p-nextarc=NULL;if(!G.vertices[i].firstarc)G.vertices[i].firstarc=p;else{for(q=G.vertices[i].firstarc;q-q-nextarc;q=q-nextarc)if(q-adjvex==j)returnERROR;//边已经存在q-nextarc=p;}G.arcnum++;returnOK;}//Insert_Arc7.17//为节省篇幅,本题只给出较为复杂的Delete_Vex算法.其余算法请自行写出.StatusDelete_Vex(OLGraph&G,charv)//在十字链表表示的图G上删除顶点v{if((m=LocateVex(G,v))0)returnERROR;n=G.vexnum;for(i=0;in;i++)//删除所有以v为头的边{if(G.xlist[i].firstin-tailvex==m)//如果待删除的边是头链上的第一个结点{q=G.xlist[i].firstin;G.xlist[i].firstin=q-hlink;free(q);G.arcnum--;}else//否则{for(p=G.xlist[i].firstin;p&&p-hlink-tailvex!=m;p=p-hlink);if(p){q=p-hlink;p-hlink=q-hlink;free(q);G.arcnum--;}}//else}//forfor(i=0;in;i++)//删除所有以v为尾的边{if(G.xlist[i].firstout-headvex==m)//如果待删除的边是尾链上的第一个结点{q=G.xlist[i].firstout;G.xlist[i].firstout=q-tlink;free(q);G.arcnum--;}else//否则{for(p=G.xlist[i].firstout;p&&p-tlink-headvex!=m;p=p-tlink);if(p){q=p-tlink;p-tlink=q-tlink;free(q);G.arcnum--;}}//else}//forfor(i=m;in;i++)//顺次用结点m之后的顶点取代前一个顶点{G.xlist[i]=G.xlist[i+1];//修改表头向量for(p=G.xlist[i].firstin;p;p=p-hlink)p-headvex--;for(p=G.xlist[i].firstout;p;p=p-tlink)p-tailvex--;//修改各链中的顶点序号}G.vexnum--;returnOK;}//Delete_Vex7.18//为节省篇幅,本题只给出Delete_Arc算法.其余算法请自行写出.StatusDelete_Arc(AMLGraph&G,charv,charw)////在邻接多重表表示的图G上删除边(v,w){if((i=LocateVex(G,v))0)returnERROR;if((j=LocateVex(G,w))0)returnERROR;if(G.adjmulist[i].firstedge-jvex==j)G.adjmulist[i].firstedge=G.adjmulist[i].firstedge-ilink;else{for(p=G.adjmulist[i].firstedge;p&&p-ilink-jvex!=j;p=p-ilink);if(!p)returnERROR;//未找到p-ilink=p-ilink-ilink;}//在i链表中删除该边if(G.adjmulist[j].firstedge-ivex==i)G.adjmulist[j].firstedge=G.adjmulist[j].firstedge-jlink;else{for(p=G.adjmulist[j].firstedge;p&&p-jlink-ivex!=i;p=p-jlink);if(!p)returnERROR;//未找到q=p-jlink;p-jlink=q-jlink;free(q);}//在i链表中删除该边G.arcnum--;returnOK;}//Delete_Arc7.19StatusBuild_AdjMulist(AMLGraph&G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接多重表{InitAMLGraph(G);scanf(%d,&v);if(v0)returnERROR;//顶点数不能为负G.vexnum=v;scanf(%d,&a);if(a0)returnERROR;//边数不能为负G.arcnum=a;for(m=0;mv;m++)G.adjmulist[m].data=getchar();//输入各顶点的符号for(m=1;m=a;m++){t=getchar();h=getchar();//t为弧尾,h为弧头if((i=LocateVex(G,t))0)returnERROR;if((j=LocateVex(G,h))0)returnERROR;//顶点未找到p=(EBox*)malloc(sizeof(EBox));p-ivex=i;p-jvex=j;p-ilink=NULL;p-jlink=NULL;//边结点赋初值if(!G.adjmulist[i].firstedge)G.adjmulist[i].firstedge=p;else{q=G.adjmulist[i].firstedge;while(q){r=q;if(q-ivex==i)q=q-ilink;elseq=q-jlink;}if(r-ivex==i)r-ilink=p;//注意i值既可能出现在边结点的ivex域中,elser-jlink=p;//又可能出现在边结点的jvex域中}//else//插入i链表尾部if(!G.adjmulist[j].firstedge)G.adjmulist[j].firstedge=p;else{q=G.adjmulist[i].firstedge;while(q){r=q;if(q-jvex==j)q=q-jlink;elseq=q-ilnk;}if(r-jvex==j)r-jlink=p;elser-ilink=p;}//else//插入j链表尾部}//forreturnOK;}//Build_AdjList7.20intPass_MGraph(MGraphG)//判断一个邻接矩阵存储的有向图是不是可传递的,是则返回1,否则返回0{for(x=0;xG.vexnum;x++)for(y=0;yG.vexnum;y++)if(G.arcs[x][y]){for(z=0;zG.vexnum;z++)if(z!=x&&G.arcs[y][z]&&!G.arcs[x][z])return0;//图不可传递的条件}//ifreturn1;}//Pass_MGraph分析:本算法的时间复杂度大概是O(n^2*d).7.21intPass_ALGraph(ALGraphG)//判断一个邻接表存储的有向图是不是可传递的,是则返回1,否则返回0{for(x=0;xG.vexnum;x++)for(p=G.vertices[x].firstarc;p;p=p-nextarc){y=p-adjvex;for(q=G.vertices[y].firstarc;q;q=q-nextarc){z=q-adjvex;if(z!=x&&!is_adj(G,x,z))return0;}//for}//for