數(shù)據(jù)結構課程設計-最小生成樹問題

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

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

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

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

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

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

4、;p>　　1)提示輸入頂點數(shù)目；　　2)接受輸入，按照項目要求產(chǎn)生邊權值的隨機矩陣；然后求解最小生成樹；　　3)輸出最小生成樹并且退出；　　(6)測試數(shù)據(jù):9　　二概要設計:</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(){}　　//重載運算符

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); //判斷頂點x是否已與其它頂點連通　　};　　3. 自定義隊列，用于存放連通圖，或按權排列后的邊:　　class MyQueues<p&

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

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

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

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

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

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

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

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

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

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

22、;/p>　　//析構函數(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的實現(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、;　　}　　/*設置棧定元素*/　　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 坐標結構 */　　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)　　{}　　/*用鄰接矩陣表示的圖類，可以帶權，權不可以為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);//按權值大小排序插入　　bool bound(int x); //判斷頂點x是否已與其它頂點連通　　};　　//構造函數(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;　　}　　//構造函數(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];　　}　　//測試頂點x是否已與其他點連通　　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表示的邊，并且設置權　　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>　　}　　/*自定義隊列，用于存放連通圖，或按權排列后的邊*/　　class MyQueues　　{　　public:<

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

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

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

62、p>　　//邊按權值插入隊列中合適位置,　　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);　　}　　//將圖的連通分量插入隊列　　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、判斷是否構成回路　　void kruskal(const Graph& graph,Graph& smtree);//克魯斯卡爾算法　　void SmallestTreeOutput(const Graph& smtree); //輸出最小生成樹 　　void SetMatrix(int

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

69、t;　　cout<<"************************************************"<<endl;　　cout<<”標題:最小生成樹”<<endl;　　cout<<"班級:計本2班&quo

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

71、*********************"<<endl;　　cout<<"請輸入頂點數(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;　　}　　//用隨機數(shù)組初始化matrix數(shù)組并且打印　　void SetMatrix(int

74、 vexnum,int *pmatrix)　　{ 　　srand((unsigned)time(NULL));　　for(int i=0;i<vexnum;++i)//產(chǎ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的隨機整數(shù)作為邊的權值　　pmatrix[

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

78、lt;<vexnum<<"] ****\n";　　for( i=0;i<vexnum;++i)//輸出隨機權值矩陣　　{　　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;　　}　　四設計和調試分析　　1.在調試MyQueues類的時候，由于對數(shù)組的按行存儲理解的不夠好導致開始時未能獲得正確的數(shù)據(jù)，經(jīng)單步

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

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

溫馨提示

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

數(shù)據(jù)結構課程設計-最小生成樹問題

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結構課程設計-最小生成樹問題

文檔簡介

溫馨提示

最新文檔

評論

免費下載