數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-最小生成樹問題

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

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

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

文檔簡介

1、　　課程設(shè)計(jì)報(bào)告　　課程名稱《數(shù)據(jù)結(jié)構(gòu)》 　　課題名稱最小生成樹問題 　　專業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 　　班級 10計(jì)本2班

2、 　　“最小生成樹問題”課程設(shè)計(jì)　　題目: 編制一個求出N個頂點(diǎn)圖的最小生成樹程序　　一需求分析:　　(1)在n個城市間建設(shè)通信網(wǎng)絡(luò)，只需要架設(shè)n-1條線路即可。以最低的代價建設(shè)這個通信網(wǎng)，即求圖的最小生成樹。

3、;　　(2)利用克魯斯卡爾算法求網(wǎng)的最小生成樹。　　(3)利用自定義的隊(duì)列結(jié)構(gòu)存放連通分量。　　(4)以文本形式輸出最小生成樹中的各條邊及它們的權(quán)值。輸出格式為(int a,int b,int n),其中a，b為頂點(diǎn)序號,n為ab邊的權(quán)；　　(5)程序運(yùn)行流程:<

4、;p>　　1)提示輸入頂點(diǎn)數(shù)目；　　2)接受輸入，按照項(xiàng)目要求產(chǎn)生邊權(quán)值的隨機(jī)矩陣；然后求解最小生成樹；　　3)輸出最小生成樹并且退出；　　(6)測試數(shù)據(jù):9　　二概要設(shè)計(jì):</p&

5、gt;　　1.表示邊的類定義和接口:　　class MyArc　　{　　public:　　int m_beginVex;　　int

6、m_endVex;　　int m_weight;　　MyArc(int beginVex,int endVex,int weight);　　MyArc(){}　　//重載運(yùn)算符

7、　　inline bool operator < (const MyArc& arc){ return m_weight<arc.m_weight;}　　inline bool operator == (const MyArc& arc){ return m_weight==arc.m_weight;}&l

8、t;p>　　inline bool operator > (const MyArc& arc){ return m_weight>arc.m_weight; }　　};　　2. 用鄰接矩陣表示的圖類的定義和接口:　　class Graph&l

9、t;/p>　　{　　private:　　int m_vexnum;　　int m_arcnum;　　int *m_pmatrix;<p&g

10、t;　　public:　　~Graph();　　Graph(int vexnum);　　Graph(int vexnum,int *pmatrix);　　void insert(MyArc arc

11、);//連通arc 邊　　bool bound(int x); //判斷頂點(diǎn)x是否已與其它頂點(diǎn)連通　　};　　3. 自定義隊(duì)列，用于存放連通圖，或按權(quán)排列后的邊:　　class MyQueues<p&

12、gt;　　{　　public:　　list<MyArc> m_list;　　MyQueues(){}　　void insert(const MyArc& arc); //按權(quán)值

13、大小排序插入　　void InsertGraph(const Graph &graph); //將圖的連通分量插入隊(duì)列　　MyArc pop();//出隊(duì)列　　};　　4.本程序的結(jié)構(gòu)&l

14、t;/p>　　1)主程序模塊:　　void main()　　{　　申明邊權(quán)值矩陣數(shù)組并用隨機(jī)函數(shù)初始化；　　創(chuàng)建圖；</p&

15、gt;　　調(diào)用克魯斯卡爾算法函數(shù)；　　輸出邊的權(quán)值矩陣，最小生成樹中的各條邊及它們的權(quán)值　　退出；　　}　　2)帶權(quán)的邊類模塊---實(shí)現(xiàn)帶權(quán)邊的存儲和運(yùn)算。

16、;　　鄰接矩陣類模塊---實(shí)現(xiàn)圖的狀態(tài)記錄和相關(guān)操作。　　自定義隊(duì)列類模塊---實(shí)現(xiàn)邊的按權(quán)存貯和相關(guān)操作。　　3)核心kruskal算法模塊---用克魯斯卡爾算法求出最小生成樹 　　各模塊調(diào)用關(guān)系:<b&

17、gt;　　三詳細(xì)設(shè)計(jì)　　#include<iostream>　　#include<stdlib.h>//產(chǎn)生隨機(jī)數(shù)組用　　#include<time.h> //同上　　//#include "basic.

18、h" //所用到的自定義數(shù)據(jù)結(jié)構(gòu)定義和實(shí)現(xiàn)文件　　using namespace std;　　#include<list>　　/*MyStack 堆棧類的結(jié)構(gòu) [ 0 1 ... curlen ... size] [棧底(bottom) ... prt ... ]*/

