./問題描述：實驗題目：需要在某個城市n個居民小區之間鋪設煤氣管道,則在這n個居民小區之間只需要鋪設n-1條管道即可。假設任意兩個小區之間都可以鋪設管道,但由于地理環境不同,所需要的費用也不盡相同。選擇最優的方案能使總投資盡可能小,這個問題即為求無向網的最小生成樹。基本要求：在可能假設的m條管道中,選取n-1條管道,使得既能連通n個小區,又能使總投資最小。每條管道的費用以網中該邊的權值形式給出,網的存儲采用鄰接表的結構。測試數據：使用下圖給出的無線網數據作為程序的輸入,求出最佳鋪設方案。右側是給出的參考解。簡述每一部分的對象、目的和要求：=1\*ROMANI.主函數部分：對象：圖G；目的：為圖G分配空間,以作為后續調用函數的參數；要求：無。=2\*ROMANII.Create_ALGraph<>函數部分：對象：頂點,邊及其權值；目的：將頂點,邊存放在一起,構成圖；要求：構造頂點表,各頂點的鄰接表以構造圖。=3\*ROMANIII.Create_WLGraph<>函數部分：對象：圖G；目的：將圖中的權值只存放一次,存放到w指向的結構體中；要求：權值只存放一次,再分別存放該邊的左右頂點。=4\*ROMANIV.select_info<>函數部分：對象：w指向的結構體；目的：將該結構體中的各權值以升序排列；要求：采用簡單選擇法進行排序。=5\*ROMANV.Create_TLGraph<>函數部分：對象：排序后的w指向的結構體；目的：找到構成最小生成樹的邊；要求：依權值升序排列,判斷各邊是否構成回路來取舍各邊。需求分析程序所能達到的基本可能：在n個小區m條管道中,選取n-1條管道,實現連通這n個小區,同時權值之和為最小。輸入輸出形式及輸入值范圍：程序運行后,用戶可根據提示信息："Pleaseinputtheverticesandtheedges<n,e>:"輸入頂點數和邊數,再根據提示信息："Pleaseinputtheinformationofthevertices<v>:"輸入頂點信息,然后進入循環,創建各個頂點的鄰接表,即根據提示信息"Pleaseinputtheinformationofedges<p,q>:"和"Pleaseinputtheinformationofweight:"依次輸入各頂點與其他頂點本身以及兩者之間的權值,創建圖完畢。用戶輸入完畢后,程序自動輸出運行結果。輸入值必須為字母和浮點數,可以不必區分大小寫。測試數據要求：用戶輸入字母時,輸入大寫或小寫,都可以被該程序識別,正常運行。但必須根據提示信息后面給出的參考形式,有針對性地輸入逗號。概要設計為了實現上述功能,該程序以鄰接表來存儲圖,因此需要圖這個抽象數據類型。圖抽象數據類型定義：ADTALGraph{數據對象：D={,i=1,2,3,n,n}數據關系：R=;基本操作：Create_ALGraph<G>；//創建圖Create_WLGraph<G>；//將圖G中各頂點以及權值存放到新圖中,權值只存放一次select_info<W,G>；//將新圖W中的權值按升序排列Create_TLGraph<w,G>；//將最小生成樹以頂點對〔i,j的形式輸出}ADTALGraph2.本程序保護模塊：主函數模塊圖模塊調用關系：3.主要算法流程圖：Create_ALGraph<>算法流程圖：Create_WLGraph<>算法流程圖：Create_TLGraph<>算法流程圖：詳細設計相關頭文件的調用說明：#include<stdio.h>#include<stdlib.h>#defineMaxVerNum1002.元素類型、結點類型和結點指針類型：staticvoidforcefloat<float*p>{floatf=*p;forcefloat<&f>;}typedefstructnode{intadjvex;floatinfo;structnode*next;}EdgeNode;typedefstructvnode{charvertex;EdgeNode*firstedge;}VertexNode;typedefVertexNodeAdjList[MaxVerNum];structbian{intz,y;floatinfo;};typedefstruct{charv[MaxVerNum];structbiane[MaxVerNum];}WGraph;structvisit{visited[MaxVerNum];position[MaxVerNum];vvpp[MaxVerNum][MaxVerNum];}3.鄰接表類型：typedefstruct {AdjListadjlist; intn,e; }ALGraph;//部分基本操作的偽碼實現Create_ALGraph<ALGraph*G>{inti,j;charp,q;intk;/*intx=0;*/EdgeNode*s;chara,b;printf<"Pleaseinputtheverticesandtheedges<n,e>:\n">;scanf<"%d,%d",&<G->n>,&<G->e>>;printf<"Pleaseinputtheinformationofthevertices<v>:\n">;getchar<>;for<i=0;i<<G->n>;i++>{scanf<"%c",&<G->adjlist[i].vertex>>;G->adjlist[i].firstedge=NULL;/*if<G->adjlist[i].vertex!=''&&G->adjlist[i].vertex!='\n'&&G->adjlist[i].vertex!=' '>x++;*/}for<k=0;k<2*<G->e>;k++>{printf<"Pleaseinputtheinformationofedges<p,q>:\n">;getchar<>;scanf<"%c,%c",&p,&q>;s=<EdgeNode*>malloc<sizeof<EdgeNode>>;s->adjvex=q-64;i=p-64;getchar<>;printf<"Pleaseinputtheinformationofweight:\n">;scanf<"%f",&<s->info>>;s->next=G->adjlist[i-1].firstedge;G->adjlist[i-1].firstedge=s;}/*printf<"Pleaseoutputtheinformation:\n">;printf<"%d,%d\n",G->n,G->e>;printf<"x=%d\n",x>;for<i=0;i<G->n;i++>{printf<"%c\n",G->adjlist[i].vertex>;s=G->adjlist[i].firstedge;while<s!=NULL>{printf<"thelinbianis%d,theinfois%.1f\n",s->adjvex,s->info>;s=s->next;}}*/}intPanduan_Vertex<intk,inti,WGraph*w,EdgeNode*s>{intt;for<t=0;t<k;t++>if<<w->e[t]>.y==i+1&&<w->e[t]>.z==s->adjvex>return1;return0;}voidselect_info<WGraph*W,ALGraph*G>{inti,j,p,k;floatt;for<i=0;i<<G->e>;i++>{p=i;for<j=i+1;j<<G->e>;j++>if<W->e[j].info<W->e[p].info>p=j;if<p!=i>{t=W->e[p].info;W->e[p].info=W->e[i].info;W->e[i].info=t;k=W->e[p].z;W->e[p].z=W->e[i].z;W->e[i].z=k;k=W->e[p].y;W->e[p].y=W->e[i].y;W->e[i].y=k;}}/*for<i=0;i<<G->e>;i++>printf<"%.1f",W->e[i].info>;printf<"\n">;*/}intjudge_vertex<WGraph*w,inti,structvisit*vp>{if<vp->visited[w->e[i].z-1]==-1&&vp->visited[w->e[i].y-1]==-1>return1;elseif<vp->visited[w->e[i].z-1]==-1&&vp->visited[w->e[i].y-1]==1>return2;elseif<vp->visited[w->e[i].y-1]==-1&&vp->visited[w->e[i].z-1]==1>return3;elseif<vp->visited[w->e[i].z-1]==1&&vp->visited[w->e[i].y-1]==1>return4;}voidCreate_TLGraph<WGraph*w,ALGraph*G>{WGraphT;inti,j,t,h,k=2;intm=1;intabc,bcd;structvisit*vp;vp=<structvisit*>malloc<sizeof<structvisit>>;for<i=0;i<<G->n>;i++>{vp->visited[i]=-1;vp->position[i]=-1;vp->vvpp[i][0]=i+1;for<j=1;j<G->n;j++>vp->vvpp[i][j]=0;}T.v[0]=w->v[w->e[0].z-1];T.v[1]=w->v[w->e[0].y-1];vp->visited[w->e[0].z-1]=1;vp->position[w->e[0].z-1]=w->e[0].z;for<j=0;j<<G->n>;j++>if<vp->vvpp[w->e[0].z-1][j]==0>{vp->vvpp[w->e[0].z-1][j]=w->e[0].y;break;}vp->visited[w->e[0].y-1]=1;vp->position[w->e[0].y-1]=w->e[0].z;T.e[0].info=w->e[0].info;T.e[0].z=w->e[0].z;T.e[0].y=w->e[0].y;for<i=1;i<<G->e>;i++>{t=judge_vertex<w,i,vp>;if<t==4>{if<vp->position[w->e[i].z-1]==vp->position[w->e[i].y-1]>continue; else{abc=0;bcd=0; for<j=0;j<G->n;j++> if<vp->vvpp[vp->position[w->e[i].y-1]-1][j]!=0> abc++; for<j=0;j<G->n;j++> if<vp->vvpp[vp->position[w->e[i].z-1]-1][j]!=0> bcd++; for<j=bcd,h=0;j<G->n&&h<abc;j++,h++> {vp->vvpp[<vp->position[w->e[i].z-1]>-1][j]=vp->vvpp[<vp->position[w->e[i].y-1]>-1][h];vp->vvpp[vp->position[w->e[i].y-1]-1][h]=0; } for<h=bcd;h<abc+bcd;h++> vp->position[<vp->vvpp[vp->position[w->e[i].z-1]-1][h]>-1]=vp->position[w->e[i].z-1]; T.e[m].info=w->e[i].info;T.e[m].z=w->e[i].z;T.e[m].y=w->e[i].y;m++; }}elseif<t==1> {vp->visited[w->e[i].z-1]=1; vp->visited[w->e[i].y-1]=1; T.v[k++]=w->v[w->e[i].z-1]; T.v[k++]=w->v[w->e[i].y-1];T.e[m].info=w->e[i].info;T.e[m].z=w->e[i].z;T.e[m].y=w->e[i].y;m++; vp->position[w->e[i].z-1]=w->e[i].z;vp->position[w->e[i].y-1]=w->e[i].z; vp->vvpp[w->e[i].z-1][1]=w->e[i].y; vp->vvpp[w->e[i].y-1][0]=0;}elseif<t==2>{vp->visited[w->e[i].z-1]=1;vp->position[w->e[i].z-1]=vp->position[w->e[i].y-1];for<j=0;j<<G->n>;j++> if<vp->vvpp[vp->position[w->e[i].y-1]-1][j]==0> {vp->vvpp[vp->position[w->e[i].y-1]-1][j]=w->e[i].z; break; } vp->vvpp[w->e[i].z-1][0]=0; T.v[k++]=w->v[w->e[i].z-1]; T.e[m].info=w->e[i].info;T.e[m].z=w->e[i].z;T.e[m].y=w->e[i].y;m++;}elseif<t==3>{vp->visited[w->e[i].y-1]=1;vp->position[w->e[i].y-1]=vp->position[w->e[i].z-1];for<j=0;j<<G->n>;j++> if<vp->vvpp[vp->position[w->e[i].z-1]-1][j]==0> {vp->vvpp[vp->position[w->e[i].z-1]-1][j]=w->e[i].y; break; } vp->vvpp[w->e[i].y-1][0]=0; T.v[k++]=w->v[w->e[i].y-1]; T.e[m].info=w->e[i].info;T.e[m].z=w->e[i].z;T.e[m].y=w->e[i].y;m++; }}printf<"Pleaseoutputtheinformation:\n">;for<i=0;i<<G->n>-1;i++>printf<"<%c,%c>\n",T.e[i].z+64,T.e[i].y+64>;}voidCreate_WLGraph<ALGraph*G>{inti,j,t,m,k=0;EdgeNode*s,*p;WGraph*W;W=<WGraph*>malloc<sizeof<WGraph>>;W->v[0]=G->adjlist[0].vertex;s=G->adjlist[0].firstedge;while<s!=NULL>{W->e[k].z=1;W->e[k].y=s->adjvex;W->e[k].info=s->info;k++;s=s->next;}for<i=1;i<<G->n>;i++>{W->v[i]=G->adjlist[i].vertex;s=G->adjlist[i].firstedge;while<s!=NULL>{m=Panduan_Vertex<k,i,W,s>;if<m==1>{s=s->next;continue;}else{W->e[k].z=i+1;W->e[k].y=s->adjvex;W->e[k].info=s->info;k++;s=s->next;}}}/*printf<"Pleaseoutputtheinformation:\n">;for<i=0;i<G->n;i++>printf<"%c\n",W->v[i]>;for<i=0;i<G->e;i++>printf<"%d,%d,%.1f\n",W->e[i].z,W->e[i].y,W->e[i].info>;*/select_info<W,G>;Create_TLGraph<W,G>;}主函數的偽碼：main<>{ALGraph*G;G=<ALGraph*>malloc<sizeof<ALGraph>>;Create_ALGraph<G>;Create_WLGraph<G>;}5.函數調用關系：五．調試分析1.出現問題及解決方法：在剛開始寫程序時,由于考慮不全面,在去除連通圖閉合回路的算法中遇到很大困難,后來采用以下方法解決了這個問題：將每個頂點分別放在一個結構體中,結構體中的數組visited[i]記錄頂點Vi是否被訪問過的情況,position[i]記錄頂點Vi的具體位置,二維數組vvpp[i][j]記錄已經將以該頂點為左頂點或右頂點的權值存入T中后,該權值的右頂點或左頂點的編號。其具體思想是：只要將一個權值存入T中,就將相應的左右頂點放到同一個二維數組中,之后每欲將一個權值加入T中,先檢驗該權值的兩頂點是否在同一個二維數組中。若不在,則將該權值存入T中；若在,將該權值舍去〔因為再將該權值加入T中,就會出現回路。方法優缺點分析：優點：=1\*GB3①思想比較簡單,容易令人理解；=2\*GB3②在寫核心算法時,先將字母頂點用相應的數字代替,所以在將數字轉化成字母回去時,利用數字與ASCII碼值的固定差值,可以保證用戶在輸入時的大小寫字母都可以被該程序識別。缺點：由于采用數字來代替字母,中間的轉換關系比較復雜,尤其是將對應關系理清需要足夠的耐心和細心。3．主要算法的時間和空間復雜度分析：〔1由于Create_ALGraph<>算法中將讀入頂點的操作執行了n次,讀入邊的操作執行了2m次,故其時間復雜度為O〔n+2m；〔2由于Create_WLGraph<>算法將讀入權值及其左右頂點的操作執行了n次,故其時間復雜度為O〔n；〔3由于Create_TLGraph<>算法中根據判斷是否構成回路來取舍邊,因為有n條邊,故要執行n次,所以時間復雜度是O〔n；〔4由于select_info<>函數采用簡單選擇法排序,時間復雜度是O〔；〔5所有算法的空間復雜度都是O〔1。六．使用說明程序運行后,用戶根據提示輸入頂點數,邊數,頂點信息,邊的信息,權值,輸入完畢后程序會自動以頂點對〔i,j的形式輸出最小生成樹的邊。七．調試結果輸入數據："9","15","ABCDEFGHI","A,B","32.8","A,C","44.6","A,H","12.1","A,I","18.2","B,A","32.8","B,C","5.9","C,A","44.6","C,B","5.9","C,D","21.3","C,E","41.1","C,G","56.4","D,C","21.3","D,E","67.3","D,F","98.7","E,C","41.1","E,D","67.3","E,F","85.6","E,G","10.5","F,D","98.7","F,E","85.6","F,I","79.2","G,C","56.4","G,E","10.5","G,H","52.5","H,A","12.1","H,G","52.5","H,I","8.7","I,A","18.2","I,F","79.2","I,H","8.7"。<雙引號不需輸入>輸出數據：<B,C>,<H,I>,<E,G>,<A,H>,<C,D>,<A,B>,<C,E>,<F,I>運行結果截屏：八．附錄源程序清單：#include<stdio.h>/*調用的頭文件庫說明*/#include<stdlib.h>#defineMaxVerNum100staticvoidforcefloat<float*p>{floatf=*p;/*由于我的TC中不支持浮點數,故添加了這個程序段*/forcefloat<&f>;}typedefstructnode/*構造鄰接表的結構體*/{intadjvex;floatinfo;/*存放權值*/structnode*next;/*指向下一個鄰接點的指針域*/}EdgeNode;typedefstructvnode/*構造頂點表的結構體*/{charvertex;/*頂點域*/EdgeNode*firstedge;/*邊表頭指針*/}VertexNode;typedefVertexNodeAdjList[MaxVerNum];typedefstruct/*構造圖的結構體*/ {AdjListadjlist;/*鄰接表*/ intn,e;/*頂點數和邊數*/ }ALGraph;structbian/*存放權值及其左右頂點的結構體*/{intz,y;floatinfo;};typedefstruct/*用該結構體來只存放一次權值及其相應的頂點*/{charv[MaxVerNum];structbiane[MaxVerNum];}WGraph;structvisit/*用該結構體來存放各結點被訪問的情況,{visited[MaxVerNum];位置,和其他結點的關系*/position[MaxVerNum];vvpp[MaxVerNum][MaxVerNum];}Create_ALGraph<ALGraph*G>/*創建圖*/{inti,j;charp,q;intk;EdgeNode*s;chara,b;printf<"Pleaseinputtheverticesandtheedges<n,e>:\n">;/*輸入頂點數和邊數*/scanf<"%d,%d",&<G->n>,&<G->e>>;printf<"Pleaseinputtheinformationofthevertices<v>:\n">;getchar<>;for<i=0;i<<G->n>;i++>/*建立有n各頂點的頂點表*/{scanf<"%c",&<G->adjlist[i].vertex>>;/*讀入頂點信息*/G->adjlist[i].firstedge=NULL;}for<k=0;k<2*<G->e>;k++>/*建立邊表*/{printf<"Pleaseinputtheinformationofedges<p,q>:\n">;getchar<>;scanf<"%c,%c",&p,&q>;/*讀入邊的頂點*/s=<EdgeNode*>malloc<sizeof<EdgeNode>>;s->adjvex=q-64;/*鄰接點的序號為q-64*/i=p-64;getchar<>;printf<"Pleaseinputtheinformationofweight:\n">;/*讀入權值*/scanf<"%f",&<s->info>>;s->next=G->adjlist[i-1].firstedge;/*將新邊表結點s插入到頂點Vi的邊表頭部*/G->adjlist[i-1].firstedge=s;}}intPanduan_Vertex<intk,inti,WGraph*w,EdgeNode*s>/*判斷該邊是不是已經讀入到w指{intt;向的結構體中*/for<t=0;t<k;t++>if<<w->e[t]>.y==i+1&&<w->e[t]>.z==s->adjvex>return1;return0;}voidselect_info<WGraph*W,ALGraph*G>/*將w指向的結構體中各權值按升序{inti,j,p,k;排列*/floatt;for<i=0;i<<G->e>;i++>/*簡單選擇排序*/{p=i;for<j=i+1;j<<G->e>;j++>if<W->e[j].info<W->e[p].info>p=j;if<p!=i>{t=W->e[p].info;/*將兩條邊的權值左右頂點都進行交換*/W->e[p].info=W->e[i].info;W->e[i].info=t;k=W->e[p].z;W->e[p].z=W->e[i].z;W->e[i].z=k;k=W->e[p].y;W->e[p].y=W->e[i].y;W->e[i].y=k;}}/*for<i=0;i<<G->e>;i++>printf<"%.1f",W->e[i].info>;printf<"\n">;*/}intjudge_vertex<WGraph*w,inti,structvisit*vp>/*判斷頂點的訪問情況*/{if<vp->visited[w->e[i].z-1]==-1&&vp->visited[w->e[i].y-1]==-1>return1;elseif<vp->visited[w->e[i].z-1]==-1&&vp->visited[w->e[i].y-1]==1>return2;elseif<vp->visited[w->e[i].y-1]==-1&&vp->visited[w->e[i].z-1]==1>return3;elseif<vp->visited[w->e[i].z-1]==1&&vp->visited[w->e[i].y-1]==1>return4;}voidCreate_TLGraph<WGraph*w,ALGraph*G>/*生成最小生成樹*/{WGraphT;inti,j,t,h,k=2;intm=1;intabc,bcd;structvisit*vp;vp=<structvisit*>malloc<sizeof<structvisit>>;for<i=0;i<<G->n>;i++>/*將各頂點的被訪問情況,位置,與其他頂點{vp->visited[i]=-1;的相互關系進行初始化*/vp->position[i]=-1;vp->vvpp[i][0]=i+1;for<j=1;j<G->n;j++>vp->vvpp[i][j]=0;}T.v[0]=w->v[w->e[0].z-1];T.v[1]=w->v[w->e[0].y-1];vp->visited[w->e[0].z-1]=1;vp->position[w->e[0].z-1]=w->e[0].z;for<j=0;j<<G->n>;j++>if<vp->vvpp[w->e[0].z-1][j]==0>{vp->vvpp[w->e[0].z-1][j]=w->e[0].y;break;}vp->visited[w->e[0].y-1]=1;vp->position[w->e[0].y-1]=w->e[0].z;T.e[0].info=w->e[0].info;T.e[0].z=w->e[0].z;T.e[0].y=w->e[0].y;for<i=1;i<<G->e>;i++>{t=judge_vertex<w,i,vp>;/*根據不同的頂點訪問情況選取相應操作*/if<t==4>/*兩頂點均已被訪問過的情況*/{if<vp->position[w->e[i].z-1]==vp->position[w->e[i].y-1]>/*兩頂點位置相同*/continue;/*舍去這條邊,否則會構成回路*/ else{abc=0;bcd=0;/*倘若兩頂點位置不同*/ for<j=0;j<G->n;j++> if<vp->vvpp[vp->position[w->e[i].y-1]-1][j]!=0> abc++; for<j=0;j<G->n;j++> if<vp->vvpp[vp->position[w->e[i].z-1]-1][j]!=0> bcd++; for<j=bcd,h=0;j<G->n&&h<abc;j++,h++>將兩頂點放在同一個數組中*/ {vp->vvpp[<vp->position[w->e[i].z-1]>-1][j]=vp->vvpp[<vp->position[w->e[i].y-1]>-1][h];vp->vvpp[vp->position[w->e[i].y-1]-1][h]=0;/*將原數組置零*/ } for<h=bcd;h<abc+bcd;h++> vp->position[<vp->vvpp[vp->position[w->e[i].z-1]-1][h]>-1]=vp->position[w->e[i].z-1]; T.e[m].info=w->e[i].info;/*將該邊存入T中*/T.e[m].z=w->e[i].z;T.e[m].y=w->e[i].y;m++; }}elseif<t==1>/*兩頂點都未被訪問的情況*/ {vp->visited[w->e[i].z-1]=1; vp->visited[w->e[i].y-1]=1; T.v[k++]=w->v[w->e[i].z-1]; T.v[k++]=w->v[w->e[i].y-1];T.e[m].info=w->e[i].info;/*將該邊存入T中*/T.e[m].z=w->e[i].z;T.e[m].y=w->e[i].y;m++; vp->position[w->e[i].z-1]=w->e[i].z;/*將兩頂點的位置改為相同*/vp->position[w->e[i].y-1]=w->e[i].z; vp->vvpp[w->e[i].z-1][1]=w->e[i].y;/*將兩頂點存放到一個數組中*/ vp->vvpp[w->e[i].y-1][0]=0;}elseif<t==2>/*左頂點未被訪問,右頂點已被訪問的情況*/{vp->visited[w->e[i].z-1]=1;vp->position[w->e[i].z-1]=vp->position[w->e[i].y-1];/*將左頂點的位置改為右頂點的位置*/for<j=0;j<<G->n>;j++>/*將兩頂點存放到一個數組中*/ if<vp->vvpp[vp->position[w->e[i].y-1]-1][j]==0> {vp->vvpp[vp->position[w->e[i].y-1]-1][j]=w->e[i].z; break; } vp->vvpp[w->e[i].z-