C語言及程序設(shè)計(jì)

1、數(shù)據(jù)結(jié)構(gòu)（C語言版）課程設(shè)計(jì) 學(xué) 院： 班 級(jí)：姓 名： 指導(dǎo)老師： 二一五年一月二十二日一、課程設(shè)計(jì)的題目校園網(wǎng)架設(shè)的方案與設(shè)計(jì)問題【問題描述】若要在揚(yáng)州大學(xué)的七個(gè)校區(qū)（江陽路南校區(qū)、江陽路北校區(qū)、瘦西湖校區(qū)、農(nóng)學(xué)院校區(qū)、工學(xué)院校區(qū)、水利學(xué)院校區(qū)、醫(yī)學(xué)院校區(qū)）之間架設(shè)校園網(wǎng)，如何以最低的經(jīng)濟(jì)代價(jià)架設(shè)這個(gè)校園網(wǎng)。并求出江陽路南校區(qū)到其他各校區(qū)之間的最短距離?！净疽蟆浚?）利用二種方法（Prim算法和克魯斯卡爾（Kruskual）算法生成校園網(wǎng)的架設(shè)方案。（2）利用迪杰斯特拉算法求出江陽路校區(qū)到其他各校區(qū)之間的最短距離。（3）寫出課程設(shè)計(jì)報(bào)告?！緶y(cè)試數(shù)據(jù)】對(duì)每種方法設(shè)定一組模擬測(cè)試數(shù)據(jù)進(jìn)行測(cè)

2、試，驗(yàn)證程序的正確性。二、課程設(shè)計(jì)的目的課程設(shè)計(jì)的目的是培養(yǎng)學(xué)生綜合程序設(shè)計(jì)的能力，訓(xùn)練學(xué)生靈活應(yīng)用所學(xué)數(shù)據(jù)結(jié)構(gòu)知識(shí)，獨(dú)立完成問題分析、總體設(shè)計(jì)、詳細(xì)設(shè)計(jì)和編程實(shí)現(xiàn)等軟件開發(fā)全過程的綜合實(shí)踐能力。鞏固、深化學(xué)生的理論知識(shí)，提高編程水平，并在此過程中培養(yǎng)他們嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度和良好的學(xué)習(xí)作風(fēng)。為今后學(xué)習(xí)其他計(jì)算機(jī)課程打下基礎(chǔ)。課程設(shè)計(jì)為學(xué)生提供了一個(gè)既動(dòng)手又動(dòng)腦，獨(dú)立實(shí)踐的機(jī)會(huì)，將書本上的理論知識(shí)和工作、生產(chǎn)實(shí)際有機(jī)地結(jié)合起來，從而鍛煉學(xué)生分析問題、解決實(shí)際問題的能力，提高學(xué)生的編程序能力和創(chuàng)新意識(shí)。三、分析系統(tǒng)的主要功能及用途在揚(yáng)州大學(xué)的七個(gè)校區(qū)（江陽路南校區(qū)、江陽路北校區(qū)、瘦西湖校區(qū)、農(nóng)學(xué)院校區(qū)

3、、工學(xué)院校區(qū)、水利學(xué)院校區(qū)、醫(yī)學(xué)院校區(qū)）之間架設(shè)校園網(wǎng)，所架設(shè)的校園網(wǎng)經(jīng)濟(jì)代價(jià)最低。并能計(jì)算出江陽路南校區(qū)到其他各校區(qū)之間的最短距離。四、分析和描述的基本要求1、基本要求（1）利用二種方法（Prim算法和克魯斯卡爾（Kruskual）算法生成校園網(wǎng)的架設(shè)方案。（2）利用迪杰斯特拉算法求出江陽路校區(qū)到其他各校區(qū)之間的最短距離。（3）寫出課程設(shè)計(jì)報(bào)告。2、程序包含模塊1） 主程序模塊，其中主函數(shù)為main() 初始化圖形界面； 讀入用戶選擇信息； 根據(jù)用戶選擇執(zhí)行相應(yīng)模塊； 關(guān)閉文件及圖形界面； ；2） 創(chuàng)建模塊實(shí)現(xiàn)將七個(gè)校區(qū)設(shè)計(jì)成無向圖G的創(chuàng)建；3） 普里姆模塊實(shí)現(xiàn)圖G的經(jīng)濟(jì)代價(jià)最低的校園網(wǎng)的架

