顶部
收藏

数据结构——炫动的0、1之弦


作者:
邹恒明
定价:
32.00 元
版面字数:
570千字
开本:
16开
装帧形式:
平装
版次:
1
最新版次
印刷时间:
2012年
ISBN:
978-7-04-032486-0
物料号:
32486-00
出版时间:
2012-01-18
读者对象:
高等教育
一级分类:
计算机/教育技术类
二级分类:
计算机类专业核心课程
三级分类:
数据结构

本书从软件设计师和系统架构师的视角对数据结构进行阐述。通过两个角度的对望,以实际生活中的“问题”为驱动,以计算机软件设计师的“使用”为轴线,对每一种数据结构出现的动机、发展逻辑、表示方式、实现细节进行演绎,再现了数据结构的本质和内涵。本书讨论的结构包括栈、队列、表、栈表、索引表、跳转表、哈希表、二叉(查找)树、AVL树、伸展树、B/B+树、堆、幂堆、斐波那契堆、图、集合、划分和标准模板结构等。全书逻辑性强,注重阐述如何从一种想法转换为一种设计,又如何从设计转化为具体程序,从而化复杂为简单、化抽象为具体,大幅度降低学习和掌握数据结构的难度。为了方便准备考研的读者,本书还提供了2009—2010年两年的全国硕士研究生入学统一考试中数据结构部分真题的详细解析。

