程序设计中实用的数据结构

出版时间：2012-1  出版社：人民邮电出版社  作者：王建德,吴永辉  页数：370  
Tag标签：无  

内容概要

　　本书对近年来程序设计教育和竞赛培训活动中涌现的许多实用的数据结构设计方法进行了全面总结，通过深入的分析和生动的实例引导读者寻找问题中各对象之间的关系，确定数学模型所使用的逻辑结构；实现对各个对象的操作，即确定数据所采用的存储结构；将数据类型与定义在该类型上的运算融于一体，为面向对象的程序设计方法奠定基础。
　　 本书既是大学计算机专业数据结构课程和算法设计课程的优秀参考书，也是大中学生程序设计竞赛不可多得的培训教材。
本书特色
　　按照数据结构的知识体系，全书分为“线性表”、“树型问题”和“图型问题”三篇，介绍了几十种存储方式和相应的算法。
介绍了许多实用的数据结构设计方法，同时引导读者尽可能采用“扬长避短”的选择原则和“取长补短”的结合方法，选择有利于提升算法效率的数据结构。
对每个比较难懂的概念都举实例加以说明，对每个比较抽象的定理都有具体的应用例证帮助理解，对每个经典算法都有清晰的程序流程给予示范。此外，还大量运用图表，使得概念、定理和算法的由来变得具体、形象和直观。
书中采用了一种结构清晰、移植性强且贴近自然语言表述的类程序设计语言。只要读者具备Pascal和C等任一种语言的基础，就可以比较轻松地读懂其语义。

作者简介

　　王建德
国务院特殊津贴专家、上海师范大学特聘教授、控江中学特级教师。他辅导学生在国际奥林匹克信息学竞赛（IOI）中获8金、4银、2铜，先后出版了《新编实用算法分析与程序设计》和《程序设计中常用的计算思维方式》等多本广受好评的图书，这些图书长期以来是国内各类程序设计竞赛的必备教程。
　　吴永辉
博士，复旦大学计算机科学与工程系副教授，ACM-ICPC中国赛区指导委员会成员，复旦大学ACM程序设计竞赛队教练。自2001年起连续带队进入
ACM-ICPC世界总决赛，并取得过世界第六名的佳绩。主要研究方向为数据库，在《计算机研究与发展》、《软件学报》以及重大学术会议上发表过多篇论文，参与翻译的著作有《数据通信与网络》和《数据通信、计算机网络与开放系统》。

书籍目录

