數(shù)據(jù)結構與算法教程

第1章　緒論　
1.1　預備知識　
1.1.1　集合的笛卡兒積　
1.1.2　二元關系　
1.1.3　二元關系的基本性質和幾種重要關系　
1.2　什么是數(shù)據(jù)結構　
1.2.1　從實際問題理解數(shù)據(jù)結構　
1.2.2　數(shù)據(jù)結構所討論的內(nèi)容　
1.2.3　如何表示數(shù)據(jù)結構　
1.3　抽象數(shù)據(jù)類型　
1.3.1　什么是抽象數(shù)據(jù)類型　
1.3.2　抽象數(shù)據(jù)類型的定義與實現(xiàn)　
1.4　算法與算法分析　
1.4.1　什么是算法　
1.4.2　算法描述　
1.4.3　常用的算法設計方法　
1.4.4　算法分析　
習題　
上機練習題　
第2章　線性表的順序存儲及其運算　
2.1　線性表的概念　
2.1.1　 什么是線性表　
2.1.2　線性表的抽象數(shù)據(jù)類型　
2.2　順序表及其運算實現(xiàn)　
2.2.1　線性表的順序存儲——順序表　
2.2.2　順序表的基本運算　
2.2.3　順序表應用例——求子集　
2.3　?！?br /> 2.3.1　什么是棧　
2.3.2　棧的抽象數(shù)據(jù)類型　
2.3.3　順序棧及其運算　
2.4　棧應用　
2.4.1　棧在優(yōu)先級處理中的應用　
2.4.2　棧與分治法　
2.4.3　棧與回溯法　
2.4.4　棧與遞歸　
2.5　隊列　
2.5.1　隊列及其抽象數(shù)據(jù)類型　
2.5.2　順序隊列及其運算　
2.5.3　隊列應用例　
2.5.4　優(yōu)先隊列　
2.6　數(shù)組與特殊矩陣的表示　
2.6.1　數(shù)組的順序存儲　
2.6.2　規(guī)則矩陣的壓縮存儲　
2.6.3　稀疏矩陣的三列二維數(shù)組表示——三元組順序表　
習題　
上機練習題　
第3章　鏈表　
3.1　線性表的鏈式存儲——線性鏈表　
3.1.1　線性鏈表的結構特點　
3.1.2　線性鏈表的運算　
3.2　鏈式棧與鏈式隊列　
3.2.1　棧的鏈式存儲——鏈式?！?br /> 3.2.2　隊列的鏈式存儲——鏈式隊列　
3.3　循環(huán)鏈表　
3.3.1　循環(huán)鏈表的結構特點　
3.3.2　循環(huán)鏈表的基本運算　
3.3.3　鏈表應用例　
3.4　多重鏈表　
3.4.1　多重鏈表結構　
3.4.2　雙向鏈表　
3.5　廣義表　
3.5.1　什么是廣義表　
3.5.2　廣義表的存儲表示　
3.5.3　廣義表的基本運算　
習題　
上機練習題　
第4章　樹與二叉樹　
4.1　樹的基本概念　
4.1.1　 什么是樹　
4.1.2　樹的性質　
4.2　二叉樹　
4.2.1　什么是二叉樹　
4.2.2　二叉樹的基本性質　
4.2.3　二叉樹的抽象數(shù)據(jù)類型　
4.2.4　二叉樹的存儲結構　
4.2.5　二叉樹的遍歷及其他運算　
4.2.6　線索二叉樹　
4.3　二叉樹應用　
4.3.1　表達式線性化　
4.3.2　最優(yōu)二叉樹　
4.3.3　二叉搜索樹　
4.3.4　堆　
4.3.5　二叉樹與減治法　
4.4　樹的運算　
4.4.1　樹的抽象數(shù)據(jù)類型　
4.4.2　樹的存儲結構　
4.4.3　樹的遍歷　
4.4.4　樹的其他運算　
4.5　樹與回溯法　
4.5.1　問題解的描述——解空間樹　
4.5.2　回溯法的求解過程分析——遍歷解空間樹　
4.5.3　回溯法求解問題的形式化描述　
4.6　森林的遍歷　
4.6.1　森林與二叉樹的轉換　
4.6.2　森林的遍歷　
習題　
上機練習題　
第5章　圖　
5.1　圖的基本概念　
5.1.1　圖的定義和概念　
5.1.2　圖的抽象數(shù)據(jù)類型　
5.1.3　歐拉路徑　
5.2　圖的存儲結構　
5.2.1　圖的鄰接矩陣表示　
5.2.2　圖的鄰接表表示　
5.2.3　圖的其他表示方法　
5.3　圖的遍歷　
5.3.1　圖的深度優(yōu)先遍歷　
5.3.2　圖的廣度優(yōu)先遍歷　
5.3.3　圖遍歷的應用　
5.3.4　圖的連通性　
5.4　有向圖與有向無環(huán)圖　
5.4.1　有向圖的連通性和傳遞閉包　
5.4.2　有向無環(huán)圖和拓撲排序　
5.4.3　關鍵路徑　
5.5　最小生成樹　
5.5.1　圖的生成樹與最小生成樹　
5.5.2　普里姆(Prim)算法　
5.5.3　克魯斯卡爾(Kruskal)算法　
5.5.4　貪心算法　
5.6　最短路徑問題　
5.6.1　單源最短路徑　
5.6.2　全源最短路徑　
5.6.3　動態(tài)規(guī)劃算法　
5.7　圖應用例——城市間公路交通網(wǎng)問題　
5.7.1　問題描述　
5.7.2　問題求解思路　
習題　
上機練習題　
第6章　查找　
6.1　線性查找表　
6.1.1　順序查找　
6.1.2　折半查找　
6.1.3　斐波那契查找　
6.1.4　線性查找表的性能比較　
6.2　二叉搜索樹查找性能　
6.3　AVL樹　
6.3.1　BST的旋轉操作　
6.3.2　AVL樹的插入和平衡化旋轉　
6.3.3　AVL樹的刪除　
6.3.4　AVL樹的性能　
6.4　B-樹　
6.4.1　多路動態(tài)搜索樹　
6.4.2　B-樹的查找　
6.4.3　B-樹的插入　
6.4.4　B-樹的刪除　
6.5　散列方法　
6.5.1　散列技術　
6.5.2　散列函數(shù)　
6.5.3　沖突處理　
6.5.4　散列的刪除　
6.5.5　散列的性能　
6.6　靜態(tài)索引結構　
6.6.1　索引查找　
6.6.2　索引存儲方式　
6.6.3　索引文件結構　
6.7　模式匹配　
6.7.1　字符串及其ADT　
6.7.2　字符串的存儲表示　
6.7.3　字符串的模式匹配及簡單匹配算法　
6.7.4　字符串匹配的KMP算法　
習題　
上機練習題　
第7章　排序　
7.1　排序的概念及算法性能分析　
7.2　基本排序方法　
7.2.1　冒泡排序　
7.2.2　插入排序　
7.2.3　直接選擇排序　
7.2.4　基本排序方法的比較　
7.3　快速排序　
7.3.1　快速排序的過程　
7.3.2　快速排序的性能分析　
7.4　歸并排序　
7.4.1　二路歸并　
7.4.2　自底向上的歸并排序　
7.4.3　自頂向下的歸并排序　
7.5　錦標賽排序　
7.6　堆排序　
7.6.1　堆排序的思想　
7.6.2　堆排序的實現(xiàn)　
7.7　內(nèi)排序方法分析　
7.7.1　排序方法的下界　
7.7.2　內(nèi)排序方法的比較　
7.8　線性時間復雜度的排序算法　
7.8.1　計數(shù)排序　
7.8.2　基數(shù)排序　
7.9　外部排序　
7.9.1　外部排序方法　
7.9.2　基于敗者樹的k路歸并方法　
7.9.3　排序——歸并的改進　
習題　
上機練習題　
實驗指導　
實驗一　順序表及其應用　
實驗二　求解迷宮問題　
實驗三　簡單算術表達式的處理　
實驗四　求解簡單背包問題　
實驗五　鏈表及其應用　
實驗六　實驗室機時機位的管理　
實驗七　實現(xiàn)Huffman編碼　
實驗八　文件管理的模擬　
實驗九　求網(wǎng)絡站點間的最短連接　
實驗十　查找最高分與次高分　
實驗十一　比賽日程安排與成績統(tǒng)計