數據結構與算法設計編程實踐

目錄

第1章緒論1

1.1導學1

1.1.1思維導圖1

1.1.2重難點分析2

1.2案例3

1.3基礎實驗7

實驗1.1判斷一個大於2的正整數n是否為素數7

實驗1.2數組遍歷8

實驗1.3冷熱數據隊列10

實驗1.4數組元素刪除14

1.4拓展實驗15

實驗1.5紙張尺寸15

實驗1.6刷題統計17

實驗1.7翻硬幣18

第2章線性表20

2.1導學20

2.1.1思維導圖20

2.1.2重難點分析21

2.2案例21

案例2.1線性表元素的插入操作21

案例2.2刪除順序表中指定值的所有元素23

案例2.3查找鏈表中的最大值24

案例2.4刪除鏈表中滿足區間值的結點26

2.3基礎實驗28

實驗2.1順序表L的所有元素逆置28

實驗2.2兩個遞增的有序鏈表合並為一個遞增的有序鏈表28

實驗2.3求出A與B的交集，並存放在A鏈表中30

實驗2.4鏈表原地逆轉31

實驗2.5猴子選大王（約瑟夫環問題）32

實驗2.6查找鏈表中倒數第k個結點33

實驗2.7刪除鏈表中絕對值相等的結點34

2.4拓展實驗36

實驗2.8坐標變換36

實驗2.9環形鏈表39

實驗2.10LRU緩存40

第3章棧與隊列44

3.1導學44

3.1.1思維導圖44

3.1.2重難點分析44

3.2案例44

案例3.1數制轉換44

案例3.2括號匹配47

案例3.3行編輯程序48

案例3.4表達式求值50

3.3基礎實驗52

實驗3.1棧的順序表示和實現52

實驗3.2棧的鏈式表示和實現55

實驗3.3隊列的順序表示和實現58

實驗3.4隊列的鏈式表示和實現61

3.4拓展實驗64

實驗3.5迷宮的求解64

實驗3.6停車場管理69

實驗3.7二十四點73

實驗3.8機器翻譯76

實驗3.9拖拉機77

第4章串81

4.1導學81

4.1.1思維導圖81

4.1.2重難點分析81

4.2案例82

案例4.1統計字符出現的頻度82

案例4.2逆序存儲84

案例4.3字符串的插入85

案例4.4查找子串87

4.3基礎實驗89

實驗4.1KMP算法實現89

4.4拓展實驗91

實驗4.2QQ賬戶的申請與登錄91

實驗4.3基於KMP算法的網絡入侵檢測93

實驗4.4子串簡寫96

實驗4.5模板生成系統98

實驗4.6字符串匹配102

第5章數組和廣義表104

5.1導學104

5.1.1思維導圖104

5.1.2重難點分析104

5.2案例105

案例5.1數列求和105

案例5.2區間刪除106

案例5.3求鏈表倒數第m個元素107

案例5.4有序表的合並110

案例5.5一元多項式的運算112

5.3基礎實驗116

實驗5.1二分查找116

實驗5.2矩陣的壓縮存儲117

5.4拓展實驗121

實驗5.3檢測點查詢121

實驗5.4統計子矩陣122

實驗5.5矩陣運算124

實驗5.6壘骰子126

第6章樹130

6.1導學130

6.1.1思維導圖130

6.1.2重難點分析130

6.2案例131

案例6.1二叉樹的創建與遍歷131

案例6.2列出葉子結點132

案例6.3二叉搜索樹的插入、查找與刪除135

6.3基礎實驗137

實驗6.1計算二叉樹的深度和結點個數137

實驗6.2遞歸實現二叉樹左、右子樹交換139

實驗6.3輸入一個無序序列，創建一棵二叉排序樹141

實驗6.4判斷一棵樹是否為二叉排序樹143

6.4拓展實驗145

實驗6.5用前序與中序遍歷序列構造二叉樹145

實驗6.6網絡延時146

