著重介紹了數據結構的邏輯特性和物理表示法。

遵循循序漸進、前后銜接原則，便于理解掌握。

用Python 語言作為算法實現工具，可上機執行。

數據結構是計算機通信類專業的重要學科基礎課，也是高層次利用計算機進行問題求解的重要基礎。在各高等學校，自動化、交通運輸工程、數字出版、物流管理等很多專業都開設了數據結構課程。Python語言語法簡潔、交互性強，本書用Python語言來描述數據結構與算法。

數據結構主要研究的是現實世界中數據的各種邏輯結構，在計算機中的存儲結構以及定義這種邏輯結構、實現存儲結構的各種操作的算法設計問題。解決同一問題往往有很多種方法，且不同方法之間的效率可能相差甚遠，而解決問題的方法與效率，實質上與數據的組織方式、存儲結構密切相關。本書遵循由易到難、循序漸進、前后銜接自然的原則，將問題脈絡交代清楚，便于讀者理解掌握各種數據結構的實質。本書著重介紹了各種結構的邏輯特性和物理表示法，定義了相應的算法，并用Python語言作為算法實現工具。書中的各種算法是用Python函數編寫的，只需要按照Python函數調用規則調用，就可上機執行。

本書共分為8章。第1章介紹數據結構與算法的基本概念，重點介紹了抽象數據類型和算法復雜度的概念；第2章針對Python語言基礎應用，介紹了Python語言的基本數據描述、程序的三種基本結構、函數以及幾種復合數據類型，為后續章節進行數據結構的實現做準備；第3章介紹線性表，包括順序結構和鏈式結構的線性表及相關操作；第4章介紹棧、隊列和串，棧和隊列是線性表的兩種基本應用，串是種特殊的線性表；第5章介紹樹，樹是一種非常重要的非線性結構，具有很強的實用性；第6章介紹圖，圖是比樹更復雜的數據結構，在這一章中討論了圖的表示及相關應用；第7章介紹排序，包括各種經典的排序算法；第8章介紹散列，重點對經典散列映射技術進行了討論。

本書由曹岳輝、劉衛國、康松林編著，在本書編寫過程中，得到了中南大學計算機基礎教學實驗中心全體教師的大力支持，在此表示衷心的感謝。

由于編者學識水平有限，書中的疏漏在所難免，懇請廣大讀者批評指正。

編 者

2022年8月

第1章　緒論 1
1.1　幾個簡單的數據結構問題 1
1.2　數據結構 4
1.2.1　什么是數據結構 4
1.2.2　數據的邏輯結構 4
1.2.3　數據的存儲結構 5
1.2.4　抽象數據類型 7
1.3　算法 8
1.3.1　算法的定義 8
1.3.2　算法的時間復雜度 9
1.3.3　算法的空間復雜度 11
習題 12
第2章　Python語言基礎 15
2.1　Python語言簡介 15
2.2　Python的數據描述 16
2.2.1　變量與賦值 16
2.2.2　Python數據類型 17
2.2.3　常用系統函數 20
2.2.4　基本運算與表達式 21
2.3　Python程序流程控制 23
2.3.1　順序結構 23
2.3.2　選擇結構 25
2.3.3　循環結構 27
2.4　序列 29
2.4.1　序列的共性操作 29
2.4.2　字符串的常用方法 31
2.4.3　列表的操作 32
2.5　字典與集合 34
2.5.1　字典的操作 34
2.5.2　集合的操作 37
2.6　函數 38
2.6.1　函數的定義與調用 38
2.6.2　兩類特殊函數 39
2.7　文件操作 41
2.7.1　文件的打開與關閉 41
2.7.2　文本文件的操作 42
習題 43
第3章　線性表 48
3.1　線性表的基本概念 48
3.1.1　什么是線性表 48
3.1.2　線性表的概念及其抽象數據類型 49
3.1.3　線性表的基本運算 49
3.2　線性表的順序結構 50
3.2.1　順序表 51
3.2.2　順序表的建立 51
3.2.3　順序表的基本操作 52
3.2.4　順序表應用案例 54
3.3　線性表的鏈式結構 55
3.3.1　鏈表的定義和特點 55
3.3.2　鏈表的種類 55
3.3.3　單鏈表的建立 57
3.3.4　單鏈表的基本操作 58
3.3.5　雙鏈表 61
3.3.6　循環鏈表 64
3.3.7　單鏈表的應用 69
習題 69
第4章　棧、隊列和串 73
4.1　棧 73
4.1.1　棧的概念及其抽象數據類型 73
4.1.2　棧的順序存儲 75
4.1.3　棧的鏈式存儲 79
4.1.4　棧的應用 82
4.2　隊列 85
4.2.1　隊列的概念及其抽象數據類型 85
4.2.2　隊列的順序存儲 87
4.2.3　隊列的鏈式存儲 92
4.2.4　隊列的應用 96
4.3　串 98
4.3.1　串的概念及其抽象數據類型 98
4.3.2　串的實現 100
4.3.3　串的模式匹配 102
習題 108
第5章　樹 111
5.1　樹的定義及相關術語 111
5.2　二叉樹 113
5.2.1　二叉樹的定義 114
5.2.2　二叉樹的性質 114
5.2.3　二叉樹的存儲結構 117
5.2.4　遍歷二叉樹 120
5.2.5　線索二叉樹 127
5.3　樹、森林和二叉樹 131
5.3.1　樹與二叉樹轉換 131
5.3.2　森林與二叉樹轉換 133
5.4　樹的應用 135
5.4.1　二叉排序樹 135
5.4.2　平衡二叉樹 141
5.4.3　哈夫曼樹 145
習題 151
第6章　圖 155
6.1　圖的基本概念 155
6.1.1　圖的定義 155
6.1.2　圖的基本術語 156
6.1.3　圖的抽象數據類型定義 159
6.2　圖的存儲結構 160
6.2.1　圖的鄰接矩陣 160
6.2.2　圖的鄰接表 163
6.2.3　圖在Python中的實現 165
6.3　圖的遍歷 166
6.3.1　深度優先搜索 167
6.3.2　廣度優先搜索 168
6.4　圖的應用 169
6.4.1　最小生成樹 169
6.4.2　最短路徑 177
6.4.3　拓撲排序 181
6.4.4　關鍵路徑 183
習題 185
第7章　排序 189
7.1　排序的基本概念 189
7.2　插入排序 190
7.2.1　直接插入排序 190
7.2.2　二分插入排序 191
7.2.3　希爾排序 193
7.3　交換排序 194
7.3.1　冒泡排序 195
7.3.2　快速排序 196
7.4　選擇排序 198
7.4.1　簡單選擇排序 199
7.4.2　堆排序 200
7.5　歸并排序 204
7.6　基數排序 205
7.7　各種排序比較 207
習題 208
第8章　散列 213
8.1　查找 213
8.1.1　查找的基本概念 213
8.1.2　順序查找 214
8.1.3　索引查找 216
8.2　散列的基本概念 218
8.3　散列函數的構造 219
8.4　解決沖突的方法 221
8.4.1　開放定址法 221
8.4.2　鏈接法 223
8.5　散列表的查找 225
習題 227
參考文獻 230

