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

第1章  概論
1.1  概述
1.2  數(shù)據(jù)結(jié)構(gòu)的基本概念
1.2.1  數(shù)據(jù)結(jié)構(gòu)的基本術(shù)語(yǔ)
1.2.2  數(shù)據(jù)的邏輯結(jié)構(gòu)
1.2.3  數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)
1.3  算法性能分析與度量
1.3.1  算法和算法的描述方法
1.3.2  算法的特性
1.3.3  算法設(shè)計(jì)的要求
1.3.4  算法時(shí)間復(fù)雜度的度量
1.3.5  算法存儲(chǔ)空間的需求
本章小結(jié)
習(xí)題1
第2章  線性表
2.1  線性表的定義及基本運(yùn)算
2.1.1  線性表的定義
2.1.2  線性表的基本運(yùn)算
2.2  線性表的順序存儲(chǔ)結(jié)構(gòu)及其運(yùn)算
2.2.1  線性表的順序存儲(chǔ)結(jié)構(gòu)
2.2.2  順序表的基本運(yùn)算
2.2.3  順序表上插入和刪除運(yùn)算的時(shí)間分析
2.2.4  順序表的優(yōu)點(diǎn)和缺點(diǎn)
2.3  線性表的鏈接存儲(chǔ)結(jié)構(gòu)及其運(yùn)算
2.3.1  單鏈表
2.3.2  單鏈表上的基本運(yùn)算
2.3.3  單鏈表上查找、插入和刪除運(yùn)算的時(shí)間分析
2.3.4  循環(huán)鏈表
2.3.5  雙向鏈表
2.4  順序表和鏈表的比較
2.5  線性表的簡(jiǎn)單應(yīng)用舉例
本章小結(jié)
習(xí)題2
第3章  棧和隊(duì)列
3.1  棧的基本概念
3.2  棧的存儲(chǔ)結(jié)構(gòu)
3.2.1  棧的順序存儲(chǔ)結(jié)構(gòu)
3.2.2  棧的鏈接存儲(chǔ)結(jié)構(gòu)
3.2.3  棧的兩種存儲(chǔ)結(jié)構(gòu)的比較
3.2.4  多個(gè)順序棧共享一個(gè)數(shù)組的存儲(chǔ)空間
3.3  棧的基本運(yùn)算
3.3.1  順序存儲(chǔ)結(jié)構(gòu)上順序棧的運(yùn)算實(shí)現(xiàn)
3.3.2  鏈接存儲(chǔ)結(jié)構(gòu)上鏈棧的運(yùn)算實(shí)現(xiàn)
3.4  棧的簡(jiǎn)單應(yīng)用舉例
3.4.1  棧在遞歸過(guò)程中的作用
3.4.2  簡(jiǎn)單應(yīng)用舉例
3.5  隊(duì)列的基本概念
3.6  隊(duì)列的存儲(chǔ)結(jié)構(gòu)
3.6.1  隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)
3.6.2  順序存儲(chǔ)的循環(huán)隊(duì)列
3.6.3  隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)
3.7  隊(duì)列的基本運(yùn)算
3.7.1  順序存儲(chǔ)結(jié)構(gòu)上順序隊(duì)列的運(yùn)算實(shí)現(xiàn)
3.7.2  順序存儲(chǔ)結(jié)構(gòu)上循環(huán)隊(duì)列的運(yùn)算實(shí)現(xiàn)
3.7.3  鏈接存儲(chǔ)結(jié)構(gòu)上鏈隊(duì)列的運(yùn)算實(shí)現(xiàn)
3.8  隊(duì)列的簡(jiǎn)單應(yīng)用舉例
本章小結(jié)
習(xí)題3
第4章  串
4.1  串的基本概念
4.2  串的存儲(chǔ)結(jié)構(gòu)
4.2.1  串的順序存儲(chǔ)結(jié)構(gòu)
4.2.2  串的鏈接存儲(chǔ)結(jié)構(gòu)
4.3  串的基本運(yùn)算及實(shí)現(xiàn)
4.3.1  串的基本運(yùn)算
4.3.2  順序串上基本運(yùn)算的實(shí)現(xiàn)
4.3.3  鏈串上基本運(yùn)算的實(shí)現(xiàn)
4.4  串的模式匹配運(yùn)算
4.4.1  BF模式匹配算法
4.4.2  BM模式匹配算法
4.4.3  KMP模式匹配算法
4.5  串的簡(jiǎn)單應(yīng)用舉例
本章小結(jié)
習(xí)題4
第5章  數(shù)組和廣義表
5.1  數(shù)組的概念和存儲(chǔ)
5.1.1  數(shù)組的概念
5.1.2  數(shù)組的存儲(chǔ)結(jié)構(gòu)
5.2  特殊矩陣的壓縮存儲(chǔ)
5.2.1  對(duì)稱矩陣的壓縮存儲(chǔ)
5.2.2  三角矩陣的壓縮存儲(chǔ)
5.2.3  對(duì)角矩陣的壓縮存儲(chǔ)
5.3  稀疏矩陣的壓縮存儲(chǔ)
5.3.1  稀疏矩陣的三元組表示
5.3.2  稀疏矩陣的十字鏈表表示
5.3.3  稀疏矩陣的簡(jiǎn)單應(yīng)用舉例
5.4  廣義表
5.4.1  廣義表的基本概念
5.4.2  廣義表的鏈接存儲(chǔ)結(jié)構(gòu)
5.4.3  廣義表的基本運(yùn)算
5.4.4  廣義表的簡(jiǎn)單應(yīng)用舉例
本章小結(jié)
習(xí)題5
第6章  樹
6.1  樹的基本概念
6.1.1  樹的定義
6.1.2  樹的基本術(shù)語(yǔ)
6.2  二叉樹
6.2.1  二叉樹的概念
6.2.2  二叉樹的基本性質(zhì)
6.2.3  二叉樹的存儲(chǔ)結(jié)構(gòu)
6.3  二叉樹的運(yùn)算
6.3.1  二叉樹的遍歷
6.3.2  二叉樹的建立
6.3.3  二叉樹的其他運(yùn)算舉例
6.4  線索化二叉樹
6.4.1  線索二叉樹的概念
6.4.2  二叉樹的中序線索化
6.4.3  線索二叉樹的遍歷和插入運(yùn)算
6.5  樹和森林
6.5.1  樹的存儲(chǔ)結(jié)構(gòu)
6.5.2  樹和森林與二叉樹的轉(zhuǎn)換
6.5.3  樹的遍歷
6.5.4  森林的遍歷
6.6  哈夫曼樹及其應(yīng)用
6.6.1  哈夫曼樹的基本概念
6.6.2  哈夫曼樹的構(gòu)造及實(shí)現(xiàn)
6.6.3  哈夫曼編碼
6.6.4  哈夫曼譯碼
6.6.5  哈夫曼樹在編碼問(wèn)題中的完整程序
本章小結(jié)
習(xí)題6
第7章  圖
7.1  圖的基本概念
7.1.1  圖的實(shí)際背景
7.1.2  圖的定義
7.1.3  圖的基本術(shù)語(yǔ)
7.2  圖的存儲(chǔ)結(jié)構(gòu)
7.2.1  鄰接矩陣表示法
7.2.2  鄰接表表示法
7.3  圖的遍歷
7.3.1  連通圖的深度優(yōu)先搜索遍歷
7.3.2  連通圖的廣度優(yōu)先搜索遍歷
7.3.3  非連通圖的遍歷
7.4  生成樹和最小生成樹
7.4.1  生成樹和最小生成樹的概念
7.4.2  Kruskal算法
7.4.3  Prim算法
7.5  最短路徑
7.5.1  最短路徑的概念
7.5.2  單源最短路徑
7.5.3  所有頂點(diǎn)對(duì)之間的最短路徑
7.6  AOV網(wǎng)和拓?fù)渑判?br />7.6.1  AOV網(wǎng)和拓?fù)渑判?br />7.6.2  拓?fù)渑判蛩惴?br />7.7  AOE網(wǎng)和關(guān)鍵路徑
7.7.1  AOE網(wǎng)和關(guān)鍵路徑的概念
7.7.2  關(guān)鍵路徑的確定
7.8  圖的簡(jiǎn)單應(yīng)用舉例
本章小結(jié)
習(xí)題7
第8章  排序
8.1  排序的基本概念
8.2  插入排序
8.2.1  直接插入排序
8.2.2  希爾排序
8.3  交換排序
8.3.1  冒泡排序
8.3.2  快速排序
8.4  選擇排序
8.4.1  直接選擇排序
8.4.2  堆排序
8.5  歸并排序
8.5.1  兩個(gè)相鄰有序表的一次歸并過(guò)程
8.5.2  一趟歸并排序過(guò)程
8.5.3  二路歸并排序
8.6  各種內(nèi)排序方法的比較和選擇
8.6.1  各種內(nèi)排序方法的總結(jié)
8.6.2  各種內(nèi)排序方法的比較
8.6.3  排序方法的選擇
8.7  排序的簡(jiǎn)單應(yīng)用舉例
本章小結(jié)
習(xí)題8
第9章  查找
9.1  查找的基本概念
9.2  線性表的查找
9.2.1  順序查找
9.2.2  二分查找
9.2.3  分塊查找
9.3  樹表的查找
9.3.1  二叉排序樹
9.3.2  平衡的二叉排序樹
9.3.3  B-樹
9.4  散列表的查找
9.4.1  散列表的概念
9.4.2  散列函數(shù)的構(gòu)造方法
9.4.3  處理沖突的方法
9.4.4  散列表的運(yùn)算
9.4.5  散列表的查找及分析
9.5  查找的簡(jiǎn)單應(yīng)用程序舉例
本章小結(jié)
習(xí)題9
第10章  文件
10.1  文件的基本概念
10.2  順序文件
10.3  索引文件
10.4  索引順序文件
10.4.1  ISAM文件
10.4.2  VSAM文件
10.5  散列文件
10.6  多關(guān)鍵字文件
10.6.1  多重表文件
10.6.2  倒排文件
本章小結(jié)
習(xí)題10378
參考文獻(xiàn)