1、淮 海 工 學 院 計算機工程學院課程設計報告設計名稱： 數據結構課程設計 選題名稱： 高校專用通信網絡建設 姓 名： 陳韋迪 學 號： 2014122778 專業班級： 計算機科學與技術 計算機142 系 （院）： 計算機工程學院 設計時間： 2014.12.222015.1.4 設計地點： 計算機實驗室、教室 成績：指導教師評語： 簽名： 年 月 日1 / 331課程設計目的1、訓練學生靈活應用所學數據結構知識，獨立完成問題分析，結合數據結構理論知識，編寫程序求解指定問題。 2、初步掌握軟件開發過程的問題分析、系統設計、程序編碼、測試等基本方法和技能；3、提高綜合運用所學的理論知識和方法獨

2、立分析和解決問題的能力；4、訓練用系統的觀點和軟件開發一般規范進行軟件開發，鞏固、深化學生的理論知識，提高編程水平，并在此過程中培養他們嚴謹的科學態度和良好的工作作風。2課程設計任務與要求：任務根據教材數據結構-C語言描述（耿國華主編）和參考書數據結構題集（C語言版）（嚴蔚敏、吳偉民主編）選擇課程設計題目，要求通過設計，在數據結構的邏輯特性和物理表示、數據結構的選擇應用、算法的設計及其實現等方面加深對課程基本內容的理解和綜合運用。設計題目從任務書所列選題表中選取，每班每題不得超過2人。學生自選課題。學生原則上可以結合個人愛好自選課題，要求課題有一定的深度與難度，有一定的算法復雜性，能夠鞏固數據

3、結構課程所學的知識。學生自選課題需在18周前報課程設計指導教師批準方可生效。要求：1、在處理每個題目時，要求從分析題目的需求入手，按設計抽象數據類型、構思算法、通過設計實現抽象數據類型、編制上機程序和上機調試等若干步驟完成題目，最終寫出完整的分析報告。前期準備工作完備與否直接影響到后序上機調試工作的效率。在程序設計階段應盡量利用已有的標準函數，加大代碼的重用率。 2、設計的題目要求達到一定工作量（300行以上代碼），并具有一定的深度和難度。3、程序設計語言推薦使用C/C+，程序書寫規范，源程序需加必要的注釋;4、每位同學需提交可獨立運行的程序；5、每位同學需獨立提交設計報告書（每人一份），要求

4、編排格式統一、規范、內容充實，不少于10頁（代碼不算）；6、課程設計實踐作為培養學生動手能力的一種手段，單獨考核。 3課程設計說明書一 需求分析 問題描述 中國移動公司正在積極推廣3G通信應用，計劃在江蘇高校之間建立一個專用通信網絡，請為其規劃一個投資最省的通信線路架設方案。基本要求（1） 用無向網模擬該系統，頂點表示各高校，邊表示線路建設成本（2） 高校數量不少于10個，覆蓋蘇南、蘇中、蘇北、南京等地的高校（3） 輸出方案的結果直觀、明確（4） 交互式改變某些線路的建設成本，可重新輸出新方案二 概要設計3課程設計說明書二概要設計void menu(graph *g); /菜單 void Ed

5、itgraph(graph *g); /編輯通信網絡系統 int Creategraph(graph *g) /創建通信網絡系統 int InsertVex(graph *g,string v) /添加高校 void ChangeVex(graph *g,string v) /修改高校名 int InsertArc(graph *g,string v,string w) /添加高校間的路線 int DeleteArc(graph *g,string v,string w) /刪除高校間的路線 void ChangeWeight(graph *g,string v,string w) /修改高校

6、間的路線及其成本 int Destroygraph(graph *g) /銷毀通信網絡系統 int Display(graph *g) /輸出通信網絡系統 void save(graph *g) /保存通信網絡系統基本操作：InitList(L)初始化L為空表DestoryList(L) 銷毀LClearList(L) 將L置為空表ListLength(L) 若L為空表則返回0，否則返回表中元素個數Locate(L,e)若L中存在元素e則將當前指針指向e所在位置并返回真GetData(L,i) 返回L中第i個元素的值InsList(L,I,e) 在L中第i個位置插入e，L的長度增加1DelLi

