新數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---圖的遍歷和生成樹(shù)求解實(shí)現(xiàn)

1、<p><b>　　數(shù) 據(jù) 結(jié) 構(gòu)</b></p><p>　　課 程 設(shè) 計(jì) 說(shuō) 明 書(shū)</p><p>　　2013年1月17日</p><p>　　設(shè)計(jì)目的(小標(biāo)題黑體五號(hào)字)</p><p>　　《數(shù)據(jù)結(jié)構(gòu)》課程主要介紹最常用的數(shù)據(jù)結(jié)構(gòu)，闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論其在計(jì)算機(jī)中的存儲(chǔ)表示，以及在

2、其上進(jìn)行各種運(yùn)算時(shí)的實(shí)現(xiàn)算法，并對(duì)算法的效率進(jìn)行簡(jiǎn)單的分析和討論。進(jìn)行數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)要達(dá)到以下目的：</p><p>　　了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；</p><p>　　初步掌握軟件開(kāi)發(fā)過(guò)程的問(wèn)題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能；</p><p>　　提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問(wèn)題的能力；&

3、lt;/p><p>　　訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開(kāi)發(fā)一般規(guī)范進(jìn)行軟件開(kāi)發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。</p><p>　　2 設(shè)計(jì)內(nèi)容和要求</p><p><b>　　設(shè)計(jì)內(nèi)容：</b></p><p>　　采用合適的存儲(chǔ)結(jié)構(gòu)來(lái)創(chuàng)建圖，并實(shí)現(xiàn)圖的遍歷；</p><p>　　（2）

4、計(jì)算圖的最小生成樹(shù)，求聯(lián)通分量</p><p><b>　　設(shè)計(jì)要求：</b></p><p>　?。?）先任意創(chuàng)建一個(gè)圖；</p><p>　?。?) 圖的DFS,BFS的遞歸和非遞歸算法的實(shí)現(xiàn)</p><p>　?。?) 最小生成樹(shù)（兩個(gè)算法）的實(shí)現(xiàn)，求連通分量的實(shí)現(xiàn)</p><

5、;p>　　（4) 要求用鄰接矩陣、鄰接表、十字鏈表多種結(jié)構(gòu)存儲(chǔ)實(shí)現(xiàn)</p><p>　　3．本設(shè)計(jì)所采用的數(shù)據(jù)結(jié)構(gòu)</p><p>　　(1) 選擇合適的數(shù)據(jù)結(jié)構(gòu)，并定義數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)體；</p><p>　　(2) 根據(jù)程序所要完成的基本要求和程序?qū)崿F(xiàn)提示，設(shè)計(jì)出完整的算法；</p><p>　　(3) 按格式要求寫(xiě)出課程設(shè)

6、計(jì)說(shuō)明書(shū)。</p><p><b>　　功能模塊詳細(xì)設(shè)計(jì)</b></p><p>　　4.1 詳細(xì)設(shè)計(jì)思想（個(gè)人負(fù)責(zé)模塊的NS流程圖）</p><p>　　4.2 核心代碼（個(gè)人負(fù)責(zé)模塊代碼）</p><p>　　//----------最小生成樹(shù)的普利姆算法-----------</p><p>

7、;　　typedef struct</p><p><b>　　{</b></p><p>　　int adjvex;</p><p>　　int lowcost;</p><p>　　}closedge;</p><p>　　int MiniSpanTree_PRIM(int g[][max],

8、int n)</p><p><b>　　{</b></p><p>　　int lowcost[max],prevex[max]; //lowcost[]存儲(chǔ)當(dāng)前集合分別到剩余結(jié)點(diǎn)的最小權(quán)值 //prevex[]存儲(chǔ)最短路徑的前一個(gè)結(jié)點(diǎn)</p><p>　　int i,j,k,min;</p><p>　　for(i=

9、2;i<=n;i++) //n個(gè)頂點(diǎn)，n-1條邊</p><p><b>　　{</b></p><p>　　lowcost[i]=g[1][i]; //初始化</p><p>　　prevex[i]=1; //頂點(diǎn)未加入到最小生成樹(shù)中</p><p><b>　　}</b></p>

10、;<p>　　lowcost[1]=0; //標(biāo)志頂點(diǎn)1加入U(xiǎn)集合</p><p>　　for(i=2;i<=n;i++) //形成n-1條邊的生成樹(shù)</p><p><b>　　{</b></p><p><b>　　min=inf;</b></p><p><b>

11、　　k=0;</b></p><p>　　for(j=2;j<=n;j++) //尋找滿足邊的一個(gè)頂點(diǎn)在U,另一個(gè)頂點(diǎn)在V的最小邊</p><p>　　if((lowcost[j]<min)&&(lowcost[j]!=0))</p><p><b>　　{</b></p><p>

12、;　　min=lowcost[j];</p><p><b>　　k=j;</b></p><p><b>　　}</b></p><p>　　cout<<"("<<prevex[k]-1<<","<<k-1<<"

