管道鋪設(shè)問(wèn)題

1、實(shí)驗(yàn)三：管道鋪設(shè)施工的最佳方案一問(wèn)題描述1.實(shí)驗(yàn)題目：需要在某個(gè)城市n個(gè)居民小區(qū)之間鋪設(shè)煤氣管道，則在這n個(gè)居民小區(qū)之間只需要鋪設(shè)n-1條管道鋪設(shè)n-1條管道即可。假設(shè)任意兩個(gè)小區(qū)之間則可以鋪設(shè)管道，但由于地理環(huán)境不同，所需要的費(fèi)用也不盡相同。選擇最優(yōu)的方案能使總投資盡可能小，這個(gè)問(wèn)題即為求無(wú)向網(wǎng)的最小生成樹(shù)。2. 基本要求： 在可能假設(shè)的m條管道中，選取n-1條管道，使得既能連通n個(gè)小區(qū)，又能使總投資最小。每條管道的費(fèi)用以網(wǎng)中該邊的權(quán)值形式給出，網(wǎng)的存儲(chǔ)采用鄰接表的結(jié)構(gòu)。3. 測(cè)試數(shù)據(jù)： 使用下圖給出的無(wú)線網(wǎng)數(shù)據(jù)作為程序的輸入，求出最佳鋪設(shè)方案。參考解：二需求分析1.程序所能達(dá)到的基本可能：

2、在某個(gè)城市n個(gè)居民小區(qū)之間鋪設(shè)煤氣管道，則在這n個(gè)居民小區(qū)之間只需要鋪設(shè)n-1條管道鋪設(shè)n-1條管道即可。假設(shè)任意兩個(gè)小區(qū)之間則可以鋪設(shè)管道，但由于地理環(huán)境不同，所需要的費(fèi)用也不盡相同。選擇最優(yōu)的方案能使總投資盡可能小，在可能假設(shè)的m條管道中，選取n-1條管道，使得既能連通n個(gè)小區(qū)，又能使總投資最小。2.輸入輸出形式及輸入值范圍：程序運(yùn)行后，顯示提示信息：請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)（輸入格式為：頂點(diǎn)數(shù),邊數(shù)）之后程序從文件名為”C:data.txt讀入頂點(diǎn)信息和邊的信息，之后顯示提示信息輸入開(kāi)始節(jié)點(diǎn)，執(zhí)行生成最小樹(shù)程序，輸出生成的最小樹(shù)信息。3.測(cè)試數(shù)據(jù)要求：頂點(diǎn)數(shù)邊數(shù)為整數(shù)，頂點(diǎn)信息為大寫(xiě)字母，邊的

3、權(quán)值為浮點(diǎn)型，C:data.txt文件內(nèi)容為：ABCDEFGHI1 2 32.8 2 3 5.9 1 3 44.6 3 4 21.3 4 5 67.3 4 6 98.7 5 6 85.6 5 7 10.5 3 7 56.4 6 9 79.2 7 8 52.5 1 8 12.1 8 9 8.7 1 9 18.2 3 5 41.1三概要設(shè)計(jì)1. 所用到得數(shù)據(jù)結(jié)構(gòu)及其ADT typedef struct node /邊表結(jié)點(diǎn)int NO; /鄰接點(diǎn)域; vertexType adjvex;EdgeType info; /權(quán)值struct node *next; /指向下一個(gè)鄰接點(diǎn)的指針域EdgeNo

