可編輯版/可編輯版數據結構課程設計目錄一.設計目的2二.設計內容2三．概要設計11、功能模塊圖12、各個模塊詳細的功能描述1四．詳細設計21．主函數和其他函數的偽碼算法22、主要函數的程序流程圖63、函數之間的調用關系圖13五．測試數據及運行結果141．正常測試數據及運行結果142、非正常測試數據及運行結果15六．調試情況,設計技巧及體會17七．參考文獻17八．附錄：源代碼17一.設計目的課程設計是軟件設計的綜合訓練,包括問題分析、總體結構設計、用戶界面設計、程序設計基本技能和技巧。能夠在設計中逐步提高程序設計能力,培養科學的軟件工作方法。而且通過數據結構課程設計能夠在下述各方面得到鍛煉：1、能根據實際問題的具體情況,結合數據結構課程中的基本理論和基本算法,正確分析出數據的邏輯結構,合理地選擇相應的存儲結構,并能設計出解決問題的有效算法。2、提高程序設計和調試能力。通過上機實習,驗證自己設計的算法的正確性。學會有效利用基本調試方法,迅速找出程序代碼中的錯誤并且修改。3、培養算法分析能力。分析所設計算法的時間復雜度和空間復雜度,進一步提高程序設計水平。二.設計內容最小生成樹問題:設計要求：在n個城市之間建設網絡,只需保證連通即可,求最經濟的架設方法。存儲結構采用多種。求解算法多種。概要設計1、功能模塊圖開始開始創建一個圖功能選擇1.建立鄰接矩陣2.建立鄰接表3.PRIM算法4.kruscal算法結束2、各個模塊詳細的功能描述※創建一個圖：通過給用戶信息提示,讓用戶將城市信息及城市之間的聯系關系和連接權值寫入程序,并根據寫入的數據創建成一個圖。※功能選擇：給用戶提示信息,讓用戶選擇相應功能。※建立鄰接矩陣：將用戶輸入的數據整理成鄰接矩陣并顯現在屏幕上。※建立鄰接表：將用戶輸入的數據整理成臨接表并顯現在屏幕上。※PRIM算法：利用PRIM算法求出圖的最小生成樹,即：城市之間最經濟的連接方案。四．詳細設計1．主函數和其他函數的偽碼算法※主函數：voidmain<>{MGraphG;Dgevaluedgevalue;CreateUDG<G,dgevalue>; charu;cout<<"圖創建成功。";cout<<"請根據如下菜單選擇操作。\n";cout<<"*****************************************"<<endl;cout<<"**1、用鄰接矩陣存儲：********************"<<endl;cout<<"**2、用鄰接表存儲：**********************"<<endl;cout<<"**3、普里姆算法求最經濟的連接方案********"<<endl;cout<<"**4、克魯斯卡爾算法求最經濟的連接方案****"<<endl;cout<<"*****************************************"<<endl<<endl;ints;chary='y';while<y='y'>{cout<<"請選擇菜單："<<endl;cin>>s;switch<s>{case1:cout<<"用鄰接矩陣存儲為："<<endl;Adjacency_Matrix<G>;break;case2:cout<<"用鄰接表存儲為："<<endl;Adjacency_List<G,dgevalue>;break;case3:cout<<"普里姆算法最經濟的連接方案為:"<<endl;cout<<"請輸入起始城市名稱：";cin>>u;MiniSpanTree_PRIM<G,u>;break;case4:cout<<"克魯斯卡爾算法最經濟的連接方案為:"<<endl;MiniSpanTree_KRSL<G,dgevalue>;break;default: cout<<"您的輸入有誤!";break;}cout<<endl<<"是否繼續？y/n:";cin>>y;if<y=='n'>break;}}※鄰接矩陣和臨接表的創建：intCreateUDG<MGraph&G,Dgevalue&dgevalue>//構造無向加權圖的鄰接矩陣{inti,j,k;cout<<"請輸入城市個數及其之間的可連接線路數目：";cin>>G.vexnum>>G.arcnum;cout<<"請輸入各個城市名稱<分別用一個字符代替>：";for<i=0;i<G.vexnum;++i>cin>>G.vexs[i];for<i=0;i<G.vexnum;++i>//初始化數組for<j=0;j<G.vexnum;++j>{G.arcs[i][j].adj=MAX;}cout<<"請輸入兩個城市名稱及其連接費用<嚴禁連接重復輸入!>："<<endl;for<k=0;k<G.arcnum;++k>{cin>>dgevalue[k].ch1>>dgevalue[k].ch2>>dgevalue[k].value;i=LocateVex<G,dgevalue[k].ch1>;j=LocateVex<G,dgevalue[k].ch2>;G.arcs[i][j].adj=dgevalue[k].value;G.arcs[j][i].adj=G.arcs[i][j].adj;}returnOK;}※臨接矩陣的輸出：voidAdjacency_Matrix<MGraphG>//用鄰接矩陣存儲數據{ inti,j; for<i=0;i<G.vexnum;i++>{for<j=0;j<G.vexnum;j++>if<G.arcs[i][j].adj==MAX> cout<<0<<""; else cout<<G.arcs[i][j].adj<<"";cout<<endl;}}※鄰接表的輸出：voidAdjacency_List<MGraphG,Dgevaluedgevalue>//用鄰接表儲存數據{ inti,j; for<i=0;i<G.vexnum;i++> { cout<<G.vexs[i]<<"->"; for<j=0;j<G.arcnum;j++> if<dgevalue[j].ch1==G.vexs[i]&&dgevalue[j].ch2!=G.vexs[i]> cout<<dgevalue[j].ch2<<"->"; elseif<dgevalue[j].ch1!=G.vexs[i]&&dgevalue[j].ch2==G.vexs[i]> cout<<dgevalue[j].ch1<<"->"; cout<<"\b\b"<<endl; }}※最小生成樹PRIM算法：voidMiniSpanTree_PRIM<MGraphG,charu>//普里姆算法求最小生成樹{inti,j,k;Closedgeclosedge;k=LocateVex<G,u>;for<j=0;j<G.vexnum;j++>//輔助數組初始化 {if<j!=k>{closedge[j].adjvex=u;closedge[j].lowcost=G.arcs[k][j].adj;} }closedge[k].lowcost=0;for<i=1;i<G.vexnum;i++>{k=Minimum<G,closedge>;cout<<"城市"<<closedge[k].adjvex<<"與城市"<<G.vexs[k]<<"連接。"<<endl;closedge[k].lowcost=0;for<j=0;j<G.vexnum;++j>{if<G.arcs[k][j].adj<closedge[j].lowcost>{closedge[j].adjvex=G.vexs[k];closedge[j].lowcost=G.arcs[k][j].adj;}}}}intMinimum<MGraphG,Closedgeclosedge>//求closedge中權值最小的邊,并返回其頂點在vexs中的位置{inti,j;doublek=1000;for<i=0;i<G.vexnum;i++>{if<closedge[i].lowcost!=0&&closedge[i].lowcost<k>{k=closedge[i].lowcost;j=i;}}returnj;}※最小生成樹kruscal算法：voidMiniSpanTree_KRSL<MGraphG,Dgevalue&dgevalue>//克魯斯卡爾算法求最小生成樹{intp1,p2,i,j;intbj[MAX_VERTEX_NUM];//標記數組for<i=0;i<G.vexnum;i++>//標記數組初始化bj[i]=i;Sortdge<dgevalue,G>;//將所有權值按從小到大排序for<i=0;i<G.arcnum;i++>{p1=bj[LocateVex<G,dgevalue[i].ch1>];p2=bj[LocateVex<G,dgevalue[i].ch2>];if<p1!=p2>{cout<<"城市"<<dgevalue[i].ch1<<"與城市"<<dgevalue[i].ch2<<"連接。"<<endl;for<j=0;j<G.vexnum;j++>{if<bj[j]==p2>bj[j]=p1;}}}}voidSortdge<Dgevalue&dgevalue,MGraphG>//對dgevalue中各元素按權值按從小到大排序{inti,j;doubletemp;charch1,ch2;for<i=0;i<G.arcnum;i++>{for<j=i;j<G.arcnum;j++>{if<dgevalue[i].value>dgevalue[j].value>{temp=dgevalue[i].value;dgevalue[i].value=dgevalue[j].value;dgevalue[j].value=temp;ch1=dgevalue[i].ch1;dgevalue[i].ch1=dgevalue[j].ch1;dgevalue[j].ch1=ch1;ch2=dgevalue[i].ch2;dgevalue[i].ch2=dgevalue[j].ch2;dgevalue[j].ch2=ch2;}}}}2、主要函數的程序流程圖※main〔主函數※CreatUDG<>建圖函數※Adjacency_Matrix<>鄰接矩陣輸出函數※Adjacency_List<>鄰接表輸出函數※MiniSpanTree_PRIM<>普里姆算法：基本思想：假設WN=<V,{E}>是一個含有n個頂點的連通網,TV是WN上最小生成樹中頂點的集合,TE是最小生成樹中邊的集合。顯然,在算法執行結束時,TV=V,而TE是E的一個子集。在算法開始執行時,TE為空集,TV中只有一個頂點,因此,按普利姆算法構造最小生成樹的過程為：在所有"其一個頂點已經落在生成樹上,而另一個頂點尚未落在生成樹上"的邊中取一條權值為最小的邊,逐條加在生成樹上,直至生成樹中含有n-1條邊為止。在此系統中,N是你所需要輸入的城市個數。而每條邊的權值就是你所輸入的每兩個城市之間的建設成本。開始開始標志頂點1加入U集合尋找滿足邊的一個頂點在U,另一個頂點在V的最小邊形成n-1條邊的生成樹頂點k加入U修改由頂點k到其他頂點邊的權值結束得到最小生成樹※MiniSpanTree_KRSL<>克魯斯卡爾算法：基本思想：假設WN=〔V,{E}是一個含有N個頂點的連通網。則按照克魯斯卡爾算法構造最小生成樹的過程為：先構造一個只含n個頂點,而邊集為空的子圖,若將該子圖中各個頂點看成是各棵樹上的根結點,則它是一個含有n棵樹的一個森林。之后,從網的邊集E中選取一條權值最小的邊,若該條邊的兩個頂點分屬不同的樹,則將其加入子圖,也就是說,將這兩個頂點分別所在的兩棵樹合成一棵樹；反之,若該條邊的兩個頂點已落在同一棵樹上,則不可取,而應該取下一條權值最小的邊再試之。依次類推,直到森林中只有一棵樹,也即子圖中含有n-1條邊為止。在此系統中,N是你所需要輸入的城市個數。而每條邊的權值就是你所輸入的每兩個城市之間的建設成本。※LocateVex〔節點位置函數：※Minimum<>權值比較函數：※Sortdge<>權值排序函數：3、函數之間的調用關系圖五．測試數據及運行結果1．正常測試數據及運行結果2、非正常測試數據及運行結果六．調試情況,設計技巧及體會通過此次課程設計,我更深刻地理解了最小生成樹問題,知道如何在n個城市之間建設網絡,只需保證連通即可,求最經濟的架設方法。并且用了多種求解方式。數據結構是學習計算機的一門重要的基礎課,在學習數據結構之前我們學習了C語言在我們看來數據結構就是學習C語言的延續。這幾天的課程設計讓我充分地體會到了上機實踐對于計算機編程的重要性。其實在于計算機語言這類課程看重的就是上機的實際操作,不滿足于基本理論的學習。上機操作才能讓我們更加好的掌握我們所要學習的計算機語言知識。只顧學習理論是遠遠不夠的。實踐中可以發現許許多多的問題,然后通過同學老師的幫助,得以解決,讓自己的編程能力得到極大的提升。此外,也讓我更加明白編程是要解決現實問題的。只有擁有把現實問題理論化的能力,才是編程真正需要達到的境界。七．參考文獻《《新編C語言課程設計教程》》周二強編著清華大學出版社《《數據結構〔C語言版》》嚴蔚敏吳偉民編著清華大學出版社八．附錄：源代碼#include<stdio.h>#include<stdlib.h>#include<iostream.h>#defineMAX_VERTEX_NUM20#defineOK1#defineERROR0#defineMAX1000typedefstructArcell{doubleadj;}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{charvexs[MAX_VERTEX_NUM];//節點數組AdjMatrixarcs;//鄰接矩陣intvexnum,arcnum;//圖的當前節點數和弧數}MGraph;typedefstructPnode//用于普利姆算法{charadjvex;//節點doublelowcost;//權值}Pnode,Closedge[MAX_VERTEX_NUM];//記錄頂點集U到V-U的代價最小的邊的輔助數組定義typedefstructKnode//用于克魯斯卡爾算法中存儲一條邊及其對應的2個節點{charch1;//節點1charch2;//節點2doublevalue;//權值}Knode,Dgevalue[MAX_VERTEX_NUM];//intCreateUDG<MGraph&G,Dgevalue&dgevalue>;intLocateVex<MGraphG,charch>;intMinimum<MGraphG,Closedgeclosedge>;voidMiniSpanTree_PRIM<MGraphG,charu>;voidSortdge<Dgevalue&dgevalue,MGraphG>;voidAdjacency_Matrix<MGraphG>;voidAdjacency_List<MGraphG,Dgevaluedgevalue>;//intCreateUDG<MGraph&G,Dgevalue&dgevalue>//構造無向加權圖的鄰接矩陣{inti,j,k;cout<<"請輸入城市個數及其之間的可連接線路數目：";cin>>G.vexnum>>G.arcnum;cout<<"請輸入各個城市名稱<分別用一個字符代替>：";for<i=0;i<G.vexnum;++i>cin>>G.vexs[i];for<i=0;i<G.vexnum;++i>//初始化數組for<j=0;j<G.vexnum;++j>{G.arcs[i][j].adj=MAX;}cout<<"請輸入兩個城市名稱及其連接費用<嚴禁連接重復輸入!>："<<endl;for<k=0;k<G.arcnum;++k>{cin>>dgevalue[k].ch1>>dgevalue[k].ch2>>dgevalue[k].value;i=LocateVex<G,dgevalue[k].ch1>;j=LocateVex<G,dgevalue[k].ch2>;G.arcs[i][j].adj=dgevalue[k].value;G.arcs[j][i].adj=G.arcs[i][j].adj;}returnOK;}intLocateVex<MGraphG,charch>//確定節點ch在圖G.vexs中的位置{inta;for<inti=0;i<G.vexnum;i++>if<G.vexs[i]==ch>a=i;returna;}voidMiniSpanTree_PRIM<MGraphG,charu>//普里姆算法求最小生成樹{inti,j,k;Closedgeclosedge;k=LocateVex<G,u>;for<j=0;j<G.vexnum;j++>//輔助數組初始化 {if<j!=k>{closedge[j].adjvex=u;closedge[j].lowcost=G.arcs[k][j].adj;} }closedge[k].lowcost=0;for<i=1;i<G.vexnum;i++>{k=Minimum<G,closedge>;cout<<"城市"<<closedge[k].adjvex<<"與城市"<<G.vexs[k]<<"連接。"<<endl;closedge[k].lowcost=0;for<j=0;j<G.vexnum;++j>{if<G.arcs[k][j].adj<closedge[j].lowcost>{closedge[j].adjvex=G.vexs[k];closedge[j].lowcost=G.arcs[k][j].adj;}}}}intMinimum<MGraphG,Closedgeclosedge>//求closedge中權值最小的邊,并返回其頂點在vexs中的位置{inti,j;doublek=1000;for<i=0;i<G.vexnum;i++>{if<closedge[i].lowcost!=0&&closedge[i].lowcost<k>{k=closedge[i].lowcost;j=i;}}returnj;}voidMiniSpanTree_KRSL<MGraphG,Dgevalue&dgevalue>//克魯斯卡爾算法求最小生成樹{intp1,p2,i,j;intbj[MAX_VERTEX_NUM];//標記數組for<i=0;i<G.vexnum;i++>//標記數組初始化bj[i]=i;Sortdge<dgevalue,G>;//將所有權值按從小到大排序for<i=0;i<G.arcnum;i++>{p1=bj[LocateVex<G,dgevalue[i].ch1>];p2=bj[LocateVex<G,dgevalue[i].ch2>];if<p1!=p2>{cout<<"城市"<<dgevalue[i].ch1<<"與城市"<<dgevalue[i].ch2<<"連接。"<<endl;for<j=0;j<G.vexnum;j++>{if<bj[j]==p2>bj[j]=p1;}}}}voidSortdge<Dgevalue&dgevalue,MGraphG>//對dgevalue中各元素按權值按從小到大排序{inti,j;doubletemp;charch1,ch2;for<i=0;i<G.arcnum;i++>{for<j=i;j<G.arcnum;j++>{if<dgevalue[i].value>dgevalue[j].value>{temp=dgevalue[i].value;dgevalue[i].value=dgevalue[j].value;dgevalue[j].value=temp;ch1=dgevalue[i].ch1;dgevalue[i].ch1=dgevalue[j].ch1;dgevalue[j].ch1=ch1;ch2=dgevalue[i].ch2;dgevalue[i].ch2=dgevalue[j].ch2;dgevalue[j].ch2=ch2;}}}}voidAdjacency_Matrix<MGraphG>//用鄰接矩陣存儲數據{ inti,j; for<i=0;i<G.vexnum;i++>{for<j=0;j<G.vexnum;j++>if<G.arcs[i][j].adj==MAX> cout<<0<<""; else cout<<G.arcs[i][j].adj<<"";cout<<endl;}}voidAdjacency_List<MGraphG,Dgevalue