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

1、 安徽省巢湖學(xué)院計(jì)算機(jī)與信息工程學(xué)院課程設(shè)計(jì)報(bào)告課程名稱 數(shù)據(jù)結(jié)構(gòu) 課題名稱 最小生成樹問題 專業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 班級(jí) 10計(jì)本2班 學(xué)號(hào)10012121 姓名 聯(lián)系方式 指導(dǎo)教師 20 11 年 12 月 30 日 “最小生成樹問題”課程設(shè)計(jì)題目: 編制一個(gè)求出n個(gè)頂點(diǎn)圖的最小生成樹程序一 需求分析:(1)在n個(gè)城市間建設(shè)通信網(wǎng)絡(luò)，只需要架設(shè)n-1條線路即可。以最低的代價(jià)建設(shè)這個(gè)通信網(wǎng)，即求圖的最小生成樹。 (2)利用克魯斯卡爾算法求網(wǎng)的最小生成樹。(3)利用自定義的隊(duì)列結(jié)構(gòu)存放連通分量。(4)以文本形式輸出最小生成樹中的各條邊及它們的權(quán)值。輸出格式為(int a,int b,int n

2、),其中a，b為頂點(diǎn)序號(hào),n為ab邊的權(quán)；(5)程序運(yùn)行流程: 1)提示輸入頂點(diǎn)數(shù)目； 2)接受輸入，按照項(xiàng)目要求產(chǎn)生邊權(quán)值的隨機(jī)矩陣；然后求解最小生成樹； 3)輸出最小生成樹并且退出；(6)測試數(shù)據(jù):9二 概要設(shè)計(jì):1.表示邊的類定義和接口:class myarcpublic: int m_beginvex; int m_endvex; int m_weight; myarc(int beginvex,int endvex,int weight); myarc() /重載運(yùn)算符 inline bool operator (const myarc& arc) return m_weight (

3、const myarc& arc) return m_weightarc.m_weight; ;2. 用鄰接矩陣表示的圖類的定義和接口:class graphprivate: int m_vexnum; int m_arcnum; int *m_pmatrix;public: graph(); graph(int vexnum); graph(int vexnum,int *pmatrix); void insert(myarc arc);/連通arc 邊 bool bound(int x); /判斷頂點(diǎn)x是否已與其它頂點(diǎn)連通;3. 自定義隊(duì)列，用于存放連通圖，或按權(quán)排列后的邊:class m

4、yqueuespublic: list m_list; myqueues() void insert(const myarc& arc); /按權(quán)值大小排序插入 void insertgraph(const graph &graph); /將圖的連通分量插入隊(duì)列 myarc pop();/出隊(duì)列;4.本程序的結(jié)構(gòu)1)主程序模塊:void main()申明邊權(quán)值矩陣數(shù)組并用隨機(jī)函數(shù)初始化；創(chuàng)建圖；調(diào)用克魯斯卡爾算法函數(shù)；輸出邊的權(quán)值矩陣，最小生成樹中的各條邊及它們的權(quán)值退出；2)帶權(quán)的邊類模塊-實(shí)現(xiàn)帶權(quán)邊的存儲(chǔ)和運(yùn)算。鄰接矩陣類模塊-實(shí)現(xiàn)圖的狀態(tài)記錄和相關(guān)操作。自定義隊(duì)列類模塊-實(shí)現(xiàn)邊的按權(quán)存貯

5、和相關(guān)操作。3)核心kruskal算法模塊-用克魯斯卡爾算法求出最小生成樹 各模塊調(diào)用關(guān)系:三 詳細(xì)設(shè)計(jì)#include#include/產(chǎn)生隨機(jī)數(shù)組用#include /同上/#include basic.h /所用到的自定義數(shù)據(jù)結(jié)構(gòu)定義和實(shí)現(xiàn)文件using namespace std;#include/*mystack 堆棧類的結(jié)構(gòu) 0 1 . curlen . size 棧底(bottom) . prt . */#define basesize 64 /默認(rèn)堆棧數(shù)組空間大?。?*8）,可以自擴(kuò)充template class mystackprivate: type *bottom; /