1. 邊緣計算與智能視覺應用 [主編 林海 許華宇 徐卉]
2. 零基礎玩轉國產大模型DeepSeek [徐永冰 張帥 編著]
3. 網絡工程師5天修煉（適配第6版考綱） [主編　朱小平 施游]
4. 信息系統項目管理師考試32小時通關（適用第4版考綱） [薛大龍]
5. 信息系統管理工程師考試32小時通關（適配第2版考綱） [薛大龍　劉偉]
6. 土木工程材料檢測實訓 [洪曉江 達則曉麗 錢波]
7. 科技信息檢索與論文寫作實用教程 [李振華]
8. 傳統山水畫論解讀與實踐 [陳鈉 著]
9. Python數據庫編程 [主編 殷樹友 邢 翀]
10. 計算機基礎實訓指導 [主編 袁春萍 朱妮]
11. 嵌入式人工智能技術應用（數字教材） [主編 胡娜 楊國勇 晏廷榮]
12. Vienna整流器技術 [桂存兵 著]
13. 變頻器與伺服應用 [陳剛 葉云飛]
14. 物聯網工程設計與實踐 [湯琳 李敏]
15. 爐邊夜話——深入淺出話AI [汪建　著]
16. 電商運營與管理 [鐘肖英 陳瀟]
17. Java面向對象程序設計 [主編 姜春磊 陳虹潔]
18. 信息技術基礎（Windows 10+WPS Office）（微課版） [主編　石利平　田輝平　謝盛嘉]
19. 人工智能應用 [主編　陳　萍　劉培培　陳孟軍]
20. 大學生職業發展與就業指導 [主編　劉志堅]
21. 高級辦公應用項目教程 [主編 屈晶 趙成麗]
22. 微信小程序開發項目實戰（微課版） [主編 黃龍泉 郭峰 朱倩]
23. 企業檔案工作實戰寶典百問百答 [華俊 盧秀英 邵甜甜 著]
24. 計算機網絡原理及應用 [主編 唐繼勇 葉坤 孫夢娜]
25. 大學生創業基礎 [主編 王麗莉 王 楊]
26. 船舶輔機 [主編 王連海 于洋 姜淑翠]
27. 大學生就業指導 [主編 王麗莉 董宴廷]
28. 系統架構設計師章節習題與考點特訓 [主編 薛大龍 鄒月平]
29. 高校學生工作探索與實踐 [郭亮 著]
30. 大學生情商管理 [方雄 著]