数据结构与算法
基本信息·出版社：高等教育出版社 ·页码：297 页 ·出版日期：2000年06月 ·ISBN：9787040224733 ·条形码：9787040224733 ·版本：第1版 ·装帧：平装 ...
| 商家名称 |
信用等级 |
购买信息 |
订购本书 |
|
|
 |
数据结构与算法 |
 |
|
|
数据结构与算法 |
|
基本信息·出版社：高等教育出版社
·页码：297 页
·出版日期：2000年06月
·ISBN：9787040224733
·条形码：9787040224733
·版本：第1版
·装帧：平装
·开本：16
·正文语种：中文
·读者对象：高校师生，科技工作者
·丛书名：普通高等教育“十一五”国家级规划教材
内容简介 《数据结构与算法》是在教育部高等学校计算机科学与技术教学指导委员会制定的专业规范思想指导下，以哈尔滨工业大学国家精品课程“数据结构与算法”为基础，融人数据结构与算法的最新研究成果编写而成。《数据结构与算法》为普通高等教育“十一五”国家级规划教材。全书按抽象数据型的观点组织，算法用类c语言描述，共分8章。第1章给出抽象数据型的定义、算法的基本概念及其复杂性的表示方法，扼要地介绍逐步求精的程序设计方法；第2、3、4章是对线性表、树、图等主要数据结构定义相应的抽象数据型，给出各种物理表示法和有关算法；第5、6、7章是关于数据处理技术的内容，介绍几种主要的查找和排序算法，同时还介绍文件的组织形式；第8章介绍几种典型的算法设计方法及其分析方法。全书注意理论与实践相结合，内容深入浅出。《数据结构与算法》可以作为计算机科学与技术专业的本科教材，同时也适用于计算机工程方向、软件工程方向和信息技术方向的本科教学；也可作为硕士研究生“算法设计与分析”课程的教学参考书，计算机学科相关专业的教材或参考书，同时对计算机科技工作者也有参考价值。
编辑推荐 《数据结构与算法》特色：
多年锤炼，精益求精。哈尔滨工业大学是国内较早开设数据结构课程的学校之一，该书是在当时编写的讲义基础上发展起来的，几经修改，不断完善，并充分吸纳了IEEE／ACM制订的CC2001-CC2005的最新研究成果。数据结构与算法的有机结合。在内容上，除了介绍各种数据结构的基本概念和实现方法之外，还对算法进行了定量和定性分析；同时，阐述了各种典型算法设计策略的基本思想、原理、技术和方法，强化了对算法性能的深入分析。采用抽象数据型的概念组织教材。在编排上，采用抽象数据型的概念组织教材内容，有利于采用面向对象的程序设计方法设计开发软件。也有利于学生对问题的全面理解和掌握。
目录 第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.1 0单源最短路径
4.1 l每一对顶点之间的最短路径
4.1 1.1 Floyd算法
4.1 1.2 Warshau算法
4.1 1.3 求有向图的中心点
4.1 2求有向图的基本环路
习题
第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 旅行商问题
习题
参考文献
……
序言 计算机和通信技术的迅猛发展，不仅形成了融合度最高、潜力最大、增长最快的信息产业，而且成为推动全球经济快速增长和全面变革的关键因素。进入21世纪，我国的信息产业虽然已取得了长足的发展，但与发达国家相比，还有不小的差距。国家信息化的发展和信息产业国际竞争能力的提高，迫切需要高素质、创新型的计算机专业人才。
高素质计算机专业人才的培养离不开高质量的计算机教育。我们的专业虽然机会多，处于非常有利的条件，但是我们同样面临着一件事，就是从规模发展向质量提高的转变。怎么提高质量？专业素质的教育和应用素质的训练非常重要。尤其是我国高等教育进入大众化发展阶段，社会对计算机专业人才呈现出了多样化的需求。而与此同时，计算机学科的发展已极大地突破了原有的学科体系框架，形成了在“计算机科学与技术”之下向多个专业方向发展的新格局。在这种背景下，教育部高等学校计算机科学与技术教学指导委员会编制了《高等学校计算机科学与技术专业发展战略研究报告暨专业规范（试行）》（以下简称“专业规范”）。专业规范按照“培养规格分类”的指导思想，提出了三种类型、四个方向，即科学型（计算机科学方向），工程型（计算机工程方向、软件工程方向），应用型（信息技术方向）的计算机专业发展建议，体现了社会对不同人才类型的需求，对于指导我国计算机教学改革与建设，规范计算机教学工作，促进计算机教学质量的提高都具有重要的意义。
高水平的教材是一流教育质量的重要保证。为了配合专业规范的试行，便于广大高校教师按照新的专业规范组织实施教学，高等教育出版社在大力支持专业规范研究与起草工作的同时，还邀请规范起草小组的有关专家成立“高等学校计算机科学与技术专业系列教材编审委员会”，组织规划了结合计算机专业规范、面向全国高等学校计算机专业本科生的“高等学校计算机科学与技术专业系列教材”。令人高兴的是，一批有创新、改革精神，且有丰富教学经验的高等学校教师投身到新体系计算机专业教材的编写中来，他们用自己创造性的思维、辛勤的汗水诠释专业规范的思想，把新的课程体系和教学内容生动地传达给师生，并进行着有意义的教学实践。
文摘 插图：
1．3．3多层次抽象技术
抽象数据型的应用范围十分广泛，比较简单的有队列、表、二叉树和树等（这些将在第2章和第3章讨论），比较复杂的有数据库文件、编译程序中的符号表和文字处理系统中的文本文件等。对于比较复杂的数据类型，可以采用多层次抽象技术。一般事先将比较简单、基本的数据类型抽象出来，给出定义；再用已定义的数据类型去定义更复杂的数据类型，完成对后者的抽象。即用已定义的类型来表述要定义的类型的定义域，并用前者的操作来表述后者的操作，这就是所谓逐层抽象的方法。例如，文本文件可以看做是行的集合，而行又可以看做是由字组成的。由于在定义高层数据类型时不必考虑底层数据类型及其操作的内部细节，因此在对复杂数据类型进行抽象时可以减少很多麻烦。例如，在定义文本文件时，就不必考虑如何在某一行中检索、增加或删去一个字，如何检测某一行的长度等。这些操作都放在定义行和字的时候考虑，在定义文件时可以直接调用它们。
多层次抽象通常可以采用自底向上的方式进行。先抽象出最基本的数据类型，然后利用它们定义上一层数据类型，如此逐层向上，直至达到最高层的数据类型为止。这样，可以防止底层倒过来引用高层数据类型，因此底层应该服从高层的要求。自底向上方式使底层的抽象有一定的盲目性，在抽象过程中，可能要从高层返回底层做修正，因此不得不穿插一些自顶向下的过程。
