數據結構（C語言實現）

《數據結構（C語言實現）》是機械工業出版社於2020年出版的書籍

基本介紹

• 中文名：數據結構（C語言實現）
• 作者：郝建偉
• 出版時間：2020年8月19日
• ISBN：9787111660668
• 定價：79.0 元
• 開本：16 開
• 裝幀：平裝

圖書簡介

《數據結構（C語言實現）》內容編排符合當前高等院校“數據結構”課程的現狀和發展趨勢，知識點涵蓋全面，案例和課後習題豐富，每章均有綜合案例以鞏固對知識點的掌握程度，突出實用性和實踐性。《數據結構（C語言實現）》共9章，內容包括緒論、線性表、棧與佇列、串、數組與廣義表、樹、圖、查找及排序。《數據結構（C語言實現）》採用C語言作為數據結構和算法的描述語言。 《數據結構（C語言實現）》可作為高等院校計算機、軟體工程等相關專業“數據結構”課程的教材，也可作為從事計算機軟體開發、準備考取計算機專業研究生和參加軟考的人員的參考用書。

圖書目錄

前言

第1章 緒論1

1.1 數據結構的基本概念1

1.2 抽象數據類型3

1.2.1 抽象數據類型的定義3

1.2.2 抽象數據類型的描述3

1.3 數據的邏輯結構與存儲結構4

1.3.1 邏輯結構4

1.3.2 存儲結構5

1.4 算法的特性與算法的描述6

1.4.1 算法的定義6

1.4.2 算法的特性6

1.4.3 算法的描述6

1.5 算法分析7

1.5.1 算法設計的要求8

1.5.2 算法時間複雜度8

1.5.3 算法空間複雜度13

1.6 關於數據結構課程的地位及

學習方法13

習題14

第2章 線性表17

2.1 線性表的概念及運算17

2.1.1 線性表的邏輯結構17

2.1.2 線性表的抽象數據類型18

2.2 線性表的順序表示與實現19

2.2.1 線性表的順序存儲19

2.2.2 順序表的基本運算20

2.2.3 基本操作算法分析23

2.2.4 順序表套用舉例23

2.3 線性表的鏈式表示與實現27

2.3.1 單鍊表的存儲結構27

2.3.2 單鍊表上的基本運算28

2.3.3 單鍊表套用舉例33

2.3.4 循環單鍊表38

2.3.5 雙向鍊表41

2.4* 靜態鍊表43

2.4.1 靜態鍊表的存儲結構44

2.4.2 靜態鍊表的實現44

2.4.3 靜態鍊表套用舉例46

2.5 線性表套用舉例：一元多項式的

表示與相乘48

2.5.1 一元多項式的表示48

2.5.2 一元多項式的相乘49

2.6 小結53

習題54

第3章 棧與佇列59

3.1 棧的表示與實現59

3.1.1 棧的定義59

3.1.2 棧的抽象數據類型60

3.1.3 順序棧61

3.1.4 鏈棧65

3.2 棧的套用68

3.2.1 數制轉換68

3.2.2 行編輯程式68

3.2.3 算術表達式求值70

3.3 遞歸76

3.3.1 遞歸的定義76

3.3.2 消除遞歸79

3.4 佇列的表示與實現82

3.4.1 佇列的定義82

3.4.2 佇列的抽象數據類型82

3.4.3 順序佇列83

3.4.4 順序循環佇列85

3.4.5* 雙端佇列88

3.4.6 鏈式佇列88

3.4.7 鏈式佇列的實現90

3.5 佇列的套用92

3.5.1 佇列在楊輝三角中的套用92

3.5.2 佇列在回文中的套用94

3.6 綜合案例：停車場管理97

3.7 小結105

習題105

第4章 串109

4.1 串109

4.1.1 串的定義109

4.1.2 串的抽象數據類型109

4.2 串的表示與實現111

4.2.1 定長順序存儲表示與實現111

4.2.2* 堆串的存儲分配表示與實現117

4.2.3* 塊鏈存儲表示與實現123

4.3 串的模式匹配128

4.3.1 Brute-Force經典算法128

4.3.2 KMP算法130

4.3.3 模式匹配套用舉例134

4.4 小結138

習題138

第5章 數組與廣義表141

5.1 數組的定義與運算141

5.1.1 數組的定義141

5.1.2 數組的抽象數據類型142

5.1.3 數組的順序表示與實現142

5.2 特殊矩陣的壓縮存儲146

5.2.1 對稱矩陣的壓縮存儲147

5.2.2 三角矩陣的壓縮存儲147

5.2.3 對角矩陣的壓縮存儲148

5.3 稀疏矩陣的壓縮存儲149

5.3.1 稀疏矩陣的定義149

