用鄰接表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)圖的遍歷

《用鄰接表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)圖的遍歷》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、用鄰接表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)圖的遍歷學(xué)生姓名：XXXX指導(dǎo)老師：XXXX摘要本課程設(shè)計(jì)主要實(shí)現(xiàn)用鄰接表存儲(chǔ)結(jié)構(gòu)對(duì)圖進(jìn)行操作。在課程設(shè)計(jì)中，系統(tǒng)開(kāi)發(fā)平臺(tái)為Windows2000，程序設(shè)計(jì)語(yǔ)言采用VisualC++，程序運(yùn)行平臺(tái)為Windows98/2000/XP。用鄰接表存儲(chǔ)結(jié)構(gòu)在圖中對(duì)頂點(diǎn)進(jìn)行插入、刪除、修改操作，對(duì)圖進(jìn)行深度優(yōu)先及廣度優(yōu)先遍歷。程序通過(guò)調(diào)試運(yùn)行，實(shí)現(xiàn)了設(shè)計(jì)的目標(biāo)。關(guān)鍵詞程序設(shè)計(jì)；C++；鄰接表；圖1引言上學(xué)期我們學(xué)習(xí)了很多圖的存儲(chǔ)結(jié)構(gòu)，有鄰接矩陣、鄰接表、十字鏈表等。其中鄰接矩陣和鄰接表為圖的主要存儲(chǔ)結(jié)構(gòu)。圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)的主

2、要特點(diǎn)是把圖的邊信息存儲(chǔ)在一個(gè)矩陣中，是一種靜態(tài)存儲(chǔ)方法。圖的鄰接表存儲(chǔ)結(jié)構(gòu)就是圖的邊信息的矩陣中全部非零元素的三元組的行指針數(shù)組結(jié)構(gòu)的三元組鏈表，是一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)相結(jié)合的存儲(chǔ)方法[1]。二者各有利弊，具體應(yīng)用時(shí)，要根據(jù)圖的稠密和稀疏程度以及問(wèn)題需求進(jìn)行選擇。從空間性能上說(shuō)，圖越稀疏鄰接表的空間效率相應(yīng)的越高。從時(shí)間性能上來(lái)說(shuō)，鄰接表在圖的算法中時(shí)間代價(jià)較鄰接矩陣要低[3]。本課程設(shè)計(jì)主要是實(shí)現(xiàn)使用鄰接表存儲(chǔ)結(jié)構(gòu)存儲(chǔ)一個(gè)圖，并在所存儲(chǔ)的圖中實(shí)現(xiàn)結(jié)點(diǎn)的插入、刪除和修改操作，以及對(duì)圖實(shí)現(xiàn)深度優(yōu)先和廣度優(yōu)先遍歷。本課程設(shè)計(jì)是用C++語(yǔ)言輔

3、助完成，在VisualC++6.0平臺(tái)實(shí)現(xiàn)的。我們大一學(xué)過(guò)C++，對(duì)C++比較熟悉。并且我自己電腦上安裝了VisualC++6.0，所以C++是我編程的最佳選擇。2問(wèn)題分析2.1技術(shù)分析C++是一種靜態(tài)數(shù)據(jù)類型檢查的，支持多重編程范式的通用程序設(shè)計(jì)語(yǔ)言。它支持過(guò)程化程序設(shè)計(jì)、數(shù)據(jù)抽象、面向?qū)ο蟪绦蛟O(shè)計(jì)、制作圖標(biāo)等等泛型程序設(shè)計(jì)等多種程序設(shè)計(jì)風(fēng)格。它是由C語(yǔ)言發(fā)展而來(lái)的，既可以用于面向過(guò)程的結(jié)構(gòu)化程序設(shè)計(jì)，也可以用于面向?qū)ο蟮某绦蛟O(shè)計(jì),是一門(mén)功能強(qiáng)大的程序設(shè)計(jì)語(yǔ)言[2]。VisualC++6.0是Microsoft公司在1998年推出的基于W

