數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---圖的遍歷和生成樹求解

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：28 大?。?81.50KB 人氣指數(shù)：12 舉報 版權(quán)申訴

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---圖的遍歷和生成樹求解_第1頁

已閱讀1頁，還剩27頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、　　數(shù)學(xué)與計算機學(xué)院　　課程設(shè)計說明書　　課程名稱: 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計 　　課程代碼: 　　題目: 圖

2、的遍歷和生成樹求解實現(xiàn) 　　目錄 　　摘要3　　引言4　　1 需求分析5</p&

3、gt;　　1.1任務(wù)與分析5　　1.2測試數(shù)據(jù)5　　2 概要設(shè)計5　　2.1 ADT描述5　　2.2程序模塊結(jié)構(gòu)7<

4、b>　　軟件結(jié)構(gòu)設(shè)計：7　　2.3　各功能模塊7　　3 詳細(xì)設(shè)計8　　3.1結(jié)構(gòu)體定義19　　3.2 初始化21　　3.3 插入操作（四號黑體）21<

5、;/p>　　4 調(diào)試分析21　　5 用戶使用說明21　　6 測試結(jié)果23　　結(jié) 論26　　摘要

6、　　《數(shù)據(jù)結(jié)構(gòu)》課程主要介紹最常用的數(shù)據(jù)結(jié)構(gòu)，闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論其在計算機中的存儲表示，以及在其上進(jìn)行各種運算時的實現(xiàn)算法，并對算法的效率進(jìn)行簡單的分析和討論。進(jìn)行數(shù)據(jù)結(jié)構(gòu)課程設(shè)計要達(dá)到以下目的：　　了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力；　　初步掌

7、握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；　　提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力；　　訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。　　這次課程設(shè)計我們主要是應(yīng)用以前學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)與面向?qū)ο蟪绦蛟O(shè)計知識，結(jié)合起來才完成

8、了這個程序。　　因為圖是一種較線形表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線形表中，數(shù)據(jù)元素之間僅有線性關(guān)系，每個元素只有一個直接前驅(qū)和一個直接后繼，并且在圖形結(jié)構(gòu)中，節(jié)點之間的關(guān)系可以是任意的，圖中任意兩個數(shù)據(jù)元素之間都可能相關(guān)。因此，本程序是采用鄰接矩陣、鄰接表、十字鏈表等多種結(jié)構(gòu)存儲來實現(xiàn)對圖的存儲。采用鄰接矩陣即為數(shù)組表示法，鄰接表和十字鏈表都是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。對圖的遍歷分別采用了廣度優(yōu)先遍歷

9、和深度優(yōu)先遍歷。　　關(guān)鍵詞：計算機；圖；算法。 　　引言 　　很多涉及圖的操作的算法都是以圖的遍歷操作為基礎(chǔ)，通過遍歷的演示，方便在學(xué)習(xí)中更好的理解突地遍歷的過程。　　通過對圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的演示，分別兩種遍歷的

10、不同與其優(yōu)缺點。　　我們在對一些問題進(jìn)行求解時，會發(fā)現(xiàn)有些問題很難找到規(guī)律，或者根本無規(guī)律可尋。對于這樣的問題，可以利用計算機運算速度快的特點，先搜索查找所有可能出現(xiàn)的情況，再根據(jù)題目條件從所有可能的情況中，刪除那些不符合條件的解。　　在深度優(yōu)先搜索算法中，是深度越大的結(jié)點越先得到擴展。如果在搜索中把算法改為按結(jié)點的層次進(jìn)行搜索，本層的結(jié)點沒有搜索處理完

11、時，不能對下層結(jié)點進(jìn)行處理，即深度越小的結(jié)點越先得到擴展，也就是說先產(chǎn)生的結(jié)點先得以擴展處理，這種搜索算法稱為廣度優(yōu)先搜索法。很多問題都可以用廣度優(yōu)先搜索進(jìn)行處理、如翻幣問題、最短路徑問題等。　　在計算機中，有多種方法存儲圖的信息，由于圖的結(jié)構(gòu)復(fù)雜，使用廣泛，一般應(yīng)根據(jù)實際的應(yīng)用，選擇適合的表示方法。常用的圖的存儲結(jié)構(gòu)有鄰接矩陣、鄰接多重表和鄰接表。在實際問題當(dāng)中，經(jīng)常遇到這類問題，為新建的某

