據結構、算法與套用

《據結構、算法與套用》是2015年出版的圖書，作者是齊悅、夏克儉、姚琳。

基本介紹

• 中文名：據結構、算法與套用
• 作者：齊悅、夏克儉、姚琳
• 出版時間：2015年4月23日 
• 出版社：清華大學出版社 
• ISBN：9787302399766
• 定價：34.5 元
• 裝幀：平裝

主要內容

本書系統地介紹了各種類型的數據結構、數據結構在計算機存儲器中的表示以及相關的C語言描述算法。另外，對各類數據結構在實際中的套用做了較深入的介紹，包含示例分析及典型算法的C語言源程式。本書最後對算法設計的基礎知識進行了討論，拓展了知識面。每章後附有習題，便於讀者進一步理解和鞏固所學的知識。

本書可作為大專院校計算機專業或相關專業的教材，也可供從事計算機軟體開發的工程技術人員參考。

目錄

第1章緒論1

1.1數據結構研究的內容和方法1

1.1.1數據結構的含義1

1.1.2數據結構研究的內容2

1.1.3研究數據結構的方法6

1.2抽象數據類型的表示與實現7

1.3學習數據結構的目的8

1.3.1數據結構的發展簡史及在計算機科學中的地位8

1.3.2學習數據結構的目的9

1.4算法和算法分析9

1.4.1算法的定義9

1.4.2算法的性質9

1.4.3算法的設計目標11

1.4.4算法效率的度量11

習題114

第2章線性表16

2.1線性表的定義及其基本操作16

2.1.1線性表的定義16

2.1.2線性表的邏輯結構和特徵16

2.1.3線性表的抽象數據類型表示17

2.2線性表的順序存儲結構19

2.2.1順序表20

2.2.2順序表上的基本操作20

2.2.3順序存儲結構的基本特點23

2.3線性表的鏈式存儲結構24

2.3.1單鍊表24

2.3.2單鍊表中的基本操作262.3.3單向循環鍊表31

2.3.4雙向鍊表32

2.3.5靜態鍊表34

2.3.6鏈式存儲結構的特點37

2.4線性表套用舉例38

2.4.1Josephu問題38

2.4.2一元多項式的表示與相加41

本章小結45

習題245

第3章棧與佇列47

3.1棧47

3.1.1棧的定義及其操作47

3.1.2棧的順序存儲結構49

3.1.3棧的鏈式存儲結構51

3.2棧套用舉例52

3.2.1數制轉換53

3.2.2行編輯處理54

3.2.3表達式求值56

3.3棧與遞歸函式61

3.3.1遞歸定義與遞歸函式61

3.3.2遞歸函式到非遞歸函式的轉化64

3.4佇列66

3.4.1佇列的定義及其操作66

3.4.2佇列的順序存儲結構67

3.4.3佇列的鏈式存儲結構70

3.5佇列套用實例72

3.5.1迷宮問題72

3.5.2離散事件模擬75

3.5.3有序事件模擬80

本章小結82

習題383

第4章串84

4.1串的定義及其操作84

4.1.1串的定義84

4.1.2串的抽象數據類型85

4.2串的存儲結構87

4.2.1串的靜態存儲結構87

4.2.2串的動態存儲結構93

4.3串模式匹配98

4.4串套用舉例101

4.4.1文本編輯101

4.4.2建立詞索引表104

本章小結106

習題4106

第5章數組和廣義表107

5.1數組的定義及其操作107

5.1.1數組的定義107

5.1.2數組的抽象數據類型108

5.2數組的存儲結構109

5.2.1數組的靜態存儲方式109

5.2.2數組的動態存儲方式112

5.3矩陣的壓縮存儲113

5.3.1特殊矩陣的壓縮存儲113

5.3.2稀疏矩陣的壓縮存儲116

5.4廣義表的定義及其操作120

5.4.1廣義表的定義120

5.4.2廣義表的抽象數據類型121

5.5廣義表的存儲結構122

5.5.1廣義表的鏈式存儲122

5.5.2廣義表基本操作的遞歸算法124

本章小結127

習題5127

第6章樹129

6.1樹的基本概念129

6.1.1樹的定義及基本操作130

6.1.2樹的性質133

6.2二叉樹135

6.2.1二叉樹的定義及基本操作135

6.2.2二叉樹的性質137

6.2.3二叉樹的存儲結構139

6.3二叉樹的遍歷142

6.3.1二叉樹的遍歷算法142

6.3.2二叉樹遍歷算法的非遞歸形式144

6.3.3二叉樹遍歷的套用148

6.4線索二叉樹151

6.4.1線索二叉樹的概念151

6.4.2建立線索二叉樹153

6.4.3線索二叉樹的遍歷154

6.4.4線索二叉樹的更新155

6.5樹和森林156

6.5.1樹的存儲結構156

6.5.2森林和二叉樹的轉換160

6.5.3樹和森林的遍歷161

6.6二叉樹套用舉例162

6.6.1Huffman樹及其構造算法162

6.6.2Huffman編碼及解碼166

本章小結169

習題6169

第7章圖171

7.1圖的定義及操作171

7.1.1圖的定義171

7.1.2圖的抽象數據類型175

7.2圖的存儲結構177

7.2.1數組表示法177

7.2.2鄰接表表示法179

7.2.3十字鍊表表示法181

7.2.4鄰接多重表表示法183

7.3圖的遍歷184

7.3.1深度優先搜尋算法184

7.3.2廣度優先搜尋算法186

7.3.3求連通分量的算法187

7.4最小生成樹188

7.4.1Prim算法189

7.4.2Kruskal算法191

7.5最短路徑問題193

7.5.1Dijkstra算法193

7.5.2Floyd算法197

7.6圖的套用實例199

7.6.1拓撲排序200

7.6.2關鍵路徑204

本章小結208

習題7209

第8章查找211

8.1查找概述211

8.2順序表的靜態查找212

8.2.1順序查找算法213

8.2.2折半查找算法214

8.2.3分塊查找算法216

8.3樹表的動態查找219

8.3.1二叉排序樹和平衡二叉排序樹219

8.3.2B-樹232

8.3.3B+樹和B樹240

8.4Hash表的查找241

8.4.1Hash表的含義241

8.4.2Hash函式的構造方法243

8.4.3處理衝突的方法246

8.4.4Hash表的查找及分析248

本章小結251

習題8252

第9章排序253

9.1排序概述253

9.2插入排序255

9.2.1直接插入排序255

9.2.2折半插入排序258

9.2.3鍊表插入排序259

9.2.4Shell排序261

9.3交換排序262

9.3.1起泡排序262

9.3.2快速排序264

9.4選擇排序266

9.4.1直接選擇排序267

9.4.2堆選擇排序268

9.5歸併排序274

9.6基數排序276

9.7各種內排序方法的比較討論280

9.8外排序概述281

習題9283

第10章算法設計基礎284

10.1窮舉法284

10.1.1算法概述284

10.1.2窮舉法解決背包問題285

10.2貪心法287

10.2.1算法概述287

10.2.2貪心法解決背包問題288

10.3分治法289

10.3.1分治策略289

10.3.2套用實例： 大整數乘法291

10.4動態規劃法292

10.4.1算法概述292

10.4.2動態規劃法解決背包問題293

10.5回溯法294

10.5.1算法概述294

10.5.2回溯法解決背包問題295

本章小結296

習題10296

參考文獻298