《数据结构》课程教学资源：答案_第七章 图

第七章图 7.14 Status Build AdjList( ALGraph&G输入有向图的顶点数边数顶点信息和边的 信息建立邻接表 InitAL Graph(G); nf("%d", &v); fyv< O) return ERROR;/顶点数不能为负 scanf("%d", &a) fa<O) return error,边数不能为负 G arcum=a for(m=0; m<v; m++) G vertices]data= getchar,输入各顶点的符号 for(m=l; m<=a; m++) t= getchar: h= getchar(,t为弧尾h为弧头 if(LOcate Vex(G, t))<)return ERROR if(= Locate Vex(Gh)0) return error;∥顶点未找到 =(ArcNode*)malloc(sizeof(ArcNode)); if(IG vertices. [i]. firstarc)G vertices[]. firstarc=p for(q=G vertices[]. firstarc; q->nextarc; q=q->nextarc); q->nextare-p; p->adjvex=i p->nextarc=NULL i//while eturn OK i//Build AdjList 7.15 ∥本题中的图G均为有向无权图,其余情况容易由此写出 Status Insert vex( MGraph&G, char v/在邻接矩阵表示的图G上插入顶点ⅴ If(G. vexnum+lPMAX VERTEX NUM return INFEASIBLE, G vex++G. vexnum=v eturn oK g//nsert Vex

第七章 图 7.14 Status Build_AdjList(ALGraph &G)//输入有向图的顶点数,边数,顶点信息和边的 信息建立邻接表 { InitALGraph(G); scanf("%d",&v); if(v<0) return ERROR; //顶点数不能为负 G.vexnum=v; scanf("%d",&a); if(a<0) return ERROR; //边数不能为负 G.arcnum=a; for(m=0;m<v;m++) G.vertices[m].data=getchar(); //输入各顶点的符号 for(m=1;m<=a;m++) { t=getchar();h=getchar(); //t 为弧尾,h 为弧头 if((i=LocateVex(G,t))<0) return ERROR; if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到 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; }//while return OK; }//Build_AdjList 7.15 //本题中的图 G 均为有向无权图,其余情况容易由此写出 Status Insert_Vex(MGraph &G, char v)//在邻接矩阵表示的图 G 上插入顶点 v { if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE; G.vexs[++G.vexnum]=v; return OK; }//Insert_Vex

Status Insert Arc( MGraph&G, char v, char w∥在邻接矩阵表示的图G上插入边 if(LOcate Vex(G, v)0)return ERROR; if(=Locate Vex(G, w)<0)return ERROR; if(i-D return ERROR if(!G arcs[00]adj) G arcs[].adF1; G arcum++ return OK. 3//nsert Arc Status delete vex( MGraph&G, char v∥在邻接矩阵表示的图G上删除顶点v n=G vexnum if((m=Locate Vex(G, v))<0)return ERROR; G. vex[m]<-> G vex[n],/将待删除顶点交换到最后一个顶点 for(F0; i<n; i++) G arcs[m=G arcs[n]: G. arcs][= G arcs[;∥将边的关系随之交换 Garcs m). adF0 G. vexnun return OK i/Delete Vex 分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂而伴随 着大量元素的移动时间复杂度也会大大增加 Status delete arc( MGraph&G, char v, char w/在邻接矩阵表示的图G上删除边 (v,w) If(( Locate Vex(G, v)o) return ERROR, if(LOcate Vex(G, w)0)return ERROR; if(G arcs[O0adj) G arcs[]adj=0; G. arcnum-- return OK i//Delete Arc 7.16

Status Insert_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图 G 上插入边 (v,w) { if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(i==j) return ERROR; if(!G.arcs[i][j].adj) { G.arcs[i][j].adj=1; G.arcnum++; } return OK; }//Insert_Arc Status Delete_Vex(MGraph &G,char v)//在邻接矩阵表示的图 G 上删除顶点 v { n=G.vexnum; if((m=LocateVex(G,v))<0) return ERROR; G.vexs[m]<->G.vexs[n]; //将待删除顶点交换到最后一个顶点 for(i=0;i<n;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--; return OK; }//Delete_Vex 分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂,而伴随 着大量元素的移动,时间复杂度也会大大增加. Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图 G 上删除边 (v,w) { if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(G.arcs[i][j].adj) { G.arcs[i][j].adj=0; G.arcnum--; } return OK; }//Delete_Arc 7.16

∥.节省篇幅,本题只给出 Insert_Arc算法其余算法请自行写出 Status Insert Arc( ALGraph&G, char v, char w)/在邻接表表示的图G上插入边(v,w) if(LOcate Vex(G, v))<0) return ERROR; if(Locate Vex(G, w)0) return ERROR p=(ArcNode*)malloc(sizeof(ArcNode)); >adjvex=j, p->nextarc=NULL if(!G vertices[i]. firstarc)Gvertices[i]. firstarc=p else for(q=Gvertices[]. firstarc: q->q->nextarc q=q->nextarc) fq→> adnex=j) return error;∥边已经存在 q->nextarc=p; G arcum++. eturn oK 3//nsert Arc 7.17 ∥.节省篇幅,本题只给出较为复杂的 Delete vex算法.其余算法请自行写出 Status Delete Vex( OGRaph& G. char v∥在十字链表表示的图G上删除顶点v if((m=Locate Vex(G, v)0) return ERROR; n=G. vexnum for(i=0in;计+)/删除所有以v为头的边 if(G xlist[] firstin-> tailvex==m)∥如果待删除的边是头链上的第一个结点 FG. xlist]. firstin G xlist[ firstin=q->hlink free(q); Garcum else/否则 for(p=Gxlist[]. firstin p&&p-hlink->tailvexl=m p=p-hlink) qFE p->hlink=q->hlink free(q): G.arcnum-; i/else

