数据结构（Python语言描述）

着重介绍了数据结构的逻辑特性和物理表示法。

遵循循序渐进、前后衔接原则，便于理解掌握。

用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. 民用航空飞机标准线路施工 [主编　王志敏　陈明]
3. 不息的水脉—大运河讲谈录 [赵珩　著]
4. 实用运筹学 [主编　邢育红　于晋臣]
5. 三峡梯级电站水资源决策支持系统研究与开发 [姚华明 潘红忠 汤正]
6. 海南黎族民俗文化鉴赏 [庞国华　著]
7. 石墨烯在太赫兹及中红外频段电磁器件设计中的应用 [李艳秀 庄华伟 著]
8. 电子技术（第二版） [主编 覃爱娜 李飞]
9. 办公自动化高级应用 [陈萍 朱晓玉]
10. 信息处理技术员考试32小时通关 [薛大龙]
11. 电子产品设计案例教程（微课版）—基于嘉立创EDA（专业版） [王静 莫志宏 陈学昌 丁红]
12. C程序设计实践教程 [刘卫国]
13. C程序设计（慕课版） [刘卫国]
14. Web技术开发教程（基于.NET开源MVC框架） [王合闯 韩红玲 王青正 陈海蕊]
15. 商务英语翻译教程（笔译）（第四版） [主编 王军平]
16. 智慧零售技术与应用 [洪旭 著]
17. 建设工程法规实务 [主编 余滢]
18. 商务秘书理论与实务（第三版） [主编 张同钦]
19. 程序设计基础实践教程（C/C++语言版） [张桂芬 葛丽娜]
20. C++案例项目精讲 [主编 杨国兴]
21. 劳动争议处理实务 [主编 王秀卿 罗静]
22. 工程数学 [主编 郭立娟 王海]
23. 语音识别理论与实践 [主编　莫宏伟]
24. 信息系统项目管理师章节习题与考点特训（第二版） [主编 薛大龙]
25. 武术基础教程 [主编 李代勇 谢志民]
26. 计算机网络实训教程 [主编 张浩军 赵玉娟]
27. 画法几何与机械制图习题集（多学时） [主编 赵军]
28. HCIA-Datacom认证题库分类精讲 [主 编 韩立刚]
29. SwiftUI完全开发 [李智威 著]
30. 网络规划设计师备考一本通 [夏杰 编著]