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

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

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

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

4、程設(shè)計(jì)實(shí)踐作為培養(yǎng)學(xué)生動(dòng)手能力的一種手段，單獨(dú)考核。 3課程設(shè)計(jì)說明書一 需求分析問題描述 中國(guó)移動(dòng)公司正在積極推廣3G通信應(yīng)用，計(jì)劃在江蘇高校之間建立一個(gè)專用通信網(wǎng)絡(luò)，請(qǐng)為其規(guī)劃一個(gè)投資最省的通信線路架設(shè)方案。數(shù)據(jù)需求高校（高校名稱，地址，數(shù)量）高校間的線路線路的成本功能需求 能夠構(gòu)造通信網(wǎng)絡(luò)系統(tǒng)，編輯通信網(wǎng)絡(luò)系統(tǒng)，銷毀通信網(wǎng)絡(luò)系統(tǒng)，添加高校，刪除高校，修改高校名，添加高校間的線路，刪除高校間的線路，修改線路的成本，能生成最佳方案，輸出通信網(wǎng)絡(luò)系統(tǒng)，保存通信網(wǎng)絡(luò)系統(tǒng)。性能需求 輸出方案的結(jié)果直觀、明確高校專用通信網(wǎng)絡(luò)建設(shè)二 概要設(shè)計(jì) 保存通信網(wǎng)絡(luò)輸出通信網(wǎng)絡(luò)生成最佳方案編輯通信網(wǎng)絡(luò)構(gòu)造通信網(wǎng)

5、絡(luò)修改線路成本添加刪除高校間的線路修改高校名添加刪除高校銷毀通信網(wǎng)絡(luò)ADT LinearList數(shù)據(jù)元素：D=ai|aiD0,i=1,2，n，n0，D0為高校關(guān)系：S=ai,ai+1|ai,ai+1D0，i=1,2，n-1基本操作：InitList(L) 初始化L為空表DestoryList(L) 銷毀LClearList(L) 將L置為空表ListLength(L) 若L為空表則返回0，否則返回表中元素個(gè)數(shù)Locate(L,e) 若L中存在元素e則將當(dāng)前指針指向e所在位置并返回真GetData(L,i) 返回L中第i個(gè)元素的值InsList(L,I,e) 在L中第i個(gè)位置插入e，L的長(zhǎng)度增加

6、1DelList(L,I,&e) 刪除L的第i個(gè)元素，并用e返回其值，L長(zhǎng)度減少1ADT LinearList數(shù)據(jù)定義：typedef struct ArcNodeint adj;/權(quán)值A(chǔ)rcNode;typedef struct string vexsMAX_VERTEX_NUM;/頂點(diǎn) ArcNode arcsMAX_VERTEX_NUMMAX_VERTEX_NUM;/鄰接矩陣 int vexnum,arcnum;/頂點(diǎn)數(shù)和邊數(shù)graph;/圖的類型typedef struct string adjvex;int lowcost;minside;/求最小生成樹時(shí)的輔助數(shù)組的類voi

7、d menu(graph *g); /菜單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,st

8、ring v,string 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)main()主函數(shù)Menu()菜單 m n InPutNumber(m)InsertVex()Creategraph()Destorygraph()ChangeVex()DeleteVex()三 詳細(xì)設(shè)計(jì)創(chuàng)建通信系統(tǒng)int Creategraph(graph *g) int i,j,k,w; string va,vb;讀取文件"通信網(wǎng)絡(luò)

9、.txt" if(未找到文件) cout<<"open error!"<<endl;return 0; 從文件讀入頂點(diǎn)數(shù) 從文件讀入邊數(shù) 頂點(diǎn)向量 infile>>(*g).vexsi; 初始化鄰接矩陣 for(j=0;j<(*g).vexnum;+j)(*g).arcsij.adj=INFINITY; /網(wǎng) for(k=0;k<(*g).arcnum;+k) infile>>va>>vb>>w; i=LocateVex(g,va); j=LocateVex(g,vb); 無向網(wǎng)

