熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

嚴蔚敏《數據結構(c語言版)習題集》算法設計題第七章答案

2013-11-15 15:31:49  來源: 數據結構 

  第七章 圖

  

  Status Build_AdjList(ALGraph &G)//輸入有向圖的頂點數邊數頂點信息和邊的信息建立鄰接表

  {

  InitALGraph(G);

  scanf(%d&v);

  if(v<) return ERROR; //頂點數不能為負

  Gvexnum=v;

  scanf(%d&a);

  if(a<) return ERROR; //邊數不能為負

  Garcnum=a;

  for(m=;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上插入邊(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

  {

  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((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

  {

  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

  }//for

  for(i=0;i

  {

  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

  {

  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[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

  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)

  {

  r=q;

  if(q->ivex==i) q=q->ilink;

  else q=q->jlink;

  }

  if(r->ivex==i) r->ilink=p;//注意i值既可能出現在邊結點的ivex域中,

  else r->jlink=p; //又可能出現在邊結點的jvex域中

  }//else //插入i鏈表尾部

  if(!G.adjmulist[j].firste
From:http://tw.wingwit.com/Article/program/sjjg/201311/23563.html

    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.