數據結構 (Java版) (第2版.微課視頻版) 9787302629757 呂雲翔 郭穎美 王子豪

內容簡介
本書在選材與編排上，貼近當前普通高等院校「數據結構」課程的現狀和發展趨勢，內容難度適度，突出實用性和應用性。在內容選取與結構上，本書並未對各種數據結構面面俱到，而是通過分類和講解典型結構，使讀者形成對數據結構的宏觀認識。根據內容側重，本書共8章，分別為緒論、線性表、棧和隊列、串和數組、樹結構、圖、排序和查找。
本書是高等院校計算機科學、軟體工程及相關專業「數據結構」課程的理想教材，也可供程序員、系統工程師等相關人員閱讀參考。

目錄

目錄
第1章緒論
1 1引言
1 1 1學習目的
1 1 2課程內容
1 2基本概念
1 2 1數據與數據結構
1 2 2數據類型與抽象數據類型
1 3演算法
1 3 1演算法的概念
1 3 2演算法描述
1 3 3演算法分析
1 4Java提供的泛型方法
1 4 1使用Object類表示泛型
1 4 2使用Comparable介面類型表示泛型
小結
習題1
第2章線性表
2 1線性表及其基本操作
2 1 1線性表的基本概念
2 1 2抽象數據類型描述
2 1 3線性表的存儲和實現
2 2線性表的順序存儲
2 2 1順序表
2 2 2順序表的基本操作實現
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
第3章棧和隊列
3 1棧
3 1 1棧的基本概念
3 1 2棧的抽象數據類型描述
3 1 3順序棧
3 1 4鏈棧
3 2隊列
3 2 1隊列的基本概念
3 2 2隊列的抽象數據類型描述
3 2 3順序隊列
3 2 4鏈隊列
3 2 5優先順序隊列
3 3棧和隊列的比較
3 4實驗
3 4 1漢諾塔
3 4 2吃巧克力
3 4 3表達式求值
小結
習題3
第4章串和數組
4 1串
4 1 1串的基本概念
4 1 2串的抽象數據類型描述
4 1 3順序串
4 1 4鏈串
4 2串的模式匹配
4 2 1BruteForce演算法
4 2 2KMP演算法
4 3數組
4 3 1數組的基本概念
4 3 2數組的特性
4 3 3數組的遍歷
4 4特殊矩陣的壓縮存儲
4 4 1三角矩陣的壓縮存儲
4 4 2對稱矩陣的壓縮存儲
4 4 3對角矩陣的壓縮存儲
4 4 4稀疏矩陣的壓縮存儲
4 5實驗
4 5 1最大連續子數組
4 5 2最大上升子序列
4 5 3走迷宮
小結
習題4
第5章樹結構
5 1樹
5 1 1樹的基本概念
5 1 2樹的術語
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 3 4構造哈夫曼樹和哈夫曼編碼的類的描述
5 4樹和森林
5 4 1樹的存儲結構
5 4 2樹的遍歷規則
5 5實驗
5 5 1平衡二叉樹檢驗
5 5 2查找最近公共祖先
5 5 3由前序遍歷和中序遍歷構造二叉樹
小結
習題5
第6章圖
6 1圖概述
6 1 1圖的基本概念
6 1 2圖的抽象數據類型描述
6 2圖的存儲結構
6 2 1鄰接矩陣
6 2 2鄰接表
6 3圖的遍歷
6 4最小生成樹
6 4 1最小生成樹的基本概念
6 4 2Kruskal演算法
6 4 3Prim演算法
6 5最短路徑
6 5 1求某個頂點到其餘頂點的最短路徑
6 5 2求任意兩個頂點間的最短路徑
6 6拓撲排序和關鍵路徑
6 6 1拓撲排序
6 6 2關鍵路徑
6 7實驗
6 7 1Prime演算法
6 7 2單源最短路
小結
習題6
第7章排序
7 1排序概述
7 1 1排序的基本概念
7 1 2排序演算法的性能評價
7 1 3待排序的記錄和順序表的類描述
7 2插入排序
7 2 1直接插入排序
7 2 2希爾排序
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
第8章查找
8 1查找的基本概念
8 1 1什麼是查找
8 1 2查找表
8 1 3平均查找長度
8 2靜態表查找
8 2 1順序查找
8 2 2二分查找
8 2 3分塊查找
8 3動態表查找
8 3 1二叉排序樹查找
8 3 2平衡二叉樹
8 3 3B-樹和B+樹
8 4哈希表查找
8 4 1哈希表的概念
8 4 2哈希函數
8 4 3解決衝突的方法
8 4 4哈希表查找性能分析
8 5實驗
8 5 1尋找山形數組的頂點
8 5 2查找重複數
8 5 3有序矩陣查找
小結
習題8
附錄A綜合實踐題
參考文獻

