數(shù)據(jù)結(jié)構(gòu) 無(wú)向圖的存儲(chǔ)和遍歷

《數(shù)據(jù)結(jié)構(gòu) 無(wú)向圖的存儲(chǔ)和遍歷》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告◎?qū)嶒?yàn)題目:無(wú)向圖的存儲(chǔ)和遍歷◎?qū)嶒?yàn)?zāi)康模?、掌握使用VisualC++6.0上機(jī)調(diào)試程序的基本方法；2、掌握?qǐng)D的鄰接表存儲(chǔ)結(jié)構(gòu)和深度優(yōu)先遍歷的非遞歸算法。3、提高自己分析問(wèn)題和解決問(wèn)題的能力，在實(shí)踐中理解教材上的理論?！?qū)嶒?yàn)內(nèi)容：建立有10個(gè)頂點(diǎn)的無(wú)向圖的鄰接表存儲(chǔ)結(jié)構(gòu)，然后對(duì)其進(jìn)行深度優(yōu)先遍歷，該無(wú)向圖可以是無(wú)向連通圖或無(wú)向非連通圖。一、需求分析1、輸入的形式和輸入值的范圍：根據(jù)提示，首先輸入圖的所有邊建立鄰接表存儲(chǔ)結(jié)構(gòu)，然后輸入遍歷的起始頂點(diǎn)對(duì)圖或非連通圖的某一連通分量進(jìn)行遍歷。2、輸出

2、的形式：輸出對(duì)該圖是連通圖或非連通圖的判斷結(jié)果，若是非連通圖則輸出各連通分量的頂點(diǎn)，之后輸出隊(duì)連通圖或非連通圖的某一連通分量的遍歷結(jié)果。3、程序所能達(dá)到的功能：輸入圖的所有邊后，建立圖的鄰接表存儲(chǔ)結(jié)構(gòu)，判斷該圖是連通圖或非連通圖，最后對(duì)圖進(jìn)行遍歷。4、測(cè)試數(shù)據(jù)：輸入10個(gè)頂點(diǎn)（空格分隔）:ABCDEFGHIJ輸入邊的信息（格式為xy）:ABACAFCEBDDCHGGIIJHJEH該圖為連通圖,請(qǐng)輸入遍歷的起始頂點(diǎn):A遍歷結(jié)果為:AFCDBEHJIG是否繼續(xù)？（是,輸入1;否,輸入0）:1輸入10個(gè)頂點(diǎn)（空格分隔）

3、:ABCDEFGHIJ輸入邊的信息（格式為xy）:ABACCECAAFHGHJIJIG該圖為非連通圖,各連通分量中的頂點(diǎn)為:輸入第1個(gè)連通分量起始頂點(diǎn):F第1個(gè)連通分量的遍歷結(jié)果為:FACEB輸入第2個(gè)連通分量起始頂點(diǎn):I第2個(gè)連通分量的遍歷結(jié)果為:IGHJ輸入第3個(gè)連通分量起始頂點(diǎn):D第3個(gè)連通分量的遍歷結(jié)果為:D是否繼續(xù)？（是,輸入1;否,輸入0）:0謝謝使用!Pressanykeytocontinue二概要設(shè)計(jì)1、鄰接表是圖的一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)結(jié)合的存儲(chǔ)方法。鄰接表表

4、示法類似于樹的孩子鏈表表示法。就是對(duì)圖G中的每個(gè)頂點(diǎn)Vi，將所有鄰接于Vi的頂點(diǎn)Vj鏈成一個(gè)單鏈表，這個(gè)單鏈表就稱為頂點(diǎn)Vi的鄰接表，再將所有鄰接表的表頭放到數(shù)組中，就構(gòu)成了圖的鄰接表，鄰接表表示中的兩種結(jié)點(diǎn)結(jié)構(gòu)如下所示。一種頂點(diǎn)表的結(jié)點(diǎn)結(jié)構(gòu)，它由頂點(diǎn)域(vertex)和指向第一條鄰接邊的指針域(firstedge)構(gòu)成，另一種是邊表（即鄰接表）結(jié)點(diǎn)，它由鄰接點(diǎn)域(adjvex)和指向下一條鄰接邊的指針域(next)構(gòu)成。2、無(wú)向圖的建立輸入頂點(diǎn)后，將頂點(diǎn)信息存入頂點(diǎn)表的頂點(diǎn)域。在輸入邊的信息后，如輸入的一條邊為

5、XY，則生成新的邊表結(jié)點(diǎn)，將其插入到頂點(diǎn)X的邊表頭部，同理，生成新的邊表結(jié)點(diǎn)，將其插入到頂點(diǎn)Y的邊表頭部。最終完成圖的建立。3、圖的深度優(yōu)先遍歷設(shè)p為指向邊表結(jié)點(diǎn)的指針，首先訪問(wèn)圖的指定的起始頂點(diǎn)V，從V出發(fā)訪問(wèn)一個(gè)與V鄰接的p所指的頂點(diǎn)，并將其壓入棧中，再?gòu)膒所指定點(diǎn)出發(fā)，訪問(wèn)與p所指頂點(diǎn)鄰接且未被訪問(wèn)的頂點(diǎn)，以后從該頂點(diǎn)出發(fā)。重復(fù)上述過(guò)程，知道找不到存在未訪問(wèn)過(guò)的鄰接頂點(diǎn)為止。之后執(zhí)行出棧操作，退回到尚有未訪問(wèn)過(guò)的鄰接點(diǎn)的頂點(diǎn)，從該頂點(diǎn)出發(fā)，重復(fù)之前所述的操作，知道所有被訪問(wèn)過(guò)的頂點(diǎn)的鄰接點(diǎn)都已被訪問(wèn)為止。下

6、圖中的深度優(yōu)先遍歷結(jié)果為ABDCEHJIGF，AFCEHGIJDB等。4、本程序的基本操作和模塊：確定頂點(diǎn)所對(duì)應(yīng)的下標(biāo)的函數(shù)：locate(ALGraph&G,charch)建立圖的鄰接表存儲(chǔ)結(jié)構(gòu)的函數(shù)：Create(ALGraph&G,SeqStack&s)深度優(yōu)先遍歷的函數(shù)：DFS(ALGraph&G,intv,SeqStack&s,intvisited[],inttag)判斷圖是否連通的函數(shù)：Judge(ALGraph&G,intvisited[],SeqStack&s)確定非連通圖連通分量值的函數(shù)：Get

7、(ALGraph&G,intvisited[],SeqStack&s)主函數(shù)：main()函數(shù)的調(diào)用關(guān)系如下圖所示:三詳細(xì)設(shè)計(jì)（一）元素類型、結(jié)點(diǎn)類型1、鄰接表的表示形式描述typedefstructnode//邊表結(jié)點(diǎn){intadjvex;//鄰接點(diǎn)域structnode*next;//指向下一個(gè)鄰接點(diǎn)的指針域}EdgeNode;typedefstructvnode//頂點(diǎn)表結(jié)點(diǎn){charvertex;//頂點(diǎn)域EdgeNode*firstedge;//邊表頭指針}VertexNode;typedefVerte

8、xNodeAdjList[10];//AdjList是鄰接表類型typedefstruct//以鄰接表方式存儲(chǔ)的圖類型{AdjListadjlist;//鄰接表inte;//圖的邊數(shù)}ALGraph;1、順序棧的類型描述typedefstruct//存放訪問(wèn)過(guò)的結(jié)點(diǎn)的棧{EdgeNode*pin[10];//存放邊表結(jié)點(diǎn)的指針inttop;//棧頂指針}SeqStack;