4、de;typedef struct vnode /頂點(diǎn)表節(jié)點(diǎn)vertexType vertex; /頂點(diǎn)域EdgeNode *firstedge; /編表頭指針VertexNode;typedef struct /鄰接表 VertexNode adjlistMaxVertexNum;int n,e; /頂點(diǎn)數(shù)和邊數(shù)ALGraph; / ALGraph是以鄰接表方式存儲(chǔ)的圖類(lèi)型基本操作：ALGraph * CreateALGraph() /建表2. 主程序流程及其模塊調(diào)用關(guān)系 1) 主程序模塊建表模塊ALGraph * CreateALGraph() 最小生成樹(shù)模塊void tree(ALGra

5、ph *G,int m) 函數(shù)調(diào)用關(guān)系圖 四、 詳細(xì)設(shè)計(jì) 1. 實(shí)現(xiàn)每個(gè)操作的偽碼，重點(diǎn)語(yǔ)句加注釋 1）建表模塊ALGraph * CreateALGraph() /建表int i,j,k;float m;FILE *fp;EdgeNode *s,*t;ALGraph *G;fp=fopen("C:data.txt","r");/打開(kāi)文件if(fp=NULL)/未找到文件printf("Cann't open the file!n");exit(1); G=(ALGraph *)malloc(sizeof(ALGraph);p

6、rintf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)（輸入格式為：頂點(diǎn)數(shù),邊數(shù)）n");scanf("%d,%d",&G->n,&G->e);for(i=1;i<=G->n;i+)/建立頂點(diǎn)信息 G->adjlisti.vertex=fgetc(fp);G->adjlisti.firstedge=NULL;visitedi=i;for(k=1;k<=G->e;k+) /printf("請(qǐng)輸入第%d條邊的兩個(gè)端點(diǎn)序號(hào)，輸入格式為：i,jn",k);/scanf("%d,%d"

