數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--圖的遍歷

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 1.引 言 數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門核心專業(yè)基礎(chǔ)課程，是一門理論性強(qiáng)、思維抽象、難度較大的課程。在軟件工程專業(yè)的課程體系中起著承上啟下的作用，學(xué)好數(shù)據(jù)結(jié)構(gòu)對(duì)于提高理論認(rèn)知水平和實(shí)踐能力有著極為重要的作用。通過(guò)本門課程的學(xué)習(xí)，我們應(yīng)該能透徹地理解各種數(shù)據(jù)對(duì)象的特點(diǎn)，學(xué)會(huì)數(shù)據(jù)的組織方法和實(shí)現(xiàn)方法，并進(jìn)一步培養(yǎng)良好的程序設(shè)計(jì)能力和解決實(shí)際問(wèn)題的能力。我認(rèn)為學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的最終目的是為了獲得求解問(wèn)題的能力。對(duì)于現(xiàn)實(shí)世界中的問(wèn)題，我們應(yīng)該能從中抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型，該數(shù)學(xué)模型在計(jì)算機(jī)內(nèi)部用相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來(lái)表示，然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法，再進(jìn)行編程調(diào)試，最后

2、獲得問(wèn)題的解答。 圖是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，在數(shù)據(jù)結(jié)構(gòu)中也占著相當(dāng)大的比重。這個(gè)學(xué)期的數(shù)據(jù)結(jié)構(gòu)課程中，我們學(xué)習(xí)了很多圖的存儲(chǔ)結(jié)構(gòu)，有鄰接矩陣、鄰接表、十字鏈表等。其中鄰接矩陣和鄰接表為圖的主要存儲(chǔ)結(jié)構(gòu)。圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)的主要特點(diǎn)是把圖的邊信息存儲(chǔ)在一個(gè)矩陣中，是一種靜態(tài)存儲(chǔ)方法。圖的鄰接表存儲(chǔ)結(jié)構(gòu)是一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)相結(jié)合的存儲(chǔ)方法。從空間性能上說(shuō)，圖越稀疏鄰接表的空間效率相應(yīng)的越高。從時(shí)間性能上來(lái)說(shuō)，鄰接表在圖的算法中時(shí)間代價(jià)較鄰接矩陣要低。 本課程設(shè)計(jì)主要是實(shí)現(xiàn)使用鄰接表存儲(chǔ)結(jié)構(gòu)存儲(chǔ)一個(gè)圖，并在所存儲(chǔ)的圖中實(shí)現(xiàn)深度優(yōu)先和廣度優(yōu)先遍歷以及其鏈表結(jié)構(gòu)的輸出。 2.需求分析2.1 原理

3、當(dāng)圖比較稀疏時(shí)，鄰接表存儲(chǔ)是最佳的選擇。并且在存儲(chǔ)圖的時(shí)候鄰接表要比鄰接矩陣節(jié)省時(shí)間。在圖存儲(chǔ)在系統(tǒng)中后，我們有時(shí)還需要對(duì)圖進(jìn)行一些操作，如需要添加一個(gè)頂點(diǎn)，修改一個(gè)頂點(diǎn)，或者刪除一個(gè)頂點(diǎn)，而這些操作都需要一圖的深度優(yōu)先及廣度優(yōu)先遍歷為基礎(chǔ)。本系統(tǒng)將構(gòu)建一個(gè)圖，圖的結(jié)點(diǎn)存儲(chǔ)的是int型數(shù)據(jù)。運(yùn)行本系統(tǒng)可對(duì)該圖進(jìn)行鏈?zhǔn)浇Y(jié)構(gòu)輸出、深度優(yōu)先及廣度優(yōu)先遍歷?？刂品椒ㄈ缦拢?表2-1 控制鍵的功能 控制鍵 1 2 3 0 功能 輸出鏈 表結(jié)構(gòu) 深度優(yōu) 先遍歷 廣度優(yōu) 先遍歷 退出2.2 要求（1）建立基于鄰接表的圖；（2）對(duì)圖進(jìn)行遍歷；（3）輸出遍歷結(jié)果；2.3 運(yùn)行環(huán)境 (1)WINDOWS 7系統(tǒng)

