數據結構與算法

目錄

第1章概論1

1.1什麼是數據結構1

1.2數據結構的基本概念和術語3

1.3抽象數據類型及其表示與實現6

1.4算法和算法分析8

1.4.1什麼是算法8

1.4.2算法的設計要求9

1.4.3算法時間性能分析9

1.4.4算法空間性能分析14

1.5類C語言描述15

小結17

習題18

實驗題20第2章線性表23

2.1線性表的類型定義23

2.1.1線性表的定義23

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

2.2線性表的順序存儲結構及實現25

2.2.1線性表的順序表示25

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

2.2.3順序表的算法舉例31

2.3線性表的鏈式存儲結構及實現31

2.3.1單鏈表的表示31

2.3.2單鏈表操作的實現33

2.3.3鏈表的算法舉例39

2.3.4循環鏈表402.3.5雙向鏈表41

2.3.6靜態鏈表43

2.4線性表實現方法的比較46

2.5線性表的應用舉例47

2.5.1一元多項式的表示47

2.5.2一元多項式的存儲47

2.5.3一元多項式的運算48

2.6算法舉例50

小結53

習題53

實驗題57數據結構與算法目錄第3章棧和隊列61

3.1棧61

3.1.1棧的定義61

3.1.2棧的順序存儲結構和實現62

3.1.3棧的鏈式存儲結構和實現65

3.2棧的典型應用67

3.3棧與遞歸71

3.3.1遞歸的實現71

3.3.2遞歸算法舉例72

3.4隊列74

3.4.1隊列的定義74

3.4.2隊列的順序存儲結構及實現74

3.4.3隊列的鏈式存儲結構及實現77

3.5棧和隊列的應用舉例79

3.6算法舉例84

小結87

習題88

實驗題92第4章串和數組95

4.1串的定義95

4.2串的存儲結構96

4.2.1串的順序存儲結構96

4.2.2串的鏈式存儲結構96

4.3串的模式匹配97

4.3.1簡單模式匹配算法97

4.3.2KMP算法99

4.4串的應用舉例102

4.5數組的定義103

4.6數組的順序存儲結構104

4.7矩陣的壓縮存儲106

4.7.1特殊矩陣106

4.7.2稀疏矩陣107

4.8算法舉例113

小結115

習題115

實驗題118第5章樹和二叉樹121

5.1樹的邏輯結構121

5.1.1樹的定義和術語121

5.1.2樹的邏輯表示方法123

5.2樹的存儲結構124

5.3二叉樹的邏輯結構127

5.3.1二叉樹的定義127

5.3.2二叉樹的性質128

5.4二叉樹的存儲結構130

5.4.1二叉樹的順序存儲結構130

5.4.2二叉樹的鏈式存儲結構131

5.4.3基於二叉鏈表的二叉樹遍歷131

5.4.4線索鏈表和線索二叉樹139

5.5樹、森林與二叉樹的相互轉換143

5.5.1樹與二叉樹的相互轉換143

5.5.2森林與二叉樹的相互轉換144

5.5.3樹和森林的遍歷146

5.6哈夫曼樹及其應用147

5.6.1哈夫曼樹（最優二叉樹）147

5.6.2哈夫曼編碼150

5.7二叉樹的應用舉例153

5.8算法舉例156

小結159

習題159

實驗題164第6章圖169

6.1圖的定義和術語169

6.2圖的存儲結構173

6.2.1鄰接矩陣173

6.2.2鄰接表175

6.2.3十字鏈表177

6.2.4鄰接多重表178

6.3圖的遍歷179

6.3.1深度優先遍歷180

6.3.2廣度優先遍歷181

6.3.3圖的遍歷與圖的連通性183

6.4生成樹和最小生成樹183

6.4.1生成樹183

6.4.2最小生成樹184

6.5最短路徑189

6.5.1單源點最短路徑189

6.5.2任意兩頂點之間的最短路徑192

6.6有向無環圖及其應用194

6.6.1拓撲排序194

6.6.2關鍵路徑197

6.7圖的應用舉例202

6.8算法舉例205

小結208

習題209

實驗題212第7章查找217

7.1集合和查找217

7.2靜態查找表上的查找218

7.2.1順序查找218

7.2.2折半查找220

7.2.3分塊查找223

7.3動態查找表上的查找225

7.3.1二叉排序樹225

7.3.2平衡二叉樹230

7.3.3B樹239

7.4哈希表上的查找244

7.4.1哈希表的定義244

7.4.2構造哈希函數的方法245

7.4.3解決沖突的方法246

7.4.4哈希表的查找性能分析250

7.4.5開放定址法與鏈地址法的比較251

7.5算法舉例252

小結255

習題255

實驗題258第8章排序263

8.1概述263

8.2插入排序265

8.2.1直接插入排序265

8.2.2折半插入排序267

8.2.3希爾排序268

8.3交換排序269

8.3.1起泡排序269

8.3.2快速排序271

8.4選擇排序274

8.4.1直接選擇排序274

8.4.2堆排序275

8.5歸並排序279

8.6分配排序281

8.7各種內部排序方法的比較285

8.8外部排序286

8.8.1文件管理286

8.8.2外部排序的方法287

8.8.3多路平衡歸並排序288

8.8.4最佳歸並樹290

8.9算法舉例292

小結294

習題294

實驗題297參考文獻300