10、infile.close(); return 1;開始創(chuàng)建通信系統(tǒng)能否讀取文件 N YOpen error 創(chuàng)建成功 結(jié)束添加高校 int InsertVex(graph *g,string v) /在圖g中增添新頂點(diǎn)vif(頂點(diǎn)數(shù)為0)cout<<"未建立通信網(wǎng)絡(luò)系統(tǒng)!n"system(暫停);Editgraph(g);cout<<"請(qǐng)輸入要添加的高校名:"cin>>v;int n=LocateVex(g,v);if(高校名重復(fù))cout<<"該高校已存在!n"system(暫停);E

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

12、aph(g);int i,j; int m=0; if（ v不是圖g的頂點(diǎn)） return 0; m=無限; for(j=0;j<(*g).vexnum;j+) if(有入弧或邊) 修改弧數(shù) for(序號(hào)k后面的頂點(diǎn)向量依次前移) (*g).vexsj-1=(*g).vexsj; for(i=0;i<(*g).vexnum;i+) for(j=k+1;j<(*g).vexnum;j+) 移動(dòng)待刪除頂點(diǎn)之后的矩陣元素 for(i=0;i<(*g).vexnum;i+) for(j=k+1;j<(*g).vexnum;j+)移動(dòng)待刪除頂點(diǎn)之下的矩陣元素 更新圖的頂點(diǎn)數(shù)

13、 return 1;修改高校名void ChangeVex(graph *g,string v)/修改高校名cout<<"請(qǐng)輸入要修改的高校名:"cin>>v;int n=LocateVex(g,v);if(n<0)cout<<"不存在該學(xué)校!n"system(暫停);Editgraph(g);string s;cout<<"請(qǐng)輸入修改后的高校名:"cin>>s;g->vexsn=s;添加路線int InsertArc(graph *g,string v,stri

14、ng w)/在g中增添弧<v,w>,若g是無向的,則還增添對(duì)稱弧<w,v>if(頂點(diǎn)數(shù)為0)cout<<"未建立通信網(wǎng)絡(luò)系統(tǒng)!n"system(暫停);Editgraph(g);cout<<"請(qǐng)輸入要添加的線路的兩端的高校名:"cin>>v>>w;int v1,w1; v1=LocateVex(g,v); /尾 w1=LocateVex(g,w); /頭 if(v1<0|w1<0|v1=w1)cout<<"高校名輸入錯(cuò)誤!n"system(

15、暫停);Editgraph(g);else if(路線兩頭高校名重復(fù))cout<<"該線路已存在!n"system(暫停);Editgraph(g); 弧或邊數(shù)加1 cout<<"請(qǐng)輸入該條線路的建設(shè)費(fèi)用:" cin>>(*g).arcsv1w1.adj;bool bRet = cin.good(); if(!bRet)cout<<"輸入的成本不是整型的!n"system(暫停);exit(0); (*g).arcsw1v1.adj=(*g).arcsv1w1.adj;return 1;

16、刪除線路int DeleteArc(graph *g,string v,string w) /在g中刪除弧<v,w>,若g是無向的,則還刪除對(duì)稱弧<w,v> if(頂點(diǎn)數(shù)為0)cout<<"未建立通信網(wǎng)絡(luò)系統(tǒng)!n"system(暫停);Editgraph(g);cout<<"請(qǐng)輸入要?jiǎng)h除的線路的兩端的高校名:"cin>>v>>w;int n=LocateVex(g,v);int m=LocateVex(g,w);if(m<0|n<0|m=n)cout<<&qu

17、ot;學(xué)校名輸入錯(cuò)誤!n"system(暫停);Editgraph(g);else if(花費(fèi)無限)cout<<"不存在該線路!n" system(暫停);編輯 g->arcsnm.adj=INFINITY;(*g).arcsmn.adj=(*g).arcsnm.adj;(*g).arcnum-; return 1;四 程序設(shè)計(jì)與調(diào)試分析1. 程序中運(yùn)用到大多的插入與刪除，但應(yīng)前期需求分析的準(zhǔn)備工作不充分，導(dǎo)致程序運(yùn)行功能不全，比如查找時(shí)關(guān)于此書的信息不能全部顯示出來，并且添加刪除時(shí)庫(kù)存的變化不能直接顯示出來。程序的健壯性不能達(dá)到預(yù)期的結(jié)果，這些

