課程設(shè)計(jì)報(bào)告-- 小區(qū)網(wǎng)絡(luò)光纖的鋪設(shè)

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁(yè)數(shù)：15 大?。?50.50KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

2023年全國(guó)碩士研究生考試考研英語(yǔ)一試題真題（含答案詳解+作文范文）_第1頁(yè)

已閱讀1頁(yè)，還剩14頁(yè)未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說(shuō)明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、　　課程設(shè)計(jì)報(bào)告　　課程設(shè)計(jì)的主要內(nèi)容　　設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)和算法，實(shí)現(xiàn)居民小區(qū)之間網(wǎng)絡(luò)光纖鋪設(shè)的最佳方案選擇，主要內(nèi)容如下：需要在某個(gè)城市n個(gè)居民小區(qū)之間鋪設(shè)網(wǎng)絡(luò)光纖，假設(shè)任意兩個(gè)居民小區(qū)之間均需要鋪設(shè)光纖，則在這n個(gè)居民小區(qū)之間只需要鋪設(shè)n-1條光纖即可形成一個(gè)網(wǎng)

2、絡(luò)，但由于地理環(huán)境不同，所需要的代價(jià)也不盡相同。本課程設(shè)計(jì)要求事先隨機(jī)生成任意居民小區(qū)之間鋪設(shè)網(wǎng)絡(luò)光纖的代價(jià)，并將代價(jià)存入文件，然后設(shè)計(jì)一個(gè)最佳方案進(jìn)行光纖鋪設(shè)，使得既能連通所有小區(qū)之間的網(wǎng)絡(luò)，又能使網(wǎng)絡(luò)光纖鋪設(shè)的代價(jià)最小，最終以圖形形式輸出所設(shè)計(jì)的最佳方案。　　功能和結(jié)構(gòu)設(shè)計(jì)　　1、克魯斯卡爾算法：</p&g

3、t;　　克魯斯卡爾算法的思想：　　設(shè)無(wú)向連通網(wǎng)為G=（V，E），令G的最小生成樹(shù)為T(mén)=（U，TE）,其初態(tài)為U=V，TE={}，這樣T中個(gè)頂點(diǎn)各自構(gòu)成一個(gè)連通分量。然后，按照邊的權(quán)值由小到大的順序，依次考察邊集E中的各條邊。若被考察邊的兩個(gè)頂點(diǎn)屬于T的兩個(gè)不同的連通分量，則將此邊加入到TE中，同時(shí)把兩個(gè)連通分量連接為一個(gè)連通分量；若被考察邊的兩個(gè)頂點(diǎn)屬于同一個(gè)連通分量，則舍

4、去此邊，以免造成回路，如此下來(lái)，當(dāng)T中的連通分量個(gè)數(shù)為1時(shí)，此連通分量便為G的一棵最小生成樹(shù)。　　算法過(guò)程描述：　　初始化：U=V; TE={};　　重復(fù)下述操作直到T中的連通分量個(gè)數(shù)為1；　　2、1 在E中尋找最短邊（U,V）；

5、　　2、2 如果頂點(diǎn)u、v位于T的兩個(gè)不同連通分量，則　　2 . 2 . 1、將邊（u、v）并入TE；　　2 . 2 . 2、將這兩個(gè)連通分量合為一個(gè)；　　2、3 在E中標(biāo)記邊（u，v），使得（u，v）不參加后續(xù)最短邊的選??；<p&g

6、t;　　模塊分析　　根據(jù)對(duì)模型的功能分析，該管道鋪設(shè)設(shè)計(jì)可以具有以下功能：　　網(wǎng)絡(luò)光纖鋪設(shè)信息的輸入；　　最小生成樹(shù)信息的輸出；　　抽象數(shù)據(jù)類型分析　　V

7、ertex[] 居民區(qū)　　Edge[][] 鄰接矩陣儲(chǔ)存居民區(qū)的關(guān)系　　R[] 居民區(qū)之間的距離　　vertexNum 表示居民區(qū)數(shù)量　　edgeNum 表示居民區(qū)的路線數(shù)目<b&g