4、indows9X和WindowsNT一個(gè)優(yōu)秀集成開(kāi)發(fā)環(huán)境。該開(kāi)發(fā)環(huán)境為用戶提供了良好的可視化編程環(huán)境，程序員可以利用該開(kāi)發(fā)環(huán)境輕松地訪問(wèn)C++源代碼編輯器、資源編輯器和使用內(nèi)部調(diào)試器，并且可以創(chuàng)建項(xiàng)目文件。VisualC++6.0不僅包括編譯器，而且它還包括許多有用組件，如程序向?qū)ppWizard、類向?qū)lassWizard等，通過(guò)這些組件的協(xié)同工作，可以在VisualC++6.0集成開(kāi)發(fā)環(huán)境中輕松的完成創(chuàng)建源文件、編輯資源，以及對(duì)程序的編譯、連接和調(diào)試等各項(xiàng)工作[5]2.2需求分析當(dāng)圖比較稀疏時(shí)，鄰接表存儲(chǔ)是最佳的選擇。并且在存儲(chǔ)圖的

5、時(shí)候鄰接表要比鄰接矩陣節(jié)省時(shí)間。在圖存儲(chǔ)在系統(tǒng)中后，我們有時(shí)還需要對(duì)圖進(jìn)行一些操作，如需要添加一個(gè)頂點(diǎn)，修改一個(gè)頂點(diǎn)，或者刪除一個(gè)頂點(diǎn)。還有時(shí)需要對(duì)圖進(jìn)行深度優(yōu)先及廣度優(yōu)先遍歷。本系統(tǒng)將所有這些功能都包括進(jìn)來(lái)，以長(zhǎng)沙理工大學(xué)的教學(xué)樓為頂點(diǎn)構(gòu)建了一個(gè)圖。運(yùn)行本系統(tǒng)可對(duì)該圖進(jìn)行頂點(diǎn)的插入、刪除和修改，還可對(duì)該圖進(jìn)行深度優(yōu)先及廣度優(yōu)先遍歷。控制方法如下：表2-1控制鍵的功能控制鍵01234567功能輸出輸出任插入修改刪除深度優(yōu)廣度優(yōu)退出頂點(diǎn)一頂點(diǎn)頂點(diǎn)頂點(diǎn)頂點(diǎn)先遍歷先遍歷3系統(tǒng)總框架及算法設(shè)計(jì)3.1系統(tǒng)總框架系統(tǒng)的主要功能是用鄰接表存儲(chǔ)結(jié)構(gòu)在圖中對(duì)

6、頂點(diǎn)進(jìn)行插入、刪除、修改操作，并對(duì)圖進(jìn)行深度優(yōu)先及廣度優(yōu)先遍歷?？偪蚣苋缦拢猴@示“需要輸出頂點(diǎn)信息請(qǐng)按0需要輸出任一頂點(diǎn)信息請(qǐng)按1需要插入頂點(diǎn)請(qǐng)按2需要修改頂點(diǎn)請(qǐng)按3需要?jiǎng)h除頂點(diǎn)請(qǐng)按4需要深度優(yōu)先遍歷請(qǐng)按5需要廣度優(yōu)先遍歷請(qǐng)按6需要退出請(qǐng)按7”輸入所要執(zhí)行的功能。頂點(diǎn)的輸出、插入、刪除與修改退出系統(tǒng)圖的深度及廣度優(yōu)先遍歷圖3-1系統(tǒng)總框架3.2算法設(shè)計(jì)（1）首先，要定義頭文件，在頭文件中定義邊表結(jié)點(diǎn)ArcNode和頂點(diǎn)表結(jié)點(diǎn)VertexNode。具體如下：structArcNode//定義邊表結(jié)點(diǎn){intadjvex;//鄰接點(diǎn)域ArcNo

7、de*next;};//指向下一個(gè)邊結(jié)點(diǎn)的指針templatestructVertexNode//定義頂點(diǎn)表結(jié)點(diǎn){Tvertex;//頂點(diǎn)的名稱ArcNode*firstedge;};//邊表的頭指針其次，在頭文件中還需定義鄰接表存儲(chǔ)結(jié)構(gòu)下圖的抽象數(shù)據(jù)類型定義。（2）編寫(xiě)源文件，必須先引入頭文件。然后進(jìn)行圖的初始化，首先要輸入頂點(diǎn)信息，初始化頂點(diǎn)表。然后依次輸入每一條邊，并在相應(yīng)邊表中插入結(jié)點(diǎn)。再輸入邊所依附的兩個(gè)頂點(diǎn)的序號(hào)。最后生成一個(gè)編表結(jié)點(diǎn)，將生成的結(jié)點(diǎn)插入到編表的表頭。接下來(lái)編寫(xiě)對(duì)圖進(jìn)行的各種操作。用析構(gòu)函數(shù)~ALG

8、raph()循環(huán)刪除釋放節(jié)點(diǎn)空間。ALGraph::~ALGraph(){for(inti=0;i