//为节省篇幅,本题只给出 Insert_Arc 算法.其余算法请自行写出. Status Insert_Arc(ALGraph &G,char v,char w)//在邻接表表示的图G上插入边(v,w) { if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; 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) return ERROR; //边已经存在 q->nextarc=p; } G.arcnum++; return OK; }//Insert_Arc 7.17 //为节省篇幅,本题只给出较为复杂的 Delete_Vex 算法.其余算法请自行写出. Status Delete_Vex(OLGraph &G,char v)//在十字链表表示的图 G 上删除顶点 v { if((m=LocateVex(G,v))<0) return ERROR; n=G.vexnum; for(i=0;i<n;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

i//for for(i=0in;i+)/删除所有以v为尾的边 if(G xlist [].firstout> headvex=m)∥/如果待删除的边是尾链上的第一个结点 FG. xlist[]. firstout G xlist[]. firstout=q->tlink free(q): G else∥则 for(p=G xlist i firstout: p&&p->tIink->headvexl=m P=p->tlink); q=p->tlink p→ tlink=q> tlink free(q): G.arcnum-- i/else for(i=mi<n;计+)∥顺次用结点m之后的顶点取代前一个顶点 G. xlist= G. xlist[i+1,∥修改表头向量 for(p=Gxlist[]. firstin p; p=p->hlink p->head vex-, for(p=G xlist [i]. firstout p: p=p->tlink) tailvex-;∥修改各链中的顶点序号 G.vexnum-- return OK i/Delete Vex 7.18 ∥.节省篇幅,本题只给出 Delete arc算法.其余算法请自行写出. Status delete arc( AMLGraph& G. char v, char w)∥在邻接多重表表示的图G上删 除边(v if((i-Locate Vex(G, v)0) return ERROR if(=Locate Vex(G, w)0) return ERROR; if(G. adjmulist[j]. firstedge- G. adjmulist[i].firstedge=G. adjmulist[]. firsted ge->ilink; el

}//for for(i=0;i<n;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 }//for for(i=m;i<n;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--; return OK; }//Delete_Vex 7.18 //为节省篇幅,本题只给出 Delete_Arc 算法.其余算法请自行写出. Status Delete_Arc(AMLGraph &G,char v,char w)////在邻接多重表表示的图 G 上删 除边(v,w) { if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(G.adjmulist[i].firstedge->jvex==j) G.adjmulist[i].firstedge=G.adjmulist[i].firstedge->ilink; else {

for(p=G. adjmulist[]. firstedge p&&p->ilink->jvex!=j p=p->ilink ) if(p) return error;∥.找到 p->link=p->ilink->ilink }/在i链表中删除该边 if(G. adjmulist []. firstedge->ivex==i) G. adjmulist[]. firstedge=G. adjmulist[]. firstedge->jlink else for(p=G. adjmulist I]. firsted ge, p&&p->jlink->ivex=i; p=p->jlink ); if(p) return error;∥未找到 q=p->jlink; p->jlink=q->jlin ee }/在i链表中删除该边 G.arcum- eturn OK. i/Delete Arc 7.19 Status Build Ad](( AMLGraph&G输入有向图的顶点数边数顶点信息和 边的信息建立邻接多重表 Init AMLGraph(G); scanf("%d", &v) ifv<o) return Error;∥顶点数不能为负 G. vexnum=v ifa<o) return error;∥边数不能为负 for(m=0; m<v; m++ G. adjmulist[m]data= getchar,/输入各顶点的符号 for(m=l; m<=a, m++) t= getchar(: h= getcha(0;M为弧尾h为弧头 if(LOcate Vex(G, t )0) return ERROR if(= Locate vex(Gh)<O) return error;∥顶点未找到 p=(EBox* )malloc(sizeof(EBox); p->lvex=lp→ pve=J p> ilink-NULL p>jink=NULL;∥边结点赋初值 if(!G. adjmulist [ ].firstedge)G. adjmulist [].firstedge=p: else q=G.adjmulist i firsted ge, while(q)

for(p=G.adjmulist[i].firstedge;p&&p->ilink->jvex!=j;p=p->ilink); if (!p) return ERROR; //未找到 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) return ERROR; //未找到 q=p->jlink; p->jlink=q->jlink; free(q); } //在 i 链表中删除该边 G.arcnum--; return OK; }//Delete_Arc 7.19 Status Build_AdjMulist(AMLGraph &G)//输入有向图的顶点数,边数,顶点信息和 边的信息建立邻接多重表 { InitAMLGraph(G); scanf("%d",&v); if(v<0) return ERROR; //顶点数不能为负 G.vexnum=v; scanf(%d",&a); if(a<0) return ERROR; //边数不能为负 G.arcnum=a; for(m=0;m<v;m++) G.adjmulist[m].data=getchar(); //输入各顶点的符号 for(m=1;m<=a;m++) { t=getchar();h=getchar(); //t 为弧尾,h 为弧头 if((i=LocateVex(G,t))<0) return ERROR; if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到 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)