数据结构——从概念到Java实现

1. 合理规划教学内容。紧扣《高等学校计算机专业核心课程教学实施方案》和《计算机学科硕士研究生入学考试大纲》，涵盖教学方案及考研大纲要求的全部知识点。 2. 遵循认知规律，理清教学主线。根据学生的认知规律和课程的知识结构，按照从已知到未知的思维进程逐步推进教学内容，梳理和规划了各知识单元及其拓扑结构。 3. 提炼基础知识，适当扩展提高。抓牢核心概念，贯彻数据结构课程的基本教学要求，同时对某些知识点进行了适当的扩充和提高。 4. 兼顾概念层和实现层。将数据结构的实现过程分为抽象层、设计层和实现层，既强调数据结构的基本概念和原理方法，又注重数据结构的程序实现和实际运用。 5. 展现求解过程，培养计算思维。按照“问题？想法？算法？程序”的模式进行问题求解，采用“阐述基本思想→伪代码描述算法→Java语言实现算法”的模式进行算法设计。 6. 明确重点，化解难点。给出每一章的重点难点、各知识点的教学要求，以及有效的处理方法。针对数据结构内容抽象的特点，设计大量图解降低了理解问题的复杂性。

数据结构是计算机及相关专业的核心课程，也是计算机及相关专业硕士研究生入学考试的必考科目，而且是理工专业的热门公选课程。本书介绍了数据结构、算法以及抽象数据类型的概念，讲述了线性表、栈和队列、字符串和多维数组、树和二叉树、图等常用数据结构，讨论了查找和排序技术。本书通过合理规划教学内容，梳理了知识单元及其拓扑结构，并兼顾概念层和实现层，既强调数据结构的基本概念和原理及方法，又注重数据结构的程序实现和实际运用，在提炼基础知识的同时，进行了适当的扩展和提高。 本书内容丰富，层次清晰，深入浅出且结合了实例，可作为计算机及相关专业数据结构课程的教材，也可供从事计算机软件开发和应用的工程技术人员参考和阅读。

