数据结构――基于PYTHON语言（微课版）

数据结构是计算机相关专业一门重要的专业基础课程。本书基于Python语言系统介绍数据结构的知识，内容包括数据结构与算法概述、线性表、栈与队列、串、数组与广义表、基于线性表的查找算法、基于线性表的排序算法、树、基于树的查找算法、基于树的排序算法、图、计算式查找法。

第1章 数据结构与算法概述 / 1 1.1 数据结构 / 1 1.1.1 什么是数据结构 / 1 1.1.2 数据结构的分类 / 3 1.1.3 数据类型与抽象数据类型 / 6 1.2 算法 / 7 1.3 算法分析 / 9 1.3.1 算法的时间复杂度 / 10 1.3.2 算法的空间复杂度 / 13 1.4 本章习题 / 13 第2章 线性表 / 15 2.1 什么是线性表 / 15 2.2 顺序表 / 16 2.2.1 顺序表的定义 / 16 2.2.2 顺序表的实现 / 17 2.3 单链表 / 24 2.3.1 单链表的定义 / 24 2.3.2 单链表的实现 / 25 2.4 双向链表 / 34 2.4.1 双向链表的定义 / 34 2.4.2 双向链表的实现 / 34 2.5 循环链表 / 38 2.5.1 循环链表的定义 / 38 2.5.2 循环链表的实现 / 39 2.6 线性表的比较 / 42 2.6.1 顺序表与链表的比较 / 42 2.6.2 链式存储方式的比较 / 42 2.7 线性表的应用 / 43 2.7.1 一元多项式的表示及相加 / 43 2.7.2 约瑟夫环 / 47 2.8 本章实验：线性表初探 / 49 2.9 本章习题 / 50 第3章 栈与队列 / 53 3.1 什么是栈 / 53 3.2 栈的实现 / 54 3.2.1 顺序栈存储实现 / 54 3.2.2 双端栈存储实现 / 57 3.2.3 链栈存储实现 / 59 3.3 栈与递归 / 61 3.3.1 递归的概念 / 61 3.3.2 栈的应用 / 63 3.4 什么是队列 / 66 3.5 队列的实现 / 66 3.5.1 顺序队列的实现 / 66 3.5.2 循环队列的实现 / 68 3.5.3 链式队列的实现 / 71 3.6 队列的应用 / 74 3.7 讨论课：如何选择合适的线性表解决实际问题 / 75 3.8 本章实验：栈的定义与应用 / 75 3.9 本章习题 / 76 第4章 串 / 78 4.1 什么是串 / 78 4.2 串的存储结构 / 78 4.2.1 串的顺序存储实现 / 78 4.2.2 串的链式存储实现 / 83 4.3 串的模式匹配算法 / 83 4.3.1 朴素的模式匹配算法 / 83 4.3.2 KMP算法 / 85 4.4 综合实验：校友通讯录―线性表的应用 / 89 4.5 本章习题 / 90 第5章 数组与广义表 / 92 5.1 数组 / 92 5.2 矩阵存储 / 93 5.2.1 特殊矩阵 / 93 5.2.2 稀疏矩阵 / 94 5.3 广义表 / 100 5.3.1 广义表的定义 / 100 5.3.2 广义表的存储结构 / 101 5.3.3 广义表的递归运算 / 102 5.4 本章习题 / 105 第6章 基于线性表的查找算法 / 107 6.1 查找概述 / 107 6.2 顺序表查找法 / 108 6.3 折半查找法 / 108 6.4 索引顺序查找法 / 111 6.5 本章实验：折半查找 / 113 6.6 本章习题 / 113 第7章 基于线性表的排序算法 / 115 7.1 排序的概念及分类 / 115 7.2 插入排序 / 116 7.2.1 直接插入排序 / 116 7.2.2 折半插入排序 / 119 7.2.3 希尔排序 / 119 7.3 交换排序 / 120 7.3.1 冒泡排序 / 121 7.3.2 快速排序 / 123 7.4 归并排序 / 124 7.5 本章实验：冒泡排序改动算法 / 126 7.6 本章习题 / 127 第8章 树 / 129 8.1 树 / 129 8.1.1 什么是树 / 129 8.1.2 树的基本概念及常用术语 / 130 8.2 树的存储结构 / 131 8.2.1 双亲表示法 / 131 8.2.2 孩子表示法 / 132 8.2.3 孩子兄弟表示法 / 132 8.3 二叉树 / 134 8.3.1 什么是二叉树 / 134 8.3.2 二叉树的分类 / 134 8.3.3 二叉树的性质 / 135 8.4 二叉树的存储结构 / 137 8.4.1 二叉树的顺序存储 / 137 8.4.2 二叉树的链式存储 / 138 8.5 树的遍历与应用 / 139 8.5.1 二叉树的遍历 / 139 8.5.2 二叉树的应用 / 143 8.5.3 树的遍历 / 147 8.6 树的转换、构建与线索化 / 147 8.6.1 二叉树与树、森林之间的转换 / 147 8.6.2 二叉树的构建 / 150 8.6.3 线索化二叉树 / 153 8.7 哈夫曼树 / 155 8.7.1 什么是哈夫曼树 / 155 8.7.2 哈夫曼树的构造 / 155 8.7.3 哈夫曼编码 / 156 8.7.4 哈夫曼树的实现 / 157 8.8 讨论课：如何学习树 / 158 8.9 本章实验一：二叉树的创建与遍历 / 159 8.10 本章实验二：二叉树的查找 / 159 8.11 综合实验：校友通讯录―树的应用 / 160 8.12 本章习题 / 161 第9章 基于树的查找算法 / 164 9.1 二叉排序树 / 164 9.1.1 二叉排序树的插入 / 164 9.1.2 二叉排序树的删除 / 168 9.1.3 二叉排序树的查找 / 170 9.2 平衡二叉树 / 172 9.2.1 平衡二叉树的定义 / 172 9.2.2 平衡二叉树的平衡化旋转 / 173 9.3 B树 / 177 9.3.1 B树的查找 / 178 9.3.2 B树的插入 / 178 9.3.3 B+树和B*树 / 179 9.4 本章习题 / 180 第10章 基于树的排序算法 / 182 10.1 选择排序 / 182 10.1.1 简单选择排序 / 182 10.1.2 树形选择排序 / 183 10.2 堆排序 / 184 10.2.1 堆的定义 / 184 10.2.2 堆的存储 / 185 10.2.3 堆排序的思想 / 189 10.3 综合比较 / 193 10.4 本章习题 / 194 第11章 图 / 196 11.1 图的基本概念 / 196 11.1.1 什么是图 / 196 11.1.2 图的基本术语 / 196 11.2 图的存储结构 / 199 11.2.1 邻接矩阵 / 200 11.2.2 邻接表 / 202 11.2.3 十字链表 / 205 11.2.4 邻接多重表 / 207 11.3 图的遍历 / 207 11.3.1 深度优先遍历 / 208 11.3.2 广度优先遍历 / 212 11.4 图的应用 / 216 11.4.1 最小生成树 / 216 11.4.2 最短路径 / 224 11.4.3 拓扑序列 / 235 11.4.4 关键路径 / 239 11.5 讨论课：图是什么 / 245 11.6 本章实验一：图的邻接矩阵定义与创建 / 246 11.7 本章实验二：图的邻接表定义与创建 / 246 11.8 综合实验：校友通讯录―图的应用 / 247 11.9 本章习题 / 248 第12章 计算式查找法 / 251 12.1 什么是哈希表 / 251 12.2 哈希函数的构造方法 / 252 12.3 处理冲突的方法 / 253 12.3.1 开放定址法（再散列法） / 253 12.3.2 链地址法 / 255 12.3.3 再哈希法 / 256 12.3.4 建立公共溢出区 / 256 12.4 哈希查找法 / 257 12.5 讨论课：如何选择合适的算法，达到性能的很优 / 259 12.6 综合实验：校友通讯录―算法的应用 / 259 12.7 本章习题 / 260