19、　　#define BASESIZE 64 //默認(rèn)堆棧數(shù)組空間大?。?*8）,可以自擴(kuò)充　　template <class Type> 　　class MyStack　　{

20、;　　private:　　Type *bottom; // 元素存放的動態(tài)數(shù)組 　　int size,ptr; // 堆棧大小和當(dāng)前棧頂元素索引　　public: <b&

21、gt;　　//構(gòu)造函數(shù)　　MyStack() 　　{　　bottom=new Type[BASESIZE];ptr=-1;size=BASESIZE;　　};<

22、;/p>　　//析構(gòu)函數(shù)　　~MyStack(){delete []bottom;};　　//清棧還原　　inline void clear()　　{

23、　　if(bottom!=NULL)　　delete []bottom;　　bottom=new Type[size];　　ptr=-1; 　　};<

24、/p>　　//判?？?lt;/b>　　inline bool IsEmpty()　　{　　if(ptr==-1) return true;　　else return false;&l

25、t;/p>　　}　　//入棧　　int push(Type e);　　//出棧　　int pop(Type &e);<

26、;/p>　　//獲得棧頂元素　　int top(Type &e);　　int settop(Type e);　　// 用callback函數(shù)對棧從低向上遍歷　　void traverse(void

27、callback(Type *),Type *); 　　private:　　inline int extent()　　{　　int s=size;　　Ty

28、pe *temp=new Type[size];　　for(int i=0;i<s;i++)　　temp[i]=bottom[i];　　size*=2;　　clear();

29、;　　ptr=s+1;　　for(int i=0;i<s;i++)　　bottom[i]=temp[i];　　delete [] temp;　　return size;<p&g

30、t;　　}　　};　　/*MyStack的實(shí)現(xiàn) */　　/*壓棧*/　　template <class Type> <

31、;p>　　int MyStack<Type>::push(Type e) // 　　{ 　　if(++ptr==size) extent();　　bottom[ptr]=e; 　　return ptr; &

32、lt;p>　　}　　/*出棧*/　　template <class Type> 　　int MyStack<Type>::pop(Type &e) // &l

33、t;b>　　{　　if(ptr==-1)　　return -2;//?？?，返回 -2 ！　　else 　　e=bottom[ptr--]; 　　ret

34、urn ptr;　　}　　/*獲取棧頂元素*/　　template <class Type>　　int MyStack<Type>::top(Type &e) // <p&

35、gt;　　{　　if(ptr==-1)　　return -1;//?？?返回 -1 ！　　else　　e=bottom[ptr];　　return ptr

36、;　　}　　/*設(shè)置棧定元素*/　　template <class Type>　　int MyStack<Type>::settop(Type e) //<b&g

37、t;　　{　　if(ptr==-1)　　return -1;//棧空,返回 -1 ！　　else　　bottom[ptr]=e;　　return ptr;

38、;　　}　　/*用callback函數(shù)對棧從低向上遍歷*/　　template <class Type>　　void MyStack<Type>::traverse(void callback(Type *),Type *e)&l

39、t;/p>　　{　　if(callback!=NULL)　　{　　for(int i=0;i<=ptr;i++)　　{<

40、;/p>　　e=&bottom[i];　　callback(e);　　}　　}　　}; // &l

41、t;p>　　/*MyPoint 坐標(biāo)結(jié)構(gòu) */　　typedef struct MyPoint　　{　　int x, y;　　} *pMyPoint;<p&g

42、t;　　//　　/*表示邊的類*/　　class MyArc　　{　　public:<p&

43、gt;　　int m_beginVex;　　int m_endVex;　　int m_weight;　　MyArc(int beginVex,int endVex,int weight);　　MyArc(){}

44、　　bool operator < (const MyArc& arc)　　{　　return m_weight<arc.m_weight;　　}　　bool

45、 operator == (const MyArc& arc)　　{　　return m_weight==arc.m_weight;　　}　　bool operator > (con

46、st MyArc& arc)　　{　　return m_weight>arc.m_weight;　　}　　};<p

47、>　　MyArc::MyArc(int beginVex,int endVex,int weight):m_beginVex(beginVex),m_endVex(endVex),m_weight(weight)　　{}　　/*用鄰接矩陣表示的圖類，可以帶權(quán)，權(quán)不可以為0*/<p&