7、st(L,I,&e) 刪除L的第i個元素，并用e返回其值，L長度減少1數據定義： typedef struct ArcNode int adj;/權值 ArcNode; typedef struct string vexsMAX_VERTEX_NUM;/頂點 ArcNode arcsMAX_VERTEX_NUMMAX_VERTEX_NUM;/鄰接矩陣 int vexnum,arcnum;/頂點數和邊數 graph;/圖的類型 typedef struct string adjvex; int lowcost; minside;/求最小生成樹時的輔助數組的類 三 詳細設計創建通信系統 int C

8、reategraph(graph *g) int i,j,k,w; string va,vb; 讀取文件通信網絡.txt if(未找到文件) coutopen error!(*g).vexsi; 初始化鄰接矩陣 for(j=0;j(*g).vexnum;+j) (*g).arcsij.adj=INFINITY; /網 for(k=0;kvavbw; i=LocateVex(g,va); j=LocateVex(g,vb); 無向網 infile.close(); return 1; 添加高校 int InsertVex(graph *g,string v) /在圖g中增添新頂點v if(頂點數

9、為0) cout未建立通信網絡系統!n; system(暫停); Editgraph(g); coutv; int n=LocateVex(g,v); if(高校名重復) cout該高校已存在!n; system(暫停); Editgraph(g); int i; 構造新頂點向量 for(i=0;i=(*g).vexnum;i+) 初始化該行鄰接矩陣的值 初始化該列鄰接矩陣的值 圖g的頂點數加1 return 1; 刪除學校 int DeleteVex(graph *g,string v) / 刪除g中頂點v及其相關的弧 if(頂點數為0) cout未建立通信網絡系統!n; system(暫停

10、); Editgraph(g); int k=LocateVex(g,v); if(k0) cout不存在該學校!n; system(暫停); Editgraph(g); int i,j; int m=0; if（ v不是圖g的頂點） return 0; m=無限; for(j=0;j(*g).vexnum;j+) if(有入弧或邊) 修改弧數 for(序號k后面的頂點向量依次前移) (*g).vexsj-1=(*g).vexsj; for(i=0;i(*g).vexnum;i+) for(j=k+1;j(*g).vexnum;j+) 移動待刪除頂點之后的矩陣元素 for(i=0;i(*g).

11、vexnum;i+) for(j=k+1;j(*g).vexnum;j+) 移動待刪除頂點之下的矩陣元素 更新圖的頂點數 return 1; 修改高校名 void ChangeVex(graph *g,string v)/修改高校名 coutv; int n=LocateVex(g,v); if(n0) cout不存在該學校!n; system(暫停); Editgraph(g); string s; couts; g-vexsn=s; 添加路線 int InsertArc(graph *g,string v,string w) /在g中增添弧,若g是無向的,則還增添對稱弧 if(頂點數為0)

12、 cout未建立通信網絡系統!n; system(暫停); Editgraph(g); coutvw; int v1,w1; v1=LocateVex(g,v); /尾 w1=LocateVex(g,w); /頭 if(v10|w10|v1=w1) cout高校名輸入錯誤!n; system(暫停); Editgraph(g); else if(路線兩頭高校名重復) cout該線路已存在!n; system(暫停); Editgraph(g); 弧或邊數加1 cout(*g).arcsv1w1.adj; bool bRet = cin.good(); if(!bRet) cout輸入的成本不是

13、整型的!n; system(暫停); exit(0); (*g).arcsw1v1.adj=(*g).arcsv1w1.adj; return 1; 刪除線路 int DeleteArc(graph *g,string v,string w) /在g中刪除弧,若g是無向的,則還刪除對稱弧 if(頂點數為0) cout未建立通信網絡系統!n; system(暫停); Editgraph(g); coutvw; int n=LocateVex(g,v); int m=LocateVex(g,w); if(m0|n0|m=n) cout學校名輸入錯誤!n; system(暫停); Editgraph

14、(g); else if(花費無限) coutarcsnm.adj=INFINITY; (*g).arcsmn.adj=(*g).arcsnm.adj; (*g).arcnum-; return 1; 四 程序設計與調試分析1.因為前期需求分析的準備工作不充分，程序運行功能不全，程序中運用到大多的插入與刪除，比如查找時關于線路的信息不能全部顯示出來，并且添加刪除時線路的變化不能直接顯示出來。程序的健壯性不能達到預期的結果，這些都是需要改進的。 2. 在編寫程序過程中，因為函數調用不準確，使得循環進不去，在程序中的函數調用是個非常重要的部分，也是經常需要用到的，為了達到了預期結果，后來改變函數的

15、調用關系，。五 用戶手冊【使用說明】 1.使用高校專用通信網絡系統 2.選擇1.構造通信網絡系統，則顯示出10個高校45條線路的通信系統矩陣。 3.創建成功，選擇2.編輯通信網絡系統，顯示出功能18。 4.銷毀系統，選擇1.銷毀通信網絡系統。 5.添加高校，選擇2.添加一個高校，并輸入要添加的高校名。 6.刪除高校，選擇3.刪除一個高校，并輸入要刪除的高校名。若輸入的高校名不存在，則顯示 不存在該學校。 7.修改高校名，選擇4.修改高校名，并輸入要修改的高校名。若輸入的高校名不存在，則顯示不存在該學校。 8.添加高校間的線路，選擇5.添加一條高線間的線路，輸入要添加線路兩端的高校名。若輸入的高

16、校名錯誤在則顯示學校名輸入錯誤。 9.刪除高線間的線路，選擇6.刪除一條高校間的線路，并輸入要刪除線路兩端的高校名。若輸入的高校名不存在則顯示學校名輸入錯誤。 10.修改線路的成本，選擇7.修改線路的成本，并輸入要刪除線路連段的高校名。若輸入的高校名不存在則顯示學校名輸入錯誤。 11.推出編輯通信網絡系統，選擇8.退出。回到高校專用通信網絡建設系統。 12.生成最佳方案，選擇3.生成最佳方案。并輸入起始學校和要保存的文件名。 13.輸出通信網絡系統，選擇4.輸出通信網絡系統。 14.保存通信網絡系統，選擇5.保存通信網絡系統。并輸入要保存的文件名。 15. 退出，選擇6.退出系統。六 測試成果

17、1.通信網絡系統2.添加一個高校3.刪除一個高校4.修改高校名5.添加一條高校間的線路6.刪除高校間的線路7.修改高校間的成本8.生成最佳路線9.輸出通信網絡系統10.保存通信網絡系統七 附錄（源程序清單）#include stdafx.h#include #include #include #include #include #define MAX_VERTEX_NUM 30#define INFINITY 32768using namespace std;typedef struct ArcNodeint adj;/權值ArcNode;typedef struct string vexsM

18、AX_VERTEX_NUM;/頂點ArcNode arcsMAX_VERTEX_NUMMAX_VERTEX_NUM;/鄰接矩陣int vexnum,arcnum;/頂點數和邊數graph;/圖的類型void menu(graph *g);void Editgraph(graph *g);int LocateVex(graph *g,string v)/求頂點位置函數,若v存在,輸出j;若不存在,輸出0int j=-1,k;for(k=0;kvexnum;k+)if(g-vexsk=v)/判斷是否存在頂點vj=k;break;return j;int Creategraph(graph *g)/

19、采用鄰接矩陣法,構造有向網g int i,j,k,w; string va,vb; ifstream infile(通信網絡.txt,ios:in);/從文件中讀入數據 if(!infile) coutopen error!g-vexnum;/從文件讀入頂點數 infileg-arcnum;/從文件讀入邊數 for(i=0;ivexnum;+i) /頂點向量 infile(*g).vexsi; for(i=0;i(*g).vexnum;+i) /初始化鄰接矩陣 for(j=0;j(*g).vexnum;+j)(*g).arcsij.adj=INFINITY; /網 for(k=0;kvavbw

20、; i=LocateVex(g,va); j=LocateVex(g,vb); (*g).arcsij.adj=(*g).arcsji.adj=w; /無向網 infile.close(); return 1;int InsertVex(graph *g,string v) /在圖g中增添新頂點vif(g-vexnum=0)cout未建立通信網絡系統!n;system(pause);Editgraph(g);coutv;int n=LocateVex(g,v);if(n=0&v=g-vexsn)cout該高校已存在!n;system(pause);Editgraph(g); int i; (*

21、g).vexs(*g).vexnum=v; /構造新頂點向量 for(i=0;ivexnum=0)cout未建立通信網絡系統!n;system(pause);Editgraph(g);int k=LocateVex(g,v);if(k0)cout不存在該學校!n;system(pause);Editgraph(g);int i,j; int m=0; if(k0) /v不是圖g的頂點 return 0; m=INFINITY; for(j=0;j(*g).vexnum;j+) if(*g).arcsjk.adj!=m) /有入弧或邊 (*g).arcnum-; /修改弧數 for(j=k+1;

22、j(*g).vexnum;j+) /序號k后面的頂點向量依次前移(*g).vexsj-1=(*g).vexsj; for(i=0;i(*g).vexnum;i+) for(j=k+1;j(*g).vexnum;j+) (*g).arcsij-1=(*g).arcsij; /移動待刪除頂點之后的矩陣元素 for(i=0;i(*g).vexnum;i+) for(j=k+1;j(*g).vexnum;j+)(*g).arcsj-1i=(*g).arcsji; /移動待刪除頂點之下的矩陣元素 (*g).vexnum-; /更新圖的頂點數 return 1;void ChangeVex(graph *

23、g,string v)/修改高校名coutv;int n=LocateVex(g,v);if(n0)cout不存在該學校!n;system(pause);Editgraph(g);string s;couts;g-vexsn=s;int InsertArc(graph *g,string v,string w)/在g中增添弧,若g是無向的,則還增添對稱弧if(g-vexnum=0)cout未建立通信網絡系統!n;system(pause);Editgraph(g);coutvw;int v1,w1; v1=LocateVex(g,v); /尾 w1=LocateVex(g,w); /頭 if(

24、v10|w10|v1=w1)coutarcsv1w1.adj!=INFINITY)cout該線路已存在!n;system(pause);Editgraph(g); (*g).arcnum+; /弧或邊數加1 cout(*g).arcsv1w1.adj;bool bRet = cin.good(); if(!bRet)cout輸入的成本不是整型的!n;system(pause);exit(0); (*g).arcsw1v1.adj=(*g).arcsv1w1.adj;return 1;int DeleteArc(graph *g,string v,string w) /在g中刪除弧,若g是無向的

