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