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

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

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

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

3、安裝了VisualC++6.0，所以C++是我編程的最佳選擇。2問題分析2.1技術(shù)分析C++是一種靜態(tài)數(shù)據(jù)類型檢查的，支持多重編程范式的通用程序設(shè)計(jì)語言。它支持過程化程序設(shè)計(jì)、數(shù)據(jù)抽象、面向?qū)ο蟪绦蛟O(shè)計(jì)、制作圖標(biāo)等等泛型程序設(shè)計(jì)等多種程序設(shè)計(jì)風(fēng)格。它是由C語言發(fā)展而來的，既可以用于面向過程的結(jié)構(gòu)化程序設(shè)計(jì)，也可以用于面向?qū)ο蟮某绦蛟O(shè)計(jì),是一門功能強(qiáng)大的程序設(shè)計(jì)語言[2]。VisualC++6.0是Microsoft公司在1998年推出的基于Windows9X和WindowsNT一個(gè)優(yōu)秀集成開發(fā)環(huán)境。該開發(fā)環(huán)境為用戶提供了良好的可視化編程環(huán)境，程序員可以利用該開發(fā)環(huán)境輕松地訪問C++源代碼編

4、輯器、資源編輯器和使用內(nèi)部調(diào)試器，并且可以創(chuàng)建項(xiàng)目文件。VisualC++6.0不僅包括編譯器，而且它還包括許多有用組件，如程序向?qū)ppWizard、類向?qū)lassWizard等，通過這些組件的協(xié)同工作，可以在VisualC++6.0集成開發(fā)環(huán)境中輕松的完成創(chuàng)建源文件、編輯資源，以及對程序的編譯、連接和調(diào)試等各項(xiàng)工作[5]2.2需求分析當(dāng)圖比較稀疏時(shí)，鄰接表存儲是最佳的選擇。并且在存儲圖的時(shí)候鄰接表要比鄰接矩陣節(jié)省時(shí)間。在圖存儲在系統(tǒng)中后，我們有時(shí)還需要對圖進(jìn)行一些操作，如需要添加一個(gè)頂點(diǎn)，修改一個(gè)頂點(diǎn)，或者刪除一個(gè)頂點(diǎn)。還有時(shí)需要對圖進(jìn)行深度優(yōu)先及廣度優(yōu)先遍歷。本系統(tǒng)將所有這些功能都

5、包括進(jìn)來，以長沙理工大學(xué)的教學(xué)樓為頂點(diǎn)構(gòu)建了一個(gè)圖。運(yùn)行本系統(tǒng)可對該圖進(jìn)行頂點(diǎn)的插入、刪除和修改，還可對該圖進(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)的主要功能是用鄰接表存儲結(jié)構(gòu)在圖中對頂點(diǎn)進(jìn)行插入、刪除、修改操作，并對圖進(jìn)行深度優(yōu)先及廣度優(yōu)先遍歷?？偪蚣苋缦拢猴@示“需要輸出頂點(diǎn)信息請按0需要輸出任一頂點(diǎn)信息請按1需要插入頂點(diǎn)請按2需要修改頂點(diǎn)請按3需要?jiǎng)h除頂點(diǎn)請按4需要深度優(yōu)先遍歷請按5需要廣度優(yōu)先遍歷請按6需要退出請按7”輸入所

6、要執(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)域ArcNode*next;};//指向下一個(gè)邊結(jié)點(diǎn)的指針templatestructVertexNode//定義頂點(diǎn)表結(jié)點(diǎn){Tvertex;//頂點(diǎn)的名稱ArcNode*firstedge;};//邊表的頭指針其次，在頭文件中還需定義鄰接表存儲結(jié)構(gòu)下圖的抽象數(shù)據(jù)類型定義。（2）編寫源文件，必須

7、先引入頭文件。然后進(jìn)行圖的初始化，首先要輸入頂點(diǎn)信息，初始化頂點(diǎn)表。然后依次輸入每一條邊，并在相應(yīng)邊表中插入結(jié)點(diǎn)。再輸入邊所依附的兩個(gè)頂點(diǎn)的序號。最后生成一個(gè)編表結(jié)點(diǎn)，將生成的結(jié)點(diǎn)插入到編表的表頭。接下來編寫對圖進(jìn)行的各種操作。用析構(gòu)函數(shù)~ALGraph()循環(huán)刪除釋放節(jié)點(diǎn)空間。ALGraph::~ALGraph(){for(inti=0;i