18、都是需要改進(jìn)的。2. 在程序中的函數(shù)調(diào)用是個(gè)非常重要的部分，也是經(jīng)常需要用到的，在編寫程序過程中，因?yàn)楹瘮?shù)調(diào)用不準(zhǔn)確，使得循環(huán)進(jìn)不去，后來改變函數(shù)的調(diào)用關(guān)系，才達(dá)到了預(yù)期結(jié)果。五 用戶手冊(cè)【使用說明】1. 進(jìn)入高校專用通信網(wǎng)絡(luò)系統(tǒng)2. 選擇1.構(gòu)造通信網(wǎng)絡(luò)系統(tǒng)，顯示出10個(gè)高校45條線路的通信系統(tǒng)矩陣。3. 若創(chuàng)建成功，選擇2.編輯通信網(wǎng)絡(luò)系統(tǒng)，顯示出功能18。4. 若要銷毀系統(tǒng)，選擇1.銷毀通信網(wǎng)絡(luò)系統(tǒng)。5. 若要添加高校，選擇2.添加一個(gè)高校，并輸入要添加的高校名。6. 若要?jiǎng)h除高校，選擇3.刪除一個(gè)高校，并輸入要?jiǎng)h除的高校名。若輸入的高校名不存在，則顯示不存在該學(xué)校。7. 若要修改高校名

19、，選擇4.修改高校名，并輸入要修改的高校名。若輸入的高校名不存在，則顯示不存在該學(xué)校。8. 若要添加高校間的線路，選擇5.添加一條高線間的線路，并輸入要添加線路兩端的高校名。若輸入的高校名錯(cuò)誤在則顯示學(xué)校名輸入錯(cuò)誤。9. 若要?jiǎng)h除高線間的線路，選擇6.刪除一條高校間的線路，并輸入要?jiǎng)h除線路兩端的高校名。若輸入的高校名不存在則顯示學(xué)校名輸入錯(cuò)誤。10. 若要修改線路的成本，選擇7.修改線路的成本，并輸入要?jiǎng)h除線路連段的高校名。若輸入的高校名不存在則顯示學(xué)校名輸入錯(cuò)誤。11. 若要推出編輯通信網(wǎng)絡(luò)系統(tǒng)，選擇8.退出?；氐礁咝Ｓ猛ㄐ啪W(wǎng)絡(luò)建設(shè)系統(tǒng)。12. 若要生成最佳方案，選擇3.生成最佳方案。并輸