7、;,&i,&j);fscanf(fp,"%d",&i);fscanf(fp,"%d",&j);s=(EdgeNode *)malloc(sizeof(EdgeNode);t=(EdgeNode *)malloc(sizeof(EdgeNode); /printf("請(qǐng)輸入第%d條邊的對(duì)應(yīng)權(quán)值n",k);fscanf(fp,"%f",&m);/保存邊信息，以無(wú)向網(wǎng)方式s->NO=j;s->adjvex=G->adjlistj.vertex; s->inf

8、o=m;s->next=G->adjlisti.firstedge;G->adjlisti.firstedge=s;t->NO=i;t->adjvex=G->adjlisti.vertex; t->info=m;t->next=G->adjlistj.firstedge;G->adjlistj.firstedge=t;fclose(fp);/關(guān)閉文件return G;2）生成最小生成樹(shù)模塊 void tree(ALGraph *G,int m)float low100;int teed100;int k,i,j;float min,s

9、um=0;EdgeNode *s;lowm=0;visitedm=0; for(i=1;i<=G->n;i+)lowi=1000;teedi=m; s=G->adjlistm.firstedge; while(s!=NULL)/數(shù)組初始化 lows->NO=s->info;s=s->next; for(i=1;i<G->n;i+) min=1000; for(j=1;j<=G->n;j+) if(visitedj>0&&lowj<min)/找到最小權(quán)值 min=lowj; k=j;/標(biāo)記節(jié)點(diǎn) sum+=mi

10、n;visitedk=0;s=G->adjlistk.firstedge;while(s!=NULL)if(visiteds->NO>0&&s->info<lows->NO)/找到最小權(quán)值lows->NO=s->info;teeds->NO=k;s=s->next; printf("最佳鋪設(shè)方案n"); for(i=1;i<=G->n;i+)/輸出最小生成樹(shù)信息 if(i!=m) printf("(%d,%d)%.2ft",i,teedi,lowi); printf(

11、"最小權(quán)值為:%.2fn",sum);3） 主函數(shù)模塊 void main() ALGraph *G;int i;time_t rawtime;struct tm * timeinfo; time (&rawtime);timeinfo = localtime (&rawtime); printf(" 實(shí)驗(yàn)名稱(chēng)：實(shí)驗(yàn)三：管道鋪設(shè)施工的最佳方案n");printf(" 學(xué)號(hào)：031350102n"); printf(" 姓名：王亞文n"); printf("=n");printf(

12、"程序運(yùn)行開(kāi)始，");printf("Current local time and date:%s",asctime(timeinfo);G=CreateALGraph();/建表printf("輸入開(kāi)始節(jié)點(diǎn)n");scanf("%d",&i); tree(G,i);/生成最小樹(shù)/printfALGraph(G); printf("n");printf("Current local time and date:%s",asctime(timeinfo);五、 調(diào)試分析

13、 1. 設(shè)計(jì)與調(diào)試過(guò)程中遇到的問(wèn)題分析、體會(huì) 1）一開(kāi)始對(duì)文件讀寫(xiě)操作不熟，采用從鍵盤(pán)輸出的方式驗(yàn)證正確與否，對(duì)應(yīng)程序如下：int i,j,k;float m;EdgeNode *s,*t;ALGraph *G; G=(ALGraph *)malloc(sizeof(ALGraph);printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)（輸入格式為：頂點(diǎn)數(shù),邊數(shù)）n");scanf("%d,%d",&G->n,&G->e);for(i=1;i<=G->n;i+)/建立頂點(diǎn)信息 G->adjlisti.vertex=fgetc(

14、fp);G->adjlisti.firstedge=NULL;visitedi=i;for(k=1;k<=G->e;k+) printf("請(qǐng)輸入第%d條邊的兩個(gè)端點(diǎn)序號(hào)，輸入格式為：i,jn",k); scanf("%d,%d",&i,&j);s=(EdgeNode *)malloc(sizeof(EdgeNode);t=(EdgeNode *)malloc(sizeof(EdgeNode); printf("請(qǐng)輸入第%d條邊的對(duì)應(yīng)權(quán)值n",k);scanf("%f",&

15、m);/保存邊信息，以無(wú)向網(wǎng)方式s->NO=j;s->adjvex=G->adjlistj.vertex; s->info=m;s->next=G->adjlisti.firstedge;G->adjlisti.firstedge=s;t->NO=i;t->adjvex=G->adjlisti.vertex; t->info=m;t->next=G->adjlistj.firstedge;G->adjlistj.firstedge=t;return G;對(duì)應(yīng)截屏如下：發(fā)現(xiàn)這種方式輸入耗時(shí)長(zhǎng)，而且在生成樹(shù)程序不正

16、確時(shí)修改程序需要重復(fù)輸入，較為麻煩2）為檢驗(yàn)所建立的無(wú)向網(wǎng)，編寫(xiě)了一個(gè)輸出函數(shù)，輸出各個(gè)頂點(diǎn)以及與該頂點(diǎn)相鄰的其他頂點(diǎn)以及對(duì)應(yīng)權(quán)值，輸出函數(shù)為void printfALGraph(ALGraph *G) /輸出表int i;EdgeNode *s;printf("輸出信息n"); for(i=1;i<=G->n;i+)printf("%c的鄰接點(diǎn)及權(quán)值:n",G->adjlisti.vertex);s=G->adjlisti.firstedge;while(s!=NULL)printf("%c %.2f ",s

17、->adjvex,s->info);s=s->next;printf("n");輸出測(cè)試截屏如下證明從文件讀寫(xiě)的與所需要建立的無(wú)向網(wǎng)相符2. 主要算法的時(shí)間復(fù)雜度分析 六、 使用說(shuō)明程序運(yùn)行后，顯示提示信息：請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)（輸入格式為：頂點(diǎn)數(shù),邊數(shù)）之后程序從文件名為”C:data.txt讀入頂點(diǎn)信息和邊的信息，之后顯示提示信息輸入開(kāi)始節(jié)點(diǎn)，執(zhí)行生成最小樹(shù)程序，輸出生成的最小樹(shù)信息。七、 測(cè)試結(jié)果 3） 這個(gè)程序遇到的第一個(gè)主要問(wèn)題是在建表過(guò)程，因?yàn)檫叺捻旤c(diǎn)信息是大寫(xiě)英文字母，一開(kāi)始我是用的ASCLL碼值，使用不方便，后來(lái)采用在定義時(shí)考慮多定義一個(gè)量，

18、原程序：typedef struct node /邊表結(jié)點(diǎn)vertexType adjvex; /鄰接點(diǎn)域; EdgeType info; /權(quán)值struct node *next; /指向下一個(gè)鄰接點(diǎn)的指針域EdgeNode;修正后的程序?yàn)椋簍ypedef struct node /邊表結(jié)點(diǎn)int NO; /鄰接點(diǎn)域; vertexType adjvex;EdgeType info; /權(quán)值struct node *next; /指向下一個(gè)鄰接點(diǎn)的指針域EdgeNode;這樣多定義了一個(gè)量在后面的過(guò)程中會(huì)簡(jiǎn)單許多，其次書(shū)上給的程序是生成有向網(wǎng)的， 一開(kāi)始我是考慮的將邊輸入兩邊，就是在循環(huán)時(shí)的

19、終止條件設(shè)為k<=2*G->e；這樣雖然能解決無(wú)向網(wǎng)問(wèn)題，但是一條邊重復(fù)輸入兩邊，較為麻煩，后期修正為：s->NO=j;s->adjvex=G->adjlistj.vertex; s->info=m;s->next=G->adjlisti.firstedge;G->adjlisti.firstedge=s;t->NO=i;t->adjvex=G->adjlisti.vertex; t->info=m;t->next=G->adjlistj.firstedge;G->adjlistj.firstedg

20、e=t;修正后的函數(shù)雖然語(yǔ)句較之前的多了5句但在輸入時(shí)少輸了一半的邊信息。其次解決耗時(shí)最長(zhǎng)的一個(gè)錯(cuò)誤是在建表中，原程序：typedef VertexNode AdjlistMaxVertexNum;typedef struct /鄰接表Adjlist adjlist; /int n,e; /頂點(diǎn)數(shù)和邊數(shù)int n;int e;ALGraph; / ALGraph是以鄰接表方式存儲(chǔ)的圖類(lèi)型這個(gè)程序是抄的書(shū)上的，一開(kāi)始不覺(jué)得書(shū)上的程序會(huì)是錯(cuò)的，結(jié)果一直沒(méi)有看這個(gè)定義，在輸入邊的信息時(shí)循環(huán)次數(shù)總是不對(duì)，一直嘗試著改動(dòng)寫(xiě)的輸入信息，弄了一下午也沒(méi)有搞定這個(gè)問(wèn)題，于是去求助研究生學(xué)長(zhǎng)，下面是研究生學(xué)長(zhǎng)發(fā)

21、過(guò)來(lái)的郵件幫我指出錯(cuò)誤所在，看了學(xué)長(zhǎng)的這封郵件后，重新改了一下自己的程序，修正后的程序?yàn)閠ypedef struct /鄰接表 VertexNode adjlistMaxVertexNum;int n,e; /頂點(diǎn)數(shù)和邊數(shù)ALGraph; / ALGraph是以鄰接表方式存儲(chǔ)的圖類(lèi)型程序修正后輸入正常了，就開(kāi)始進(jìn)入下一個(gè)階段生成最小樹(shù)的程序。3） 在生成最小樹(shù)這個(gè)程序的編寫(xiě)中，開(kāi)始因?yàn)榫幊绦蚴窃诶蠋熤v解生成樹(shù)之前，所以一開(kāi)始是完全沒(méi)有地方下手，網(wǎng)上百度了一下如何生成最小樹(shù)，發(fā)現(xiàn)有兩種方法，Kruskal和prim算法，但研究生學(xué)長(zhǎng)這個(gè)適合用prim算法，Kruskal算法適合與邊稀疏的連通圖求

