數據結構：C語言描述

《數據結構：C語言描述》是殷人昆編寫的，2011年6月1日在機械工業出版社出版。

基本介紹

• 書名：數據結構：C語言描述
• 作者：殷人昆
• ISBN：9787111349716
• 定價：35.00元
• 出版社：機械工業出版社
• 出版時間： 2011年6月1日
• 裝幀：平裝
• 開本：16

內容簡介

第1章介紹數據結構的地位和主要知識點，數據結構和算法的基本概念，算法分析的簡單方法，以及用C語言編程的要點；第2～7章對應考試大綱的6個知識單元，包括線性表，棧、佇列和數組，樹與二叉樹，圖，查找，排序。《數據結構:C語言描述》融入了作者三十多年的教學經驗和考試輔導體會，合理安排相關知識點，對學生容易忽略的地方和隱含在所討論問題之後的內容給出適當的提示。

《數據結構:C語言描述》既可作為普通高校計算機科學與技術及相關專業本科生學習數據結構課程的教材，也可作為計算機專業考研的輔導教材或其他專業計算機考試的複習教材，還可作為計算機系統開發人員的學習資料。

作者簡介

殷人昆，清華大學計算機系教授，中國科學院研究生院工程教育部兼職教授。1985年赴日本東京理科大學做訪問學者，研究方向為軟體工程過程的質量管理和軟體產品的質量評價。主要負責清華大學計算機系“數據結構”、“軟體工程”的本科課程教學工作和“軟體工程技術與設計”、“軟體項目管理”的研究生課程教學工作。主講的“數據結構”課程被評為清華大學精品課程。曾與人合作或單獨編寫教材十餘本。曾在核心刊物和專業會議發表論文多篇。

圖書目錄

出版者的話

編委會

叢書序言

前言

教學安排建議

第1章 緒論1

1.1 數據結構的概念及分類1

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

1.1.2 與數據結構相關的基本術語2

1.1.3 數據結構的分類4

1.1.4 數據結構的存儲結構6

1.1.5 定義在數據結構上的操作6

1.2 使用c語言描述數據結構6

1.2.1 數據類型7

1.2.2 算法的控制結構7

1.2.3 算法的函式結構8

1.2.4 動態存儲分配10

1.2.5 邏輯和關係運算的約定11

1.2.6 輸入與輸出11

1.3 算法和算法設計12

1.3.1 算法的定義和特性12

1.3.2 算法的設計步驟12

1.3.3 算法設計的基本方法13

1.4 算法分析與度量16

1.4.1 算法的評價標準16

1.4.2 算法的時間和空間複雜度度量16

1.4.3 算法的漸近分析19

小結21

習題21

第2章 線性表23

2.1 線性表的定義及操作23

2.1.1 線性表的定義和特點23

2.1.2 線性表的主要操作24

2.2 順序表25

2.2.1 順序表的定義和特點25

2.2.2 順序表的結構定義25

2.2.3 順序表主要操作的實現26

2.2.4 順序表主要操作的性能分析28

2.2.5 順序表的套用舉例29

2.3 單鍊表30

2.3.1 單鍊表的定義和特點30

2.3.2 單鍊表的結構定義31

2.3.3 單鍊表中的插入與刪除31

2.3.4 帶頭結點的單鍊表33

2.3.5 單鍊表主要操作的性能分析35

2.3.6 單鍊表的順序訪問與尾遞歸36

2.3.7 單鍊表的套用舉例38

2.4 順序表與線性鍊表的比較40

2.5 線性鍊表的其他變形41

2.5.1 循環鍊表41

2.5.2 雙向鍊表44

2.5.3 靜態鍊表46

2.6 線性表的套用：字元串47

2.6.1 字元串的概念47

2.6.2 字元串的初始化和賦值48

2.6.3 c語言中有關字元串的庫函式48

2.6.4 自定義字元串的存儲表示50

2.7 單鍊表的套用：一元多項式及其運算53

2.7.1 一元多項式的表示53

