高校專用通信網(wǎng)絡(luò)建設(shè)

1、淮 海 工 學(xué) 院 計算機(jī)工程學(xué)院課程設(shè)計報告設(shè)計名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 選題名稱： 高校專用通信網(wǎng)絡(luò)建設(shè) 姓 名： 陳韋迪 學(xué) 號： 2014122778 專業(yè)班級： 計算機(jī)科學(xué)與技術(shù) 計算機(jī)142 系 （院）： 計算機(jī)工程學(xué)院 設(shè)計時間： 2014.12.222015.1.4 設(shè)計地點： 計算機(jī)實驗室、教室 成績：指導(dǎo)教師評語： 簽名： 年 月 日43 / 44文檔可自由編輯1課程設(shè)計目的1、訓(xùn)練學(xué)生靈活應(yīng)用所學(xué)數(shù)據(jù)結(jié)構(gòu)知識，獨立完成問題分析，結(jié)合數(shù)據(jù)結(jié)構(gòu)理論知識，編寫程序求解指定問題。 2、初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；3、提高綜合運用所學(xué)的

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

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

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

5、 void Editgraph(graph *g); /編輯通信網(wǎng)絡(luò)系統(tǒng) int Creategraph(graph *g) /創(chuàng)建通信網(wǎng)絡(luò)系統(tǒng) 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

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

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

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

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

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

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

12、f(頂點數(shù)為0) cout未建立通信網(wǎng)絡(luò)系統(tǒng)!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(路線兩頭高校名重復(fù)) cout該線路已存在!n; system(暫停); Editgraph(g); 弧或邊數(shù)加1 cout(*g).arcsv1w1.adj; bool bRet = cin.good(); if(!bRet) cou

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

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

15、，后來改變函數(shù)的調(diào)用關(guān)系，。五 用戶手冊【使用說明】 1.使用高校專用通信網(wǎng)絡(luò)系統(tǒng) 2.選擇1.構(gòu)造通信網(wǎng)絡(luò)系統(tǒng)，則顯示出10個高校45條線路的通信系統(tǒng)矩陣。 3.創(chuàng)建成功，選擇2.編輯通信網(wǎng)絡(luò)系統(tǒng)，顯示出功能18。 4.銷毀系統(tǒng)，選擇1.銷毀通信網(wǎng)絡(luò)系統(tǒng)。 5.添加高校，選擇2.添加一個高校，并輸入要添加的高校名。 6.刪除高校，選擇3.刪除一個高校，并輸入要刪除的高校名。若輸入的高校名不存在，則顯示 不存在該學(xué)校。 7.修改高校名，選擇4.修改高校名，并輸入要修改的高校名。若輸入的高校名不存在，則顯示不存在該學(xué)校。 8.添加高校間的線路，選擇5.添加一條高線間的線路，輸入要添加線路兩端的高

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

17、統(tǒng)。六 測試成果1.通信網(wǎng)絡(luò)系統(tǒng)2.添加一個高校3.刪除一個高校4.修改高校名5.添加一條高校間的線路6.刪除高校間的線路7.修改高校間的成本8.生成最佳路線9.輸出通信網(wǎng)絡(luò)系統(tǒng)10.保存通信網(wǎng)絡(luò)系統(tǒng)七 附錄（源程序清單）#include stdafx.h#include #include #include #include #include #define MAX_VERTEX_NUM 30#define INFINITY 32768using namespace std;typedef struct ArcNodeint adj;/權(quán)值A(chǔ)rcNode;typedef struct stri

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

19、aph *g)/采用鄰接矩陣法,構(gòu)造有向網(wǎng)g int i,j,k,w; string va,vb; ifstream infile(通信網(wǎng)絡(luò).txt,ios:in);/從文件中讀入數(shù)據(jù) if(!infile) coutopen error!g-vexnum;/從文件讀入頂點數(shù) infileg-arcnum;/從文件讀入邊數(shù) 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; /網(wǎng) for(k=

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

21、nt i; (*g).vexs(*g).vexnum=v; /構(gòu)造新頂點向量 for(i=0;ivexnum=0)cout未建立通信網(wǎng)絡(luò)系統(tǒng)!n;system(pause);Editgraph(g);int k=LocateVex(g,v);if(k0)cout不存在該學(xué)校!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-; /修改弧數(shù) fo

22、r(j=k+1;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-; /更新圖的頂點數(shù) return 1;void ChangeVex

23、(graph *g,string v)/修改高校名coutv;int n=LocateVex(g,v);if(n0)cout不存在該學(xué)校!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未建立通信網(wǎng)絡(luò)系統(tǒng)!n;system(pause);Editgraph(g);coutvw;int v1,w1; v1=LocateVex(g,v); /尾 w1=LocateVex(g,w)

24、; /頭 if(v10|w10|v1=w1)coutarcsv1w1.adj!=INFINITY)cout該線路已存在!n;system(pause);Editgraph(g); (*g).arcnum+; /弧或邊數(shù)加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中刪除

25、弧,若g是無向的,則還刪除對稱弧 if(g-vexnum=0)cout未建立通信網(wǎng)絡(luò)系統(tǒng)!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=Loc

26、ateVex(g,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未建立通信網(wǎng)絡(luò)系統(tǒng)!n;system(pause);Editgraph(g);int i; for(i=

27、0;ivexsi);(*g).vexnum=0; (*g).arcnum=0;return 1;int Display(graph *g)/以矩陣方式輸出圖if(g-vexnum=0)cout未建立通信網(wǎng)絡(luò)系統(tǒng)!n;system(pause);menu(g);int i,j;coutvexnum個高校arcnum條線路的通信系統(tǒng)如下面的矩陣: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=INFINIT

28、Y)coutsetw(5) ;elsecoutsetw(5)arcsij.adj ;coutendl;return 1;/普里姆算法typedef struct string adjvex;int lowcost;minside;/求最小生成樹時的輔助數(shù)組的類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.

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

30、.lowcost=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

31、-vexsk0;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未建立通信網(wǎng)絡(luò)系統(tǒng)!n;system(pause);menu(g);ch

32、ar name20;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 Edi

33、tgraph(graph *g)system(cls);couttt*n;couttt 1.銷毀通信網(wǎng)絡(luò)系統(tǒng) 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);bre

34、ak;case 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);