4、(2)C+ 編譯環(huán)境2.4 開發(fā)工具C+語(yǔ)言 3.數(shù)據(jù)結(jié)構(gòu)分析本課程設(shè)計(jì)是針對(duì)于圖的，程序中采用鄰接表進(jìn)行數(shù)據(jù)存儲(chǔ)。在計(jì)算機(jī)科學(xué)中，鄰接表描述一種緊密相關(guān)的數(shù)據(jù)結(jié)構(gòu)，用于表征圖。在 鄰接表的表示中，對(duì)于圖中的每個(gè)頂點(diǎn)，我們將保存所有其它與之相連的頂點(diǎn)（即 “鄰接表”）。 鄰接表是一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)相結(jié)合的存儲(chǔ)方法，該存儲(chǔ)方式在圖比較稀疏是相對(duì)于圖的鄰接矩陣存儲(chǔ)有明顯優(yōu)勢(shì)。設(shè)計(jì)實(shí)現(xiàn)了圖的鄰接表結(jié)構(gòu)輸出、深度有新遍歷和廣度優(yōu)先遍歷操作的實(shí)現(xiàn)。鄰接表的結(jié)構(gòu)：（1） 、頭結(jié)點(diǎn)結(jié)構(gòu)firstarcdata Firstarc：結(jié)點(diǎn)的指針域（2） 、鄰接點(diǎn)的結(jié)構(gòu)nextarcadjvex Adjvex：

5、鄰接點(diǎn)的數(shù)據(jù)域； Nextarc：鄰接點(diǎn)的指針域，指向下一個(gè)鄰接點(diǎn)；在該程序中，除了鄰接表結(jié)構(gòu)以外，還有到了一個(gè)mark數(shù)組，它是用來(lái)標(biāo)記結(jié)點(diǎn)Vi是否被訪問(wèn)。若Vi被訪問(wèn)，則marki=1，否則為0；它是一個(gè)比較簡(jiǎn)單的一維數(shù)組。（注：在每次對(duì)圖進(jìn)行遍歷之前mark都會(huì)被清零）圖的深度優(yōu)先訪問(wèn)：從圖中每個(gè)頂點(diǎn)V出發(fā)，訪問(wèn)此頂點(diǎn)，然后依次從V的未訪問(wèn)鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至所有與V有通路的頂點(diǎn)被訪問(wèn)，否則選擇另外未訪問(wèn)點(diǎn)作為起點(diǎn)，重復(fù)上述過(guò)程。圖的廣度優(yōu)先遍歷：從圖中每個(gè)頂點(diǎn)V出發(fā)，訪問(wèn)此頂點(diǎn)，然后依次訪問(wèn)V的未訪問(wèn)鄰接點(diǎn)，并保證先被訪問(wèn)的結(jié)點(diǎn)的鄰接點(diǎn)先于后被訪問(wèn)的結(jié)點(diǎn)，直至所有與V有通路的

6、頂點(diǎn)被訪問(wèn)，否則選擇另外未訪問(wèn)點(diǎn)作為起點(diǎn)，重復(fù)上述過(guò)程。 4.算法設(shè)計(jì)（1）首先，要定義頭文件，在頭文件中定義鄰接點(diǎn)point、圖的基本結(jié)點(diǎn)graph以及在廣度優(yōu)先搜索中會(huì)用到隊(duì)列queue。具體如下：struct point int n; /鄰接點(diǎn)的序號(hào)point *next; /指向下一條弧節(jié)點(diǎn)的地址;struct graphint data; /表接點(diǎn)的數(shù)據(jù)struct point *f; /結(jié)點(diǎn)的指針域，給出自該結(jié)點(diǎn)發(fā)出的第 一弧節(jié)點(diǎn)的地址;struct queueint elemd; /隊(duì)列的容量int front; /front為首指針，指向第一個(gè)元素int rear; /rear