4、設(shè)方案；4） 克魯斯卡爾模塊實(shí)現(xiàn)圖G的經(jīng)濟(jì)代價(jià)最低的校園網(wǎng)的架設(shè)方案；5） 迪杰斯特拉算法求最短距離模塊實(shí)現(xiàn)圖G從江陽路南校區(qū)（v0）到其它各校區(qū)的最短距離。3、模塊功能框圖主程序模塊創(chuàng)建模塊普里姆模塊克魯斯卡爾模塊迪杰斯特拉算法求最短距離模塊五、問題實(shí)現(xiàn)的主要算法與分析1、頂點(diǎn)、邊、圖和最小生成樹的邊類型#define MAX 20 /最大頂點(diǎn)數(shù)設(shè)為20#define INF 10000 /無窮設(shè)為32767typedef struct node int adjvex; /鄰接點(diǎn)struct node * next; /指向下一個(gè)鄰接點(diǎn)的指針域EdgeNode;typedef struct

5、vnode int vertex; /頂點(diǎn) int indegree; /入度 EdgeNode * firstedge; /邊表頭指針VertexNode;typedef VertexNode AdjListMAX; /adj_list是鄰接表類型typedef struct AdjList adjlist; /鄰接表 int vexnum,arcnum; /圖中頂點(diǎn)數(shù)和邊數(shù)ALGraph;typedef struct int vexsMAX; /定點(diǎn)表 int AdjMatrixMAXMAX; /鄰接矩陣 int vexnum,arcnum; /頂點(diǎn)數(shù)和邊數(shù)MGragh;typedef s

6、truct int begin,end; /邊頂點(diǎn)序號(hào) int cost; /邊上的權(quán)值TreeEdge;2、圖的基本操作void Create (void)/將七個(gè)校區(qū)設(shè)計(jì)成一個(gè)無向圖G，創(chuàng)建無向圖G的鄰接矩陣存儲(chǔ)void prim(void)/用Prim算法建立經(jīng)濟(jì)代價(jià)最低的校園網(wǎng)架設(shè)方案void Sort(void)/在G中選擇經(jīng)濟(jì)代價(jià)最低的校園網(wǎng)void Kruskal(int n)/用克魯斯卡爾算法求圖G的經(jīng)濟(jì)代價(jià)最低的校園網(wǎng)架設(shè)方案void ShortPath(int path,int i,int v0)/將源點(diǎn)設(shè)為v0（江陽路南校區(qū)）void Distance(int v0)/迪

7、杰斯特拉算法求無向網(wǎng)G的從江陽路南校區(qū)（v0）到其它各校區(qū)的最短距離3、函數(shù)調(diào)用關(guān)系mainCreate()()primsortKruskalShortPathDistance六、源程序 #include<stdio.h>#include<malloc.h>#define MAX 20#define INF 10000typedef struct nodeint adjvex;/鄰接點(diǎn)struct node * next;/指向下一個(gè)鄰接點(diǎn)的指針域EdgeNode;typedef struct vnodeint vertex;/頂點(diǎn)int indegree;/入度Edg

8、eNode * firstedge;/邊表頭指針VertexNode;typedef VertexNode AdjListMAX;/adj_list是鄰接表類型typedef structAdjList adjlist;/鄰接表int vexnum,arcnum;/圖中頂點(diǎn)數(shù)和邊數(shù)ALGraph;typedef struct int vexsMAX;/定點(diǎn)表 int AdjMatrixMAXMAX;/鄰接矩陣 int vexnum,arcnum;/頂點(diǎn)數(shù)和邊數(shù)MGragh;typedef struct int begin,end;/邊頂點(diǎn)序號(hào) int cost;/邊上的權(quán)值TreeEdge;M

9、Gragh G;void Create(void)/創(chuàng)建無向圖G的鄰接矩陣存儲(chǔ)FILE *f1;int i,j,k,x;f1=fopen("d:c.txt","r");fscanf(f1,"%d%d",&G.vexnum,&G.arcnum);for (i=0;i<G.vexnum;i+)for(j=0;j<G.vexnum;j+)G.AdjMatrixij=INF;for(k=0;k<G.arcnum;k+)fscanf(f1,"%d%d%d",&i,&j,&am

10、p;x);G.AdjMatrixij=x;G.AdjMatrixji=G.AdjMatrixij;fclose(f1);void prim(void) int n=G.vexnum;int lowerCostMAX,mincost=0,closeVertexMAX;TreeEdge closeMAX;int i,j,k,sum=0;for(i=1;i<n;i+) lowerCosti=G.AdjMatrix0i; closeVertexi=0; lowerCost0=0; closeVertex0=0;for(i=1;i<n;i+)mincost=INF; j=1;k=1;whil

