1、*實踐教學* 蘭州理工大學計算機與通信學院2012年春季學期 算法與數(shù)據(jù)結(jié)構(gòu) 課程設計題 目：_專業(yè)班級：_姓 名：_學 號： 指導教師： 李 睿 成 績：_目 錄摘 要21采用類C語言定義相關(guān)數(shù)據(jù)類型22各模塊流程圖及偽碼算法33函數(shù)的調(diào)用關(guān)系圖104調(diào)試分析115測試結(jié)果126.源程序（見附錄）18設計總結(jié)19參考文獻20致 謝20附件 任務一源程序代碼21 摘 要很多涉及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的，該設計要求寫一個程序，演示出圖遍歷的過程，并給出圖的生成樹（網(wǎng)的最小代價生成樹）。通過該題目的設計過程，可以加深理解圖數(shù)據(jù)結(jié)構(gòu)及隊列的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及圖的深度優(yōu)先和廣度優(yōu)先遍

2、歷過程，掌握圖數(shù)據(jù)據(jù)結(jié)構(gòu)上基本運算的實現(xiàn)，進一步理解和熟練掌握課本中所學的各種數(shù)據(jù)結(jié)構(gòu)，學會如何把學到的知識用于解決實際問題，培養(yǎng)動手能力。關(guān)鍵字：圖；深度優(yōu)先遍歷；廣度優(yōu)先遍歷；生成樹1采用類C語言定義相關(guān)數(shù)據(jù)類型圖存儲結(jié)構(gòu)的定義：1）順序存儲（鄰接矩陣）#define MAX_VERTEX_NUM 30 /最大頂點個數(shù)Typedef enumDG,DN,UDG,UDN GraphKind; /圖的種類：有向圖、有向網(wǎng)、無向圖、無向網(wǎng)ArcTypeAdjMtrixMAX_VERTEX_NUMMAX_VERTEX_NUM; /ArcType是頂點關(guān)系類型，對無權(quán)圖，用0和1表示是否相鄰，對于網(wǎng)

3、，則為權(quán)值類型typedef struct VertexType vexMAX_VERTEX_NUM; /頂點數(shù)組 AdjMtrix arc; /鄰接矩陣 int vexnum,arcnum; /圖中的頂點數(shù)和邊數(shù) GraphKind kind; /圖的種類 GraphMtrix; （2） 鄰接表的存儲 #define MAX_VERTEX_NUM 30 /最大頂點個數(shù) typedef struct EdgeNode /表結(jié)點 int adjvex; /邊或弧依賴的頂點序號 InfType *info; /弧或邊的相關(guān)信息，在網(wǎng)中則為權(quán)值 struct EdgeNode *next; Edge

4、Node; typedef struct VexNode /頂點元素 VertexType vextex; EdgeNode *link; VexNode,AdjListMAX_VERTEX_NUM; typedef struct /鄰接表 AdjList vertices; int vexnum,arcnum; /圖中的頂點數(shù)和邊數(shù) GraphKind kind; /圖的種類 AdjListGrap2各模塊流程圖及偽碼算法(1) 遍歷算法 a.深度優(yōu)先遍歷void DFS(AdjListGraph G,int v)/圖G采用鄰接表存儲結(jié)構(gòu)，v是遍歷起始 點在鄰接表中的下標值，其下標從0開始v

