數(shù)據(jù)結(jié)構(gòu)

第1章 緒論 1
1.1 什么是數(shù)據(jù)結(jié)構(gòu) 1
1.2 數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu) 2
1.3 算法描述 4
1.3.1 數(shù)據(jù)結(jié)構(gòu)上的基本操作 4
1.3.2 算法的描述方法 5
1.4 算法分析 7
1.4.1 算法設(shè)計(jì)的要求 8
1.4.2 算法設(shè)計(jì)的時(shí)間因素 8
1.5 小結(jié) 9
習(xí)題1 10
第2章 線性表 11
2.1 線性表的邏輯結(jié)構(gòu) 11
2.1.1 線性表的定義 11
2.1.2 線性表的邏輯結(jié)構(gòu)表示 12
2.1.3 線性表的基本操作 13
2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)表示 13
2.3 線性表元素的操作 15
2.3.1 線性表元素插入操作 15
2.3.2 線性表元素刪除操作 17
2.3.3 線性表元素定位操作 17
2.4 線性表應(yīng)用舉例 20
2.5 小結(jié) 28
習(xí)題2 28
第3章 鏈表 30
3.1 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示 30
3.2 單鏈表的基本操作 33
3.2.1 單鏈表的建立 33
3.2.2 單鏈表元素定位操作 34
3.2.3 單鏈表元素插入操作 37
3.2.4 單鏈表元素刪除操作 42
3.3 單鏈表應(yīng)用舉例 44
3.4 循環(huán)鏈表 48
3.5 雙向鏈表 51
3.6 各種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的比較 52
3.7 順序表與鏈表的結(jié)構(gòu)和應(yīng)用比較 52
3.8 鏈表應(yīng)用舉例 53
3.9 小結(jié) 58
習(xí)題3 59
第4章 棧和隊(duì)列 60
4.1 棧的結(jié)構(gòu)及其運(yùn)算 60
4.2 隊(duì)列的結(jié)構(gòu)及其運(yùn)算 63
4.3 鏈棧和鏈隊(duì) 69
4.3.1 鏈棧的存儲(chǔ)結(jié)構(gòu)及其運(yùn)算 70
4.3.2 鏈隊(duì)的存儲(chǔ)結(jié)構(gòu)及其運(yùn)算 71
4.4 棧的應(yīng)用舉例 73
4.5 小結(jié) 75
習(xí)題4 75
第5章 數(shù)組 77
5.1 二維數(shù)組的順序存儲(chǔ)表示 77
5.2 稀疏矩陣的壓縮 80
5.3 特殊矩陣的壓縮 83
5.4 小結(jié) 85
習(xí)題5 85
第6章 串 87
6.1 串的定義和特性 87
6.2 串的存儲(chǔ)結(jié)構(gòu) 88
6.2.1 串的靜態(tài)存儲(chǔ)結(jié)構(gòu) 88
6.2.2 串的動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu) 90
6.3 串的運(yùn)算 91
6.3.1 串的基本運(yùn)算 91
6.3.2 串運(yùn)算的應(yīng)用 93
6.4 串在文本編輯中的應(yīng)用 97
6.5 小結(jié) 99
習(xí)題6 100
第7章 樹 101
7.1 樹的基本概念 101
7.2 樹的存儲(chǔ)結(jié)構(gòu) 103
7.3 二叉樹 105
7.3.1 二叉樹的表示 105
7.3.2 二叉樹的特性 106
7.3.3 二叉樹的存儲(chǔ)結(jié)構(gòu) 108
7.4 遍歷二叉樹 109
7.4.1 遍歷二叉樹的遞歸算法 109
7.4.2 中根遍歷的非遞歸算法 113
7.5 樹和森林 116
7.5.1 森林與二叉樹的轉(zhuǎn)換 116
7.5.2 樹的遍歷 118
7.6 哈夫曼樹及其應(yīng)用 119
7.6.1 哈夫曼樹的表示 119
7.6.2 哈夫曼樹的構(gòu)造 121
7.6.3 哈夫曼樹的應(yīng)用 121
7.7 二叉樹的應(yīng)用舉例 123
7.8 小結(jié) 126
習(xí)題7 126
第8章 圖 128
8.1 圖的基本概念 128
8.2 圖的存儲(chǔ)結(jié)構(gòu) 132
8.2.1 圖的鄰接矩陣表示 132
8.2.2 圖的鏈接表表示 134
8.3 圖的遍歷 137
8.3.1 深度優(yōu)先搜索法 138
8.3.2 廣度優(yōu)先搜索法 139
8.4 最短路徑 141
8.5 生成樹 143
8.6 拓?fù)渑判?146
8.7 小結(jié) 151
習(xí)題8 151
第9章 查找 153
9.1 查找的基本概念 153
9.2 靜態(tài)查找 154
9.2.1 順序查找 154
9.2.2 折半查找 156
9.2.3 分塊查找 158
9.3 動(dòng)態(tài)查找 160
9.3.1 二叉查找樹查找 160
9.3.2 二叉查找樹插入結(jié)點(diǎn)的算法 161
9.4 哈希查找 164
9.4.1 哈希表和哈希函數(shù) 164
9.4.2 沖突和解決沖突的方法 169
9.5 各種查找方法的比較 175
9.6 查找應(yīng)用舉例 176
9.7 小結(jié) 178
習(xí)題9 178
第10章 排序 180
10.1 排序的基本概念 180
10.2 排序方法 181
10.2.1 直接插入排序 181
10.2.2 簡單選擇排序 183
10.2.3 快速排序 185
10.2.4 堆排序 191
10.2.5 歸并排序 197
10.3 各種排序方法的比較 200
10.4 排序應(yīng)用舉例 204
10.5 小結(jié) 206
習(xí)題10 206
附錄1 上機(jī)實(shí)驗(yàn) 208
實(shí)驗(yàn)一 順序表中元素的插入和刪除 208
實(shí)驗(yàn)二 單鏈表中元素的查找. 插入和刪除 208
實(shí)驗(yàn)三 棧和隊(duì)列中元素的交換 208
實(shí)驗(yàn)四 二叉樹的建立和中根遍歷的應(yīng)用 208
實(shí)驗(yàn)五 圖遍歷的應(yīng)用 209
實(shí)驗(yàn)六 折半查找的應(yīng)用 209
實(shí)驗(yàn)七 哈希查找中的鏈地址法 209
實(shí)驗(yàn)八 直接插入排序和快速排序在實(shí)際中的應(yīng)用 209
實(shí)驗(yàn)九 查找和排序技術(shù)的綜合應(yīng)用 209
附錄2 課程設(shè)計(jì) 210
參考文獻(xiàn) 211