25、,則還刪除對稱弧 if(g-vexnum=0)cout未建立通信網絡系統!n;system(pause);Editgraph(g);coutvw;int n=LocateVex(g,v);int m=LocateVex(g,w);if(m0|n0|m=n)coutarcsnm.adj=INFINITY)coutarcsnm.adj=INFINITY;(*g).arcsmn.adj=(*g).arcsnm.adj;(*g).arcnum-; return 1;void ChangeWeight(graph *g,string v,string w)coutvw;int m=LocateVex(g

26、,v);int n=LocateVex(g,w);if(m0|n0)coutarcsnm.adj=INFINITY)cout不存在該線路!n; system(pause);Editgraph(g);char s;couts;fflush(stdin);bool bRet = cin.good(); if(!bRet)coutarcsmn.adj=g-arcsnm.adj=s;int Destroygraph(graph *g) /銷毀圖g if(g-vexnum=0)cout未建立通信網絡系統!n;system(pause);Editgraph(g);int i; for(i=0;ivexsi

27、);(*g).vexnum=0; (*g).arcnum=0;return 1;int Display(graph *g)/以矩陣方式輸出圖if(g-vexnum=0)cout未建立通信網絡系統!n;system(pause);menu(g);int i,j;coutvexnum個高校arcnum條線路的通信系統如下面的矩陣:nn;cout ;for(i=0;ivexnum;i+)coutsetw(2) vexsi ;coutendl;for(i=0;ivexnum;i+)coutvexsi ;for(j=0;jvexnum;j+)if(g-arcsij.adj=INFINITY)coutse