6、元素存放的動(dòng)態(tài)數(shù)組 int size,ptr; / 堆棧大小和當(dāng)前棧頂元素索引public: /構(gòu)造函數(shù) mystack() bottom=new typebasesize;ptr=-1;size=basesize; ; /析構(gòu)函數(shù) mystack()delete bottom; /清棧還原 inline void clear() if(bottom!=null) delete bottom; bottom=new typesize; ptr=-1; ; /判棧空 inline bool isempty() if(ptr=-1) return true; else return false;

7、/入棧 int push(type e); /出棧 int pop(type &e); /獲得棧頂元素 int top(type &e); int settop(type e); / 用callback函數(shù)對(duì)棧從低向上遍歷 void traverse(void callback(type *),type *); private: inline int extent() int s=size; type *temp=new typesize; for(int i=0;is;i+) tempi=bottomi; size*=2; clear(); ptr=s+1; for(int i=0;is;i

8、+) bottomi=tempi; delete temp; return size; ;/*mystack的實(shí)現(xiàn) */*壓棧*/template int mystack:push(type e) / if(+ptr=size) extent(); bottomptr=e; return ptr; /*出棧*/template int mystack:pop(type &e) / if(ptr=-1) return -2;/棧空，返回 -2 ！ else e=bottomptr-; return ptr;/*獲取棧頂元素*/template int mystack:top(type &e) /

9、 if(ptr=-1) return -1;/?？?返回 -1 ！ else e=bottomptr; return ptr;/*設(shè)置棧定元素*/template int mystack:settop(type e) / if(ptr=-1) return -1;/棧空,返回 -1 ！ else bottomptr=e; return ptr;/*用callback函數(shù)對(duì)棧從低向上遍歷*/template void mystack:traverse(void callback(type *),type *e) if(callback!=null) for(int i=0;i=ptr;i+) e

10、=&bottomi; callback(e); ; / /*mypoint 坐標(biāo)結(jié)構(gòu) */typedef struct mypoint int x, y; *pmypoint;/*表示邊的類*/class myarcpublic: int m_beginvex; int m_endvex; int m_weight; myarc(int beginvex,int endvex,int weight); myarc() bool operator (const myarc& arc) return m_weight (const myarc& arc) return m_weightarc.m_

11、weight; ;myarc:myarc(int beginvex,int endvex,int weight):m_beginvex(beginvex),m_endvex(endvex),m_weight(weight)/*用鄰接矩陣表示的圖類，可以帶權(quán)，權(quán)不可以為0*/class graphpublic: int m_vexnum; int m_arcnum; int *m_pmatrix;public: graph(); graph(int vexnum); graph(int vexnum,int *pmatrix); void insert(myarc arc);/按權(quán)值大小排序插入

12、 bool bound(int x); /判斷頂點(diǎn)x是否已與其它頂點(diǎn)連通;/構(gòu)造函數(shù)graph:graph(int vexnum) m_pmatrix=new intvexnum*vexnum; m_vexnum=vexnum;m_arcnum=0; for(int i=0;ivexnum*vexnum;+i) m_pmatrixi=0;/構(gòu)造函數(shù)graph:graph(int vexnum,int *pmatrix) m_vexnum=vexnum; / m_arcnum=arcnum; m_pmatrix=new intm_vexnum*m_vexnum; for(int i=0;im_v

13、exnum*m_vexnum;+i) m_pmatrixi=pmatrixi;/測試 頂點(diǎn)x是否已與其他點(diǎn)連通bool graph:bound(int x) for(int i=0;im_vexnum;+i) if(m_pmatrixx+i*m_vexnum!=0) return true; return false;/在鄰接表中連通 arc表示的邊，并且設(shè)置權(quán)void graph:insert(myarc arc) m_pmatrixarc.m_beginvex*m_vexnum+arc.m_endvex=arc.m_weight; m_pmatrixarc.m_endvex*m_vexnu

