第1章  數據結構與算法概述
1.1  為什麼要學習數據結構
1.2  基本概念和術語
1.3  數據的邏輯結構與存儲結構
1.3.1  邏輯結構
1.3.2  存儲結構
1.4  抽像數據類型及其描述
1.4.1  什麼是抽像數據類型
1.4.2  抽像數據類型的描述
1.5  算法
1.5.1  數據結構與算法的關繫
1.5.2  什麼是算法
1.5.3  算法的五大特性
1.5.4  算法的描述
1.6  算法分析
1.6.1  算法設計的4個目標
1.6.2  算法效率評價
1.6.3  算法時間復雜度
1.6.4  算法的空間復雜度
1.7  學好數據結構的秘訣
1.8  習題
第2章  線性表
2.1  線性表的概念及運算
2.1.1  線性表的邏輯結構
2.1.2  線性表的抽像數據類型
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.3.4  循環單鏈表
2.3.5  雙向鏈表
2.5 &nbs多項式的表示與相乘
2.5.1 &nbs多項式的表示
2.5.2 &nbs多項式相乘
2.6  小結
第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.3  棧與遞歸
3.3.1  遞  歸
3.3.2  消除遞歸
3.4  隊列的表示與實現
3.4.1  隊列的定義
3.4.2  隊列的抽像數據類型
3.4.3  順序隊列
3.4.4  順序循環隊列
3.4.5  雙端隊列
3.4.6  鏈式隊列
3.5  隊列的應用
3.5.1  隊列在楊輝三角中的應用
3.5.2  隊列在回文中的應用
3.6  小  結
第4章  串、數組與廣義表
4.1  串的定義及抽像數據類型
4.1.1  什麼是串
4.1.2  串的抽像數據類型
4.2  串的存儲表示
4.2.1  串的順序存儲結構
4.2.2  串的鏈式存儲結構
4.2.3  順序串應用舉例
4.3  串的模式匹配
4.3.1  樸素模式匹配算法——模式匹配算法Brute-Force
4.3.2  KMP算法
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.4  廣義表的擴展線性鏈表表示
4.6  小結
第5章  樹
5.1  樹
5.1.1  樹的定義
5.1.2  樹的邏輯表示
5.1.2  樹的抽像數據類型
5.2  二叉樹
5.2.1  二叉樹的定義
5.2.2  二叉樹的性質
5.2.3  二叉樹的抽像數據類型
5.2.4  二叉樹的存儲表示
5.3  二叉樹的遍歷
5.3.1  二叉樹遍歷的定義
5.3.2  二叉樹的先序遍歷
5.3.3  二叉樹的中序遍歷
5.3.4  二叉樹的後序遍歷
5.4  二叉樹的線索化
5.4.1  二叉樹的線索化定義
5.4.2  二叉樹的線索化
5.4.3  線索二叉樹的遍歷
5.4.4  線索二叉樹的應用舉例
5.5  樹、森林與二叉樹
5.5.1  樹的存儲結構
5.5.2  樹轉換為二叉樹
5.5.3  森林轉換為二叉樹
5.5.4  二叉樹轉換為樹和森林
5.5.5  樹和森林的遍歷
5.6  哈夫曼樹
5.6.1  哈夫曼樹的定義
5.6.2  哈夫曼編碼
5.6.3  哈夫曼編碼算法的實現
5.7  小  結
習  題
第6章  圖
6.1  圖的定義與相關概念
6.1.1  圖的定義
6.1.2  圖的相關概念
6.1.3  圖的抽像數據類型
6.2  圖的存儲結構
6.2.1  鄰接矩陣表示法
6.2.2  鄰接表表示法
6.2.3  十字鏈表
6.2.4  鄰接多重表
6.3  圖的遍歷
6.3.1  圖的深度優先遍歷
6.3.2  圖的廣度優先遍歷
6.4  圖的連通性問題
6.4.1  無向圖的連通分量與生成樹
6.4.2  小生成樹
6.5  有向無環圖
6.5.1  AOV網與拓撲排序
6.5.2  AOE網與關鍵路徑
6.6  短路徑
6.6.1  從某個頂點到其餘各頂點的短路徑
6.6.2  每一對頂點之間的短路徑
6.7  圖的應用舉例
6.7.1  距離某個頂點的短路徑長度為k的所有頂點
6.7.2  求圖中頂點u到頂點v的簡單路徑
6.8  小結
第7章  查找
7.1  查找的基本概念
7.2  靜態查找
7.2.1  順序表的查找
7.2.2  有序順序表的查找
7.2.3  索引順序表的查找
7.3  動態查找
7.3.1  二叉排序樹
7.3.2  平衡二叉樹
7.4  B-樹與B 樹
7.4.1  B-樹
7.4.2  B 樹
7.5  哈希表
7.5.1  哈希表的定義
7.5.2  哈希函數的構造方法
7.5.3  處理衝突的方法
7.5.4  哈希表應用舉例
7.6  小  結
第8章  排序
8.1  排序的基本概念
8.2  插入排序
8.2.1  直接插入排序
8.2.2  折半插入排序
8.2.3  希爾排序
8.2.4  插入排序應用舉例
8.3  選擇排序
8.3.1  簡單選擇排序
8.3.2  堆排序
8.4  交換排序
8.4.1  冒泡排序
8.4.2  快速排序
8.4.3  交換排序應用舉例
8.5  歸並排序
8.6  基數排序
8.6.1  基數排序算法
8.6.2  基數排序應用舉例
8.7  小  結
參考文獻

