目　录
第1　章
绪论　001
1.1　数据结构的研究内容.........................002
1.2　数据结构的基本概念和术语.............004
1.2.1　数据、数据元素、数据项和数据
对象.......................................................　004
1.2.2　数据结构...............................................　004
1.3　算法和算法分析.................................007
1.3.1　算法的定义及特性..............................　007
1.3.2　算法的描述...........................................　008
1.3.3　评价算法优劣的基本标准..................　009
1.3.4　算法的时间复杂度..............................　010
1.3.5　算法的空间复杂度..............................　013
1.4　小结......................................................014
习题...............................................................015
第2　章
线性表　018
2.1　线性表的定义和基本操作.................019
2.1.1　线性表的定义 .....................................　019
2.1.2　线性表的基本操作..............................　019
2.2　案例引入.............................................020
2.3　线性表的顺序表示和实现.................020
2.3.1　线性表的顺序表示 .............................　020
2.3.2　顺序表基本操作的实现......................　022
2.4　线性表的链式表示和实现.................026
2.4.1　单链表的定义和表示..........................　027
2.4.2　单链表基本操作的实现 .....................　029
2.4.3　循环链表...............................................　034
2.4.4　双向链表...............................................　035
2.5　顺序表和链表的比较.........................036
2.5.1　空间性能的比较..................................　037
2.5.2　时间性能的比较..................................　037
2.6　线性表的应用.....................................037
2.6.1　线性表的合并.......................................　037
2.6.2　有序表的合并.......................................　038
2.7　案例分析与实现.................................041
2.8　精选习题解析.....................................043
2.9　AI 协作实战........................................045
2.10　Python 标准库中的线性表................049
2.11　小结......................................................050
习题...............................................................051
第３章
栈和队列　054
3.1　栈和队列的定义及基本操作.............055
3.1.1　栈的定义和基本操作..........................　055
3.1.2　队列的定义和基本操作......................　055
3.2　案例引入.............................................056
3.3　栈的表示和实现.................................057
3.3.1　顺序栈的表示和实现..........................　057
目录
II　数据结构（Python 版）（第2 版）（附微课视频）
3.3.2　链栈的表示和实现..............................　059
3.4　栈与递归.............................................061
3.4.1　采用递归算法解决的问题..................　061
3.4.2　递归过程与递归工作栈......................　065
3.4.3　递归算法的效率分析..........................　067
3.5　队列的表示和实现.............................068
3.5.1　顺序队的表示和实现..........................　068
3.5.2　链队的表示和实现..............................　071
3.5.3　特殊队列...............................................　074
3.6　案例分析与实现.................................074
3.7　精选习题解析.....................................078
3.8　AI 协作实战........................................081
3.9　Python 标准库中的栈和队列............086
3.10　小结......................................................087
习题...............................................................088
第4　章
串和数组　091
4.1　串的定义.............................................092
4.2　案例引入.............................................092
4.3　串.........................................................093
4.3.1　串的存储结构 .....................................　093
4.3.2　串的模式匹配算法..............................　095
4.4　数组.....................................................103
4.4.1　数组的类型定义 .................................　103
4.4.2　数组的顺序存储 .................................　104
4.4.3　特殊矩阵的压缩存储 .........................　105
4.5　案例分析与实现.................................107
4.6　精选习题解析.....................................108
4.7　AI 协作实战........................................111
4.8　Python 标准库中的数组与字符串....114
4.8.1　数组.......................................................　114
4.8.2　字符串...................................................　116
4.9　小结......................................................117
习题...............................................................117
第5　章
树和二叉树　120
5.1　树和二叉树的定义及基本操作.........121
5.1.1　树的定义...............................................　121
5.1.2　树的基本术语.......................................　121
5.1.3　树的基本操作.......................................　122
5.1.4　二叉树的定义.......................................　123
5.1.5　二叉树的基本操作..............................　124
5.2　案例引入.............................................124
5.3　二叉树的性质和存储结构.................126
5.3.1　二叉树的性质.......................................　126
5.3.2　二叉树的存储结构..............................　127
5.4　遍历二叉树.........................................128
5.4.1　遍历二叉树的方法..............................　128
5.4.2　根据遍历序列确定二叉树..................　130
5.4.3　二叉树的创建.......................................　131
5.4.4　二叉树遍历算法的应用......................　132
5.5　树和森林.............................................134
5.5.1　树的存储表示法..................................　134
5.5.2　森林与二叉树的转换..........................　135
5.5.3　树和森林的遍历..................................　136
5.6　哈夫曼树及其应用.............................137
5.6.1　哈夫曼树的基本概念..........................　137
5.6.2　哈夫曼树的构造算法..........................　138
5.6.3　哈夫曼编码...........................................　140
5.7　案例分析与实现.................................142
5.8　精选习题解析.....................................143
5.9　AI 协作实战........................................146
5.10　Python 标准库中的堆........................150
5.11　小结......................................................152
习题...............................................................153
第6　章
图　156
6.1　图的定义和基本操作.........................157
目录III
6.1.1　图的定义...............................................　157
6.1.2　图的基本术语 .....................................　157
6.1.3　图的基本操作.......................................　159
6.2　案例引入.............................................159
6.3　图的存储结构.....................................160
6.3.1　邻接矩阵...............................................　160
6.3.2　邻接表 ..................................................　162
6.4　图的遍历.............................................165
6.4.1　深度优先遍历 .....................................　165
6.4.2　广度优先遍历 .....................................　168
6.5　图的应用.............................................169
6.5.1　最小生成树 .........................................　169
6.5.2　最短路径 .............................................　174
6.5.3　拓扑排序 .............................................　180
6.5.4　关键路径 .............................................　182
6.6　案例分析与实现.................................185
6.7　精选习题解析.....................................187
6.8　AI 协作实战........................................190
6.9　小结......................................................194
习题...............................................................196
第7　章
查找　199
7.1　查找的基本概念.................................200
7.2　案例引入.............................................200
7.3　线性表的查找.....................................201
7.3.1　顺序查找...............................................　201
7.3.2　折半查找...............................................　203
7.3.3　分块查找...............................................　206
7.4　树表的查找.........................................207
7.4.1　二叉排序树...........................................　207
7.4.2　平衡二叉树...........................................　214
7.4.3　B- 树.....................................................　218
7.4.4　B+ 树.....................................................　227
7.5　散列表的查找.....................................228
7.5.1　散列表的基本概念..............................　228
7.5.2　散列函数的构造方法..........................　229
7.5.3　处理冲突的方法..................................　231
7.5.4　散列表查找的算法实现......................　233
7.6　案例分析与实现.................................237
7.7　精选习题解析.....................................239
7.8　AI 协作实战........................................242
7.9　Python 标准库中的集合、字典与
散列函数..............................................242
7.10　小结......................................................245
习题...............................................................246
第8　章
排序　249
8.1　排序的基本概念和方法概述.............250
8.1.1　排序的基本概念..................................　250
8.1.2　内部排序的算法的分类......................　250
8.1.3　待排序记录的存储方式......................　251
8.1.4　排序算法效率的评价指标..................　251
8.2　案例引入.............................................252
8.3　插入排序.............................................252
8.3.1　直接插入排序.......................................　252
8.3.2　折半插入排序.......................................　254
8.3.3　希尔排序...............................................　255
8.4　交换排序.............................................257
8.4.1　冒泡排序...............................................　257
8.4.2　快速排序...............................................　259
8.5　选择排序.............................................262
8.5.1　简单选择排序.......................................　262
8.5.2　堆排序...................................................　263
8.6　归并排序.............................................267
8.7　基数排序.............................................269
8.7.1　多关键字的排序 .................................　269
8.7.2　链式基数排序 .....................................　270
8.8　外部排序..............................................274
IV　数据结构（Python 版）（第2 版）（附微课视频）
8.9　案例分析与实现..................................275
8.10　精选习题解析......................................278
8.11　AI 协作实战........................................282
8.12　Python 标准库中的排序方法............283
8.13　小结......................................................284
习题...............................................................286