算法程序設計實驗報告

1、程序設計課程設計姓 名：王學 號：20100034班 級：軟件工程00班指導教師： 王會青 成 績：2010年6月實驗一.構造可以使n個城市連接的最小生成樹專業(yè)：_軟件工程_ 班級：_軟件 姓名：_王_ 學號：_20100034完成日期：_2010/6/26_一、【問題描述】給定一個地區(qū)的n個城市間的距離網(wǎng)，用Prim算法或Kruskal算法建立最小生成樹，并計算得到的最小生成樹的代價。1 城市間的道路網(wǎng)采用鄰接矩陣表示，鄰接矩陣的存儲結構定義采用課本中給出的定義，若兩個城市之間不存在道路，則將相應邊的權值設為自己定義的無窮大值。2 顯示出城市間道路網(wǎng)的鄰接矩陣。3 最小生成樹中包括的邊及其權

2、值，并顯示得到的最小生成樹的總代價。4 輸入城市數(shù)、道路數(shù)輸入城市名輸入道路信息執(zhí)行Kruskal 算法執(zhí)行 Prim 算法輸出最小生成樹二、【問題分析】1. 抽象數(shù)據(jù)類型結構體數(shù)組的定義：#ifndef ADJACENCYMATRIXED/防止該頭文件被重復引用#define ADJACENCYMATRIXED/而引起的數(shù)據(jù)重復定義#define INFINITY32767/最大值#define MAX_VERTEX_NUM20/最大頂點個數(shù)typedef intVRType;/權值，即邊的值typedef charInfoType;/附加信息的類型，后面使用時會定義成一個指針typedef

3、 charVertexTypeMAX_VERTEX_NUM;/頂點類型typedef enum DG=1, DN, UDG, UDN GraphKind;/有向圖，有向網(wǎng)，無向圖，無向網(wǎng)typedef struct ArcCellVRTypeadj;/VRType 是頂點關系類型。對無權圖，用 1 或 0 表示相鄰否；對帶權圖，則為權值類型。InfoType*info;/該弧關系信息的指針ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexTypevexsMAX_VERTEX_NUM;/頂點向量AdjMatrix

4、arcs;/鄰接矩陣intvexnum, arcnum;/圖的當前頂點數(shù)和弧數(shù)GraphKindkind;/圖的種類標志MGraph;typedef struct/普里姆算法輔助數(shù)組的定義VertexTypeadjvex;VRTypelowcost;closedgeMAX_VERTEX_NUM;#endif/結束if2 程序模塊MGraph G;/網(wǎng) G，唯一的全局變量int main(int argc, char * argv);/主函數(shù)Status LocateVex(MGraph G, VertexType v);/判斷城市 v 在網(wǎng) G 中的位置Status CreateUDN(MGr

5、aph &G);/創(chuàng)建網(wǎng) G 的鄰接矩陣void DisplayNet(MGraph G);/以鄰接矩陣的形式顯示網(wǎng) Gvoid MiniSpanTree_KRUSKAL(MGraph G);/最小生成樹的 Kruskal 算法void MiniSpanTree_PRIM(MGraph G, VertexType u);/最小生成樹的 Prim 算法Status Minimum(closedge closeEdge, int n); /Prim 算法中求下一個城市的函數(shù)void DeleteInfo(MGraph &G);/釋放堆內存上動態(tài)申請的空間3.流程圖創(chuàng)建用鄰接矩陣表示

6、的城市道路網(wǎng)輸入城市數(shù)G.vexnum、道路數(shù)G.arcnum輸入城市名G.vexsi輸入表示道路的兩個城市及道路值G.arcsij.adj返回 OKPrim算法化輔助數(shù)組closeEdgefor (i=1; i<G.vexnum; +i)求下一個城市k = Minimum(closeEdge, G.vexnum)輸出找到的道路標記城市，避免重復輸出總耗費4.數(shù)據(jù)類型定義為了用鄰接矩陣表示圖 G ，先是定義二維數(shù)組的每一個元素含道路值然后在圖的定義中定義一個此二維數(shù)組的結構成員。并且在圖中還定義一個用來存放城市的一維數(shù)組及int 型的城市數(shù)級道路數(shù)。用二維數(shù)組的兩個下標表示道路，這兩個下

