數據結構原理與套用實踐教程

《數據結構原理與套用實踐教程》是2022年清華大學出版社出版的圖書，作者是徐慧、丁紅、朱玲玲、周建美、劉維華。

基本介紹

• 中文名：數據結構原理與套用實踐教程
• 作者：徐慧、丁紅、朱玲玲、周建美、劉維華
• 出版社：清華大學出版社
• 出版時間：2022年12月1日
• 定價：79 元
• ISBN：9787302623434

內容簡介

本書是江蘇省高等學校重點教材《數據結構原理與套用》的配套教材，補充與拓展課堂教學內容，銜接理論與實踐。本書在選材與編排上以“易讀”“易用”“易練”“可研”為目標，為數據結構相關課程提供全方位的實踐練習指導。全書分為4篇： 第1篇是原理篇，簡述典型結構（線性表、棧和佇列、數組和矩陣、樹和二叉樹、圖等）及其在計算機中的實現原理，查找和排序的經典算法的原理；第2篇是驗證篇，提供了主教材的算法實現；第3篇是設計篇，按主教材內容順序，為每一章設計了3～5個設計型實踐活動，適合作為課程實驗素材；第4篇是綜合篇，給出10個涉及多個知識點的複雜設計任務，可作為課程設計的素材。

本書內容全面，可單獨作為數據結構相關課程的實踐教材使用。本書提供的大量源程式和設計思想，對於從事計算機套用及開發的技術人員、數據結構和程式設計教授或學習的教師和學生具有很好的參考和指導作用。

圖書目錄

第1篇原理篇

第1章線性表3

1.1順序表3

1.1.1順序表存儲定義與特性3

1.1.2順序表操作實現原理4

1.1.3順序表的套用6

1.2鍊表7

1.2.1單鍊表存儲定義與特性7

1.2.2單鍊表操作實現原理8

1.2.3鍊表的套用11第2章棧13

2.1順序棧13

2.1.1順序棧的存儲定義和特性13

2.1.2順序棧操作實現原理14

2.2鏈棧14

2.2.1鏈棧的存儲定義和特性14

2.2.2鏈棧操作實現原理15

2.3棧的套用16第3章佇列19

3.1循環佇列19

3.1.1循環佇列存儲定義和特性19

3.1.2循環佇列操作實現原理20

3.2鏈隊21

3.2.1鏈隊的存儲定義和特性21

3.2.2鏈隊的操作實現原理21

3.3佇列的套用22第4章數組和矩陣23

4.1數組和矩陣的存儲23

4.2稀疏矩陣轉置23

4.3稀疏矩陣求和24第5章樹和二叉樹27

5.1樹27

5.2二叉樹27

5.2.1二叉樹的存儲定義27

5.2.2二叉樹操作實現原理28

5.3線索二叉樹31

5.3.1線索二叉樹的存儲定義31

5.3.2線索二叉樹操作實現原理31

5.4最優二叉樹33

5.4.1最優二叉樹的存儲定義和特性33

5.4.2最優二叉樹的構建33

5.4.3哈夫曼編碼的構建34第6章圖35

6.1鄰接矩陣存儲35

6.1.1鄰接矩陣存儲定義與特性35

6.1.2鄰接矩陣操作實現原理36

6.2圖的鄰接表存儲37

6.2.1鄰接表存儲定義與特性37

6.2.2鄰接表操作實現原理38

6.3圖的遍歷及其套用39

6.3.1深度優先遍歷39

6.3.2廣度優先遍歷39

6.3.3連通性問題40

6.3.4求最遠頂點40

6.4圖的套用41

6.4.1求最小生成樹41

6.4.2單源點最短距離42

6.4.3任意兩點的最短距離42

6.4.4AOE網的拓撲排序43

6.4.5AOE網的關鍵活動43第7章查找45

7.1線性表查找45

7.2串的模式匹配46

7.3二叉排序樹47

7.3.1二叉排序樹存儲定義與特性47

7.3.2二叉排序樹操作實現原理47

7.4散列查找48

7.4.1散列技術48

7.4.2散列表操作實現原理48第8章排序51

8.1插入類排序51

8.2交換類排序52

8.3選擇排序53

8.4二路歸併排序54

8.5基數排序54

第2篇驗證篇

第1章緒59

1.1算法到程式轉換60

1.2驗證性實踐步驟63

1.3實驗環境簡介64

1.3.1VC++ 6.064

1.3.2VS系列67

1.4驗證程式的設計71第2章線性表73

2.1順序表73

2.2單鍊表82

2.3順序表的套用95

2.4一元稀疏多項式求和101第3章棧和佇列109

3.1順序棧109

3.2鏈棧116

