本书系统地介绍了线性表、栈、队列、串、数组、广义表、树、二叉树、图等常用数据结构以及查找、排序、索引等算法设计技术，给出了较多的数据结构应用实例及其算法在计算机中的存储和实现，分析了复杂度。书中各种算法采用C++语言描述，既适合在MS VC下使用，也适合在MS VC++.NET中使用。全书注重程序设计风格，可读性和实用性强。
样章试读
目录
- 目录
前言
第1章 绪论 1
1.1 引言 1
1.2 数据结构中的基本概念和术语 4
1.3 算法和算法描述 12
1.3.1 算法的概念 12
1.3.2 算法的描述方法 13
1.4 算法的评价方法 16
1.4.1 评价算法的一般原则 16
1.4.2 算法的复杂度 17
1.5 C++中的typedef、模板与异常处理 24
本章小结和学习要点 33
习题1 34
思考题1 36
上机题1 36
第2章 线性表 37
2.1 线性表及其基本操作 37
2.1.1 线性表的逻辑结构定义 37
2.1.2 线性表的抽象数据类型定义 38
2.2 线性表的顺序存储结构——顺序表 40
2.2.1 顺序表的基本表示 40
2.2.2 顺序表模板类表示下的基本操作 44
2.2.3 顺序表表示线性表下的其他操作 49
2.2.4 间接寻址方式及其他方式实现的顺序表 56
2.3 线性表的链式存储结构 56
2.3.1 单链表 56
2.3.2 循环单链表 67
2.3.3 双链表及循环双链表 68
2.3.4 静态链表 71
2.3.5 间接寻址方式实现的单链表 73
2.4 线性表的应用 73
2.4.1 一元多项式的表示及相加 73
2.4.2 算法举例 77
2.5 顺序表和单链表的比较 82
2.5.1 时间性能比较 82
2.5.2 空间性能比较 82
本章内容小结和学习要点 83
习题2 84
思考题2 88
上机题2 88
第3章 栈和队列 89
3.1 栈 89
3.1.1 栈的逻辑结构 89
3.1.2 栈的顺序存储结构——顺序栈 91
3.1.3 栈的链式存储结构 96
3.2 队列 99
3.2.1 队列的逻辑结构 99
3.2.2 队列的链式存储结构 102
3.2.3 队列的顺序存储结构 106
3.3 栈和队列的综合应用 115
3.3.1 算术表达式求值 115
3.3.2 用顺序栈作辅助存储结构求迷宫的一条路径解 124
本章内容小结和学习要点 126
习题3 126
思考题3 128
上机题3 129
第4章 字符串 130
4.1 串及其运算 130
4.2 串的顺序存储结构 134
4.3 串的链式存储结构 137
4.4 串的模式匹配算法 138
4.5 串的应用 149
4.5.1 大整数加法 149
4.5.2 名字特征数 152
本章小结和学习要点 153
习题4 153
思考题4 154
上机题4 154
第5章 数组和广义表 155
5.1 数组的寻址和运算 155
5.2 矩阵的压缩存储 159
5.2.1 特殊矩阵 160
5.2.2 稀疏矩阵 163
5.3 广义表 170
5.3.1 广义表的概念 170
5.3.2 广义表的存储结构 172
5.3.3 广义表的操作 174
本章小结和学习要点 178
习题5 178
思考题5 180
上机题5 180
第6章 树和二叉树 182
6.1 树的基本定义 182
6.2 二叉树 186
6.2.1 二叉树的定义和基本运算 187
6.2.2 二叉树的性质 189
6.2.3 二叉树的存储结构 192
6.3 二叉树的建立和遍历 197
6.3.1 遍历二叉树 197
6.3.2 建立和释放一棵二叉树的二叉链表 202
6.3.3 二叉链表其他函数和主函数 204
6.3.4 二叉树的三种遍历的非递归算法 206
6.3.5 二叉树的其他算法例 210
6.4 线索二叉树 213
6.5 树和森林 219
6.6 哈夫曼树及其应用 228
本章小结和学习要点 237
习题6 237
思考题6 242
上机题6 242
第7章 图的数据结构 243
7.1 图的定义、基本术语和操作 243
7.2 图的存储结构 248
7.2.1 邻接矩阵 248
7.2.2 边数组 252
7.2.3 邻接表 252
7.2.4 图的十字链表表示 258
7.2.5 邻接多重表 260
7.3 图的遍历 262
7.3.1 深度优先搜索遍历图 262
7.3.2 广度优先搜索遍历图 266
7.3.3 图的遍历 268
7.4 图的连通性和生成树 270
7.4.1 图的连通性和连通分量 270
7.4.2 生成树和生成森林 272
7.4.3 最小生成树 274
7.5 最短路径问题 283
7.5.1 求某个源点到其余各顶点的最短路径 283
7.5.2 求带权图中每一对顶点之间的最短路径 288
7.6 拓扑排序 291
7.7 求关键路径 298
7.8 图的遍历算法的应用 305
7.8.1 求过给定点v长度大于或等于k的简单有向回路 305
7.8.2 地图四色问题 306
本章小结和学习要点 308
习题7 308
思考题7 313
上机题7 313
第8章 排序 315
8.1 排序的基本概念和术语 315
8.2 插入排序 318
8.2.1 直接插入排序 318
8.2.2 谢尔排序 322
8.3 选择排序 324
8.3.1 简单选择排序 325
8.3.2 改进的简单选择排序 326
8.3.3 堆排序 327
8.4 交换排序 333
8.4.1 冒泡排序 333
8.4.2 快速排序 335
8.5 归并排序 340
8.6 基数排序 342
8.7 各种内部排序算法的比较 346
本章小结和学习要点 349
习题8 350
思考题8 355
上机题8 355
第9章 查找 356
9.1 查找的基本概念和术语 356
9.2 以顺序表为基础的查找 358
9.2.1 顺序表的顺序查找 358
9.2.2 有序表的二分法查找 361
9.2.3 静态树表的查找 366
9.2.4 分块查找 370
9.3 树形结构的查找 373
9.3.1 二叉排序树 373
9.3.2 平衡二叉树 383
9.4 散列表的查找 391
9.4.1 散列技术中的主要概念 391
9.4.2 散列函数的构造方法 392
9.4.3 冲突的处理方法 396
9.4.4 散列表上的查找算法 400
9.4.5 散列表查找的时间复杂度分析 400
本章小结和学习要点 405
习题9 405
思考题9 408
上机题9 408
第10章 索引技术 409
10.1 索引的基本概念 409
10.2 线性索引 410
10.2.1 稠密索引 410
10.2.2 稀疏索引 411
10.2.3 多重表 413
10.2.4 倒排表 413
10.3 树形索引 415
10.3.1 B-树 415
10.3.2 B+树 424
10.3.3 键树 425
本章内容小结和学习要点 432
习题10 432
思考题10 434
上机题10 434
主要参考文献 435
附录上机实验报告格式 437
索引 439
京公网安备 11010102004214号