数据结构与算法分析

第1章 绪论 2 1.1 数据结构概述 2 1.1.1 数据结构的引入 2 1.1.2 数据结构的基本概念 4 1.1.3 数据结构与程序设计 7 1.2 算法分析 9 1.2.1 算法的定义及特点 9 1.2.2 算法的效率分析 10 1.3 程序设计的关键技术 12 1.3.1 程序结构设计 12 1.3.2 模块设计 16 1.3.3 良好的编程风格 16 1.3.4 排错与测试 21 1.3.5 程序性能 25 1.4 程序设计步骤及实例 25 1.4.1 程序设计的步骤 26 1.4.2 程序设计实例 28 本章小结 38 习题 38 第2章 线性表 40 2.1 线性表的基本概念及运算 40 2.2 线性表的顺序存储实现——顺序表 42 2.2.1 线性表的顺序存储实现 42 2.2.2 顺序表的基本运算 43 2.3 线性表的链式存储实现——链表 47 2.3.1 单链表 48 2.3.2 单链表的基本运算 49 2.3.3 循环链表 56 2.3.4 双向链表 57 2.4 应用实例 59 2.4.1 顺序表应用实例——学生学籍 信息管理 60 2.4.2 链表应用实例——多项式的 表示及运算 62 本章小结 66 习题 67 第3章 栈和队列 70 3.1 栈 70 3.1.1 栈的定义及性质 70 3.1.2 顺序存储实现——顺序栈 71 3.1.3 链式存储实现——链栈 74 3.1.4 栈的应用 75 3.2 队列 81 3.2.1 队列的定义及性质 81 3.2.2 顺序存储实现——循环队列 82 3.2.3 链式存储实现——链队列 85 3.2.4 队列的应用 87 3.3 应用实例 90 3.3.1 迷宫问题 90 3.3.2 离散事件的仿真——银行排队 问题 94 本章小结 99 习题 100 第4章 串和数组 103 4.1 串及基本运算 103 4.2 串的存储实现 106 4.2.1 顺序存储 106 4.2.2 链式存储 107 4.2.3 索引存储 107 4.3 串运算的实现 110 4.3.1 基本运算的实现 110 4.3.2 KMP算法 114 4.4 多维数组的存储实现 116 4.5 矩阵的压缩存储 119 4.5.1 特殊矩阵 119 4.5.2 稀疏矩阵 121 4.6 应用实例 123 4.6.1 稀疏矩阵的运算 123 4.6.2 文本编辑 127 本章小结 131 习题 132 第5章 树 134 5.1 树的基本概念 134 5.2 二叉树 135 5.3 二叉树的存储实现 139 5.3.1 顺序存储结构 139 5.3.2 链式存储结构 141 5.3.3 二叉树的建立 141 5.4 二叉树的遍历 143 5.4.1 二叉树的深度优先遍历 143 5.4.2 二叉树的广度优先遍历 145 5.4.3 深度优先遍历的非递归算法 146 5.4.4 从遍历序列恢复二叉树 147 5.4.5 遍历算法的应用 149 5.5 线索二叉树 151 5.5.1 线索二叉树的建立 151 5.5.2 访问线索二叉树 153 5.6 树和森林 155 5.6.1 树的存储结构 156 5.6.2 树、森林和二叉树之间的转换 157 5.7 二叉树的应用 159 5.7.1 哈夫曼树及哈夫曼编码 159 5.7.2 二叉排序树 167 5.8 应用实例 171 5.8.1 数据的压缩与解压缩 171 5.8.2 基于二叉排序树的通讯录管理 177 本章小结 181 习题 181 第6章 图 184 6.1 图的基本概念 184 6.2 图的存储实现 187 6.2.1 邻接矩阵 187 6.2.2 邻接表 189 6.3 图的遍历 190 6.3.1 深度优先搜索遍历 191 6.3.2 广度优先搜索遍历 193 6.4 生成树和*小生成树 195 6.5 *短路径 201 6.5.1 从某个源点到其余各顶点的 *短路径 202 6.5.2 每一对顶点之间的*短路径 205 6.6 拓扑排序 207 6.7 关键路径 213 6.8 应用实例 217 6.8.1 社交关系网络聚合性问题 218 6.8.2 课程学习实施方案的设计 221 本章小结 224 习题 225 第7章 索引结构与散列技术 229 7.1 索引结构及查找 229 7.1.1 线性索引 229 7.1.2 倒排表 231 7.2 散列技术 232 7.2.1 散列的概念 232 7.2.2 散列函数 234 7.2.3 解决冲突的方法 236 7.2.4 散列表的查找及分析 239 7.3 应用实例 242 7.3.1 银行账户的管理 242 7.3.2 文本单词的词频统计 246 本章小结 250 习题 251 第二部分 经典算法策略 第8章 缩小规模策略 254 8.1 分治与递归策略 254 8.1.1 递归算法设计 254 8.1.2 分治算法设计 255 8.2 递归的典型应用 256 8.2.1 Hanoi塔问题 257 8.2.2 全排列问题 258 8.3 分治策略的应用 259 8.3.1 二分搜索技术 259 8.3.2 归并排序 261 8.3.3 快速排序 263 本章小结 266 习题 266 第9章 动态规划与贪心策略 268 9.1 动态规划思想 268 9.1.1 矩阵连乘问题 268 9.1.2 动态规划的基本要素 272 9.1.3 备忘录方法 273 9.2 贪心策略的基本要素 274 9.3 贪心策略的应用 275 本章小结 280 习题 280 第10章 搜索策略 282 10.1 回溯法 282 10.1.1 问题的解空间 282 10.1.2 回溯策略的基本思想 283 10.1.3 递归和迭代回溯 284 10.1.4 子集树与排列树 285 10.2 回溯法的应用 286 10.2.1 *大团问题 286 10.2.2 图的m着色问题 287 10.2.3 旅行售货员问题 289 10.3 分支界限法 291 10.3.1 分支界限法的基本思想 291 10.3.2 分支界限法与回溯法的区别 292 10.4 分支界限法的应用 293 10.4.1 装载问题 293 10.4.2 布线问题 298 本章小结 301 习题 301 附录 303 参考文献 304