12、個機構(gòu)進(jìn)行選址、道路交通路線、如何走完所有路線、旅游線路等一系列問題都涉及到圖的知識。圖是一種復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，一個圖G（Grah）由兩個集合V和E構(gòu)成。圖存在兩種遍歷方式：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。廣度優(yōu)先遍歷基本思路是假設(shè)從圖中某頂點U出發(fā)，在訪問了頂點U之后依次訪問U的各個未訪問的領(lǐng)接點，然后分別從這些領(lǐng)接點出發(fā)依次訪問他們的領(lǐng)接點，并使先訪問的頂點的領(lǐng)接點先于后訪問的頂點被訪問。直至所有領(lǐng)接點被訪問到。深度優(yōu)先的基本思路是

13、從某個頂點出發(fā)訪問此頂點，然后依次從V的未被訪問的領(lǐng)接點出發(fā)深度優(yōu)先檢索圖。直至圖中所有頂點都被訪問到。PRIM算法—KRUSKAL算法，可以對圖形進(jìn)行最小生成樹的求解。樹型結(jié)構(gòu)是一種非線性結(jié)構(gòu)，它用于描述數(shù)據(jù)元素之間層次關(guān)系，如人類社會的族譜等，樹型結(jié)構(gòu)的應(yīng)用非常廣泛，磁盤文件目錄結(jié)構(gòu)就是一個典型的例子。　　1 需求分析 <

14、p>　　1.1任務(wù)與分析 　　問題描述：　　圖的遍歷和生成樹求解實現(xiàn)　　圖是一種較線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素之間僅有線性關(guān)系，每個數(shù)據(jù)元素只有一個直接前驅(qū)和一個直接后繼；在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間有著明顯的層

15、次關(guān)系，并且每一層上的數(shù)據(jù)元素可能和下一層中多個元素（及其孩子結(jié)點）相關(guān)但只能和上一層中一個元素（即雙親結(jié)點）相關(guān)；而在圖形結(jié)構(gòu)中，節(jié)點之間的關(guān)系可以是任意的，圖中任意兩個數(shù)據(jù)元素之間都可能相關(guān)。　　生成樹求解主要利用普利姆和克雷斯特算法求解最小生成樹，只有強連通圖才有生成樹。　　基本功能&l

16、t;p>　　1) 先任意創(chuàng)建一個圖；　　2) 圖的DFS,BFS的遞歸和非遞歸算法的實現(xiàn)　　3) 最小生成樹（兩個算法）的實現(xiàn)，求連通分量的實現(xiàn)　　4) 要求用鄰接矩陣、鄰接表等多種結(jié)構(gòu)存儲實現(xiàn)　　輸入輸出

17、　　輸入數(shù)據(jù)類型為整型和字符型，輸出為整型和字符。　　1.2測試數(shù)據(jù)　　根據(jù)提示，輸入所對應(yīng)的功能，輸入相關(guān)數(shù)據(jù)進(jìn)行測試。　　2 概要設(shè)計 　　設(shè)計思路：&l

18、t;/b>　　a.圖的鄰接矩陣存儲：根據(jù)所建無向圖的結(jié)點數(shù)n,建立n*n的矩陣，其中元素全是無窮大（int_max），再將邊的信息存到數(shù)組中。其中無權(quán)圖的邊用1表示，無邊用0表示；有全圖的邊為權(quán)值表示，無邊用∞表示。　　b.圖的鄰接表存儲：將信息通過鄰接矩陣轉(zhuǎn)換到鄰接表中，即將鄰接矩陣的每一行都轉(zhuǎn)成鏈表的形式將有邊的結(jié)點進(jìn)行存儲。