48、gt;　　class Graph　　{　　public:　　int m_vexnum;　　int m_arcnum;　　int *m_pmatrix;&l

49、t;/p>　　public:　　~Graph();　　Graph(int vexnum);　　Graph(int vexnum,int *pmatrix);　　void

50、 insert(MyArc arc);//按權(quán)值大小排序插入　　bool bound(int x); //判斷頂點(diǎn)x是否已與其它頂點(diǎn)連通　　};　　//構(gòu)造函數(shù)　　Graph::Graph(i

51、nt vexnum)　　{　　m_pmatrix=new int[vexnum*vexnum];　　m_vexnum=vexnum;m_arcnum=0;　　for(int i=0;i<vexnum*vexnum;++i) m_

52、pmatrix[i]=0;　　}　　//構(gòu)造函數(shù)　　Graph::Graph(int vexnum,int *pmatrix)　　{&

53、lt;p>　　m_vexnum=vexnum;　　// m_arcnum=arcnum;　　m_pmatrix=new int[m_vexnum*m_vexnum];　　for(int i=0;i<m_vexnum*m_vexnum;++i)　　m_pmatr

54、ix[i]=pmatrix[i];　　}　　//測試頂點(diǎn)x是否已與其他點(diǎn)連通　　bool Graph::bound(int x)　　{　　for(int

55、 i=0;i<m_vexnum;++i) if(m_pmatrix[x+i*m_vexnum]!=0) return true;　　return false;　　}　　//在鄰接表中連通 arc表示的邊，并且設(shè)置權(quán)　　void

56、Graph::insert(MyArc arc)　　{　　m_pmatrix[arc.m_beginVex*m_vexnum+arc.m_endVex]=arc.m_weight;　　m_pmatrix[arc.m_endVex*m_vexnum+arc.m_beginVex

57、]=arc.m_weight;　　++m_arcnum;　　}　　Graph::~Graph()　　{　　delete[] m_pmatrix;</

58、p>　　}　　/*自定義隊(duì)列，用于存放連通圖，或按權(quán)排列后的邊*/　　class MyQueues　　{　　public:<

59、/p>　　list<MyArc> m_list;　　MyQueues(){}　　void insert(const MyArc& arc);//邊按權(quán)值插入隊(duì)列中合適位置,　　void InsertGraph(const Graph &graph);//將圖

60、的連通分量插入隊(duì)列　　MyArc pop();　　};　　//邊出隊(duì)　　MyArc MyQueues::pop()　　{</b&g

61、t;　　MyArc arc=m_list.front();　　m_list.pop_front(); 　　return arc;　　}<

62、p>　　//邊按權(quán)值插入隊(duì)列中合適位置,　　void MyQueues::insert(const MyArc& arc)　　{　　list<MyArc>::iterator pos=m_list.begin();<p&

63、gt;　　while(pos!=m_list.end())　　{　　if(*pos>arc) break;　　else ++pos;　　}　　m_l

64、ist.insert(pos,arc);　　}　　//將圖的連通分量插入隊(duì)列　　void MyQueues::InsertGraph(const Graph &graph)　　{</

65、p>　　for(int i=0;i<graph.m_vexnum;++i)　　{　　for(int j=i+1;j<graph.m_vexnum;++j)　　if(graph.m_pmatrix[i*graph.m_vexnum+j])

66、 insert(MyArc(i,j,graph.m_pmatrix[i*graph.m_vexnum+j]));　　}　　}　　bool IsCycle(Graph &graph,MyArc& arc); //

67、判斷是否構(gòu)成回路　　void kruskal(const Graph& graph,Graph& smtree);//克魯斯卡爾算法　　void SmallestTreeOutput(const Graph& smtree); //輸出最小生成樹 　　void SetMatrix(int

68、vexnum,int *matrix); //用隨機(jī)數(shù)組初始化matrix數(shù)組并且打印　　/*主函數(shù)*/　　void main()　　{　　char i;</b&g

69、t;　　cout<<"************************************************"<<endl;　　cout<<”標(biāo)題:最小生成樹”<<endl;　　cout<<"班級:計(jì)本2班&quo

70、t;<<endl;　　cout<<"姓名:張娟"<<endl;　　cout<<"學(xué)號:10012121 "<<endl;　　cout<<"***************************

71、*********************"<<endl;　　cout<<"請輸入頂點(diǎn)數(shù)目:";　　cin>>i;　　int vex=i-'0';　　i