7、為最后一個(gè)元素，指向隊(duì)尾元素的下一個(gè)位置q; 其次，在頭文件中還需定義鄰接表存儲(chǔ)結(jié)構(gòu)下圖的抽象數(shù)據(jù)類型定義。 （2）編寫源文件，進(jìn)行圖的初始化，首先要輸入頂點(diǎn)信息，初始化頂點(diǎn)表，在輸入點(diǎn)v的值時(shí)，同時(shí)構(gòu)造v的鄰接點(diǎn)。輸入鄰接點(diǎn)的序號(hào)，最后生成一個(gè)鄰接點(diǎn)鏈表。子函數(shù)功能：1.void creatgraph(int m) /n表示節(jié)點(diǎn)的個(gè)數(shù) 構(gòu)造圖的鏈表結(jié)構(gòu)，在此函數(shù)中要輸入圖結(jié)點(diǎn)的值，鄰接點(diǎn)的序號(hào)。2.void print(struct graph a,int m) 將圖a的鏈表結(jié)構(gòu)打印出來(lái),m為結(jié)點(diǎn)個(gè)數(shù)3.void dpv(struct graph a,int v) 對(duì)圖進(jìn)行深度優(yōu)先遍歷。先訪

8、問(wèn)指定的頂點(diǎn)v，從該頂點(diǎn)的未被訪問(wèn)的鄰接點(diǎn)中選取一個(gè)頂點(diǎn)p,從p出發(fā)進(jìn)行深度優(yōu)先遍歷。重復(fù)以上的步驟，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問(wèn)到。4.void wdv(struct graph a,int v,queue &Q) 從v點(diǎn)開始廣度優(yōu)先遍歷a是連通圖或是連通分量），先訪問(wèn)頂點(diǎn)v，依次訪問(wèn)v的各個(gè)未被訪問(wèn)的鄰接點(diǎn)v1,v2,vk,分別從,v1,v2,vk出發(fā)依次訪問(wèn)它們未被訪問(wèn)的鄰接點(diǎn)，并使“先被訪問(wèn)頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問(wèn)的頂點(diǎn)”被訪問(wèn)，直至圖中所有與頂點(diǎn)v有路徑相通的頂點(diǎn)都被訪問(wèn)到。5.void enqueue(queue &Q,int e) e入隊(duì)列Q的隊(duì)尾

9、。 6.void delqueue(queue &Q,int &e) 刪除隊(duì)列Q的對(duì)首元素。7.int queueempty(queue &Q) 判斷隊(duì)列Q是否為空。（3）編寫主函數(shù)。用數(shù)組存放圖結(jié)點(diǎn)。輸入所要進(jìn)行的操作的序號(hào)，并設(shè)置每次只能選擇一種功能，調(diào)用相應(yīng)的函數(shù)，輸出相應(yīng)的結(jié)果。4.2 主要模塊的算法描述（1）、深度優(yōu)先遍歷算法，利用遞歸void dpv(graph a,vtxptr v0) /從點(diǎn)v開始進(jìn)行深度訪問(wèn) /a為連通圖或非連通圖的一個(gè)連通分量visit（v0）； /訪問(wèn)v結(jié)點(diǎn)markv0=1; /標(biāo)記為已訪問(wèn) w=v0的第一個(gè)鄰接點(diǎn)；while(當(dāng)鄰

10、接點(diǎn)w存在時(shí)1)if(w未訪問(wèn))dpv(a,w);w=下一個(gè)鄰接點(diǎn)；/dpv（2）、廣度優(yōu)先遍歷算法，利用隊(duì)列先入先出void wdv(graph a,vtxptr v)/從v點(diǎn)開始廣度優(yōu)先，a是連通圖或是連通分量visit（v）； /訪問(wèn)點(diǎn)vmarkv=1; /并標(biāo)記為以訪問(wèn) initqueue（Q)；enqueue(Q,v);/v進(jìn)隊(duì)列while(!queueempty(Q)delqueue(Q,v1);w=v1的第一個(gè)鄰接點(diǎn)；while(當(dāng)鄰接點(diǎn)w存在時(shí))if(w為訪問(wèn))visit（w）； markw=1; enqueue(Q,w);w=下一個(gè)鄰接點(diǎn)； /wdv4.3 函數(shù)調(diào)用圖 5.程

11、序?qū)崿F(xiàn)及測(cè)試5.1 創(chuàng)建工程并建立文件（1）啟動(dòng)Microsoft Visual C+ 6.0。（2）新建工程名為“課程設(shè)計(jì)” 的Win32控制臺(tái)應(yīng)用程序。（3）建立頭文件“鄰接表.cpp”，在其中定義圖的創(chuàng)建函數(shù)creategraph()、深度優(yōu)先遍歷的函數(shù)dpv()、廣度優(yōu)先遍歷的函數(shù)wdv()、輸出函數(shù)print（）以及main（），通過(guò)main（）調(diào)用其他函數(shù)來(lái)實(shí)現(xiàn)對(duì)圖的操作。5.2 測(cè)試及運(yùn)行狀況（1） 、創(chuàng)建用戶所給圖的存儲(chǔ)結(jié)構(gòu)，鄰接表存儲(chǔ)。主函數(shù)main（）會(huì)調(diào)用函數(shù)creategraph ( )；假如圖為下示： V1（12） V2（45） V4（15）V3（37） V5（26）

