數據結構教程（C++版）

吉根林，博士，教授，博士生導師，現任南京師範大學計算機與電子信息學院/人工智能學院教授委員會主任；教育部計算機課程教學指導委員會委員、教育部教育教學審核評估專家；江蘇省“青藍工程”中青年學術帶頭人；全國高等師範院校計算機教育研究會副理事長；中國計算機學會人工智能與模式識別專委會委員、系統軟件專委會委員、計算機教育專委會委員，江蘇省計算機學會常務理事、大數據專家委員會主任；江蘇省人工智能學會監事長；南京師範大學“計算機科學與技術”國家一流專業負責人，《數據結構》國家一流本科課程負責人；承擔國家及省部級科研項目十多項；在國內外學術期刊和國際學術會議發表論文150多篇；獲得江蘇省科學技術獎、江蘇省計算機傑出教育獎；主編教材11部，其中1部被評為國家“十一五”、“十二五”規劃教材、江蘇省“十四五”規劃教材。授權發明專利9件;2009-2022年任南京師範大學計算機學院、計算機與電子信息學院院長/人工智能學院院長。

目錄

第1章緒論1

1.1“數據結構”課程的研究內容1

1.2基本概念及術語2

1.3算法與算法分析5

1.3.1算法5

1.3.2算法分析7

小結9

習題110

上機實驗題111

上機實驗題1指導11第2章線性表13

2.1線性表的基本概念13

2.2線性表的存儲結構14

2.2.1順序存儲結構14

2.2.2鏈式存儲結構15

2.3線性表的操作算法17

2.3.1順序表的操作算法17

2.3.2鏈表的操作算法22

2.4線性表的應用30

2.5順序表和鏈表的綜合比較34

小結34

習題235

上機實驗題235

上機實驗題2指導36第3章棧和隊列41

3.1棧41數據結構教程（C++版）目錄3.1.1棧的基本概念41

3.1.2棧的存儲結構42

3.1.3棧的操作算法43

3.1.4棧的應用46

3.2隊列52

3.2.1隊列的基本概念52

3.2.2隊列的存儲結構52

3.2.3隊列的操作算法54

3.2.4隊列的應用56

小結57

習題357

上機實驗題358

上機實驗題3指導58第4章串61

4.1串的基本概念61

4.2串的存儲結構61

4.2.1串的順序存儲結構61

4.2.2串的鏈式存儲結構62

4.3串的操作算法63

4.3.1串的基本操作算法63

4.3.2串的模式匹配64

4.4串的應用69

小結72

習題473

上機實驗題473

上機實驗題4指導74第5章數組和特殊矩陣77

5.1數組77

5.1.1數組的基本概念77

5.1.2數組的存儲結構78

5.2特殊矩陣的壓縮存儲79

5.2.1對稱矩陣的壓縮存儲79

5.2.2三角矩陣的壓縮存儲80

5.2.3對角矩陣的壓縮存儲80

5.2.4稀疏矩陣的壓縮存儲81

小結86

習題586

上機實驗題586

上機實驗題5指導87第6章廣義表89

6.1廣義表的概念89

6.2廣義表的存儲結構90

6.2.1廣義表中結點的結構90

6.2.2廣義表的存儲結構91

6.3廣義表的操作算法93

6.3.1構造算法93

6.3.2遍歷廣義表94

6.3.3廣義表的復制與析構95

6.3.4廣義表的應用97

小結99

習題699

上機實驗題699

上機實驗題6指導100第7章樹和二叉樹103

7.1樹的概念和性質103

7.1.1樹的定義103

7.1.2樹的基本術語104

7.1.3樹的基本性質106

7.2二叉樹的概念和性質107

7.2.1二叉樹的定義107

7.2.2二叉樹的基本性質108

7.3二叉樹的存儲結構109

7.3.1二叉樹的順序存儲結構109

7.3.2二叉樹的鏈式存儲結構111

7.4二叉樹的遍歷113