28、tw(5) ;elsecoutsetw(5)arcsij.adj ;coutendl;return 1;/普里姆算法typedef struct string adjvex;int lowcost;minside;/求最小生成樹時的輔助數組的類int minimum(graph *G,minside closedgeMAX_VERTEX_NUM) /求closedgei.lowcost最小值，并返回iint i=0,j,k,min;while(closedgei.lowcost=0)/找到第一個值不為0的closedgei.lowcost的序號i+;min=closedgei.lowcost;

29、/min標記第一個不為0的值k=i;for(j=i+1;jvexnum;j+)/繼續查找if(closedgej.lowcost0&closedgej.lowcostvexnum=0)cout未建立通信網絡系統!n;system(pause);menu(g);couts;int n=LocateVex(g,s);if(n0)cout不存在該學校!n;system(pause);menu(g);minside closedgeMAX_VERTEX_NUM;int k=LocateVex(g,s);string a30,b30;/a,b為中間變量，用來存放邊的頂點closedgek.lowcost

30、=0;/初始化，U=sfor(int i=0;ivexnum;i+)/初始化closedgekif(i!=k)closedgei.adjvex=s;closedgei.lowcost=g-arcski.adj; char name20;coutname;strcat(name,.txt);ofstream outfile(name);outfile最佳方案:n;cout最佳方案:n;for(int e=1;evexnum-1;e+)/找到n-1條邊int k0=minimum(g,closedge);string u0=closedgek0.adjvex;string v0=g-vexsk0;

