数据结构(C++版)学习辅导与实验指导(第2版)

第一篇 学习 辅 导

第1章 绪论3

1.1 本章导学3

1.2 重点难点释疑4

1.2.1 信息、数据与结构4

1.2.2 数据结构、数据类型和抽象数据类型5

1.2.3 逻辑结构与存储结构6

1.2.4 如何选择或设计数据结构6

1.2.5 算法设计的一般原则7

1.2.6 算法的时间复杂度分析8

1.3 习题解析9

1.3.1 课后习题讲解9

1.3.2 学习自测题及答案15

第2章 线性表17

2.1 本章导学17

2.2 重点难点释疑18

2.2.1 存储结构与存取结构18

2.2.2 头指针、尾标志、开始结点与头结点19

2.2.3 带头结点的单链表与不带头结点的

单链表的比较19

2.2.4 单链表的算法设计技巧21

2.2.5 有序单链表的算法设计技巧25

2.2.6 循环链表的算法设计技巧26

2.3 习题解析27

2.3.1 课后习题讲解27

2.3.2 学习自测题及答案36 数据结构（C++版）学习辅导与实验指导（第2版）目录 第3章 栈和队列41

3.1 本章导学41

3.2 重点难点释疑42

3.2.1 浅析栈的操作特性42

3.2.2 递归算法转换为非递归算法43

3.2.3 循环队列中队空和队满的判定方法44

3.3 习题解析47

3.3.1 课后习题讲解47

3.3.2 学习自测题及答案52

第4章 字符串和多维数组55

4.1 本章导学55

4.2 重点难点释疑56

4.2.1KMP算法中如何求next数组56

4.2.2 特殊矩阵压缩存储后存储位置的计算58

4.3 习题解析59

4.3.1 课后习题讲解59

4.3.2 学习自测题及答案64

第5章 树和二叉树67

5.1 本章导学67

5.2 重点难点释疑69

5.2.1 二叉树和树是两种不同的树结构69

5.2.2 二叉树的构造方法69

5.2.3 二叉树遍历的递归实现图解70

5.2.4 二叉树的算法设计技巧70

5.2.5 哈夫曼树的构造过程中应注意的问题73

5.3 习题解析74

5.3.1 课后习题讲解74

5.3.2 学习自测题及答案84

第6章 图89

6.1 本章导学89

6.2 重点难点释疑91

6.2.1 深度优先遍历算法的非递归实现91

6.2.2 图的遍历算法的应用92

6.2.3 有向图的强连通分量93

6.2.4 改进的拓扑排序算法94

6.3 习题解析94

6.3.1 课后习题讲解94

6.3.2 学习自测题及答案106

第7章 查找技术109

7.1 本章导学109

7.2 重点难点释疑111

7.2.1 折半查找判定树及其应用111

7.2.2 时空权衡112

7.2.3 平衡二叉树的调整方法113

7.2.4 散列查找的性能分析114

7.3 习题解析115

7.3.1 课后习题讲解115

7.3.2 学习自测题及答案124

第8章 排序技术127

8.1 本章导学127

8.2 重点难点释疑129

8.2.1 排序算法的稳定性129

8.2.2 如何将排序算法移植到单链表上130

8.2.3 二叉排序树与堆的区别131

8.2.4 递归算法的时间性能分析132

8.3 习题解析134

8.3.1 课后习题讲解134

8.3.2 学习自测题及答案144

第9章 索引技术149

9.1 本章导学149

9.2 习题解析150

9.2.1 课后习题讲解150

9.2.2 学习自测题及答案154

第二篇 实验 指 导

第10章 实验基础159

10.1 实验的一般过程159

10.1.1 本书的实验安排159

10.1.2 验证实验的一般过程160

10.1.3 设计实验和综合实验的一般过程161

10.2 VC++编程工具的使用162

10.2.1 控制台程序162

10.2.2 单文件结构162

10.2.3 多文件结构163

10.2.4 程序的调试166

第11章 线性表实验171

