数据结构基础（C语言版）第2版

《数据结构基础(C语言版)(第2版)》是最经典数据结构教材的最新版本，国内外大多数的同类教材都是以《数据结构基础(C语言版)(第2版)》为蓝本编写而来的。《数据结构基础(C语言版)(第2版)》用C作为描述语言，全面而生动地介绍了数据结构的有关知识，如数组、栈、队列、链表、树和图，以及构成所有软件基础的排序散列技术。此外，《数据结构基础(C语言版)(第2版)》还介绍了各种高级或特殊数据结构，如优先级队列、高效二叉查找树、多路查找树等。《数据结构基础(C语言版)(第2版)》对大多数算法都给出了计算时间在最优、最差情形下的复杂度分析。

第1章 基本概念 1 1.1 概观：系统生命周期 1 1.2 指针和动态存储分配 3 1.2.1 指针 3 1.2.2 动态存储分配 4 1.2.3 指针隐患 6 1.3 算法形式规范 6 1.3.1 综论 6 1.3.2 递归算法 11 1.4 数据抽象 14 1.5 性能分析 17 1.5.1 空间复杂度 18 1.5.2 时间复杂度 20 1.5.3 渐近记号（O，Ω，Θ） 27 1.5.4 实际复杂度 33 1.6 性能度量 35 1.6.1 定时 35 1.6.2 生成测试数据 39 1.7 参考文献和选读材料 40 第2章 数组和结构 41 2.1 数组 41 2.1.1 数组的抽象数据类型 41 2.1.2 C语言的数组 41 2.2 数组的动态存储分配 44 2.2.1 一维数组 44 2.2.2 二维数组 44 2.3 结构体和联合体 47 2.3.1 结构体 47 2.3.2 联合体 49 2.3.3 结构的内部实现 50 2.3.4 自引用结构 50 2.4 多项式 51 2.4.1 多项式的抽象数据类型 51 2.4.2 多项式的表示 52 2.4.3 多项式加法 55 2.5 稀疏矩阵 58 2.5.1 稀疏矩阵的抽象数据类型 58 2.5.2 稀疏矩阵的表示 58 2.5.3 矩阵转置 59 2.5.4 矩阵相乘 63 2.6 多维数组的表示 67 2.7 字符串 68 2.7.1 字符串的抽象数据类型 68 2.7.2 C语言的字符串 68 2.7.3 模式匹配 71 2.8 参考文献和选读材料 77 2.9 补充习题 78 第3章 栈与队列 83 3.1 栈 83 3.2 动态栈 87 3.3 队列 88 3.4 动态循环队列 92 3.5 迷宫问题 95 3.6 表达式求值 98 3.6.1 表达式 98 3.6.2 后缀表达式求值 100 3.6.3 中缀表达式转换成后缀表达式 103 3.7 多重栈与多重队列 108 3.8 补充习题 111 第4章 链表 113 4.1 单向链表 113 4.2 用C语言表示单向链表 115 4.3 链式栈与链式队列 121 4.4 多项式 124 4.4.1 多项式表示 124 4.4.2 多项式加法 125 4.4.3 销毁多项式 128 4.4.4 循环链表与多项式 129 4.4.5 小结 130 4.5 其它链表操作 133 4.5.1 单向链表操作 133 4.5.2 循环链表操作 134 4.6 等价类 135 4.7 稀疏矩阵 139 4.7.1 稀疏矩阵表示 139 4.7.2 输入稀疏矩阵 142 4.7.3 输出稀疏矩阵 144 4.7.4 销毁稀疏矩阵 144 4.8 双向链表 146 第5章 树 149 5.1 引论 149 5.1.1 术语 149 5.1.2 树的表示 151 5.2 二叉树 154 5.2.1 二叉树的抽象数据类型 154 5.2.2 二叉树的性质 155 5.2.3 二叉树的表示 157 5.3 遍历二叉树 159 5.3.1 中序遍历 160 5.3.2 先序遍历 161 5.3.3 后序遍历 161 5.3.4 非递归（循环）中序遍历 162 5.3.5 层序遍历 163 5.3.6 不设栈遍历二叉树 163 5.4 其它二叉树操作 164 5.4.1 复制二叉树 164 5.4.2 判断两个二叉树全等 164 5.4.3 可满足性问题 165 5.5 线索二叉树 168 5.5.1 线索 168 5.5.2 中序遍历线索二叉树 169 5.5.3 线索二叉树插入结点 170 5.6 堆 172 5.6.1 优先级队列 172 5.6.2 大根堆定义 174 5.6.3 大根堆插入操作 174 5.6.4 大根堆删除操作 176 5.7 二叉查找树 178 5.7.1 定义 178 5.7.2 二叉查找树的查找 179 5.7.3 二叉查找树的插入 180 5.7.4 二叉查找树的删除 181 5.7.5 二叉查找树的合并与分裂 182 5.7.6 二叉查找树的高度 183 5.8 选拔树 185 5.8.1 引子 185 5.8.2 优胜树 186 5.8.3 淘汰树 187 5.9 森林 188 5.9.1 森林转换为二叉树 189 5.9.2 遍历森林 189 5.10 不相交集合的表示 190 5.1 0.1 引子 190 5.1 0.2 合并与查找操作 191 5.1 0.3 划分等价类 197 5.11 二叉树的计数 199 5.1 1.1 不同态二叉树 199 5.1 1.2 栈置换 200 5.1 1.3 矩阵乘法 201 5.1 1.4 不同二叉树的数目 203 5.12 参考文献和选读材料 204 第6章 图 205 6.1 图的抽象数据类型 205 6.1.1 引子 205 6.1.2 图的定义和术语 206 6.1.3 图的表示 210 6.2 图的基本操作 216 6.2.1 深度优先搜索 216 6.2.2 广度优先搜索 217 6.2.3 连通分量 218 6.2.4 生成树 219 6.2.5 重连通分量 220 6.3 最小代价生成树 225 6.3.1 Kruskal算法 225 6.3.2 Prim算法 228 6.3.3 Sollin算法 229 6.4 最短路径和迁移闭包 230 6.4.1 单源点至所有其它节点：边权值非负 231 6.4.2 单源点至所有其它节点：边权值正负无限制 233 6.4.3 所有节点两两之间的最短路径 237 6.4.4 迁移闭包 238 6.5 活动网络 242 6.5.1 活动节点（AOV）网络 242 6.5.2 活动边（AOE）网络 247 6.6 参考文献和选读材料 253 6.7 补充习题 254 第7章 排序 256 7.1 动机 256 7.2 插入排序 259 7.3 快速排序 261 7.4 排序最快有多快 264 7.5 归并排序 265 7.5.1 归并 265 7.5.2 非递归归并排序 266 7.5.3 递归归并排序 267 7.6 堆排序 270 7.7 多关键字排序 273 7.8 链表排序和索引表排序 277 7.9 内部排序小结 284 7.10 外部排序 289 7.1 0.1 引子 289 7.1 0.2 k路归并 291 7.1 0.3 缓存与并行操作 292 7.1 0.4 生成多路数据 298 7.1 0.5 最优多路归并 300 7.11 参考文献和选读材料 303 第8章 Hash法 304 8.1 引言 304 8.2 静态Hash法 304 8.2.1 Hash表 304 8.2.2 Hash函数 305 8.2.3 溢出处理 307 8.2.4 处理溢出方法的理论估计 312 8.3 动态Hash法 315 8.3.1 动态Hash法的动机 315 8.3.2 设目录的动态Hash法 316 8.3.3 不设目录的动态Hash法 318 8.4 Bloom滤波器 320 8.4.1 差异文件及其应用 320 8.4.2 设计Bloom滤波器 321 8.5 参考文献和选读材料 323 第9章 优先级队列 324 9.1 单端优先级队列与双端优先级队列 324 9.2 左倾树 325 9.2.1 高度左倾树 325 9.2.2 权值左倾树 330 9.3 二项式堆 332 9.3.1 代价分摊 332 9.3.2 二项式堆的定义 333 9.3.3 二项式堆的插入 333 9.3.4 融合两个二项式堆 334 9.3.5 删除最小元 334 9.3.6 分析 336 9.4 Fibonacci堆 338 9.4.1 定义 338 9.4.2 F-堆的删除 338 9.4.3 减小关键字 339 9.4.4 上行切除 339 9.4.5 分析 340 9.4.6 F-堆与最短路径问题 342 9.5 配偶堆 344 9.5.1 定义 344 9.5.2 融合与插入 344 9.5.3 减小关键字值 345 9.5.4 删除最小元 346 9.5.5 删除任意元 348 9.5.6 实现细节 349 9.5.7 复杂度分析 349 9.6 对称最小-最大堆 350 9.6.1 定义与性质 350 9.6.2 SMMH的表示 351 9.6.3 SMMH的插入 351 9.6.4 SMMH的删除 353 9.7 区间堆 358 9.7.1 定义和性质 358 9.7.2 区间堆的插入 359 9.7.3 删除最小元 360 9.7.4 区间堆的初始化 361 9.7.5 区间堆操作的复杂度 361 9.7.6 区间外查找 361 9.8 参考文献和选读材料 363 第10章 高效二叉查找树 366 10.1 最优二叉查找树 366 10.2 AVL树 373 10.3 红-黑树 384 10.3.1 定义 384 10.3.2 红-黑树的表示 386 10.3.3 红-黑树的查找 386 10.3.4 红-黑树的插入 386 10.3.5 红-黑树的删除 389 10.3.6 红-黑树的合并 389 10.3.7 红-黑树的分裂 391 10.4 Splay树 393 10.4.1 自底向上Splay树 394 10.4.2 自顶向下Splay树 398 10.5 参考文献和选读材料 403 第11章 多路查找树 405 11.1 m-路查找树 405 11.1.1 定义和性质 405 11.1.2 m-路查找树的查找 406 11.2 B-树 407 11.2.1 定义和性质 407 11.2.2 B-树中数据元素的个数 408 11.2.3 B-树的插入 409 11.2.4 B-树的删除 412 11.3 B+-树 419 11.3.1 定义 419 11.3.2 B+-树的查找 420 11.3.3 B+-树的插入 420 11.3.4 B+-树的删除 422 11.4 参考文献和选读材料 426 第12章 数字查找结构 427 12.1 数字查找树 427 12.1.1 定义 427 12.1.2 查找、插入、删除 427 12.2 二路Trie树与Patricia树 428 12.2.1 二路Trie树 428 12.2.2 压缩二路Trie树 429 12.2.3 Patricia树 429 12.3 多路Trie树 434 12.3.1 定义 434 12.3.2 Trie树的查找 436 12.3.3 取样策略 437 12.3.4 Trie树的插入 439 12.3.5 Trie树的删除 439 12.3.6 变长关键字 440 12.3.7 Trie树的高度 440 12.3.8 空间需求与其它结点结构 440 12.3.9 查找前缀及其应用 443 12.3.10 压缩Trie树 444 12.3.11 设skip域的压缩Trie树 446 12.3.12 设边标记的压缩Trie树 446 12.3.13 压缩Trie树的空间需求 449 12.4 后缀树 450 12.4.1 你见过基因串吗 450 12.4.2 后缀树数据结构 450 12.4.3 查！查！查子串！（后缀树的查找） 453 12.4.4 后缀树的妙用 454 12.5 Trie树与互连网的包转发 455 12.5.1 IP路由 455 12.5.21 -bit Trie树 456 12.5.3 固定步长Trie树 457 12.5.4 不定步长Trie树 459 12.6 参考文献和选读材料 461 索引 463

暂无相关内容，正在全力查找中

暂无其它内容！

• 错误太多了，没见过错误更多的书了。

  来源：豆瓣 发布时间：2025-05-10 03:32:30

• 翻译的实在是垃圾！

  来源：豆瓣 发布时间：2025-05-10 03:32:30

• 正在读

  来源：豆瓣 发布时间：2025-05-10 03:32:30

• 请后来者指路

  来源：豆瓣 发布时间：2025-05-10 03:32:30

• 我的读后心得

  来源：豆瓣 发布时间：2025-05-10 03:32:30