第1章 概论 1__eol__1.1 什么是数据结构 1__eol__1.2 基本概念和术语 4__eol__1.3 算法和算法分析 7__eol__1.3.1 算法的定义及特性 7__eol__1.3.2 算法的设计要求 8__eol__1.3.3 算法效率的衡量方法 9__eol__1.3.4 算法的时间复杂度 9__eol__1.3.5 算法的空间复杂度 15__eol__1.4 抽象数据类型 16__eol__习题1 18__eol__第2章 线性表 19__eol__2.1 线性表的类型定义 19__eol__2.1.1 线性表的概念 19__eol__2.1.2 线性表的抽象数据类型 20__eol__2.2 线性表的顺序表示和实现 21__eol__2.2.1 线性表的顺序表示 21__eol__2.2.2 顺序表基本运算的实现 22__eol__2.3 线性表的链式表示和实现 26__eol__2.3.1 线性表的链式表示 27__eol__2.3.2 单链表上基本运算的实现 30__eol__2.4 双链表 37__eol__2.5 循环链表 41__eol__2.6 线性表实现方法的比较 43__eol__2.7 算法拓展 44__eol__习题2 48__eol__第3章 栈和队列 51__eol__3.1 栈 51__eol__3.1.1 栈的类型定义 51__eol__3.1.2 顺序栈的表示和实现 53__eol__3.1.3 链栈的表示和实现 55__eol__3.2 栈的应用举例 57__eol__3.2.1 十进制数转换为其他进制数 57__eol__3.2.2 表达式中括号的匹配检查 58__eol__3.2.3 表达式求值 59__eol__3.2.4 利用栈消除递归 67__eol__3.3 队列 71__eol__3.3.1 队列的类型定义 71__eol__3.3.2 循环队列—队列的顺序表示和实现 73__eol__3.3.3 链队列—队列的链式表示和实现 76__eol__3.4 算法拓展 78__eol__习题3 81__eol__第4章 串 83__eol__4.1 串的基本概念 83__eol__4.2 串的表示和实现 84__eol__4.2.1 串的顺序存储结构 84__eol__4.2.2 串的链式存储结构 87__eol__4.3 串的模式匹配 88__eol__4.3.1 朴素的模式匹配算法 88__eol__4.3.2 KMP算法 89__eol__习题4 94__eol__第5章 数组 96__eol__5.1 基本概念 96__eol__5.2 矩阵的压缩存储 99__eol__5.2.1 特殊矩阵 99__eol__5.2.2 稀疏矩阵 102__eol__5.3 算法拓展 109__eol__习题5 112__eol__第6章 树和二叉树 115__eol__6.1 树的概念 115__eol__6.2 二叉树的概念和性质 117__eol__6.2.1 二叉树的概念和抽象数据类型 117__eol__6.2.2 二叉树的性质 119__eol__6.3 二叉树的表示和实现 121__eol__6.3.1 二叉树的存储结构 121__eol__6.3.2 二叉树的遍历 123__eol__6.3.3 二叉树的其他基本运算 130__eol__6.4 树和森林 132__eol__6.4.1 树的存储结构 133__eol__6.4.2 树、森林和二叉树的相互转换 135__eol__6.4.3 树和森林的遍历 138__eol__6.4.4 树和森林的其他基本运算 141__eol__*6.5 线索二叉树 143__eol__6.6 算法拓展 145__eol__习题6 145__eol__第7章 树和二叉树的应用 148__eol__*7.1 表达式树 148__eol__7.2 哈夫曼树和哈夫曼编码 153__eol__7.2.1 哈夫曼树 153__eol__7.2.2 哈夫曼编码 157__eol__7.3 堆和优先级队列 160__eol__7.3.1 堆 160__eol__7.3.2 优先级队列 161__eol__*7.4 并查集 167__eol__7.5 算法拓展 169__eol__习题7 171__eol__第8章 图 173__eol__8.1 图的概念 173__eol__8.2 图的存储结构 177__eol__8.2.1 邻接矩阵 177__eol__8.2.2 邻接表 181__eol__*8.2.3 十字链表 186__eol__*8.2.4 邻接多重表 187__eol__8.3 图的遍历 187__eol__8.3.1 深度优先遍历 187__eol__8.3.2 广度优先遍历 190__eol__8.3.3 图的连通分量和生成树 192__eol__8.4 算法拓展 193__eol__习题8 194__eol__第9章 图的应用 197__eol__9.1 最小生成树 197__eol__9.1.1 最小生成树的概念 197__eol__9.1.2 Prim算法 198__eol__9.1.3 Kruskal算法 201__eol__9.2 有向无环图及其应用 204__eol__9.2.1 拓扑排序 205__eol__9.2.2 关键路径 210__eol__9.3 最短路径 216__eol__9.3.1 单源点最短路径 216__eol__9.3.2 每对顶点之间的最短路径 220__eol__9.4 算法拓展 223__eol__习题9 224__eol__第10章 集合与查找 226__eol__10.1 基本概念 226__eol__10.2 静态查找表上的查找 227__eol__10.2.1 顺序查找 227__eol__10.2.2 折半查找 229__eol__10.2.3 分块查找 233__eol__10.3 动态查找表上的查找 234__eol__10.3.1 二叉查找树 234__eol__10.3.2 平衡二叉树 241__eol__*10.3.3 B树 254__eol__*10.3.4 B+树 259__eol__*10.3.5 字典树 260__eol__10.4 算法拓展 261__eol__习题10 264__eol__第11章 散列表 267__eol__11.1 散列表的概念 267__eol__11.2 构造散列函数的方法 268__eol__11.2.1 直接定址法 268__eol__11.2.2 折叠法 268__eol__11.2.3 数字分析法 268__eol__11.2.4 平方取中法 268__eol__11.2.5 除留余数法 269__eol__11.3 解决冲突的方法 269__eol__11.3.1 闭散列法 269__eol__11.3.2 开散列法 272__eol__11.4 散列表的查找性能分析 272__eol__11.5 散列表的实现 273__eol__11.5.1 闭散列表的表示和实现 274__eol__11.5.2 开散列表的表示和实现 278__eol__11.5.3 闭散列表与开散列表的比较 281__eol__习题11 281__eol__第12章 排序 283__eol__12.1 排序的基本概念 283__eol__12.2 插入排序 284__eol__12.2.1 直接插入排序 284__eol__12.2.2 折半插入排序 285__eol__12.2.3 希尔排序 285__eol__12.3 交换排序 287__eol__12.3.1 冒泡排序 287__eol__12.3.2 快速排序 288__eol__12.4 选择排序 292__eol__12.4.1 直接选择排序 292__eol__12.4.2 堆排序 292__eol__*12.4.3 锦标赛排序 295__eol__12.5 归并排序 296__eol__*12.6 基数排序 298__eol__12.7 各种内部排序算法的比较 300__eol__*12.8 外部排序 303__eol__12.8.1 置换选择排序 304__eol__12.8.2 多路归并排序 305__eol__习题12 306__eol__附录A 情景项目 309__eol__参考资料 313