3.3棧的套用121

3.3.1括弧匹配121

3.3.2表達式計算124

3.4順序佇列133

3.5鏈隊140

3.6佇列套用147第4章稀疏矩陣153

4.1稀疏矩陣轉置153

4.2稀疏矩陣求和158第5章二叉樹165

5.1二叉樹簡介165

5.2中序線索化二叉樹176

5.3哈夫曼樹和哈夫曼編碼183第6章圖189

6.1圖的實現189

6.1.1程式設計簡介189

6.1.2無向圖的鄰接矩陣實現190

6.1.3有向網的鄰接表實現202

6.2圖的遍歷套用217

6.2.1鄰接矩陣存儲的圖的遍歷套用217

6.2.2鄰接表存儲的圖的遍歷套用221

6.3圖的套用225

6.3.1最小生成樹225

6.3.2最短距離232

6.3.3拓撲排序239

6.3.4關鍵活動244第7章查找251

7.1靜態查找251

7.2字元串匹配256

7.3二叉排序樹262

7.4散列查找270第8章內部排序277

第3篇設計篇

第1章緒299

1.1實驗步驟299

1.2實驗報告格式301

1.3實驗報告案例301第2章線性表303

2.1實驗目的303

2.2實驗任務303

2.2.1集合運算303

2.2.2一元多項式求導305

2.2.3有序表合併307

2.2.4循環單鍊表309

2.2.5約瑟夫環問題311第3章棧和佇列315

3.1實驗目的315

3.2實驗任務315

3.2.1數制轉換315

3.2.2算術表達式正確性判斷317

3.2.3棧的逆置318

3.2.4求任意長兩個大整數的和319

3.2.5單指針鏈隊問題322

3.2.6楊輝三角形問題324第4章數組和矩陣327

4.1實驗目的327

4.2實驗任務327

4.2.1求兩個對稱矩陣之和與乘積327

4.2.2“蛇形”矩陣329

4.2.3魔方問題330第5章樹與二叉樹333

5.1實驗目的333

5.2實驗任務333

5.2.1二叉樹的葉結點計數333

5.2.2複製二叉樹335

5.2.3求二叉樹的寬度336

5.2.4求先/中/後序遍歷序列的首、尾數據元素339

5.2.5葉結點路徑問題341第6章圖343

6.1實驗目的343

6.2實驗任務343

6.2.1存儲結構轉換問題343

6.2.2有向圖的路徑問題346

6.2.3無向圖的路徑問題350

6.2.4俱樂部選址問題352

6.2.5物流最短路徑問題354第7章查找357

7.1實驗目的357

7.2實驗任務357

7.2.1順序查找與折半查找357

7.2.2用二叉排序樹實現字元統計358

7.2.3拉鏈法處理衝突的散列表360

7.2.4開放定址法處理衝突的散列表363第8章排序367

8.1實驗目的367

8.2實驗任務367

8.2.1單鍊表上的直接插入排序367

8.2.2單鍊表上的簡單選擇排序369

8.2.3雙向冒泡排序370

8.2.4序列重排372

8.2.5堆判斷374

第4篇綜合篇

第1章緒論379

1.1綜合設計內容380

1.2綜合設計報告格式381第2章綜合任務383

2.1個人樂庫管理系統383

2.1.1問題描述383

2.1.2分析與設計提示383

2.1.3性能要求384

2.2高校學生信息快速查詢系統384

2.2.1問題描述384

2.2.2分析與設計提示384

2.2.3性能要求386

2.3紙牌遊戲386

2.3.1問題描述386

2.3.2分析與設計提示387

2.3.3性能要求388

2.4排雷遊戲388

2.4.1問題描述388

2.4.2分析與設計提示389

2.4.3性能要求390

2.5迷宮問題390

2.5.1問題描述390

2.5.2分析與設計提示391

2.5.3性能要求393

2.6校園導遊系統393

2.6.1問題描述393

2.6.2分析與設計提示393

2.6.3性能要求395

2.7列印任務管理395

2.7.1問題描述395

2.7.2分析與設計提示396

2.7.3性能要求396

2.8教學計畫編制397

2.8.1問題描述397

2.8.2分析與設計提示398

2.8.3性能要求398

2.9基於哈夫曼編碼的編碼解碼問題398

2.9.1問題描述398

2.9.2分析與設計提示398

2.9.3性能要求399

2.10校園優秀學生的推薦與評比400

2.10.1問題描述400

2.10.2分析與設計提示400

2.10.3性能要求401

參考文獻403附錄實驗報告示例405

實驗學生基本信息管理405

1問題描述與分析405

2數據結構設計406

3算法設計407

4運行與測試409

5小結410