數據結構（C語言版）

本書系統地介紹了各種常用的數據結構以及查找、排序算法，對每種數據結構以實例作為切入點，詳細闡述了基本概念、邏輯結構、存儲表示、基本操作以及相關的應用，書中每章均有典型案例，並給出了算法實現的思路及完整的C程序。為了便於學生自學和教師教學，每章後均配有大量習題及參考答案。附錄B是各章實訓題目及參考答案。

本書中所有程序均在TC 2.0下調試運行通過。 本書內容精練，通俗易懂，既便於教學，又適合自學。本書既可作為高職高專計算機專業及信息管理專業講授數據結構課程的教材，也可作為從事計算機軟件與應用的工作人員、參加自學考試的考生及社會上數據結構學習者的參考用書。 ^[1] 

第1章緒論 1

1.1引言 1

1.2基本概念與術語 4

1.3抽象數據類型 9

1.3.1數據類型 9

1.3.2抽象數據類型概述 10

1.4算法和算法分析 11

1.4.1算法的基本概念 11

1.4.2算法的時間複雜度 14

1.4.3算法的空間複雜度 16

本章小結 16

習題 17

第2章線性表 19

2.1線性表的定義及其基本操作 19

2.1.1線性表的引例 19

2.1.2線性表的定義 20

2.1.3線性表的基本操作 20

2.2線性表的順序存儲結構 20

2.2.1順序表結構 20

2.2.2順序表的基本操作 22

2.3線性表的鏈式存儲結構 26

2.3.1鏈式存儲結構 26

2.3.2單鏈表上的基本運算 26

2.3.3循環鏈表和雙向鏈表 33

2.4順序表與鏈表的比較 36

2.5線性表的應用 36

本章小結 43

習題 43

第3章棧和隊列 47

3.1棧 47

3.1.1棧的引例 47

3.1.2棧的定義及基本操作 47

3.1.3棧的順序存儲表示和

操作的實現 48

3.1.4棧的鏈式存儲表示和

操作的實現 51

3.2棧的應用 53

3.3隊列 56

3.3.1隊列的引例 56

3.3.2隊列的定義及基本操作 56

3.3.3隊列的順序存儲表示和

操作的實現 57

3.3.4隊列的鏈式存儲表示和

操作的實現 61

3.4隊列的應用 64

本章小結 66

習題 67

第4章串 71

4.1串的定義及基本操作 71

4.1.1串的基本概念 71

4.1.2串的基本操作 72

4.2串的存儲結構 73

4.2.1串的順序存儲結構 73

4.2.2串的堆式存儲 78

4.2.3串的塊鏈式存儲結構 81

4.3串的應用 81

本章小結 84

習題 84

第5章數組 86

5.1數組的定義和運算 86

5.2數組的順序存儲結構 87

5.3矩陣的壓縮存儲結構 89

5.3.1特殊矩陣 89

5.3.2稀疏矩陣 91

5.4廣義表的定義 94

5.5廣義表的存儲結構 95

5.5.1頭尾表示法 95

5.5.2孩子兄弟表示法 96

5.6數組的應用 97

本章小結 101

習題 101

第6章樹和二叉樹 104

6.1樹的概念和基本操作 104

6.1.1樹的引例 104

6.1.2樹的定義和基本術語 104

6.1.3樹的基本操作 106

6.2二叉樹 107

6.2.1二叉樹的定義 107

6.2.2二叉樹的性質 107

6.2.3二叉樹的基本操作 109

6.3二叉樹的存儲結構 110

6.3.1順序存儲結構 110

6.3.2鏈式存儲結構 110

6.4二叉樹的遍歷 112

6.4.1先序遍歷 112

6.4.2中序遍歷 113

6.4.3後序遍歷 113

6.4.4層次遍歷 114

6.5線索二叉樹 115

6.5.1線索二叉樹的概念 115

6.5.2中序線索二叉樹的

構造算法 116

6.5.3線索二叉樹的遍歷 117

6.6哈夫曼樹及其應用 119

6.6.1哈夫曼樹的定義 119

6.6.2構造哈夫曼樹 120

6.6.3哈夫曼樹的應用 122

6.7樹與森林 124

6.7.1樹的存儲結構 124

6.7.2樹、森林與二叉樹的轉換 126

6.8二叉樹的應用 128

本章小結 131

習題 131 ^[1-2]