5、isitedv=1; /置已訪問標志visite(G.verticesv.vextex); /訪問頂點 for (p = G.verticesv.link; p; p = p-next) if (!visitedp-adjvex)DFS(G,p-adjvex); /當前頂點未訪問，繼續(xù)深度優(yōu)先遍歷 / DFSb.廣度優(yōu)先遍歷void BFS(AdjListGrap G,intv) /圖G采用鄰接表存儲結(jié)構(gòu)，v是遍歷起始點在鄰接表中的下標，鄰接表中下標從0開始，以隊列作為基本輔助數(shù)據(jù)結(jié)構(gòu)InitQueue(Q); /初始化隊列Q visitedv=1; /置已訪問標志visite(G.verti

6、cesv. vextex); /訪問頂點EnQueue(Q,v); /被訪問頂點入隊 while (!QueueEmpty(Q) DeQueue(Q,v); /出隊列 for (p = G.verticesv.link; p; p = p-next) /找所有和v相鄰接的頂點 if (!visitedp-adjvex)visitedp-adjvex=1; visite(G.vertices p-adjvex.vextex); EnQueue(Q,p-adjvex); /if /while / BFS(2)流程圖a.深度優(yōu)先遍歷dfstraInt i,j;i=0i!=gra.vexnumvisi

7、tedi=0+iYj=0j!=gra.vexnumNMultiplex+jreturn0NYb.廣度優(yōu)先遍歷BfstraInt i,j;i=0i!=gra.vexnumvisitedi=0+iYj=0j!=gra.vexnumNMultiplex+jreturn0NYc.Prim算法Int lowcostmax ,prevexmaxi=2i=nlowcosti=g1ii +Ylowcost1=0ivexsi)；/*訪問頂點vi*/ visitedi=TRUE； for(j=0；jn；j+) /*依次搜索vi的鄰接點*/ if(G-edgesij=1&!visitedj) DFSM(G，j)/*

8、(vi，vj)E，且vj未訪問過，故vj為新出發(fā)點 DFSM*/說明：對于具有n個頂點和e條邊的無向圖或有向圖，遍歷算法DFSTraverse對圖中每頂點至多調(diào)用一次DFS或DFSM。從DFSTraverse中調(diào)用DFS(或DFSM)及DFS(或DFSM)內(nèi)部遞歸調(diào)用自己的總次數(shù)為n。 當訪問某頂點vi時，DFS(或DFSM)的時間主要耗費在從該頂點出發(fā)搜索它的所有鄰接點上。用鄰接矩陣表示圖時，其搜索時間為O(n)；用鄰接表表示圖時，需搜索第i個邊表上的所有結(jié)點。因此，對所有n個頂點訪問，在鄰接矩陣上共需檢查n2個矩陣元素，在鄰接表上需將邊表中所有O(e)個結(jié)點檢查一遍。 所以，DFSTrav

