圖結構的課程設計


本文共計16頁，4939字；

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

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