數(shù)據(jù)結(jié)構(gòu)（Python語(yǔ)言描述）

著重介紹了數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示法。

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

用Python 語(yǔ)言作為算法實(shí)現(xiàn)工具，可上機(jī)執(zhí)行。

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)通信類專業(yè)的重要學(xué)科基礎(chǔ)課，也是高層次利用計(jì)算機(jī)進(jìn)行問(wèn)題求解的重要基礎(chǔ)。在各高等學(xué)校，自動(dòng)化、交通運(yùn)輸工程、數(shù)字出版、物流管理等很多專業(yè)都開(kāi)設(shè)了數(shù)據(jù)結(jié)構(gòu)課程。Python語(yǔ)言語(yǔ)法簡(jiǎn)潔、交互性強(qiáng)，本書(shū)用Python語(yǔ)言來(lái)描述數(shù)據(jù)結(jié)構(gòu)與算法。

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

本書(shū)共分為8章。第1章介紹數(shù)據(jù)結(jié)構(gòu)與算法的基本概念，重點(diǎn)介紹了抽象數(shù)據(jù)類型和算法復(fù)雜度的概念；第2章針對(duì)Python語(yǔ)言基礎(chǔ)應(yīng)用，介紹了Python語(yǔ)言的基本數(shù)據(jù)描述、程序的三種基本結(jié)構(gòu)、函數(shù)以及幾種復(fù)合數(shù)據(jù)類型，為后續(xù)章節(jié)進(jìn)行數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)做準(zhǔn)備；第3章介紹線性表，包括順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)的線性表及相關(guān)操作；第4章介紹棧、隊(duì)列和串，棧和隊(duì)列是線性表的兩種基本應(yīng)用，串是種特殊的線性表；第5章介紹樹(shù)，樹(shù)是一種非常重要的非線性結(jié)構(gòu)，具有很強(qiáng)的實(shí)用性；第6章介紹圖，圖是比樹(shù)更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，在這一章中討論了圖的表示及相關(guān)應(yīng)用；第7章介紹排序，包括各種經(jīng)典的排序算法；第8章介紹散列，重點(diǎn)對(duì)經(jīng)典散列映射技術(shù)進(jìn)行了討論。

本書(shū)由曹岳輝、劉衛(wèi)國(guó)、康松林編著，在本書(shū)編寫(xiě)過(guò)程中，得到了中南大學(xué)計(jì)算機(jī)基礎(chǔ)教學(xué)實(shí)驗(yàn)中心全體教師的大力支持，在此表示衷心的感謝。

由于編者學(xué)識(shí)水平有限，書(shū)中的疏漏在所難免，懇請(qǐng)廣大讀者批評(píng)指正。

編 者

2022年8月

