数据结构课后习题解答第七章 图.doc

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

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、 {    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->next

3、arc);      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;  returnOK;}//Insert_VexStatusInsert_Arc(MG

4、raph&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

5、;  if((m=LocateVex(G,v))<0)returnERROR;  G.vexs[m]<->G.vexs[n];//将待删除顶点交换到最后一个顶点  for(i=0;i

6、tusDelete_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,cha

7、rv,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  {    f