数据结构(PYTHON语言描述)

第1章绪论1
1.1数据结构的相关概念1
1.2抽象数据类型3
1.2.1抽象数据类型的定义3
1.2.2抽象数据类型的描述4
1.3数据的逻辑结构与存储结构7
1.3.1逻辑结构7
1.3.2存储结构8
1.4算法的特性与算法的描述8
1.4.1算法的定义8
1.4.2算法的特性9
1.4.3算法的描述9
1.5算法分析11
1.5.1算法设计的要求11
1.5.2算法时间复杂度11
1.5.3算法空间复杂度16
1.6关于数据结构课程的地位及学习方法16
习题19
第2章线性表22
2.1线性表的定义及抽象数据类型22
2.1.1线性表的逻辑结构23
2.1.2线性表的抽象数据类型23
2.2顺序表24
2.2.1表的顺序存储结构24
2.2.2顺序表的基本操作25
2.2.3顺序表的实现算法分析28
2.2.4顺序表的优缺点28
2.2.5顺序表应用举例29
2.3单链表31
2.3.1单链表的存储结构31
2.3.2单链表的基本操作33
2.3.3链式存储结构与顺序存储结构的比较37
2.3.4单链表应用举例38
2.4循环单链表43
2.4.1循环单链表的存储结构43
2.4.2循环单链表应用举例44
2.5双向链表47
2.5.1双向链表的存储结构47
2.5.2双向链表的插入和删除操作47
2.5.3双向链表应用举例49
2.6综合案例：一元多项式的表示与相加51
2.6.1一元多项式的表示51
2.6.2一元多项式相加52
2.7小结56
2.8上机实验57
2.8.1基础实验57
2.8.2综合实验：一元多项式相乘58
习题59
第3章栈和队列62
3.1栈63
3.1.1栈的基本概念63
3.1.2栈的抽象数据类型64
3.1.3栈的顺序表示与实现64
3.1.4栈的链式表示与实现67
3.1.5栈的典型应用72
3.2栈与递归80
3.2.1设计递归算法80
3.2.2分析递归调用过程82
3.2.3消除递归84
3.3队列86
3.3.1队列的定义与抽象数据类型86
3.3.2队列的顺序存储及实现87
3.3.3队列的链式存储及实现93
3.4双端队列97
3.4.1什么是双端队列97
3.4.2双端队列的应用98
3.5小结98
3.6上机实验99
3.6.1基础实验99
3.6.2综合实验：迷宫求解和模拟停车场管理100
习题102
第4章串、数组和广义表105
4.1串的定义及抽象数据类型105
4.1.1什么是串106
4.1.2串的抽象数据类型106
4.2串的存储表示107
4.2.1串的顺序存储结构108
4.2.2串的链式存储结构108
4.2.3顺序串应用举例109
4.3串的模式匹配111
4.3.1BruteForce算法111
4.3.2KMP算法112
4.3.3模式匹配应用举例117
4.4数组118
4.4.1数组的基本概念118
4.4.2数组的顺序存储结构119
4.4.3特殊矩阵的压缩存储120
4.4.4稀疏矩阵的压缩存储123
4.5广义表130
4.5.1什么是广义表130
4.5.2广义表的抽象数据类型131
4.5.3广义表的头尾链表表示131
4.5.4广义表的扩展线性链表表示132
4.6小结133
4.7上机实验134
4.7.1基础实验134
4.7.2综合实验：稀疏矩阵相加134
习题135
第5章树和二叉树138
5.1树139
5.1.1树的定义139
5.1.2树的逻辑表示140
5.1.3树的抽象数据类型140
5.2二叉树142
5.2.1二叉树的定义142
5.2.2二叉树的性质143
5.2.3二叉树的抽象数据类型145
5.2.4二叉树的存储表示146
5.3二叉树的遍历149
5.3.1二叉树遍历的定义149
5.3.2二叉树的先序遍历149
5.3.3二叉树的中序遍历151
5.3.4二叉树的后序遍历152
5.3.5二叉树的层次遍历154
5.4二叉树的线索化155
5.4.1二叉树的线索化定义155
5.4.2二叉树线索化方法156
5.4.3线索二叉树的遍历157
5.4.4线索二叉树的应用举例159
5.5树、森林与二叉树161
5.5.1树的存储结构161
5.5.2树转换为二叉树163
5.5.3森林转换为二叉树164
5.5.4二叉树转换为树和森林165
5.5.5树和森林的遍历167
5.6并查集168
5.6.1并查集的定义168
5.6.2并查集的实现168
5.6.3并查集的应用171
5.7二叉树的典型应用——哈夫曼树172
5.7.1哈夫曼树及应用173
5.7.2利用二叉树求算术表达式的值178
5.8小结183
5.9上机实验184
5.9.1基础实验184
5.9.2综合实验：哈夫曼树、二叉树及应用184
习题185
第6章图190
6.1图的定义与相关概念190
6.1.1图的定义190
6.1.2图的相关概念191
6.1.3图的抽象数据类型193
6.2图的存储结构194
6.2.1邻接矩阵194
6.2.2邻接表197
6.2.3十字链表201
6.2.4邻接多重表201
6.3图的遍历203
6.3.1图的深度优先遍历203
6.3.2图的广度优先遍历205
6.4图的连通性问题207
6.4.1无向图的连通分量与生成树207
6.4.2*小生成树208
6.5有向无环图214
6.5.1AOV网与拓扑排序214
6.5.2AOE网与关键路径217
6.6*短路径223
6.6.1利用Dijkstra算法求*短路径223
6.6.2利用Floyd算法求*短路径229
6.7图的应用举例233
6.7.1距离某个顶点的*短路径长度为k的所有顶点233
6.7.2求图中顶点u到顶点v的简单路径235
6.8小结237
6.9上机实验237
6.9.1基础实验237
6.9.2综合实验：图的应用238
习题238
第7章查找242
7.1查找的基本概念242
7.2静态查找243
7.2.1顺序表的查找243
7.2.2有序顺序表的查找244
7.2.3索引顺序表的查找247
7.3动态查找248
7.3.1二叉排序树248
7.3.2平衡二叉树254
7.3.3红黑树261
7.4B树与B+树269
7.4.1B树269
7.4.2B+树276
7.5哈希表277
7.5.1哈希表的定义277
7.5.2哈希函数的构造方法278
7.5.3处理冲突的方法279
7.5.4哈希表查找与分析280
7.5.5哈希表应用举例281
7.6小结286
7.7上机实验286
7.7.1基础实验286
7.7.2综合实验：疫苗接种信息管理系统287
习题287
第8章排序291
8.1排序的基本概念291
8.2插入排序292
8.2.1直接插入排序292
8.2.2折半插入排序294
8.2.3希尔排序294
8.2.4插入排序应用举例295
8.3选择排序296
8.3.1简单选择排序296
8.3.2堆排序297
8.4交换排序302
8.4.1冒泡排序302
8.4.2快速排序304
8.4.3交换排序应用举例306
8.5归并排序309
8.6基数排序311
8.6.1基数排序的过程和算法实现311
8.6.2基数排序应用举例313
8.7小结316
8.8上机实验317
8.8.1基础实验317
8.8.2综合实验：疫苗接种信息管理系统V2.0318
习题319
参考文献321