20、入起始學(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.退出系統(tǒng)。六 測(cè)試成果構(gòu)造通信網(wǎng)絡(luò)系統(tǒng)編輯通信網(wǎng)絡(luò)系統(tǒng)，添加一個(gè)高校刪除一個(gè)高校修改高校名添加一條高校間的線路刪除高校間的線路修改高校間的成本生成最佳路線輸出通信網(wǎng)絡(luò)系統(tǒng)保存通信網(wǎng)絡(luò)系統(tǒng)七 附錄（源程序清單）#include "stdafx.h"#include <iostream>#include <iomanip>#include <windows.h>

21、#include <fstream>#include <string>#define MAX_VERTEX_NUM 30#define INFINITY 32768using namespace std;typedef struct ArcNodeint adj;/權(quán)值A(chǔ)rcNode;typedef struct string vexsMAX_VERTEX_NUM;/頂點(diǎn)ArcNode arcsMAX_VERTEX_NUMMAX_VERTEX_NUM;/鄰接矩陣int vexnum,arcnum;/頂點(diǎn)數(shù)和邊數(shù)graph;/圖的類型void menu(graph *g)

22、;void Editgraph(graph *g);int LocateVex(graph *g,string v)/求頂點(diǎn)位置函數(shù),若v存在,輸出j;若不存在,輸出0int j=-1,k;for(k=0;k<g->vexnum;k+)if(g->vexsk=v)/判斷是否存在頂點(diǎn)vj=k;break;return j;int Creategraph(graph *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(!inf

23、ile) cout<<"open error!"<<endl;return 0; infile>>g->vexnum;/從文件讀入頂點(diǎn)數(shù) infile>>g->arcnum;/從文件讀入邊數(shù) for(i=0;i<g->vexnum;+i) /頂點(diǎn)向量 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=0

24、;k<(*g).arcnum;+k) infile>>va>>vb>>w; 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中增添新頂點(diǎn)vif(g->vexnum=0)cout<<"未建立通信網(wǎng)絡(luò)系統(tǒng)!n"system("pause");Editgraph(g);co

25、ut<<"請(qǐng)輸入要添加的高校名:"cin>>v;int n=LocateVex(g,v);if(n>=0&&v=g->vexsn)cout<<"該高校已存在!n"system("pause");Editgraph(g); int i; (*g).vexs(*g).vexnum=v; /構(gòu)造新頂點(diǎn)向量 for(i=0;i<=(*g).vexnum;i+) (*g).arcs(*g).vexnumi.adj=INFINITY; /初始化該行鄰接矩陣的值 (*g).arc

26、si(*g).vexnum.adj=INFINITY; /初始化該列鄰接矩陣的值 (*g).vexnum+=1; / 圖g的頂點(diǎn)數(shù)加1 return 1;int DeleteVex(graph *g,string v) / 刪除g中頂點(diǎn)v及其相關(guān)的弧if(g->vexnum=0)cout<<"未建立通信網(wǎng)絡(luò)系統(tǒng)!n"system("pause");Editgraph(g);int k=LocateVex(g,v);if(k<0)cout<<"不存在該學(xué)校!n"system("pause&q

27、uot;);Editgraph(g);int i,j; int m=0; if(k<0) /v不是圖g的頂點(diǎn) return 0; m=INFINITY; for(j=0;j<(*g).vexnum;j+) if(*g).arcsjk.adj!=m) /有入弧或邊 (*g).arcnum-; /修改弧數(shù) for(j=k+1;j<(*g).vexnum;j+) /序號(hào)k后面的頂點(diǎn)向量依次前移(*g).vexsj-1=(*g).vexsj; for(i=0;i<(*g).vexnum;i+) for(j=k+1;j<(*g).vexnum;j+) (*g).arcsij

28、-1=(*g).arcsij; /移動(dòng)待刪除頂點(diǎn)之后的矩陣元素 for(i=0;i<(*g).vexnum;i+) for(j=k+1;j<(*g).vexnum;j+)(*g).arcsj-1i=(*g).arcsji; /移動(dòng)待刪除頂點(diǎn)之下的矩陣元素 (*g).vexnum-; /更新圖的頂點(diǎn)數(shù) return 1;void ChangeVex(graph *g,string v)/修改高校名cout<<"請(qǐng)輸入要修改的高校名:"cin>>v;int n=LocateVex(g,v);if(n<0)cout<<&quo

29、t;不存在該學(xué)校!n"system("pause");Editgraph(g);string s;cout<<"請(qǐng)輸入修改后的高校名:"cin>>s;g->vexsn=s;int InsertArc(graph *g,string v,string w)/在g中增添弧<v,w>,若g是無向的,則還增添對(duì)稱弧<w,v>if(g->vexnum=0)cout<<"未建立通信網(wǎng)絡(luò)系統(tǒng)!n"system("pause");Editgraph(

30、g);cout<<"請(qǐng)輸入要添加的線路的兩端的高校名:"cin>>v>>w;int v1,w1; v1=LocateVex(g,v); /尾 w1=LocateVex(g,w); /頭 if(v1<0|w1<0|v1=w1)cout<<"高校名輸入錯(cuò)誤!n"system("pause");Editgraph(g);else if(g->arcsv1w1.adj!=INFINITY)cout<<"該線路已存在!n"system("

31、pause");Editgraph(g); (*g).arcnum+; /弧或邊數(shù)加1 cout<<"請(qǐng)輸入該條線路的建設(shè)費(fèi)用:" cin>>(*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,str

32、ing w) /在g中刪除弧<v,w>,若g是無向的,則還刪除對(duì)稱弧<w,v> if(g->vexnum=0)cout<<"未建立通信網(wǎng)絡(luò)系統(tǒng)!n"system("pause");Editgraph(g);cout<<"請(qǐng)輸入要?jiǎng)h除的線路的兩端的高校名:"cin>>v>>w;int n=LocateVex(g,v);int m=LocateVex(g,w);if(m<0|n<0|m=n)cout<<"學(xué)校名輸入錯(cuò)誤!n&qu

