第1章 緒論 1
1.1 數(shù)據(jù)結(jié)構(gòu)概述 1
1.1.1 基本概念 1
1.1.2 數(shù)據(jù)結(jié)構(gòu)的定義 2
1.2 算法及其描述 8
1.2.1 算法的概念 8
1.2.2 算法描述 9
1.3 算法分析 11
1.3.1 時(shí)間復(fù)雜度 12
1.3.2 空間復(fù)雜度 14
小結(jié) 14
知識(shí)鞏固 14
實(shí)訓(xùn)演練 15
第2章 線性表 16
2.1 線性表的定義及基本運(yùn)算 16
2.1.1 線性表的定義 16
2.1.2 線性表的基本運(yùn)算 17
2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn) 18
2.2.1 線性表的順序存儲(chǔ)結(jié)構(gòu) 18
2.2.2 順序表基本運(yùn)算的實(shí)現(xiàn) 19
2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn) 23
2.3.1 單鏈表 24
2.3.2 雙向鏈表 29
2.3.3 循環(huán)單鏈表 32
2.3.4 循環(huán)雙向鏈表 33
2.3.5 順序表與鏈表的比較 35
2.4 經(jīng)典應(yīng)用實(shí)例 36
2.4.1 約瑟夫問題 36
2.4.2 多項(xiàng)式求和 41
小結(jié) 46
知識(shí)鞏固 46
實(shí)訓(xùn)演練 48
第3章 棧和隊(duì)列 50
3.1 棧的定義及基本運(yùn)算 50
3.1.1 棧的定義 50
3.1.2 棧的基本運(yùn)算 51
3.2 棧的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn) 51
3.2.1 棧的順序存儲(chǔ)結(jié)構(gòu) 52
3.2.2 棧的基本運(yùn)算在順序棧上的實(shí)現(xiàn) 52
3.2.3 棧在遞歸中的應(yīng)用 54
3.3 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn) 56
3.3.1 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 56
3.3.2 棧的基本運(yùn)算在鏈棧上的實(shí)現(xiàn) 56
3.4 棧的經(jīng)典應(yīng)用實(shí)例 57
3.4.1 數(shù)制轉(zhuǎn)換 57
3.4.2 表達(dá)式求值 59
3.5 隊(duì)列的定義及基本運(yùn)算 66
3.5.1 隊(duì)列的定義 66
3.5.2 隊(duì)列的基本運(yùn)算 67
3.6 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn) 67
3.6.1 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu) 67
3.6.2 順序隊(duì)列基本運(yùn)算的實(shí)現(xiàn) 68
3.6.3 循環(huán)隊(duì)列 69
3.7 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn) 71
3.7.1 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 71
3.7.2 鏈?zhǔn)疥?duì)列基本運(yùn)算的實(shí)現(xiàn) 71
3.8 隊(duì)列的經(jīng)典應(yīng)用實(shí)例 73
3.8.1 迷宮問題 73
3.8.2 模擬就診過程 78
小結(jié) 81
知識(shí)鞏固 81
實(shí)訓(xùn)演練 84
第4章 串 86
4.1 串的概念與操作 86
4.1.1 串的概念 86
4.1.2 串的操作 87
4.2 串的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn) 88
4.2.1 串的順序存儲(chǔ)結(jié)構(gòu) 88
4.2.2 順序串基本運(yùn)算的實(shí)現(xiàn) 88
4.2.3 常用的字符串處理函數(shù) 90
4.3 串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn) 92
4.3.1 串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 92
4.3.2 鏈串基本運(yùn)算的實(shí)現(xiàn) 93
4.4 經(jīng)典應(yīng)用實(shí)例 96
4.4.1 測(cè)試串的基本操作 96
4.4.2 模式匹配 102
小結(jié) 105
知識(shí)鞏固 105
實(shí)訓(xùn)演練 107
第5章 數(shù)組和廣義表 109
5.1 數(shù)組 109
5.1.1 數(shù)組的基本概念 109
5.1.2 數(shù)組的存儲(chǔ)結(jié)構(gòu) 110
5.2 特殊矩陣的壓縮存儲(chǔ) 112
5.2.1 三角矩陣 112
5.2.2 對(duì)稱矩陣 113
5.2.3 帶狀矩陣 114
5.2.4 稀疏矩陣 114
5.3 廣義表 117
5.3.1 廣義表的概念 117
5.3.2 廣義表的存儲(chǔ)結(jié)構(gòu) 118
5.3.3 廣義表的運(yùn)算 119
5.4 經(jīng)典應(yīng)用實(shí)例 119
5.4.1 矩陣鞍點(diǎn) 120
5.4.2 稀疏矩陣相加 122
小結(jié) 126
知識(shí)鞏固 126
實(shí)訓(xùn)演練 127
第6章 遞歸 128
6.1 遞歸 128
6.1.1 遞歸的定義 128
6.1.2 遞歸的使用 129
6.2 遞歸算法的設(shè)計(jì) 130
6.2.1 遞歸模型的建立 130
6.2.2 遞歸算法的設(shè)計(jì) 131
6.2.3 遞歸算法的性能分析 132
6.3 遞歸和棧 132
6.3.1 遞歸調(diào)用與棧 132
6.3.2 遞歸到非遞歸的轉(zhuǎn)換 133
6.4 經(jīng)典應(yīng)用實(shí)例 134