新編數據結構及算法教程

《新編數據結構及算法教程概述 》介紹了數據結構的基本概念、基本知識以及數據結構的套用。全書共有三部分：第一部分是線性結構，第二部分是非線性結構，第三部分是數據處理技術。其內容內容涵蓋了全國碩士研究生計算機綜合考試課程的數據結構知識。該書適合作為各類高等院校、高等職業技術學校和計算機相關的各類專業的數據結構與算法的教學用書，同時也是從事軟體設計人員的參考書。

基本介紹

• 書名：新編數據結構及算法教程
• 定價：39.5元
• 出版時間：2012-8-14
• 裝幀：平裝
• 印刷日期：2012-8-14

圖書簡介

本書介紹了數據結構的基本概念、基本知識以及數據結構的套用。全書按照三部分編寫。第一部分是線性結構，包括線性表、棧與佇列、數組和特殊矩陣；第二部分是非線性結構，包括樹和二叉樹、圖；第三部分是數據處理技術，包括查找和排序，內容涵蓋了全國碩士研究生計算機綜合考試課程的數據結構知識。

本書適合作為各類高等院校、高等職業技術學校與計算機相關的各類專業的數據結構與算法的教學用書，也是從事軟體設計人員一本難得的參考書。

目錄

第1章 緒論 /1

1.1 數據結構的起源與發展1

1.2 基本概念和術語2

1.3 理解數據結構3

1.4 數據的邏輯結構和存儲結構4

1.4.1 邏輯結構5

1.4.2 存儲結構6

1.5 抽象數據類型8

1.5.1 數據類型8

1.5.2 抽象數據類型8

1.6 算法分析與評價11

1.6.1 數據結構與算法的關係11

1.6.2 算法的定義11

1.6.3 算法的5大特性11

1.6.4 算法設計的要求12

1.6.5 算法效率分析13

1.6.6 算法的時間複雜度14

1.6.7 算法存儲空間需求16

1.7 本章小結17

1.8 習題17

第2章 線性表 /20

2.1 問題的提出20

2.1.1 問題中的數據分析20

2.1.2 問題中的功能分析21

2.1.3 問題中的數據結構22

2.2 線性表22

2.2.1 線性表的定義22

2.2.2 線性表的存儲結構和基本操作的實現24

2.2.3 線性表的兩種存儲結構的區別47新編數據結構及算法教程目錄 2.3 案例實現48

2.3.1 基於順序表的新生成績管理系統48

2.3.2 基於單向鍊表的新生成績管理系統52

2.4 其他形式的鍊表54

2.4.1 單向循環鍊表54

2.4.2 雙向循環鍊表57

2.5 線性表的套用60

2.5.1 兩個線性表的合併60

2.5.2 一元多項式的套用63

2.6 本章小結69

2.7 習題與實驗70

第3章 棧與佇列 /74

3.1 問題的提出74

3.1.1 問題中的數據分析74

3.1.2 問題中的功能分析74

3.1.3 問題中的數據結構75

3.2 棧76

3.2.1 棧的定義76

3.2.2 棧的存儲結構和基本操作的實現77

3.2.3 棧的兩種存儲結構的區別87

3.2.4 案例實現: 基於棧的括弧匹配87

3.3 棧的套用89

3.3.1 表達式求值89

3.3.2 棧與遞歸94

3.4 佇列103

3.4.1 佇列的定義103

3.4.2 佇列的存儲結構和基本操作的實現105

3.4.3 佇列的兩種存儲結構的區別116

3.4.4 案例實現: 基於佇列的醫院掛號模擬系統116

3.5 佇列的套用120

3.6 共用棧和雙佇列124

3.6.1 共用棧124

3.6.2 雙端佇列126

3.7 本章小結127

3.8 習題與實驗127

第4章 數組和特殊矩陣 /133

4.1 多維數組133

4.1.1 數組的邏輯結構133

4.1.2 數組的記憶體映像133

4.2 特殊矩陣的壓縮存儲136

4.2.1 對稱矩陣136

4.2.2 三角矩陣138

4.2.3 帶狀矩陣139

4.3 稀疏矩陣140

4.3.1 稀疏矩陣的三元組表存儲140

4.3.2 稀疏矩陣的十字鍊表存儲146

4.4 本章小結152

4.5 習題152

第5章 樹和二叉樹 /155

5.1 問題的提出155

5.1.1 問題中的數據分析155

