目录


第1章绪论1
1.1课程属性与术语1
1.1.1数据结构是程序的
重要组成部分1
1.1.2数据结构是提升
编程能力的必备 …2
1.1.3数据结构与术语 …2
1.1.4数据结构决定
算法4
1.2数据结构的研究内容4
1.2.1逻辑结构5
1.2.2存储结构/物理
结构6
1.2.3逻辑结构与物理
结构的关系7
1.2.4非数值计算问题 …8
1.2.5数据结构与程序
设计的关系10
1.3抽象数据类型11
1.3.1抽象数据类型的
定义11
1.3.2抽象数据类型的
实现12
1.4算法与算法分析13
1.4.1算法的概念13
1.4.2算法描述13
1.4.3算法性能分析15
1.5数据结构的重要性与
应用20
1.5.1数据结构的重
要性20
1.5.2数据结构的应用
实例23
1.6小结24
习题125

第2章线性表29
2.1线性表的定义29
2.1.1线性表的逻辑
特性29
2.1.2线性表的抽象数据
类型30
2.2顺序表32
2.2.1顺序表的定义……32
2.2.2顺序表的存储
设计33
2.2.3顺序表的操作及
实现34
2.2.4顺序表应用举例 …40
2.3链表42
2.3.1单链表的定义及
特性42
2.3.2单链表的存储
设计432.3.3单链表的操作及实现44
2.3.4其他形式的链表52
2.3.5链表应用举例56
2.4顺序表与链表的比较60
2.4.1空间性能比较60
2.4.2时间性能比较60
2.4.3环境性能比较60
2.5线性表在大数据处理中的
应用61
2.5.1日志处理61
2.5.2数据预处理与数据清洗 …61
2.5.3数据缓存62
2.5.4数据索引62
2.6小结63
习题264

第3章栈和队列69
3.1栈69
3.1.1栈的定义和特点69
3.1.2顺序栈71
3.1.3链栈75
3.1.4顺序栈和链栈的比较78
3.1.5栈的应用78
3.2队列85
3.2.1队列的定义和特点85
3.2.2循环队列86
3.2.3链队90
3.2.4循环队列与链队列的
比较94
3.2.5队列的应用94
3.3栈与队列在操作系统中的
高级应用96
3.3.1进程调用栈和系统调
用栈96
3.3.2进程调度96
3.3.3内存管理97
3.3.4并发控制98
3.4小结99
习题399

第4章数组和矩阵103
4.1多维数组103
4.1.1数组的定义103
4.1.2数组的顺序存储105
4.2特殊矩阵107
4.2.1对称矩阵107
4.2.2三角矩阵108
4.2.3对角矩阵109
4.3稀疏矩阵110
4.3.1三元组表顺序存储110
4.3.2带行指针向量的链式
存储113
4.3.3十字链表116
4.4数组与矩阵在工程计算中的
应用116
4.4.1结构工程中的力学分析 …117
4.4.2信号处理117
4.4.3图像处理118
4.4.4控制系统设计119
4.4.5电子电路仿真与设计119
4.4.6天气预报与气候建模120
4.4.7金融工程与风险管理121
4.5小结121
习题4122

第5章树和二叉树125
5.1树126
5.1.1树的定义与表示126
5.1.2树的术语127
5.1.3树的抽象数据类型128
5.1.4树的存储设计129
5.1.5树和森林的遍历132
5.2二叉树的定义与特性133
5.2.1二叉树的定义133
5.2.2特殊二叉树134
5.2.3二叉树的性质135
5.2.4二叉树的抽象数据类型…137
5.3二叉树的存储结构138
5.4二叉树操作140
5.4.1二叉树遍历140
5.4.2根据遍历序列确定二
叉树148
5.4.3先、中、后序遍历的非递归
算法150
5.4.4二叉树的其他操作155
5.5线索二叉树158
5.5.1线索二叉树的定义158
5.5.2线索二叉树的建立159
5.5.3线索二叉树的遍历161
5.6树和森林与二叉树的相互
转换164
5.6.1树与二叉树相互转换……164
5.6.2森林与二叉树相互转换…166
5.7最优二叉树及其应用167
5.7.1基本概念167
5.7.2构造最优二叉树168
5.7.3哈夫曼编码173
5.8树结构在机器学习中的应用
举例176
5.8.1决策树及其应用176
5.8.2随机森林及其应用179
5.8.3自然语言处理180
5.9小结181
习题5182

第6章图187
6.1图的定义及相关术语187
6.1.1图的定义187
6.1.2图的术语188
6.1.3图的抽象数据类型191
6.2图的存储及操作193
6.2.1邻接矩阵表示法及操作
举例193
6.2.2邻接表表示法及操作
举例197
6.2.3十字链表表示法及操作
举例200
6.2.4邻接多重表表示法及
操作举例202
6.3图的遍历及应用204
6.3.1深度优先遍历204
6.3.2广度优先遍历207
6.3.3遍历应用举例210
6.4图的应用213
6.4.1最小生成树213
6.4.2最短路径219
6.4.3AOV网与拓扑排序225
6.4.4AOE网与关键路径230
6.5图结构在现代技术中的
应用举例234
6.5.1社交网络分析234
6.5.2交通规划236
6.5.3互联网链接分析236
6.6小结237
习题6238

第7章查找243
7.1查找的基本概念243
7.1.1术语243
7.1.2查找性能244
7.2线性表查找技术245
7.2.1顺序查找245
7.2.2折半查找246
7.2.3串的模式匹配248
7.3树表查找254
7.3.1二叉排序树254
7.3.2平衡二叉树261
7.4散列查找265
7.4.1散列函数的构造方法……266
7.4.2处理冲突的方法268
7.4.3散列表的查找270
7.5查找算法在搜索技术中的
应用272
7.5.1文档检索273
7.5.2数据库查询273
7.5.3字符串匹配274
7.5.4Web搜索引擎274
7.5.5地理信息系统275
7.6小结276
习题 7277

第8章排序279
8.1排序的基本概念279
8.1.1排序的定义279
8.1.2内排序与外排序280
8.1.3排序性能281
8.1.4内部排序方法的分类281
8.1.5待排序记录的存储方式…282
8.2插入排序282
8.2.1直接插入排序283
8.2.2折半插入排序285
8.2.3希尔排序286
8.3交换排序288
8.3.1冒泡排序288
8.3.2快速排序290
8.4选择排序294
8.4.1简单选择排序295
8.4.2树形选择排序296
8.4.3堆排序298
8.5归并排序303
8.6基数排序306
8.6.1分配排序306
8.6.2多关键码排序306
8.6.3基数排序详解3088.7各种排序方法的比较310
8.7.1性能比较310
8.7.2方法选用311
8.8排序技术应用举例312
8.8.1数据库管理系统313
8.8.2电子商务313
8.8.3生物信息学314
8.8.4文件系统314
8.8.5操作系统调度315
8.9小结316
习题8316

第9章分布与并发数据结构319
9.1分布式数据结构319
9.1.1分布式系统基本概念……319
9.1.2分布式数据结构及其
应用323
9.2并发数据结构328
9.2.1并发系统基本概念328
9.2.2并发数据结构及其应用…331
9.3分布与并发数据结构应用
案例333
9.3.1大规模分布式存储系统…333
9.3.2分布式文件系统335
9.3.3区块链技术中的分布式
数据结构338
9.4小结341
习题9341

附录术语表342

参考文献346