2.7.2 多項式的結構定義54

2.7.3 多項式的加法55

2.7.4 多項式的乘法56

小結58

習題58

第3章 棧、佇列和數組61

3.1 棧61

3.1.1 棧的概念61

3.1.2 順序棧62

3.1.3 鏈式棧66

3.1.4 棧的混洗68

3.2 佇列69

3.2.1 佇列的概念69

3.2.2 循環佇列70

3.2.3 鏈式佇列73

3.3 棧的套用75

3.3.1 數制轉換75

3.3.2 括弧匹配75

3.3.3 表達式的計算與優先權處理76

3.3.4 棧與遞歸的實現80

3.4 佇列的套用83

3.4.1 列印楊輝三角形與逐行處理83

3.4.2 電路布線與兩點間的最短路徑84

3.5 數組86

3.5.1 一維數組86

3.5.2 多維數組87

3.5.3 數組的套用舉例89

3.6 在算法設計中使用遞歸89

3.6.1 漢諾塔問題與分治法90

3.6.2 迷宮問題與回溯法92

3.6.3 計算組合數與動態規劃95

3.7 特殊矩陣96

3.7.1 對稱矩陣的壓縮存儲96

3.7.2 三對角線矩陣的壓縮存儲97

3.7.3 稀疏矩陣的壓縮存儲98

3.8 雙端佇列100

3.8.1 雙端佇列的概念100

3.8.2 雙端佇列的主要操作101

3.8.3 雙端佇列的順序存儲表示101

3.8.4 雙端佇列的連結存儲表示103

小結103

習題104

第4章 樹與二叉樹108

4.1 樹的基本概念108

4.1.1 樹的定義和術語108

4.1.2 樹的基本操作110

4.2 二叉樹111

4.2.1 二叉樹的概念111

4.2.2 二叉樹的性質112

4.2.3 二叉樹的主要操作113

4.3 二叉樹的存儲表示114

4.3.1 二叉樹的順序存儲表示114

4.3.2 二叉樹的鍊表存儲表示115

4.4 二叉樹的遍歷116

4.4.1 二叉樹遍歷的遞歸算法116

4.4.2 遞歸遍歷算法的套用舉例117

4.4.3 二叉樹遍歷的非遞歸算法120

4.4.4 非遞歸遍歷算法的套用舉例123

4.4.5 二叉樹的計數125

4.5 線索二叉樹127

4.5.1 線索二叉樹的概念127

4.5.2 線索二叉樹的種類128

4.5.3 中序線索二叉樹的建立和遍歷129

4.5.4 前序與後序線索二叉樹131

4.6 樹與森林132

4.6.1 樹的存儲表示132

4.6.2 森林與二叉樹的轉換134

4.6.3 樹與森林的深度優先遍歷135

4.6.4 樹與森林的廣度優先遍歷137

4.6.5 樹遍歷算法的套用舉例138

4.7 二叉樹的套用：二叉排序樹138

4.7.1 二叉排序樹的概念138

4.7.2 二叉排序樹的查找139

4.7.3 二叉排序樹的插入140

4.7.4 二叉排序樹的刪除141

4.7.5 二叉排序樹的性能分析142

4.8 二叉樹的套用：平衡二叉樹144

4.8.1 平衡二叉樹的概念144

4.8.2 平衡化旋轉144

4.8.3 平衡二叉樹的插入146

4.8.4 平衡二叉樹的刪除147

4.8.5 平衡二叉樹的性能分析149

4.9 二叉樹的套用：huffman樹150

4.9.1 帶權路徑長度的概念150

4.9.2 huffman樹與huffman算法151

4.9.3 huffman樹的套用：最優判定樹153

4.9.4 huffman樹的套用：huffman編碼154

4.10 二叉樹的套用：堆155

4.10.1 小根堆和大根堆155

4.10.2 堆的建立156

4.10.3 堆的插入158

4.10.4 堆的刪除158

4.11 樹的套用：八皇后問題與樹的剪枝159