5.3.2 稀疏矩陣的抽象數據類型149

5.3.3 稀疏矩陣的三元組表示與實現150

5.3.4 稀疏矩陣套用舉例156

5.3.5 稀疏矩陣的十字鍊表表示與實現160

5.4 廣義表164

5.4.1 廣義表的定義164

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

5.5 廣義表的頭尾鍊表表示與實現165

5.5.1 廣義表的頭尾鍊表存儲結構166

5.5.2 廣義表的基本運算166

5.5.3 廣義表套用舉例169

5.6 廣義表的擴展線性鍊表表示與

實現172

5.6.1 廣義表的擴展線性鍊表存儲172

5.6.2 廣義表的基本運算173

5.6.3 採用擴展線性鍊表存儲結構的

廣義表套用舉例175

5.7 廣義表套用舉例：導師-本科生

制管理178

5.8 小結183

習題184

第6章 樹188

6.1 樹188

6.1.1 樹的定義188

6.1.2 樹的邏輯表示189

6.1.3 樹的抽象數據類型190

6.2 二叉樹191

6.2.1 二叉樹的定義191

6.2.2 二叉樹的性質193

6.2.3 二叉樹的抽象數據類型195

6.2.4 二叉樹的存儲表示與實現196

6.3 二叉樹的遍歷201

6.3.1 二叉樹遍歷的定義202

6.3.2 二叉樹的先序遍歷202

6.3.3 二叉樹的中序遍歷203

6.3.4 二叉樹的後序遍歷205

6.4 二叉樹的線索化207

6.4.1 二叉樹的線索化定義207

6.4.2 二叉樹的線索化實現209

6.4.3 線索二叉樹的遍歷210

6.4.4 線索二叉樹套用舉例212

6.5 樹、森林與二叉樹215

6.5.1 樹的存儲結構215

6.5.2 樹轉換為二叉樹217

6.5.3 森林轉換為二叉樹219

6.5.4 二叉樹轉換為樹和森林219

6.5.5 樹和森林的遍歷220

6.6 綜合套用舉例：哈夫曼樹221

6.6.1 哈夫曼樹的定義221

6.6.2 哈夫曼編碼222

6.6.3 哈夫曼編碼算法的實現223

6.7 小結226

習題227

第7章 圖232

7.1 圖的定義與相關概念232

7.1.1 圖的定義232

7.1.2 圖的相關概念233

7.1.3 圖的抽象數據類型235

7.2 圖的存儲結構236

7.2.1 鄰接矩陣表示法236

7.2.2 鄰接表表示法240

7.2.3 十字鍊表表示法244

7.2.4 多重表表示法245

7.3 圖的遍歷246

7.3.1 圖的深度優先遍歷246

7.3.2 圖的廣度優先遍歷249

7.4 圖的連通性問題251

7.4.1 無向圖的連通分量與生成樹251

7.4.2 最小生成樹252

7.5 有向無環圖257

7.5.1 AOV網與拓撲排序257

7.5.2 AOE網與關鍵路徑260

7.6 最短路徑264

7.6.1 從某個頂點到其餘各頂點的

最短路徑264

7.6.2 每一對頂點之間的最短路徑271

7.7 圖的套用舉例275

7.7.1 距離某個頂點的最短路徑長度為

k的所有頂點275

7.7.2 求圖中頂點u到頂點v的簡單

路徑277

7.8 圖的綜合套用：鐵路交通線路

規劃279

7.9 小結286

習題287

第8章 查找291

8.1 查找的基本概念291

8.2 靜態查找292

8.2.1 順序表的查找292

8.2.2 有序順序表的查找293

8.2.3 索引順序表的查找295

8.3 動態查找296

8.3.1 二叉排序樹296

8.3.2* 平衡二叉樹303

8.4* B-樹與B+樹311

8.4.1 B-樹311

8.4.2 B+樹319

8.5 哈希表320

8.5.1 哈希表的定義320

8.5.2 哈希函式的構造方法321

8.5.3 處理衝突的方法322

8.5.4 哈希表查找與分析324

8.5.5 哈希表套用舉例324

8.6 小結328

習題329

第9章 排序332

9.1 排序的基本概念332

9.2 插入排序333

9.2.1 直接插入排序333

9.2.2 折半插入排序335

9.2.3 希爾排序336

9.2.4 插入排序套用舉例338

9.3 選擇排序339

9.3.1 簡單選擇排序339

9.3.2 堆排序340

9.4 交換排序346

9.4.1 冒泡排序346

9.4.2 快速排序347

9.4.3 交換排序套用舉例350

9.5 歸併排序353

9.6 基數排序354

9.6.1 基數排序算法355

9.6.2 基數排序套用舉例357

9.7 小結360

習題361

參考文獻364