數據結構（C語言描述）——以項目案例為驅動

目錄

資源下載

第1章緒論1

1.1數據結構的基本概念2

1.2抽象數據類型3

1.2.1抽象數據類型的定義3

1.2.2抽象數據類型的描述4

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

1.3.1邏輯結構8

1.3.2存儲結構9

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

1.4.1算法的定義9

1.4.2算法的特性10

1.4.3算法的描述10

1.5算法分析12

1.5.1算法設計的要求12

1.5.2算法時間復雜度13

1.5.3算法空間復雜度18

1.6數據結構課程的發展歷史19

習題21

第2章線性表22

2.1為什麼要學習線性表23

2.2線性表的概念及運算23

2.2.1線性表的邏輯結構24

2.2.2線性表的抽象數據類型24

2.3線性表的順序表示與實現25

2.3.1線性表的順序存儲25數據結構（C語言描述）——以項目案例為驅動目錄2.3.2順序表的基本運算26

2.3.3基本操作算法分析29

2.3.4順序表的應用舉例30

2.4線性表的鏈式表示與實現34

2.4.1單鏈表的存儲結構35

2.4.2單鏈表上的基本運算36

2.4.3單鏈表應用舉例41

2.4.4循環單鏈表46

2.4.5雙向鏈表49

2.5線性表應用舉例： 一元多項式的表示與相乘52

2.5.1一元多項式的表示52

2.5.2一元多項式相乘53

2.6小結57

習題58

第3章棧與隊列59

3.1如何利用計算機實現算術表達式求值60

3.2棧的表示與實現60

3.2.1棧的定義60

3.2.2棧的抽象數據類型61

3.2.3順序棧61

3.2.4鏈棧64

3.3棧的應用67

3.3.1數制轉換67

3.3.2行編輯程序68

3.3.3算術表達式求值70

3.4棧與遞歸81

3.4.1遞歸81

3.4.2消除遞歸84

3.5隊列的表示與實現87

3.5.1隊列的定義87

3.5.2隊列的抽象數據類型87

3.5.3順序隊列88

3.5.4順序循環隊列89

3.5.5雙端隊列92

3.5.6鏈式隊列92

3.6隊列的應用96

3.6.1隊列在楊輝三角中的應用96

3.6.2隊列在回文中的應用98

3.7小結101

習題101

第4章串、數組與廣義表102

4.1串的定義和抽象數據類型103

4.1.1串的定義103

4.1.2串的抽象數據類型103

4.1.3串的表示與實現105

4.1.4串的模式匹配107

4.2數組117

4.2.1數組的定義118

4.2.2數組的順序表示與實現118

4.2.3特殊矩陣的壓縮存儲123

4.2.4稀疏矩陣的壓縮存儲125

4.2.5稀疏矩陣的應用舉例133

4.3廣義表138

4.3.1廣義表的定義138

4.3.2廣義表的抽象數據類型139

4.3.3廣義表的存儲表示139

4.3.4廣義表的應用舉例141

4.4小結146

習題147

第5章樹和二叉樹148

5.1樹和二叉樹的基本應用149

5.1.1數據編碼149

5.1.2算術表達式求值149

5.1.3堆排序150

5.2樹的定義和抽象數據類型150

5.2.1樹的定義150

5.2.2樹的邏輯表示152

5.2.3樹的抽象數據類型152

5.3二叉樹153

5.3.1二叉樹的定義153

5.3.2二叉樹的性質155

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

5.3.4二叉樹的存儲結構158

5.4二叉樹的遍歷及應用160

5.4.1二叉樹遍歷的定義160

5.4.2二叉樹的先序遍歷160

5.4.3二叉樹的中序遍歷162

5.4.4二叉樹的後序遍歷164

5.4.5二叉樹的應用166

5.5二叉樹的線索化169

5.5.1二叉樹的線索化定義169

5.5.2二叉樹的線索化170

5.5.3線索二叉樹的遍歷172

5.5.4線索二叉樹的應用舉例173

5.6樹、森林與二叉樹176

5.6.1樹的存儲結構177

5.6.2樹轉換為二叉樹179

5.6.3森林轉換為二叉樹180

5.6.4二叉樹轉換為樹和森林181

5.6.5樹和森林的遍歷182

5.7並查集184

5.7.1並查集的定義184

5.7.2並查集的實現184

5.7.3並查集的應用188

5.8二叉樹的綜合應用189

5.8.1哈夫曼樹189

5.8.2算術表達式求值——表達式樹方式實現195

5.9小結200

習題201

第6章圖202

6.1為什麼學習圖203

6.2圖的定義與相關概念204

6.2.1圖的定義204

6.2.2圖的相關概念204

6.2.3圖的抽象數據類型207

6.3圖的存儲結構208

6.3.1鄰接矩陣表示法208

6.3.2鄰接表表示法213

6.3.3十字鏈表217

6.3.4鄰接多重表218

6.4圖的遍歷220

6.4.1圖的深度優先遍歷220

6.4.2圖的廣度優先遍歷223

6.5圖的連通性問題225

6.5.1無向圖的連通分量與生成樹225

6.5.2最小生成樹226

6.6有向無環圖233

6.6.1AOV網與拓撲排序234

6.6.2AOE網與關鍵路徑236

6.7最短路徑241

6.7.1從某個頂點到其他頂點的最短路徑241

6.7.2每對頂點之間的最短路徑248

6.8圖的應用舉例253

6.8.1求距離某個頂點的最短路徑長度為k的所有頂點253

6.8.2求圖中頂點u到頂點v的簡單路徑255

6.9小結258

習題258

第7章查找259

7.1查找的基本概念260

7.2靜態查找260

7.2.1順序表的查找261

7.2.2有序順序表的查找262

7.2.3索引順序表的查找265

7.3動態查找267

7.3.1二叉排序樹267

7.3.2平衡二叉樹274

7.3.3紅黑樹278

7.4B樹與B+樹286

7.4.1B樹286

7.4.2B+樹291

7.5哈希表292

7.5.1哈希表的定義292

7.5.2哈希函數的構造方法293

7.5.3處理沖突的方法294

7.5.4哈希表的查找與分析296

7.5.5哈希表應用舉例297

7.6小結301

習題302

第8章排序303

8.1排序的基本概念304

8.2插入排序305

8.2.1直接插入排序305

8.2.2折半插入排序307

8.2.3希爾排序308

8.2.4插入排序應用舉例309

8.3選擇排序311

8.3.1簡單選擇排序311

8.3.2堆排序313

8.4交換排序319

8.4.1冒泡排序319

8.4.2快速排序321

8.4.3交換排序應用舉例323

8.5歸並排序327

8.6基數排序329

8.6.1基數排序算法329

8.6.2基數排序應用舉例332

8.7外排序335

8.7.1外排序的基本概念335

8.7.2生成初始歸並段336

8.7.3處理歸並段形成有序文件337

8.8小結343

習題344

參考文獻345