14、m+arc.m_beginvex=arc.m_weight; +m_arcnum;graph:graph() delete m_pmatrix;/*自定義隊(duì)列，用于存放連通圖，或按權(quán)排列后的邊*/class myqueuespublic: list m_list; myqueues() void insert(const myarc& arc);/邊按權(quán)值插入隊(duì)列中合適位置, void insertgraph(const graph &graph);/將圖的連通分量插入隊(duì)列 myarc pop();/邊出隊(duì)myarc myqueues:pop() myarc arc=m_list.front(

15、); m_list.pop_front(); return arc;/邊按權(quán)值插入隊(duì)列中合適位置,void myqueues:insert(const myarc& arc) list:iterator pos=m_list.begin(); while(pos!=m_list.end() if(*posarc) break; else +pos; m_list.insert(pos,arc);/將圖的連通分量插入隊(duì)列void myqueues:insertgraph(const graph &graph) for(int i=0;igraph.m_vexnum;+i) for(int j=i

16、+1;jgraph.m_vexnum;+j) if(graph.m_pmatrixi*graph.m_vexnum+j) insert(myarc(i,j,graph.m_pmatrixi*graph.m_vexnum+j); bool iscycle(graph &graph,myarc& arc); /判斷是否構(gòu)成回路void kruskal(const graph& graph,graph& smtree);/克魯斯卡爾算法void smallesttreeoutput(const graph& smtree); /輸出最小生成樹 void setmatrix(int vexnum,in

17、t *matrix); /用隨機(jī)數(shù)組初始化matrix數(shù)組并且打印/*主函數(shù)*/void main()char i;cout*endl;cout”標(biāo)題:最小生成樹”endl;cout班級(jí):計(jì)本2班endl;cout姓名:張娟endl;cout學(xué)號(hào):10012121 endl;cout*endl; couti; int vex=i-0; int *matrix=new intvex*vex; coutendl; setmatrix(vex,matrix); graph graph(vex,matrix),smtree(vex); kruskal(graph,smtree); smallesttr

18、eeoutput(smtree); delete matrix;/用隨機(jī)數(shù)組初始化matrix數(shù)組并且打印void setmatrix(int vexnum,int *pmatrix) srand(unsigned)time(null); for(int i=0;ivexnum;+i)/產(chǎn)生隨機(jī)權(quán)值矩陣 for(int j=i;jvexnum;+j) if(j=i) pmatrixi*vexnum+j=0; continue; int rnum=rand();rnum%=99;rnum+;/產(chǎn)生199的隨機(jī)整數(shù)作為邊的權(quán)值 pmatrixi*vexnum+j=rnum; pmatrixj*ve

19、xnum+i=rnum; cout*隨機(jī)產(chǎn)生的各邊權(quán)值矩陣 頂點(diǎn)數(shù)為 vexnum *n; for( i=0;ivexnum;+i)/輸出隨機(jī)權(quán)值矩陣 for(int j=0;jvexnum;+j) coutpmatrixi*vexnum+jt; coutendl; /判斷連通邊arc后 圖graph 是否存在回路 bool iscycle(graph& graph, myarc& arc) list mylist; mylist.push_back(arc.m_beginvex); int *ps=new intgraph.m_vexnum; for(int i=0;igraph.m_vex

20、num;+i) psi=0; while(!mylist.empty() int x=mylist.front(); psx=1; mylist.pop_front(); for(int i=0;igraph.m_vexnum;+i) if(graph.m_pmatrixi+x*graph.m_vexnum!=0) if(i=arc.m_endvex) return true; if(psi!=1) mylist.push_back(i); delete ps; return false;/克魯斯卡爾算法void kruskal(const graph& graph,graph& smtree) myqueues arcqueues;/保存從小到大排列的邊 arcqueues.insertgraph(graph); myarc myarc;/arc表示邊的類型 int arcnum=0;