9、erse的時間復雜度為O(n2) （調(diào)用DFSM）或0(n+e)b.深度優(yōu)先遍歷：void BFS(AdjListGrap G,intv) /圖G采用鄰接表存儲結(jié)構(gòu)，v是遍歷起始點在鄰接表中的下標，鄰接表中下標從0開始，以隊列作為基本輔助數(shù)據(jù)結(jié)構(gòu)InitQueue(Q); /初始化隊列Q visitedv=1; /置已訪問標志visite(G.verticesv. vextex); /訪問頂點EnQueue(Q,v); /被訪問頂點入隊 while (!QueueEmpty(Q) DeQueue(Q,v); /出隊列 for (p = G.verticesv.link; p; p = p-ne

10、xt) /找所有和v相鄰接的頂點 if (!visitedp-adjvex) visitedp-adjvex=1; visite(G.vertices p-adjvex.vextex); EnQueue(Q,p-adjvex); /if /while / BFSPrim算法：voidPrimAlgorithm(GraphMtrix G,VertexType u)k = VerIndex(G,u); /k為頂點u在圖G中的序號for(i=0; i G.vernum; i+) /輔助數(shù)組初始化 if(i!=k) closedgei.lowcost = G.arc ki; /當前頂點不在生成樹上，應

11、存儲該邊上的權(quán)closedgei. adjvex = k; /依附的在U中的頂點序號初始為k /ifclosedgek.lowcost = 0; /將頂點u并入最小生成樹集合，即U=uor(i = 0; i 0,vV-Uprintf(closedgek. adjvex, G. vexk); closedgek.lowcost = 0; /將k對應的頂點并入最小生成樹集合，for(j = 0; j G.vernum; j+)if(G.arckj closedgej.lowcost)closedgej.lowcost = G.arcskj;closedgej. adjvex = k; /if /f

12、or / PrimAlgorithm 圖的存儲函數(shù)圖的創(chuàng)建函數(shù)3函數(shù)的調(diào)用關(guān)系圖隊列初始化函數(shù)顯示圖鄰接表函數(shù)入隊函數(shù)出對函數(shù)顯示圖鄰接矩陣函數(shù)深度優(yōu)先遍歷函數(shù) 主函數(shù)廣度優(yōu)先遍歷函數(shù)最小生成樹PRIM算法最小生成樹KRUSCAL圖的連通分量函數(shù)4調(diào)試分析a.調(diào)試中遇到的問題及對問題的解決方法在調(diào)試過程中遇到了種種錯誤，一些錯誤歸屬于同一類，總結(jié)起來，有以下方面（附帶有解決方法）：（1） 頭文件加載不正確，缺少了，。加載了相應的頭文件后相應錯誤和警告不再提示。（2） 函數(shù)返回值有具體類型是，但是標注為: void .在程序?qū)彶楹蟾臑榱苏_的返回類型。（3） 數(shù)次插入結(jié)點時，插入位置計算有誤，打

13、印結(jié)果與事實不符，進一步計算后調(diào)試正確。（4） 用switch() case ,做選擇菜單，沒有定義default ,當命令提示符顯示菜單后，對于選項之外的選擇，程序無法處理。補充后程序完善。b.算法的時間復雜度和空間復雜度（1）圖的鄰接矩陣存儲： 空間復雜度為O(n2) 時間復雜度都為O(n)。（2）圖的鄰接表表示： 對于有n個頂點，e條邊的圖，該算法的時間性能為O(n+e)（3）深度優(yōu)先遍歷： 假設n為圖中的頂點數(shù)，e為邊數(shù)，則DFS算法的時間復雜性是O(n+e)（4）廣度優(yōu)先遍歷： 遍歷圖的過程實質(zhì)是對每個頂點查找其鄰接點的過程，因此廣度優(yōu)先遍歷算法的時間復雜度和深度優(yōu)先遍歷算法的時間復

14、雜度相同，也為O(n+e)，兩者的不同之處僅僅在于對頂點的訪問順序不同。（5）分析prim算法： 設連通網(wǎng)中有n個頂點，則第一個進行初始化的循環(huán)執(zhí)行n-1次，第二個循環(huán)也執(zhí)行n-1次，它內(nèi)嵌兩個循環(huán)，其一是MinEdge函數(shù)在長度為n的數(shù)組中查找最小值，需要執(zhí)行n-1次，其二是修改輔助數(shù)組closedge，需要執(zhí)行n-1次，所以prim算法的時間復雜度為O(n2)，與網(wǎng)中的邊數(shù)無關(guān)5測試結(jié)果圖3.1創(chuàng)建無向圖G圖3.2程序主菜單圖3.3選擇菜單圖3.1選擇菜單及結(jié)束6.源程序（見附錄）設計總結(jié)從圖中某個頂點出發(fā)訪問圖中所有頂點，且使得每一頂點僅被訪問一次，這個過程稱為圖的遍歷。圖的遍歷是從圖中

15、某個頂點出發(fā)，沿著某條搜索路徑對圖中其余每個頂點進行訪問, 并且使圖中的每個頂點僅被訪問一次的過程。圖的遍歷是圖運算中最重要的運算,也是圖的基本運算之一,圖的許多運算都是以遍歷為基礎(chǔ)的。通過該題目的設計過程, 自己的編程語言知識和數(shù)據(jù)結(jié)構(gòu)知識得到了鞏固，編程能力也有了一定的提高，加深了對圖數(shù)據(jù)結(jié)構(gòu)及隊列的邏輯結(jié)構(gòu),存儲結(jié)構(gòu)及圖的深度優(yōu)先和廣度優(yōu)先遍歷過程的理解,對圖數(shù)據(jù)結(jié)構(gòu)上基本運算的實現(xiàn)有所掌握,對課本中所學的各種數(shù)據(jù)結(jié)構(gòu)進一步理解和掌握,學會了如何把學到的知識用于解決實際問題,鍛煉了自己動手的能力。總結(jié)起來，自己主要有以下幾點體會：1.必須牢固掌握基礎(chǔ)知識。2.必須培養(yǎng)嚴謹?shù)目茖W態(tài)度。自己

16、在編程時經(jīng)常因為一些類似于“少了分號”的小錯誤而導致錯誤，不夠認真細致，這給自己帶來了許多麻煩。編程是一件十分嚴謹?shù)氖虑椋莶坏民R虎。所以在今后自己一定要培養(yǎng)嚴謹?shù)目茖W態(tài)度。3.這次課程設計也讓我充分認識到數(shù)據(jù)結(jié)構(gòu)這門課的重要性。它給我們一個思想和大綱，讓我們在編程時容易找到思路，不至于無章可循。同時它也有廣泛的實際應用。在課程設計時遇到了很多的問題，在老師的幫助，和對各種資料的查閱中，將問題解決，培養(yǎng)了我自主動手，獨立研究的能力，為今后在學習工作中能更好的發(fā)展打下了堅實的基礎(chǔ)。三周的課程設計很短暫，但其間的內(nèi)容是很充實的，在其中我學習到了很多平時書本中無法學到的東西，積累了經(jīng)驗，鍛煉了自己分