22、解最小生成樹(shù)，所以在編寫(xiě)時(shí)主要研究的是用prim算法，在編寫(xiě)prim算法時(shí)除了很多問(wèn)題，例如一開(kāi)始我并沒(méi)有在循環(huán)中寫(xiě)teedi=m;這句話，導(dǎo)致在最后輸出邊的信息時(shí)會(huì)有隨機(jī)數(shù)產(chǎn)生，截圖如下：想到隨機(jī)數(shù)產(chǎn)生可能是因?yàn)闆](méi)有賦值，所以加上teedi=m;這句話果然最后就輸出正確了，再次在輸出時(shí)，產(chǎn)生的結(jié)果中有重復(fù)的一個(gè)節(jié)點(diǎn)，<1,1>1000.00這個(gè)不應(yīng)該被輸出，所以考慮在輸出時(shí)加一個(gè)限制條件if(i!=m)再次輸出就沒(méi)有了，中間編寫(xiě)時(shí)問(wèn)題不大，之前有看過(guò)prim算法的詳細(xì)介紹，所以在主思路上沒(méi)有太大的錯(cuò)誤，相對(duì)寫(xiě)起來(lái)也比較順利。2） 建立鄰接表的復(fù)雜度為O(n+e); Prim算法的

23、時(shí)間復(fù)雜度為O(elogn);八、 附錄 #include <stdio.h> #include <malloc.h> #include <stdlib.h> #include <time.h> /輸入序號(hào)與字母對(duì)應(yīng)關(guān)系A(chǔ)-1,B-2，C-3，D-4，E-5，F(xiàn)-6，G-7，H-8，I-9#define MaxVertexNum 100typedef char vertexType;typedef float EdgeType;int visited100;/訪問(wèn)變量，為一時(shí)表示未訪問(wèn)typedef struct node /邊表結(jié)點(diǎn)int NO