19、;　　c.圖的廣度優(yōu)先遍歷：假設(shè)從圖中的某個頂點v出發(fā)，在訪問了v之后依次訪問v的各個未曾訪問過的鄰接點，然后再訪問此鄰接點的未被訪問的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點”被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。若此時圖中還有未被訪問的，則另選未被訪問的重復(fù)以上步驟，是一個非遞歸過程。　　d.圖的深度優(yōu)先遍歷：假設(shè)從圖中某頂點v

20、出發(fā)，依依次訪問v的鄰接頂點，然后再繼續(xù)訪問這個鄰接點的系一個鄰接點，如此重復(fù)，直至所有的點都被訪問，這是個遞歸的過程。　　e.圖的連通分量：這是對一個非強連通圖的遍歷，從多個結(jié)點出發(fā)進(jìn)行搜索，而每一次從一個新的起始點出發(fā)進(jìn)行搜索過程中得到的頂點訪問序列恰為其連通分量的頂點集。本程序利用的圖的深度優(yōu)先遍歷算法。　　2.1 ADT描述&l

21、t;/b>　　ADT Queue{　　數(shù)據(jù)對象：D={ai| ai ∈ElemSet,i=1,2,3……，n,n≥0}　　數(shù)據(jù)關(guān)系：R1={<ai-1,ai>| ai-1,ai ∈D,i=1,2,3,……，n}　　基本操作：</b

22、>　　InitQueue(&Q)　　操作結(jié)果：構(gòu)造一個空隊列Q。　　QueueEmpty(Q)　　初始條件：Q為非空隊列。　　操作結(jié)果：若Q為空隊列，則返回真，否則為假。

23、EnQueue(&Q,e)　　初始條件：Q為非空隊列。　　操作結(jié)果：插入元素e為Q的新的隊尾元素。　　DeQueue(&Q,e)　　初始條件：Q為非空隊列。　　操作結(jié)果：刪除Q的隊頭元素，并用e返回其值。</

24、p>　　}ADT Queue　　ADT Graph{　　數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。　　數(shù)據(jù)關(guān)系R：　　R={VR}

25、　　VR={<v,w>|v,w∈V且P（v，w）,<v,w>表示從v到w的弧，　　謂詞P（v,w）定義了弧<v,w>的意義或信息}　　基本操作P：　　CreatGraph(&G,V,VR);

26、　　初始條件：V是圖的頂點集，VR是圖中弧的集合。　　操作結(jié)果：按V和VR的定義構(gòu)造圖G。　　BFSTraverse(G,visit());　　初始條件：圖G存在，Visit是定點的應(yīng)用函數(shù)。　　操作結(jié)果：對圖進(jìn)行廣度優(yōu)先遍歷。在遍歷過程中對每個頂點

27、 　　調(diào)用函數(shù)Visit一次且僅一次。一旦visit（）失 　　敗，則操作失敗。　　DFSTraverse(G,visit());　　初始條件：圖G存在，Visit是定點的應(yīng)用函數(shù)。　　操

28、作結(jié)果：對圖進(jìn)行廣度優(yōu)先遍歷。在遍歷過程中對每個頂點 　　調(diào)用函數(shù)Visit一次且僅一次。一旦visit（）失 　　敗，則操作失敗。　　DFStra_fen(G)　　初始條件：圖G存在，存在圖的深度優(yōu)先遍歷算法。</p&g

29、t;　　操作結(jié)果：從多個頂點對圖進(jìn)行深度優(yōu)先遍歷，得到連通分量。　　}ADT Graph;　　2.2程序模塊結(jié)構(gòu) 　　軟件結(jié)構(gòu)設(shè)計：　　2.2.1　結(jié)構(gòu)體定義<b

30、>　　鄰接矩陣定義:　　typedef struct ArcCell　　typedef struct　　鄰接表的定義:　　typedef struct ArcNode//弧結(jié)點<

31、p>　　typedef struct VNode//鄰接鏈表頂點頭接點　　typedef struct//圖的定義　　隊列定義:　　typedef struct QNode　　2.3　各功能模塊</b&g

