本书是数据结构与算法设计的教科书，将数据结构与算法设计有机地结合起来，向读者系统介绍了数据结构的基本概念及主要的算法设计方法。
全书共分七章，第一章介绍了数据结构的基本概念及主要的数学方法，第二章至第七章分别介绍了线性表、栈和队列及数组，树和图等重要的数据结构及基本操作的实现过程，以及查找和排序等数据结构的相关知识。本书在内容讲授过程中辅以大量的实例，旨在帮助读者更好地理解概念并了解如何使用这些概念去解决实际问题。书中主要算法都用C++语言写出，并给出了必要的注解。
本书概念清楚，选材精练，叙述深入浅出，用了大量的例子和图表来说明基本概念和方法，直观易懂。每章后面都附有习题，读者可以通过练习来检验所学知识。本书可以作为大专院校计算机专业学生的教材，也可以作为广大计算机科学与工程领域从业人员的一本参考书。
数据结构
C++语言描述
辛运帏 陈有祺 编著
本书的编写融入了国内外经典教材的先进理念，并结合了编者多年讲授“数据结构和算法分析”课程的经验，力求在内容方面深入浅出、通俗易懂，结构上先进严谨。
本书特点：
将数据结构与算法设计有机地结合起来，向读者系统地介绍数据结构的基本概念及主要的算法设计方法。
注重培养学生的程序设计能力，引导学生掌握必要的算法分析方法，学会分析问题并抽取出其中的数学模型，从而提高解决实际问题的能力。
涵盖研究生统一入学考试关于“数据结构”课程的知识点，读者可以通过本书掌握应会、必会的数据结构知识。
采用准C++语言作为全书的基本描述语言，并对各段程序代码都尽可能地给出说明，即使没有学习过C++的读者也能很快理解书中的内容。
每章的最后给出了大量习题，附录还给出了综合考试题和期末模拟考试题，学生通过完成这些题目，可以检查自己的学习效果。
数据结构历来是计算机科学与技术专业的核心课程之一。自1968年将数据结构列为一门独立的课程，至今已经过去了将近半个世纪，其体系也越来越完整。目前它在计算机学科的教学体系中愈加重要，成为计算机及相关专业学生必须学习的专业课程之一。
本书的目的是要为师生提供一本涉及该课程教学主要内容的合适教材。本书主要包含以下内容：第1章主要介绍数据结构的基本概念和有关的预备知识，这些都是程序设计过程中必不可少的内容。在此基础上，介绍算法设计技术及时间复杂度的概念。第2章介绍线性表的定义及存储方式，实现线性表在不同存储方式下的各种操作，分析这些操作的复杂度。最后给出线性表的应用实例。第3章介绍两个特殊的线性表——栈和队列，根据它们各自的特点，给出最具有成效的实现方式。同时，本章还讨论了数组的相关内容。第4章介绍树的相关内容，定义树中用到的术语，特别介绍了应用非常广泛的二叉树，详细讨论了相关的定义、基本运算、实现方法和一些重要的应用实例。第5章介绍图的概念，讨论图的主要存储方式，定义图的基本操作，并在两种不同存储方式下实现图的基本操作。在此基础上，还介绍了图的一些经典问题，给出相应的算法。第6章介绍了三大类查找方法，分别是顺序表上的查找方法、树形结构上的查找方法及哈希方法，并分析了不同查找方法的适用条件及相应的查找效率。第7章介绍了排序的概念，详细讨论了包括插入排序、交换排序、选择排序等在内的各类排序方法，分析各排序方法的效率，说明它们各自的适用条件，并对它们进行简单的比较。
本书各章的介绍中，既包含了数据结构的基本概念，也介绍了算法的设计与实现。实际上，数据结构与算法设计是程序设计的核心，二者是密不可分的。掌握了初步的程序设计方法之后，面对实际的应用问题，最重要的就是学习如何选择和设计有效的数据结构和算法，解决问题才是编写程序的目的。本书采用准C++语言作为全书的基本描述语言，书中对各段程序代码都尽可能地给出了说明，相信即使没有学习过C++的读者，也能很快理解书中的内容。
本书还力求在培养学生具备良好的程序设计技巧和必要的算法分析方法等方面做出努力，旨在提高他们的程序设计能力和解决问题的能力。本书引入了一些实际应用问题，在使用数据结构知识解决这些问题的过程中，向学生介绍分析问题并抽取出其中的数学模型的方法。对同一个问题，书中还会给出不同的算法并加以分析，比较各算法的优劣。
每章的最后均给出了习题，包括选择题、简答题及实习题等，基本涵盖了一章所学的内容，学生通过完成这些题目，可以检查自己的学习效果。
本书在编写过程中参阅了国内外经典著作和最新教材，并结合了编者多年讲授数据结构和算法分析课程的经验，力求在内容方面深入浅出、通俗易懂，结构上先进严谨，为广大师生提供一本适用的教材。
本书由辛运帏、陈有祺编写。在本书的编写过程中，一直得到南开大学卢桂章教授、刘璟教授、周玉龙教授的鼓励和支持。机械工业出版社华章分社的朱劼编辑从本书的策划到出版一直默默地做着大量的工作，提出了许多宝贵的意见，付出了巨大的心血。在此对关心、帮助本书编写的所有老师、朋友、同事表示诚挚的感谢。
虽然编者希望奉献一本优秀的数据结构与算法教材，但限于水平和能力，书中一定会有错误和不妥之处，敬请阅读本书的专家、老师和同学们提出宝贵意见。
编者于南开园
计算机\数据结构
本书的编写参阅了国内外经典著作和最新教材，并结合编者多年讲授数据结构和算法分析课程的经验，力求在内容方面深入浅出、通俗易懂，结构上先进严谨，为广大师生提供一本适用的教材。
本书特点：
● 将数据结构与算法设计有机地结合起来，向读者系统介绍数据结构的基本概念及主要的算法设计方法。
● 注重培养学生的程序设计能力，引导学生掌握必要的算法分析方法，学会分析问题并抽取出其中的数学模型，从而提高解决实际问题的能力。
● 采用准C++语言作为全书的基本描述语言，并对各段程序代码都尽可能地给出了说明，即使没有学习过C++的读者也能很快理解书中的内容。
● 每章的最后均给出了大量习题，书末附录还给出了综合考试题和期末模拟考试题，学生通过完成这些题目，可以检查自己的学习效果。
前言
教学建议
第1章 绪论1
1.1 数据结构的基本概念和术语1
1.2 抽象数据类型及面向对象的概念3
1.2.1 抽象数据类型3
1.2.2 面向对象的概念4
1.3 有关的预备知识4
1.3.1 集合4
1.3.2 递归6
1.4 算法和算法分析9
1.4.1 算法的基本概念9
1.4.2 算法的评估和复杂度度量10
1.4.3 算法设计的一个实例13
本章小结14
习题14
第2章 线性表16
2.1 线性表的定义和基本运算16
2.1.1 线性表的定义16
2.1.2 线性表的操作18
2.2 线性表的实现19
2.2.1 顺序存储结构19
2.2.2 链式存储结构23
2.2.3 两种基本存储实现方式的比较30
2.2.4 循环链表31
2.2.5 双向链表32
2.3 线性表的应用35
本章小结39
习题39
第3章 栈、队列和数组43
3.1 栈43
3.1.1 栈的定义43
3.1.2 栈的实现45
3.1.3 栈的应用48
3.2 队列51
3.2.1 队列的定义及基本运算51
3.2.2 队列的实现52
3.2.3 队列的应用57
3.3 数组59
3.3.1 数组的抽象数据类型59
3.3.2 数组的存储方式60
3.3.3 特殊数组61
3.3.4 数组的应用66
本章小结70
习题70
第4章 树与二叉树73
4.1 树73
4.1.1 树的基本概念73
4.1.2 树的抽象数据类型75
4.2 二叉树76
4.2.1 二叉树的定义及其主要特性76
4.2.2 二叉树的实现79
4.2.3 二叉树的遍历82
4.3 树与森林85
4.3.1 树的存储结构85
4.3.2 森林与二叉树的转换88
4.3.3 树和森林的遍历89
4.4 哈夫曼树和哈夫曼编码90
本章小结102
习题102
第5章 图结构106
5.1 图106
5.1.1 图的基本概念106
5.1.2 图的抽象数据类型110
5.2 图的存储结构111
5.2.1 邻接矩阵111
5.2.2 邻接表112
5.2.3 图的实现114
5.3 图的遍历及求图的连通分量118
5.3.1 深度优先搜索120
5.3.2 广度优先搜索123
5.3.3 无向图的连通分量126
5.4 有向无环图及拓扑排序127
5.4.1 有向无环图128
5.4.2 拓扑排序128
5.5 生成树和最小代价生成树132
5.5.1 生成树132
5.5.2 最小代价生成树134
5.6 单源最短路径142
5.6.1 问题的提出142
5.6.2 单源最短路径的算法143
本章小结146
习题146
第6章 查找149
6.1 查找的基本概念149
6.2 顺序表的查找150
6.2.1 顺序查找方法150
6.2.2 折半查找方法154
6.3 树形结构的查找158
6.3.1 二叉排序树158
6.3.2 平衡二叉树166
6.3.3 B树175
6.4 哈希表及其查找178
6.4.1 哈希的概念178
6.4.2 哈希函数的构造方法180
6.4.3 处理冲突的几种方法182
6.4.4 哈希表的查找及其效率分析184
本章小结185
习题185
第7章 内部排序188
7.1 排序的基本概念188
7.2 插入排序190
7.2.1 直接插入排序191
7.2.2 折半插入排序193
7.2.3 希尔排序194
7.3 交换排序196
7.4 基于分治法的排序199
7.4.1 归并排序199
7.4.2 快速排序204
7.5 选择排序208
7.5.1 简单选择排序208
7.5.2 堆排序210
7.6 分配排序和桶式排序214
7.7 有关内部排序算法的比较218
本章小结218
习题219
附录221
数据结构综合测试题221
数据结构期末模拟考试试卷一222
数据结构期末模拟考试试卷二225
数据结构期末模拟考试试卷三228
参考文献230