11、e(j<n)if(lowerCostj!=0&&lowerCostj<mincost)mincost=lowerCostj;k=j;j+;closei-1.begin=closeVertexk;closei-1.end=k;closei-1.cost=mincost;sum=sum+mincost;lowerCostk=0;for(j=1;j<n;j+)if(G.AdjMatrixkj<lowerCostj)lowerCostj=G.AdjMatrixkj;closeVertexj=k; printf("校園網(wǎng)構(gòu)架方案如下所示：n")

12、; printf("n"); printf("始點(diǎn)終點(diǎn)兩校距離n"); for(i=0;i<n-1;i+) printf("n");printf("%4d%4d%8dn",closei.begin,closei.end,closei.cost); printf("n"); printf("校園網(wǎng)最低的經(jīng)濟(jì)代價(jià)總長為:%dn",sum);TreeEdge edgeMAX*MAX,treeMAX;void Sort(void)/在G中選擇經(jīng)濟(jì)代價(jià)最低的校園網(wǎng)int i,j,

13、k=0,p;TreeEdge temp; for(i=0;i<G.vexnum;i+) for(j=0;j<=i;j+) if(G.AdjMatrixij<INF) edgek.begin=i; edgek.end=j; edgek.cost=G.AdjMatrixij; k+; for(i=0;i<k-1;i+) p=i; for(j=i;j<k;j+) if(edgej.cost<edgep.cost) p=j; if(p!=i) temp=edgei; edgei=edgep; edgep=temp; void Kruskal(int n)int v=

14、0,j,k,sum=0; int cnvxMAX; for(j=0;j<n;j+) cnvxj=j; for(k=0;k<n-1;k+) while(cnvxedgev.begin=cnvxedgev.end) v+; treek=edgev; sum=sum+edgev.cost;for(j=0;j<n;j+)if(cnvxj=cnvxedgev.begin)cnvxj=cnvxedgev.end; v+;printf("校園網(wǎng)構(gòu)架方案如下所示：n"); printf("n"); printf("始點(diǎn)終點(diǎn)兩校距離n"

15、;);for(j=0;j<n-1;j+)printf("n");printf("%4d%4d%8dn",treej.end,treej.begin,treej.cost);printf("n");printf("校園網(wǎng)最低的經(jīng)濟(jì)代價(jià)總長為:%dn",sum);void ShortPath(int path,int i,int v0)/將源點(diǎn)設(shè)為v0即為路南校區(qū)int k;k=pathi; if(k!=v0) ShortPath(path,k,v0); printf("%d ",k);voi

16、d DIJ(int v0) int v,w,i,min,pathMAX,finalMAX,disMAX; int pMAXMAX; for(v=0;v<G.vexnum;+v) pathv=0; for(w=0;w<G.vexnum;+w) pvw=0; for(v=0;v<G.vexnum;+v)finalv=0;disv=G.AdjMatrixv0v; disv0=0; finalv0=1; pathv0=-1; for(i=1;i<G.vexnum;+i) min=INF; for(w=0;w<G.vexnum;+w) if(!finalw) if(disw

17、<min) v=w; min=disw; finalv=1; for(w=0;w<G.vexnum;+w) if(!finalw&&(min+G.AdjMatrixvw<disw) disw=min+G.AdjMatrixvw;pathw=v; printf("最短路徑:n"); for(i=1;i<G.vexnum;+i) if(finali=1 && i!=v0) printf("從校區(qū)%d到校區(qū)%d的最短距離為:%dt路徑為:",v0,i,disi); ShortPath(path,i,v0)

18、; printf("%dn",i); else printf("從%d到%d不存在!n",v0,i); main() int c;Create();printf("n 校園網(wǎng)架設(shè)的方案與設(shè)計(jì)nn");printf(" 1.prim算法的實(shí)現(xiàn)n");printf(" 2.克魯斯卡爾（Kruskual）算法的實(shí)現(xiàn)n");printf(" 3.路南校區(qū)到各個(gè)區(qū)的最短距離n");printf(" 4.退出系統(tǒng)nn");printf(" 請(qǐng)輸入您所要做的序號(hào)：");scanf("%d",&c);if(c<1|c>4) printf(" 無此菜單號(hào)，請(qǐng)重新輸入!n");printf(" 請(qǐng)輸入您所要做的序號(hào)：");scanf(&