顶部
收藏

数据结构与算法(第4版)

“十一五”国家规划教材

作者:
廖明宏 郭福顺 张岩 李秀坤
定价:
29.00 元
版面字数:
430千字
开本:
16开
装帧形式:
平装
版次:
4
最新版次
印刷时间:
2018年
ISBN:
978-7-04-022473-3
物料号:
22473-00
出版时间:
2007-11-19
读者对象:
高等教育
一级分类:
计算机/教育技术类
二级分类:
计算机类专业核心课程
三级分类:
数据结构

本书是在教育部高等学校计算机科学与技术教学指导委员会制定的专业规范思想指导下,以哈尔滨工业大学国家精品课程“数据结构与算法”为基础,融入数据结构与算法的最新研究成果编写而成。本书为普通高等教育“十一五”国家级规划教材。全书按抽象数据型的观点组织,算法用类C语言描述,共分8章。第1章给出抽象数据型的定义、算法的基本概念及其复杂性的表示方法,扼要地介绍逐步求精的程序设计方法;第2、3、4章是对线性表、树、图等主要数据结构定义相应的抽象数据型,给出各种物理表示法和有关算法;第5、6、7章是关于数据处理技术的内容,介绍几种主要的查找和排序算法,同时还介绍文件的组织形式;第8章介绍几种典型的算法设计方法及其分析方法。