11.1 验证实验171

11.1.1 顺序表的实现171

11.1.2 单链表的实现174

11.2 设计实验178

11.2.1 约瑟夫环问题178

11.2.2 用单链表实现集合的操作180

11.3 综合实验182

11.3.1 大整数的代数运算182

11.3.2 一元多项式相加183

第12章 栈和队列实验185

12.1 验证实验185

12.1.1 顺序栈的实现185

12.1.2 链队列的实现187

12.2 设计实验191

12.2.1 汉诺塔问题191

12.2.2 火车车厢重排问题192

12.3 综合实验194

12.3.1 表达式求值194

12.3.2 迷宫问题195

第13章 字符串和多维数组实验197

13.1 验证实验197

13.1.1 串操作的实现197

13.1.2 对称矩阵的压缩存储199

13.2 设计实验200

13.2.1 统计文本中单词的个数200

13.2.2 幻方201

13.3 综合实验203

13.3.1 近似串匹配203

13.3.2 数字旋转方阵205

第14章 树和二叉树实验207

14.1 验证实验207

14.1.1 二叉树的实现207

14.1.2 树的实现210

14.2 设计实验214

14.2.1 求二叉树中叶子结点的个数214

14.2.2 二叉表示树215

14.3 综合实验216

14.3.1 信号放大器216

14.3.2 哈夫曼算法的应用218

第15章 图实验219

15.1 验证实验219

15.1.1 邻接矩阵的实现219

15.1.2 邻接表的实现222

15.2 设计实验225

15.2.1TSP问题225

15.2.2 哈密顿路径226

15.3 综合实验228

15.3.1 农夫过河228

15.3.2 医院选址问题228

第16章 查找技术实验231

16.1 验证实验231

16.1.1 顺序查找的实现231

16.1.2 折半查找的实现232

16.1.3 散列查找的实现234

16.2 设计实验235

16.2.1 二叉排序树的查找性能235

16.2.2 闭散列表和开散列表查找性能的比较236

16.3 综合实验236

16.3.1 个人电话号码查询系统236

16.3.2 斐波那契查找237

第17章 排序技术实验239

17.1 验证实验239

17.1.1 插入排序算法的实现239

17.1.2 交换排序算法的实现241

17.1.3 选择排序算法的实现244

17.2 设计实验246

17.2.1 直接插入排序基于单链表的实现246

17.2.2 双向起泡排序248

17.3 综合实验249

17.3.1 各种排序算法时间性能的比较249

17.3.2 机器调度问题249

附录A 实验报告的一般格式251

附录B 课程设计报告的一般格式253

参考文献255

作者：王红梅、胡明、王涛 ISBN：9787302255291

定价：26元

印次：2-1

装帧：平装

印刷日期：2011-8-26

该书是一部关于计算机科学与工程领域基础性核心课程--数据结构与算法的专著，本书《内容实用，体例新颖，结构清晰，既可以作为大、中专院校在校师生相关课程的参考书，也可以作为信息学竞赛中数据结构方面的辅导用书。此外，《C++数据结构原理与经典问题求解》也可供计算机科学与工程领域从业人员参考和查阅。

《C++数据结构原理与经典问题求解》全书以典型数据结构、程序设计方法及问题求解方法为研究对象，用C++面向对象程序设计语言作为描述语言，时刻突出对经典问题求解这一要旨，并将丰富的C++语言程序设计实践融入其中。

全书采用"数据结构原理描述→面向对象实现→解决经典问题→STL介绍"的基本架构，既强调理论的完整性，又突出实例引导的驱动性，用经典问题和大量背景描述提高读者的阅读兴趣，从而使原本枯燥的理论变得妙趣横生。基于上述框架，《C++数据结构原理与经典问题求解》简要回顾了基本C++程序设计方法后，又全面系统地介绍了链表、队列、栈、树、图等基本数据结构。此外，《C++数据结构原理与经典问题求解》还提供了近百个算法、数十个经典问题和十余个综合问题的完整实现代码近万余行。