8、t;　　功能分析　　信息輸入：　　程序輸出：　　最短路徑：　　流程圖和算法設(shè)計(jì)

9、　　//居民區(qū)數(shù)據(jù)輸入　　cout<<"請(qǐng)輸入居民區(qū)的個(gè)數(shù)：";　　cin>>vertexNum;　　cout<<endl;　　cout<<&qu

10、ot;分別輸入居民區(qū)：";　　for(i=0;i<vertexNum;i++)　　cin>>vertex[i];　　cout<<"請(qǐng)輸入網(wǎng)絡(luò)光纖鋪設(shè)路線的總條數(shù)：";　　cin>>edgeNum;&l

11、t;/p>　　//二維數(shù)組存儲(chǔ)居民區(qū)信息　　cout<<"請(qǐng)按此格式輸入邊和權(quán)值：n, m, k（表示 n 居民區(qū)到 m 居民區(qū)的距離為 k 米）："<<endl;　　for(i=0;i<edgeNum;i++)

12、{　　cin>>n>>m>>k;　　Edge[n][m]=k;　　Edge[m][n]=k;　　R[i]=k;　　}&

13、lt;/b>　　cout<<endl;　　//對(duì)儲(chǔ)存權(quán)值的數(shù)組R[]進(jìn)行排序　　void Graph<Datatype>::InsertSort()　　{<

14、b>　　int k;　　for(int i=1;i<edgeNum;i++)　　{　　k=R[i];　　for(int j=i-1;k<R[j];j--)&l

15、t;/p>　　{R[j+1]=R[j];}　　R[j+1]=k;　　}　　}　　//克魯卡爾算法生成最小生成樹(shù)

16、　　void Graph<Datatype>::Kruskal()　　{　　Sum=0;　　int i,b=0,d=0,num,vex1,vex2;　　for(i

17、=0;i<vertexNum;i++)　　parent[i]=-1;　　cout<<"選取光纖鋪設(shè)路線："<<endl;　　for(num=0,i=0;i<edgeNum;i++)　　{</b

18、>　　vex1=FindRoot(parent,edge[i].from);　　vex2=FindRoot(parent,edge[i].to);　　if(vex1!=vex2)　　{

19、　parent[vex1]=vex2;　　num++;　　cout<<"從居民區(qū)"<<edge[i].from<<"到"<<"居民區(qū)"<<edge[i].to<<"，路徑長(zhǎng)度為

20、:"<<edge[i].weight<<" 米"<<endl;　　edgeP[d].from=edge[i].from;　　edgeP[d].to=edge[i].to;　　d++;&l

21、t;p>　　Sum=Sum+edge[i].weight;　　if(num==vertexNum-1)return;　　}　　}　　}

22、;　　流程圖：　　N　　Y　　源程序代碼　　#ifndef Graph_H

23、　　#define Graph_H　　const int MaxVertex=10;　　const int MaxEdge=100;　　struct EdgeType　　{

24、　int from,to;　　int weight;　　};　　template<class Datatype>　　class Graph　　{

25、;　　public:　　Graph();　　~Graph(){}　　void Kruskal();　　void InsertSort();</p&g

26、t;　　void BubbleSort1();　　int FindRoot(int a[],int n);　　void outSum();　　void Price();　　void Print();<b

27、>　　private:　　Datatype vertex[MaxVertex];　　int Edge[MaxVertex][MaxVertex];　　EdgeType edge[MaxEdge];　　EdgeType edgeP[MaxEdge]

28、;　　int parent[MaxVertex];　　int vertexNum,edgeNum;　　int R[MaxEdge];　　int Sum;　　int price;</p&g

29、t;　　};　　#endif　　#include<iostream>　　using namespace std;　　#include "Graph.h&

30、quot;　　#include<graphics.h>　　#include<conio.h>　　#include <string>　　#include<iomanip>　　#incl