實驗6.7哈夫曼樹150

實驗6.8景區導遊151

實驗6.9飛機降落155

第7章圖159

7.1導學159

7.1.1思維導圖159

7.1.2重難點分析159

7.2案例160

案例7.1圖的鄰接矩陣存儲及圖初始化160

案例7.2圖的鄰接表存儲及圖初始化162

案例7.3圖的廣度優先搜索163

案例7.4圖的深度優先搜索165

案例7.5拓撲排序167

案例7.6Prim算法生成最小生成樹172

7.3基礎實驗175

實驗7.1創建無向圖175

實驗7.2列出連通集176

實驗7.3有向圖深度優先搜索178

實驗7.4求最短路徑179

實驗7.5圖不連通方案181

實驗7.6奇怪圖的哈密頓回路問題183

實驗7.7小動物逃亡問題185

實驗7.8平均長度最大環問題189

7.4拓展實驗191

實驗7.9哈利·波特的考試191

實驗7.10旅遊規劃194

實驗7.11公路村村通197

實驗7.12畫圖201

實驗7.13最優配餐204

實驗7.14最優灌溉208

實驗7.15地鐵修建211

第8章算法思想216

8.1導學216

8.1.1思維導圖216

8.1.2重難點分析217

8.2案例217

案例8.1百錢買百雞問題217

案例8.2組合枚舉法219

案例8.3排列枚舉法220

案例8.4指數枚舉法222

案例8.5區間分治223

案例8.601背包223

案例8.7完全背包224

案例8.8普通貪心226

8.3基礎實驗227

實驗8.1八皇後問題227

實驗8.2分治法解決平面上最接近點對229

實驗8.3多機調度問題230

實驗8.4最大子序列和231

實驗8.5最長上升子序列233

實驗8.6最長公共子序列235

實驗8.7分治法構建線段樹238

8.4拓展實驗243

實驗8.8編輯距離243

實驗8.9撲克遊戲245

實驗8.10最大子樹和249

實驗8.11寶物篩選252

實驗8.12引水入城254

實驗8.13保衛王國256

第9章查找261

9.1導學261

9.1.1思維導圖261

9.1.2重難點分析262

9.2案例262

案例9.1順序表的查找262

案例9.2有序表折半查找263

案例9.3二叉排序樹查找263

案例9.4二叉排序樹插入算法263

案例9.5平衡二叉樹插入算法264

案例9.6B樹查找算法266

案例9.7開放定址哈希表查找267

9.3基礎實驗267

實驗9.1靜態表查找267

實驗9.2魔法書中的查找與插入268

實驗9.3班級學生成績查詢系統270

實驗9.4哈希表的基本操作272

實驗9.5部落沖突275

實驗9.6中序遍歷樹並判斷是否為二叉搜索樹277

9.4拓展實驗278

實驗9.7在線購物平臺商品管理系統278

實驗9.8社交網絡用戶管理系統283

實驗9.9二叉排序樹287

實驗9.10掃雷289

實驗9.11墾田計劃292

第10章排序296

10.1導學296

10.1.1思維導圖296

10.1.2重難點分析297

10.2案例297

案例10.1直接插入排序297

案例10.2折半插入排序297

案例10.3希爾排序298

案例10.4冒泡排序298

案例10.5快速排序298

案例10.6簡單選擇排序299

案例10.7堆排序299

案例10.8歸並排序300

10.3基礎實驗300

實驗10.1冒泡排序在整數數組中的應用300

實驗10.2快速排序在字符串數組中的應用302

實驗10.3歸並排序在鏈表中的應用304

實驗10.4堆排序在浮點數數組中的應用307

10.4拓展實驗309

實驗10.5尋找大富翁309

實驗10.6蛇語翻譯310

實驗10.7小朋友排隊312

實驗10.8數位排序315

實驗10.9第k個數316

附錄A綜合實驗319

A.1文件加密解密319

A.2校園導航324