数据结构课后习题解答图

《数据结构课后习题解答图》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题及参考答案　第七章图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、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].first

3、arc;q->nextarc;q=q->nextarc);      q->nextarc=p;    }    p->adjvex=j;p->nextarc=NULL;  }//while  returnOK;}//Build_AdjList7.15//本题中的图G均为有向无权图,其余情况容易由此写出StatusInsert_Vex(MGraph&G,charv)//在邻接矩阵表示的图G上插入顶点v{  if(G.vexnum+1)>MAX_VERTEX_NUMreturnINFEASIBLE;  G.vexs[++G.vexnum]=v;  retur

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

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

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

8、ices[i].firstarc=p;  else  {    f