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

2、試，驗證程序的正確性。二、課程設計的目的課程設計的目的是培養學生綜合程序設計的能力，訓練學生靈活應用所學數據結構知識，獨立完成問題分析、總體設計、詳細設計和編程實現等軟件開發全過程的綜合實踐能力。鞏固、深化學生的理論知識，提高編程水平，并在此過程中培養他們嚴謹的科學態度和良好的學習作風。為今后學習其他計算機課程打下基礎。課程設計為學生提供了一個既動手又動腦，獨立實踐的機會，將書本上的理論知識和工作、生產實際有機地結合起來，從而鍛煉學生分析問題、解決實際問題的能力，提高學生的編程序能力和創新意識。三、分析系統的主要功能及用途在揚州大學的七個校區（江陽路南校區、江陽路北校區、瘦西湖校區、農學院校區

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

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

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

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

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

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

9、Gragh G;void Create(void)/創建無向圖G的鄰接矩陣存儲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("校園網構架方案如下所示：n")

12、; printf("n"); printf("始點終點兩校距離n"); for(i=0;i<n-1;i+) printf("n");printf("%4d%4d%8dn",closei.begin,closei.end,closei.cost); printf("n"); printf("校園網最低的經濟代價總長為:%dn",sum);TreeEdge edgeMAX*MAX,treeMAX;void Sort(void)/在G中選擇經濟代價最低的校園網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("校園網構架方案如下所示：n"); printf("n"); printf("始點終點兩校距離n"

15、;);for(j=0;j<n-1;j+)printf("n");printf("%4d%4d%8dn",treej.end,treej.begin,treej.cost);printf("n");printf("校園網最低的經濟代價總長為:%dn",sum);void ShortPath(int path,int i,int v0)/將源點設為v0即為路南校區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("從校區%d到校區%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 校園網架設的方案與設計nn");printf(" 1.prim算法的實現n");printf(" 2.克魯斯卡爾（Kruskual）算法的實現n");printf(" 3.路南校區到各個區的最短距離n");printf(" 4.退出系統nn");printf(" 請輸入您所要做的序號：");scanf("%d",&c);if(c<1|c>4) printf(" 無此菜單號，請重新輸入!n");printf(" 請輸入您所要做的序號：");scanf(&