清华大学数据结构7

《清华大学数据结构7》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、清华大学数据结构7第七章图7.14StatusBuild_AdjList(ALGraph&G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表{InitALGraph(G);scanf("%d",&v);if(v<0)returnERROR;//顶点数不能为负G.vexnum=v;scanf("%d",&a);if(a<0)returnERROR;//边数不能为负G.arcnum=a;for(m=0;m

2、or(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

3、->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

4、;}//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_V

5、ex(MGraph&G,charv)//在邻接矩阵表示的图G上删除顶点v{n=G.vexnum;if((m=LocateVex(G,v))<0)returnERROR;G.vexs[m]<->G.vexs[n];//将待删除顶点交换到最后一个顶点for(i=0;i

6、x分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂,而伴随着大量元素的移动,时间复杂度也会大大增加.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;}//D

7、elete_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.vert

8、ices[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_V