第一部分學 習 輔 導
第1章緒論/3
1.1本章導學3
1.1.1知識結構圖3
1.1.2重點整理3
1.2重點難點釋疑4
1.2.1信息、數據與結構4
1.2.2數據類型與抽像數據類型5
1.2.3邏輯結構與存儲結構5
1.2.4如何選擇（或設計）數據結構6
1.2.5算法的時間復雜度分析7
1.3習題解析8
第2章線性表/18
2.1本章導學18
2.1.1知識結構圖18
2.1.2重點整理18
2.2重點難點釋疑19
2.2.1頭指針、尾標志、開始結點與頭結點19
2.2.2帶頭結點的單鏈表與不帶頭結點的單鏈表20
2.2.3單鏈表的算法設計技巧22
2.3習題解析26
第3章棧、隊列和數組/39
3.1本章導學39
3.1.1知識結構圖39
3.1.2重點整理39
3.2重點難點釋疑41
3.2.1淺析棧的操作特性413.2.2遞歸算法轉換為非遞歸算法41
3.2.3循環隊列中隊空和隊滿的判定方法42
3.2.4特殊矩陣壓縮存儲的尋址計算43
3.3習題解析44
第4章樹和二叉樹/57
4.1本章導學57
4.1.1知識結構圖57
4.1.2重點整理57
4.2重點難點釋疑59
4.2.1樹和二叉樹是兩種不同的樹結構59
4.2.2二叉樹的構造方法60
4.2.3二叉樹遍歷的遞歸執行過程60
4.2.4二叉樹的算法設計技巧60
4.2.5構造哈夫曼樹的兩種常見錯誤63
4.3習題解析63
〖1〗數據結構學習輔導與實驗指導——從概念到實現目錄〖3〗〖3〗第5章圖/79
5.1本章導學79
5.1.1知識結構圖79
5.1.2重點整理79
5.2重點難點釋疑81
5.2.1深度優先遍歷算法的非遞歸實現81
5.2.2基於圖遍歷的算法設計技巧81
5.2.3有向圖的強連通分量82
5.3習題解析83
第6章查找技術/99
6.1本章導學99
6.1.1知識結構圖99
6.1.2重點整理99
6.2重點難點釋疑101
6.2.1折半查找判定樹及其應用101
6.2.2平衡二叉樹的調整方法102
6.2.3散列查找的性能分析103
6.2.4模式匹配KMP算法的失效數組104
6.3習題解析106
第7章排序技術/122
7.1本章導學122
7.1.1知識結構圖122
7.1.2重點整理122
7.2重點難點釋疑123
7.2.1排序算法的穩定性123
7.2.2將排序算法移植到單鏈表124
7.2.3辨析二叉查找樹和堆126
7.3習題解析127
第二部分實 驗 指 導
第8章實驗概述/141
8.1實驗的一般過程141
8.1.1本書的實驗安排141
8.1.2驗證實驗的一般過程142
8.1.3設計實驗和綜合實驗的一般過程142
8.2Code::Blocks編程工具143
8.2.1單文件結構144
8.2.2多文件結構145
8.2.3程序的調試148
第9章線性表/153
9.1驗證實驗153
9.1.1線性表的順序存儲及實現153
9.1.2線性表的鏈接存儲及實現154
9.2設計實驗155
9.2.1提純線性表155
9.2.2合並有序鏈表156
9.2.3士兵訓練157
9.2多項式相加158
第10章棧、隊列和數組/160
10.1驗證實驗160
10.1.1棧的順序存儲及實現160
10.1.2隊列的鏈接存儲及實現161
10.1.3對稱矩陣的壓縮存儲162
10.2設計實驗163
10.2.1漢諾塔問題163
10.2.2布爾表達式求值164
10.2.3機器翻譯165
10.2.4數塔問題166
第11章樹和二叉樹/168
11.1驗證實驗168
11.1.1二叉樹的二叉鏈表存儲及實現168
11.1.2樹的孩子兄弟存儲及實現169
11.2設計實驗170
11.2.1最近共同祖先170
11.2.2掃黑行動171
11.2.3鏡像對稱二叉樹172
11.2.4二叉樹表示樹173
第12章圖/175
12.1驗證實驗175
12.1.1圖的鄰接矩陣存儲及實現175
12.1.2圖的鄰接表存儲及實現176
12.2設計實驗177
12.2.1農夫抓牛177
12.2.2研發卡車178
12.2.3城市郵遞員179
12.2.4城堡問題180
第13章查找技術/183
13.1驗證實驗183
13.1.1順序查找算法及實現183
13.1.2折半查找算法及實現184
13.1.3散列查找算法及實現184
13.2設計實驗185
13.2.1團隊合影185
13.2.2單詞出現的次數186
13.2.3獨一無二的雪花187
13.2.4二叉查找樹188
第14章排序技術/190
14.1驗證實驗190
14.1.1插入排序算法及實現190
14.1.2交換排序算法及實現191
14.1.3選擇排序算法及實現191
14.2設計實驗192
14.2.1車廂重排192
14.2.2素193
14.2.3Topk問題194
14.2.4奶牛學校的書架195
第15章綜合實驗/197
15.1大整數的代數運算197
15.2用單鏈表實現集合200
15.3算術表達式求值202
15.4貨車車廂重排203
15.5幻方204
15.6文檔壓縮206
15.7迷宮問題208
15.82048遊戲209
15.9五子棋212
15.10賽事統計215
附錄A實驗報告的一般格式/216

