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.2Python内置的队列操作方法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.12-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