著重介紹了數(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)行問題求解的重要基礎(chǔ)。在各高等學(xué)校，自動(dòng)化、交通運(yùn)輸工程、數(shù)字出版、物流管理等很多專業(yè)都開設(shè)了數(shù)據(jù)結(jié)構(gòu)課程。Python語(yǔ)言語(yǔ)法簡(jiǎn)潔、交互性強(qiáng)，本書用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ì)問題。解決同一問題往往有很多種方法，且不同方法之間的效率可能相差甚遠(yuǎn)，而解決問題的方法與效率，實(shí)質(zhì)上與數(shù)據(jù)的組織方式、存儲(chǔ)結(jié)構(gòu)密切相關(guān)。本書遵循由易到難、循序漸進(jìn)、前后銜接自然的原則，將問題脈絡(luò)交代清楚，便于讀者理解掌握各種數(shù)據(jù)結(jié)構(gòu)的實(shí)質(zhì)。本書著重介紹了各種結(jié)構(gòu)的邏輯特性和物理表示法，定義了相應(yīng)的算法，并用Python語(yǔ)言作為算法實(shí)現(xiàn)工具。書中的各種算法是用Python函數(shù)編寫的，只需要按照Python函數(shù)調(diào)用規(guī)則調(diào)用，就可上機(jī)執(zhí)行。

本書共分為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章介紹樹，樹是一種非常重要的非線性結(jié)構(gòu)，具有很強(qiáng)的實(shí)用性；第6章介紹圖，圖是比樹更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，在這一章中討論了圖的表示及相關(guān)應(yīng)用；第7章介紹排序，包括各種經(jīng)典的排序算法；第8章介紹散列，重點(diǎn)對(duì)經(jīng)典散列映射技術(shù)進(jìn)行了討論。

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

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

編 者

2022年8月

第1章　緒論 1
1.1　幾個(gè)簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)問題 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　文件的打開與關(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章　樹 111
5.1　樹的定義及相關(guān)術(shù)語(yǔ) 111
5.2　二叉樹 113
5.2.1　二叉樹的定義 114
5.2.2　二叉樹的性質(zhì) 114
5.2.3　二叉樹的存儲(chǔ)結(jié)構(gòu) 117
5.2.4　遍歷二叉樹 120
5.2.5　線索二叉樹 127
5.3　樹、森林和二叉樹 131
5.3.1　樹與二叉樹轉(zhuǎn)換 131
5.3.2　森林與二叉樹轉(zhuǎn)換 133
5.4　樹的應(yīng)用 135
5.4.1　二叉排序樹 135
5.4.2　平衡二叉樹 141
5.4.3　哈夫曼樹 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　最小生成樹 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　開放定址法 221
8.4.2　鏈接法 223
8.5　散列表的查找 225
習(xí)題 227
參考文獻(xiàn) 230

1. 輸水管線工程風(fēng)險(xiǎn)管理 [張勇 黨亥生 著]
2. 民用航空飛機(jī)標(biāo)準(zhǔn)線路施工 [主編　王志敏　陳明]
3. 不息的水脈—大運(yùn)河講談錄 [趙珩　著]
4. 實(shí)用運(yùn)籌學(xué) [主編　邢育紅　于晉臣]
5. 三峽梯級(jí)電站水資源決策支持系統(tǒng)研究與開發(fā) [姚華明 潘紅忠 湯正]
6. 海南黎族民俗文化鑒賞 [龐國(guó)華　著]
7. 石墨烯在太赫茲及中紅外頻段電磁器件設(shè)計(jì)中的應(yīng)用 [李艷秀 莊華偉 著]
8. 電子技術(shù)（第二版） [主編 覃愛娜 李飛]
9. 辦公自動(dòng)化高級(jí)應(yīng)用 [陳萍 朱曉玉]
10. 信息處理技術(shù)員考試32小時(shí)通關(guān) [薛大龍]
11. 電子產(chǎn)品設(shè)計(jì)案例教程（微課版）—基于嘉立創(chuàng)EDA（專業(yè)版） [王靜 莫志宏 陳學(xué)昌 丁紅]
12. C程序設(shè)計(jì)實(shí)踐教程 [劉衛(wèi)國(guó)]
13. C程序設(shè)計(jì)（慕課版） [劉衛(wèi)國(guó)]
14. Web技術(shù)開發(fā)教程（基于.NET開源MVC框架） [王合闖 韓紅玲 王青正 陳海蕊]
15. 商務(wù)英語(yǔ)翻譯教程（筆譯）（第四版） [主編 王軍平]
16. 智慧零售技術(shù)與應(yīng)用 [洪旭 著]
17. 建設(shè)工程法規(guī)實(shí)務(wù) [主編 余瀅]
18. 商務(wù)秘書理論與實(shí)務(wù)（第三版） [主編 張同欽]
19. 程序設(shè)計(jì)基礎(chǔ)實(shí)踐教程（C/C++語(yǔ)言版） [張桂芬 葛麗娜]
20. C++案例項(xiàng)目精講 [主編 楊國(guó)興]
21. 勞動(dòng)爭(zhēng)議處理實(shí)務(wù) [主編 王秀卿 羅靜]
22. 工程數(shù)學(xué) [主編 郭立娟 王海]
23. 語(yǔ)音識(shí)別理論與實(shí)踐 [主編　莫宏偉]
24. 信息系統(tǒng)項(xiàng)目管理師章節(jié)習(xí)題與考點(diǎn)特訓(xùn)（第二版） [主編 薛大龍]
25. 武術(shù)基礎(chǔ)教程 [主編 李代勇 謝志民]
26. 計(jì)算機(jī)網(wǎng)絡(luò)實(shí)訓(xùn)教程 [主編 張浩軍 趙玉娟]
27. 畫法幾何與機(jī)械制圖習(xí)題集（多學(xué)時(shí)） [主編 趙軍]
28. HCIA-Datacom認(rèn)證題庫(kù)分類精講 [主 編 韓立剛]
29. SwiftUI完全開發(fā) [李智威 著]
30. 網(wǎng)絡(luò)規(guī)劃設(shè)計(jì)師備考一本通 [夏杰 編著]