數據結構

第1章 數據結構基礎概論 1
1.1 數據結構研究的主要內容 1
1.2 基本概念和術語 4
1.3 算法 4
1.3.1 算法的概念 4
1.3.2 算法的描述 5
1.3.3 算法的評價 7
本章小結 8
練習題 9
第2章 線性表 10
2.1 線性表的定義和基本操作 10
2.1.1 線性表的定義 10
2.1.2 線性表的基本操作 11
2.2 線性表的順序存儲結構 12
2.2.1 線性表的順序存儲結構及其特點 12
2.2.2 典型操作的算法實現 13
2.3 線性表的鏈式存儲結構 16
2.3.1 線性表的鏈式存儲結構及其特點 16
2.3.2 典型操作的算法實現 18
2.3.3 循環(huán)鏈表 22
2.3.4 雙向循環(huán)鏈表 23
2.4 線性表的應用舉例 25
2.4.1 使用順序存儲結構的例子 26
2.4.2 使用鏈式存儲結構的例子 27
本章小結 29
練習題 29
第3章 棧和隊列 31
3.1 棧 31
3.1.1 棧的定義 31
3.1.2 棧的順序存儲 32
3.1.3 棧的鏈式存儲 34
3.1.4 棧的應用舉例 35
3.2 隊列 38
3.2.1 隊列的定義 38
3.2.2 隊列的順序存儲 39
3.2.3 隊列的鏈式存儲 44
3.2.4 隊列的應用舉例 46
本章小結 47
練習題 47
第4章 串和數組 48
4.1 串 48
4.1.1 串的定義和基本運算 48
4.1.2 串的存儲結構 50
4.2 數組 53
4.2.1 數組的定義和基本運算 53
4.2.2 數組的存儲結構 54
4.2.3 矩陣的壓縮存儲 56
本章小結 62
練習題 62
第5章 樹和二叉樹 64
5.1 樹 64
5.1.1 樹的定義和基本運算 64
5.1.2 樹的存儲結構 66
5.2 二叉樹 70
5.2.1 二叉樹的定義和基本運算 70
5.2.2 二叉樹的性質 71
5.2.3 二叉樹的存儲結構 74
5.2.4 遍歷二叉樹 76
5.2.5 典型二叉樹的操作算法 83
5.2.6 樹、森林與二叉樹的轉換 87
5.3 哈夫曼樹及其應用 90
5.3.1 哈夫曼樹的定義 90
5.3.2 判定樹 93
5.3.3 前綴編碼 94
本章小結 96
練習題 96

第6章 圖 98
6.1 圖的定義 98
6.1.1 圖的定義 98
6.1.2 圖的基本操作 100
6.2 圖的存儲結構 101
6.2.1 鄰接矩陣 101
6.2.2 鄰接表 102
6.3 圖的遍歷 105
6.3.1 深度優(yōu)先遍歷 105
6.3.2 廣度優(yōu)先遍歷 107
6.4 最小生成樹問題 109
6.4.1 圖的生成樹和森林 109
6.4.2 最小生成樹 110
6.5 拓撲排序問題 113
本章小結 116
練習題 116
第7章 查找 118
7.1 基本概念 118
7.2 靜態(tài)查找 119
7.2.1 順序查找 119
7.2.2 折半查找 121
7.3 動態(tài)查找 123
7.3.1 二叉排序樹 124
7.3.2 二叉排序樹的查找 124
7.3.3 二叉排序樹的插入 126
7.3.4 二叉排序樹的刪除 128
7.4 哈希表 129
7.4.1 哈希表的概念 129
7.4.2 哈希函數的構造 129
7.4.3 解決沖突的方法 130
7.4.4 哈希表查找及其分析 130
本章小結 131
練習題 132
第8章 排序 133
8.1 基本概念 133
8.2 插入排序 134
8.2.1 直接插入排序 134
8.2.2 希爾排序 136
8.3 交換排序 139
8.3.1 冒泡排序 139
8.3.2 快速排序 143
8.4 選擇排序 147
8.4.1 簡單選擇排序 147
8.4.2 堆排序 149
8.5 歸并排序 154
8.5.1 歸并排序的基本思想 154
8.5.2 歸并排序過程示例 154
8.5.3 歸并排序算法 154
8.6 基數排序 156
8.6.1 基數排序的基本思想 156
8.6.2 基數排序示例 159
8.6.3 鏈式基數排序算法 160
本章小結 162
練習題 163
第9章 文件 164
9.1 文件的基本概念 164
9.2 文件的操作 165
9.3 文件的組織 165
本章小結 166
練習題 166