前言/序言
黨的二十大報告中指出: 教育、科技、人才是全面建設社會主義現代化國家
的基礎性、戰略性支撐。必須堅持科技是第一生產力、人才是第一資源、創新是
第一動力，深入實施科教興國戰略、人才強國戰略、創新驅動發展戰略，這三大
戰略共同服務於創新型國家的建設。高等教育與經濟社會發展緊密相連，對促進
就業創業、助力經濟社會發展、增進人民福祉具有重要意義。
自2017年11月出版以來，《數據結構（Java版）》經過了多次印刷，被許多高校選為「數據結構」課程的教材，深受這些學校師生的鍾愛，並獲得了良好的社會效益。但從另外一個角度來看，作者有責任和義務維護好這本書的質量，及時更新書中內容，做到與時俱進。
近年來，信息技術突飛猛進，在雲計算、大數據和人工智慧等方面發展得越來越快。即使在前一版的文章中已經涉及的一些技術，由於有了進一步的發展，也有必要將其內容進行及時的更新。本書改動內容如下。
（1） 重新對每章的內容進行了梳理。
（2） 在第2∼8章，每章都增加了實驗題及其解答，便於讀者提高動手能力。
（3） 針對每章的應用題，重新運行原有程序，使習題答案準確無誤。
（4） 針對每章的重點或難點的演算法和實驗，配置了微課視頻進行講解。
（5） 刪除了附錄A的考試試題，將試題及其答案作為配套資源提供。
通過上述修改，希望教師和學生更喜歡本教材，也希望本教材信息容量大、知識性強的特色能夠很好地得到延續。
為便於教學，本書提供豐富的配套資源，包括教學大綱、教學課件、電子教案、程序源碼、習題答案和微課視頻。本書配套的視頻二維碼位置如表1所示。
表1視頻二維碼位置
序號
視頻內容標題
視頻二維碼位置
所在頁碼
1
U2鏈表
2 3線性表的鏈式存儲和實現24
2
U3中綴表達式轉後綴表達式
3 4 3表達式求值57
3
U4 KMP
4 2 2KMP演算法72
4
U5隊列實現二叉樹的層次遍歷
5 2 4二叉樹的遍歷95
5
U5哈夫曼樹
5 3哈夫曼樹及哈夫曼編碼103
6
U5由二叉樹的前序遍歷和中序遍歷還原樹
5 5 3從前序遍歷和中序遍歷構造二叉樹110
7
U6迪傑斯特拉
6 5 1求某個頂點到其餘頂點的最短路徑133
8
U6拓撲排序
6 6拓撲排序和關鍵路徑135
9
U7快速排序
7 3 2快速排序153
10
U7歸併排序
7 5歸併排序160
11
U7實驗題3——鏈表歸併排序
7 6 3鏈表排序（進階）166
12
U8快慢指針查找重複數——理論
8 5 2查找重複數186
13
U8快慢指針查找重複數——代碼
8 5 2查找重複數186
資源下載提示
課件等資源： 掃描封底的「課件下載」二維碼，在公眾號「書圈」下載。
數據文件等資源： 掃描目錄上方的二維碼下載。
視頻等資源： 掃描封底的文泉雲盤防盜碼，再掃描書中相應章節的二維碼，可以在線學習。
本書的作者為呂雲翔、郭穎美、王子豪，曾洪立參与了部分內容的編寫並進行了素材整理及配套資源製作等。
最後，請讀者不吝賜教，及時提出寶貴意見。
編者
2023年5月
前言
隨著近年來計算概念的快速發展，計算學科已經發展成為一個內涵繁雜的綜合性學科，其至少可以劃分為計算機工程(CE)、計算機科學(CS)、信息系統(IS)、信息技術(IT)和軟體工程(SE)5個領域，而且不同領域的人才所應具備的知識結構與能力側重也不盡相同。儘管如此，從目前已經完成的部分來看，數據結構在各領域的知識體系中仍然佔據著重要的位置。「數據結構」是普通高等院校計算機和信息管理等專業的一門必修課程，主要討論數據的邏輯結構、在計算機中的存儲結構以及對其進行的各種處理運算的方法和演算法。
N Wirth早在20世紀70年代就指出「程序=數據結構+演算法」。數據結構主要研究數據在計算機中存儲、組織、傳遞和轉換的過程及方法，這些也是構成與支撐演算法的基礎。近年來，隨著面向對象技術的廣泛應用，從數據結構的定義、分類、組成到設計、實現與分析的模式和方法都有了長足的發展，現代數據結構更加註重和強調數據結構的整體性、通用性、復用性、簡潔性和安全性。
為遵循上述原則，本書選擇Java作為描述語言，因為相對於其他語言，Java程序設計語言是應用最廣泛、面向對象程度化最高的語言，利用Java語言中的類和介面能夠準確地描述任何一種數據結構的邏輯定義和運算，利用一種存儲結構定義的派生類能夠高效地實現對數據的運算。
在內容的選取與結構上，本書並未涉及各種數據結構，而是通過分類和講解典型結構使讀者形成對數據結構的宏觀認識。根據內容的側重，本書共分8章，分別為緒論、線性表、棧和隊列、串和數組、樹結構、圖、排序和查找。
第1章介紹數據結構的基本概念，演算法的描述和演算法時間複雜度、空間複雜度等內容，是全書的基礎。
第2章主要介紹線性表的基本概念和抽象數據類型定義、線性表順序和鏈式兩種存儲方式的表示、基本操作的實現和相應的應用。
第3章簡要介紹棧和隊列的基本概念和抽象數據類型定義、棧和隊列在順序存儲和鏈式存儲結構下的基本操作和應用。
第4章主要介紹串的基本概念和數據類型定義、串的存儲結構、基本操作實現和應用等內容。
第5章主要介紹樹和二叉樹的基本概念，詳細介紹二叉樹的性質和存儲結構、遍歷方法的實現及應用、哈夫曼樹的概念和構造方法。
第6章主要介紹圖的基本概念、抽象數據類型定義、存儲結構和遍歷方法，還介紹最小生成樹的基本概念和演算法、最短路徑的相關演算法、拓撲排序的概念和實現方法。
第7章介紹排序的基本概念，插入排序、交換排序、選擇排序、歸併排序等多種排序的原理、實現方法及性能分析。
第8章主要介紹查找的基本概念，順序查找、二分查找等查找的原理、實現方法和性能分析，平衡二叉樹、哈希表的概念、結構定義和實現方法。
本書理論知識的教學安排建議如下：
第一章節內容學時數
第1章緒論2
第2章線性表4~6
第3章棧和隊列6~8
第4章串和數組2~4
第5章樹結構6~8
第6章圖4~8
第7章排序4~6
第8章查找4~6
建議先修課程： Java語言
建議理論教學時數： 32~48學時
建議實驗(實踐)教學時數： 16~32學時
本書中的所有演算法都已經通過上機調試，盡量確保演算法的正確性。在每章內容后都有小結，便於讀者複習總結，並配有豐富的習題，包括選擇題、填空題、演算法設計題等，給讀者更多思考的