第1章　緒論　1

　1.1 數(shù)據(jù)結(jié)構(gòu)概述　2

1.1.1　什么是數(shù)據(jù)結(jié)構(gòu)　2

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

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

　1.2 數(shù)據(jù)類型概述　6

1.2.1　數(shù)據(jù)類型　6

1.2.2　抽象數(shù)據(jù)類型　7

　1.3 算法概述　9

1.3.1　什么是算法　9

1.3.2　算法的時(shí)間復(fù)雜度　9

1.3.3　算法的空間復(fù)雜度　12

　1.4 本章小結(jié)　13

　1.5 上機(jī)實(shí)驗(yàn)　14

1.5.1　基礎(chǔ)實(shí)驗(yàn)　14

1.5.2　綜合實(shí)驗(yàn)　15

　習(xí)題　16

第2章　線性表　18

　2.1 線性表簡(jiǎn)介　19

　2.2 順序表　21

2.2.1　順序表的概念　21

2.2.2　順序表的操作　22

2.2.3　順序表的應(yīng)用　29

　2.3 鏈表　31

2.3.1　鏈表的基本概念　32

2.3.2　單鏈表　35

2.3.3　循環(huán)單鏈表　45

2.3.4　雙鏈表　50

2.3.5　循環(huán)雙鏈表　58

2.3.6　鏈表的應(yīng)用　64

　2.4 本章小結(jié)　78

　2.5 上機(jī)實(shí)驗(yàn)　79

2.5.1　基礎(chǔ)實(shí)驗(yàn)　79

2.5.2　綜合實(shí)驗(yàn)　81

　習(xí)題　85

第3章　棧、隊(duì)列和遞歸　87

　3.1 棧　88

3.1.1　棧的基本概念　88

3.1.2　棧的順序存儲(chǔ)　89

3.1.3　棧的鏈?zhǔn)酱鎯?chǔ)　97

3.1.4　棧的典型應(yīng)用　107

　3.2 隊(duì)列　112

3.2.1　隊(duì)列的基本概念　112

3.2.2　隊(duì)列的順序存儲(chǔ)　113

3.2.3　隊(duì)列的鏈?zhǔn)酱鎯?chǔ)　125

3.2.4　隊(duì)列的典型應(yīng)用　136

　3.3 遞歸　139

3.3.1　什么是遞歸　139

3.3.2　遞歸算法的設(shè)計(jì)和實(shí)現(xiàn)　141

3.3.3　遞歸到非遞歸的轉(zhuǎn)換　146

　3.4 本章小結(jié)　154

　3.5 上機(jī)實(shí)驗(yàn)　154

3.5.1　基礎(chǔ)實(shí)驗(yàn)　154

3.5.2　綜合實(shí)驗(yàn)　156

　習(xí)題　158

第4章　串、數(shù)組和廣義表　160

　4.1 串　161

4.1.1　串的基本概念　161

4.1.2　串的順序存儲(chǔ)及運(yùn)算　163

4.1.3　串的鏈?zhǔn)酱鎯?chǔ)及運(yùn)算　167

4.1.4　串的模式匹配　173

　4.2 數(shù)組和特殊矩陣　185

4.2.1　數(shù)組的基本概念　185

4.2.2　數(shù)組的順序存儲(chǔ)　187

4.2.3　特殊矩陣　188

　4.3 廣義表　192

4.3.1　廣義表的基本概念　192

4.3.2　廣義表的存儲(chǔ)　194

4.3.3　廣義表的操作　196

　4.4 本章小結(jié)　202

　4.5 上機(jī)實(shí)驗(yàn)　202

4.5.1　基礎(chǔ)實(shí)驗(yàn)　202

4.5.2　綜合實(shí)驗(yàn)　204

　習(xí)題　206

第5章　樹(shù)、二叉樹(shù)和森林　208

　5.1 樹(shù)　209

5.1.1　樹(shù)的基本概念　209

5.1.2　樹(shù)的存儲(chǔ)　215

5.1.3　樹(shù)的遍歷　219

　5.2 二叉樹(shù)　220

5.2.1　二叉樹(shù)的基本概念　220

5.2.2　二叉樹(shù)的存儲(chǔ)　225

5.2.3　二叉樹(shù)的遍歷　228

5.2.4　線索二叉樹(shù)　242

5.2.5　二叉樹(shù)的典型應(yīng)用　247

　5.3 森林　253

5.3.1　森林的定義　253

5.3.2　樹(shù)、森林和二叉樹(shù)　254

5.3.3　樹(shù)或森林轉(zhuǎn)換為二叉樹(shù)　255

5.3.4　二叉樹(shù)轉(zhuǎn)換為森林或樹(shù)　256

