數據結構

作者：朱昌傑、肖建於

定價：29元

印次：2-1

ISBN：9787302370635

出版日期：2014.09.01

印刷日期：2014.08.22

本書系統地介紹了各種常用的數據結構與演演算法方面的基本知識，並使用C語言描述其演演算法。全書共8章，第1章介紹了數據結構與演演算法的一些基本概念；第2～6章分別討論了線性表、棧與隊列、串、多維數組與廣義表、樹和二叉樹、圖等常用的數據結構及其應用；第7章和第8章分別介紹查找和內部排序，它們都是數據處理時廣泛使用的技術。本書的特色是深入淺出，既注重理論又重視實踐；全書配有大量的例題和詳盡的註釋，各章都有不同類型的習題。本書可以作為高等院校計算機專業本科生的教材，也可以作為報考高等學校計算機專業碩士研究生入學考試的復慣用書，也可以作為專科和成人教育的教材，同時還可以作為從事計算機系統軟體和應用軟體設計與開發人員的參考資料。

第1章緒論　/1

1.1數據結構的基本概念 1

1.1.1數據的邏輯結構 1

1.1.2數據的物理結構 2

1.2數據類型和抽象數據類型 3

1.2.1數據類型 3

1.2.2抽象數據類型 4

1.3C語言的數據類型 5

1.4用C語言描述演演算法的注意事項 6

1.4.1演演算法及其特徵 6

1.4.2C語言描述演演算法的注意事項 7

1.5演演算法設計目標和演演算法效率度量 9

1.5.1演演算法設計目標 9

1.5.2演演算法效率度量 10

習題1 11

第2章線性表　/13

2.1線性表的類型定義 13

2.1.1線性表的定義 13

2.1.2線性表的基本運算 14

2.2線性表的順序存儲及實現 14

2.2.1順序表 14

2.2.2順序表基本運算的實現 15

2.2.3順序表其他演演算法舉例 18

2.3線性表的鏈式存儲及實現 19

2.3.1單鏈表 20

2.3.2單鏈表的基本運算的實現 21

2.3.3單鏈表的其他操作舉例 27

2.3.4循環單鏈表 30

2.3.5雙向鏈表 31

2.3.6靜態鏈表 33

2.4線性表的應用舉例 37

2.4.1一元多項式的表示與相加 37

2.4.2約瑟夫環問題 40

習題2 41

第3章棧和隊列　/44

3.1棧 44

3.1.1棧的定義 44

3.1.2棧的順序存儲結構 45

3.1.3棧的鏈式存儲結構 47

3.2棧的應用舉例 48

3.2.1數制轉換 49

3.2.2括弧匹配的檢驗 49

3.2.3簡單表達式求值 51

3.3隊列 55

3.3.1隊列的定義 55

3.3.2隊列的順序存儲結構 56

3.3.3隊列的鏈式存儲結構 60

3.4隊列應用舉例 62

3.4.1鍵盤輸入循環緩衝區問題 62

3.4.2舞伴問題 64

習題3 66

第4章串、多維數組與廣義表　/68

4.1串 68

4.1.1串的定義 68

4.1.2串的表示和實現 70

4.1.3串的模式匹配演演算法 74

4.1.4串的操作應用——文本編輯 80

4.2數組 81

4.2.1數組的定義 81

4.2.2數組的順序存儲結構 82

4.3矩陣的壓縮存儲 83

4.3.1特殊矩陣 83

4.3.2稀疏矩陣 85

4.4廣義表 88

4.4.1廣義表的定義 88

4.4.2廣義表的基本操作 90

4.4.3廣義表的存儲結構 90

習題4 92

第5章樹和二叉樹　/94

5.1樹的基本概念 94

5.1.1樹的定義 94

5.1.2樹的基本術語 96

5.2二叉樹 97

5.2.1二叉樹的定義 97

5.2.2二叉樹的性質 99

5.2.3二叉樹的存儲結構 102

5.3遍歷二叉樹和線索二叉樹 103

5.3.1二叉樹的遍歷方法及遞歸實現 103

5.3.2二叉樹遍歷的非遞歸實現 105

5.3.3遍歷演演算法的應用 108

5.3.4由遍歷序列構造二叉樹 111

5.3.5線索二叉樹 112

5.4樹和森林 115

5.4.1樹的存儲結構 115

5.4.2樹與二叉樹的轉換 117

5.4.3森林與二叉樹的轉換 118

5.4.4樹和森林的遍歷 120

5.5哈夫曼樹 121

5.5.1哈夫曼樹的基本概念 121

5.5.2哈夫曼樹的構造方法 122

5.5.3哈夫曼編碼 125

習題5 127

第6章圖　/129

6.1圖的基本概念 129

6.1.1圖的定義 129

6.1.2圖的基本術語 130

6.2圖的存儲結構 131

6.2.1鄰接矩陣 131

6.2.2鄰接表 132

6.3圖的遍歷 134

6.3.1深度優先搜索 134

6.3.2廣度優先搜索 136

6.4最小生成樹 137

6.4.1最小生成樹的基本概念 137

6.4.2Prim演演算法構造最小生成樹 138

6.4.3Kruskal演演算法構造最小生成樹 140

6.5有向無環圖及其應用 142

6.5.1拓撲排序 142

6.5.2關鍵路徑 144

6.6最短路徑 147

6.6.1單源點的最短路徑 147

6.6.2每對頂點之間的最短路徑 149

習題6 151

第7章查找　/155

7.1查找的基本概念 155

7.2順序表的靜態查找 156

7.2.1順序查找 156

7.2.2折半查找 157

7.2.3分塊查找 160

7.3樹表的動態查找 162

7.3.1二叉排序樹 163

7.3.2平衡二叉樹 169

7.3.3B-樹 175

7.3.4B+樹 180

7.4散列（Hash）表的查找 182

7.4.1散列表的基本概念 183

7.4.2散列函數構造方法 183

7.4.3處理衝突的方法 186

7.4.4散列表的查找及其分析 189

習題7 191

第8章內部排序　/194

8.1排序的基本概念 194

8.2插入排序 195

8.2.1直接插入排序 195

8.2.2折半插入排序 197

8.2.3希爾排序 198

8.3交換排序 200

8.3.1冒泡排序 200

8.3.2快速排序 202

8.4選擇排序 206

8.4.1直接選擇排序 206

8.4.2堆排序 208

8.5歸併排序 211

8.6基數排序 214

8.6.1多關鍵碼排序 214

8.6.2鏈式基數排序 216

8.7各種內部排序演演算法的比較 220

8.7.1內部排序演演算法的性能比較 220

8.7.2各種內部排序演演算法的選擇 222

習題8 223

參考文獻　/226