基本介紹
- 書名：數據結構
- 作者：汪沁，奚李峰
- ISBN：9787302208044
- 定價：25.00元
- 出版社：清華大學出版社
- 出版時間：2009-9-1
- 開本：16
內容介紹,圖書目錄,
內容介紹
本書敘述清晰、深入淺出、注重實踐環節，便於教學與實踐。
本書可作為高等院校計算機專業的教材，也可供從事計算機套用與工程工作的科技工作者作為自學參考圖書。
圖書目錄
第1章 緒論
1.1 數據結構的概念
1.1.1 引言
1.1.2 數據結構有關概念與術語
1.2 抽象數據類型
1.3 算法描述與分析
1.3.1 什麼是算法
1.3.2 算法分析技術
1.4 小結
討論小課堂
習題
第2章 線性表
2.1 線性表的定義及其運算
2.1.1 線性表的定義
2.1.2 線性表的基本操作
2.2 線性表的順序存儲結構及實現
2.2.1 順序存儲結構
2.2.2 線性表在向量中基本運算的實現
2.3 線性表的鍊表存儲結構
2.3.1 單鍊表
2.3.2 線性鍊表基本運算的實現
2.4 循環鍊表和雙向鍊表
2.4.1 循環鍊表
2.4.2 雙向鍊表
2.4.3 順序存儲結構與鍊表存儲結構的綜合分析與比較
2.5 單鍊表的套用
2.5.1 多項式相加的鍊表存儲結構
2.5.2 多項式相加的算法實現
2.6 小結
討論小課堂
習題
第 3章 棧和佇列
3.1 棧
3.1.1 棧的定義
3.1.2 棧的基本操作
3.2 棧的順序存儲結構及實現
3.2.1 棧的順序存儲結構
3.2.2 順序棧的類定義
3.3 棧的鍊表存儲結構及實現
3.4 棧的套用
3.4.1 表達式的計算
3.4.2 子程式的嵌套調用
3.4.3 遞歸調用
3.4.4 n階Hanoi塔問題
3.5 佇列
3.5.1 佇列的定義及運算
3.5.2 佇列的抽象數據類型描述
3.6 佇列的順序存儲結構及實現
3.7 佇列的鍊表存儲結構及實現
3.8 佇列的套用
3.9 小結
討論小課堂
習題
第4章 串
4.1 串的基本概念
4.1.1 串的定義
4.1.2 串的基本操作
4.2 串的存儲與基本操作的實現
4.2.1 定長順序串
4.2.2 堆串
4.2.3 塊鏈串
4.2.4 串操作的實現
4.3 串的模式匹配
4.3.1 樸素模式匹配算法
4.3.2 模式匹配的KMP算法
4.4 串的套用舉例：文本編輯
4.5 小結
討論小課堂
習題
第5章 數組和廣義表
5.1數組的定義及運算80
5.1.1數組的定義80
5.1.2數組的基本操作81
5.2數組的存儲結構81
5.3特殊矩陣的壓縮存儲82
5.3.1對稱矩陣83
5.3.2三角矩陣84
5.3.3對角矩陣85
5.4稀疏矩陣的壓縮存儲86
5.4.1稀疏矩陣的順序存儲結構--三元組順序表86
5.4.2稀疏矩陣的鏈式存儲結構89
5.5廣義表92
5.5.1廣義表的定義和基本運算92
5.5.2廣義表的存儲93
5.6小結95
討論小課堂96
習題96第6章樹與二叉樹98
6.1樹的概念及術語98
6.1.1樹的定義99
6.1.2樹的基本操作100
6.1.3樹的表示方式100
6.2二叉樹101
6.2.1二叉樹的定義101
6.2.2二叉樹的重要性質101
6.2.3二叉樹的存儲結構102
6.3二叉樹的遍歷104
6.3.1先序遍歷105
6.3.2中序遍歷105
6.3.3後根遍歷106
6.3.4按層遍歷107
6.3.5非遞歸遍歷算法107
6.3.6二叉樹的建立109
6.3.7二叉樹遍歷的套用舉例111
6.4二叉樹與樹、森林的轉換112
6.4.1樹與二叉樹的轉換112
6.4.2森林與二叉樹的轉換113
6.5樹的存儲結構114
6.5.1樹的雙親表示法115
6.5.2孩子表示法115
6.5.3孩子-兄弟表示法115
6.6樹的遍歷116
6.6.1一般樹的遍歷116
6.6.2森林的遍歷118
6.7二叉樹的套用118
6.7.1哈夫曼樹118
6.7.2哈夫曼樹的構造119
6.7.3哈夫曼樹的實現算法119
6.7.4哈夫曼編碼121
6.8小結121
討論小課堂122
習題122第7章圖125
7.1圖的基本概念125
7.1.1圖的定義125
7.1.2圖的術語126
7.1.3圖的基本操作128
7.2圖的存儲結構129
7.2.1圖的鄰接矩陣129
7.2.2鄰接矩陣表示法的C語言類型描述131
7.2.3鄰接矩陣表示法的基本操作的實現132
7.2.4圖的鄰接鍊表133
7.2.5圖的鄰接表表示法的C語言類型描述134
7.2.6建立圖的鄰接表函式和輸出圖的信息函式135
7.3圖的遍歷與圖的連通性137
7.3.1圖的深度優先遍歷137
7.3.2圖的廣度優先遍歷140
7.3.3非連通圖和連通分量141
7.4圖的最小生成樹142
7.4.1最小生成樹的基本概念142
7.4.2普里姆算法143
7.4.3克魯斯卡爾算法145
7.5最短路徑146
7.5.1從某頂點到其餘各頂點的最短路徑146
7.5.2每對頂點之間的最短路徑149
7.6拓撲排序與關鍵路徑151
7.6.1拓撲排序151
7.6.2關鍵路徑154
7.7圖的套用159
7.7.1圖在路由器尋徑中的套用160
7.7.2圖在物流信息系統中套用160
7.8小結161
討論小課堂161
習題162第8章查找163
8.1概述163
8.2靜態查找表164
8.2.1順序查找164
8.2.2折半查找165
8.2.3分塊查找166
8.3動態查找表168
8.3.1二叉排序樹168
8.3.2平衡二叉樹173
8.4小結176
討論小課堂176
習題176第9章排序178
9.1排序的基本概念178
9.2插入排序179
9.2.1直接插入排序179
9.2.2折半插入排序180
9.2.3希爾排序180
9.3交換排序182
9.3.1冒泡排序182
9.3.2快速排序183
9.4選擇排序186
9.4.1簡單選擇排序186
9.4.2堆排序187
9.5歸併排序190
9.6基數排序192
9.7小結195
討論小課堂196
習題197第10章索引結構與散列198
10.1靜態索引結構198
10.1.1索引表198
10.1.2索引表查找198
10.2動態索引結構（B-樹和B+樹）200
10.2.1B-樹的定義201
10.2.2B-樹的運算202
10.2.3B+樹204
10.3鍵樹及Trie樹205
10.3.1鍵樹的定義205
10.3.2雙鏈樹206
10.3.3Trie樹207
10.4哈希表及其查找208
10.4.1哈希表與哈希函式208
10.4.2構造哈希函式的常用方法209
10.4.3解決衝突的主要方法211
10.4.4哈希查找的性能分析215
10.5小結216
討論小課堂216
習題217附錄上機實驗指導220
第1部分上機實驗要求及規範220
第2部分實驗部分221
實驗1複數ADT及其實現221
實驗2線性表223
實驗3棧和佇列230
實驗4串235
實驗5數組237
實驗6樹與二叉樹239
實驗7圖243
實驗8查找247
實驗9排序249
實驗10哈希查找254參考文獻257