上篇 讨论线性表
　第1章 数组
　　1.1 数组的基本概念
　　1.1.1 数组是一种顺序存储结构
　　1.1.2 数组是程序设计中使用频率最高的数据类型
　　1.2 优化数组的存储方式
　　1.2.1 规则矩阵的压缩存储
　　1.2.2 稀疏矩阵的压缩存储
　　1.2.3 矩阵的压缩存储
　　1.3 排序与顺序统计
　　1.3.1 排序的基本概念
　　1.3.2 计数排序与贪心策略
　　1.3.3 采用“二分”策略的排序方法
　　1.3.4 顺序统计的基本方法
　第2章 链式存储结构
　　2.1 链表的基本概念
　　2.1.1 单链表
　　2.1.2 循环链表
　　2.1.3 双向链表
　　2.2 链表的基本运算
　　2.2.1 构建单链表
　　2.2.2 插入操作
　　2.2.3 删除操作
　　2.2.4 读取操作
　　2.3 链表的应用
　第3章 两种存取方式特殊的线性表
　　3.1 “后进先出”的栈
　　3.1.1 栈的基本运算
　　3.1.2 栈的应用
　　3.2 “先进先出”的队列
　　3.2.1 队列的基本运算
　　3.2.2 队列的应用
　第4章 散列技术
　　4.1 散列表
　　4.2 散列函数的设计
　　4.3 消除冲突的基本方法
　　4.3.1 使用开放寻址法消除冲突
　　4.3.2 使用分离链接法消除冲突
　第5章 后缀数组
　　5.1 后缀数组的基本概念
　　5.2 采用倍增算法求解rank数组
　　5.3 利用rank数组计算最长公共前缀
　　5.3.1 计算最长公共前缀是一个典型的RMQ问题
　　5.3.2 计算最长公共前缀的基本方法
　　5.4 后缀数组的应用
　　5.4.1 利用后缀数组处理单个字符串
　　5.4.2 两个字符串的公共子串问题
　　5.4.3 多个字符串共享子串的问题
　　上篇小结
中篇 讨论树型问题
　第6章 树的基本概念和遍历规则
　　6.1 树的递归定义
　　6.2 节点的分类
　　6.3 有关度的定义
　　6.4 树的深度(高度)
　　6.5 森林
　　6.6 有序树和无序树
　　6.7 树的表示方法
　　6.8 树的遍历规则
　　6.8.1 先根次序遍历树
　　6.8.2 后根次序遍历树
　第7章 树的存储结构
　　7.1 采用数组存储入边信息
　　7.1.1 存储无权树的入边信息
　　7.1.2 存储加权树的入边信息
　　7.2 采用数组存储所有儿子的地址信息
　　7.2.1 采用整数存储儿子的数组下标
　　7.2.2 采用指针存储儿子的地址
　　7.3 采用邻接表存储出边信息
　　7.3.1 采用数组存储方式的邻接表
　　7.3.2 采用单链表存储方式的邻接表
　　7.4 无根树的一般存储方式
　第8章 二叉树
　　8.1 二叉树的基本概念和存储结构
　　8.1.1 二叉树的基本概念
　　8.1.2 二叉树的存储结构
　　8.2 将普通有序树和森林转换成对应的二叉树
　　8.2.1 将普通有序树转换成对应的二叉树
　　8.2.2 将普通有序树组成的森林转换成对应的二叉树
　　8.3 二叉树的遍历
　　8.3.1 前序遍历
　　8.3.2 中序遍历
　　8.3.3 后序遍历
　　8.3.4 由两种遍历确定二叉树结构
　第9章 并查集
　　9.1 并查集的基本概念
　　9.2 查找元素所在树的根节点并进行路径压缩
　　9.3 合并两个元素所在的集合
　第10章 堆
　　10.1 二叉堆的概念
　　10.2 在插入或删除节点时维护堆性质
　　10.2.1 插入节点
　　10.2.2 删除最小值元素
　　10.3 建堆
　　10.4 堆排序
　第11章 最优二叉树
　　11.1 最优二叉树的基本概念
　　11.2 构造最优二叉树
　第12章 线段树
　　12.1 线段树的基本概念
　　12.1.1 用于区间运算的线段树
　　12.1.2 用于数据统计的线段树
　　12.1.3 线段树的数据结构
　　12.2 线段树的基本操作
　　12.2.1 建立线段树
　　12.2.2 在区间内插入线段或数据
　　12.2.3 删除区间内的线段或数据
　　12.2.4 计算区间内的线段或数据状态
　　12.3 线段树在静态统计问题上的应用
　　12.4 线段树在动态统计问题上的应用
　第13章 二叉查找树
　　13.1 二叉排序树
　　13.1.1 二叉排序树的基本概念
　　13.1.2 二叉排序树的基本操作
　　13.2 静态二叉排序树
　　13.2.1 静态二叉排序树的特征
　　13.2.2 静态二叉排序树的构造方法
　　13.2.3 在静态二叉排序树上进行数据统计
　　13.3 子树大小平衡树(SBT)
　　13.3.1 SBT的性质
　　13.3.2 旋转
　　13.3.3 动态维护SBT的平衡特性
　　13.3.4 SBT的基本操作
　　中篇小结
下篇 讨论图型问题
　第14章 图的基本概念及其存储结构
　　14.1 图的基本概念
　　14.2 图的简单分类
　　14.2.1 无向图和有向图
　　14.2.2 无权图和加权图
　　14.2.3 稀疏图和稠密图
　　14.2.4 完全图和补图
　　14.2.5 树和森林
　　14.2.6 图的生成树和生成森林
　　14.2.7 平面图
　　14.2.8 二分图
　　14.2.9 相交图和区间图
　　14.3 图的存储结构
　　14.3.1 存储节点间相邻关系的相邻矩阵
　　14.3.2 存储边信息的3种数据结构
　第15章 图的遍历及其应用
　　15.1 广度优先遍历(BFS算法)
　　15.1.1 BFS算法的基本概念
　　15.1.2 BFS算法的应用
　　15.2 深度优先遍历(DFS算法)
　　15.2.1 DFS的基本概念
　　15.2.2 在DFS遍历过程中记录节点颜色变化的时间
　　15.2.3 根据节点颜色对边进行分类
　　15.2.4 分析DFS森林的结构
　　15.2.5 使用DFS算法进行拓扑排序
　　15.2.6 使用DFS算法计算欧拉回路
　第16章 有向图的强连通分量和传递闭包
　　16.1 判定仙人掌图
　　16.2 计算强连通分量
　　16.3 传递闭包的应用
　第17章 无向图的连通性分析
　　17.1 计算节点的low函数
　　17.2 计算连通图的割点和桥
　　17.2.1 计算连通图的割点
　　17.2.2 计算连通图的桥
　　17.3 计算双连通子图
　　17.4 分析连通图的连通程度
　　17.4.1 连通图的顶连通度
　　17.4.2 连通图的边连通度
　第18章 最小生成树
　　18.1 基本概念
　　18.2 最小生成树的应用价值
　　18.3 最小生成树的计算策略
　　18.4 计算最小生成树的两种算法
　　18.4.1 Kruskal算法
　　18.4.2 Prim算法
　　18.5 最小生成树算法的应用实例
　第19章 加权图的单源最短路径问题
　　19.1 基本概念
　　19.1.1 单源算法是高效解决所有最短路径问题的基础
　　19.1.2 负权回路影响单源最短路径的计算
　　19.1.3 松弛技术是单源算法的核心
　　19.2 求解单源最短路径问题的3 种算法
　　19.2.1 Dijkstra算法
　　19.2.2 Bellman-Ford算法
　　19.2.3 SPFA算法
　　19.3 单源最短路径算法的应用实例
　第20章 二分图的匹配问题
　　20.1 基本概念
　　20.1.1 图的匹配概念
　　20.1.2 二分图的概念和判定方法
　　20.2 计算无权二分图的最大匹配
　　20.2.1 匈牙利算法的基本思路
　　20.2.2 匈牙利算法的基本流程
　　20.2.3 匈牙利算法的应用实例
　　20.3 计算带权二分图的最佳匹配
　　20.3.1 最佳匹配的概念
　　20.3.2 KM算法的基本思路
　　20.3.3 KM算法的基本流程和应用实例
　第21章 最大流问题
　　21.1 基本概念
　　21.2 在可增广路径的基础上计算最大流
　　21.2.1 可增广路径的基本概念
　　21.2.2 基于最大流定理上的最大流算法
　　21.3 按层次计算最大流的Dinic算法
　　21.3.1 Dinic算法的基本思路
　　21.3.2 Dinic算法的基本流程
　　21.4 利用最大流最小割定理解题
　　21.4.1 割的概念
　　21.4.2 最小割的计算方法和应用实例
　　21.5 计算多源多汇网络的可行流
　　21.6 网络增加容量下界因素后的流量计算问题
　　21.6.1 求容量有上下界的网络的最大流
　　21.6.2 求容量有上下界的网络的最小流
　　21.7 网络增加费用因素后的流量计算问题
　　21.7.1 计算最小费用最大流
　　21.7.2 计算容量有上下界的网络的最小费用最小流
　　下篇小结
　　　　