31、ude <fstream>　　template<class Datatype>　　Graph<Datatype>::Graph()　　{　　getch();&l

32、t;/p>　　int i,j,k,n,m;　　cout<<"請(qǐng)輸入居民區(qū)的個(gè)數(shù)：";　　cin>>vertexNum;　　cout<<endl;　　cout<<"分別

33、輸入居民區(qū)：";　　for(i=0;i<vertexNum;i++)　　cin>>vertex[i];　　cout<<"生成居民區(qū)序號(hào)表："<<endl;　　cout<<"┏━━

34、━";　　for(int g=0;g<vertexNum;g++){cout<<"┳━━━";}cout<<"┓"<<endl;　　cout<<"┃"<<left<<setw(6)<<"

35、居民區(qū)";　　for(int h=0;h<vertexNum;h++)　　{cout<<"┃"<<setw(6)<<vertex[h];}cout<<"┃"<<endl;　　cout<<

36、"┣━━━";　　for(int e=0;e<vertexNum;e++){cout<<"╋━━━";}cout<<"┫"<<endl;　　cout<<"┃"<<left<<setw(6)<&

37、lt;"序號(hào)";　　for(int f=0;f<vertexNum;f++){cout<<"┃"<<setw(6)<<f;}cout<<"┃"<<endl;　　cout<<"┗━━━";</p

38、>　　for(int t=0;t<vertexNum;t++){cout<<"┻━━━";}cout<<"┛"<<endl;　　getch();　　cout<<endl;&

39、lt;p>　　cout<<"請(qǐng)輸入網(wǎng)絡(luò)光纖鋪設(shè)路線的總條數(shù)：";　　cin>>edgeNum;　　cout<<endl;　　if(edgeNum>vertexNum*(vertexNum-1)/2)<

40、;b>　　{　　int c;　　cout<<"輸入條數(shù)有誤，請(qǐng)重新輸入!"<<endl;　　cin>>c;　　ed

41、geNum=c;　　}　　for(i=0;i<MaxVertex;i++)　　for(j=0;j<MaxVertex;j++)　　Edge[i][j]=0;　　cout<&l

42、t;"請(qǐng)按此格式輸入邊和權(quán)值：n, m, k（表示 n 居民區(qū)到 m 居民區(qū)的距離為 k 米）："<<endl;　　for(i=0;i<edgeNum;i++)　　{　　cin>>n>>m>>k;&l

43、t;/p>　　Edge[n][m]=k;　　Edge[m][n]=k;　　R[i]=k;　　}　　cout<<endl;<p&

44、gt;　　}　　template<class Datatype>　　void Graph<Datatype>::InsertSort()　　{　　int

45、k;　　for(int i=1;i<edgeNum;i++)　　{　　k=R[i];　　for(int j=i-1;k<R[j];j--)&

46、lt;p>　　{R[j+1]=R[j];}　　R[j+1]=k;　　}　　}　　template<class Datatype></p

47、>　　void Graph<Datatype>::BubbleSort1()　　{　　int count=0;　　while(count!=edgeNum)　　{</b&

48、gt;　　for(int i=0;i<vertexNum;i++)　　for(int j=i;j<vertexNum;j++)　　{　　if(Edge[i][j]==R[count])<p&g

49、t;　　{　　edge[count].from=i;　　edge[count].to=j;　　edge[count].weight=R[count];　　count++;

50、　　}　　}　　}　　}　　template<class Datatype></p&

51、gt;　　void Graph<Datatype>::Kruskal()　　{　　Sum=0;　　int i,b=0,d=0,num,vex1,vex2;　　fo

52、r(i=0;i<vertexNum;i++)　　parent[i]=-1;　　cout<<"選取光纖鋪設(shè)路線："<<endl;　　for(num=0,i=0;i<edgeNum;i++)　　{<

53、;/b>　　vex1=FindRoot(parent,edge[i].from);　　vex2=FindRoot(parent,edge[i].to);　　if(vex1!=vex2)　　{<p&g

54、t;　　parent[vex1]=vex2;　　num++;　　cout<<"從居民區(qū)"<<edge[i].from<<"到"<<"居民區(qū)"<<edge[i].to<<"，路徑

55、長(zhǎng)度為:"<<edge[i].weight<<" 米"<<endl;　　edgeP[d].from=edge[i].from;　　edgeP[d].to=edge[i].to;　　d++;

56、　　Sum=Sum+edge[i].weight;　　if(num==vertexNum-1)return;　　}　　}　　}</p