4.11.1 八皇后問題的提出159

4.11.2 八皇后問題的狀態樹160

4.11.3 八皇后問題算法161

小結162

習題162

第5章 圖168

5.1 圖的基本概念168

5.1.1 與圖有關的概念168

5.1.2 圖的基本操作170

5.2 圖的存儲結構171

5.2.1 圖的鄰接矩陣表示171

5.2.2 圖的鄰接表表示175

5.2.3 鄰接矩陣表示與鄰接表表示

的比較178

5.2.4 圖的鄰接多重表表示179

5.3 圖的遍歷180

5.3.1 深度優先搜尋181

5.3.2 廣度優先搜尋182

5.3.3 連通分量183

5.3.4 重連通圖184

5.3.5 歐拉迴路與一筆畫問題186

5.3.6 有向圖的強連通分量187

5.4 最小生成樹188

5.4.1 最小生成樹求解和貪婪法188

5.4.2 kruskal算法190

5.4.3 prim算法193

5.5 最短路徑194

5.5.1 非負權重的單源最短路徑194

5.5.2 所有頂點之間的最短路徑197

5.5.3 無權重的最短路徑199

5.6 用頂點表示活動的網路（aov網路）200

5.7 用邊表示活動的網路（aoe網路）204

小結207

習題208

第6章 查找212

6.1 查找的基本概念與性能分析212

6.1.1 查找的概念212

6.1.2 查找算法的性能分析213

6.2 順序查找法213

6.2.1 順序表上的順序查找算法213

6.2.2 線性鍊表上的順序查找算法216

6.3 折半查找法216

6.3.1 一般的折半查找法216

6.3.2 擬最優查找樹：折半查找的

改進方法219

6.3.3 斐波那契查找：折半查找的

變形222

6.3.4 插值查找：折半查找的變形223

6.4 b樹224

6.4.1 索引順序表與分塊查找224

6.4.2 多級索引結構與m叉查找樹225

6.4.3 b樹的概念226

6.4.4 b樹上的查找227

6.4.5 b樹上的插入228

6.4.6 b樹上的刪除229

6.4.7 b+樹231

6.5 散列表及其查找233

6.5.1 散列的概念233

6.5.2 常見的散列函式234

6.5.3 解決衝突的開地址法236

6.5.4 解決衝突的鏈地址法242

6.5.5 散列法分析244

小結245

習題245

第7章 排序250

7.1 排序的概念與算法性能250

7.1.1 排序的概念250

7.1.2 排序算法的性能251

7.1.3 數據表和靜態鍊表的結構定義251

7.2 幾種簡單的排序方法253

7.2.1 直接插入排序253

7.2.2 基於鍊表的直接插入排序254

7.2.3 折半插入排序255

7.2.4 起泡排序256

7.2.5 簡單選擇排序258

7.3 希爾排序259

7.3.1 希爾排序的設計思路259

7.3.2 希爾排序的算法實現260

7.4 快速排序261

7.4.1 快速排序的設計思路261

7.4.2 快速排序的算法描述262

7.4.3 快速排序的算法分析262

7.4.4 快速排序的改進算法263

7.5 堆排序264

7.5.1 大根堆264

7.5.2 堆排序的算法265

7.5.3 堆排序的算法分析267

7.6 歸併排序267

7.6.1 兩路歸併267

7.6.2 遞歸的歸併排序算法268

7.6.3 疊代的歸併排序算法269

7.6.4 基於鍊表的歸併排序算法271

7.7 基數排序272

7.7.1 基數排序的概念272

7.7.2 msd基數排序273

7.7.3 lsd基數排序274

7.8 內排序算法的分析與比較276

7.8.1 排序方法的下界276

7.8.2 各種內排序方法的比較279

7.8.3 鍊表排序結果的重排280

小結282

習題283

附錄一 2009～2011年全國考研計算機學科聯考專業基礎綜合考試數據結構部分試題解析288

附錄二 大作業要求及樣例303

參考文獻308