32、t;　　鄰接矩陣存儲：int creatMGraph_L(MGraph_L &G)　　鄰接矩陣的輸出：void ljjzprint(MGraph_L G) 　　用鄰接表存儲圖：int creatadj(ALGraph &gra,MGraph_L G)　　鄰

33、接表輸出：void adjprint(ALGraph gra,MGraph_L G) 　　初始化隊列：Status InitQueue(LinkQueue &Q)　　入隊：Status EnQueue(LinkQueue &Q,QElemType e)//入隊,插入元素e為Q的新的隊尾元素　　出隊

34、：Status DeQueue(LinkQueue &Q,QElemType &e)//出隊，若隊列不空，則刪除Q的隊頭元素，用e返回，并返回真，否則假　　判斷隊為空：Status QueueEmpty(LinkQueue Q　　廣度優(yōu)先遍歷：void BFSTraverse(ALGraph gra)<p&g

35、t;　　深度優(yōu)先遍歷：int DFS(ALGraph gra,int i)　　連通分量：int DFSTraverse_fen(ALGraph gra)　　3 詳細(xì)設(shè)計　　主函數(shù)：　　int ma

36、in()　　{　　int s;　　char y='y';　　cout<<"||¤¤¤¤¤¤

37、4;¤¤¤¤¤¤¤¤¤¤菜單¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤||"<<endl;　　cout

38、<<"||-------------------------【0、創(chuàng)建一個無向圖------------------------------||"<<endl;　　cout<<"||-------------------------【1、顯示該圖的鄰接矩陣--------------------------||"<

39、<endl;　　cout<<"||-------------------------【2、顯示該圖的鄰接表----------------------------||"<<endl;　　cout<<"||-------------------------【3、廣度優(yōu)先遍歷------

40、--------------------------||"<<endl;　　cout<<"||-------------------------【4、深度優(yōu)先遍歷--------------------------------||"<<endl;　　cout<<"||

41、-------------------------【5、最小生成樹MiniSpanTree_PRIM算法-------------||"<<endl;　　cout<<"||-------------------------【6、最小生成樹MiniSpanTree_KRUSCAL算法----------||"<<endl;</

42、p>　　cout<<"||-------------------------【7、連通分量------------------------------------||"<<endl;　　cout<<"||¤¤¤¤¤¤¤¤&#

43、164;¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤||"<<endl;　　whil

44、e(y=='y')　　{　　cout<<"請選擇菜單："<<endl;　　cin>>s;　　if(s==0

45、)　　{　　++o;　　if(o==2)　　{<b&

46、gt;　　n=0;　　l=0;　　o=0;　　}　　}&l

47、t;b>　　switch(s)　　{　　case 0:cout<<"創(chuàng)建一個無向圖："<<endl;　　MGraph_L G;　　creatMGraph_L(G);

48、　　ALGraph gra;　　creatadj(gra,G);　　break;　　case 1:cout<<"鄰接矩陣顯示如下："<<endl;

49、　ljjzprint(G);　　break;　　case 2:　　cout<<"鄰接表顯示如下："<<endl;　　adjprint(gra,G);&l

50、t;/p>　　break;　　case 3:　　cout<<"廣度優(yōu)先遍歷：";　　BFSTraverse(gra);　　cout<

51、;<endl;　　break;　　case 4:　　cout<<"深度優(yōu)先遍歷：";　　DFStra(gra);

52、cout<<endl;　　break;　　case 5:　　if(n==0){cout<<"無權(quán)圖沒有最小生成樹";break;}　　else if(l

53、>0){cout<<"若該圖為非強連通圖(含有多個連通分量)時，最小生成樹不存在"<<endl;break;}　　else　　{　　int i,g[max][max];

54、　　for(i=0;i!=G.vexnum;++i)　　for(int j=0;j!=G.vexnum;++j)　　g[i+1][j+1]=G.arcs[i][j].adj;　　cout<<"普利姆算法:"<<endl;&l

55、t;p>　　MiniSpanTree_PRIM(g,G.vexnum);　　break;　　}　　case 6:if(n==0){cout<<"無權(quán)圖沒有最小生成樹";break;}

56、;　　else if(l>0){cout<<"該圖為非強連通圖(含有多個連通分量)，最小生成樹不存在"<<endl;break;}　　else　　{　　cout<

57、;<"克魯斯卡爾算法:"<<endl;　　MiniSpanTREE_KRUSCAL(G,gra);　　break;　　}　　case 7:cout<&l

58、t;"連通分量:"<<endl;　　DFSTraverse_fen(gra);　　break;　　}　　cout<<endl<<"

59、是否繼續(xù)？y/n:";　　cin>>y;　　if(y=='n')　　break;　　}<p

60、>　　return 0;　　}　　鄰接矩陣存儲：　　int creatMGraph_L(MGraph_L &G)//創(chuàng)建圖用鄰接矩陣表示<

61、b>　　{　　char v1,v2;　　int i,j,w;　　cout<<"請輸入頂點和弧的個數(shù)"<<endl;　　cin>>G.vexnum>>G.arcnum;</p

62、>　　cout<<"輸入各個頂點"<<endl;　　for(i=0;i<G.vexnum;++i)　　{　　cin>>G.vexs[i];<

63、;b>　　}　　for(i=0;i<G.vexnum;++i)　　for(j=0;j<G.vexnum;++j)　　{　　G.arcs[i][j].adj=int_max;

64、　　G.arcs[i][j].info=NULL;　　}　　for(int k=0;k<G.arcnum;++k)　　{　　cout<<"輸入一條邊依

65、附的頂點和權(quán)"<<endl;　　cin>>v1>>v2>>w;//輸入一條邊依附的兩點及權(quán)值　　i=localvex(G,v1);//確定頂點V1和V2在圖中的位置　　j=localvex(G,v2);　　G.ar

66、cs[i][j].adj=w;　　G.arcs[j][i].adj=w;　　}　　for(i=0;i!=G.vexnum;++i)　　for(j=0;j!=G.vexnum;++j)<b

67、>　　{　　if(G.arcs[i][j].adj!=1&&G.arcs[i][j].adj<int_max)n+=1;　　}　　if(n>=1)cout<<"這是一個有權(quán)圖"<<

68、;endl;　　else cout<<"這是一個無權(quán)圖"<<endl;　　cout<<"圖G鄰接矩陣創(chuàng)建成功！"<<endl;　　return G.vexnum;

69、}　　鄰接矩陣的輸出：　　void ljjzprint(MGraph_L G) //鄰接矩陣的輸出　　{　　int i,j;</p&

70、gt;　　if(n==0)　　{　　for(i=0;i!=G.vexnum;++i)　　{　　for(j=0;j!=G.vexnum;+

71、+j)　　{　　if(G.arcs[i][j].adj==int_max){cout<<"0"<<" ";}　　else {cout<<G.arcs[i][j].adj<<" &

72、quot;;}　　}　　cout<<endl;　　}　　}　　else</b&g

73、t;　　{　　for(i=0;i!=G.vexnum;++i)　　{　　for(j=0;j!=G.vexnum;++j)　　{</

74、b>　　if(G.arcs[i][j].adj==int_max){cout<<"∞"<<" ";}　　else {cout<<G.arcs[i][j].adj<<" ";}　　}

75、　　cout<<endl;　　}　　}　　}　　用鄰接表存儲圖：&