57、>　　template<class Datatype>　　int Graph<Datatype>::FindRoot(int parent[],int v)　　{　　int t=v;&l

58、t;/p>　　if(parent[t]>-1) t=parent[t];　　return t;　　}　　template<class Datatype>

59、;　　void Graph<Datatype>::outSum()　　{　　cout<<endl;　　cout<<"這 "<<vertexNum<<" 個(gè)居民區(qū)之間鋪設(shè)網(wǎng)絡(luò)光纖總長(zhǎng)度中最

60、短的長(zhǎng)度為："<<Sum<<" 米"<<endl;　　cout<<endl;　　}　　template<class Datatype>　　voi

61、d Graph<Datatype>::Price()　　{　　cout<<"請(qǐng)輸入單位長(zhǎng)度路線鋪設(shè)的價(jià)格（元）：";　　cin>>price;　　cout<<endl

62、;　　cout<<"所以,這 "<<vertexNum<<" 個(gè)居民區(qū)之間鋪設(shè)網(wǎng)絡(luò)光纖所需最小費(fèi)用為："<<Sum*price<<" 元"<<endl;　　}&l

63、t;p>　　template<class Datatype>　　void Graph<Datatype>::Print()　　{　　int x1,x2,y1,y2;　　initgraph(500,500)

64、;　　if(vertexNum>0){　　circle(100,200,25);　　outtextxy(100,200,vertex[0]);　　if(vertexNum>1){　　circle(250,100,25)

65、;　　outtextxy(250,100,vertex[1]);　　if(vertexNum>2){　　circle(150,350,25);　　outtextxy(150,350,vertex[2]);　　if(verte

66、xNum>3){　　circle(350,350,25);　　outtextxy(350,350,vertex[3]);　　if(vertexNum>4){　　circle(400,200,25);　　outtextx

67、y(400,200,vertex[4]);　　if(vertexNum>5)circle(250,250,25);　　outtextxy(250,250,vertex[5]);}}}}}　　for(int n=0,k=0;k<edgeNum;k++)<b

68、>　　{　　switch(edgeP[n].from)　　{　　case 0:{x1=100;y1=200;}break;　　case 1:{x1=250;y1=100;}break;

69、　　case 2:{x1=150;y1=350;}break;　　case 3:{x1=350;y1=350;}break;　　case 4:{x1=400;y1=200;}break;　　case 5:{x1=250;y1=250;}break;<

70、;b>　　}　　switch(edgeP[n].to)　　{　　case 0:{x2=100;y2=200;}break;　　case 1:{x2=250;y2=100;}break;

71、　　case 2:{x2=150;y2=350;}break;　　case 3:{x2=350;y2=350;}break;　　case 4:{x2=400;y2=200;}break;　　case 5:{x2=250;y2=250;}break;<

72、;b>　　}　　line(x1,y1,x2,y2);　　n++;　　}　　getch();

73、　　closegraph();　　}　　#include<iostream>　　using namespace std;　　#include "Graph.cpp"<p&g

74、t;　　#include<graphics.h>　　#include<conio.h>　　int main()　　{　　int a1;<p&g

75、t;　　for(a1=0;a1<25;a1++) 　　cout<<" "; 　　cout<<"網(wǎng)絡(luò)光纖鋪設(shè)的最佳方案選擇"<<endl; 　　for(a1=0;a1<21;a1++)

76、　　cout<<" "; 　　for(a1=0;a1<34;a1++) 　　cout<<"*"; 　　cout<<endl; 　　for(a1=0;a1<21;a1++) <

77、/p>　　cout<<" "; 　　cout<<"* *"<<endl;　　for(a1=0;a1<21;a1++) 　　cout<

78、<" "; 　　cout<<"* 歡迎使用本程序,希望本程序可以 *"; 　　cout<<endl; 　　for(a1=0;a1<21;a1++) 　　cout<<" &

79、quot;; 　　cout<<"* 幫您選擇最佳鋪設(shè)方案 *"; 　　cout<<endl; 　　for(a1=0;a1<21;a1++) 　　cout<<" ";&

80、lt;/p>　　cout<<"* *"; 　　cout<<endl; 　　for(a1=0;a1<21;a1++) 　　cout<<" "

81、;　　for(a1=0;a1<34;a1++)　　cout<<"*";　　cout<<endl;　　Graph<char>G;　　G.InsertSort();<

82、/p>　　G.BubbleSort1();　　G.Kruskal();　　G.outSum();　　G.Price ();　　getch();　　G.Print (

83、);　　cout<<endl;　　for(a1=0;a1<15;a1++) 　　cout<<" "; 　　for(a1=0;a1<25;a1++) 　　cout<<

84、;"*"; 　　cout<<endl; 　　for(a1=0;a1<15;a1++) 　　cout<<" "; 　　cout<<"* 謝謝您的使用 ! *&qu

85、ot;<<endl; 　　for(a1=0;a1<15;a1++) 　　cout<<" ";　　for(a1=0;a1<25;a1++)　　cout<<"*";

86、　　cout<<endl;　　return 0;　　}　　課程設(shè)計(jì)總結(jié)　　經(jīng)過(guò)兩個(gè)多星期的不懈努力，我們小組終于完成本次課程