5.1.2 問題中的功能分析156

5.1.3 問題中的數據結構156

5.2 樹的定義和基本術語156

5.2.1 樹的遞歸定義156

5.2.2 樹的基本術語156

5.2.3 樹的表示158

5.2.4 樹的抽象數據類型描述159

5.3 二叉樹159

5.3.1 二叉樹的定義159

5.3.2 二叉樹的性質161

5.3.3 二叉樹的抽象數據類型162

5.3.4 二叉樹的存儲結構163

5.3.5 二叉樹的遍歷及其套用166

5.3.6 案例實現： 基於表達式二叉樹的動態表達式計算192

5.4 線索二叉樹192

5.4.1 線索二叉樹的定義193

5.4.2 線索二叉樹的基本操作實現194

5.4.3 基於中序線索二叉樹的遍歷算法200

5.5 樹、森林與二叉樹的轉換及其套用203

5.5.1 樹、森林與二叉樹的轉換203

5.5.2 樹的存儲結構204

5.5.3 樹和森林的遍歷209

5.5.4 樹的簡單套用210

5.5.5 案例實現： 基於樹結構的行政機構管理217

5.6 哈夫曼樹及其套用220

5.6.1 最優二叉樹--哈夫曼樹220

5.6.2 哈夫曼樹及哈夫曼編碼的構建算法224

5.7 本章小結229

5.8 習題與實驗229

第6章 圖 /234

6.1 問題的提出234

6.1.1 問題中的數據分析235

6.1.2 問題中的功能分析235

6.1.3 問題中的數據結構235

6.2 圖的定義和基本術語235

6.2.1 圖的定義235

6.2.2 圖的基本術語235

6.2.3 圖的分類與連通性237

6.2.4 圖的抽象數據類型定義238

6.3 圖的存儲結構239

6.3.1 圖的鄰接矩陣表示240

6.3.2 圖的鄰接表表示243

6.3.3 有向圖的十字鍊表表示246

6.3.4 無向圖的鄰接多重表表示247

6.4 圖的遍歷249

6.4.1 連通圖的深度優先搜尋(Depth-First Search)249

6.4.2 連通圖的廣度優先搜尋(Breadth-First Search)253

6.4.3 非連通圖的深度(廣度）優先遍歷255

6.4.4 圖的遍歷算法套用255

6.5 圖的連通性261

6.5.1 無向圖的連通分量和生成樹261

6.5.2 最小生成樹及套用261

6.6 最短路徑272

6.6.1 求從某個源點到其餘各點的最短路徑272

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

6.7 有向無環圖及其套用283

6.7.1 拓撲排序284

6.7.2 關鍵路徑287

6.7.3 案例實現： 教學計畫編排系統290

6.7.4 案例實現： 基於有向無環圖的表達式計算295

6.8 本章小結300

6.9 習題與實驗301

第7章 查找 /305

7.1 問題的提出305

7.2 基本概念與描述306

7.2.1 查找的基本概念306

7.2.2 性能分析307

7.2.3 內部查找和外部查找308

7.2.4 C語言描述308

7.3 線性表查找308

7.3.1 順序查找309

7.3.2 二分查找310

7.3.3 分塊查找314

7.3.4 案例實現： 基於順序查找的學生信息表查詢316

7.4 樹表查找320

7.4.1 二叉排序樹320

7.4.2 平衡二叉樹328

7.4.3 B-樹和B+樹344

7.4.4 案例實現： 基於二叉排序樹的學生信息管理352

7.5 哈希表357

7.5.1 哈希表概念357

7.5.2 常用的哈希函式358

7.5.3 解決衝突的方法359

7.5.4 哈希表的查找及其性能分析362

7.6 本章小結364

7.7 習題與實驗365

第8章 排序 /369

8.1 問題的提出369

8.2 基本概念369

8.3 插入排序371

8.3.1 直接插入排序371

8.3.2 折半插入排序373

8.3.3 希爾排序374

8.4 交換排序375

8.4.1 冒泡排序375

8.4.2 快速排序377

8.5 選擇排序379

8.5.1 簡單選擇排序380

8.5.2 堆排序381

8.6 歸併排序384

8.7 基數排序386

8.7.1 多關鍵字排序386

8.7.2 鏈式基數排序387

8.8 案例實現： 學生基本信息表的排序390

8.9 各種內部排序方法的比較397

8.10 本章小結398

8.11 習題399

參考文獻 /402