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