圖基本操作的編程實現(xiàn)湖北汽車工業(yè)學(xué)院數(shù)據(jù)結(jié)構(gòu)

1、撫1此矩車工處學(xué)昵HUBEIUNIVERSITYOFAUTOMOTIVETECHNOLOGY實驗項目圖基本操作的編程實現(xiàn)學(xué)生姓名學(xué)生學(xué)號完成日期2014年12月11日指導(dǎo)教師馬老師，實驗成績評閱日期評閱教師實驗六圖基本操作的編程實現(xiàn)【實驗?zāi)康摹繄D基本操作的編程實現(xiàn)要求：圖基本操作的編程實現(xiàn)（2學(xué)時，驗證型），閱讀程序功能方面要求掌握圖的建立、遍歷、插入、刪除等基本操作的編程實現(xiàn)，程序設(shè)計方面要求掌握圖的遍歷。存儲結(jié)構(gòu)可以在順序結(jié)構(gòu)、鏈接結(jié)構(gòu)等中選擇，也可以全部實現(xiàn)。也鼓勵學(xué)生利用基本操作進行一些應(yīng)用的程序設(shè)計?！緦嶒瀮?nèi)容】一、在給出的程序代碼基礎(chǔ)上，首先排除遇到的語法問題，然后通過填空完成遍歷

2、的任務(wù)，通過自己繪制的圖形進行驗證。本部分資料直接通過.cpp文件直接給出。請注意下載。為了保證在實驗時間內(nèi)完成，最好提前預(yù)習(xí)。涉及的主要問題包括：常用語句也出錯了?；A(chǔ)部分的結(jié)點存儲結(jié)構(gòu)的一維數(shù)組設(shè)計需要自己寫。圖的數(shù)據(jù)結(jié)構(gòu)定義部分。顯示圖的結(jié)構(gòu)。主要遍歷的功能設(shè)計。存儲結(jié)構(gòu)主要是鄰接矩陣，最后可以通過提供參考答案來對比。鄰接表的程序代碼刪除了更多的部分，且不提供參考答案，供有能力的學(xué)生自己研究。二、如果希望自行獨立編程，可以實現(xiàn)對圖進行存儲（鄰接矩陣或鄰接表都可以，學(xué)生自由選擇），之后可以詢問任何兩個結(jié)點之間是否有通路和路徑數(shù)。以下的題目都可以作為獨立編程的題目設(shè)計一個將圖形轉(zhuǎn)成鄰接鏈表的

3、程序。設(shè)計一個深度優(yōu)先搜索法來查找圖形的程序。設(shè)計一個廣度優(yōu)先搜索法來查找一個圖形的程序。鼓勵開發(fā)出難度更高的程序。【思考問題】1. 圖的定義和特性？2. 圖的主要存儲結(jié)構(gòu)是什么？是獨立的某種還是多種數(shù)據(jù)結(jié)構(gòu)的綜合？3. 圖的主要遍歷思路是哪些？4. 舉出圖的應(yīng)用范例？【注意事項】1開發(fā)語言：使用C+。2. 可以自己增加其他功能?！緦嶒灧治?、說明過程】【大體介紹】深度遍歷程序主要是利用了棧的先進后出的思想，回溯，遞歸的思想，而廣度遍歷主要是利用了隊列的思想，先進先出?！旧疃缺闅v】【代碼說明】1先從開始指定的結(jié)點進行訪問，然后標(biāo)記位它為一，（代表他已經(jīng)被訪問過）2然后取他的第一個鄰接點。3然后進

4、入循環(huán)，循環(huán)條件為鄰接點不為空，如果這個鄰接結(jié)點，沒有被標(biāo)記，則執(zhí)行語句遞歸，再次執(zhí)行該函數(shù)，然后再繼續(xù)尋找該點的鄰接結(jié)點，依次進行下去，最后直到遞歸返回到第一層，結(jié)束程序?！井媹D顯示】dat123456122b【廣度遍歷】【代碼說明】1. 從某個結(jié)點開始，把這個結(jié)點入隊，然后設(shè)置標(biāo)志為1.2. 執(zhí)行循環(huán)體里面的內(nèi)容，條件為隊列不為空，循環(huán)體，先將隊列出隊，然后查找這個點是否具有鄰接點，如果有結(jié)點先判斷這個鄰接點是否時被標(biāo)記過的，如果沒被標(biāo)記，就先訪問這個結(jié)點，設(shè)置標(biāo)志位為1,然后入隊。3. 反復(fù)進行2步驟，直到隊列為空?！井媹D演示】【遍歷顯示】【代碼說明】一，關(guān)系矩陣的對角線輸出0；實驗截圖