7.4.1二叉樹遍歷的概念114

7.4.2二叉樹遍歷算法117

7.4.3二叉樹的構造和析構算法120

7.5二叉樹遍歷算法的應用124

7.5.1計算二叉樹的結點數124

7.5.2計算二叉樹的高度124

7.5.3根據關鍵值查找結點125

7.5.4查找結點的父結點126

7.5.5查找二叉樹中的極值126

7.5.6判斷兩個二叉樹是否相等127

7.6堆結構128

7.6.1順序結構上的二叉樹遍歷128

7.6.2堆的定義128

7.6.3進堆130

7.6.4出堆131

7.7線索二叉樹132

7.7.1線索二叉樹的概念132

7.7.2線索二叉樹的存儲結構134

7.7.3線索二叉樹的操作算法135

7.8樹的存儲結構與算法139

7.8.1樹的存儲結構139

7.8.2樹的操作算法144

7.9Huffman樹與Huffman編碼148

7.9.1Huffman樹的定義148

7.9.2Huffman樹的構造150

7.9.3Huffman編碼算法152

7.9.4Huffman譯碼算法153

7.10並查集154

7.10.1等價關系與等價類154

7.10.2並查集的基本操作154

7.10.3性能分析與改進156

小結157

習題7158

上機實驗題7159

上機實驗題7指導160第8章圖165

8.1圖的基本概念165

8.1.1圖的定義165

8.1.2圖的基本術語166

8.2圖的存儲結構169

8.2.1鄰接矩陣表示法169

8.2.2鄰接表表示法172

8.3圖的遍歷174

8.3.1圖遍歷的概念174

8.3.2深度優先搜索175

8.3.3廣度優先搜索176

8.3.4圖遍歷算法的應用178

8.4最小生成樹180

8.4.1最小生成樹的概念及其性質180

8.4.2Prim算法181

8.4.3Kruskal算法184

8.5最短路徑186

8.5.1最短路徑的概念186

8.5.2單源最短路徑187

8.5.3每對頂點之間的最短路徑191

8.6AOV網與拓撲排序193

8.6.1有向無環圖與AOV網的概念193

8.6.2拓撲排序194

8.7AOE網與關鍵路徑197

8.7.1AOE網的概念197

8.7.2關鍵路徑197

小結199

習題8200

上機實驗題8201

上機實驗題8指導201第9章查找207

9.1查找的基本概念207

9.2順序表的查找208

9.2.1順序查找208

9.2.2折半查找209

9.2.3分塊查找212

9.3樹表的查找213

9.3.1二叉排序樹213

9.3.2平衡二叉樹218

9.3.3B樹221

9.3.4B+樹227

9.4Hash查找228

9.4.1Hash查找的基本概念228

9.4.2Hash表的構造229

9.4.3Hash表查找算法及分析232

9.5查找的應用234

9.5.1精準查找和近似查找234

9.5.2多樣化的查找235

9.5.3查找的計算資源和性能需求236

小結237

習題9238

上機實驗題9239

上機實驗題9指導239第10章排序243

10.1排序的基本概念243

10.2冒泡排序244

10.3選擇排序245

10.4插入排序246

10.4.1直接插入排序246

10.4.2折半插入排序247

10.5希爾排序248

10.6快速排序250

10.7堆排序252

10.8歸並排序257

10.8.1二路歸並排序的非遞歸實現257

10.8.2二路歸並排序的遞歸實現259

10.9基數排序260

10.9.1多關鍵字排序260

10.9.2鏈式基數排序260

小結262

習題10264

上機實驗題10265

上機實驗題10指導265附錄A數據結構試題267

A.1數據結構試題A267

A.2數據結構試題B269

A.3數據結構試題C270

A.4數據結構試題D271

A.5數據結構試題E273

A.6數據結構試題F275

A.7數據結構試題G276

A.8數據結構試題H277附錄B數據結構課程設計與指導279參考文獻286