數據結構與算法（第4版）

《數據結構與算法（第4版）》是2020年2月機械工業出版社出版的圖書，作者是羅文劼、史青宣、苗秀芬。

基本介紹

• 中文名：數據結構與算法（第4版）
• 作者：羅文劼、史青宣、苗秀芬
• 出版社：機械工業出版社
• 出版時間：2020年2月
• 定價：59 元
• 開本：16 開
• 裝幀：平裝
• ISBN：9787111614067

內容簡介

《數據結構與算法 第4版》共包括8章內容，詳細講述了線性結構、樹結構和圖結構中的數據表示及數據處理的方法，並對查找和排序兩種重要的數據處理技術做了細緻的探討。《數據結構與算法 第4版》對每一類數據結構的分析均按照“邏輯結構—存儲結構—基本運算的實現—時空性能分析—典型套用實例—知識小結—練習題—實驗題”的順序進行講解，算法全部採用C語言描述，很容易轉換成程式。《數據結構與算法 第4版》語言敘述通俗易懂、由淺入深，算法可讀性好、套用性強。《數據結構與算法 第4版》不僅配有算法設計的套用實例和大量的練習題，還針對重點、難點問題配有授課視頻講解，掃描二維碼即可觀看。

圖書目錄

前言

第1章 緒論1

1.1 引言1

1.1.1 為什麼要學習數據結構1

1.1.2 “數據結構”課程的內容4

1.2 數據結構的概念5

1.2.1 基本概念和術語5

1.2.2 抽象數據類型7

1.3 算法8

1.3.1 算法及其特徵8

1.3.2 算法的描述9

1.3.3 算法的性能分析9

1.4 遞歸12

1.4.1 遞歸的概念12

1.4.2 遞歸調用的實現原理13

1.4.3 遞歸轉換為非遞歸15

1.4.4 遞歸套用舉例16

1.5 本章知識點小結17

練習題18

實驗題20

題目1 比較算法複雜性描述函式的

增長20

題目2 全排列的遞歸實現21

題目3 皇后問題21

第2章 基本線性結構22

2.1 線性表22

2.1.1 問題提出22

2.1.2 線性表的定義23

2.1.3 線性表的基本運算23

2.2 線性表的順序存儲24

2.2.1 順序表24

2.2.2 順序表上基本運算的實現26

2.2.3 順序表套用舉例29

2.3 線性表的鏈式存儲31

2.3.1 單鍊表31

2.3.2 單鍊表上基本運算的實現33

2.3.3 循環鍊表39

2.3.4 雙向鍊表39

2.3.5 鍊表套用舉例41

2.4 順序表和鍊表的比較44

2.5 堆疊45

2.5.1 堆疊的定義45

2.5.2 堆疊的存儲及基本運算的

實現46

2.5.3 堆疊套用舉例49

2.6 佇列58

2.6.1 佇列的定義58

2.6.2 佇列的存儲及基本運算的

實現59

2.6.3 佇列套用舉例64

2.7 本章知識點小結67

練習題68

實驗題72

題目1 Josephus環問題72

題目2 模擬停車場管理73

第3章 線性結構的擴展75

3.1 字元串75

3.1.1 字元串的基本概念75

3.1.2 順序串76

3.1.3 模式匹配79

3.2 多維數組與特殊矩陣84

3.2.1 多維數組84

3.2.2 特殊矩陣86

3.2.3 稀疏矩陣90

3.3 廣義表99

3.3.1 廣義表的基本概念99

3.3.2 廣義表的存儲101

3.4 本章知識點小結103

練習題104

實驗題107

題目 格式化文本107

第4章 樹結構110

4.1 引言110

4.1.1 問題提出110

4.1.2 相關概念111

4.2 二叉樹113

4.2.1 二叉樹的概念113

4.2.2 二叉樹的主要性質114

4.2.3 二叉樹的存儲116

4.2.4 二叉樹基本運算的實現119

4.3 二叉樹的遍歷121

4.3.1 遞歸方法實現二叉樹的遍歷121

4.3.2 非遞歸方法實現二叉樹的遍歷123

4.3.3 佇列方法實現二叉樹的層次遍歷126

4.4 二叉樹遍歷的套用127

4.4.1 構造二叉樹的二叉鍊表存儲127

4.4.2 在二叉樹中查找值為x的數據元素128

4.4.3 統計給定二叉樹中葉子結點的數目128

