第 1章　緒論　1

1.1　數(shù)據(jù)結(jié)構(gòu)的定義　2

1.1.1　數(shù)據(jù)的邏輯結(jié)構(gòu)　2

1.1.2　基本操作　2

1.1.3　抽象數(shù)據(jù)類型　3

1.1.4　數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)　3

1.1.5　基本操作的實(shí)現(xiàn)　3

1.1.6　典型應(yīng)用　4

　1.2 數(shù)據(jù)結(jié)構(gòu)的C語(yǔ)言實(shí)現(xiàn)　4

　1.3 算法及算法分析　4

1.3.1　算法及其要求　4

1.3.2　時(shí)間復(fù)雜度的度量　5

1.3.3　空間復(fù)雜度的度量　7

　1.4 小結(jié)　7

　1.5 習(xí)題　8

第　2章 線性表　9

　2.1 線性表的定義及ADT　10

　2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)　11

2.2.1　順序表　11

2.2.2　順序表基本操作的實(shí)現(xiàn)　12

2.3　線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)　17

2.3.1　單鏈表　18

2.3.2　單鏈表基本操作的實(shí)現(xiàn)　19

2.3.3　單向循環(huán)鏈表　24

2.3.4　雙鏈表、雙向循環(huán)鏈表　25

2.4　線性表的應(yīng)用　27

2.4.1　一元多項(xiàng)式的加法　27

2.4.2　字符串的存儲(chǔ)和實(shí)現(xiàn)　32

2.4.3　稀疏矩陣　42

2.5　小結(jié)　43

2.6　習(xí)題　43

第3章　棧和隊(duì)列　45

　3.1 �！�46

3.1.1　棧的定義和抽象數(shù)據(jù)類型　46

3.1.2　棧的順序存儲(chǔ)及實(shí)現(xiàn)　47

3.1.3　棧的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn)　51

3.2　棧的應(yīng)用　54

3.2.1　括號(hào)配對(duì)檢查　54

3.2.2　表達(dá)式計(jì)算　55

3.3　隊(duì)列　60

3.3.1　隊(duì)列的定義和抽象數(shù)據(jù)類型　60

3.3.2　隊(duì)列的順序存儲(chǔ)及實(shí)現(xiàn)　61

3.3.3　隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn)　64

3.3.4　優(yōu)先隊(duì)列　67

3.4　小結(jié)　68

3.5　習(xí)題　69

第4章　樹(shù)及二叉樹(shù)　70

4.1　樹(shù)的定義、術(shù)語(yǔ)和結(jié)構(gòu)　71

4.2　二叉樹(shù)　72

4.2.1　二叉樹(shù)的定義　72

4.2.2　二叉樹(shù)的性質(zhì)　74

4.2.3　二叉樹(shù)的存儲(chǔ)和實(shí)現(xiàn)　75

4.3　二叉樹(shù)的遍歷及實(shí)現(xiàn)　81

4.4　最優(yōu)二叉樹(shù)及其應(yīng)用　92

4.4.1　基本概念　92

4.4.2　哈夫曼算法的實(shí)現(xiàn)　94

4.4.3　哈夫曼編碼　96

4.5　等價(jià)類問(wèn)題　99

4.5.1　等價(jià)關(guān)系及等價(jià)類　99

4.5.2　不相交集及其存儲(chǔ)　99

4.5.3　不相交集的基本操作　100

　4.6 樹(shù)和森林　101

4.6.1　孩子兄弟表示法　101

4.6.2　樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換　102

4.6.3　樹(shù)的遍歷　104

4.6.4　森林的遍歷　105

4.7　小結(jié)　106

4.8　習(xí)題　106

第5章　圖　108

5.1　圖的基本概念　109

5.1.1　圖的概念和術(shù)語(yǔ)　109

5.1.2　圖的抽象數(shù)據(jù)類型　111

5.2　圖的存儲(chǔ)表示　112

5.2.1　鄰接矩陣和加權(quán)鄰接矩陣　112

5.2.2　鄰接表　119

5.2.3　多重鄰接表　127

5.2.4　十字鏈表　128

5.3　圖的遍歷和連通性　129

5.3.1　深度優(yōu)先遍歷DFS　129

5.3.2　廣度優(yōu)先遍歷BFS　132

5.3.3　圖的連通性　134

5.4　最小代價(jià)生成樹(shù)　136

5.4.1　普里姆算法　137

5.4.2　克魯斯卡爾算法　140

　5.5 最短路徑問(wèn)題　141

5.5.1　單源最短路徑　141

5.5.2　所有頂點(diǎn)對(duì)之間的最短路徑　145

5.6　AOV網(wǎng)和AOE網(wǎng)　150

5.6.1　拓?fù)渑判颉?50

5.6.2　關(guān)鍵路徑　153

5.7　小結(jié)　163

5.8　習(xí)題　163

第6章　查找　165

6.1　靜態(tài)查找技術(shù)　166

6.1.1　順序查找　166

6.1.2　折半查找　167

6.1.3　插值查找　168

6.2　二叉查找樹(shù)　168

6.2.1　二叉查找樹(shù)的定義　168

6.2.2　基本操作　169

6.2.3　順序統(tǒng)計(jì)　174

6.3　平衡二叉查找樹(shù)（AVL樹(shù)）　175

6.3.1　插入　176

6.3.2　刪除　180

6.3.3　最大高度　181

6.4　紅黑樹(shù)　182

6.4.1　插入操作　183

6.4.2　刪除操作　188

6.5　B樹(shù)和B+樹(shù)　192

6.5.1　B樹(shù)　192

6.5.2　B樹(shù)的查找分析　193

6.5.3　插入操作　194

6.5.4　刪除操作　195

6.5.5　B+樹(shù)　197

6.6　哈希（hash）方法　198

6.6.1　常用的哈希函數(shù)　198

6.6.2　線性探測(cè)法　199

6.6.3　二次探測(cè)法　200

6.6.4　鏈地址法　200

6.7　小結(jié)　200

6.8　習(xí)題　201

第7章　排序　202

7.1　引言　203

7.2　冒泡排序　203

7.3　插入排序　205

7.3.1　簡(jiǎn)單插入排序　205

7.3.2　折半插入排序　206

7.3.3　希爾排序　206

7.4　歸并排序　208

7.5　快速排序　213

7.6　選擇排序和堆排序　216

7.6.1　選擇排序　216

7.6.2　堆排序　218

7.6.3　堆和優(yōu)先隊(duì)列　224

7.7　基數(shù)排序　225

7.7.1　多關(guān)鍵字排序　225

7.7.2　口袋排序法　225

7.8　內(nèi)排序算法的比較　229

7.9　外排序　230

7.9.1　外排序處理過(guò)程　230

7.9.2　2k路歸并　230

7.9.3　初始?xì)w并段　232

7.9.4　最佳歸并樹(shù)　233

7.10　小結(jié)　233

7.11　習(xí)題　234