　5.4 哈夫曼樹(shù)　257

5.4.1　哈夫曼樹(shù)的基本概念　258

5.4.2　哈夫曼算法及實(shí)現(xiàn)　259

5.4.3　哈夫曼編碼及應(yīng)用　262

　5.5 本章小結(jié)　266

　5.6 上機(jī)實(shí)驗(yàn)　267

5.6.1　基礎(chǔ)實(shí)驗(yàn)　267

5.6.2　綜合實(shí)驗(yàn)　269

　習(xí)題　271

第6章　圖　273

　6.1 圖的基本概念　274

6.1.1　圖的定義　274

6.1.2　圖的相關(guān)術(shù)語(yǔ)　275

6.1.3　圖的性質(zhì)　280

　6.2 圖的存儲(chǔ)結(jié)構(gòu)　280

6.2.1　數(shù)組表示法　280

6.2.2　鄰接表表示法　282

6.2.3　十字鏈表表示法　285

6.2.4　鄰接多重表表示法　287

　6.3 圖的遍歷　289

6.3.1　深度優(yōu)先遍歷　289

6.3.2　廣度優(yōu)先遍歷　291

　6.4 圖的最小生成樹(shù)　293

6.4.1　基本概念　293

6.4.2　Prim算法　294

6.4.3　Kruskal算法　296

6.4.4　應(yīng)用實(shí)例　298

　6.5 最短路徑　300

6.5.1　基本概念　300

6.5.2　從某源點(diǎn)到其余各頂點(diǎn)的最短

路徑　300

6.5.3　每一對(duì)頂點(diǎn)之間的最短路徑　303

6.5.4　應(yīng)用實(shí)例　305

　6.6 拓?fù)渑判颉?06

6.6.1　基本概念　306

6.6.2　拓?fù)渑判虻膶?shí)現(xiàn)　307

　6.7 關(guān)鍵路徑　310

6.7.1　基本概念　310

6.7.2　求關(guān)鍵路徑的算法　311

　6.8 本章小結(jié)　316

　6.9 上機(jī)實(shí)驗(yàn)　317

6.9.1　基礎(chǔ)實(shí)驗(yàn)　317

6.9.2　綜合實(shí)驗(yàn)　319

　習(xí)題　322

第7章　查找　326

　7.1 查找的基本概念　327

7.1.1　相關(guān)術(shù)語(yǔ)　327

7.1.2　查找表的基本操作　328

　7.2 基于靜態(tài)查找表的查找　329

7.2.1　順序查找　330

7.2.2　折半查找　332

7.2.3　索引查找　336

　7.3 基于動(dòng)態(tài)查找表的查找　338

7.3.1　樹(shù)查找　338

7.3.2　哈希表查找　369

　7.4 本章小結(jié)　384

　7.5 上機(jī)實(shí)驗(yàn)　385

7.5.1　基礎(chǔ)實(shí)驗(yàn)　385

7.5.2　綜合實(shí)驗(yàn)　386

　習(xí)題　387

第8章　內(nèi)排序　389

　8.1 排序的基本概念　390

　8.2 插入排序　393

8.2.1　直接插入排序　393

8.2.2　折半插入排序　396

8.2.3　希爾排序　398

8.2.4　表插入排序　401

　8.3 交換排序　403

8.3.1　冒泡排序　403

8.3.2　快速排序　407

　8.4 選擇排序　410

8.4.1　簡(jiǎn)單選擇排序　410

8.4.2　樹(shù)形選擇排序　412

8.4.3　堆排序　414

　8.5 歸并排序　418

　8.6 基數(shù)排序　421

8.6.1　多關(guān)鍵字排序　421

8.6.2　鏈?zhǔn)交鶖?shù)排序　423

　8.7 本章小結(jié)　427

　8.8 上機(jī)實(shí)驗(yàn)　429

8.8.1　基礎(chǔ)實(shí)驗(yàn)　429

8.8.2　綜合實(shí)驗(yàn)　431

　習(xí)題　434

第9章　外排序　436

　9.1 外排序概述　437

9.1.1　典型的外存儲(chǔ)設(shè)備　437

9.1.2　外排序的基本方法　438

　9.2 磁盤(pán)排序　439

9.2.1　磁盤(pán)排序過(guò)程　439

9.2.2　多路平衡歸并　441

9.2.3　初始?xì)w并段的生成　444

9.2.4　最佳歸并樹(shù)　446

　9.3 本章小結(jié)　449

　9.4 上機(jī)實(shí)驗(yàn)　449

9.4.1　基礎(chǔ)實(shí)驗(yàn)　449

9.4.2　綜合實(shí)驗(yàn)　449

　習(xí)題　451