本书介绍了数据结构的基本概念、基本理论和基本方法，包括线性表、栈和队列、字符串、多维矩阵和广义表、树和二叉树、图、排序、查找、索引技术以及相关操作的算法，并分析了算法复杂度，用应用实例说明了常用数据结构在计算机中的存储和实现。书中算法采用C++语言描述，适合在MS VC++下使用，也可做适当修改后在DEV C++或MS VC++.NET中使用。全书内容由浅入深，概念清晰，强调程序设计书写风格，提高算法可读性和实用性。
样章试读
目录
- 目录
第1章 绪论 1
1.1 数据结构的研究对象 1
1.2 概念术语 2
1.3 算法和算法描述 9
1.3.1 算法的概念 9
1.3.2 算法的描述方法 9
1.4 算法的评价方法 11
1.4.1 评价算法的准则 11
1.4.2 算法的复杂度 11
1.4.3 算法描写的一些说明 17
本章 小结和学习要点 19
习题1 19
思考题1 21
上机题1 21
实验1 21
第2章 线性表 22
2.1 线性表及其基本操作 22
2.1.1 线性表的逻辑结构定义 22
2.1.2 线性表的抽象数据类型定义 23
2.2 线性表的顺序存储结构——顺序表 25
2.2.1 顺序表的基本表示 25
2.2.2 顺序表的基本操作 28
2.2.3 顺序表下的其他操作 33
2.3 线性表的链式存储结构 35
2.3.1 单链表 35
2.3.2 循环单链表 44
2.3.3 双链表及循环双链表 45
2.3.4 静态链表* 46
2.4 线性表的应用 48
2.4.1 删除整数表中值相同而多余的元素 48
2.4.2 合并两个有序单链表 48
2.4.3 逆置单链表 49
2.4.4 约瑟夫环问题求解 50
2.5 顺序表和单链表的比较 51
2.5.1 时间性能比较 51
2.5.2 空间性能比较 52
本章 小结和学习要点 53
习题2 53
思考题2 57
上机题2 57
实验2 57
第3章 栈和队列 58
3.1 栈 58
3.1.1 栈的逻辑定义 58
3.1.2 顺序栈 58
3.1.3 链栈 63
3.2 队列 66
3.2.1 队列的定义 66
3.2.2 队列的顺序存储结构 66
3.2.3 队列的链式存储结构 70
3.3 栈和队列的应用 73
3.3.1 栈的应用——算术表达式求值 73
3.3.2 队列的应用 75
3.3.3 栈和队列联合应用——停车场管理 78
本章 小结和学习要点 79
习题3 80
思考题3 82
上机题3 82
实验3 82
第4章 字符串 83
4.1 字符串的逻辑结构 83
4.2 字符串的顺序存储结构 84
4.3 字符串的链式存储结构 85
4.4 串的模式匹配算法 86
4.5 字符串的应用 91
4.5.1 大整数加法 91
4.5.2 名字#征数 92
本章 小结和学习要点 92
习题4 92
思考题4 94
上机题4 94
实验4 94
第5章 多维矩阵和广义表 95
5.1 多维矩阵的操作和简单存储 95
5.2 矩阵的压缩存储 98
5.2.1 特殊矩阵的压缩存储 99
5.2.2 稀疏矩阵的压缩存储 102
*5.3 广义表 106
5.3.1 广义表的概念 106
5.3.2 广义表的操作 107
本章 小结和学习要点 108
习题5 108
思考题5 110
上机题5 110
实验5 110
第6章 树和二叉树 111
6.1 树 111
6.2 二叉树 114
6.2.1 二叉树的定义和基本操作 114
6.2.2 二叉树的性质 115
6.2.3 二叉树的存储结构 118
6.3 遍历和建立二叉树 122
6.3.1 遍历二叉树 122
6.3.2 建立和释放二叉链表 126
6.3.3 二叉树的三种遍历的非递归算法 128
6.3.4 二叉树的其他应用算法 130
6.4 树和森林 131
6.5 哈夫曼树及其应用 137
6.6 森林结构的置信度推理 142
本章 小结和学习要点 144
习题6 145
思考题6 149
上机题6 149
实验6 149
第7章 图 150
7.1 图的定义、基本术语和操作 150
7.2 图的存储结构 151
7.2.1 邻接矩阵 151
7.2.2 边数组 152
7.2.3 邻接表 152
7.2.4 图的十字链表 157
7.3 图的遍历 159
7.3.1 深度优先搜索遍历图 159
7.3.2 广度优先搜索遍历图 161
7.3.3 图的遍历 162
7.4 图的连通性和生成树 163
7.5 最小生成树 164
7.5.1 普里姆算法 164
7.5.2 克鲁斯卡尔算法 167
7.6 最短路径问题 169
7.6.1 求单源顶点最短路径的Dijkstra算法 169
7.6.2 求顶点间最短路径的Floyd算法 172
7.7 拓扑排序 174
7.8 求关键路径 175
7.9 图的着色问题 180
7.10 隐式图与启发式搜索 180
本章 小结和学习要点 183
习题7 184
思考题7 188
上机题7 189
实验7 189
第8章 排序 190
8.1 排序的基本概念 190
8.2 插入排序 191
8.2.1 直接插入排序 191
8.2.2 谢尔排序 194
8.3 选择排序 195
8.3.1 直接选择排序 195
8.3.2 堆排序 197
8.4 交换排序 200
8.4.1 胃泡排序 200
8.4.2 快速排序 202
8.5 归并排序 205
8.6 基数排序 207
8.7 各种内排序算法的比较 208
本章 小结和学习要点 211
习题8 212
思考题8 216
上机题8 217
实验8 217
第9章 查找 218
9.1 查找的基本概念和术语 218
9.2 以顺序表为基础的查找 219
9.2.1 顺序表的顺序查找 219
9.2.2 有序表的二分法查找 222
9.2.3 分块查找 226
9.3 树形结构的查找 228
9.3.1 二叉排序树 229
9.3.2 平衡二叉树 236
9.4 散列查找 242
9.4.1 散列查找中的几个主要概念 242
9.4.2 散列函数设计方法 243
9.4.3 冲突的处理方法 246
9.4.4 散列表上的查找算法 249
9.4.5 散列表查找的时间复杂度分析 250
本章 小结和学习要点 253
习题9 253
思考题9 256
上机题9 256
实验9 256
第10章 索引技术 257
10.1 索引的基本概念 257
10.2 线性索引 258
10.2.1 稠密索引 258
10.2.2 稀疏索引 259
10.3 树形索引 260
10.3.1 树 260
10.3.2 B+树 262
10.3.3 键树 263
本章 小结和学习要点 268
习题10 268
思考题10 270
上机题10 270
主要参考文献 271
附录上机实验报告格式 272
京公网安备 11010102004214号