第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 時間復雜度 12
1.3.2 空間復雜度 14
小結(jié) 14
知識鞏固 14
實訓演練 15
第2章 線性表 16
2.1 線性表的定義及基本運算 16
2.1.1 線性表的定義 16
2.1.2 線性表的基本運算 17
2.2 線性表的順序存儲結(jié)構(gòu)及其基本運算的實現(xiàn) 18
2.2.1 線性表的順序存儲結(jié)構(gòu) 18
2.2.2 順序表基本運算的實現(xiàn) 19
2.3 線性表的鏈式存儲結(jié)構(gòu)及其基本運算的實現(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)用實例 36
2.4.1 約瑟夫問題 36
2.4.2 多項式求和 41
小結(jié) 46
知識鞏固 46
實訓演練 48
第3章 棧和隊列 50
3.1 棧的定義及基本運算 50
3.1.1 棧的定義 50
3.1.2 棧的基本運算 51
3.2 棧的順序存儲結(jié)構(gòu)及其基本運算的實現(xiàn) 51
3.2.1 棧的順序存儲結(jié)構(gòu) 52
3.2.2 棧的基本運算在順序棧上的實現(xiàn) 52
3.2.3 棧在遞歸中的應(yīng)用 54
3.3 棧的鏈式存儲結(jié)構(gòu)及其基本運算的實現(xiàn) 56
3.3.1 棧的鏈式存儲結(jié)構(gòu) 56
3.3.2 棧的基本運算在鏈棧上的實現(xiàn) 56
3.4 棧的經(jīng)典應(yīng)用實例 57
3.4.1 數(shù)制轉(zhuǎn)換 57
3.4.2 表達式求值 59
3.5 隊列的定義及基本運算 66
3.5.1 隊列的定義 66
3.5.2 隊列的基本運算 67
3.6 隊列的順序存儲結(jié)構(gòu)及其基本運算的實現(xiàn) 67
3.6.1 隊列的順序存儲結(jié)構(gòu) 67
3.6.2 順序隊列基本運算的實現(xiàn) 68
3.6.3 循環(huán)隊列 69
3.7 隊列的鏈式存儲結(jié)構(gòu)及其基本運算的實現(xiàn) 71
3.7.1 隊列的鏈式存儲結(jié)構(gòu) 71
3.7.2 鏈式隊列基本運算的實現(xiàn) 71
3.8 隊列的經(jīng)典應(yīng)用實例 73
3.8.1 迷宮問題 73
3.8.2 模擬就診過程 78
小結(jié) 81
知識鞏固 81
實訓演練 84
第4章 串 86
4.1 串的概念與操作 86
4.1.1 串的概念 86
4.1.2 串的操作 87
4.2 串的順序存儲結(jié)構(gòu)及其基本運算的實現(xiàn) 88
4.2.1 串的順序存儲結(jié)構(gòu) 88
4.2.2 順序串基本運算的實現(xiàn) 88
4.2.3 常用的字符串處理函數(shù) 90
4.3 串的鏈式存儲結(jié)構(gòu)及其基本運算的實現(xiàn) 92
4.3.1 串的鏈式存儲結(jié)構(gòu) 92
4.3.2 鏈串基本運算的實現(xiàn) 93
4.4 經(jīng)典應(yīng)用實例 96
4.4.1 測試串的基本操作 96
4.4.2 模式匹配 102
小結(jié) 105
知識鞏固 105
實訓演練 107
第5章 數(shù)組和廣義表 109
5.1 數(shù)組 109
5.1.1 數(shù)組的基本概念 109
5.1.2 數(shù)組的存儲結(jié)構(gòu) 110
5.2 特殊矩陣的壓縮存儲 112
5.2.1 三角矩陣 112
5.2.2 對稱矩陣 113
5.2.3 帶狀矩陣 114
5.2.4 稀疏矩陣 114
5.3 廣義表 117
5.3.1 廣義表的概念 117
5.3.2 廣義表的存儲結(jié)構(gòu) 118
5.3.3 廣義表的運算 119
5.4 經(jīng)典應(yīng)用實例 119
5.4.1 矩陣鞍點 120
5.4.2 稀疏矩陣相加 122
小結(jié) 126
知識鞏固 126
實訓演練 127
第6章 遞歸 128
6.1 遞歸 128
6.1.1 遞歸的定義 128
6.1.2 遞歸的使用 129
6.2 遞歸算法的設(shè)計 130
6.2.1 遞歸模型的建立 130
6.2.2 遞歸算法的設(shè)計 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)用實例 134