本书是《数据结构：C++版》的配套课程设计书，不仅按教材的相应章节设计，而且还给出各章的重点和难点、典型例题及实验解答。全书共分11章，给出了与数据结构内容相关的知识解析、算法分析以及课程设计，描述了相关数据结构的存储表示及其实际套用的操作算法，对用C++模板方法描述的各种算法进行了详细的注释和性能分析，并对各套用的解题思路、方法进行了较详细的分析

前言

第1章　数据结构概论1

1.1　本章重点1

1.2　本章难点1

1.3　求解鸡兔同笼问题实验解答1

1.3.1　实验要求1

1.3.2　参考答案1

1.4　百钱买百鸡问题课程设计3

1.4.1　设计要求3

1.4.2　解答3

1.5　评分标準5

第2章　类和类模板基础6

2.1　重点和难点6

2.1.1　模板函式专门化和模板重载6

2.1.2　类模板8

2.1.3　在类中使用动态分配记忆体9

2.2　多档案编程实验解答10

2.2.1　实验题目10

2.2.2　实验要求10

2.2.3　实验解答10

2.3　课程设计13

2.3.1　在主程式中使用动态记忆体14

2.3.2　将函式改为成员函式17

2.3.3　在成员函式中使用动态记忆体19

2.3.4　使用结构作为模板的数据类型20

2.4　评分标準22

第3章　线性表23

3.1　本章重点23

3.2　本章难点23

3.2.1　使用类模板的学生信息鍊表23

3.2.2　使用类的学生信息鍊表26

3.3　实现一元多项式的加法运算实验解答28

3.3.1　问题分析28

3.3.2　算法解析29

3.3.3　完整的源程式清单31

3.3.4　程式运行测试33

3.4　求解改进的约瑟夫环游戏课程设计34

3.4.1　设计要求34

3.4.2　设计思想35

3.4.3　档案及函式组成37

3.4.4　参考程式清单39

3.4.5 　运行示例41

3.5　评价标準42

第4章　栈和伫列43

4.1　本章重点43

4.2　本章难点46

4.3　栈和伫列的特点49

4.3.1　栈的特点49

4.3.2　循环伫列的特点49

4.4　八皇后问题实验解答49

4.4.1　设计思想49

4.4.2　算法设计50

4.4.3　算法扩充52

4.4.4　完整的算法实现52

4.5　模拟后缀表达式的计算过程课程设计54

4.5.1　设计思想54

4.5.2　设计类54

4.5.3　参考程式56

4.5.4　运行示例60

4.6　评价标準60

第5章　字元串61

5.1　重点和难点61

5.1.1　字元串的概念61

5.1.2　顺序串62

5.1.3　链串62

5.1.4　串运算的实现62

5.2　串运算实例64

5.3　串模式匹配算法实验解答66

5.3.1　朴素模式匹配算法66

5.3.2　给定位置的串匹配算法69

5.4　字元串课程设计71

5.4.1　设计思想71

5.4.2　设计String类72

5.4.3　String类程式清单75

5.5　评价标準82

第6章　多维数组和广义表83

6.1　重点和难点83

6.1.1　多维数组83

6.1.2　特殊矩阵84

6.1.3　广义表85

6.1.4　典型例题85

6.2　稀疏矩阵的加法运算实验解答91

6.2.1　实验题目91

6.2.2　设计思想92

6.2.3　完整的参考程式及运行示例94

6.3　广义表课程设计98

6.3.1　设计要求98

6.3.2　广义表的存储结构98

6.3.3　广义表的基本算法99

6.3.4　算法实现101

6.4　评分标準107

第7章　树和二叉树108

7.1　重点和难点108

7.1.1　树的概念和术语108

7.1.2　二叉树概述108

7.1.3　二叉树的运算109

7.1.4　线索二叉树111

7.1.5　树和森林113

7.1.6　哈夫曼树114

7.2　二叉树的遍历与查找算法实验解答116

7.2.1　实验题目和要求116

7.2.2　参考答案116

7.3　查找结点并显示该结点的层次和路径课程设计122

7.3.1　设计要求122

7.3.2　设计思想122

7.3.3　参考程式124

7.4　哈夫曼编码课程设计125

7.4.1　设计要求125

7.4.2　设计哈夫曼树的类125

7.5　评分标準130

第8章　图131

8.1　重点和难点131

8.1.1　图的基本术语131

8.1.2　图的存储表示方式132

8.1.3　图的基本运算133

8.1.4　拓扑排序法135

8.2　实现无向网路的最小生成树的普里姆算法实验解答135

8.2.1　实验要求135

8.2.2　参考答案136

8.3　交通谘询系统课程设计138

8.3.1　设计要求及分析138

8.3.2　设计功能的实现139

8.3.3　运行示例142

8.4　评分标準145

第9章　排序146

9.1　重点和难点146

9.1.1　排序的基本概念146

9.1.2　各种排序方法比较148

9.2　典型算法148

9.2.1 插入排序149

9.2.2　交换排序149

9.2.3　使用单鍊表的直接选择排序151

9.2.4　使用堆的直接选择排序154

9.2.5　分配排序155

9.3　堆排序实验解答159

9.4　学生成绩处理课程设计161

9.4.1　设计要求161

9.4.2　设计思想162

9.4.3　参考答案162

9.5　评分标準165

第10章　查找166

10.1　重点和难点166

10.1.1　顺序表查找166

10.1.2　二叉排序树170

10.1.3　散列表查找173

10.2　二叉排序树实验解答176

10.2.1　实验题目176

10.2.2　参考答案176

10.3　航班信息的查询与检索课程设计177

10.3.1　设计要求177

10.3.2　设计分析177

10.3.3　参考程式178

10.3.4　运行示例181

10.4　评分标準183

第11章　档案184

11.1　重点和难点184

11.1.1　档案的基本概念184

11.1.2　常用的档案结构185

11.2　档案实例187

11.3　演示档案和重载实例189

11.4　图书管理信息系统课程设计190

11.4.1　设计要求190

11.4.2　设计分析191

11.4.3　程式清单195

11.4.4　运行示例212

11.5　评分标準215

参考文献216