本书可作为高等学校计算机科学与技术、软件工程等相关专业数据结构课程教材,也可供程序设计人员及参加全国硕士研究生入学统一考试的应试者参考使用。

  • 目录
    • 第1章 数据结构基础
      • 1.1 什么是数据结构
        • 1.2 数据结构的定义
          • 1.3 数据结构的目的
            • 1.4 数据结构的种类
              • 1.5 数据结构与抽象数据类型
                • 1.6 数据结构的特性
                  • 1.7 数据结构的表现方式
                    • 1.8 数据结构的基本操作
                      • 1.8.1 数据结构操作的成本
                        • 1.8.2 最好、最坏、平均
                          • 1.8.3 O、Ω、Θ表示
                          • 1.9 数据结构的哲学
                            • 1.10 为什么学习数据结构
                              • 思考题
                              • 第2章 栈结构
                                • 2.1 后进先出即为栈
                                  • 2.2 栈的定义
                                    • 2.3 栈的实现
                                      • 2.4 栈的应用
                                        • 2.4.1 应用1:乘坐校园通勤车
                                          • 2.4.2 应用2:反转波兰计算器
                                            • 2.4.3 表达式的前、中、后缀表示及其转换
                                              • 2.4.4 应用3:括号匹配
                                              • 2.5 链接栈(栈的链接实现)
                                                • 2.6 链接栈存在的问题
                                                  • 思考题
                                                  • 第3章 队列结构
                                                    • 3.1 先进先出即为队列
                                                      • 3.2 队列的实现
                                                        • 3.3 队列实现的别样问题
                                                          • 3.4 队列的环形实现
                                                            • 3.5 基于计数器的循环队列的实现
                                                              • 3.6 队列应用举例
                                                                • 3.6.1 应用1:先来先得礼品专送
                                                                  • 3.6.2 应用2:机场模拟程序
                                                                  • 3.7 链接队列
                                                                    • 3.8 链接队列应用举例:多项式算术
                                                                      • 思考题
                                                                      • 第4章 表结构
                                                                        • 4.1 表的定义
                                                                          • 4.2 表的实现
                                                                            • 4.3 表结构应用举例:查找特定位置上的乘客编号
                                                                              • 4.4 链表———链接实现的表结构
                                                                                • 4.4.1 链表的插入操作
                                                                                  • 4.4.2 链表的删除操作
                                                                                    • 4.4.3 链表的其他操作
                                                                                      • 4.4.4 链表操作的时间成本
                                                                                        • 4.4.5 链表的优化:记住当前位置
                                                                                        • 4.5 双链表
                                                                                          • 4.6 基于数组和基于链表实现的表结构比较
                                                                                            • 4.7 链表的应用举例:字典
                                                                                              • 4.8 讨论:栈、队列、表、栈表、队表
                                                                                                • 思考题
                                                                                                • 第5章 查找操作
                                                                                                  • 5.1 什么是查找
                                                                                                    • 5.2 查找的实现
                                                                                                      • 5.3 顺序查找
                                                                                                        • 5.4 折半查找
                                                                                                          • 5.5 查找的成本下限
                                                                                                            • 5.6 常数查找
                                                                                                              • 5.6.1 直接查找
                                                                                                                • 5.6.2 间接查找
                                                                                                                • 思考题
                                                                                                                • 第6章 排序操作
                                                                                                                  • 6.1 什么是排序
                                                                                                                    • 6.2 排序的实现
                                                                                                                      • 6.3 插入排序
                                                                                                                        • 6.4 选择排序
                                                                                                                          • 6.5 冒泡/沉底排序
                                                                                                                            • 6.6 希尔排序
                                                                                                                              • 6.7 归并排序
                                                                                                                                • 6.7.1 归并排序的时间复杂性
                                                                                                                                  • 6.7.2 归并排序的链表实现
                                                                                                                                  • 6.8 快速排序
                                                                                                                                    • 6.8.1 快速排序的过程
                                                                                                                                      • 6.8.2 快速排序的时间成本分析
                                                                                                                                      • 思考题
                                                                                                                                      • 第7章 高级表结构
                                                                                                                                        • 7.1 穷则思变
                                                                                                                                          • 7.2 跳转表
                                                                                                                                            • 7.2.1 跳转表的定义
                                                                                                                                              • 7.2.2 跳转表操作
                                                                                                                                              • 7.3 索引表
                                                                                                                                                • 7.4 哈希表(散列表)
                                                                                                                                                  • 7.4.1 哈希函数
                                                                                                                                                    • 7.4.2 哈希结构中的碰撞问题
                                                                                                                                                      • 7.4.3 开放寻址哈希
                                                                                                                                                        • 7.4.4 封闭寻址哈希
                                                                                                                                                          • 7.4.5 探寻序列的设计
                                                                                                                                                            • 7.4.6 哈希结构的查找效率
                                                                                                                                                              • 7.4.7 哈希表的实现
                                                                                                                                                                • 7.4.8 哈希表结构的测试
                                                                                                                                                                • 7.5 讨论:跳转表、哈希表、
                                                                                                                                                                  • 索引表
                                                                                                                                                                    • 思考题
                                                                                                                                                                    • 第8章 树结构
                                                                                                                                                                      • 8.1 树结构的定义
                                                                                                                                                                        • 8.2 二叉树
                                                                                                                                                                          • 8.2.1 二叉树的另一种表示
                                                                                                                                                                            • 8.2.2 二叉树的遍历
                                                                                                                                                                              • 8.2.3 编译器中用到的二叉树结构
                                                                                                                                                                                • 8.2.4 二叉树的基本操作
                                                                                                                                                                                • 8.3 二叉查找树
                                                                                                                                                                                  • 8.3.1 二叉查找树的查找操作
                                                                                                                                                                                    • 8.3.2 二叉查找树的插入操作
                                                                                                                                                                                      • 8.3.3 二叉查找树的删除操作
                                                                                                                                                                                        • 8.3.4 构建初始二叉查找树
                                                                                                                                                                                          • 8.3.5 二叉查找树结构的测试
                                                                                                                                                                                            • 8.3.6 二叉查找树的高度
                                                                                                                                                                                            • 8.4 平衡二叉树
                                                                                                                                                                                              • 8.5 AVL高度平衡树
                                                                                                                                                                                                • 8.5.1 AVL树的实现
                                                                                                                                                                                                  • 8.5.2 AVL树的插入操作
                                                                                                                                                                                                    • 8.5.3 AVL树的节点删除操作
                                                                                                                                                                                                      • 8.5.4 AVL树结构的测试
                                                                                                                                                                                                      • 8.6 满二叉树和完全二叉树
                                                                                                                                                                                                        • 思考题
                                                                                                                                                                                                        • 第9章 高级树结构
                                                                                                                                                                                                          • 9.1 仅有二叉树是不够的
                                                                                                                                                                                                            • 9.2 B树
                                                                                                                                                                                                              • 9.2.1 B树的结构
                                                                                                                                                                                                                • 9.2.2 B树的键值
                                                                                                                                                                                                                  • 9.2.3 B树的优势
                                                                                                                                                                                                                  • 9.3 B+树和B倡树
                                                                                                                                                                                                                    • 9.3.1 B+树的定义
                                                                                                                                                                                                                      • 9.3.2 B+树的操作
                                                                                                                                                                                                                        • 9.3.3 B/B+树的代码实现
                                                                                                                                                                                                                          • 9.3.4 B+树的初始构建
                                                                                                                                                                                                                            • 9.3.5 B+树结构对磁盘查找的支持
                                                                                                                                                                                                                            • 9.4 伸展树结构
                                                                                                                                                                                                                              • 9.4.1 伸展树的特点
                                                                                                                                                                                                                                • 9.4.2 伸展树的操作
                                                                                                                                                                                                                                  • 9.4.3 伸展树的实现
                                                                                                                                                                                                                                    • 9.4.4 伸展树结构的测试
                                                                                                                                                                                                                                    • 9.5 哈夫曼树
                                                                                                                                                                                                                                      • 9.5.1 构造哈夫曼树
                                                                                                                                                                                                                                        • 9.5.2 哈夫曼树的应用
                                                                                                                                                                                                                                        • 9.6 树的转换
                                                                                                                                                                                                                                          • 9.6.1 一般树到二叉树的转换
                                                                                                                                                                                                                                            • 9.6.2 森林到二叉树的转换
                                                                                                                                                                                                                                            • 9.7 树和森林的遍历
                                                                                                                                                                                                                                              • 9.8 其他树结构
                                                                                                                                                                                                                                                • 思考题
                                                                                                                                                                                                                                                • 第10章 堆结构
                                                                                                                                                                                                                                                  • 10.1 什么是堆结构
                                                                                                                                                                                                                                                    • 10.2 二叉堆结构
                                                                                                                                                                                                                                                      • 10.2.1 二叉堆的表示
                                                                                                                                                                                                                                                        • 10.2.2 二叉堆的实现
                                                                                                                                                                                                                                                          • 10.2.3 堆的初始化构建
                                                                                                                                                                                                                                                            • 10.2.4 堆结构的测试———堆排序
                                                                                                                                                                                                                                                              • 10.2.5 堆的合并
                                                                                                                                                                                                                                                              • 10.3 幂树
                                                                                                                                                                                                                                                                • 10.4 幂堆
                                                                                                                                                                                                                                                                  • 10.4.1 幂堆的实现
                                                                                                                                                                                                                                                                    • 10.4.2 幂堆的合并操作
                                                                                                                                                                                                                                                                      • 10.4.3 幂堆的插入操作
                                                                                                                                                                                                                                                                        • 10.4.4 在幂堆里获取最大值
                                                                                                                                                                                                                                                                          • 10.4.5 在幂堆里删除最大值
                                                                                                                                                                                                                                                                          • 10.5 斐波那契堆
                                                                                                                                                                                                                                                                            • 10.5.1 斐波那契堆的定义
                                                                                                                                                                                                                                                                              • 10.5.2 斐波那契堆的操作实现
                                                                                                                                                                                                                                                                                • 10.5.3 斐波那契堆的节点更新操作
                                                                                                                                                                                                                                                                                  • 10.5.4 删除任意节点操作
                                                                                                                                                                                                                                                                                  • 思考题
                                                                                                                                                                                                                                                                                  • 第11章 图结构
                                                                                                                                                                                                                                                                                    • 11.1 图无处不在
                                                                                                                                                                                                                                                                                      • 11.2 图的定义
                                                                                                                                                                                                                                                                                        • 11.3 图的表示
                                                                                                                                                                                                                                                                                          • 11.4 图的遍历
                                                                                                                                                                                                                                                                                            • 11.5 图的最短路径操作
                                                                                                                                                                                                                                                                                              • 11.5.1 Dijkstra方法
                                                                                                                                                                                                                                                                                                • 11.5.2 Dijkstra方法的正确性证明
                                                                                                                                                                                                                                                                                                  • 11.5.3 最短路径方法的代码实现
                                                                                                                                                                                                                                                                                                  • 11.6 最小生成树操作
                                                                                                                                                                                                                                                                                                    • 11.6.1 Prim方法
                                                                                                                                                                                                                                                                                                      • 11.6.2 Prim方法的正确性证明
                                                                                                                                                                                                                                                                                                        • 11.6.3 Prim方法的代码实现
                                                                                                                                                                                                                                                                                                        • 11.7 图的拓扑排序操作
                                                                                                                                                                                                                                                                                                          • 11.7.1 深度优先的拓扑排序
                                                                                                                                                                                                                                                                                                            • 11.7.2 广度优先拓扑排序
                                                                                                                                                                                                                                                                                                            • 11.8 图结构的测试
                                                                                                                                                                                                                                                                                                              • 思考题
                                                                                                                                                                                                                                                                                                              • 第12章 集合结构
                                                                                                                                                                                                                                                                                                                • 12.1 什么是集合结构
                                                                                                                                                                                                                                                                                                                  • 12.2 数值集合
                                                                                                                                                                                                                                                                                                                    • 12.2.1 数值集合的实现
                                                                                                                                                                                                                                                                                                                      • 12.2.2 数值集合结构的测试
                                                                                                                                                                                                                                                                                                                      • 12.3 基于动态数组的集合结构
                                                                                                                                                                                                                                                                                                                        • 12.4 基于位矢量的集合结构
                                                                                                                                                                                                                                                                                                                          • 12.4.1 基于位矢量的集合结构定义
                                                                                                                                                                                                                                                                                                                            • 12.4.2 位矢量集合结构的并、交、减操作
                                                                                                                                                                                                                                                                                                                              • 12.4.3 位矢量集合结构的其他操作
                                                                                                                                                                                                                                                                                                                                • 12.4.4 位矢量集合结构的测试
                                                                                                                                                                                                                                                                                                                                • 12.5 基于链表的集合结构
                                                                                                                                                                                                                                                                                                                                  • 思考题
                                                                                                                                                                                                                                                                                                                                  • 第13章 划分结构
                                                                                                                                                                                                                                                                                                                                    • 13.1 划分结构
                                                                                                                                                                                                                                                                                                                                      • 13.1.1 划分结构的实现
                                                                                                                                                                                                                                                                                                                                        • 13.1.2 划分结构的测试
                                                                                                                                                                                                                                                                                                                                          • 13.1.3 划分结构的操作成本
                                                                                                                                                                                                                                                                                                                                          • 13.2 划分森林结构
                                                                                                                                                                                                                                                                                                                                            • 13.2.1 划分森林的实现
                                                                                                                                                                                                                                                                                                                                              • 13.2.2 构建与析构
                                                                                                                                                                                                                                                                                                                                                • 13.2.3 查找和合并
                                                                                                                                                                                                                                                                                                                                                • 13.3 优化的划分结构实现
                                                                                                                                                                                                                                                                                                                                                  • 13.3.1 路径压缩
                                                                                                                                                                                                                                                                                                                                                    • 13.3.2 按规模合并
                                                                                                                                                                                                                                                                                                                                                      • 13.3.3 按秩合并
                                                                                                                                                                                                                                                                                                                                                        • 13.3.4 划分类结构的测试
                                                                                                                                                                                                                                                                                                                                                        • 13.4 划分结构的应用
                                                                                                                                                                                                                                                                                                                                                          • 思考题
                                                                                                                                                                                                                                                                                                                                                          • 附录
                                                                                                                                                                                                                                                                                                                                                            • 附录1 标准模板结构
                                                                                                                                                                                                                                                                                                                                                              • FL1.1 标准模板库数据结构的分类
                                                                                                                                                                                                                                                                                                                                                                • FL1.2 迭代器类
                                                                                                                                                                                                                                                                                                                                                                  • FL1.3 容器类
                                                                                                                                                                                                                                                                                                                                                                    • FL1.4 容器适配器类
                                                                                                                                                                                                                                                                                                                                                                      • FL1.5 标准模板类里的通用函数
                                                                                                                                                                                                                                                                                                                                                                        • 思考题
                                                                                                                                                                                                                                                                                                                                                                        • 附录2 数据结构考研真题解析
                                                                                                                                                                                                                                                                                                                                                                          • FL2.1 2009年全国硕士研究生入学统一考试计算机科学与技术学科联考数据结构部分考题
                                                                                                                                                                                                                                                                                                                                                                            • FL2.2 2010年全国硕士研究生入学统一考试计算机科学与技术学科联考数据结构部分考题
                                                                                                                                                                                                                                                                                                                                                                          • 结语:数据结构之弦
                                                                                                                                                                                                                                                                                                                                                                            • 参考文献

                                                                                                                                                                                                                                                                                                                                                                            相关图书