數據結構是計算機及相關專業的核心課程，也是計算機及相關專業碩士研究生入學考試的必考科目。數據結構課程知識豐富、內容抽像，隱藏在各的概念和方法較多，學生必須通過知識梳理、習題演練和動手實驗纔能達成數據結構課程的教學目標。本書與清華大學出版社《數據結構——從概念到C實現》《數據結構——從概念到C 實現》《數據結構——從概念到Java實現》主教材配套使用，起到銜接課堂教學和指導實驗教學的作用。
本書包括兩部分。第一部分是學習輔導，共7章，對應主教材第1～7章。每章由3個模塊組成: 第一個模塊是本章導學，包括知識結構圖和重點整理;第二個模塊是重點難點釋疑，對本章的重點、難點進行梳理和剖析；第三個模塊是習題解析，對主教材的作業冊和補充習題進行深入淺出的解析。第二部分是實驗指導，共8章。其中，第8章為實驗概述；第9～14章對應主教材第2～7章，包括驗證實驗和設計實驗；第15章是綜合實驗。驗證實驗在主教材上都能找到具體的數據結構和算法實現，建議在學習相關知識的同時自行完成。數據結構課程通常包含實驗環節，建議在實驗課上完成設計實驗。如果數據結構課程安排了課程設計，建議在課程設計環節完成綜合實驗；如果沒有安排課程設計，建議以大作業的形式完成綜合實驗。
數據結構是一門實踐性很強的課程，能夠求解的問題更接近實際，本書按照“驗證實驗→設計實驗→綜合實驗”遞進的層次安排相關實驗，循序漸進地提高學生運用數據結構解決實際問題的能力。驗證實驗由實驗目的、實驗內容、實驗提示、實驗程序4部分組成。其中，實驗目的明確了該實驗要運用哪些知識點，實驗內容規定了實驗的具體任務，實驗提示給出了編程實現的關鍵點，實驗程序以二維碼的形式提供了C、C 、Java語言實現的範例程序和部分測試數據。設計實驗和綜合實驗由問題描述、基本要求、測試樣例、實驗提示、擴展實驗5部分組成。其中，問題描述建立問題的背景環境，對待求解的問題進行描述和說明；基本要求對求解方案進行約束規範，保證預定的實驗意圖，使某些難點和重點不會被繞過去，同時也便於教學檢查；測試樣例給出幾組測試數據，同時也有助於理解問題；實驗提示給出設計數據結構和算法的主要思路，以偽代碼形式給出算法描述；擴展實驗引導學生在完成實驗任務後進行深入思考，探索其他實現方法。本書由王紅梅編寫，其中設計實驗案例由張麗傑老師整理，綜合實驗項目和習題由蓋世蕊老師整理，2021級本科生楊寶祥調試了驗證實驗。
限於作者的知識和寫作水平，本書雖經再三斟酌和反復修改，仍難免有缺點和錯誤，歡迎專家和讀者批評指正。
作者的電子郵箱是wanghongmei@ccut.edu.cn。

作者
2024年1月