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 实战演练——使用嵌套列表构建树 

　　     张清云，浪潮集团企业云深圳研发中心高级工程师，精通Linux、Unix平台开发，12年C 开发经验，6年Python开发经验，长期从事与ERP开发、大数据开发和数据分析工作。参与研发了浪潮云海OS系统，这是中国自主研发的云数据中心操作系统，深度融合OpenStack，是集数据分析、开放、融合、安全的云数据中心操作系统，支持广泛的异构资源管理和跨云整合。

　　在计算机科学中，数据结构是一种数据组织、管理和存储的格式；简而言之，决定了数据顺序和位置关系的便是数据结构，由此可见数据结构的重要性。本书以学习笔记的形式阐述了Python语言框架下的数据结构核心知识和应用实践，尤其是对Python不同于其他语言的内置数据结构（线性表、队列和栈、数、图等）进行了重点讲解，全书更多地通过实战演练的形式将数据结构应用经验融入实践之中，旨在帮读者透彻理解数据结构在编程实践中的内涵，以期与算法实现融合，提升读者编程内功。