数据结构
2007-4
中国铁道出版社
刘振鹏，张小莉，郑艳娟 编著
260
397000
数据结构是计算机科学与技术等电子信息类相关专业的一门重要的基础课程。许多高等院校将它作为理科各系主干基础课列入学校的教学计划之中。通过讲授本课，学生可以较全面地理解算法和数据结构的概念，掌握各种数据结构和算法的实现方式，比较不同的数据结构和算法的特点。这是一门理论与实际紧密结合的课程。通过本课程的学习，学生可以学会分析研究计算机加工的数据结构特性，以便在以后的工作实践中，能够针对具体问题选择和设计出适当的逻辑结构、存储结构及相应的算法，并在此基础上，能编写出结构清晰、正确易读、符合软件工程规范的程序，从而为进一步学习后续专业课程和软件的开发打下坚实的基础。本书在内容组织和编排上，力求理论与实际应用紧密结合，而且更加突出运用。本书的主要特点有以下3点。（1）内容组织上层次分明、结构清晰。在内容的选取上坚持学以致用、学用结合的原则，集先进性、科学性和实用性于一体，尽可能地将最基础、最适用的软件技术写入教材，省略一些纯理论的推导和烦琐的数学证明。（2）在内容的深浅程度上，把握理论深度、侧重实用、由浅入深的原则，通过大量翔实的例题、算法和每一章的最后给出的练习题，进一步提高学生对数据的抽象能力和程序设计的能力。（3）内容叙述深入浅出，文体规范，文字浅显易懂，相互衔接自然，表述严谨，逻辑性强，以利于学生自学和理解。本书作为2003年版《数据结构》的第二版，保持了前一版的基本框架，概念清楚、论述充实、面向应用，进一步完善了算法与数据结构的体系内容，对所有算法进行了详尽的注释和完善，以利于读者理解算法的基本思想。各章均安排有章节提要和课后习题。本书的第l章和10章由刘振鹏编写修订，第2章～第5章由张小莉编写修订，第6章～第9章由郑艳娟编写修订，最后由刘振鹏、张小莉统一定稿。本书在写作和修订过程中，得到了许多专家和众多院校数据结构任课教师的大力支持和帮助，他们提出了许多中肯的意见和很好的建议，对本书的编写修订起到了很大的指导作用。对此，作者表示衷心的感谢。也正是他们的认可和支持，使得本书入选普通高等教育“十一五”国家级规划教材。感谢作者的多位同事和学生，许百成、罗文劫参与了编写大纲的讨论并编写了初稿的部分内容，王苗编写书中习题部分并提供了全部答案，石强、史青宣制作了电子讲义，赵红、苗秀芬等在使用本书的过程中指出了书中的一些不足之外，使得本书更加完善。尽管我们做了很大的努力，但由于编者水平有限，书中难免有不妥之处，恳请读者予以指正。
本书介绍了：各种最常用的数据结构，包括线性表、栈、队列、矩阵的压缩存储、树与二叉树、图、查找、排序等。阐明各种数据结构内在的逻辑关系，讨论它们在计算机中的存储表示，以及在这些数据结构下的运算和实现的算法，并对算法的效率进行了简要的分析。本书既注重原理又重视算法的实现，均给出用Visual
C++语言描述的算法，并加以详细的注释，分析算法的基本思路，每章都附有大量的习题。
与本书配套的《数据结构习题解答与实验指导》详细给出了书中习题的解答思路和参考答案，并且结合数据结构课堂和实践教学，设计了7项实验内容。它和本书一起构成了一个完整的教学系列。
本书内容丰富、结构清晰、突出算法、注重应用，强调理论与实践的结合。既适合作为高等院校计算机科学与应用、通信工程、电子工程等电子信息类专业的教材，又适合于计算机爱好者自学，对于从事计算机应用和开发的技术人员也具有一定的参考价值。
第1章 绪论
1-1 数据结构的概念
1-1-1 为什么要学习数据结构
1-1-2 相关概念和术语
1-1-3 数据结构课程的内容
1-2 数据类型和抽象数据类型
1-2-1 数据类型
1-2-2 抽象数据类型
1-3 算法和算法分析
1-3-1 算法特性
1-3-2 算法描述
1-3-3 算法性能分析与度量
习题
第2章 线性表
2-1 线性表的逻辑结构
2-1-1 线性表的定义
2-1-2 线性表的基本操作
2-2 线性表的顺序存储及运算实现
2-2-1 顺序表
2-2-2 顺序表上基本运算的实现
2-2-3 顺序表应用举例
2-3 线性表的链式存储和运算实现
2-3-1 单链表
2-3-2 单链表上基本运算的实现
2-3-3 循环链表
2-3-4 双向链表
2-3-5 静态链表
2-3-6 单链表应用举例
2-4 顺序表和链表的比较
习题
第3章 栈和队列
3-1 栈
3-1-1 栈的定义及基本运算
3-1-2 栈的存储实现和运算实现
3-2 栈的应用举例
3-3 队列
3-3-1 队列的定义及基本运算
3-3-2 队列的存储实现及运算实现
3-4 队列应用举例
习题
第4章 串
4-1 串及其基本运算
4-1-1 串的基本概念
4-1-2 串的基本运算
4-2 串的定长顺序存储及基本运算
4-2-1 串的定长顺序存储
4-2-2 定长顺序串的基本运算
4-2-3 模式匹配
4-3 串的堆存储结构
4-3-1 串名的存储映像
4-3-2 堆存储结构
4-3-3 基于堆结构的串的基本运算实现
习题
第5章 数组和广义表
5-1 多维数组
5-1-1 数组的逻辑结构
5-1-2 数组的内存映像
5-2 特殊矩阵的压缩存储
5-2-1 对称矩阵
5-2-2 三角矩阵
5-2-3 带状矩阵
5-3 稀疏矩阵
5-3-1 稀疏矩阵的三元组表存储
5-3-2 稀疏矩阵的十字链表存储
5-4 广义表
5-4-1 广义表的定义和基本运算
5-4-2 广义表的存储
5-4-3 广义表基本操作的实现
习题
第6章 二叉树
6-1 二叉树的定义与性质
6-1-1 二叉树的基本概念
6-1-2 二叉树的主要性质
6-2 二叉树的基本操作与存储实现
6-2-1 二叉树的存储
6-2-2 叉树的基本操作及实现
6-3 二叉树的遍历
6-3-1 二叉树的遍历方法及递归实现
6-3-2 二叉树遍历的非递归实现
6-3-3 由遍历序列恢复二叉树
6-3-4 不用栈的二叉树遍历的非递归方法
6-4 线索二叉树
6-4-1 线索二叉树的定义及结构
6-4-2 线索二叉树的基本操作实现
6-5 二叉树的应用
6-5-1 二叉树遍历的应用
6-5-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-3-3 二叉树转换为树和森林
7-4 树和森林的遍历
7-4-1 树的遍历
7-4-2 森林的遍历
7-5 树的应用
7-5-1 判定树
7-5-2 集合的表示
7-5-3 等价问题
习题
第8章 图
8-1 图的基本概念
8-1-1 图的定义和术语
8-1-2 图的基本操作
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-4 生成树与最小生成树
8-4-1 生成树和生成森林
8-4-2 最小生成树的概念
8-4-3 构造最小生成树的Prim算法
8-4-4 构造最小生成树的Kruska1算法
8-5 最短路径
8-5-1 从一个源点到其他各点的最短路径
8-5-2 每-对顶点之间的最短路径
8-6 有向无环图及其应用
8-6-1 有向无环图的概念
8-6-2 AOV网与拓扑排序
8-6-3 AOE图与关键路径
习题
第9章 查找
9-1 基本概念
9-2 静态查找表
9-2-1 静态查找表结构
9-2-2 顺序查找
9-2-3 有序表的查找
9-2-4 分块查找
9-3 动态查找表
9-3-1 二叉排序树：
9-3-2 平衡二叉树
9-3-3 B树和B树
9-4 哈希表查找（杂凑法）
9-4-1 哈希表与哈希方法
9-4-2 常用的哈希函数
9-4-3 处理冲突的方法
9-4-4 哈希表的查找分析
习题
第10章 排序
10-1 排序的基本概念
10-2 插入排序
10-2-1 直接插入排序
10-2-2 折半插入排序
10-2-3 表插入排序
10-2-4 希尔排序
10-3 交换排序
10-3-1 冒泡排序
10-3-2 快速排序
10-4 选择排序
10-4-1 简单选择排序
10-4-2 树形选择排序
10-4-3 堆排序
10-5 归并排序
10-6 基数排序
10-6-1 多关键码排序
10-6-2 链式基数排序
10-7 外排序
10-7-1 外部排序的方法
10-7-2 多路平衡归并的实现
习题
参考文献
插图：数据结构的核心技术是分解与抽象。通过对问题的抽象，舍弃数据元素的具体内容，就得到逻辑结构；类似地，通过分解将处理要求划分成各种功能，再通过抽象舍弃实现细节，就得到运算的定义。上述两个方面的结合使人们将问题转换为数据结构，这是一个从具体（即具体问题）到抽象（即数据结构）的过程。然后，通过增加对实现细节的考虑进一步得到存储结构和实现运算，从而完成设计任务，这是一个从抽象（即数据结构）到具体（即具体实现）的过程。熟练地掌握这两个过程是数据结构课程在专业技能培养方面的基本目标。数据结构作为一门独立的课程在国外是从1968年才开始的，但在此之前其有关内容已放在编译原理及操作系统课程之中。20世纪60年代中期，美国的一些大学开始设立有关课程，但当时的课程名称并不叫数据结构。1968年美国唐·欧·克努特（Donald E.knuth）教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》（Art of Computer Vrogramming，现翻译为《计算机程序设计艺术》）第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。从20世纪60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们越来越重视数据结构。从20世纪70年代中期到80年代，各种版本的数据结构著作相继问世。目前，数据结构的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，例如，多维图形数据结构等；另一方面，从抽象数据类型和面向对象的观点来讨论数据结构已成为一种新的趋势，越来越受到人们的重视。
《数据结构》：所有算法均给出C＋＋语言的描述，并加以详细的注释，利于读者理解算法的基本思想。
