數(shù)據(jù)結構基礎與應用

第1章 緒論 1
1.1認識數(shù)據(jù)結構 1
1.1.1舉例認識數(shù)據(jù)結構 1
1.1.2數(shù)據(jù)結構定義 2
1.1.3數(shù)據(jù)結構的基本結構類型和表示 2
1.2數(shù)據(jù)結構類型 3
1.2.1線性結構 4
1.2.2非線性結構 4
1.3數(shù)據(jù)結構在程序設計中的地位 4
1.3.1算法的描述 4
1.3.2算法與程序設計 5
1.3.3算法的特性 6
1.4評價 6
1.4.1評價標準 6
1.4.2評價方法 6
1.5本章小結 7
1.6本章習題 7
第2章 數(shù)據(jù)結構分類 8
2.1幾種數(shù)據(jù)結構案例 8
2.2數(shù)據(jù)結構分類 10
2.2.1數(shù)據(jù)類型 10
2.2.2抽象數(shù)據(jù)類型 10
2.3數(shù)據(jù)的邏輯結構與存儲結構 11
2.3.1數(shù)據(jù)的邏輯結構 1l
2.3.2數(shù)據(jù)的存儲結構 11
2.4本章小結 11
2.5本章習題 11
第3章 線性表 12
3.1線性表基本概念和邏輯結構 12
3.1.1線性表實例 12
3.1.2線性表定義 13
3.1.3線性表邏輯結構 13
3.2線性表存儲方式及操作 13
3.2.1線性表的順序存儲 13
3.2.2線性表順序存儲的操作 14
3.2.3線性表順序存儲操作的評價 17
3.2.4線性表的鏈式存儲 18
3.2.5單鏈表的操作 20
3.3線性表操作在單鏈表上實現(xiàn)的程序設計 26
3.4循環(huán)鏈表介紹 33
3.5靜態(tài)鏈表介紹 35
3.6順序表和鏈表的比較 39
3.7本章小結 39
3.8本章習題 39
第4章 棧 41
4.1棧的基本概念 41
4.1.1棧的實例 41
4.1.2棧的定義 42
4.1.3棧的基本操作 43
4.2棧的實現(xiàn) 43
4.2.1棧實現(xiàn)分類 43
4.2.2棧的數(shù)組實現(xiàn) 43
4.2.3棧的鏈接存儲實現(xiàn) 46
4.3棧的應用實例 49
4.3.1數(shù)制轉換實例 49
4.3.2堆棧實例 50
4.4棧與遞歸 51
4.5本章小結 52
4.6本章習題 52
第5章 隊列 53
5.1隊列的基本概念 53
5.1.1隊列的實例 53
5.1.2隊列的定義 54
5.2隊列的分類 54
5.2.1隊列存儲結構分類 54
5.2.2鏈隊列 55
5.2.3循環(huán)隊列 55
5.3隊列的實現(xiàn) 56
5.3.1隊列的運算 56
5.3.2隊列的順序存儲操作與實現(xiàn) 57
5.3.3隊列的鏈接存儲操作與實現(xiàn) 61
5.4本章小結 65
5.5本章習題 65
第6章 串 66
6.1串的應用實例 66
6.1.1串的應用舉例 66
6.1.2串的定義 67
6.2串在非數(shù)值數(shù)據(jù)運算中的重要地位 70
6.3 串的運算 70
6.3.1串的存儲表示 71
6.3.2串的存儲結構與實現(xiàn) 73
6.4本章小結 77
6.5本章習題 78
第7章 數(shù)組與矩陣 79
7.1數(shù)組概述 79
7.1.1數(shù)組實例 79
7.1.2數(shù)組定義 79
7.2數(shù)組的存儲 80
7.3矩陣 81
7.3.1矩陣簡介 8l
7.3.2稀疏矩陣 8l
7.3.3用三元數(shù)組表示的稀疏矩陣 82
7.3.4用十字鏈表示的稀疏矩陣 85
7.4特殊矩陣的壓縮存儲 89
7.4.1對稱矩陣的壓縮存儲 89
7.4.2三角矩陣的壓縮存儲 90
7.4.3帶狀矩陣的壓縮存儲 91
7.5本章小結 92
7.6本章習題 92
第8章 樹 93
8.1樹型結構 93
8.1.1樹型結構實例 93
8.1.2樹型結構定義 94
8.1.3樹型結構相關術語 95
8.1.4樹的表示方法 96
8.2二叉樹 97
8.2.1二叉樹實例 97
8.2.2二又樹定義 97
8.2.3二叉樹的基本性質 98
8.2.4二叉樹的存儲結構 100
8.2.5二叉樹的操作 102
8.2.6二又樹遍歷 104
8.3二又樹和森林的關系 106
8.3.1二叉樹與樹的轉換 106
8.3.2樹和森林的遍歷 110
8.4樹的應用 112
8.4.1最佳查找樹 112
8.4.2平衡樹 118
8.4.3huffman算法 123
8.5本章小結 126
8.6本章習題 126
第9章 圖 128
9.1 圖的定義和基本術語 128
9.1.1圖的定義 128
9.1.2圖的基本術語 129
9.2圖的存儲結構 130
9.2.1鄰接矩陣 130
9.2.2鄰接表 131
9.3圖的遍歷 133
9.3.1深度優(yōu)先搜索(dfs)遍歷 133
9.3.2深度優(yōu)先搜索(bfs)遍歷 135
9.4最小生成樹 136
9.4.1普里姆(prim)算法 137
9.4.2克魯斯卡爾(kruskal)算法 138
9.5最短路徑 140
9.6拓撲排序 143
9.7關鍵路徑法 145
9.8本章小結 149
9.9本章習題 149
第10章 查找 151
10.1線性表的查找 151
10.1.1順序查找 151
10.1.2折半查找 153
10.1.3分塊查找 156
10.2哈希法 157
10.2.1哈希表的概念 157
10.2.2哈希函數(shù)的構造 158
10.2.3處理沖突的方法 160
10.2.4.哈希表的查找分析 162
10.3本章小結 163
10.4本章習題 163
第11章 排序 164
11.1基本概念 164
11.2插入排序 165
11.2.1直接插入排序 165
11.2.2希爾排序 167
ll.3交換排序 169
11.3.1冒泡排序 169
11.3.2快速排序 171
11.4選擇排序 174
11.4.1簡單選擇排序 174
1 1.4.2堆排序 176
11.5歸并排序 178
11.5.1歸并排序的基本思想 178
11.5.2歸并排序算法 178
11.6基數(shù)排序 180
11.6.1基數(shù)排序的基本思想 180
11.6.2鏈式基數(shù)排序算法 182
11.7本章小結 183
11.8本章習題 184
部分習題答案 185