數據結構是高等院校計算機科學與技術、軟件工程、大數據、人工智能等專業的一門重要的專業基礎課程，是算法設計與分析、人工智能、機器學習、編譯原理等眾多後續課程的重要基礎，它對軟件開發具有舉足輕重的作用。目前，在使用計算機的各種軟件時，都需要處理各種數據，而這些軟件的設計都需要研究數據之間關繫的表示與處理，這正是數據結構的研究內容。數據結構是計算機、軟件工程大多數專業課程的核心基礎，直接決定著其他專業課程的學習效果。通過學習數據結構，可為算法設計和軟件開發等方面課程的學習打下堅實的知識基礎。

本書比較繫統地介紹數據結構中的線性結構、樹形結構、圖結構及查找、排序技術，闡述各種數據結構的邏輯關繫，討論它們在計算機中的存儲表示及其運算。本書理論與實踐並重，結合教學工作實際，除了對數據結構中的抽像概念和數據類型的基本運算進行詳細講解外，還通過豐富的圖表和實例、完整的代碼講解算法的應用，幫助讀者理解每種數據類型常見的基本操作及其具體應用案例的算法思想，使其學會運用數據結構知識解決日常生活中的實際問題。本書主張通過算法實現來強化對算法的理解，因此，不僅精選了一些涵蓋知識點豐富且具有代表性的案例，還挑選了部分歷年考研試題作為課後習題，所有算法均采用Python語言給出完整實現，方便讀者學習和理解，從而鞏固所學知識點。

由於Python語言強大的第三方工具庫、開發速度快捷、擅長數據分析與處理等優勢，被廣泛應用於人工智能、機器學習、大數據分析與處理，且已成為主流的開發語言之一，是數據分析與處理的工具。國內各高校均開設了Python語言程序設計課程，因此，本書采用Python語言作為描述語言，也為讀者學習人工智能、機器學習、大數據分析與處理打下牢固的基礎。

本書內容

本書共分為8章，內容分別為數據結構與算法概述，線性表，棧與隊列，串、數組與廣義表，樹，圖，查找和排序。

第1章：如果讀者剛接觸數據結構，這一章將告訴你數據結構是什麼，以及本書的學習目標、學習方法和學習內容。另外，還介紹了本書對算法的描述方法。

第2章：主要介紹線性表。首先講解線性表的邏輯結構，然後介紹線性表的各種常用存儲結構，在每一節均給出了算法的具體應用。通過學習本章內容，讀者可以掌握順序表、動態鏈表的基本操作及應用。

第3章：主要介紹操作受限的線性表——棧和隊列，內容包括棧的定義，棧的基本操作及棧與遞歸的轉化，隊列的概念，順序隊列和鏈式隊列的運算。

第4章：主要介紹串、數組與廣義表。串是另一種特殊的線性表，數組和隊列可看作是線性表的推廣。首先介紹串的概念、串的各種存儲表示及串的模式匹配算法，然後介紹數組的概念、數組（矩陣）的存儲結構及運算、特殊矩陣，後介紹廣義表的概念、表示與存儲方式。

第5章：主要介紹非線性數據結構——樹和二叉樹。首先介紹樹和二叉樹的概念，然後介紹樹和二叉樹的存儲表示、二叉樹的性質、二叉樹的遍歷和線索化、樹、森林與二叉樹的轉換及哈夫曼樹。

第6章：主要介紹非線性數據結構——圖。首先介紹圖的概念和存儲結構，然後介紹圖的遍歷、小生成樹、拓撲排序、關鍵路徑及短路徑。

第7章：主要介紹數據結構的常用技術——查找。首先介紹查找的概念，然後結合具體實例介紹各種查找算法，並給出完整的實現代碼。

第8章：主要介紹數據結構的常用技術——排序。首先介紹排序的相關概念，然後介紹各種排序技術，並給出具體的實現算法。

配套源碼、PPT課件、教學視頻等下載

本書提供配套的教學資源，包括教學視頻、電子課件、示例代碼、習題答案等。讀者可用微信掃描下面二維碼下載。如果發現問題或者有任何建議，可通過郵件與作者聯繫，，郵件主題寫“Python數據結構與算法”。

本書作者與鳴謝

參與本書編寫的有孫玉勝、陳銳、張志鋒、崔建濤、鄭倩、劉育熙、桑永宣。

在本書的出版過程中，得到了鄭州輕工業大學和清華大學出版社的大力支持，在此表示衷心感謝。尤其感謝清華大學出版社的編輯們對於本書順利出版所做的辛勤工作。

在本書編寫的過程中，參閱了大量的相關教材、著作，個別案例也參考了網絡資源，在此向各位原著者致敬！

由於作者水平有限，書中難免存在一些不足之處，懇請讀者批評指正。

編  者   

2022年9月