數據結構

本教材是《21世紀計算機專業大專系列教材》之一。全書共分9章，第1章綜述數據、數據結構、算法描述、算法分析，以及數據結構與其他課程之間的關係等。第2章至第7章介紹了基本的數據結構，如線性表、棧、隊列、串、數組、廣義表、材、二叉樹及圖等，分別討論了數據的邏輯結構和存儲結構，以及相應運算的算法。第8章和第9章為查找和排序，介紹了常用的幾種查找方法和內部排序方法。教材中使用類C語言作為算法描述語言，且所有算法都可以在任何一種C語言的開發環境中實現。在隨書的配套光盤中可以看到這些算法的C語言程序。

本書中所介紹的數據結構概念清楚，內容豐富。為了有助於學生加深對基礎理論知識的理解，培養實際應用的能力，各章（除第1章外）都配有與該章內容相關的操作應用舉例，且配有大量習題。本書可作為高等院校計算機專業大專數據結構課程的教材，也可作為非計算機專業本科生的教材。 ^[1] 

第1章緒論1

1.1數據結構概述1

1.2數據結構的發展概況2

1.3數據結構與其他課程的關係4

1.4基本概念5

1.5算法描述及分析7

1.5.1算法的重要特性7

1.5.2算法的描述方法8

1.5.3算法的設計要求10

1.5.4算法效率的度量10

1.5.5算法的空間需求12

習題12

第2章線性表15

2.1線性表的邏輯結構15

2.1.1線性表的定義15

2.1.2線性表的基本操作16

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

2.2.1線性表的順序存儲表示17

2.2.2基本操作在順序表上的實現18

2.2.3線性表順序存儲結構小結22

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

2.3.1線性表的鏈式存儲表示24

2.3.2基本操作在單鏈表上的實現24

2.3.3循環鏈表28

2.3.4雙向鏈表28

2.3.5線性錶鏈式存儲結構小結31

2.4線性表的兩種存儲結構比較31

2.5線性表操作應用舉例32

習題37

第3章棧和隊列40

3.1棧40

3.1.1棧的邏輯結構40

3.1.2棧的順序存儲結構41

3.1.3棧的鏈式存儲結構44

3.2隊列46

3.2.1隊列的邏輯結構46

3.2.2隊列的順序存儲結構47

3.2.3隊列的鏈式存儲結構50

3.3棧和隊列操作應用舉例53

習題58

第4章串60

4.1串的邏輯結構60

4.1.1串的定義60

4.1.2串的基本操作61

4.2串的存儲結構62

4.2.1定長順序存儲結構62

4.2.2堆分配存儲結構65

4.2.3塊鏈存儲結構67

4.3串操作應用舉例69

習題76

第5章數組與廣義表78

5.1數組的邏輯結構78

5.1.1數組的定義78

5.1.2數組的基本操作79

5.2數組的順序存儲結構79

5.3矩陣的壓縮存儲83

5.3.1特殊矩陣的壓縮存儲83

5.3.2稀疏矩陣的邏輯結構85

5.3.3稀疏矩陣的存儲結構86

5.4廣義表91

5.4.1廣義表的邏輯結構91

5.4.2廣義表的存儲結構93

5.5數組與廣義表操作應用舉例94

習題96

第6章樹與二叉樹98

6.1樹98

6.1.1樹的邏輯結構98

6.1.2樹的存儲結構101

6.2二叉樹104

6.2.1二叉樹的邏輯結構104

6.2.2二叉樹的基本性質107

6.2.3二叉樹的存儲結構109

6.3遍歷二叉樹113

6.3.1遍歷二叉樹的操作定義113

6.3.2遍歷二叉樹的遞歸算法114

6.3.3遍歷二叉樹的非遞歸算法115

6.3.4建立二叉樹的算法121

6.4二叉線索樹122

6.4.1二叉線索樹的引出122

6.4.2二叉線索樹的定義123

6.4.3二叉線索樹的存儲結構124

6.4.4二叉線索樹的操作125

6.5樹和森林與二叉樹的轉換129

6.5.1樹與二叉樹的轉換129

6.5.2森林與二叉樹的轉換132

6.5.3樹和森林的遍歷133

6.6赫夫曼樹及其應用135

6.6.1基本概念136

6.6.2赫夫曼算法137

6.6.3赫夫曼編碼137

6.6.4赫夫曼樹和赫夫曼編碼的存儲表示139

6.6.5赫夫曼編碼的算法139

6.6.6示例140

6.7樹與二叉樹操作應用舉例142

習題146

第7章圖149

7.1圖的邏輯結構149

7.1.1圖的定義149

7.1.2圖的基本操作149

7.1.3圖的基本概念151

7.2圖的存儲結構154

7.2.1鄰接矩陣表示法154

7.2.2鄰接表表示法157

7.2.3十字鏈表表示法160

7.2.4鄰接多重表表示法162

7.3圖的遍歷164

7.3.1深度優先搜索164

7.3.2廣度優先搜索165

7.4最小生成樹167

7.4.1生成樹167

7.4.2最小生成樹168

7.5最短路徑173

7.5.1求某個源點到其他頂點的最短路徑174

7.5.2求每一對頂點之間的最短路徑177

7.6拓撲排序179

7.6.1AOV網179

7.6.2拓撲排序180

7.7關鍵路徑183

7.7.1AOE網183

7.7.2關鍵路徑的概念184

7.7.3關鍵路徑的算法184

7.8圖操作應用舉例187

習題191 ^[2]