5、】4eCQCQCOCO5fco1co請輸入選頂：a當(dāng)前圖的坐標(biāo)和結(jié)點如下:0123abed.當(dāng)前圖的鄰接矩陣如下：011oo10co11co6QOOO1CO0COQO0CO110Sf1個列d一序第歷8從遍k定先OO此誅請按任意犍繼綾請輸入選頂：S當(dāng)前圖的坐標(biāo)和結(jié)點如下:012345ahcaef當(dāng)前圖的鄰接矩陣如下已011COcoc：o0co1co10cocococ：c-0c：o1c：c-CO01cc-11e1CQcoGQ熾難"開始遍歷abcdf9請按任意鍵繼續(xù)總結(jié)：對于這次的實驗，由于圖的思想還是不能很好的理解，在編寫程序的時候十分的蹩腳，在圖的遍歷的時候，主要有利用鄰接矩陣為存儲結(jié)

6、構(gòu)，但是對于它的遍歷的思路還不是十分的清晰，有時還會混淆，在自己做完實驗以后，又繼續(xù)對代碼進行研究，還有遍歷的思路進行整理，一遍一遍的畫圖，對照著程序畫圖，將它遍歷的思想深深地理解，現(xiàn)可以利用圖進行編寫程序，也有了那些思想，現(xiàn)在編寫那些程序覺得比以前好了不少，最起碼思路有了一個很大的躍升，編寫代碼順著思路及可以了，雖然還是有不少的漏洞。對于這節(jié)的圖的思路對于以后的編程是有很大的幫助的，這節(jié)課主要是更多的傾向于算法的思想，鄰接矩陣：對于N個點的圖，需要NXN的矩陣表示點與點之間是否有邊的存在。這種表示法的缺點是浪費空間，尤其是對于NXN的矩陣是稀疏矩陣，即邊的數(shù)目遠遠小于NXN的時候，浪費了巨大

7、的存儲空間。鄰接鏈表：對于任何一個nodeA，外掛一個鄰接鏈表，如果存在A->X這樣的邊，就將X鏈入鏈表。這種表示方法的優(yōu)點是節(jié)省空間，缺點是所有鏈表都存在的缺點，地址空間的不連續(xù)造成緩存命中降低，性能有不如臨界矩陣這樣的數(shù)組。【程序部分代碼】voidgraph:depthfirstsearch(constintstartpoint,intvisited,voidvisit(charitem)/探度優(yōu)先遍歷/深度優(yōu)先遍歷實現(xiàn)代碼intneighBorpoint;visit(getvalue(startpoint);visitedstartpoint=l;neighborpoint二get

8、firstneighbor(startpoint);while(neighborpoint!=-l)if(!visitedneighborpoint)depthfirstsearch(neighborpoint,visited,visit);neighborpoint二getnextneighbor(startpoint,neighborpoint);voidgraph:breadthfirstsearch(constintstartpoint,intvisited,voidvisit(charitem)/廣度優(yōu)先遍歷/廣度優(yōu)先遍歷實現(xiàn)代碼chargetqueuehead,neighborpo

9、int;SeqQueuequeue;visit(getvalue(startpoint);visitedstartpoint=l;queue.enqueue(startpoint);while(!queue.isempty()getqueuehead二queue.dequeue();neighborpoint二getfirstneighbor(getqueuehead);while(neighborpoint!=l)if(!visitedneighborpoint)visit(getvalue(neighborpoint);visitedneighborpoint=l;queue.enqueue(neighborpoint);neighborpoint二getnextneighbor(getqueuehead,neighborpoint);voidgraph:showgraph()/圖的顯示函數(shù)for(i=0;i<Vertices.ListSize();i+)/用鄰接矩陣來模擬圖的邊的相關(guān)