第1章 绪论 1 1.1 “数据结构”的研究内容 1 1.2 本书的内容结构 2 1.3 贯穿“数据结构”的基本概念 2 1.3.1 数据 2 1.3.2 数据元素 2 1.3.3 数据项 3 1.3.4 数据对象 3 1.3.5 数据结构 3 1.3.6 数据类型 5 1.4 “数据结构”的三要素 6 1.4.1 逻辑结构 6 1.4.2 存储结构 7 1.4.3 运算 9 1.5 算法 10 1.5.1 算法的定义及特征 10 1.5.2 算法复杂度 11 第2章 线性表 14 2.1 线性表的逻辑结构 14 2.2 线性表的存储结构 15 2.2.1 顺序表 15 2.2.2 单链表 17 2.2.3 双链表 18 2.2.4 循环单链表 19 2.2.5 循环双链表 19 2.2.6 静态链表 20 2.3 线性表的基本操作的定义 21 2.4 线性表的基本操作的实现 21 2.4.1 基于顺序表的实现 21 2.4.2 基于单链表的实现 25 2.4.3 基于双链表的实现 31 2.4.4 基于循环单链表的实现 35 2.4.5 基于循环双链表的实现 39 2.4.6 基于静态链表的实现 43 第3章 栈和队列 47 3.1 栈 47 3.1.1 栈的逻辑结构 47 3.1.2 栈的存储结构 48 3.1.3 栈的基本操作的定义 50 3.1.4 栈的基本操作的实现 50 3.2 队列 56 3.2.1 队列的逻辑结构 56 3.2.2 队列的存储结构 56 3.2.3 队列的基本操作的定义 59 3.2.4 队列的基本操作的实现 59 3.2.5 双端队列 65 3.3 栈和队列的应用 66 3.3.1 栈在数制转换中的应用 66 3.3.2 栈在表达式括号匹配检验中的应用 67 3.3.3 栈在表达式求值中的应用 67 3.3.4 栈在递归中的应用 69 3.3.5 队列在二叉树和树的层次遍历中的应用 70 3.3.6 队列在计算机及网络系统中的应用 71 第4章 串 72 4.1 串的逻辑结构 72 4.2 串的存储结构 73 4.2.1 定长顺序存储表示 73 4.2.2 堆分配存储表示 73 4.2.3 块链存储表示 74 4.3 串的基本操作的定义 75 4.4 串的基本操作的实现 76 4.4.1 基于定长顺序存储表示的实现 76 4.4.2 基于堆分配存储表示的实现 80 4.4.3 基于块链存储表示的实现 84 4.5 串的模式匹配 84 4.5.1 模式匹配算法 84 4.5.2 next和nextval数组的计算 89 第5章 数组和广义表 94 5.1 数组 94 5.1.1 数组的逻辑结构 94 5.1.2 数组的存储结构 94 5.1.3 数组的基本操作 96 5.1.4 数组的基本操作的实现 96 5.1.5 数组的应用：矩阵的压缩存储 96 5.2 广义表 106 5.2.1 广义表的逻辑结构 106 5.2.2 广义表的存储结构 107 第6章 树和二叉树 110 6.1 树和森林的逻辑结构 110 6.2 二叉树 112 6.2.1 二叉树的逻辑结构 112 6.2.2 二叉树的存储结构 115 6.2.3 二叉树的遍历 117 6.2.4 二叉树的线索化 123 6.3 树和森林 130 6.3.1 树和森林的存储结构 130 6.3.2 树和森林的遍历 134 6.4 二叉树、树和森林的相互转换 136 6.4.1 树、森林转换为二叉树 136 6.4.2 二叉树转换为树（或森林） 137 6.5 哈夫曼树和哈夫曼编码 137 6.5.1 哈夫曼树的相关概念及定义 137 6.5.2 哈夫曼树的构造过程 139 6.5.3 哈夫曼树的特点 139 6.5.4 哈夫曼编码 140 第7章 图 142 7.1 图的逻辑结构 142 7.2 图的存储结构 146 7.2.1 数组表示法 147 7.2.2 邻接表 148 7.2.3 邻接多重表 150 7.2.4 十字链表 152 7.3 图的遍历 154 7.3.1 深度优先搜索 154 7.3.2 广度优先搜索 156 7.3.3 遍历算法相关结论 159 7.4 图的应用 161 7.4.1 最小生成树 161 7.4.2 最短路径 166 7.4.3 有向无环图的应用 172 第8章 查找 180 8.1 查找的基本概念 180 8.1.1 查找 180 8.1.2 查找表 180 8.1.3 关键字 181 8.1.4 平均查找长度 181 8.2 线性表的查找 181 8.2.1 顺序查找算法 182 8.2.2 折半查找算法 186 8.2.3 分块查找算法 189 8.3 树表 191 8.3.1 二叉排序树 191 8.3.2 平衡二叉树 196 8.3.3 B-树和B+树 200 8.4 哈希表 207 8.4.1 基本概念 207 8.4.2 哈希函数的选择与构造 208 8.4.3 处理冲突的方法 210 8.4.4 哈希表的构建、查找及性能分析 212 第9章 排序 217 9.1 排序的概念 217 9.2 排序的分类 217 9.2.1 根据是否涉及外存分类 217 9.2.2 按稳定性分类 218 9.2.3 按适用性分类 219 9.3 内部排序 219 9.3.1 插入排序 219 9.3.2 交换排序 226 9.3.3 选择排序 233 9.3.4 归并排序 240 9.3.5 基数排序 242 9.3.6 内部排序算法的比较 245 9.4 外部排序 246 9.4.1 基本概念 246 9.4.2 外部排序方法 246 9.4.3 高效的外部排序 247 参考文献 254 附录A 算法时间复杂度分析方法 255