17、析問題，解決問題的能力，并學會了如何將所學的各課知識融會，組織，來配合學習，三周中我收益很大，學到很多。參考文獻1 嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學出版社.2 嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)題集（C語言版）.清華大學出版社.3 DATA STRUCTURE WITH C+. William Ford,William Topp .清華大學出版社（影印版）. 4 譚浩強.c語言程序設計. 清華大學出版社. 5數(shù)據(jù)結(jié)構(gòu)與算法分析（Java版） , A Practical Introduction to Data Structures and Algorithm Analysis Java E

18、dition Clifford A. Shaffer , 張銘,劉曉丹譯電子工業(yè)出版社 2001 年1月致 謝本程序得以順利完成，我首先要感謝張永老師，從課設選題，程序編寫修改及最終說明書的出稿，其整個過程都得到了他極大的幫助，她總是在我困惑的時候，給予我指點迷津，誨人不倦。他對我的悉心指導與深深的教誨、啟迪，令我收益匪淺。在此，表示深深的敬意和誠摯的謝意。另外要感謝的是我的同學給予我的幫助，論文的完成也離不開平時與他們交流，在這里一并致謝。附件 任務一源程序代碼#include#include#include#include using namespace std; #define int_

19、max1 10000#define inf 9999 #define MAX 20/鄰接矩陣定義typedef struct ArcCell int adj; char *info;ArcCell,AdjMatrix2020;typedef struct char vexs20; AdjMatrix arcs; int vexnum,arcnum;MGraph_L;/int localvex(MGraph_L G,char v)/返回V的位置 int i=0; while(G.vexsi!=v) +i; return i;/.創(chuàng)建圖用鄰接矩陣表示.int creatMGraph_L(MGrap

20、h_L &G) char v1,v2; int i,j,w,k; cout*endl; cout 圖的遍歷和生成樹求解實現(xiàn) endl; cout*endlendlendl; cout *創(chuàng)建無向圖*endlendlendl; coutG.vexnumG.arcnum; for(i=0;i!=G.vexnum;+i) cout輸入頂點iG.vexsi; for(i=0;i!=G.vexnum;+i) for(j=0;j!=G.vexnum;+j) G.arcsij.adj=int_max1;/ /G.arcsij.adj=INT_MAX; G.=NULL; for(k=0;

21、k!=G.arcnum;+k) coutv1v2w;/輸入一條邊依附的兩點及權(quán)值 i=localvex(G,v1);/確定頂點V1和V2在圖中的位置 j=localvex(G,v2); G.arcsij.adj=w; G.arcsji.adj=w; coutendl#圖G鄰接矩陣創(chuàng)建成功!#endl; return G.vexnum; /.鄰接矩陣.void ljjzprint(MGraph_L G) int i,j; for(i=0;i!=G.vexnum;+i) for(j=0;j!=G.vexnum;+j) couttG.arcsij.adj; coutendladjvex=j; gra