7、標又在一位數(shù)組中對應兩個城市。這樣就建立起了一個城市到城市之間的道路網(wǎng)。4. 程序主要模塊說明：該程序共含5個模塊，本人負責其中2個模塊構造：*LocateVex(MGraph G, VertexType v)*Status LocateVex(MGraph G, VertexType v);while (strcmp(G.vexsi, v) i+;返回 i；* CreateUDN*輸入城市數(shù)、道路數(shù)；for (i=0; i<城市數(shù); +i) 輸入城市名；for (i=0; i<城市數(shù); +i)for(j=0; j<城市數(shù); +j)初始化鄰接矩陣：道路值= INFINITY;

8、for (i=0; i<城市數(shù); +i)for(j=0; j<城市數(shù); +j)輸入兩個城市表示道路，輸入道路值；PRIM算法* MiniSpanTree_PRIM*void MiniSpanTree_PRIM(MGraph G, VertexType u)定義輔助數(shù)組：closedge closeEdge;初始化：strcpy(closeEdgej.adjvex, u);closeEdgej.lowcost = G.arcskj.adj;for (i=1; i<G.vexnum; +i)在其余G.vexnum-1個城市中找到離輔助數(shù)組中標記的道路最小值；顯示找到的道路；標記新

9、找到的城市；* Minimum*Status Minimum(closedge closeEdge, int n)在輔助數(shù)組中找到道路值最小的道路的兩點城市：if (closeEdgei.lowcost != 0) && (minTemp > closeEdgei.lowcost)返回該城市在 G 中的位置三、【功能實現(xiàn)】#include <iostream.h>#include <stdio.h>#include <string.h>#include <windows.h>#include "TypeDefine

10、.h"#include "AdjacencyMatrix.h"#include "InitializeFunction.h"#include "MiniSpanTree_KRUSKAL.h"#include "MiniSpanTree_PRIM.h"#include "DisplayNet.h"#include "DeleteInfo.h"MGraph G;/全局變量Gint main(int argc, char * argv);/主函數(shù)Status Locate

11、Vex(MGraph G, VertexType v);/判斷城市 v 在網(wǎng) G 中的位置Status CreateUDN(MGraph &G);/創(chuàng)建網(wǎng) G 的鄰接矩陣void DisplayNet(MGraph G);/以鄰接矩陣的形式顯示網(wǎng) Gvoid MiniSpanTree_KRUSKAL(MGraph G);/最小生成樹的 Kruskal 算法void MiniSpanTree_PRIM(MGraph G, VertexType u);/最小生成樹的 Prim 算法Status Minimum(closedge closeEdge, int n);/Prim 算法中求下一個

12、城市的函數(shù)void DeleteInfo(MGraph &G);/釋放堆內存上動態(tài)申請的空間int main(int argc, char * argv)CreateGraph(G);DisplayNet(G);MiniSpanTree_KRUSKAL(G);MiniSpanTree_PRIM(G, G.vexs0);DeleteInfo(G);cout<<endl<<endl;system("pause");return 0;/intializeFunction.hStatus CreateDG(MGraph &G)return 0

13、;Status CreateDN(MGraph &G)return 0;Status CreateUDG(MGraph &G)return 0;Status CreateUDN(MGraph &G);Status LocateVex(MGraph G, VertexType v)/判斷輸入的頂點v在G中的位置。/根據(jù)頂點的類型，可重載此函數(shù)。目前為charint i=0;while (strcmp(G.vexsi, v) i+;return i;Status CreateGraph(MGraph &G)/采用數(shù)組（鄰接矩陣）表示法，構造圖G.G.kind = U

14、DN;/默認構造無向網(wǎng)/*printf("+n");printf("|1:有向圖 2:無向圖 3:有向網(wǎng) 4:無向網(wǎng)n");printf("|請選擇: bb");scanf("%d", &G.kind);printf("+n");*/switch (G.kind)case DG: return CreateDG(G);/構造有向圖Gcase DN: return CreateDN(G);/構造有向網(wǎng)Gcase UDG: return CreateUDG(G);/構造無向圖Gcase UD

15、N: return CreateUDN(G);/構造無向網(wǎng)Gdefault : return ERROR;/CreateGraphStatus CreateUDN(MGraph &G)/采用數(shù)組（鄰接矩陣）表示法，構造圖G.int i, j, k;VertexType v1, v2;VRType w;printf(" 構造可以使N個城市連接的最小生成樹n");printf("請輸入城市數(shù)、道路數(shù)(至少6個城市，10條道路)：");cin>>G.vexnum>>G.arcnum;for (i=0; i<G.vexnum

16、; +i)/構造頂點向量printf("請輸入第 %d 個城市名（共 %d 個）:", i+1, G.vexnum);cin>>G.vexsi;for (i=0; i<G.vexnum; +i)/初始化鄰接矩陣for (j=0; j<G.vexnum; +j)G.arcsij.adj = INFINITY;/G. = NULL;printf("請輸入一條道路連接的兩個城市名及權值:n");for (k=0; k<G.arcnum; +k)/構造鄰接矩陣printf("共%3d條道路，第%3d條

17、道路：", G.arcnum,k+1);cin>>v1>>v2>>w;/輸入一條邊依附的頂點及權值i = LocateVex(G, v1);/確定v1、v2在G中的位置j = LocateVex(G, v2);G.arcsij.adj = w;/弧<v1,v2>的權值G.arcsji = G.arcsij;/置<v1,v2>的對稱弧<v2,v1>return OK;/CreateUDN/MiniSpan Tree PRIM.hStatus Minimum(closedge closeEdge, int n)int

18、 i, flag, minTemp = INFINITY;for (i=0; i<n; +i)if (closeEdgei.lowcost != 0) && (minTemp > closeEdgei.lowcost)minTemp = closeEdgei.lowcost;flag = i;return flag;void MiniSpanTree_PRIM(MGraph G, VertexType u)/用普里姆算法從第 u 個頂點出發(fā)構造網(wǎng) G 的最小生成樹 T，輸出 T 的各條邊。/記錄從頂點集 U 到 V-U 的代價最小的邊的輔助數(shù)組定義見 "A

19、djacencyMatrix.h"int i, j, k, totalCost=0;closedge closeEdge;k = LocateVex(G, u);for (j=0; j<G.vexnum; +j)/輔助數(shù)組初始化if (j != k)strcpy(closeEdgej.adjvex, u);closeEdgej.lowcost = G.arcskj.adj;cout<<"nn+n"cout<<"|用Prim算法求最小生成樹的各條邊依次為：n-"closeEdgek.lowcost = 0;/初始，U

20、=u;for (i=1; i<G.vexnum; +i)/選擇其余 G.vexnum-1 個頂點k = Minimum(closeEdge, G.vexnum);/求出 T 的下一個結點：第 k 頂點/此時 closeEdgek.lowcost = MINcloseEdgevi.lowcost | closeEdgevi.lowcost > 0, viV-Ucout<<'<'<<closeEdgek.adjvex<<','<<G.vexsk<<'>'/輸出生成樹的

21、邊totalCost += closeEdgek.lowcost;closeEdgek.lowcost = 0;/第 k 頂點并入 U 集for (j=0; j<G.vexnum; +j)if (G.arcskj.adj < closeEdgej.lowcost)/新頂點并入 U 后重新選擇最小邊strcpy(closeEdgej.adjvex, G.vexsk);closeEdgej.lowcost = G.arcskj.adj;cout<<"n|總代價："<<totalCost<<endl;cout<<&quo

22、t;+/n"/MiniSpanTree四、【實例測試及運行結果】五、【心得體會】通過本周的課程設計，我有不少收獲。既鞏固和加深了對數(shù)據(jù)結構的理解，認識到數(shù)據(jù)結構是計算機專業(yè)一門重要的專業(yè)技術基礎課程，還提高了我綜合運用本課程所學知識的能力。而且，并不是單純的看看教材就能解決我們的實際問題，所以還要去查找各種我們所需要的資料，所以這次課程設計也培養(yǎng)了我選用參考書，查閱手冊及文獻資料的能力。要完成一個課程設計的課題并不是一次就能編譯成功的，中間會出現(xiàn)很多的大問題小問題，改錯是個很繁瑣的問題。通過這次課程設計培養(yǎng)了我獨立思考，深入研究，分析問題，解決問題的能力。在以后的學習過程中我將要注意

23、以下幾點：1、認真上好專業(yè)實驗課，多在實踐中鍛煉自己。2、寫程序的過程要考慮周到，嚴密。3、在做設計的時候要有信心，有耐心，切勿浮躁。4、認真的學習課本知識，掌握課本中的知識點，并在此基礎上學會靈活運用。5、在課余時間里多寫程序，熟練掌握在調試程序的過程中所遇到的常見錯誤，以便能節(jié)省調試程序的時間。實驗二：統(tǒng)計數(shù)字 專業(yè)：_軟件工程_ 班級：_軟件_ 姓名：_王_ 學號：_20100034完成日期：_2010/6/28_1.【問題描述】 某次科研調查時得到了n個自然數(shù)，每個數(shù)均不超過1500000000（1.5*109）。已知不相同的數(shù)不超過10000個，現(xiàn)在需要統(tǒng)計這些自然數(shù)各自出現(xiàn)的次數(shù)，

24、并按照自然數(shù)從小到大的順序輸出統(tǒng)計結果。 2【設計需求及分析】 （1）設計要求 原始數(shù)據(jù)保存在文件count.in中，文件包含n+1行。第1行是整數(shù)n(1<=n<=200000)，表示自然數(shù)的個數(shù)；第2n+1行每行一個自然數(shù)。 結果保存在文件count的尾部，其中結果包含m行（m為n個自然數(shù)中不相同數(shù)的個數(shù)），按照自然數(shù)從小到大的順序輸出。每行輸出兩個整數(shù)，分別是自然數(shù)和該數(shù)出現(xiàn)的次數(shù)，其間用一個空格隔開。 (2)設計思路 首先必須有文件的打開和關閉語句，將文件的內容讀取到數(shù)組a中，然后對數(shù)組進行排列和對比，計數(shù)。最終輸出數(shù)據(jù)和次數(shù)。并寫入文件的尾部。 A為容納數(shù)據(jù)的數(shù)組，fope

25、n為文件打開函數(shù)，fscanf為文件讀取函數(shù)，然后進行冒泡排序。排序之后的內容由while設置條件，用if進行判斷。在不等于時，中間嵌套了一個while循環(huán)，進行往后的排查。最后輸出數(shù)據(jù)和次數(shù)。 下面是關鍵步驟： FILE* fp=fopen("count.txt","a+"); /用只讀/的方式打開文件 if(fp=NULL) printf("無文件"); /若沒有文件則返回1 return -1; for(i=0;i<9;i+) fscanf(fp,"%d",&ai); /讀取文件 fscanf(

26、fp,"n"); int j,t; for (i=1;i<9;i+) for(j=0;j<9-i;j+) if(aj>aj+1) /冒泡排序 t=aj; aj=aj+1; aj+1=t; for(i=0;i<9;i+) count=1; if (ai!=ai+1) printf("%dt%dn",ai,count); fprintf(fp,"%dt%dn",ai,ai); i+; 對數(shù)字的循環(huán)查找和控制條件， if(ai = ai + 1) while(ai = ai + 1) count+; i+; （3）輸

27、出輸入格式 輸入時，為豎行依此輸入文件，且為數(shù)字。且為9個以內的數(shù)字。 輸出時，分為兩行，第一列為數(shù)據(jù)，第二列為次數(shù)。 3. 【設計功能的實現(xiàn)】 #include <stdio.h> int main() int a100; /創(chuàng)建容納文件數(shù)據(jù)的數(shù)組 int i; FILE* fp=fopen("count.txt","a+"); /用只讀/的方式打開文件 if(fp=NULL) printf("無文件"); /若沒有文件則返回1 return -1; for(i=0;i<9;i+) fscanf(fp,"

28、%d",&ai); /讀取文件 fscanf(fp,"n"); int j,t; for (i=1;i<9;i+) for(j=0;j<9-i;j+) if(aj>aj+1) /冒泡排序 t=aj; aj=aj+1; aj+1=t; printf("結果為：n數(shù)據(jù) 結果n"); int count; for(i=0;i<9;i+) count=1; if(ai!=ai+1) printf("%dt%dn",ai,count); printf(fp,"%dt%dn",ai,a

29、i); i+; if(ai = ai + 1) while(ai = ai + 1) count+; i+; printf("%dt%dn", ai, count); fprintf(fp,"%dt%dn", ai, count); fclose(fp); /關閉文件 return 0; 4【實例測試及運行結果】 5.【心得體會】 本次實驗使我對于文件的打開和關閉語句有了更深的理解。有打開必須有關閉。同時在這次的設計中，我學習到了用泛洪算法解決實際問題的基本思維和步驟。使我對算法的層次性更加清楚，更加加深了對算法的理解。實驗三送 貨專業(yè)：_軟件工程_ 班

30、級：_軟件 姓名：_王_ 學號：_20100034完成日期：_2010/6/26_1.【問題描述】小明希望設計一個方案，從編號為1的交叉路口出發(fā)，每次必須沿街道去往街道另一端的路口，再從新的路口出發(fā)去往下一個路口，直到所有的街道都經過了正好一次。輸入數(shù)據(jù)格式輸入的第一行包含兩個整數(shù)n, m(1n10, n-1m20)，表示交叉路口的數(shù)量和街道的數(shù)量，交叉路口從1到n標號。接下來m行，每行兩個整數(shù)a, b，表示和標號為a的交叉路口和標號為b的交叉路口之間有一條街道，街道是雙向的，小明可以從任意一端走向另一端。兩個路口之間最多有一條街道。輸出輸出格式如果小明可以經過每條街道正好一次，則輸出一行包含

31、m+1個整數(shù)p1, p2, p3, ., pm+1，表示小明經過的路口的順序，相鄰兩個整數(shù)之間用一個空格分隔。如果有多種方案滿足條件，則輸出字典序最小的一種方案，即首先保證p1最小，p1最小的前提下再保證p2最小，依此類推。如果不存在方案使得小明經過每條街道正好一次，則輸出一個整數(shù)-1。測試數(shù)據(jù)一輸入：輸出：4 51 21 31 42 43 41 2 4 1 3 4輸出說明：城市的地圖和小明的路徑如下圖所示。測試數(shù)據(jù)二輸入：輸出：4 61 21 31 42 43 42 3-1輸出說明：城市的地圖如下圖所示，不存在滿足條件的路徑。2【問題分析】 該算法使用歐拉回路，對于歐拉圖，從一個節(jié)點出發(fā)，從

32、某個節(jié)點開始，然后查出一個從這個出發(fā)回到這個點的環(huán)路徑。這種方法不保證每個邊都被遍歷。如果有某個點的邊沒有被遍歷就讓這個點為起點，這條邊為起始邊，把它和當前的環(huán)銜接上。這樣直至所有的邊都被遍歷。這樣，整個圖就被連接到一起了。具體步驟:1。如果此時與該點無相連的點，那么就加入路徑中2。如果該點有相連的點，那么就加入隊列之中，遍歷這些點，直到沒有相連的點。3。處理當前的點，刪除走過的這條邊，并在其相鄰的點上進行同樣的操作，并把刪除的點加入到路徑中去。4。這個其實是個遞歸過程。3【功能實現(xiàn)】#include<iostream> #include<stack> #include

33、<vector> #include<algorithm> #include<cstdio>#include <windows.h>using namespace std; const int maxn=10005; stack<int> st; vector<int> vecmaxn; bool mapmaxnmaxn; int vismaxn; int cpmaxn; int n,m; void pd(int a) cpa=1; vector<int>:iterator it; for(it=veca.beg

34、in();it!=veca.end();it+) if(!cp*it) pd(*it); void dfs(int a) vector<int>:iterator it; for(it=veca.begin();it!=veca.end();it+) if(!mapa*it) mapa*it=1; map*ita=1; dfs(*it); st.push(*it); void prt() st.push(1); while(!st.empty() /printf("%d ",st.top(); int ss=st.top(); st.pop(); printf(

35、"%d ",ss); int main() int num=0; /memset(cp,0,sizeof(cp); /memset(vis,0,sizeof(vis); /memset(map,0,sizeof(map); for(int i=0;i<maxn;+i) cpi=visi=0; scanf("%d %d",&n,&m); int a,b; for(int i=0;i<m;+i) scanf("%d %d",&a,&b); veca.push_back(b); vecb.push

36、_back(a); visa+; visb+; int flag=0; pd(1); for(int i=1;i<=n;+i) if(cpi=0) flag=1; else break; if(flag) printf("-1n"); else for(int i=1;i<=n;+i) sort(veci.begin(),veci.end(); if(visi%2=1) +num; if(num=0|num=2) if(num=2) if(vis1%2=1) dfs(1); prt(); else printf("-1n"); else df

37、s(1); prt(); else printf("-1n"); system("Pause"); return 0; 4 【實驗結果】5【心得體會】 通過這個實驗，我掌握了歐拉回路的基本思想。明白了用歐拉算法解決實際問題的具體步驟。而且明白了用算法解決實際問題的思維方法。 實驗4.消除類游戲 專業(yè)：_軟件工程_ 班級：_軟件 姓名：_王_ 學號：_20100034完成日期：_2010/6/28_1【問題描述】消除類游戲是深受大眾歡迎的一種游戲，游戲在一個包含有n行m列的游戲棋盤上進行，棋盤的每一行每一列的方格上放著一個有顏色的棋子，當一行或一列上有連續(xù)

38、三個或更多的相同顏色的棋子時，這些棋子都被消除。當有多處可以被消除時，這些地方的棋子將同時被消除?，F(xiàn)在給你一個n行m列的棋盤(1n,m30)，棋盤中的每一個方格上有一個棋子，請給出經過一次消除后的棋盤。請注意：一個棋子可能在某一行和某一列同時被消除。輸入數(shù)據(jù)格式：輸入的第一行包含兩個整數(shù)n, m，用空格分隔，分別表示棋盤的行數(shù)和列數(shù)。接下來n行，每行m個整數(shù)，用空格分隔，分別表示每一個方格中的棋子的顏色。顏色使用1至9編號。輸出數(shù)據(jù)格式：輸出n行，每行m個整數(shù)，相鄰的整數(shù)之間使用一個空格分隔，表示經過一次消除后的棋盤。如果一個方格中的棋子被消除，則對應的方格輸出0，否則輸出棋子的顏色編號?！緶y

39、試數(shù)據(jù)】為方便調試程序，可將輸入數(shù)據(jù)先寫入一個文本文件，然后從文件讀取數(shù)據(jù)處理，這樣可避免每次運行程序時都要從鍵盤輸入數(shù)據(jù)。測試數(shù)據(jù)一輸入：輸出：4 52 2 3 1 23 4 5 1 42 3 2 1 32 2 2 4 42 2 3 0 23 4 5 0 42 3 2 0 30 0 0 4 4輸出說明：棋盤中第4列的1和第4行的2可以被消除，其他的方格中的棋子均保留。測試數(shù)據(jù)二輸入：輸出：4 52 2 3 1 23 1 1 1 12 3 2 1 32 2 3 3 32 2 3 0 23 0 0 0 02 3 2 0 32 2 0 0 0輸出說明：棋盤中所有的1以及最后一行的3可以被同時消除，其他的方格中的棋子均保留。