第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

第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數字加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.1尋找圖中是否存在路徑

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實踐題

第2章線性表

第3章棧和隊列

第4章串和數組

第5章樹結構

第6章圖

第7章排序

第8章查找

參考文獻

《數據結構（Python版）》於2019年4月正式出版以來，經過了幾次印刷，許多高等學校已將其作為“數據結構”課程的教材。本書不僅深受這些學校師生的鐘愛，而且也獲得了良好的社會效益。但從另外一個角度來看，作者有責任和義務維護好這本書的質量，及時更新本書的內容，做到與時俱進。

 本書修訂內容如下。

（1） 重新對每章內容進行了梳理。

（2） 第2～8章中，每章都增加了實驗題及其解答，便於提高讀者動手能力。

（3） 針對每章章後的應用題，重新對程序進行了運行和調試，使習題答案準確無誤。

（4） 針對每章的重點或難點的算法和實驗，配置了微課視頻進行講解。

（5） 刪去了附錄A的考試試題，而是將試題及其答案作為教輔資源，供讀者下載。

希望通過這樣的修訂，讓更多的教師和學生喜歡本書，也希望本書信息容量大、知識性強的特色能夠很好地延續下去。

本書的作者為呂雲翔、郭穎美、孟爻、吳宜航、楊壯，曾洪立參與了部分內容的編寫並進行了素材整理及配套資源制作等。

書中如有不當，請讀者不吝賜教，及時提出寶貴意見。

作者
2023年3月

第1版前言

隨著近年來計算概念的快速拓展，計算科學已經發展成為一個內涵繁雜的綜合性學科，其至少可以劃分為計算機工程（CE）、計算機科學（CS）、信息繫統（IS）、信息技術（IT）和軟件工程（SE）5個領域，而且不同領域的人纔所應具備的知識結構與能力側重也不盡相同。盡管如此，數據結構在各領域的知識體繫中仍然占據著重要的位置。“數據結構”是普通高等學校計算機專業和信息管理專業的一門必修課程，主要討論數據的邏輯結構、在計算機中的存儲結構以及對其進行的各種處理運算的方法和算法。

N.Wirth早在20世紀70年代就指出“程序=數據結構 算法”。數據結構主要研究數據在計算機中存儲、組織、傳遞和轉換的過程及方法，這些也是構成與支撐算法的基礎。近年來，隨著面向對像技術的廣泛應用，從數據結構的定義、分類、組成到設計、實現與分析的模式和方法都有了長足的發展，現代數據結構更加注重和強調數據結構的整體性、通用性、復用性、間接性和安全性。

基於上述情況，本書選擇Python作為描述語言。Python語言語法簡潔優美，功能強大，有著廣泛的應用領域，如互聯網、大數據、人工智能等領域。因此，學習Python語言，在未來的學習和工作中，都有用武之地。同時，Python語言相對於大多數高級語言，更加適合初學者學習，Python的語法與偽代碼描述很相似，邏輯清晰； 此外，Python語言也同樣具有大部分高級語言的特性，對計算機相關專業的學生未來學習其他編程語言有所幫助。

在內容的選取與結構安排上，本書通過分類和講解典型結構使讀者對數據結構形成宏觀認識。根據內容的側重，本書分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

建議先修課程： Python語言。

建議理論教學時數： 32~48學時。

建議實驗（實踐）教學時數： 16~32學時。

本書中的所有算法都已經通過上機調試，盡量保證算法的正確性。在每章內容後都有小結，便於讀者復結，並配有豐富的習題，包括選擇題、填空題、算法設計題等，給讀者更多的思考空間。

本書在以下幾方面具有突出特色。

（1） 內容精煉，強化基礎，合理安排內容結構，做到深入淺出、循序漸進。

本書各章節都從基本概念入手，逐步介紹其特點和基本操作的實現，把重點放在基礎知識的介紹上，縮減難度較大的內容，使理論敘述簡潔明了、重點突出、詳略得當。

（2） 應用實例豐富、完整。

本書通過豐富的應用實例和源代碼使理論和應用緊密結合，增強學生的理解能力，鍛煉程序設計思維。代碼有詳細明了的注釋，易於閱讀。

（3） 每章後面附有小結和習題，便於學習、總結和提高。

本書結合學生的學習實際選擇難度適中、邏輯合理、適於初學者和進階者開拓思路、深入了解數據結構使用方法和技巧的習題，並附有詳細的解答過程和注意要點，達到通俗易懂、深入淺出的效果，培養讀者遷移知識的能力。

（4） 采用Python抽像類體現方法的通用性。

本書采用面向對像的觀點討論數據結構技術，先將抽像數據類型定義成接口，再結合具體的存儲結構加以實現，並以各實現類為線索對類中各種操作的實現方法加以說明。

（5） 圖文並茂，便於讀者直觀地理解數據結構與算法。

本書通過圖表的方式對數據結構及相應操作進行簡單直接的描述，使內容更加淺顯易懂。

教師可以按照自己對數據結構的理解適當地跳過一些章節，也可以根據教學目標靈活地調整章節的順序，增減各章的學時數。

本書的作者為呂雲翔、郭穎美、孟爻，曾洪立、呂彼佳、姜彥華參與了部分內容的編寫並進行了素材整理及配套資源制作等。

由於數據結構本身還在探索之中，加上作者的水平和能力有限，書中難免有疏漏之處，懇請各位同仁和廣大讀者給予批評指正，也希望各位能將實踐過程中的經驗和心得與作者交流。

作者
2019年1月