76、lt;/b>　　int creatadj(ALGraph &gra,MGraph_L G)//用鄰接表存儲圖　　{　　int i=0,j=0;　　ArcNode *arc;//,*tem,*p;&

77、lt;p>　　for(i=0;i!=G.vexnum;++i)　　{　　gra.vertices[i].data=G.vexs[i];　　gra.vertices[i].firstarc=NULL;　　}<

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

79、;b>　　{　　arc=(ArcNode *)malloc(sizeof(ArcNode));　　arc->adjvex=j;　　arc->nextarc=gra.vertices[i].firstarc;　　gra.vertices

80、[i].firstarc=arc;　　}　　}　　gra.vexnum=G.vexnum;　　gra.arcnum=G.arcnum;　　cout<

81、<"圖G鄰接表創(chuàng)建成功！"<<endl;　　return 1;　　}　　鄰接表輸出：　　void adjprint(AL

82、Graph gra,MGraph_L G) //鄰接表輸出　　{　　int i;　　for(i=0;i!=gra.vexnum;++i)　　{</p&g

83、t;　　ArcNode *p;　　cout<<"["<<i<<","<<G.vexs[i]<<"]";　　p=gra.vertices[i].firstarc;　　whil

84、e(p!=NULL)　　{　　cout<<"->"<<"["<<p->adjvex<<"]";　　p=p->nextarc;&

85、lt;p>　　}　　cout<<"->"<<"End";　　cout<<endl;　　}

