全书共有10章,系统地讲述了线性表、堆栈、队列、数组、树、查找、图、排序等内容,还安排了习题和实验。本书重视算法及其实践性,书中算法都有完整的C语言程序,程序代码注释详细。为了让读者能够及时地检验学习效果、把握学习进度,每章都附有丰富的习题。

第1章 绪论 1 1.1 数据结构起源 1 1.2 基本概念和术语 1 1.2.1 基本概念 1 1.2.2 数据结构 2 1.3 抽象数据类型 4 1.4 算法和算法分析 5 1.4.1 算法 5 1.4.2 算法的时间复杂度 5 1.4.3 *好、*坏和平均时间复 杂度 6 1.4.4 算法的空间复杂度 7 1.5 本章小结 7 习题 7 第2章 线性表 9 2.1 线性表定义 9 2.2 线性表的顺序存储结构和实现 10 2.2.1 线性表的顺序存储结构 10 2.2.2 顺序表基本运算的实现 11 2.3 线性表的链式存储结构和实现 14 2.3.1 单链表的定义和表示 15 2.3.2 单链表基本运算的实现 15 2.3.3 带表头结点的单链表 20 2.3.4 单循环链表 22 2.3.5 双向链表 22 2.4 顺序表与链表的比较 23 2.5 线性表的应用 24 2.6 本章小结 27 习题 27 第3章 堆栈和队列 29 3.1 堆栈 29 3.1.1 堆栈ADT 29 3.1.2 堆栈的顺序表示 29 3.1.3 堆栈的链接表示 31 3.2 队列 31 3.2.1 队列ADT 31 3.2.2 队列的顺序表示 32 3.2.3 队列的链接表示 35 3.3 表达式计算 35 3.3.1 中缀表达式 35 3.3.2 后缀表达式及其求值方法 35 3.3.3* 中缀表达式转换为后缀 表达式 40 3.4 递归 44 3.4.1 递归的概念 44 3.4.2 递归的实现 45 3.5 本章小结 46 习题 47 第4章 数组和字符串 48 4.1 数组 48 4.1.1 一维数组 48 4.1.2 二维数组 49 4.1.3 多维数组 50 4.2 数组���抽象数据类型 50 4.3 特殊矩阵 53 4.3.1 对称矩阵 53 4.3.2 三角矩阵 54 4.4 稀疏矩阵 55 4.4.1 稀疏矩阵的抽象数据类型 55 4.4.2 稀疏矩阵的转置算法 57 4.5 字符串 60 4.5.1 字符串的抽象数据类型 60 4.5.2 简单字符串匹配算法 61 4.5.3 改进的字符串匹配算法 64 4.6 本章小结 68 习题 68 第5章 树和二叉树 70 5.1 树 70 5.1.1 树的定义 70 5.1.2 基本术语 71 5.2 二叉树 72 5.2.1 二叉树的定义 72 5.2.2 二叉树的性质 73 5.2.3 二叉树ADT 74 5.2.4 二叉树的存储表示 75 5.2.5 二叉树的存储实现和基本运算 76 5.3 二叉树的遍历 78 5.3.1 二叉树遍历的递归算法 78 5.3.2 二叉树遍历的应用实例 81 5.3.3 二叉树遍历的非递归算法 83 5.3.4 线索二叉树的基本概念和构造 85 5.4 树和森林 86 5.4.1 森林与二叉树的转换 86 5.4.2 树和森林的存储表示 88 5.4.3 树和森林的遍历 91 5.5 堆和优先权队列 92 5.5.1 堆 92 5.5.2 优先权队列 95 5.6 哈夫曼树和哈夫曼编码 99 5.6.1 树的路径长度 100 5.6.2 哈夫曼树和哈夫曼算法 102 5.6.3 构造哈夫曼树 103 5.6.4 哈夫曼编码 104 5.7 本章小结 105 习题 105 第6章 集合和搜索 108 6.1 集合的表示 108 6.1.1 集合的基本概念 108 6.1.2 动态集ADT 109 6.1.3 集合的表示 109 6.2 顺序搜索 110 6.2.1 无序表的顺序搜索 110 6.2.2 有序表的顺序搜索 110 6.3 对半搜索 111 6.3.1 对半搜索方法 111 6.3.2 二叉判定树 114 6.4 本章小结 115 习题 115 第7章 搜索树 116 7.1 二叉搜索树 116 7.1.1 二叉搜索树的定义 116 7.1.2 二叉搜索树的搜索 117 7.1.3 二叉搜索树的插入 118 7.1.4 二叉搜索树的删除 119 7.1.5 二叉搜索树的高度 121 7.2* 二叉平衡树 122 7.2.1 二叉平衡树的定义 122 7.2.2 二叉平衡树的平衡调整 方法 122 7.2.3 二叉平衡树的插入 126 7.2.4 二叉平衡树的高度 127 7.3 m叉搜索树 128 7.3.1 m叉搜索树的定义 128 7.3.2 m叉搜索树的高度 129 7.4 B?树 130 7.4.1 B?树的定义 130 7.4.2 B?树的高度 131 7.4.3 B?树的搜索 131 7.4.4 B?树的插入 132 7.4.5 B?树的删除 133 7.5 本章小结 136 习题 136 第8章 散列表 138 8.1 散列技术简介 138 8.2 散列函数 139 8.3 散列冲突处理 141 8.3.1 拉链法 141 8.3.2 开地址法 142 8.3.3 性能分析 149 8.4 本章小结 149 习题 150 第9章 图 151 9.1 图的基本概念 151 9.1.1 图的定义 151 9.1.2 图的基本术语 152 9.1.3 图的类型定义 154 9.2 图的存储结构 154 9.2.1 邻接矩阵表示法 154 9.2.2 邻接矩阵的实现 155 9.2.3 邻接表表示法 158 9.2.4 邻接表的实现 158 9.3 图的遍历 161 9.3.1 深度优先遍历 162 9.3.2 宽度优先遍历 163 9.4 拓扑排序 165 9.4.1 AOV网 165 9.4.2 AOV网的拓扑排序 166 9.5 关键路径 167 9.5.1 AOE网 167 9.5.2 AOE网的关键路径 168 9.6 *小代价生成树 171 9.6.1 *小代价生成树的基本概念 171 9.6.2 普里姆算法 171 9.6.3 克鲁斯卡尔算法 173 9.7 单源*短路径 176 9.7.1 *短路径问题 176 9.7.2 单源*短路径问题 176 9.8 所有顶点之间的*短路径 179 9.9 本章小结 181 习题 182 第10章 排序 185 10.1 排序的基本概念 185 10.2 简单排序算法 186 10.2.1 简单选择排序 186 10.2.2 直接插入排序 189 10.2.3 冒泡排序 191 10.3 快速排序算法 194 10.4 两路合并排序算法 198 10.5 堆排序算法 201 10.6 外排序 204 10.6.1 预处理 204 10.6.2 多路合并 208 10.6.3 *佳合并树 211 10.6.4 完整的外排序过程 213 10.7 本章小结 213 习题 213 附录1 综合实验 215 附录2 配套慕课使用说明 220