第1章　緒論 1
1.1　幾個(gè)簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)問(wèn)題 1
1.2　數(shù)據(jù)結(jié)構(gòu) 4
1.2.1　什么是數(shù)據(jù)結(jié)構(gòu) 4
1.2.2　數(shù)據(jù)的邏輯結(jié)構(gòu) 4
1.2.3　數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 5
1.2.4　抽象數(shù)據(jù)類型 7
1.3　算法 8
1.3.1　算法的定義 8
1.3.2　算法的時(shí)間復(fù)雜度 9
1.3.3　算法的空間復(fù)雜度 11
習(xí)題 12
第2章　Python語(yǔ)言基礎(chǔ) 15
2.1　Python語(yǔ)言簡(jiǎn)介 15
2.2　Python的數(shù)據(jù)描述 16
2.2.1　變量與賦值 16
2.2.2　Python數(shù)據(jù)類型 17
2.2.3　常用系統(tǒng)函數(shù) 20
2.2.4　基本運(yùn)算與表達(dá)式 21
2.3　Python程序流程控制 23
2.3.1　順序結(jié)構(gòu) 23
2.3.2　選擇結(jié)構(gòu) 25
2.3.3　循環(huán)結(jié)構(gòu) 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　函數(shù) 38
2.6.1　函數(shù)的定義與調(diào)用 38
2.6.2　兩類特殊函數(shù) 39
2.7　文件操作 41
2.7.1　文件的打開(kāi)與關(guān)閉 41
2.7.2　文本文件的操作 42
習(xí)題 43
第3章　線性表 48
3.1　線性表的基本概念 48
3.1.1　什么是線性表 48
3.1.2　線性表的概念及其抽象數(shù)據(jù)類型 49
3.1.3　線性表的基本運(yùn)算 49
3.2　線性表的順序結(jié)構(gòu) 50
3.2.1　順序表 51
3.2.2　順序表的建立 51
3.2.3　順序表的基本操作 52
3.2.4　順序表應(yīng)用案例 54
3.3　線性表的鏈?zhǔn)浇Y(jié)構(gòu) 55
3.3.1　鏈表的定義和特點(diǎn) 55
3.3.2　鏈表的種類 55
3.3.3　單鏈表的建立 57
3.3.4　單鏈表的基本操作 58
3.3.5　雙鏈表 61
3.3.6　循環(huán)鏈表 64
3.3.7　單鏈表的應(yīng)用 69
習(xí)題 69
第4章　棧、隊(duì)列和串 73
4.1　棧 73
4.1.1　棧的概念及其抽象數(shù)據(jù)類型 73
4.1.2　棧的順序存儲(chǔ) 75
4.1.3　棧的鏈?zhǔn)酱鎯?chǔ) 79
4.1.4　棧的應(yīng)用 82
4.2　隊(duì)列 85
4.2.1　隊(duì)列的概念及其抽象數(shù)據(jù)類型 85
4.2.2　隊(duì)列的順序存儲(chǔ) 87
4.2.3　隊(duì)列的鏈?zhǔn)酱鎯?chǔ) 92
4.2.4　隊(duì)列的應(yīng)用 96
4.3　串 98
4.3.1　串的概念及其抽象數(shù)據(jù)類型 98
4.3.2　串的實(shí)現(xiàn) 100
4.3.3　串的模式匹配 102
習(xí)題 108
第5章　樹(shù) 111
5.1　樹(shù)的定義及相關(guān)術(shù)語(yǔ) 111
5.2　二叉樹(shù) 113
5.2.1　二叉樹(shù)的定義 114
5.2.2　二叉樹(shù)的性質(zhì) 114
5.2.3　二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 117
5.2.4　遍歷二叉樹(shù) 120
5.2.5　線索二叉樹(shù) 127
5.3　樹(shù)、森林和二叉樹(shù) 131
5.3.1　樹(shù)與二叉樹(shù)轉(zhuǎn)換 131
5.3.2　森林與二叉樹(shù)轉(zhuǎn)換 133
5.4　樹(shù)的應(yīng)用 135
5.4.1　二叉排序樹(shù) 135
5.4.2　平衡二叉樹(shù) 141
5.4.3　哈夫曼樹(shù) 145
習(xí)題 151
第6章　圖 155
6.1　圖的基本概念 155
6.1.1　圖的定義 155
6.1.2　圖的基本術(shù)語(yǔ) 156
6.1.3　圖的抽象數(shù)據(jù)類型定義 159
6.2　圖的存儲(chǔ)結(jié)構(gòu) 160
6.2.1　圖的鄰接矩陣 160
6.2.2　圖的鄰接表 163
6.2.3　圖在Python中的實(shí)現(xiàn) 165
6.3　圖的遍歷 166
6.3.1　深度優(yōu)先搜索 167
6.3.2　廣度優(yōu)先搜索 168
6.4　圖的應(yīng)用 169
6.4.1　最小生成樹(shù) 169
6.4.2　最短路徑 177
6.4.3　拓?fù)渑判?181
6.4.4　關(guān)鍵路徑 183
習(xí)題 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　簡(jiǎn)單選擇排序 199
7.4.2　堆排序 200
7.5　歸并排序 204
7.6　基數(shù)排序 205
7.7　各種排序比較 207
習(xí)題 208
第8章　散列 213
8.1　查找 213
8.1.1　查找的基本概念 213
8.1.2　順序查找 214
8.1.3　索引查找 216
8.2　散列的基本概念 218
8.3　散列函數(shù)的構(gòu)造 219
8.4　解決沖突的方法 221
8.4.1　開(kāi)放定址法 221
8.4.2　鏈接法 223
8.5　散列表的查找 225
習(xí)題 227
參考文獻(xiàn) 230

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