數據結構(2018年清華大學出版社出版的圖書)

成書過程

修訂情況

該教材由邵斌、葉星火、樊艷芬、朱紹軍編著，作者根據自己的教學經驗總結，為地方本科院校計算機類學生編寫了該教材。

出版工作

2018年8月1日，該教材由清華大學出版社出版。

出版社工作人員

責任編輯	封面設計	責任校對	責任印製
顏廷芳	常雪影	劉靜	叢懷宇

內容簡介

全書共分9章，第1章作為全書的綜述和基礎，介紹了數據結構、算法的相關概念和算法分析方法等，其後各章分別討論了線性表、棧和佇列、串、多維數蜜廈市組和廣義表、樹和二叉樹、圖、數據結構的定義、表示和實現，最後兩章介紹了查找和內部排序的各種方法。在重點章節中，還結合套用實例，介紹了套用數據結構和算法解決實際問題及進行程式設計的方法。在每章後面帶有適量的習題，習題中編排了選擇題和填空題，並配有習題答案。

教材目錄

第1章概論1

1.1什麼是數據結構1

1.1.1數據和數據元素1

1.1.2數據對象與數據類型2

1.1.3數據結煮船您充構2

1.2為什麼要學習數據結構5

1.2.1學習數據結構的重要性5

1.2.2數據結構的套用舉例5

1.3算法和算法分析7

1.3.1什麼是算法7

1.3.2算法的描述和設計7

1.3.3算法分析8

本章小結10

習題10

第2章線性表12

2.1線性表主鍵旬的基本概念12

2.1.1線性表的定義12

2.1.2線性表的基本操作13

2.2線性表的順序存儲13

2.2.1順序表13

2.2.2順序表的基本操作14

2.2.3順序存儲方式舉例17

2.3線性表的鏈式存儲20

2.3.1單鍊表的基本概念20

2.3.2單鍊表的基本操作22

2.3.3鏈式存儲舉例25

2.3.4循環鍊表28

2.3.5雙向鍊表30

2.3.6雙向循環鍊表332.3.7靜態鍊表34

2.4線性表順序存儲與鏈式存儲的比較35

2.5線性表的套用36

2.5.1約瑟夫問題36

2.5.2多項式加法38

2.5.3電文加密40

本章小結42

習題43

第3章棧和佇列45

3.1棧45

3.1.1棧的定義與基本操作45

3.1.2順序棧的存儲結構和操作的實現47

3.1.3鏈棧的存儲結構和操作的實現50

3.2棧的套用52

3.2.1數制轉換52

3.2.2括弧匹配問題54

3.2.3子程式的調用55

3.2.4利用一個順序棧逆置一個帶頭節點的單鍊表56

3.2.5後綴表遙愚達式59

3.3佇列61

3.3.1佇列的定義與基本操作61

3.3.2鏈佇列的存棵拜晚儲結構和操作的實現62

3.3.3順序佇列的存儲結構和操作的實現64

3.4佇列的套用68

3.4.1列印楊輝三設民肯凳角形68

3.4.2迷宮問題：尋找一條從迷宮入口到出口的最短路徑71

3.5遞歸74

3.5.1遞歸的定義與實現74

3.5.2遞歸消除77

本章小結81

習題81

第4章串85

4.1串的定義和基本操作85

4.1.1串的定義85

4.1.2串的基本操作87

4.2串的表示和實現88

4.2.1串的定長順序存儲88

4.2.2串的堆存儲結構91

4.2.3串的塊鏈存儲結構93

4.3串的模式匹配算法97

4.3.1基本的模式匹配算法97

4.3.2模式匹配的改進算法——KMP算法100

本章小結102

習題102

第5章多維數組和廣義表104

5.1多維數組104

5.1.1多維數組的定義104

5.1.2數組的存儲結構105

5.2矩陣的壓縮存儲106

5.2.1特殊矩陣106

5.2.2稀疏矩陣108

5.3廣義表114

本章小結116

習題117

第6章樹和二叉樹118

6.1樹的概念與基本操作118

6.1.1樹的定義118

6.1.2樹的一些基本兵元采概念119