目录第1章绪论1 1.1问题求解与程序设计2 1.1.1程序设计的一般过程2 1.1.2数据结构在程序设计中的作用5 1.1.3算法在程序设计中的作用6 1.1.4本书讨论的主要内容7 1.2数据结构的基本概念8 1.2.1数据结构8 1.2.2抽象数据类型11 1.3算法的基本概念13 1.3.1算法及算法的特性13 1.3.2算法的描述方法14 1.4算法分析16 1.4.1算法的时间复杂度16 1.4.2算法的空间复杂度18 1.4.3算法分析举例18 1.5扩展与提高21 1.5.1从数据到大数据21 1.5.2算法分析的其他渐进符号22 思想火花——概率算法23 习题24 第2章线性表27 2.1引言28 2.2线性表的逻辑结构29 2.2.1线性表的定义29数据结构——从概念到Java实现目录2.2.2线性表的抽象数据类型29 2.2.3线性表的Java接口定义31 2.3线性表的顺序存储结构及实现31 2.3.1顺序表的存储结构31 2.3.2顺序表的实现32 2.3.3顺序表的使用37 2.4线性表的链接存储结构及实现38 2.4.1单链表的存储结构39 2.4.2单链表的实现41 2.4.3单链表的使用47 2.4.4双链表48 2.4.5循环链表50 2.5顺序表和链表的比较51 2.6扩展与提高52 2.6.1线性表的静态链表存储52 2.6.2顺序表的动态分配方式54 2.7应用实例55 2.7.1约瑟夫环问题55 2.7.2一元多项式求和57 思想火花——好算法是反复努力和重新修正的结果61 习题62 实验题65 第3章栈和队列67 3.1引言68 3.2栈69 3.2.1栈的逻辑结构69 3.2.2栈的顺序存储结构及实现70 3.2.3栈的链接存储结构及实现73 3.2.4顺序栈和链栈的比较76 3.3队列76 3.3.1队列的逻辑结构76 3.3.2队列的顺序存储结构及实现77 3.3.3队列的链接存储结构及实现82 3.3.4循环队列与链队列的比较85 3.4扩展与提高85 3.4.1两栈共享空间85 3.4.2双端队列87 3.5应用举例88 3.5.1括号匹配问题88 3.5.2表达式求值89 思想火花——好程序要能识别和处理各种输入92 习题93 实验题95 第4章字符串和多维数组97 4.1引言98 4.2字符串99 4.2.1字符串的逻辑结构99 4.2.2字符串的存储结构101 4.2.3模式匹配101 4.3多维数组105 4.3.1数组的逻辑结构105 4.3.2数组的存储结构与寻址106 4.4矩阵的压缩存储107 4.4.1特殊矩阵的压缩存储107 4.4.2稀疏矩阵的压缩存储110 4.5扩展与提高112 4.5.1稀疏矩阵的转置运算112 4.5.2广义表114 4.6应用实例118 4.6.1发纸牌118 4.6.2八皇后问题119 思想火花——用常识性的思维去思考问题121 习题121 实验题123 第5章树和二叉树125 5.1引言126 5.2树的逻辑结构127 5.2.1树的定义和基本术语127 5.2.2树的抽象数据类型128 5.2.3树的遍历操作定义129 5.3树的存储结构130 5.3.1双亲表示法130 5.3.2孩子表示法131 5.3.3孩子兄弟表示法131 5.4二叉树的逻辑结构133 5.4.1二叉树的定义133 5.4.2二叉树的基本性质134 5.4.3二叉树的抽象数据类型定义136 5.4.4二叉树的遍历操作定义137 5.4.5二叉树的Java接口定义139 5.5二叉树的存储结构及实现139 5.5.1顺序存储结构139 5.5.2二叉链表140 5.5.3三叉链表145 5.6森林146 5.6.1森林的逻辑结构146 5.6.2树、森林与二叉树的转换147 5.7最优二叉树149 5.7.1哈夫曼算法149 5.7.2哈夫曼编码152 5.8扩展与提高154 5.8.1二叉树遍历的非递归算法154 5.8.2线索二叉树157 5.9应用实例161 5.9.1堆与优先队列161 5.9.2并查集165 思想火花——调试程序与魔术表演167 习题168 实验题169 第6章图171 6.1引言172 6.2图的逻辑结构173 6.2.1图的定义和基本术语173 6.2.2图的抽象数据类型定义176 6.2.3图的遍历操作176 6.2.4图的Java接口定义178 6.3图的存储结构及实现179 6.3.1邻接矩阵179 6.3.2邻接表183 6.3.3邻接矩阵和邻接表的比较188 6.4最小生成树188 6.4.1Prim算法189 6.4.2Kruskal算法192 6.5最短路径196 6.5.1Dijkstra算法196 6.5.2Floyd算法199 6.6有向无环图及其应用201 6.6.1AOV网与拓扑排序201 6.6.2AOE网与关键路径204 6.7扩展与提高206 6.7.1图的其他存储方法206 6.7.2图的连通性208 6.8应用实例210 6.8.1七巧板涂色问题210 6.8.2医院选址问题211 思想火花——直觉可能是错误的213 习题214 实验题217 第7章查找技术219 7.1引言220 7.1.1查找的基本概念220 7.1.2查找算法的性能221 7.2线性表的查找技术221 7.2.1线性表查找结构的定义221 7.2.2顺序查找222 7.2.3折半查找222 7.3树表的查找技术225 7.3.1二叉排序树225 7.3.2平衡二叉树231 7.3.3B树235 7.4散列表的查找技术239 7.4.1散列查找的基本思想239 7.4.2散列函数的设计240 7.4.3处理冲突的方法242 7.4.4散列查找的性能分析245 7.4.5开散列表与闭散列表的比较246 7.5各种查找方法的比较247 7.6扩展与提高247 7.6.1顺序查找的改进——分块查找247 7.6.2折半查找的改进——插值查找248 7.6.3B树的改进——B+树249 思想火花——把注意力集中于主要因素，不要纠缠于噪声250 习题251 实验题253 第8章排序技术255 8.1引言256 8.1.1排序的基本概念256 8.1.2排序算法的性能257 8.1.3排序类的定义257 8.2插入排序258 8.2.1直接插入排序258 8.2.2希尔排序260 8.3交换排序261 8.3.1起泡排序261 8.3.2快速排序263 8.4选择排序266 8.4.1简单选择排序266 8.4.2堆排序268 8.5归并排序273 8.5.1二路归并排序的递归实现273 8.5.2二路归并排序的非递归实现275 8.6各种排序技术的使用277 8.7各种排序方法的比较277 8.8扩展与提高279 8.8.1排序问题的时间下界279 8.8.2基数排序280 思想火花——学会“盒子以外的思考”283 习题284 实验题286 附录A预备知识289 A.1数学术语289 A.2级数求和289 A.3集合290 A.4关系291 附录BJava语言基本语法293 B.1程序文件结构293 B.2数据类型294 B.3Java编程规范295 B.4控制语句295 B.5函数296 B.6类与对象297 B.7接口298 B.8异常处理299 附录C中英文词汇对照表301 参考文献305