24、; /鄰接點(diǎn)域; vertexType adjvex;EdgeType info; /權(quán)值struct node *next; /指向下一個(gè)鄰接點(diǎn)的指針域EdgeNode;typedef struct vnode /頂點(diǎn)表節(jié)點(diǎn)vertexType vertex; /頂點(diǎn)域EdgeNode *firstedge; /編表頭指針VertexNode;typedef struct /鄰接表 VertexNode adjlistMaxVertexNum;int n,e; /頂點(diǎn)數(shù)和邊數(shù)ALGraph; / ALGraph是以鄰接表方式存儲(chǔ)的圖類(lèi)型ALGraph * CreateALGraph() /建

25、表int i,j,k;float m;FILE *fp;EdgeNode *s,*t;ALGraph *G;fp=fopen("C:data.txt","r");/打開(kāi)文件if(fp=NULL)/未找到文件printf("Cann't open the file!n");exit(1); G=(ALGraph *)malloc(sizeof(ALGraph);printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)（輸入格式為：頂點(diǎn)數(shù),邊數(shù)）n");scanf("%d,%d",&G->n,&am

26、p;G->e);for(i=1;i<=G->n;i+)/建立頂點(diǎn)信息 G->adjlisti.vertex=fgetc(fp);G->adjlisti.firstedge=NULL;visitedi=i;for(k=1;k<=G->e;k+) /printf("請(qǐng)輸入第%d條邊的兩個(gè)端點(diǎn)序號(hào)，輸入格式為：i,jn",k);/scanf("%d,%d",&i,&j);fscanf(fp,"%d",&i);fscanf(fp,"%d",&j);s

27、=(EdgeNode *)malloc(sizeof(EdgeNode);t=(EdgeNode *)malloc(sizeof(EdgeNode); /printf("請(qǐng)輸入第%d條邊的對(duì)應(yīng)權(quán)值n",k);fscanf(fp,"%f",&m);/保存邊信息，以無(wú)向網(wǎng)方式s->NO=j;s->adjvex=G->adjlistj.vertex; s->info=m;s->next=G->adjlisti.firstedge;G->adjlisti.firstedge=s;t->NO=i;t->

28、adjvex=G->adjlisti.vertex; t->info=m;t->next=G->adjlistj.firstedge;G->adjlistj.firstedge=t;fclose(fp);/關(guān)閉文件return G;void tree(ALGraph *G,int m)float low100;int teed100;int k,i,j;float min,sum=0;EdgeNode *s;lowm=0;visitedm=0; for(i=1;i<=G->n;i+)lowi=1000;teedi=m; s=G->adjlistm

29、.firstedge; while(s!=NULL)/數(shù)組初始化 lows->NO=s->info;s=s->next; for(i=1;i<G->n;i+) min=1000; for(j=1;j<=G->n;j+) if(visitedj>0&&lowj<min)/找到最小權(quán)值 min=lowj; k=j;/標(biāo)記節(jié)點(diǎn) sum+=min;visitedk=0;s=G->adjlistk.firstedge;while(s!=NULL)if(visiteds->NO>0&&s->inf

30、o<lows->NO)/找到最小權(quán)值lows->NO=s->info;teeds->NO=k;s=s->next; printf("最佳鋪設(shè)方案n"); for(i=1;i<=G->n;i+)/輸出最小生成樹(shù)信息 if(i!=m) printf("(%d,%d)%.2ft",i,teedi,lowi); printf("最小權(quán)值為:%.2fn",sum);/*void printfALGraph(ALGraph *G) /輸出表int i;EdgeNode *s;printf("

31、;輸出信息n"); for(i=1;i<=G->n;i+)printf("%c的鄰接點(diǎn)及權(quán)值:n",G->adjlisti.vertex);s=G->adjlisti.firstedge;while(s!=NULL)printf("%c %.2f ",s->adjvex,s->info);s=s->next;printf("n");*/void main() ALGraph *G;int i;time_t rawtime;struct tm * timeinfo; time (&rawtime);timeinfo = localtime (&rawtime); printf(" 實(shí)驗(yàn)名稱(chēng)：實(shí)驗(yàn)三：管道鋪設(shè)施工的最佳方案n");printf(" 學(xué)號(hào)：031350102n"); printf(" 姓名：王亞文n"); printf("=n");printf("程序運(yùn)行開(kāi)始，");printf("Current local time and date:%s",asctime(