编辑推荐

　  ACM竞赛的培训资料， 程序设计竞赛的经典试题。 

用户评论 (总计16条)

•   确实是实用的数据结构，里面好多有趣和高效的算法值得读
•   如果你身为一个程序员还不明白什么是数据结构，那你可以买这本书了
  
  讲的很全面
•   本书采用伪代码的形式，适合于读者用自己熟悉的语言编写代码实现。本书的组织结构也非常清楚，分为线性表，树形结构，图形结构。适合有数据结构基础的读者深入学习，本书作为参考书也很不错
•   适合做较深入的培训教材
•   喜欢这本书，经常翻看。
•   应该在拓展一些
•   很好的书，伪代码看起来有些不适应，但值得反复学习
•   书城简单看了下决定回来买的，图文并茂，不至于看着看着睡着
•   刚出来的新书，正版 ，质量很好
•   本书主要讲了利用数据结构如树、图等做题的方法，适合有一定基础，想再提高的人看。
•   这本书与先前作者出的那本解题思路很多内容都相似，可能是解题思路缺货了吧，书上关于证明原理的说明与解题思路上的是一样的，个人觉得买了那本解题思路的话就没必要买这本了，不过这的确是本还不错的入门书。
•   老师推的书
•   可能有些人看不了这种代码。
•   用的什么自然语言，其实就是pascal，看起来巨不爽。这还是小事，关键里面的讲解其实非常一般，实现过程不是太难懂，就是用得很烂的方法。当初就是看到它的目录觉得讲的挺全的才买的，后悔啊！！！！
•   给中学生奥赛买的，内容很全面，基本上包括了必须要学的东西。不过有一个不足，写得不够通俗，特别是初中生很难自己看懂
•   要是这本书中的代码是用C语言描述的就好了，不过pascal也能看。就内容而言，这本书很全面。