基本介紹
- 書名：數據結構（第3版）
- 作者：劉大有、楊博、黃晶、朱允剛、谷方明、姜麗
- ISBN：978-7-04-046787-1
- 類別：“十二五”普通高等教育本科國家級規劃教材等
- 頁數：342頁
- 出版社：高等教育出版社
- 出版時間：2017年3月6日
- 裝幀：平裝
- 開本：16開
- 版面字數：500千字
成書過程,修訂情況,人員分工,內容簡介,教材目錄,教學資源,教材特色,作者簡介,
成書過程
修訂情況
該教材修訂部分如下：
1. 精簡部分內容。從2010年《數據結構（第2版）》（以下簡稱“第2版”）中，刪去了“遞歸”“記憶體管理”“檔案”和“隨機數”4章和附錄等內容，對“緒論”“線性表堆疊和佇列”“數組和字元串”“樹”“圖排序”和“查找”等各章進行了改寫。
2.算法分析或其關鍵部分的正確性證明是讀者學習數據結枃需要掌握的技巧，為此增加了新的一章“數學準備”。
3.在第6章“圖”中新增了6.6.4節“滿足約東的最短路徑”，給出了其ADL描述和實例分析。
4.在6.7.2節中增加了 Kruskal算法的ADL描述、時間複雜性分析和關鍵部分的正確性證明。
5.增加了背景歷史介紹，以及推薦讀物與參考文獻。
6.將第2版附錄（算法的C++代碼、習題答案或解題思路）與教師講課視頻、算法動畫等以數位化資源存於網站。
2015年7月18日，《數據結構（第3版）》入選教育部“十二五”職業教育國家規劃教材。
2017年3月6日，《數據結構（第3版）》由高等教育出版社出版。
人員分工
該教材編寫分工為：劉大有對全書進行了架構設計和統稿，並撰寫了第1章、第2章、前言和內容提要；楊博撰寫了第6章；黃晶撰寫了第3章及第4章；姜麗、朱允剛撰寫了第8章；谷方明撰寫了第5章；朱允剛撰寫了第7章。吉林大學數據結構數學團隊的部分教師指導學生對一些較難的算法設計實現了動畫程式。朱允剛指導學生進行了該教材涉及的數位化資源的網上試驗。團隊成員虞強源、劉亞波、賈海洋、高瀅和賴永等在撰寫人二校的基礎上又對書稿進行了校對，提出了修改建議。
內容簡介
該教材系統介紹了數據結構的概念、原理、技術和套用實例，由紙介質部分和線上數位化資源部分所組成，紙介質部分主要包括數學準備、緒論、基本數據結構、排序與查找等內容，共8章。其中，第1章“數學準備”，系統地介紹與算法分析緊密相關的數學分支(生成函式與漸近表示除外，漸近表示在第2章簡要介紹)的基本知識；第2章“緒論”，對算法描述語言ADL和算法書寫規範、數據結構與算法的基本概念、算法分析基礎等進行闡述；第3、4章介紹線性結構，系統地描述線性表、堆疊、佇列、數組和字元串等結構的存儲、操作和套用；第5章“樹與二叉樹”，在詳細刻畫樹和二叉樹結構的基礎上，從套用和數據結構擴展的視角漸進地討論線索二叉樹、哈夫曼樹、並查集和決策樹等內容；第6章“圖”，系統地闡述圖的基本概念、基本存儲結構和基本算法，新增了帶約束的最短路徑算法和功能同Warshall算法但更高效的傳遞閉包求解算法，從套用的視角討論複雜網路概念和基於圖的典型信息搜尋算法；第7、8章“排序”與“查找”，深入討論排序和查找的重要內容，並給出典型算法的描述、時間複雜性分析和相關算法的比較等。
教材目錄
前輔文第1章 數學準備 1.1 數學歸納法 1.2 數、冪與對數 1.3 和與積 1.4 整數函式和初等數論 1.5 排列和階乘 1.6 二項式係數 1.7 調和數 1.8 斐波那契數 小結 推薦讀物與參考文獻 習題 第2章 緒論 2.1 為什麼要學習數據結構 2.2 數據結構概念 2.2.1 數據的邏輯結構 2.2.2 數據的存儲結構 2.2.3 對數據結構的操作 2.2.4 數據結構示例 2.3 算法 2.3.1 算法及其特性 2.3.2 算法的描述 2.3.3 算法的評價準則 2.4 算法的正確性證明 2.5 算法分析基礎 2.5.1 算法時間複雜性的分析方法 2.5.2 複雜性函式的漸近表示 2.5.3 算法時間與空間分析 2.5.4 計算複雜性和算法的效率 小結 推薦讀物與參考文獻 習題 第3章 線性表、堆疊和佇列 3.1 線性表的定義和基本操作 3.2 線性表的順序存儲結構 3.3 線性表的連結存儲結構 3.3.1 單鍊表 3.3.2 循環鍊表 3.3.3 雙向鍊表 3.4 複雜性分析 3.5 堆疊 3.5.1 堆疊的定義和基本操作 3.5.2 順序棧 3.5.3 鏈式棧 3.5.4 順序棧與鏈式棧的比較 3.5.5 堆疊套用——括弧匹配 3.5.6 堆疊套用——遞歸 3.6 佇列 3.6.1 佇列的定義和基本操作 3.6.2 順序佇列 3.6.3 鏈式佇列 小結 推薦讀物與參考文獻 習題 第4章 數組和字元串 4.1 數組 4.1.1 數組的存儲和定址 4.1.2 一維數組的基本操作 4.2 矩陣 4.2.1 矩陣的數組表示 4.2.2 特殊矩陣的壓縮存儲 4.2.3 三元組表 4.2.4 十字鍊表 4.3 字元串 4.3.1 字元串的定義與存儲 4.3.2 模式匹配算法 小結 推薦讀物與參考文獻 習題 第5章 樹與二叉樹 5.1 樹的基本概念 5.1.1 樹的定義 5.1.2 樹的相關術語 5.1.3 樹的表示 5.2 二叉樹 5.2.1 二叉樹定義和主要性質 5.2.2 二叉樹順序存儲 5.2.3 二叉樹連結存儲 5.2.4 二叉樹遍歷 5.2.5 二叉樹的其他操作 5.2.6 表達式樹 5.3 線索二叉樹 5.3.1 線索二叉樹的概念 5.3.2 線索二叉樹的操作 5.3.3 線索二叉樹的進一步說明 5.4 壓縮與哈夫曼樹 5.4.1 檔案編碼 5.4.2 擴充二叉樹 5.4.3 哈夫曼樹和哈夫曼編碼 5.5 樹的存儲和操作 5.5.1 樹與二叉樹的轉換 5.5.2 樹的存儲結構 | 5.5.3 樹和森林的遍歷5.5.4 樹的順序表示 5.6 等價類與並查集 5.6.1 等價類 5.6.2 並查集的實現 5.7 分類與決策樹 小結 推薦讀物與參考文獻 習題 第6章 圖 6.1 圖的基本概念 6.2 圖的存儲結構 6.2.1 鄰接矩陣 6.2.2 鄰接表 6.3 圖的遍歷算法 6.3.1 深度優先遍歷 6.3.2 廣度優先遍歷 6.4 拓撲排序 6.5 關鍵路徑 6.6 最短路徑問題 6.6.1 無權最短路徑問題 6.6.2 正權最短路徑問題 6.6.3 每對頂點之間的最短路徑 6.6.4 滿足約束的最短路徑 6.7 最小支撐樹 6.7.1 普里姆算法 6.7.2 克魯斯卡爾算法 6.8 圖的套用 6.8.1 可及性及傳遞閉包算法 6.8.2 連通分量 6.8.3 圖在網路分析和信息檢索中的套用 小結 推薦讀物與參考文獻 習題 第7章 排序 7.1 排序問題的基本概念 7.2 插入排序 7.2.1 直接插入排序 7.2.2 Shell排序 7.3 交換排序 7.3.1 冒泡排序 7.3.2 快速排序 7.4 選擇排序 7.4.1 直接選擇排序 7.4.2 堆排序 7.5 合併排序 7.6 基於關鍵字比較的排序算法分析 7.6.1 平方階排序算法及改進算法 7.6.2 線性對數階排序算法 7.6.3 分治排序的一般方法 7.6.4 基於關鍵字比較的排序算法下界 7.7 分布排序 7.8 外排序 7.8.1 外存儲器 7.8.2 磁帶排序 7.8.3 磁碟排序 小結 推薦讀物與參考文獻 習題 第8章 查找 8.1 順序查找 8.1.1 無序表的順序查找 8.1.2 有序表的順序查找 8.2 基於關鍵字比較的查找 8.2.1 對半查找 8.2.2 一致對半查找 8.2.3 斐波那契查找 8.2.4 插值查找 8.3 二叉查找樹 8.3.1 基本概念和性質 8.3.2 查找、插入和刪除 8.3.3 平均情況時間分析 8.4 最優二叉查找樹 8.4.1 訪問頻率 8.4.2 最優二叉查找樹 8.4.3 近似最優樹的構造 8.5 高度平衡樹 8.5.1 基本概念和性質 8.5.2 查找和插入操作 8.5.3 線性表的平衡樹表示 8.5.4 刪除操作 8.6 B樹 8.6.1 多叉樹 8.6.2 B樹 8.7 數字查找 8.7.1 檢索結構查找 8.7.2 數字樹查找 8.8 散列 8.8.1 散列函式 8.8.2 衝突調節 8.8.3 刪除 小結 推薦讀物與參考文獻 習題 |
教學資源
- 課程資源
《數據結構（第3版）》配套建設有數據結構數字課程，該數字課程包括電子教案、重要內容的講解視頻、較難算法的動畫演示及示例原始碼等輔助教學內容。
| 數字課程名稱 | 出版社 | 出版時間 | 內容提供者 |
|---|---|---|---|
數據結構數字課程 | 高等教育出版社、高等教育電子音像出版社 | 2017年6月 | 劉大有 |
教材特色
該教材針對一些重要知識點，著力設計啟發式教學內容。
①在選擇與組織材料時，著力構造由多個求解同一問題的不同算法組成的“算法鏈條”。
②在對某算法進行具體描述之前，闡明該算法的關鍵思想，使部分讀者能給出該算法的描繪（或較粗略的描繪）。
③對算法涉及的關鍵難點給出嚴格證明，這不僅能幫助讀者透徹理解算法，而且能培養其嚴謹的科學精神。
④在每章的結尾處給出相關算法的比較，點明對其進一步改進或提升的思路。
⑤針對一些較難的算法，設計能幫助讀者理解的動畫程式。
⑥針對一些典型算法，選擇與改寫恰當的例子，進一步加深讀者對算法機理和重要性的理解。
該教材每章之後都附加了精選的習題，並且對每道習題都列出了其重要屬性及屬性值，以使讀者更好地了解和選擇習題，具體包括：按難度將習題分為5個等級，5級是最高的難度級別；標註解答習題所需的大致平均時間；對用到高等數學知識的習題進行標記；對難度級別≥3的習題般給出了提示或分級提示（這些習題通常是有相當難度的題目，建議在讀了第一級提示後仍然沒有解題思路，才去讀第二級提示，依此類推）。
該教材重視內容的嚴謹性，並試圖使讀者在這方面受到一定的訓練。具體做法主要包括：對書中與某些算法之正確性有關的一些問題，以及與算法複雜性分析或數據結構概念相關的重要定理、引理等都給出了嚴格的數學證明；對主要概念都試圖給出嚴格的形式化定義。
作者簡介
劉大有，男，碩士，吉林大學計算機科學與技術學院教授，博士生導師。
楊博，男，碩士，吉林大學計算機科學與技術學院教授，吉林大學符號計算與知識工程教育部重點實驗室主任。
黃晶，女，博士，吉林大學計算機科學與技術學院副教授。
朱允剛，男，博士，吉林大學計算機科學與技術學院副教授。
谷方明，男，博士，吉林大學計算機科學與技術學院講師。
姜麗，女，博士，吉林大學計算機科學與技術學院講師。