全书注意理论与实践相结合,内容深入浅出。本书可以作为计算机科学与技术专业的本科教材,同时也适用于计算机工程方向、软件工程方向和信息技术方向的本科教学;也可作为硕士研究生“算法设计与分析”课程的教学参考书,计算机学科相关专业的教材或参考书,同时对计算机科技工作者也有参考价值。

  • 目录
    • 前辅文
      • 第1章 绪论
        • 1.1 数据结构的研究对象
          • 1.2 数据结构发展概况
            • 1.3 抽象数据型
              • 1.3.1 抽象数据型的定义
                • 1.3.2 数据类型、数据结构和抽象数据型
                  • 1.3.3 多层次抽象技术
                    • 1.3.4 抽象数据型的优点
                    • 1.4 算法及其复杂性
                      • 1.4.1 算法与程序
                        • 1.4.2 算法的复杂性及其表示
                          • 1.4.3 最坏、最好和平均情况分析
                            • 1.4.4 时间复杂性分析的基本方法
                            • 1.5 逐步求精的程序设计方法
                              • 1.5.1 如何求解问题
                                • 1.5.2 算法的逐步求精
                                • 1.6 关于描述语言
                                  • 1.6.1 结构体类型说明
                                    • 1.6.2 输入/输出
                                      • 1.6.3 动态存储分配
                                        • 1.6.4 引用类型参数
                                          • 1.6.5 其他
                                          • 习题
                                          • 第2章 线性表
                                            • 2.1 线性表的抽象数据型
                                              • 2.2 线性表的实现
                                                • 2.2.1 线性表的数组实现
                                                  • 2.2.2 线性表的指针实现
                                                    • 2.2.3 线性表的游标实现
                                                      • 2.2.4 双向链接表
                                                        • 2.2.5 环形链表
                                                          • 2.2.6 多项式的代数运算
                                                          • 2.3 栈
                                                            • 2.3.1 栈的数组实现
                                                              • 2.3.2 栈的指针实现
                                                                • 2.3.3 栈和递归过程
                                                                  • 2.3.4 栈的应用
                                                                  • 2.4 队列
                                                                    • 2.4.1 队列的指针实现
                                                                      • 2.4.2 队列的循环数组实现
                                                                        • 2.4.3 队列的应用
                                                                        • 2.5 串
                                                                          • 2.5.1 串的抽象数据型
                                                                            • 2.5.2 串的表示
                                                                              • 2.5.3 模式匹配算法
                                                                              • 2.6 数组
                                                                                • 2.6.1 数组的抽象数据型
                                                                                  • 2.6.2 数组的表示
                                                                                  • 2.7 广义表
                                                                                    • 习题
                                                                                    • 第3章 树
                                                                                      • 3.1 基本术语
                                                                                        • 3.2 二叉树
                                                                                          • 3.2.1 二叉树的定义及遍历
                                                                                            • 3.2.2 二叉树的性质
                                                                                              • 3.2.3 二叉树的抽象数据型
                                                                                                • 3.2.4 二叉树的表示
                                                                                                  • 3.2.5 二叉树的复制
                                                                                                  • 3.3 堆
                                                                                                    • 3.4 选择树
                                                                                                      • 3.5 树
                                                                                                        • 3.5.1 树的抽象数据型
                                                                                                          • 3.5.2 树的表示
                                                                                                          • 3.6 森林和二叉树间的转换
                                                                                                            • 3.7 树的应用
                                                                                                              • 3.7.1 集合的树结构表示
                                                                                                                • 3.7.2 判定树
                                                                                                                  • 3.7.3 哈夫曼树
                                                                                                                    • 3.7.4 表达式求值
                                                                                                                    • 习题
                                                                                                                    • 第4章 图
                                                                                                                      • 4.1 基本定义
                                                                                                                        • 4.2 图的表示
                                                                                                                          • 4.2.1 邻接矩阵
                                                                                                                            • 4.2.2 邻接表
                                                                                                                            • 4.3 图的搜索
                                                                                                                              • 4.3.1 深度优先搜索与深度优先编号
                                                                                                                                • 4.3.2 广度优先搜索与广度优先编号
                                                                                                                                • 4.4 图与树的联系
                                                                                                                                  • 4.4.1 深度优先生成森林和广度优先生成森林
                                                                                                                                    • 4.4.2 无向图与开放树的联系
                                                                                                                                      • 4.4.3 最小生成树
                                                                                                                                      • *4.5 无向图的双连通性
                                                                                                                                        • 4.5.1 无向图的双连通分量
                                                                                                                                          • 4.5.2 求关节点
                                                                                                                                          • 4.6 搜索产生的边
                                                                                                                                            • *4.7 强连通性
                                                                                                                                              • 4.8 拓扑排序
                                                                                                                                                • 4.8.1 无环路有向图
                                                                                                                                                  • 4.8.2 拓扑排序算法
                                                                                                                                                  • 4.9 关键路径
                                                                                                                                                    • 4.10 单源最短路径
                                                                                                                                                      • 4.11 每一对顶点之间的最短路径
                                                                                                                                                        • 4.11.1 Floyd算法
                                                                                                                                                          • 4.11.2 Warshall算法
                                                                                                                                                            • 4.11.3 求有向图的中心点
                                                                                                                                                            • *4.12 求有向图的基本环路
                                                                                                                                                              • 习题
                                                                                                                                                              • 第5章 查找
                                                                                                                                                                • 5.1 线性查找
                                                                                                                                                                  • 5.2 折半查找
                                                                                                                                                                    • 5.3 分块查找
                                                                                                                                                                      • 5.4 二叉查找树
                                                                                                                                                                        • 5.5 AVL树
                                                                                                                                                                          • 5.6 B-树与B+树
                                                                                                                                                                            • 5.6.1 B-树及其性质
                                                                                                                                                                              • 5.6.2 B-树的插入操作
                                                                                                                                                                                • 5.6.3 B-树的删除操作
                                                                                                                                                                                  • 5.6.4 B+树
                                                                                                                                                                                  • *5.7 Trie树
                                                                                                                                                                                    • 5.7.1 Trie树的定义
                                                                                                                                                                                      • 5.7.2 Trie树的查找操作
                                                                                                                                                                                        • 5.7.3 采样策略
                                                                                                                                                                                          • 5.7.4 Trie树的插入操作
                                                                                                                                                                                            • 5.7.5 Trie树的删除操作
                                                                                                                                                                                            • 5.8 散列法
                                                                                                                                                                                              • 5.8.1 内散列表
                                                                                                                                                                                                • 5.8.2 散列函数
                                                                                                                                                                                                  • 5.8.3 冲突的处理
                                                                                                                                                                                                    • 5.8.4 外散列表
                                                                                                                                                                                                    • 习题
                                                                                                                                                                                                    • 第6章 排序
                                                                                                                                                                                                      • 6.1 简单的排序算法
                                                                                                                                                                                                        • 6.1.1 气泡排序
                                                                                                                                                                                                          • 6.1.2 插入排序
                                                                                                                                                                                                            • 6.1.3 选择排序
                                                                                                                                                                                                            • 6.2 快速排序
                                                                                                                                                                                                              • 6.3 归并排序
                                                                                                                                                                                                                • 6.4 堆排序
                                                                                                                                                                                                                  • 6.5 基数排序
                                                                                                                                                                                                                    • *6.6 词典排序
                                                                                                                                                                                                                      • *6.7 求第K个最小元素
                                                                                                                                                                                                                        • 习题
                                                                                                                                                                                                                        • 第7章 文件与外部排序
                                                                                                                                                                                                                          • 7.1 文件及文件操作
                                                                                                                                                                                                                            • 7.1.1 文件的有关概念
                                                                                                                                                                                                                              • 7.1.2 文件操作
                                                                                                                                                                                                                              • 7.2 文件组织
                                                                                                                                                                                                                                • 7.2.1 顺序式文件
                                                                                                                                                                                                                                  • 7.2.2 索引文件
                                                                                                                                                                                                                                    • 7.2.3 散列文件
                                                                                                                                                                                                                                      • 7.2.4 链接式文件和多重链表文件
                                                                                                                                                                                                                                        • 7.2.5 倒排文件
                                                                                                                                                                                                                                        • 7.3 磁盘文件的归并排序
                                                                                                                                                                                                                                          • 7.3.1 K路归并
                                                                                                                                                                                                                                            • 7.3.2 并行操作的缓冲区处理
                                                                                                                                                                                                                                              • 7.3.3 初始归并段的生成
                                                                                                                                                                                                                                              • 7.4 磁带文件的归并排序
                                                                                                                                                                                                                                                • 7.4.1 平衡归并排序
                                                                                                                                                                                                                                                  • 7.4.2 多阶段归并排序
                                                                                                                                                                                                                                                  • 习题
                                                                                                                                                                                                                                                  • 第8章 算法设计方法
                                                                                                                                                                                                                                                    • 8.1 递归方程的求解
                                                                                                                                                                                                                                                      • 8.1.1 与递归方程解有关的两个问题
                                                                                                                                                                                                                                                        • 8.1.2 猜解法
                                                                                                                                                                                                                                                          • 8.1.3 迭代法
                                                                                                                                                                                                                                                            • 8.1.4 一类递归方程的展开式与通解
                                                                                                                                                                                                                                                            • 8.2 分治法
                                                                                                                                                                                                                                                              • 8.2.1 基本思想
                                                                                                                                                                                                                                                                • 8.2.2 整数乘法
                                                                                                                                                                                                                                                                  • 8.2.3 求两个矩阵的乘积
                                                                                                                                                                                                                                                                    • 8.2.4 平衡
                                                                                                                                                                                                                                                                    • 8.3 贪心法
                                                                                                                                                                                                                                                                      • 8.3.1 基本思想
                                                                                                                                                                                                                                                                        • 8.3.2 背包问题
                                                                                                                                                                                                                                                                        • 8.4 动态规划
                                                                                                                                                                                                                                                                          • 8.4.1 基本思想
                                                                                                                                                                                                                                                                            • 8.4.2 矩阵连乘问题
                                                                                                                                                                                                                                                                              • 8.4.3 联赛胜负概率问题
                                                                                                                                                                                                                                                                              • 8.5 回溯法
                                                                                                                                                                                                                                                                                • 8.5.1 基本思想
                                                                                                                                                                                                                                                                                  • 8.5.2 单词匹配问题
                                                                                                                                                                                                                                                                                    • 8.5.3 回溯算法与解法空间的组织
                                                                                                                                                                                                                                                                                      • 8.5.4 8皇后问题
                                                                                                                                                                                                                                                                                      • 8.6 分枝限界法
                                                                                                                                                                                                                                                                                        • 8.6.1 基本思想
                                                                                                                                                                                                                                                                                          • 8.6.2 0-1背包问题
                                                                                                                                                                                                                                                                                            • 8.6.3 旅行商问题
                                                                                                                                                                                                                                                                                            • 习题
                                                                                                                                                                                                                                                                                            • 参考文献

                                                                                                                                                                                                                                                                                            相关图书