圖結(jié)構(gòu)的課程設(shè)計(jì)
全文16頁(yè)4939字 敘述詳盡
1前言
圖(graph)是比線性表、樹(shù)與二叉樹(shù)更為復(fù)雜的一種數(shù)據(jù)結(jié)構(gòu)。在圖這種數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)結(jié)點(diǎn)之間的聯(lián)系是任意的，因此，圖這種數(shù)據(jù)結(jié)構(gòu)可以更廣泛的表示數(shù)據(jù)之間的關(guān)系?？梢哉f(shuō)，線性表、二叉樹(shù)是圖的特例，也可以說(shuō)，線性表、樹(shù)與二叉樹(shù)是最簡(jiǎn)單的圖。
由于圖的結(jié)構(gòu)比較復(fù)雜，圖中任意兩個(gè)結(jié)點(diǎn)之間都有可能存在聯(lián)系，無(wú)法用數(shù)據(jù)元素在存儲(chǔ)空間中的物理位置來(lái)表示各數(shù)據(jù)元素之間的前后件關(guān)系。另外，圖中各結(jié)點(diǎn)的度不相同，其最大度數(shù)與最小度數(shù)可能相差很大，用多重鏈表作為圖的存儲(chǔ)結(jié)構(gòu)也是很不方便的。因此，在實(shí)際應(yīng)用中，一般是根據(jù)對(duì)圖的具體運(yùn)算來(lái)選取合適的存儲(chǔ)結(jié)構(gòu)。
圖有著極為廣泛的應(yīng)用。例如，用圖可以表示有公共交通聯(lián)系的一組城市，也可以描述化學(xué)結(jié)構(gòu)式、交通網(wǎng)絡(luò)等。
目 錄
1前言 1
2 圖的存儲(chǔ) 1
3 圖的遍歷 1
3.1 圖的深度優(yōu)先遍歷 1
3.2 圖的廣度優(yōu)先遍歷 2
4 算法描述 2
4.1 圖的存儲(chǔ)結(jié)構(gòu)的建立 2
4.1.1 定義鄰接表的邊結(jié)點(diǎn)類(lèi)型以及鄰接表類(lèi)型 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 程序測(cè)試 13
8 總結(jié)與體會(huì) 14
參考文獻(xiàn) 15
圖(graph)是比線性表、樹(shù)與二叉樹(shù)更為復(fù)雜的一種數(shù)據(jù)結(jié)構(gòu)。在圖這種數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)結(jié)點(diǎn)之間的聯(lián)系是任意的，因此，圖這種數(shù)據(jù)結(jié)構(gòu)可以更廣泛的表示數(shù)據(jù)之間的關(guān)系?？梢哉f(shuō)，線性表、二叉樹(shù)是圖的特例，也可以說(shuō)，線性表、樹(shù)與二叉樹(shù)是最簡(jiǎn)單的圖。
由于圖的結(jié)構(gòu)比較復(fù)雜，圖中任意兩個(gè)結(jié)點(diǎn)之間都有可能存在聯(lián)系，無(wú)法用數(shù)據(jù)元素在存儲(chǔ)空間中的物理位置來(lái)表示各數(shù)據(jù)元素之間的前后件關(guān)系。另外，圖中各結(jié)點(diǎn)的度不相同，其最大度數(shù)與最小度數(shù)可能相差很大，用多重鏈表作為圖的存儲(chǔ)結(jié)構(gòu)也是很不方便的。因此，在實(shí)際應(yīng)用中，一般是根據(jù)對(duì)圖的具體運(yùn)算來(lái)選取合適的存儲(chǔ)結(jié)構(gòu)。
圖有著極為廣泛的應(yīng)用。例如，用圖可以表示有公共交通聯(lián)系的一組城市，也可以描述化學(xué)結(jié)構(gòu)式、交通網(wǎng)絡(luò)等。
參考文獻(xiàn)
[1] 徐士良.計(jì)算機(jī)軟件技術(shù)基礎(chǔ)[M].北京:清華大學(xué)出版社，2002
[2] 陳維鈞.計(jì)算機(jī)軟件基礎(chǔ)[M].上海:上海交通大學(xué)出版社，1996
[3] 夏克儉.數(shù)據(jù)結(jié)構(gòu)[M].北京:國(guó)防工業(yè)出版社，2007
[4] 李建學(xué).數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)案例精編[M].北京:清華大學(xué)出版社，2007
[5] 朱明方.機(jī)械工業(yè)出版社[M].北京:機(jī)械工業(yè)出版社,2007