在计算机科学中，数据结构是一种数据组织、管理和存储的格式；简而言之，决定了数据顺序和位置关系的便是数据结构，由此可见数据结构的重要性。本书以学习笔记的形式阐述了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 实战演练——使用嵌套列表构建树