86、　}　　初始化隊列：　　Status InitQueue(LinkQueue &Q)//初始化隊列　　{　　Q.front=Q.rear=(QueuePtr)mallo

87、c(sizeof(QNode));　　if(!Q.front)return 0;//存儲分配失敗　　Q.front->next=NULL;　　return 1;　　}

88、　　入隊：　　Status EnQueue(LinkQueue &Q,QElemType e)//入隊,插入元素e為Q的新的隊尾元素　　{　　QueuePtr p;　　p

89、=(QueuePtr)malloc(sizeof(QNode));　　if(!p)return 0;//存儲分配失敗　　p->data=e;p->next=NULL;　　Q.rear->next=p;Q.rear=p;　　return

90、1;　　}　　出隊：　　Status DeQueue(LinkQueue &Q,QElemType &e)//出隊，若隊列不空，則刪除Q的隊頭元素，用e返回，并返回真，否則假&l

91、t;p>　　{　　QueuePtr p;　　if(Q.front==Q.rear)return 0;　　p=Q.front->next;　　e=p->data;　　Q.fro

92、nt->next=p->next;　　if(Q.rear==p)Q.rear=Q.front;　　free(p);　　return 1;　　}&l

93、t;/p>　　判斷隊為空：　　Status QueueEmpty(LinkQueue Q)//判斷隊為空　　{　　if(Q.front==Q.rear) return 1;<p&g

94、t;　　return 0;　　}　　廣度優(yōu)先遍歷：　　void BFSTraverse(ALGraph gra)　　{&

95、lt;/p>　　int i,e;　　LinkQueue q;　　for(i=0;i!=gra.vexnum;++i)visited[i]=0;　　InitQueue(q);　　for(i=0;i!=gra.

96、vexnum;++i)　　if(!visited[i])　　{ 　　visited[i]=1;　　cout<<gra.vertices[i].data;　　EnQueue(q,i)

97、;　　while(!QueueEmpty(q))　　{　　DeQueue(q,e);　　for(we=firstadjvex(gra,gra.vertices[e]);we>=0;we=nextadjvex(gra,gra.ve

98、rtices[e],we))　　{　　if(!visited[we])　　{　　visited[we]=1;　　cout<<gra.verti

99、ces[we].data;　　EnQueue(q,we);　　}　　}　　}　　}</b&g

100、t;　　}　　深度優(yōu)先遍歷：　　int DFS(ALGraph gra,int i)　　{　　visited[i]=

101、1;　　int we1;　　cout<<gra.vertices[i].data;　　for(we=firstadjvex(gra,gra.vertices[i]);we>=0;we=nextadjvex(gra,gra.vertices[i],we))&l

102、t;/p>　　{　　we1=we;　　if(visited[we]==0)　　DFS(gra,we);　　we=we1;</

103、p>　　}　　return 1;　　}　　int DFStra(ALGraph gra)　　{

104、;　　int i,j;　　for(i=0;i!=gra.vexnum;++i)　　{　　visited[i]=0;　　}</b&g

105、t;　　for(j=0;j!=gra.vexnum;++j)　　{　　if(visited[j]==0)DFS(gra,j);　　}

106、return 0;　　}　　連通分量：　　int DFSTraverse_fen(ALGraph gra)　　{&

107、lt;p>　　int i,j;　　for(i=0;i!=gra.vexnum;++i)　　visited[i]=0;　　for(j=0;j!=gra.vexnum;++j)　　{</p

108、>　　if(visited[j]==0)　　{　　DFS(gra,j);　　cout<<endl;　　l++;&l

109、t;b>　　}　　}　　return 0;　　}　　主要函數(shù)的程序流程圖，實現(xiàn)設(shè)計中主程序和其他子模塊的算法，以流程圖的形式表示。&

