目錄
第1章 緒論 1
1.1 計算機和計算機軟件 1
1.1.1 計算機系統(tǒng)的組成 1
1.1.2 計算機語言與程序 2
1.1.3 軟件的概念與軟件的發(fā)展 4
1.2 數(shù)據(jù)結(jié)構(gòu)概述 6
1.2.1 數(shù)據(jù)與數(shù)據(jù)元素 7
1.2.2 數(shù)據(jù)結(jié)構(gòu) 7
1.3 算法與算法分析 10
1.3.1 算法的定義與描述 10
1.3.2 算法分析與復(fù)雜度計算 11
習題1 12
第2章 線性表 15
2.1 線性表及其邏輯結(jié)構(gòu) 15
2.1.1 線性表的定義 15
2.1.2 線性表的基本操作 16
2.2 線性表的順序存儲結(jié)構(gòu)及運算實現(xiàn) 16
2.2.1 順序表 16
2.2.2 順序表基本運算的實現(xiàn) 18
2.3 線性表的鏈式存儲結(jié)構(gòu)及運算實現(xiàn) 23
2.3.1 單鏈表 23
2.3.2 單鏈表基本運算的實現(xiàn) 25
2.3.3 循環(huán)鏈表 30
2.3.4 雙向鏈表 32
2.3.5 單鏈表應(yīng)用示例 34
習題2 36
第3章 特殊線性表 40
3.1 棧 40
3.1.1 棧的定義及基本運算 40
3.1.2 棧的存儲結(jié)構(gòu)及運算實現(xiàn) 41

3.2 隊列 46
3.2.1 隊列的定義及基本運算 46
3.2.2 隊列的存儲結(jié)構(gòu)及運算實現(xiàn) 46
3.3 字符串 52
3.3.1 字符串的基本概念 52
3.3.2 字符串的順序存儲結(jié)構(gòu)及基本運算 54
3.3.3 字符串的鏈式存儲結(jié)構(gòu)及基本運算 57
3.3.4 簡單模式匹配 60
3.4 數(shù)組 62
3.4.1 數(shù)組的基本概念及存儲結(jié)構(gòu) 62
3.4.2 稀疏矩陣的三元組表示及矩陣轉(zhuǎn)置 65
習題3 69
第4章 非線性數(shù)據(jù)結(jié)構(gòu) 74
4.1 樹與二叉樹 74
4.1.1 樹的基本概念 74
4.1.2 二叉樹 76
4.2 二叉樹的遍歷 81
4.2.1 二叉樹的遍歷方法 81
4.2.2 遍歷二叉樹的遞歸算法及遍歷示例 82
4.2.3 遍歷二叉樹的非遞歸算法 85
4.2.4 二叉樹遍歷的應(yīng)用 87
4.3 哈夫曼樹 91
4.3.1 哈夫曼樹的基本概念及構(gòu)造方法 91
4.3.2 哈夫曼算法的實現(xiàn) 93
4.3.3 哈夫曼編碼 95
4.4 樹和森林 97
4.4.1 樹的定義與存儲結(jié)構(gòu) 97
4.4.2 樹、森林與二叉樹之間的轉(zhuǎn)換 98
4.4.3 樹與森林的遍歷 99
4.5 圖 100
4.5.1 圖的基本概念 100
4.5.2 圖的存儲結(jié)構(gòu) 103
4.6 圖的遍歷 108
4.6.1 深度優(yōu)先搜索 108
4.6.2 廣度優(yōu)先搜索 111
4.6.3 圖的連通性問題 113
4.6.4 生成樹 114
習題4 117
第5章 查找與排序 124
5.1 查找 124
5.2 靜態(tài)查找表 125
5.2.1 順序查找 125
5.2.2 有序表的查找 126
5.3 動態(tài)查找表 131
5.3.1 二叉排序樹 131
5.3.2 哈希表與哈希方法 138
5.3.3 哈希表的查找 144
5.4 排序 146
5.4.1 排序的基本概念 146
5.4.2 插入排序 147
5.4.3 交換排序 152
5.4.4 選擇排序 156
5.4.5 歸并排序 161
習題5 164
第6章 操作系統(tǒng) 172
6.1 操作系統(tǒng)概述 172
6.1.1 操作系統(tǒng)的定義 172
6.1.2 操作系統(tǒng)的主要功能 173
6.1.3 操作系統(tǒng)的基本特征 175
6.2 操作系統(tǒng)的形成與發(fā)展 177
6.2.1 操作系統(tǒng)的形成時期 177
6.2.2 操作系統(tǒng)的成熟時期 180
6.2.3 操作系統(tǒng)的進一步發(fā)展時期 184
6.3 進程 185
6.3.1 程序的順序執(zhí)行 185
6.3.2 程序的并發(fā)執(zhí)行 186
6.3.3 進程的概念及狀態(tài)轉(zhuǎn)換 188
6.3.4 兩狀態(tài)進程模型 191
6.3.5 進程的三態(tài)模型 191
6.3.6 PCB 193
6.4 進程的互斥與同步 195
6.4.1 并發(fā)進程的關(guān)系 195
6.4.2 進程的互斥與同步 196
6.4.3 臨界資源與臨界區(qū) 197
6.4.4 信號量 198
6.4.5 使用信號量實現(xiàn)進程互斥 200
6.4.6 使用信號量實現(xiàn)進程同步 201
6.4.7 生產(chǎn)者-消費者問題 204
6.5 存儲管理 207
6.5.1 地址重定位 207
6.5.2 早期的內(nèi)存管理方法 210
6.5.3 分頁存儲管理 215
6.5.4 分段存儲管理 219
6.5.5 段頁式存儲管理 222
6.5.6 虛擬存儲器管理 224
6.6 文件管理 228
6.6.1 文件 228
6.6.2 文件的邏輯結(jié)構(gòu) 229
6.6.3 文件的物理結(jié)構(gòu) 230
6.6.4 文件存儲空間管理 234
習題6 237
參考文獻 245