12、 （2） 、在選項(xiàng)中選擇1，進(jìn)行顯示圖的鏈?zhǔn)浇Y(jié)構(gòu)的操作；（3） 、選擇2進(jìn)行深度優(yōu)先遍歷，并輸出結(jié)果；（4） 、選擇3進(jìn)行廣度優(yōu)先遍歷，并輸出結(jié)果（5） 、選擇0退出系統(tǒng)；（6） 、當(dāng)用戶選擇的選項(xiàng)不存在時(shí)，系統(tǒng)會(huì)提示重新選擇；（7） 、當(dāng)進(jìn)行遍歷時(shí)，選擇的初始結(jié)點(diǎn)不存在，系統(tǒng)會(huì)提醒重新輸入開始結(jié)點(diǎn)以便繼續(xù)遍歷；上述就是對(duì)該系統(tǒng)的測(cè)試過(guò)程。 6. 心得體會(huì)在這次數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)中遇到了很多實(shí)際性的問(wèn)題，在實(shí)際設(shè)計(jì)中才發(fā)現(xiàn)，書本上理論性的東西與在實(shí)際運(yùn)用中的還是有一定的出入的，所以有些問(wèn)題要不斷地更正以前的錯(cuò)誤思維。通過(guò)這次設(shè)計(jì)，我知道編寫程序既是一件艱苦的工作，又是一件愉快的事情。編程時(shí)如果遇到看

13、似簡(jiǎn)單但又無(wú)法解決的問(wèn)題，很容易灰心喪氣。此時(shí)切不可煩躁，一定要冷靜的思考，認(rèn)真的分析，其過(guò)程為：面對(duì)問(wèn)題，接受問(wèn)題，處理問(wèn)題，解決問(wèn)題。同時(shí)我懂得了學(xué)習(xí)的重要性，了解到理論知識(shí)與實(shí)踐相結(jié)合的重要意義，學(xué)會(huì)了堅(jiān)持、耐心和努力，這將為自己今后的學(xué)習(xí)和工作做出了最好的榜樣。我覺(jué)得作為一名軟件工程專業(yè)的學(xué)生，這次課程設(shè)計(jì)是很有意義的。更重要的是如何把自己平時(shí)所學(xué)的東西應(yīng)用到實(shí)際中。雖然自己對(duì)于這門課懂的并不多，很多基礎(chǔ)的東西都還沒(méi)有很好的掌握，覺(jué)得很難，但是靠著學(xué)習(xí)和實(shí)踐，我相信自己一定能做的更好。 7.結(jié)束語(yǔ) 經(jīng)過(guò)幾天的努力，黃天不負(fù)苦心人，我的課程設(shè)計(jì)終于完成了。本課程設(shè)計(jì)主要運(yùn)用數(shù)據(jù)結(jié)構(gòu)知識(shí)和C+程序設(shè)計(jì)完成了用鄰接表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)對(duì)圖的操作。該系統(tǒng)的主要功能為：圖的鏈?zhǔn)浇Y(jié)構(gòu)輸出、深度優(yōu)先遍歷、廣度優(yōu)先遍歷。 在這次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)中，曾遇到過(guò)一些問(wèn)題，但是經(jīng)過(guò)查找資料都已經(jīng)得到解決，也正是因?yàn)檫@些問(wèn)題引發(fā)的思考給我?guī)Я耸斋@。所以我認(rèn)為只要我們有耐心和信心，我們一定能解決問(wèn)題。再次