110、lt;/p>　　3.1結(jié)構(gòu)體定義　　鄰接矩陣定義:　　typedef struct ArcCell　　{　　VRType adj;

111、//VRType是頂點關(guān)系類型。對無權(quán)圖，用1或0表示相鄰否；對帶權(quán)圖，則為權(quán)值類型　　InfoType *info;//該弧相關(guān)信息的指針　　}ArcCell,AdjMatrix[max][max];　　typedef struct　　{</b&

112、gt;　　VertexType vexs[max];//頂點向量　　AdjMatrix arcs;//鄰接矩陣　　int vexnum,arcnum;//圖的當(dāng)前頂點數(shù)和弧數(shù)　　}MGraph_L;　　鄰接表的定

113、義:　　typedef struct ArcNode//弧結(jié)點　　{　　int adjvex;//該弧指向的頂點的位置　　struct ArcNode *nextarc;//指向下一條弧的指針

114、　　InfoType *info;//該弧相關(guān)信息的指針　　}ArcNode;　　typedef struct VNode//鄰接鏈表頂點頭接點　　{　　VertexType

115、data;//頂點信息　　ArcNode *firstarc;//指向第一條依附該頂點的弧的指針　　}VNode,AdjList;　　typedef struct//圖的定義　　{　　AdjL

116、ist vertices[max];　　int vexnum,arcnum;//圖的當(dāng)前頂點數(shù)和弧數(shù)　　}ALGraph;　　隊列定義:　　typedef struct QNode</p&g

117、t;　　{　　QElemType data;　　struct QNode *next;　　}QNode,*QueuePtr;　　typedef struct<b&g

118、t;　　{　　QueuePtr front;//隊頭指針　　QueuePtr rear;//隊尾指針　　}LinkQueue;　　3.2 初始化　　初始化

119、隊列：　　Status InitQueue(LinkQueue &Q)//初始化隊列　　{　　Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));　　if(!Q.f

120、ront)return 0;//存儲分配失敗　　Q.front->next=NULL;　　return 1;　　}　　3.3 插入操作

121、;　　Status EnQueue(LinkQueue &Q,QElemType e)//入隊,插入元素e為Q的新的隊尾元素　　{　　QueuePtr p;　　p=(QueuePtr)malloc(sizeof(QNode));

122、;　　if(!p)return 0;//存儲分配失敗　　p->data=e;p->next=NULL;　　Q.rear->next=p;Q.rear=p;　　return 1;

123、　　}　　4 調(diào)試分析　　4.1實際完成的情況說明；　　a. 先任意創(chuàng)建一個圖；　　b. 圖的DFS,BFS的遞歸和非遞歸算法的實現(xiàn)　　c. 最小生成樹（兩個算法）的實現(xiàn)，

124、求連通分量的實現(xiàn)　　d. 要求用鄰接矩陣、鄰接表等多種結(jié)構(gòu)存儲實現(xiàn)　　支持的數(shù)據(jù)類型：整型和字符型　　4.2程序的性能分析，包括時空分析；　　本程序的圖的遍歷是以鄰接表做圖的存儲結(jié)構(gòu)，其時間復(fù)雜度為O（n+e）。　　4.3上機過程

125、中出現(xiàn)的問題及其解決方案；　　a.程序開始對無權(quán)圖和有權(quán)圖的鄰接矩陣的輸出時，無邊都用的10000（無窮大int_max）表示的，這種表示和我們習(xí)慣上的0與∞的表示有差異。所以在程序中定義了全局變量n（初值為0）,來判斷創(chuàng)建的無向圖是有權(quán)圖還是無權(quán)圖，n>0為有權(quán)圖，此時輸出的時候用∞代替10000；n=0為無權(quán)圖，此時輸出的時候用0代替10000.