22、.verticesi.firstarc=arc; arc-nextarc=NULL; p=arc; +j; while(G.arcsij.adj!=int_max1&j!=G.vexnum)/ tem=(arcnode *)malloc(sizeof(arcnode); tem-adjvex=j; gra.verticesi.firstarc=tem; tem-nextarc=arc; arc=tem; +j; -j; else if(G.arcsij.adj!=int_max1&j!=G.vexnum)/ arc=(arcnode *)malloc(sizeof(arcnode); arc-

23、adjvex=j; p-nextarc=arc; arc-nextarc=NULL; p=arc; gra.vexnum=G.vexnum; gra.arcnum=G.arcnum; cout #圖G鄰接表創(chuàng)建成功!#endl; return 1;/.鄰接表.void adjprint(algraph gra) int i; for(i=0;i!=gra.vexnum;+i) arcnode *p; coutti ; p=gra.verticesi.firstarc; while(p!=NULL) coutadjvex; p=p-nextarc; coutadjvex;int nextadjv

24、ex(algraph gra,vnode v,int w)/返回依附頂點V的相對于W的下一個頂點 arcnode *p; p=v.firstarc; while(p!=NULL&p-adjvex!=w) p=p-nextarc; if(p-adjvex=w&p-nextarc!=NULL) p=p-nextarc;return p-adjvex; if(p-adjvex=w&p-nextarc=NULL) return -10;int initqueue(linkqueue &q)/初始化隊列 q.rear=(queueptr)malloc(sizeof(qnode); q.front=q.r

25、ear; if(!q.front) return 0; q.front-next=NULL; return 1;int enqueue(linkqueue &q,int e)/入隊 queueptr p; p=(queueptr)malloc(sizeof(qnode); if(!p) return 0; p-data=e; p-next=NULL; q.rear-next=p; q.rear=p; return 1;int dequeue(linkqueue &q,int &e)/出隊 queueptr p; if(q.front=q.rear) return 0; p=q.front-ne

26、xt; e=p-data; q.front-next=p-next; if(q.rear=p) q.rear=q.front; free(p); return 1;int queueempty(linkqueue q)/判斷隊為空 if(q.front=q.rear) return 1; return 0;/.廣度優(yōu)先遍歷.void bfstra(algraph gra) int i,e; linkqueue q; for(i=0;i!=gra.vexnum;+i) visitedi=0; initqueue(q); for(i=0;i!=gra.vexnum;+i) if(!visitedi

27、) visitedi=1; cout=0;we=nextadjvex(gra,gra.verticese,we) if(!visitedwe) visitedwe=1; coutgra.verticeswe.data; enqueue(q,we); /.深度優(yōu)先遍歷.int dfs(algraph gra,int i);/聲明DFSint dfstra(algraph gra) int i,j; for(i=0;i!=gra.vexnum;+i) visitedi=0; for(j=0;j!=gra.vexnum;+j) if(visitedj=0) dfs(gra,j); return 0;

28、int dfs(algraph gra,int i) visitedi=1; int we1; cout=0;we=nextadjvex(gra,gra.verticesi,we) we1=we; if(visitedwe=0) dfs(gra,we); we=we1; return 12;/.求連通分量.int bfstra_fen(algraph gra) int i,j; for(i=0;i!=gra.vexnum;+i) visitedi=0; for(j=0;j!=gra.vexnum;+j) if(visitedj=0) dfs(gra,j); coutendl; return 0

29、;typedef struct int adjvex; int lowcost; closedge;/.最小生成樹PRIM算法.int prim(int gMAX,int n) int lowcostMAX,prevexMAX; /LOWCOST存儲當前集合U分別到剩余結(jié)點的最短路徑 /prevex存儲最短路徑在U中的結(jié)點 int i,j,k,min; for(i=2;i=n;i+) /n個頂點，n-1條邊 lowcosti=g1i; /初始化 prevexi=1; /頂點未加入到最小生成樹中 lowcost1=0; /標志頂點1加入U集合 for(i=2;i=n;i+) /形成n-1條邊的生

30、成樹 min=inf; k=0; for(j=2;j=n;j+) /尋找滿足邊的一個頂點在U,另一個頂點在V的最小邊 if(lowcostjmin)&(lowcostj!=0) min=lowcostj; k=j; printf(%d,%d)%dt,prevexk-1,k-1,min); lowcostk=0; /頂點k加入U for(j=2;j=n;j+) /修改由頂點k到其他頂點邊的權(quán)值 if(gkj0) f=acrvisitedf; return f;/.最小生成樹kruscal算法.void kruscal_arc(MGraph_L G,algraph gra) edg edgs20;

31、 int i,j,k=0; for(i=0;i!=G.vexnum;+i) for(j=i;j!=G.vexnum;+j) if(G.arcsij.adj!=10000) edgsk.pre=i;edgsk.bak=j;edgsk.weight=G.arcsij.adj;+k; int x,y,m,n; int buf,edf; for(i=0;i!=gra.arcnum;+i) acrvisitedi=0; for(j=0;j!=G.arcnum;+j) m=10000; for(i=0;i!=G.arcnum;+i) if(edgsi.weightm) m=edgsi.weight;x=edgsi.pre;y=edgsi.bak;n=i; buf=find(acrvisited,x); edf=find(acrvisited,y); edgsn.weight=10000; if(buf!=edf) acrvisitedbuf=edf;cout(x,y)m;coutendl; /.選擇菜單.