本书针对大学程序设计竞赛和课程教学,基于数据结构的知识体系结构和循序渐进的原则组织内容,包括基本编程能力训练、线性数据结构的编程、树的编程、图的编程。在每一章中,先介绍了相关的数据结构知识后,然后给出相应的范例;在每章的结尾给出相关题库。
目录
- 前言
- 第一篇训练基本编程能力的实验
- 第1章简单计算的编程实验2
- 1.1改进程序书写风格2
- 1.2正确处理多个测试用例4
- 1.3在实数和整数之间转换10
- 1.4二分法、实数精度13
- 1.5相关题库20
- 第2章简单模拟的编程实验30
- 2.1直叙式模拟30
- 2.2筛选法模拟33
- 2.3构造法模拟35
- 2.4相关题库37
- 第3章递归与回溯法的编程实验44
- 3.1计算递归函数45
- 3.2求解递归数据47
- 3.3用递归算法求解问题49
- 3.4回溯法55
- 3.5相关题库63
- 本篇小结69
- 第二篇线性表的编程实验
- 第4章应用直接存取类线性表编程72
- 4.1数组应用的四个典型范例72
- 4.1.1日期计算72
- 4.1.2高精度运算78
- 4.1.3多项式的表示与处理86
- 4.1.4数值矩阵运算91
- 4.2字符串处理96
- 4.2.1使用字符串作为存储结构96
- 4.2.2字符串的模式匹配97
- 4.2.3使用Manacher算法求最长回文子串103
- 4.3在数组中快速查找指定元素107
- 4.4通过数组分块技术优化算法109
- 4.5相关题库113
- 第5章应用顺序存取类线性表编程149
- 5.1顺序表的应用149
- 5.2栈应用158
- 5.3队列应用166
- 5.3.1顺序队列166
- 5.3.2优先队列176
- 5.3.3双端队列180
- 5.4相关题库183
- 第6章应用广义索引类线性表编程192
- 6.1使用词典解题192
- 6.2应用散列技术处理字符串197
- 6.3使用散列表与散列技术解题202
- 6.4相关题库210
- 第7章线性表排序的编程实验217
- 7.1利用STL中自带的排序功能编程217
- 7.2应用排序算法编程222
- 7.3相关题库226
- 本篇小结247
- 第三篇树的编程实验
- 第8章采用树结构的非线性表编程250
- 8.1用树的遍历求解层次性问题250
- 8.2用树结构支持并查集258
- 8.3用树状数组统计子树权和266
- 8.4用四叉树求解二维空间问题272
- 8.5用Trie树查询字符串280
- 8.6用AC自动机进行多模式匹配284
- 8.7相关题库292
- 第9章应用二叉树的基本概念编程324
- 9.1普通有序树转化为二叉树324
- 9.2应用典型二叉树327
- 9.3计算二叉树路径333
- 9.4通过遍历确定二叉树结构339
- 9.5相关题库344
- 第10章应用经典二叉树编程348
- 10.1二叉搜索树348
- 10.2二叉堆355
- 10.3树堆363
- 10.3.1树堆的概念和操作363
- 10.3.2非旋转树堆370
- 10.4赫夫曼树379
- 10.4.1赫夫曼树379
- 10.4.2多叉赫夫曼树381
- 10.5AVL树384
- 10.6伸展树389
- 10.7相关题库397
- 本篇小结411
- 第四篇图的编程实验
- 第11章应用图的遍历算法编程414
- 11.1BFS算法414
- 11.2DFS算法425
- 11.3拓扑排序433
- 11.3.1删边法433
- 11.3.2采用DFS计算拓扑排序436
- 11.3.3反向拓扑排序440
- 11.4计算图的连通性443
- 11.5Tarjan算法450
- 11.6相关题库468
- 第12 章应用最小生成树算法编程489
- 12.1Kruskal算法489
- 12.2Prim算法491
- 12.3最大生成树496
- 12.4相关题库500
- 第13章应用最佳路算法编程507
- 13.1Warshall算法和Floyd-Warshall算法507
- 13.2Dijkstra算法514
- 13.3Bellman-Ford算法519
- 13.4SPFA算法523
- 13.5相关题库527
- 第14章二分图、网络流算法编程535
- 14.1二分图匹配535
- 14.1.1匈牙利算法535
- 14.1.2Hall婚姻定理541
- 14.1.3KM算法544
- 14.2计算网络最大流551
- 14.2.1网络最大流551
- 14.2.2最小费用最大流560
- 14.3相关题库570
- 第15 章应用状态空间搜索编程583
- 15.1构建状态空间树583
- 15.2优化状态空间搜索590
- 15.2.1剪枝591
- 15.2.2定界595
- 15.2.3A*算法?603
- 15.2.4IDA*算法612
- 15.3在博弈问题中使用游戏树623
- 15.4相关题库638
- 本篇小结658