126、;　　b.程序中有的功能對某些圖是不適用的，比如無權(quán)圖沒有最小生成樹，非強連通圖沒有最小生成樹等。所以在程序中又新增了全局變量l,l>0時表示為非強連通圖，則在求最小生成樹時報錯。　　C.當(dāng)程序先創(chuàng)建一個有權(quán)圖后，n的值會大于1，第二次創(chuàng)無權(quán)圖時也會被程序認(rèn)為有權(quán)圖，所以在程序中在定義全局變量o（初值為0）,來判斷創(chuàng)建了幾次圖，當(dāng)?shù)诙蝿?chuàng)建圖，即o=2時，所有全局變量在開始全歸零。<

127、/p>　　4.4程序中可以改進(jìn)的地方說明；　　當(dāng)建立一個圖時先得求其連通分量，從而確定全局變量l的值，從而才能判斷該圖是否有最小生成樹。　　5 用戶使用說明　　用戶應(yīng)該在windows操作系統(tǒng)下，按照提示進(jìn)行操作。<p

128、>　　先選0創(chuàng)建一個圖。　　選擇y繼續(xù)操作。　　按照菜單編碼選擇操作。　　6 測試結(jié)果　　創(chuàng)建一個無權(quán)圖：<

129、/p>　　創(chuàng)建一個費強連通的有權(quán)圖：　　創(chuàng)建一個有權(quán)連通圖：　　結(jié) 論 　　在做這個程序的時候你首先必須知道圖的一些概念，圖是一種較線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素之間僅有線性關(guān)系，每個數(shù)據(jù)元素只有一個直接前驅(qū)和一個直接后繼；

130、在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間有著明顯的層次關(guān)系，并且每一層上的數(shù)據(jù)元素可能和下一層中多個元素（及其孩子結(jié)點）相關(guān)但只能和上一層中一個元素（即雙親結(jié)點）相關(guān)；而在圖形結(jié)構(gòu)中，節(jié)點之間的關(guān)系可以是任意的，圖中任意兩個數(shù)據(jù)元素之間都可能相關(guān)。　　當(dāng)我們拿到一個圖時，我們對該圖的遍歷就要有一些方法，所以有了深度優(yōu)先遍歷和廣度優(yōu)先遍歷，我們要明白這兩種遍歷是怎么實現(xiàn)的，然后根據(jù)我們?nèi)四X中的方法把它寫成電腦算

131、法。　　對一個圖我們還定義了連通分量，所以將圖存到電腦中時，我們對連通分量得有個算法。　　求圖的最小生成樹有兩種算法，普利姆是從結(jié)點出發(fā)尋找權(quán)最小的邊，知道所有結(jié)點都練通了；而克魯斯卡爾算法則是從邊出發(fā)，尋找使圖連通的權(quán)值最小邊的方法。　　算法的實現(xiàn)從人腦到電腦的轉(zhuǎn)變是比較復(fù)雜的一件事，要求做到具體到實現(xiàn)該方法的

132、每一個步驟，然后再將每一個步驟通過代碼實現(xiàn)。　　這要求我們要明確各個數(shù)據(jù)元素和個元素之間的關(guān)系，然后才能明確使用算法去調(diào)用這些數(shù)據(jù)。　　通過本次的課程設(shè)計，我對數(shù)據(jù)結(jié)構(gòu)有了一定的認(rèn)識，明白了數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)，數(shù)據(jù)關(guān)系，及對其操作的方法。但同時也發(fā)現(xiàn)在自己有很多的不足，在使用語言和如何精煉語言需要進(jìn)行更多的訓(xùn)練。&l

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---圖的遍歷和生成樹求解

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---圖的遍歷和生成樹求解

文檔簡介

溫馨提示

最新文檔

評論

免費下載