前言数据结构是计算机及相关专业的核心课程，也是计算机及相关专业硕士研究生入学考试的必考科目，而且是理工专业的热门公选课程。作为程序设计的重要补充和延伸，数据结构所讨论的知识内容、蕴含的技术方法、体现的思维方式，无论是进一步学习计算机专业的其他课程，还是从事计算机领域的各项工作，都有着不可替代的作用。 数据结构课程知识丰富，内容抽象，隐藏在各知识单元的概念和方法较多，贯穿于各知识单元的链表和递归更是加重了学习难度。本书的编写者长期从事数据结构的研究和教学，深切理解学生在学习数据结构过程中遇到的问题和困惑，深入探究掌握数据结构的有效途径和方法，深刻思考数据结构对培养程序设计和计算思维的地位和作用，深度把握课程的教学目标和重点难点，在教学内容和教学设计等方面进行了如下处理。 1. 合理规划教学内容。紧扣《高等学校计算机专业核心课程教学实施方案》和《计算机学科硕士研究生入学考试大纲》，涵盖教学方案及考研大纲要求的全部知识点。 2. 遵循认知规律，理清教学主线。根据学生的认知规律和课程的知识结构，按照从已知到未知的思维进程逐步推进教学内容，梳理和规划了各知识单元及其拓扑结构，设计了清晰的教学主线。知识单元及其拓扑结构如图1所示。 3. 提炼基础知识，适当扩展提高。考虑不同学校教学要求的差异以及不同学生学习需求的差别，一方面本着“够用、实用”的原则，抓牢核心概念，提炼基础性知识，贯彻数据结构课程的基本教学要求；另一方面对某些知识点进行了适当的扩充和提高（图1中带星号部分），这部分内容可用于选讲，也可用于学生自学或课外阅读（教学建议： 目录中带一个星号可用于选讲，带两个星号可用于课外阅读，其他是必讲的基础知识）。数据结构——从概念到Java实现前言 4. 兼顾概念层和实现层。从抽象数据类型的角度将数据结构的实现过程分为抽象层、设计层和实现层，其中抽象层定义数据结构和基本操作集合，设计层是数据结构的存储表示和算法设计，实现层用Java语言实现数据结构，既强调数据结构的基本概念、原理及方法，又注重数据结构的程序实现和实际运用。 5. 展现求解过程，培养计算思维。通过讲思路讲过程讲方法，按照“问题→想法→算法→程序”的模式进行问题求解，采用“阐述基本思想→伪代码描述算法→Java语言实现算法”的模式进行算法设计与实现，这个过程正是计算思维的应用过程。每章通过两个应用实例展示了问题求解过程以及算法设计过程。 6. 明确重点，化解难点。每一章开篇即给出了本章的重点难点，以及各知识点的教学要求，在具体阐述时还有针对性的处理方法。针对数据结构内容抽象的特点，全书设计了大量插图，将抽象内容进行了具体化处理，降低了理解问题的复杂性。 总之，本书在概念的描述、实例的选择、知识的前后衔接、内容的组织结构，以及教学内容的理解、教学目标的实现、教学意图的融入、教学方法的运用等方面进行了系统思考和统筹设计，力图通过本书为读者构建多层次的知识体系。在问题求解层面，以数据表示和数据处理为主线，给出“问题→想法→算法→程序”的思维模式；在算法设计层面，通过伪代码描述算法，强调计算思维的培养；在算法分析层面，理解什么是“好”算法，给出算法分析的基本方法；在存储结构层面，通过存储示意图理解数据表示，再给出存储结构定义；在程序实现层面，给出所有数据结构的Java程序实现以及使用范例；在数据结构和算法的运用层面，通过应用实例理解如何为求解问题设计适当的数据结构，如何基于数据结构设计算法，从而将数据结构、算法和程序设计有机地融合在一起。书中所有代码均在Java 8环境下调试通过。 参加本书编写的还有王涛、肖巍等。 由于作者的知识和写作水平有限，书稿虽再三斟酌几经修改，仍难免有缺点和错误，欢迎专家和读者批评指正。作者的电子邮箱是wanghm@ccut.edu.cn。 作者 2018年10月