圖結(jié)構(gòu)的課程設(shè)計


本文共計16頁，4939字；

摘要:
圖(graph)是比線性表、樹與二叉樹更為復(fù)雜的一種數(shù)據(jù)結(jié)構(gòu)。在圖這種數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)結(jié)點之間的聯(lián)系是任意的，因此，圖這種數(shù)據(jù)結(jié)構(gòu)可以更廣泛的表示數(shù)據(jù)之間的關(guān)系。可以說，線性表、二叉樹是圖的特例，也可以說，線性表、樹與二叉樹是最簡單的圖。
由于圖的結(jié)構(gòu)比較復(fù)雜，圖中任意兩個結(jié)點之間都有可能存在聯(lián)系，無法用數(shù)據(jù)元素在存儲空間中的物理位置來表示各數(shù)據(jù)元素之間的前后件關(guān)系。另外，圖中各結(jié)點的度不相同，其最大度數(shù)與最小度數(shù)可能相差很大，用多重鏈表作為圖的存儲結(jié)構(gòu)也是很不方便的。因此，在實際應(yīng)用中，一般是根據(jù)對圖的具體運算來選取合適的存儲結(jié)構(gòu)。
圖有著極為廣泛的應(yīng)用。例如，用圖可以表示有公共交通聯(lián)系的一組城市，也可以描述化學(xué)結(jié)構(gòu)式、交通網(wǎng)絡(luò)等。
目 錄
1前言 1
2 圖的存儲 1
3 圖的遍歷 1
3.1 圖的深度優(yōu)先遍歷 1
3.2 圖的廣度優(yōu)先遍歷 2
4 算法描述 2
4.1 圖的存儲結(jié)構(gòu)的建立 2
4.1.1 定義鄰接表的邊結(jié)點類型以及鄰接表類型 2
4.1.2 初始化圖的鄰接表 3
4.1.3 建立并輸出圖的鄰接表 3
4.2 圖的遍歷 4
4.2.1 深度優(yōu)先遍歷圖的鄰接表 4
4.2.2 廣度優(yōu)先遍歷圖的鄰接表 5
5 程序流程圖 5
6 圖的遍歷源程序 7
7 程序測試 13
8 總結(jié)與體會 14
參考文獻 15

參考文獻
[1] 徐士良.計算機軟件技術(shù)基礎(chǔ)[M].北京:清華大學(xué)出版社，2002
[2] 陳維鈞.計算機軟件基礎(chǔ)[M].上海:上海交通大學(xué)出版社，1996
[3] 夏克儉.數(shù)據(jù)結(jié)構(gòu)[M].北京:國防工業(yè)出版社，2007
[4] 李建學(xué).數(shù)據(jù)結(jié)構(gòu)課程設(shè)計案例精編[M].北京:清華大學(xué)出版社，2007
[5] 朱明方.機械工業(yè)出版社[M].北京:機械工業(yè)出版社,2007