国外计算机科学教材系列：数据结构与算法分析（C++版）（第2版）

　　目  录
　　第一部分 预 备 知 识
　　第1章 数据结构和算法  
　　11  数据结构的原则  
　　111 学习数据结构的必要性
　　112 代价与效益  
　　12 抽象数据类型和数据结构  
　　13 问题、算法和程序  
　　14 深入学习导读  
　　15 习题  
　　第2章 数学预备知识  
　　21 集合和关系  
　　22 常用数学术语  
　　23 对数  
　　24 递归  
　　25 级数求和与递归  
　　26  数学证明方法  
　　261 反证法  
　　262 数学归纳法  
　　27 评估  
　　28 深入学习导读  
　　29 习题  
　　第3章 算法分析  
　　31 概述  
　　32 最佳、最差和平均情况  
　　33 换一台更快的计算机，还是换一种更快的算法  
　　34  渐近分析  
　　341 上限  
　　342 下限  
　　343 Θ表示法  
　　344 化简法则  
　　35 程序运行时间的计算  
　　36 问题的分析  
　　37 容易混淆的概念  
　　38 多参数问题  
　　39 空间代价  
　　310 实际操作中的一些因素  
　　311 深入学习导读  
　　312 习题  
　　313 项目设计  
　　第二部分 基本数据结构
　　第4章 线性表、栈和队列  
　　41  线性表  
　　411 顺序表的实现  
　　412 链表  
　　413 线性表实现方法的比较
　　
　　414 元素的表示  
　　415 双链表  
　　42 字典ADT  
　　43  栈  
　　431 顺序栈  
　　432 链式栈  
　　433 顺序栈与链式栈的比较
　　
　　434 递归的实现  
　　44  队列  
　　441 顺序队列  
　　442 链式队列  
　　443 顺序队列与链式队列的比较
　　
　　45 深入学习导读  
　　46 习题  
　　47 项目设计  
　　第5章 二叉树  
　　51 定义及主要特性  
　　511 满二叉树定理  
　　512 二叉树的抽象数据类型
　　
　　52 周游二叉树  
　　53 二叉树的实现  
　　531 使用指针实现二叉树  
　　
　　532 空间代价  
　　533 使用数组实现完全二叉树
　　
　　54 二叉查找树  
　　55 堆与优先队列  
　　56 Huffman编码树  
　　561 建立Huffman编码树  
　　
　　562 Huffman编码及其用法
　　
　　57 深入学习导读  
　　58 习题  
　　59 项目设计  
　　第6章 树  
　　61 树的定义与术语  
　　611 树结点的ADT  
　　612 树的周游  
　　62 父指针表示法  
　　63 树的实现  
　　631 子结点表表示法  
　　632 左子结点/右兄弟结点表示法
　　
　　633 动态结点表示法  
　　634 动态左子结点/右兄弟结点表示法
　　
　　64 K叉树  
　　65 树的顺序表示法  
　　66 深入学习导读  
　　67 习题  
　　68 项目设计  
　　第三部分 排序和检索
　　第7章 内排序  
　　7.1 排序术语及记号  
　　7.2  三种代价为Θ(n2)的排序方法  
　　7.2.1 插入排序  
　　7.2.2 起泡排序  
　　7.2.3 选择排序  
　　7.2.4 交换排序算法的时间代价
　　  7.3 Shell排序  
　　7.4 快速排序  
　　7.5 归并排序  
　　7.6 堆排序  
　　7.7 分配排序和基数排序  
　　7.8 对各种排序算法的实验比较  
　　7.9 排序问题的下限  
　　7.10 深入学习导读  
　　7.11 习题  
　　7.12 项目设计  
　　第8章 文件管理和外排序  
　　8.1 主存储器和辅助存储器  
　　8.2 磁盘  
　　8.2.1 磁盘结构  
　　8.2.2 磁盘访问代价  
　　8.3 缓冲区和缓冲池  
　　8.4 程序员的文件视图  
　　8.5 外部排序  
　　8.6 外部排序的简单方法  
　　8.7 置换选择排序  
　　8.8 多路归并  
　　8.9 深入学习导读  
　　8.10 习题  
　　8.11 项目设计  
　　第9章 检索  
　　9.1 检索已排序的数组  
　　9.2 自组织线性表  
　　9.3 集合的检索  
　　9.4  散列方法  
　　9.4.1 散列函数  
　　9.4.2 开散列方法  
　　9.4.3 闭散列方法  
　　9.5 深入学习导阅读  
　　9.6 习题  
　　9.7 项目设计  
　　第10章 索引技术  
　　10.1 线性索引  
　　10.2 ISAM  
　　10.3 树形索引  
　　10.4 23树  
　　10.5 B树  
　　10.5.1 B+树  
　　10.5.2 B树分析  
　　10.6 深入学习导读  
　　10.7 习题  
　　10.8 项目设计  
　　第四部分 应用与高级话题
　　第11章 图  
　　11.1 术语和表示法  
　　11.2 图的实现  
　　11.3  图的周游  
　　11.3.1 深度优先搜索  
　　11.3.2 广度优先搜索  
　　11.3.3 拓扑排序  
　　11.4 最短路径问题  
　　11.4.1 单源最短路径  
　　11.4.2 每对顶点间的最短路径
　　  11.5 最小支撑树  
　　11.5.1 Prim算法  
　　11.5.2 Kruskal算法  
　　11.6 深入学习导读  
　　11.7  习题  
　　11.8 项目设计  
　　第12章 线性表和数组高级技术  
　　
　　12.1 跳跃表  
　　12.2 广义表  
　　12.3 矩阵的表示方法  
　　12.4  存储管理  
　　12.4.1 动态存储分配  
　　12.4.2 失败处理策略和无用单元收集   
　　12.5 深入学习导读  
　　12.6 习题  
　　12.7 项目设计  
　　第13章 高级树形结构  
　　13.1 Trie结构  
　　13.2 平衡树  
　　13.2.1 AVL树  
　　13.2.2 伸展树  
　　13.3 空间数据结构  
　　13.3.1 kd树  
　　13.3.2 PR四分树  
　　13.3.3 其他空间数据结构  
　　13.4 深入学习导读  
　　13.5 习题  
　　13.6 项目设计  
　　第14章 分析技术  
　　14.1 求和技术  
　　14.2 递归关系  
　　14.2.1 估计上下限  
　　14.2.2 扩展递归  
　　14.2.3 分治法递归  
　　14.2.4 快速排序平均情况分析
　　  14.3 均摊分析  
　　14.4 深入学习导读  
　　14.5 习题  
　　14.6 项目设计  
　　第15章 计算的限制  
　　15.1 归约  
　　15.2 难解问题  
　　15.2.1 NP完全性  
　　15.2.2 绕过NP完全性问题
　　  15.3 不可解问题  
　　15.3.1 不可数性  
　　15.3.2 停机问题的不可解性  
　　
　　15.3.3 确定程序行为是不可解的
　　  15.4 深入学习导读  
　　15.5 习题  
　　15.6 项目设计  
　　附录A 实用函数  
　　参考文献

　　本书采用程序员最爱用的面向对象C+ +语言来描述数据结构和算法，并把数据结构原理和算法分析技术有机地结合在一起，系统介绍了各种类型的数据结构和排序、检索的各种方法。作者非常注意对每一种数据结构不同存储方法及有关算法进行分析比较。书中还引入了一些比较高级的数据结构与先进的算法分析技术，并介绍了可计算性理论的一般知识。本版的重要改进在于引入了参数化的模板，从而提高了算法中数据类型的通用性，支持高效的代码重用。本书概念清楚、逻辑性强、内容新颖，可作为大专院校计算机软件专业与计算机应用专业学生的教材和参考书，也可供计算机工程技术人员参考。