13、)"<<min;</p><p>　　lowcost[k]=0; //頂點(diǎn)k加入U(xiǎn)</p><p>　　for(j=2;j<=n;j++) //修改由頂點(diǎn)k到其他頂點(diǎn)邊的權(quán)值</p><p>　　if(g[k][j]<lowcost[j])</p><p><b>　　{</b><

14、/p><p>　　lowcost[j]=g[k][j];</p><p>　　prevex[j]=k;</p><p><b>　　}</b></p><p>　　cout<<endl;</p><p><b>　　}</b></p><p>

15、<b>　　return 0;</b></p><p><b>　　}</b></p><p>　　//---------------------最小生成樹(shù)的克魯斯卡爾算法------------------------</p><p>　　int acrvisited[max];//克魯斯卡爾弧標(biāo)記數(shù)組</p>

16、;<p>　　int find(int acrvisited[],int f)</p><p><b>　　{</b></p><p>　　while(acrvisited[f]>0)f=acrvisited[f];</p><p><b>　　return f;</b></p><

17、p><b>　　}</b></p><p>　　typedef struct acr</p><p><b>　　{</b></p><p>　　int pre;//弧的一結(jié)點(diǎn)</p><p>　　int bak;//弧另一結(jié)點(diǎn)</p><p>　　int weight

18、;//弧的權(quán)</p><p><b>　　}edg;</b></p><p>　　void MiniSpanTREE_KRUSCAL(MGraph_L G,ALGraph gra)</p><p><b>　　{</b></p><p>　　edg edgs[max];</p><

19、;p>　　int i,j,k=0;</p><p>　　for(i=0;i!=G.vexnum;++i)</p><p>　　for(j=i;j!=G.vexnum;++j)</p><p><b>　　{</b></p><p>　　if(G.arcs[i][j].adj!=int_max)</p>

20、<p><b>　　{</b></p><p>　　edgs[k].pre=i;</p><p>　　edgs[k].bak=j;</p><p>　　edgs[k].weight=G.arcs[i][j].adj;</p><p><b>　　++k;</b></p>&

21、lt;p><b>　　}</b></p><p><b>　　}</b></p><p>　　int x,y,m,n;</p><p>　　int buf,edf;</p><p>　　for(i=0;i!=gra.arcnum;++i)</p><p>　　acrvi

22、sited[i]=0;</p><p>　　for(j=0;j!=G.arcnum;++j)</p><p><b>　　{</b></p><p>　　m=int_max;</p><p>　　for(i=0;i!=G.arcnum;++i)</p><p><b>　　{</b

23、></p><p>　　if(edgs[i].weight<m)</p><p><b>　　{</b></p><p>　　m=edgs[i].weight;</p><p>　　x=edgs[i].pre;</p><p>　　y=edgs[i].bak;</p>&

24、lt;p><b>　　n=i;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　buf=find(acrvisited,x);</p><p>　　edf=find(acrvisited,y);</p>

25、;<p>　　edgs[n].weight=int_max;</p><p>　　if(buf!=edf)</p><p><b>　　{</b></p><p>　　acrvisited[buf]=edf;</p><p>　　cout<<"("<<x<&

26、lt;","<<y<<")"<<m;</p><p>　　cout<<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</

27、b></p><p>　　4.3運(yùn)行結(jié)果（抓圖顯示）</p><p>　　5．課程設(shè)計(jì)心得及存在問(wèn)題</p><p>　　緊張而又充實(shí)的課程設(shè)計(jì)就要結(jié)束了，在這兩周的時(shí)間里，不僅檢驗(yàn)了我這學(xué)期所學(xué)的知識(shí)，也培養(yǎng)了我如何把握一件事情，如何把一件事情做的更好。在課程設(shè)計(jì)中，和同學(xué)們相互討論，相互學(xué)習(xí)，相互監(jiān)督，和老師相互交流，使得我學(xué)會(huì)了運(yùn)籌帷幄，學(xué)會(huì)了寬容，學(xué)會(huì)

28、了理解。這次課程設(shè)計(jì)對(duì)我來(lái)說(shuō)受益良多。</p><p>　　我這次課程設(shè)計(jì)所選的題目是圖的遍歷和生成樹(shù)的求解實(shí)現(xiàn)，這個(gè)題目是用我們這學(xué)期所學(xué)過(guò)的知識(shí)再加上我們之前所學(xué)過(guò)的編譯語(yǔ)言完成的。這其中包括，鄰接矩陣的定義和輸出，鄰接表的定義和輸出，隊(duì)列的定義，圖的兩種遍歷方法，包括圖的深度遍歷，圖的廣度遍歷，連通分量的求解，在求連通分量時(shí)又用到了圖的深度遍歷，最小生成樹(shù)的實(shí)現(xiàn)，包括普里木算法和克魯斯卡爾算法。</p