目 錄
項目一 數(shù)據(jù)結(jié)構(gòu)概述························································································1
任務(wù)一 數(shù)據(jù)結(jié)構(gòu)概述··················································································1
任務(wù)引入······························································································1
任務(wù)分析······························································································1
知識準備······························································································2
一、基本概念························································································2
二、研究對象························································································3
三、數(shù)據(jù)邏輯結(jié)構(gòu)分類············································································5
四、常用數(shù)據(jù)結(jié)構(gòu)··················································································6
任務(wù)二 算法······························································································7
任務(wù)引入······························································································7
任務(wù)分析······························································································7
知識準備······························································································7
一、算法簡介························································································7
二、算法設(shè)計的要求···············································································8
三、算法效率的評價···············································································8
四、常用語句階的計算············································································9
任務(wù)三 C 語言基礎(chǔ)··················································································.10
任務(wù)引入···························································································.10
任務(wù)分析···························································································.10
知識準備···························································································.10
一、C 語言簡介··················································································.10
二、C 語言特點··················································································.11
三、C 語言基本結(jié)構(gòu)············································································.13
四、C 語言關(guān)鍵字···············································································.14
五、C 語言語法結(jié)構(gòu)············································································.15
六、C 語言程序··················································································.17
項目二 線性表······························································································.23
任務(wù)一 線性表概述··················································································.23
任務(wù)引入···························································································.23
任務(wù)分析···························································································.23
知識準備···························································································.23
一、定義···························································································.24
二、抽象數(shù)據(jù)類型線性表······································································.24
任務(wù)二 線性表的順序存儲結(jié)構(gòu)···································································.26
任務(wù)引入···························································································.26
任務(wù)分析···························································································.26
知識準備···························································································.26
一、順序存儲結(jié)構(gòu)···············································································.26
二、基本操作的實現(xiàn)············································································.27
任務(wù)三 線性表的鏈式存儲結(jié)構(gòu)···································································.29
任務(wù)引入···························································································.29
任務(wù)分析···························································································.29
知識準備···························································································.30
一、單鏈表························································································.30
二、基本操作的實現(xiàn)············································································.31
三、循環(huán)鏈表·····················································································.34
四、雙向鏈表·····················································································.35
案例——一元多項式的表示及相加··························································.37
項目三 棧和隊列···························································································.39
任務(wù)一 �！ぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁ�.39
任務(wù)引入···························································································.39
任務(wù)分析···························································································.39
知識準備···························································································.39
一、棧的定義及其運算·········································································.39
二、棧的順序存儲結(jié)構(gòu)·········································································.40
三、棧的鏈式存儲結(jié)構(gòu)·········································································.42
四、棧的應(yīng)用·····················································································.44
任務(wù)二 隊列···························································································.46
任務(wù)引入···························································································.46
任務(wù)分析···························································································.46
知識準備···························································································.46
一、抽象數(shù)據(jù)類型隊列的定義································································.46
二、鏈隊列——隊列的順序表示和實現(xiàn)····················································.48
三、循環(huán)隊列——隊列的循環(huán)表示和實現(xiàn)·················································.50
項目四 串····································································································.53
任務(wù)一 串及其基本運算············································································.53
任務(wù)引入···························································································.53
任務(wù)分析···························································································.53
知識準備···························································································.53
一、串的基本概念···············································································.54
二、串的基本運算···············································································.54
任務(wù)二 串的存儲結(jié)構(gòu)及基本運算································································.55
任務(wù)引入···························································································.55
任務(wù)分析···························································································.55
知識準備···························································································.55
一、串的定長順序存儲·········································································.55
二、定長順序串的基本運算···································································.56
三、串的鏈式存儲結(jié)構(gòu)·········································································.58
任務(wù)三 串的堆存儲結(jié)構(gòu)············································································.59
任務(wù)引入···························································································.59
任務(wù)分析···························································································.59
知識準備···························································································.59
一、串名的存儲映像············································································.59
二、堆存儲結(jié)構(gòu)··················································································.61
三、基于堆結(jié)構(gòu)的基本運算···································································.61
四、串的應(yīng)用舉例：文本編輯································································.61
項目五 數(shù)組和廣義表·····················································································.64
任務(wù)一 數(shù)組···························································································.64
任務(wù)引入···························································································.64
任務(wù)分析···························································································.64
知識準備···························································································.64
一、數(shù)組概念及其存儲結(jié)構(gòu)···································································.65
二、特殊矩陣的壓縮存儲······································································.66
三、稀疏矩陣·····················································································.67
任務(wù)二 廣義表························································································.71
任務(wù)引入···························································································.71
任務(wù)分析···························································································.71
知識準備···························································································.71
一、廣義表的定義···············································································.71
二、廣義表的存儲結(jié)構(gòu)·········································································.72
項目六 樹與二叉樹························································································.75
任務(wù)一 樹······························································································.75
任務(wù)引入···························································································.75
任務(wù)分析···························································································.76
知識準備···························································································.76
一、樹的定義·····················································································.76
二、樹的基本術(shù)語···············································································.76
任務(wù)二 二叉樹························································································.77
任務(wù)引入···························································································.77
任務(wù)分析···························································································.77
知識準備···························································································.77
一、二叉樹的定義···············································································.77
二、二叉樹的基本特點·········································································.78
三、二叉樹的基本操作·········································································.78
四、特殊形態(tài)的二叉樹·········································································.78
五、二叉樹的性質(zhì)···············································································.80
六、二叉樹的存儲結(jié)構(gòu)·········································································.81
任務(wù)三 遍歷二叉樹··················································································.82
任務(wù)引入···························································································.82
任務(wù)分析···························································································.82
知識準備···························································································.83
一、相關(guān)概念·····················································································.83
二、遍歷二叉樹的操作及算法································································.83
案例——二叉樹的遍歷·········································································.85
三、根據(jù)遍歷序列推導(dǎo)二叉樹································································.86
案例——根據(jù)二叉樹的遍歷序列推導(dǎo)二叉樹··············································.86
任務(wù)四 線索二叉樹··················································································.87
任務(wù)引入···························································································.87
任務(wù)分析···························································································.87
知識準備···························································································.87
任務(wù)五 樹、森林與二叉樹的轉(zhuǎn)換································································.90
任務(wù)引入···························································································.90
任務(wù)分析···························································································.90
知識準備···························································································.90
一、樹的存儲結(jié)構(gòu)···············································································.90
二、樹、森林與二叉樹的轉(zhuǎn)換方法··························································.92
三、樹與森林的遍歷············································································.95
任務(wù)六 哈夫曼樹及其應(yīng)用·········································································.95
任務(wù)引入···························································································.95
任務(wù)分析···························································································.96
知識準備···························································································.96
一、基本概念·····················································································.96
二、哈夫曼樹的構(gòu)造過程······································································.96
三、哈夫曼編碼的構(gòu)造·········································································.97
案例——構(gòu)造哈夫曼編碼······································································.98
四、哈夫曼編碼的幾點結(jié)論···································································.99
項目七 圖····································································································101
任務(wù)一 圖的定義和基本術(shù)語······································································101
任務(wù)引入···························································································101
任務(wù)分析···························································································102
知識準備···························································································102
一、圖的定義·····················································································102
二、圖的基本術(shù)語···············································································102
三、圖的抽象數(shù)據(jù)類型·········································································107
任務(wù)二 圖的存儲·····················································································107
任務(wù)引入···························································································107
任務(wù)分析···························································································107
知識準備···························································································108
一、圖的鄰接矩陣表示法······································································108
二、圖的鄰接表表示法·········································································111
三、鄰接多重表··················································································115
任務(wù)三 圖的遍歷·····················································································116
任務(wù)引入···························································································116
任務(wù)分析···························································································117
知識準備···························································································117
一、圖的遍歷·····················································································117
二、深度優(yōu)先遍歷···············································································117
三、廣度優(yōu)先遍歷···············································································119
四、圖的連通性問題············································································121
任務(wù)四 圖的應(yīng)用·····················································································121
任務(wù)引入···························································································121
任務(wù)分析···························································································121
知識準備···························································································122
一、最小生成樹··················································································122
二、最小生成樹性質(zhì)MST ·····································································122
三、普里姆算法··················································································122
四、克魯斯卡爾算法············································································125
任務(wù)五 最短路徑·····················································································126
任務(wù)引入···························································································126
任務(wù)分析···························································································126
知識準備···························································································126
一、迪杰斯特拉算法············································································126
二、迪杰斯特拉算法的思想···································································126
三、迪杰斯特拉算法的分析和實現(xiàn)··························································127
任務(wù)六 弗洛伊德算法···············································································128
任務(wù)引入···························································································128
任務(wù)分析···························································································128
知識準備···························································································129
一、弗洛伊德算法思想·········································································129
二、弗洛伊德算法過程·········································································129
三、弗洛伊德算法的分析和實現(xiàn)·····························································130
任務(wù)七 拓撲排序·····················································································131
任務(wù)引入···························································································131
任務(wù)分析···························································································131
知識準備···························································································131
一、AOV 網(wǎng)·······················································································131
二、拓撲排序·····················································································132
任務(wù)八 關(guān)鍵路徑·····················································································134
任務(wù)引入···························································································134
任務(wù)分析···························································································134
知識準備···························································································134
一、相關(guān)概念·····················································································134
二、求關(guān)鍵路徑算法思想······································································135
項目八 查找·································································································137
任務(wù)一 查找的相關(guān)概念············································································137
任務(wù)引入···························································································137
任務(wù)分析···························································································137
知識準備···························································································138
一、查找的相關(guān)概念············································································138
二、查找的性能指標············································································138
任務(wù)二 靜態(tài)查找表··················································································138
任務(wù)引入···························································································138
任務(wù)分析···························································································138
知識準備···························································································139
任務(wù)三 折半查找·····················································································140
任務(wù)引入···························································································140
任務(wù)分析···························································································140
知識準備···························································································141
案例——折半查找···············································································141
任務(wù)四 分塊查找·····················································································143
任務(wù)引入···························································································143
任務(wù)分析···························································································143
知識準備···························································································143
任務(wù)五 樹表查找·····················································································144
任務(wù)引入···························································································144
任務(wù)分析···························································································144
知識準備···························································································144
一、二叉排序樹的定義·········································································144
二、二叉排序樹的結(jié)構(gòu)定義···································································145
三、二叉排序樹的查找·········································································145
四、二叉排序樹的插入與創(chuàng)建································································146
五、二叉排序樹的創(chuàng)建·········································································147
實例——創(chuàng)建二叉排序樹······································································147
任務(wù)六 平衡二叉樹··················································································151
任務(wù)引入···························································································151
任務(wù)分析···························································································151
知識準備···························································································152
一、相關(guān)概念·····················································································152
二、平衡二叉樹的平衡調(diào)整方法·····························································153
任務(wù)七 散列表查找··················································································156
任務(wù)引入···························································································156
任務(wù)分析···························································································157
知識準備···························································································157
一、常用術(shù)語·····················································································157
二、散列函數(shù)的構(gòu)造方法······································································158
三、處理沖突的方法············································································160
案例——線性探測再散列······································································161
案例——二次探測法············································································162
案例——鏈地址法解決沖突···································································162
四、散列表的查找···············································································163
案例——散列表的查找·········································································163
項目九 排序·································································································166
任務(wù)一 概述···························································································166
任務(wù)引入···························································································166
任務(wù)分析···························································································166
知識準備···························································································167
一、排序相關(guān)概念···············································································167
二、內(nèi)部排序的算法效率衡量································································167
三、內(nèi)部排序算法的分類······································································167
四、數(shù)據(jù)類型定義···············································································168
任務(wù)二 插入排序·····················································································168
任務(wù)引入···························································································168
任務(wù)分析···························································································168
知識準備···························································································168
一、插入排序的基本思想······································································168
二、直接插入排序···············································································169
三、折半插入排序···············································································170
四、希爾排序·····················································································172
案例——希爾排序···············································································174
任務(wù)三 交換排序·····················································································175
任務(wù)引入···························································································175
任務(wù)分析···························································································175
知識準備···························································································175
一、交換排序的基本思想······································································175
二、冒泡排序·····················································································175
任務(wù)四 快速排序·····················································································177
任務(wù)引入···························································································177
任務(wù)分析···························································································177
知識準備···························································································177
案例——快速排序···············································································179
任務(wù)五 選擇排序·····················································································180
任務(wù)引入···························································································180
任務(wù)分析···························································································180
知識準備···························································································180
一、選擇排序的算法思想······································································180
二、簡單選擇排序···············································································181
三、堆排序························································································182
任務(wù)六 歸并排序·····················································································189
任務(wù)引入···························································································189
任務(wù)分析···························································································189
知識準備···························································································189