Python数据结构学习笔记 张清云 2021年版

Python数据结构学习笔记
作者：张清云
出版时间：2021年版
内容简介
　　在计算机科学中，数据结构是一种数据组织、管理和存储的格式；简而言之，决定了数据顺序和位置关系的便是数据结构，由此可见数据结构的重要性。本书以学习笔记的形式阐述了Python语言框架下的数据结构核心知识和应用实践，尤其是对Python不同于其他语言的内置数据结构（线性表、队列和栈、数、图等）进行了重点讲解，全书更多地通过实战演练的形式将数据结构应用经验融入实践之中，旨在帮读者透彻理解数据结构在编程实践中的内涵，以期与算法实现融合，提升读者编程内功。
目录
第1 章 数据结构基础
1.1 数据结构 1
1.1.1 数据结构的核心技术 .1
1.1.2 数据结构的起源和发展现状 .2
1.1.3 数据结构中的基本概念 .2
1.2 常用的数据结构和分类 3
1.2.1 数据结构的分类 .3
1.2.2 常用的数据结构 .6
1.3 数据类型和抽象数据类型 7
1.3.1 数据类型 .7
1.3.2 抽象数据类型 .7
第2 章 算法
2.1 算法是程序的灵魂 9
2.1.1 算法的定义 .9
2.1.2 算法的特征 .10
2.1.3 为什么说算法是程序的灵魂 .10
2.1.4 认识计算机中的算法 .11
2.2 数据结构和算法的关系 12
2.3 在计算机中表示算法的方法 13
2.3.1 用流程图来表示算法 .13
2.3.2 用N-S 流程图来表示算法 .14
2.3.3 用计算机语言来表示算法 .15
2.4 时间复杂度 15
2.4.1 寻找最优算法 .16
2.4.2 常见算法的时间复杂度 .16
2.4.3 实战演练——用Python 体验时间复杂度 17
2.5 常用的算法思想 19
2.5.1 枚举算法思想 .19
2.5.2 递归算法思想 .20
2.5.3 分治算法思想 .20
2.5.4 贪心算法思想 .20
2.5.5 试探法算法思想 .21
2.5.6 迭代算法 .22
第3 章 Python 内置的几种数据结构
3.1 使用列表 23
3.1.1 列表的基本用法 .23
3.1.2 实战演练——删除列表中的重复元素并保持顺序不变 .25
3.1.3 实战演练——找出列表中出现次数最多的元素 .26
3.1.4 实战演练——排序类定义的实例 .26
3.1.5 实战演练——使用列表推导式 .27
3.1.6 实战演练——命名切片 .28
3.2 使用元组 29
3.2.1 实战演练——创建并访问元组 .29
3.2.2 实战演练——连接组合元组 .30
3.2.3 实战演练——删除元组 .30
3.2.4 实战演练——使用内置方法操作元组 .31
3.2.5 实战演练——将序列分解为单独的变量 .31
3.2.6 实战演练——将序列中的最后几项作为历史记录 .33
3.2.7 实战演练——实现优先级队列 .33
3.3 使用字典 35
3.3.1 实战演练——创建并访问字典 .36
3.3.2 实战演练——添加、修改、删除字典中的元素 .36
3.3.3 实战演练——映射多个值 .38
3.3.4 实战演练——使用OrderedDict 类创建有序字典 .39
3.3.5 实战演练——获取字典中的最大值和最小值 .40
3.3.6 实战演练——获取两个字典中的相同键值对 .41
3.3.7 实战演练——使用函数itemgetter() 对字典进行排序 42
3.3.8 使用字典推导式 .43
3.3.9 实战演练——根据记录进行分组 .44
3.3.10 实战演练——转换并换算数据 .45
3.3.11 实战演练——将多个映射合并为单个映射 .47
第4 章 线性表
4.1 线性表的定义和基本特征 49
4.1.1 线性表和线性结构 .49
4.1.2 线性表的基本操作过程 .50
4.2 顺序表的基本操作 50
4.2.1 顺序表的定义和操作 .50
4.2.2 实战演练——建立空的顺序表 .53
4.2.3 实战演练——按值查找 .53
4.2.4 实战演练——插入新元素 .54
4.2.5 实战演练——删除操作 .55
4.2.6 实战演练——实现顺序表的插入、检索、删除和反转操作 .56
4.3 链表操作 59
4.3.1 什么是链表 .59
4.3.2 实战演练——Python 中的链表操作 .59
4.3.3 实战演练——单向链表 .62
4.3.4 实战演练——单向循环链表 .70
4.3.5 实战演练——双向链表 .75
4.3.6 实战演练——双向循环链表 .78
4.3.7 实战演练——在链表中增加比较功能 .83
4.3.8 实战演练——单链表结构字符串 .85
4.3.9 实战演练——改进后的多次匹配操作 .87
第5 章 队列和栈
5.1 队列 90
5.1.1 什么是队列 .90
5.1.2 Python 内置的队列操作方法 .91
5.1.3 实战演练——基于内置模块queue 的队列 92
5.1.4 实战演练——基于列表自定义实现的优先队列 .96
5.1.5 实战演练——基于堆实现的优先队列 .98
5.1.6 实战演练——双端队列 .100
5.1.7 实战演练——银行业务队列简单模拟 .101
5.2 栈 103
5.2.1 什么是栈 .103
5.2.2 实战演练——入栈和出栈 .103
5.2.3 实战演练——顺序栈 .105
5.2.4 实战演练——链栈 .107
5.2.5 实战演练——检查小括号是否成对 .109
第6 章 树
6.1 树的基础知识 111
6.1.1 什么是树 .111
6.1.2 树的相关概念 .112
6.2 使用列表构建树 113
6.2.1 实战演练——实现一个简单的树 .113
6.2.2 实战演练——使用列表创建二叉树 .114
6.3 二叉树 115
6.3.1 二叉树的定义 .115
6.3.2 二叉树的性质 .116
6.3.3 二叉树存储 .117
6.3.4 实战演练——使用嵌套列表构建树 .119
6.3.5 实战演练——把二叉树的任何子节点当成二叉树进行处理 .121
6.3.6 实战演练——实现二叉搜索树查找操作 .122
6.3.7 实战演练——实现二叉搜索树的删除操作 .128
6.3.8 实战演练——遍历二叉树 .136
6.3.9 实战演练——使用线索二叉树 .140
6.4 堆排列和二叉堆 148
6.4.1 实战演练——使用Python 内置的堆操作方法 148
6.4.2 实战演练——实现二叉堆操作 .149
6.5 哈夫曼树 151
6.5.1 哈夫曼树基础 .152
6.5.2 实战演练——使用面向过程方式和面向对象方式实现哈夫曼树 .154
6.5.3 实战演练——实现哈夫曼树的基本操作 .155
第7 章 图
7.1 图的起源 159
7.2 图的相关概念 160
7.3 存储结构 163
7.3.1 使用邻接矩阵表示图 .163
7.3.2 实战演练——将邻接矩阵输出成图 .165
7.3.3 实战演练——使用邻接表表示图 .165
7.3.4 邻接矩阵与邻接表的对比 .168
7.4 图的遍历 169
7.4.1 深度优先搜索 .169
7.4.2 广度优先搜索 .171
7.4.3 实战演练——实现图的深度优先和广度优先 .172
7.4.4 深度优先算法和广度优先算法的比较和选择 .174
7.5 图的连通性 175
7.5.1 无向图连通分量 .175
7.5.2 实战演练——通过二维数组建立无向图 .176
7.5.3 实战演练——根据邻接矩阵绘制无向图 .177
7.5.4 最小生成树 .178
7.5.5 实战演练——实现最小生成树和拓扑序列 .179
7.5.6 关键路径 .180
7.5.7 实战演练——使用递归解决AOE 网络最长路关键路径的问题 .182
7.6 寻求最短路径 184
7.6.1 求某一顶点到其他各顶点的最短路径 .184
7.6.2 任意一对顶点间的最短路径 .186
7.6.3 实战演练——使用Dijkstra 算法计算指定一个点到其他
各顶点的路径 .188
7.6.4 实战演练——使用Floyd-Warshall 算法计算图的最短路径 189
7.6.5 实战演练——使用Bellman-Ford 算法计算图的最短路径 .190
7.6.6 实战演练——使用Dijkstra 算法解决加权最短路径问题 191
7.6.7 几种最短路径算法的比较 .193
第8 章 数据结构的查找算法
8.1 数据结构的查找处理 195
8.1.1 查找的基本概念 .195
8.1.2 查找算法的分类 .196
8.2 顺序查找 196
8.2.1 顺序查找法基础 .196
8.2.2 分析顺序查找的性能 .197
8.2.3 使用Python 内置函数顺序查找 197
8.2.4 实战演练———遍历有序列表 .198
8.2.5 实战演练———遍历无序列表 .198
8.2.6 实战演练———查找两个有序列表的中位数 .201
8.2.7 实战演练———在列表中顺序查找最大值和最小值 .202
8.3 折半查找算法 202
8.3.1 折半查找法基础 .203
8.3.2 分析折半查找法的性能 .203
8.3.3 实战演练——使用折半查找算法查找指定的数据 .203
8.3.4 实战演练——使用递归折半查找和非递归折半查找 .204
8.3.5 实战演练——比较顺序查找算法和折半查找算法的效率 .206
8.4 插值查找算法 207
8.4.1 插值查找算法基础 .207
8.4.2 分析插值查找的性能 .208
8.4.3 实战演练——使用插值查找算法查找指定的数据 .208
8.5 分块查找算法 209
8.5.1 分块查找算法基础 .209
8.5.2 分析分块查找算法的性能 .210
8.5.3 实战演练——使用分块查找算法在列表中查找某元素 .210
8.5.4 实战演练——升级策略后的分块查找算法 .212
8.5.5 实战演练——一道算法题 .213
8.6 二叉排序树法 216
8.6.1 二叉排序树法基础 .216
8.6.2 分析二叉排序树法的性能 .216
8.6.3 实战演练——实现二叉树的搜索、插入、删除、先序遍历
和后序遍历操作 .217
8.7 平衡查找树法 221
8.7.1 2-3 查找树 .221
8.7.2 平衡查找树之红黑树（Red-Black Tree） 225
8.7.3 平衡二叉树 .227
8.8 哈希查找算法 233
8.8.1 哈希查找算法的基本思想 .233
8.8.2 分析哈希查找算法的性能 .234
8.8.3 实战演练——使用哈希查找算法查找数据 .234
8.9 斐波那契查找算法 235
8.9.1 斐波那契查找算法基础 .235
8.9.2 实战演练——使用斐波那契查找算法查找数据 .236
第9 章 数据结构的排序算法
9.1 数据结构排序的基础知识 238
9.1.1 排序算法的定义和评价标准 .238
9.1.2 排序算法的分类 .239
9.2 使用插入排序算法 239
9.2.1 插入排序算法基础 .239
9.2.2 直接插入排序 .240
9.2.3 实战演练——使用直接插入排序算法对列表中的元素进行排序 .241
9.2.4 折半插入排序 .242
9.2.5 实战演练——使用折半插入排序法查找指定数字 .243
9.2.6 实战演练——使用折半插入排序 .243
9.2.7 实战演练——对链表进行插入排序 .244
9.3 使用希尔排序算法 245
9.3.1 希尔排序算法基础 .245
9.3.2 分析希尔排序算法的性能 .246
9.3.3 实战演练——使用希尔排序算法对数据进行排序处理 .246
9.3.4 实战演练——排序一个大的随机列表 .247
9.4 冒泡排序算法 249
9.4.1 冒泡排序算法基础 .249
9.4.2 分析冒泡排序算法的性能 .250
9.4.3 实战演练——实现从大到小的冒泡排序 .250
9.4.4 实战演练——使用冒泡排序法实现升序排序 .251
9.5 使用快速排序算法 252
9.5.1 快速排序算法基础 .252
9.5.2 分析快速排序算法的性能 .253
9.5.3 实战演练——使用快速排序算法排列输入的列表 .254
9.6 选择排序 255
9.6.1 直接选择排序 .255
9.6.2 实战演练——使用直接选择排序法排序列表list 中的元素 256
9.6.3 树形选择排序 .257
9.6.4 实战演练——创建二叉树并实现完整树形排序 .257
9.6.5 堆排序 .259
9.6.6 实战演练——对9 个待排序数字实现完整堆排序 .260
9.7 归并排序 263
9.7.1 归并排序算法原理与性能 .263
9.7.2 实战演练——使用归并排序算法由小到大排序一个列表 .265
9.8 基数排序 266
9.8.1 基数排序算法原理与性能 .266
9.8.2 实战演练——使用基数排序算法排列一个列表 .267