4.4.4 由遍歷序列恢復二叉樹129

4.5 線索二叉樹130

4.5.1 線索二叉樹的定義及結構130

4.5.2 線索二叉樹的構建132

4.5.3 線索二叉樹的遍歷133

4.6 最優二叉樹136

4.6.1 最優二叉樹的概念136

4.6.2 最優二叉樹的構造138

4.6.3 最優二叉樹的套用——哈夫曼編碼141

4.7 樹和森林143

4.7.1 樹的基本操作與表示143

4.7.2 樹的存儲144

4.7.3 樹和森林與二叉樹之間的轉換148

4.7.4 樹或森林的遍歷150

4.7.5 樹的套用151

4.8 本章知識點小結153

練習題155

實驗題159

題目 哈夫曼編碼/解碼器159

第5章 圖結構161

5.1 引言161

5.1.1 問題提出161

5.1.2 相關概念162

5.1.3 圖的基本操作165

5.2 圖的存儲方法165

5.2.1 鄰接矩陣165

5.2.2 鄰接表167

*5.2.3 十字鍊表169

*5.2.4 鄰接多重表171

5.3 圖的遍歷173

5.3.1 深度優先搜尋173

5.3.2 廣度優先搜尋175

5.3.3 套用圖的遍歷判定圖的連通性177

5.4 生成樹與最小生成樹178

5.4.1 生成樹和生成森林178

5.4.2 最小生成樹179

5.4.3 構造最小生成樹的Prim

算法180

5.4.4 構造最小生成樹的Kruskal

算法183

5.5 最短路徑186

5.5.1 從一個源點到其他各點的最短路徑186

*5.5.2 每一對頂點之間的最短路徑——弗洛伊德算法189

5.6 拓撲排序193

5.6.1 有向無環圖的概念193

5.6.2 AOV網與拓撲排序194

5.7 關鍵路徑198

5.7.1 AOE網與關鍵路徑198

5.7.2 關鍵路徑的確定199

5.8 本章知識點小結203

練習題206

實驗題208

題目 校園導遊程式208

第6章 查找210

6.1 引言210

6.1.1 問題提出210

6.1.2 相關概念210

6.2 線性表查找212

6.2.1 順序查找212

6.2.2 在順序存儲的有序表上查找214

6.3 樹表查找218

6.3.1 二叉排序樹218

6.3.2 平衡二叉樹224

*6.3.3 B樹和B+樹230

6.4 散列表查找236

6.4.1 散列表236

6.4.2 常用的散列函式237

6.4.3 處理衝突的方法及散列表的構造238

6.4.4 散列表上的查找242

6.4.5 散列表上的插入244

6.4.6 散列表上的刪除245

6.5 本章知識點小結245

練習題246

實驗題249

題目1 職工信息檢索系統249

題目2 個人圖書管理系統250

第7章 排序252

7.1 引言252

7.1.1 問題提出252

7.1.2 相關概念252

7.2 插入排序254

7.2.1 直接插入排序254

7.2.2 折半插入排序256

7.2.3 希爾排序256

7.3 交換排序258

7.3.1 冒泡排序258

7.3.2 快速排序259

7.4 選擇排序261

7.4.1 簡單選擇排序261

7.4.2 樹型選擇排序262

7.4.3 堆排序263

7.5 歸併排序266

7.5.1 兩個有序表的合併266

7.5.2 二路歸併排序的疊代算法267

7.5.3 二路歸併排序的遞歸算法268

*7.6 基數排序268

7.6.1 多關鍵碼排序268

7.6.2 鏈式基數排序269

7.7 排序方法比較272

7.8 本章知識點小結274

練習題275

實驗題278

題目 各種內部排序的性能比較278

第8章 擴展套用舉例279

8.1 求最大子段和279

8.1.1 問題描述279

8.1.2 問題分析與解決279

8.2 表達式樹的構造283

8.2.1 問題描述283

8.2.2 問題分析與解決283

8.3 由等價關係求劃分287

8.3.1 問題描述287

8.3.2 問題分析與解決287

8.4 本章知識點小結289

練習題290

實驗題290

題目1 模擬銀行排隊辦理業務290

題目2 0-1背包問題291

附錄292

附錄A 實驗要求292

實驗題目294

附錄B 模擬試卷295

模擬試卷一295

模擬試卷二296

模擬試卷三299

模擬試卷四301

參考文獻304