72、nt *matrix=new int[vex*vex];　　cout<<endl;　　SetMatrix(vex,matrix); 　　Graph graph(vex,matrix),smtree(vex);　　kruskal(graph,smtree

73、);　　SmallestTreeOutput(smtree);　　delete []matrix;　　}　　//用隨機(jī)數(shù)組初始化matrix數(shù)組并且打印　　void SetMatrix(int

74、 vexnum,int *pmatrix)　　{ 　　srand((unsigned)time(NULL));　　for(int i=0;i<vexnum;++i)//產(chǎn)生隨機(jī)權(quán)值矩陣　　{</b

75、>　　for(int j=i;j<vexnum;++j)　　{ 　　if(j==i)　　{　　p

76、matrix[i*vexnum+j]=0;　　continue;　　}　　int rnum=rand();rnum%=99;rnum++;//產(chǎn)生1~99的隨機(jī)整數(shù)作為邊的權(quán)值　　pmatrix[

77、i*vexnum+j]=rnum;　　pmatrix[j*vexnum+i]=rnum;　　}　　}　　cout<<"***隨機(jī)產(chǎn)生的各邊權(quán)值矩陣 [頂點(diǎn)數(shù)為 "&

78、lt;<vexnum<<"] ****\n";　　for( i=0;i<vexnum;++i)//輸出隨機(jī)權(quán)值矩陣　　{　　for(int j=0;j<vexnum;++j)<b

79、>　　{ 　　cout<<pmatrix[i*vexnum+j]<<"\t";　　}　　cout<<endl;　　}</

80、b>　　}　　//判斷連通邊arc后圖graph 是否存在回路 　　bool IsCycle(Graph& graph, MyArc& arc) 　　{</p&g

81、t;　　list<int> mylist;　　mylist.push_back(arc.m_beginVex);　　int *ps=new int[graph.m_vexnum];　　for(int i=0;i<graph.m_vexnum;++i)

82、　　ps[i]=0;　　while(!mylist.empty())　　{　　int x=mylist.front();　　ps[x]=1;

83、　　mylist.pop_front();　　for(int i=0;i<graph.m_vexnum;++i)　　{　　if(graph.m_pmatrix[i+x*graph.m_vexnum]!=0)

84、　　{　　if(i==arc.m_endVex) return true;　　if(ps[i]!=1) mylist.push_back(i);　　}　　}&

85、lt;/b>　　}　　delete[] ps; 　　return false;　　}　　//克魯斯卡爾算法&l

86、t;/p>　　void kruskal(const Graph& graph,Graph& smtree)　　{　　MyQueues arcqueues;//保存從小到大排列的邊　　arcqueues.InsertGraph(gra

87、ph);　　MyArc myarc;//Arc表示邊的類型　　int arcnum=0; //邊的個數(shù)　　while(arcnum<graph.m_vexnum-1)　　{　　myarc

88、=arcqueues.pop();　　if(!IsCycle(smtree,myarc))　　{　　smtree.insert(myarc);　　++arcnum;<

89、p>　　}　　}　　}　　//輸出最小生成樹　　void SmallestTreeOutput(const Gra

90、ph& smtree)　　{　　cout<<"最小生成樹:"<<endl;　　for(int i=0;i<smtree.m_vexnum;++i)//輸出最小樹　　for(in

91、t j=i+1;j<smtree.m_vexnum;++j)　　if(smtree.m_pmatrix[i*smtree.m_vexnum+j]) cout<<'('<<i<<','<<j<<','<<smtree.m_pmatrix[i

92、*smtree.m_vexnum+j]<<')'<<endl;　　}　　四設(shè)計(jì)和調(diào)試分析　　1.在調(diào)試MyQueues類的時候，由于對數(shù)組的按行存儲理解的不夠好導(dǎo)致開始時未能獲得正確的數(shù)據(jù)，經(jīng)單步

93、跟蹤調(diào)試后發(fā)現(xiàn)下標(biāo)超出范圍，修正后即可正常運(yùn)行。　　2.在本實(shí)驗(yàn)中，自定義了3個類，定義了基于它們的數(shù)據(jù)和操作，它們是本程序的實(shí)現(xiàn)基礎(chǔ)。　　3.由于翻譯核心算法 kruskal的時間復(fù)雜度與邊的數(shù)目的函數(shù)有線性關(guān)系，同時IsCycle函數(shù)含有while和for循環(huán)，在頂點(diǎn)數(shù)目不多的時候，算法時間很快，適用于稀疏矩陣。 <p&

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

溫馨提示

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-最小生成樹問題

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-最小生成樹問題

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載