31、ae=u0;be=v0;int m=LocateVex(g,u0);int n=LocateVex(g,v0);cout(u0v0)t成本為:arcsmn.adjendl;outfile(u0v0)t成本為:arcsmn.adjarcsmn.adj;closedgek0.lowcost=0;for(i=0;ivexnum;i+)if(g-arcsk0i.adjarcsk0i.adj;closedgei.adjvex=v0;cout總成本:sumendl;outfile總成本:sumvexnum=0)cout未建立通信網絡系統!n;system(pause);menu(g);char name2

32、0;coutname;strcat(name,.txt);ofstream outfile(name);outfilevexnumendl;outfilearcnumendl;for(int n=0;nvexnum;n+)outfilevexsnendl;for(int i=0;ivexnum;i+)for(int j=0;jvexsi);int b=LocateVex(g,g-vexsj);int w=g-arcsab.adj;if(w!=INFINITY)outfilevexsi vexsj wendl;cout保存成功!n;outfile.close();void Editgraph(g

33、raph *g)system(cls);couttt*n;couttt 1.銷毀通信網絡系統 n;couttt 2.添加一個高校 n;couttt 3.刪除一個高校 n;couttt 4.修改高校名 n;couttt 5.添加一條高校間的線路 n;couttt 6.刪除一條高校間的線路 n;couttt 7.修改線路的成本 n;couttt 8.退出 n;couttt*n;coutn;fflush(stdin);switch(n)case 1:Destroygraph(g);Display(g);cout銷毀成功!n;system(pause);Editgraph(g);break;case

34、2:InsertVex(g,v);Display(g);cout添加成功!n;system(pause);Editgraph(g);break;case 3:coutv;DeleteVex(g,v);Display(g);cout刪除成功!n;system(pause);Editgraph(g);break;case 4:ChangeVex(g,v);Display(g);cout修改成功!n;system(pause);Editgraph(g);case 5:InsertArc(g,v,w);Display(g);cout添加成功!n;system(pause);Editgraph(g);break;case 6:DeleteArc(g,v,w);Display(g);cout刪除成功!n;system(pause);Editgraph(g);break;case 7:ChangeWeight(g,v,w);Display(g);cout修改成功!n;system(pause);Editgraph(g);break;case 8:menu(g);system(pause);default:cout輸入錯誤，請重新輸入!n;system(pause);Editgraph(g);b