目錄
第1章 緒論 1
1.1 計算機(jī)和計算機(jī)軟件 1
1.1.1 計算機(jī)系統(tǒng)的組成 1
1.1.2 計算機(jī)語言與程序 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
習(xí)題1 12
第2章 線性表 15
2.1 線性表及其邏輯結(jié)構(gòu) 15
2.1.1 線性表的定義 15
2.1.2 線性表的基本操作 16
2.2 線性表的順序存儲結(jié)構(gòu)及運(yùn)算實(shí)現(xiàn) 16
2.2.1 順序表 16
2.2.2 順序表基本運(yùn)算的實(shí)現(xiàn) 18
2.3 線性表的鏈?zhǔn)酱鎯�結(jié)構(gòu)及運(yùn)算實(shí)現(xiàn) 23
2.3.1 單鏈表 23
2.3.2 單鏈表基本運(yùn)算的實(shí)現(xiàn) 25
2.3.3 循環(huán)鏈表 30
2.3.4 雙向鏈表 32
2.3.5 單鏈表應(yīng)用示例 34
習(xí)題2 36
第3章 特殊線性表 40
3.1 棧 40
3.1.1 棧的定義及基本運(yùn)算 40
3.1.2 棧的存儲結(jié)構(gòu)及運(yùn)算實(shí)現(xiàn) 41

3.2 隊(duì)列 46
3.2.1 隊(duì)列的定義及基本運(yùn)算 46
3.2.2 隊(duì)列的存儲結(jié)構(gòu)及運(yùn)算實(shí)現(xiàn) 46
3.3 字符串 52
3.3.1 字符串的基本概念 52
3.3.2 字符串的順序存儲結(jié)構(gòu)及基本運(yùn)算 54
3.3.3 字符串的鏈?zhǔn)酱鎯�結(jié)構(gòu)及基本運(yùn)算 57
3.3.4 簡單模式匹配 60
3.4 數(shù)組 62
3.4.1 數(shù)組的基本概念及存儲結(jié)構(gòu) 62
3.4.2 稀疏矩陣的三元組表示及矩陣轉(zhuǎn)置 65
習(xí)題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 哈夫曼算法的實(shí)現(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
習(xí)題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
習(xí)題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)的進(jìn)一步發(fā)展時期 184
6.3 進(jìn)程 185
6.3.1 程序的順序執(zhí)行 185
6.3.2 程序的并發(fā)執(zhí)行 186
6.3.3 進(jìn)程的概念及狀態(tài)轉(zhuǎn)換 188
6.3.4 兩狀態(tài)進(jìn)程模型 191
6.3.5 進(jìn)程的三態(tài)模型 191
6.3.6 PCB 193
6.4 進(jìn)程的互斥與同步 195
6.4.1 并發(fā)進(jìn)程的關(guān)系 195
6.4.2 進(jìn)程的互斥與同步 196
6.4.3 臨界資源與臨界區(qū) 197
6.4.4 信號量 198
6.4.5 使用信號量實(shí)現(xiàn)進(jìn)程互斥 200
6.4.6 使用信號量實(shí)現(xiàn)進(jìn)程同步 201
6.4.7 生產(chǎn)者-消費(fèi)者問題 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
習(xí)題6 237
參考文獻(xiàn) 245