6.1.3樹的基本操作120

6.2二叉樹120

6.2.1二叉樹的定義和基本操作120

6.2.2二叉樹的性質121

6.2.3二叉樹的存儲結構123

6.3二叉樹的遍歷與線索化124

6.3.1二叉樹的遍歷124

6.3.2線索二叉樹127

6.3.3基於遍歷的套用與線索二叉樹的套用129

6.3.4標識符樹134

6.4樹和森林134

6.4.1樹的存儲結構134

6.4.2樹、森林和二叉樹之間的轉換137

6.4.3樹和森林的遍歷140

6.5哈夫曼樹及其套用142

6.5.1與哈夫曼樹相關的基本概念142

6.5.2哈夫曼樹的套用144

6.5.3哈夫曼編碼算法的實現146

*6.6樹的計數147

本章小結150

習題151

第7章圖154

7.1圖的基本概念154

7.1.1圖的定義154

7.1.2圖的相關術語155

7.2圖的存儲結構157

7.2.1鄰接矩陣表示法157

7.2.2鄰接表表示法159

7.3圖的遍歷163

7.3.1深度優先搜尋法163

7.3.2廣度優先搜尋法165

7.3.3非連通圖的遍歷167

7.4生成樹與最小生成樹167

7.4.1生成樹的概念167

7.4.2構造最小生成樹的普里姆(Prim)算法168

7.4.3構造最小生成樹的克魯斯卡爾(Kruskal)算法171

7.5最短路徑173

7.5.1從某個源點到其餘各頂點的最短路徑174

7.5.2每一對頂點之間的最短路徑178

7.6拓撲排序181

7.7關鍵路徑184

本章小結190

習題190

第8章查找195

8.1查找的基本概念195

8.1.1查找表和查找195

8.1.2查找表的數據結構表示196

8.1.3平均查找長度ASL196

8.2線性表的查找196

8.2.1順序查找196

8.2.2二分查找198

8.2.3分塊查找201

8.3樹表的查找203

8.3.1二叉排序樹203

*8.3.2平衡二叉樹208

*8.3.3B-樹212

8.4散列表的查找221

8.4.1散列表的概念221

8.4.2散列函式的構造方法222

8.4.3處理衝突的方法223

8.4.4散列表上的運算227

本章小結230

習題230

第9章排序232

9.1排序的基本概念232

9.1.1關鍵字與排序232

9.1.2排序的穩定性233

9.1.3排序方法的分類233

9.1.4排序算法性能評價233

9.1.5不同存儲方式的排序過程233

9.2插入排序234

9.2.1直接插入排序234

9.2.2希爾排序237

9.3交換排序239

9.3.1冒泡排序239

9.3.2快速排序(霍爾排序)240

9.4選擇排序244

9.4.1直接選擇排序244

9.4.2堆排序245

9.5歸併排序250

9.6基數排序253

9.6.1桶排序253

9.6.2多關鍵字的排序253

9.6.3鏈式基數排序254

9.7內部排序算法比較257

9.8外部排序簡介259

本章小結259

習題260

參考文獻263

（註：目錄排版順序為從左列至右列）

教學資源

該教材有配套教材——《數據結構習題解答與實驗指導》。

書名	書號	出版社	出版時間	作者
《數據結構習題解答與實驗指導》	9787302493310	清華大學出版社	2018.09.01	樊艷芬、邵斌、朱紹軍

教材特色

該教材採用C語言作為數據結構和算法的描述語言，並且對關鍵的算法都安排了比較完整的C語言程式供學生上機實習參考，只要添加上主函式，程式即可運行。該教材避免抽象理論的介紹和複雜公式的推導。對各種數據結構均從實際出發，通過對實例的分析，使學生理解數據結構的基本概念。

作者簡介

邵斌，1971年生，男，碩士，湖州師範學院信息工程學院副教授、碩士生導師。研究方向為人工智慧、模式識別、數據融合、數據挖掘、GIS等。

葉星火，男，1982年生，博士，湖州師範學院信息工程學院教師。研究方向為數據挖掘生物信息學等。

朱紹軍，湖州師範學院信息工程學院教師。