87、設(shè)計(jì)一一《網(wǎng)絡(luò)光纖鋪設(shè)的最佳方案選擇》，我們選用克魯斯卡爾算法進(jìn)行程序設(shè)計(jì)。首先，我們對(duì)程序的大概框架進(jìn)行構(gòu)想，設(shè)計(jì)好基本的邏輯框架，然后針對(duì)克魯斯卡爾算法進(jìn)行程序編寫(xiě)，對(duì)于高級(jí)程序員來(lái)說(shuō)，雖然bug可以使程序崩潰，但他們依然可以閑庭信步般把問(wèn)題解決，可是對(duì)于我們這些正在成長(zhǎng)中的初級(jí)程序員來(lái)說(shuō)，那就是一個(gè)災(zāi)難，需要我們一起扛才能度過(guò)難關(guān)，于是我們的合作精神就被發(fā)揮得淋漓盡致了，不管對(duì)外還是對(duì)內(nèi)，我們這些菜鳥(niǎo)程序員都是一家子，處理分析問(wèn)題

88、就跟快，完成了編寫(xiě)，再經(jīng)過(guò)多次的調(diào)試，終于完成本次程序設(shè)計(jì)。　　通過(guò)本次程序設(shè)計(jì)，使我們對(duì)本學(xué)期學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)有了進(jìn)一步的了解，鞏固上一學(xué)年所學(xué)的知識(shí)；而且，我們對(duì)程序設(shè)計(jì)的算法有了基本的認(rèn)識(shí)，同時(shí)，讓我們知道算法對(duì)于一個(gè)程序來(lái)說(shuō)是非常重要的，好的程序就應(yīng)該要用好的算法；本次課程設(shè)計(jì)中涉及到圖形的處理，但我們對(duì)于圖形是一無(wú)所知的，經(jīng)過(guò)在多種渠道的查閱，最后通過(guò)使用C++圖形庫(kù)EasyX實(shí)現(xiàn)圖形處

89、理。　　本次程序設(shè)計(jì)使我們學(xué)會(huì)了很多，鞏固課本所學(xué)的知識(shí)的同時(shí)，也掌握一些課外的有關(guān)程序設(shè)計(jì)的知識(shí)，希望以后能夠編寫(xiě)出更好的程序！　　參考資料　　1、胡明《數(shù)據(jù)結(jié)構(gòu)》（C++版）清華大學(xué)出版社　　2、張勇《C++語(yǔ)

眾賞文庫(kù)> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

課程設(shè)計(jì)報(bào)告-- 小區(qū)網(wǎng)絡(luò)光纖的鋪設(shè)

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

課程設(shè)計(jì)報(bào)告-- 小區(qū)網(wǎng)絡(luò)光纖的鋪設(shè)

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載