33、ot;system("pause");Editgraph(g);else if(g->arcsnm.adj=INFINITY)cout<<"不存在該線路!n" system("pause");Editgraph(g); g->arcsnm.adj=INFINITY;(*g).arcsmn.adj=(*g).arcsnm.adj;(*g).arcnum-; return 1;void ChangeWeight(graph *g,string v,string w)cout<<"請(qǐng)輸入要修改的

34、線路的兩端的高校名:"cin>>v>>w;int m=LocateVex(g,v);int n=LocateVex(g,w);if(m<0|n<0)cout<<"輸入的學(xué)校不存在!n"system("pause");Editgraph(g);else if(g->arcsnm.adj=INFINITY)cout<<"不存在該線路!n" system("pause");Editgraph(g);char s;cout<<"

35、;請(qǐng)輸入該路線修改后的成本:"cin>>s;fflush(stdin);bool bRet = cin.good(); if(!bRet)cout<<"輸入的成本不是整型的!n"system("pause");exit(0);elseg->arcsmn.adj=g->arcsnm.adj=s;int Destroygraph(graph *g) /銷毀圖g if(g->vexnum=0)cout<<"未建立通信網(wǎng)絡(luò)系統(tǒng)!n"system("pause"

36、);Editgraph(g);int i; for(i=0;i<(*g).vexnum;i+)/刪除所有的點(diǎn)和邊DeleteVex(g,g->vexsi);(*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;cout<<g->vexnum<<"個(gè)高校"<&l

37、t;g->arcnum<<"條線路的通信系統(tǒng)如下面的矩陣:nn"cout<<" "for(i=0;i<g->vexnum;i+)cout<<setw(2)<<" "<<g->vexsi<<" "cout<<endl;for(i=0;i<g->vexnum;i+)cout<<g->vexsi<<" "for(j=0;j<g->vexnum

38、;j+)if(g->arcsij.adj=INFINITY)cout<<setw(5)<<""<<" "elsecout<<setw(5)<<g->arcsij.adj<<" "cout<<endl;return 1;/普里姆算法typedef struct string adjvex;int lowcost;minside;/求最小生成樹時(shí)的輔助數(shù)組的類int minimum(graph *G,minside closedgeMAX_VE

39、RTEX_NUM) /求closedgei.lowcost最小值，并返回iint i=0,j,k,min;while(closedgei.lowcost=0)/找到第一個(gè)值不為0的closedgei.lowcost的序號(hào)i+;min=closedgei.lowcost;/min標(biāo)記第一個(gè)不為0的值k=i;for(j=i+1;j<G->vexnum;j+)/繼續(xù)查找if(closedgej.lowcost>0&&closedgej.lowcost<min)min=closedgej.lowcost;k=j;return k;/返回當(dāng)前最小正值的序號(hào)void

40、 MiniSpanTree_Prim(graph *g,string s)static int sum=0;if(g->vexnum=0)cout<<"未建立通信網(wǎng)絡(luò)系統(tǒng)!n"system("pause");menu(g);cout<<"請(qǐng)輸入起始學(xué)校:"cin>>s;int n=LocateVex(g,s);if(n<0)cout<<"不存在該學(xué)校!n"system("pause");menu(g);minside closedgeM

41、AX_VERTEX_NUM;int k=LocateVex(g,s);string a30,b30;/a,b為中間變量，用來存放邊的頂點(diǎn)closedgek.lowcost=0;/初始化，U=sfor(int i=0;i<g->vexnum;i+)/初始化closedgekif(i!=k)closedgei.adjvex=s;closedgei.lowcost=g->arcski.adj; char name20;cout<<"輸入要保存的文件名:"cin>>name;strcat(name,".txt");ofs

42、tream outfile(name);outfile<<"最佳方案:n"cout<<"最佳方案:n"for(int e=1;e<=g->vexnum-1;e+)/找到n-1條邊int k0=minimum(g,closedge);string u0=closedgek0.adjvex;string v0=g->vexsk0;ae=u0;be=v0;int m=LocateVex(g,u0);int n=LocateVex(g,v0);cout<<"("<<u0<

43、<"->"<<v0<<")t成本為:"<<g->arcsmn.adj<<endl;outfile<<"("<<u0<<"->"<<v0<<")t成本為:"<<g->arcsmn.adj<<endl;sum+=g->arcsmn.adj;closedgek0.lowcost=0;for(i=0;i<g->vexnum;i

44、+)if(g->arcsk0i.adj<closedgei.lowcost)closedgei.lowcost=g->arcsk0i.adj;closedgei.adjvex=v0;cout<<"總成本:"<<sum<<endl;outfile<<"總成本:"<<sum<<endl;outfile.close();void save(graph *g)if(g->vexnum=0)cout<<"未建立通信網(wǎng)絡(luò)系統(tǒng)!n"syste

45、m("pause");menu(g);char name20;cout<<"輸入要保存的文件名:"cin>>name;strcat(name,".txt");ofstream outfile(name);outfile<<g->vexnum<<endl;outfile<<g->arcnum<<endl;for(int n=0;n<g->vexnum;n+)outfile<<g->vexsn<<endl;for(

46、int i=0;i<g->vexnum;i+)for(int j=0;j<i;j+)int a=LocateVex(g,g->vexsi);int b=LocateVex(g,g->vexsj);int w=g->arcsab.adj;if(w!=INFINITY)outfile<<g->vexsi<<" "<<g->vexsj<<" "<<w<<endl;cout<<"保存成功!n"outfile.cl

47、ose();void Editgraph(graph *g)system("cls");cout<<"tt*n"cout<<"tt 1.銷毀通信網(wǎng)絡(luò)系統(tǒng) n"cout<<"tt 2.添加一個(gè)高校 n"cout<<"tt 3.刪除一個(gè)高校 n"cout<<"tt 4.修改高校名 n"cout<<"tt 5.添加一條高校間的線路 n"cout<<"tt 6.刪除一條高

48、校間的線路 n"cout<<"tt 7.修改線路的成本 n"cout<<"tt 8.退出 n"cout<<"tt*n"cout<<"請(qǐng)選擇:"string v,w;char n;cin>>n;fflush(stdin);switch(n)case '1':Destroygraph(g);Display(g);cout<<"銷毀成功!n"system("pause");Editgr

49、aph(g);break;case '2':InsertVex(g,v);Display(g);cout<<"添加成功!n"system("pause");Editgraph(g);break;case '3':cout<<"請(qǐng)輸入要?jiǎng)h除的高校名:" cin>>v;DeleteVex(g,v);Display(g);cout<<"刪除成功!n"system("pause");Editgraph(g);break;ca

50、se '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&

51、quot;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<<"輸入錯(cuò)誤，請(qǐng)重新輸入!n"system("pause");Editgr

52、aph(g);break;system("pause");void menu(graph *g)system("cls");cout<<"tt*n"cout<<"tt 高校專用通信網(wǎng)絡(luò)建設(shè)系統(tǒng) nn"cout<<"tt 1.構(gòu)造通信網(wǎng)絡(luò)系統(tǒng) n"cout<<"tt 2.編輯通信網(wǎng)絡(luò)系統(tǒng) n"cout<<"tt 3.生成最佳方案 n"cout<<"tt 4.輸出通信網(wǎng)絡(luò)系統(tǒng) n

53、"cout<<"tt 5.保存通信網(wǎng)絡(luò)系統(tǒng) n"cout<<"tt 6.退出系統(tǒng) n"cout<<"tt*n"cout<<"請(qǐng)選擇:"string v;char n;cin>>n;switch(n)case '1':Creategraph(g);Display(g);cout<<"創(chuàng)建成功!n"system("pause");menu(g);break;case '2':Editgraph(g);break;case '3':MiniSpanTree_Prim(g,v);system("pause");menu(g);break;case '4':Display(