数据结构原理与应用实践教程

第1篇原理篇

第1章线性表3

1.1顺序表3

1.1.1顺序表存储定义与特性3

1.1.2顺序表操作实现原理4

1.1.3顺序表的应用6

1.2链表7

1.2.1单链表存储定义与特性7

1.2.2单链表操作实现原理8

1.2.3链表的应用11第2章栈13

2.1顺序栈13

2.1.1顺序栈的存储定义和特性13

2.1.2顺序栈操作实现原理14

2.2链栈14

2.2.1链栈的存储定义和特性14

2.2.2链栈操作实现原理15

2.3栈的应用16第3章队列19

3.1循环队列19

3.1.1循环队列存储定义和特性19

3.1.2循环队列操作实现原理20

3.2链队21

3.2.1链队的存储定义和特性21

3.2.2链队的操作实现原理21

3.3队列的应用22第4章数组和矩阵23

4.1数组和矩阵的存储23

4.2稀疏矩阵转置23

4.3稀疏矩阵求和24第5章树和二叉树27

5.1树27

5.2二叉树27

5.2.1二叉树的存储定义27

5.2.2二叉树操作实现原理28

5.3线索二叉树31

5.3.1线索二叉树的存储定义31

5.3.2线索二叉树操作实现原理31

5.4*优二叉树33

5.4.1*优二叉树的存储定义和特性33

5.4.2*优二叉树的构建33

5.4.3哈夫曼编码的构建34第6章图35

6.1邻接矩阵存储35

6.1.1邻接矩阵存储定义与特性35

6.1.2邻接矩阵操作实现原理36

6.2图的邻接表存储37

6.2.1邻接表存储定义与特性37

6.2.2邻接表操作实现原理38

6.3图的遍历及其应用39

6.3.1深度优先遍历39

6.3.2广度优先遍历39

6.3.3连通性问题40

6.3.4求*远顶点40

6.4图的应用41

6.4.1求*小生成树41

6.4.2单源点*短距离42

6.4.3任意两点的*短距离42

6.4.4AOE网的拓扑排序43

6.4.5AOE网的关键活动43第7章查找45

7.1线性表查找45

7.2串的模式匹配46

7.3二叉排序树47

7.3.1二叉排序树存储定义与特性47

7.3.2二叉排序树操作实现原理47

7.4散列查找48

7.4.1散列技术48

7.4.2散列表操作实现原理48第8章排序51

8.1插入类排序51

8.2交换类排序52

8.3选择排序53

8.4二路归并排序54

8.5基数排序54

第2篇验证篇

第1章绪59

1.1算法到程序转换60

1.2验证性实践步骤63

1.3实验环境简介64

1.3.1VC++ 6.064

1.3.2VS系列67

1.4验证程序的设计71第2章线性表73

2.1顺序表73

2.2单链表82

2.3顺序表的应用95

2.4一元稀疏多项式求和101第3章栈和队列109

3.1顺序栈109

3.2链栈116

3.3栈的应用121

3.3.1括号匹配121

3.3.2表达式计算124

3.4顺序队列133

3.5链队140

3.6队列应用147第4章稀疏矩阵153

4.1稀疏矩阵转置153

4.2稀疏矩阵求和158第5章二叉树165

5.1二叉树简介165

5.2中序线索化二叉树176

5.3哈夫曼树和哈夫曼编码183第6章图189

6.1图的实现189

6.1.1程序设计简介189

6.1.2无向图的邻接矩阵实现190

6.1.3有向网的邻接表实现202

6.2图的遍历应用217

6.2.1邻接矩阵存储的图的遍历应用217

6.2.2邻接表存储的图的遍历应用221

6.3图的应用225

6.3.1*小生成树225

6.3.2*短距离232

6.3.3拓扑排序239

6.3.4关键活动244第7章查找251

7.1静态查找251

7.2字符串匹配256

7.3二叉排序树262

7.4散列查找270第8章内部排序277

第3篇设计篇

第1章绪299

1.1实验步骤299

1.2实验报告格式301

1.3实验报告案例301第2章线性表303

2.1实验目的303

2.2实验任务303

2.2.1集合运算303

2.2.2一元多项式求导305

2.2.3有序表合并307

2.2.4循环单链表309

2.2.5约瑟夫环问题311第3章栈和队列315

3.1实验目的315

3.2实验任务315

3.2.1数制转换315

3.2.2算术表达式正确性判断317

3.2.3栈的逆置318

3.2.4求任意长两个大整数的和319

3.2.5单指针链队问题322

3.2.6杨辉三角形问题324第4章数组和矩阵327

4.1实验目的327

4.2实验任务327

4.2.1求两个对称矩阵之和与乘积327

4.2.2“蛇形”矩阵329

4.2.3魔方问题330第5章树与二叉树333

5.1实验目的333

5.2实验任务333

5.2.1二叉树的叶结点计数333

5.2.2复制二叉树335

5.2.3求二叉树的宽度336

5.2.4求先/中/后序遍历序列的首、尾数据元素339

5.2.5叶结点路径问题341第6章图343

6.1实验目的343

6.2实验任务343

6.2.1存储结构转换问题343

6.2.2有向图的路径问题346

6.2.3无向图的路径问题350

6.2.4俱乐部选址问题352

6.2.5物流*短路径问题354第7章查找357

7.1实验目的357

7.2实验任务357

7.2.1顺序查找与折半查找357

7.2.2用二叉排序树实现字符统计358

7.2.3拉链法处理冲突的散列表360

7.2.4开放定址法处理冲突的散列表363第8章排序367

8.1实验目的367

8.2实验任务367

8.2.1单链表上的直接插入排序367

8.2.2单链表上的简单选择排序369

8.2.3双向冒泡排序370

8.2.4序列重排372

8.2.5堆判断374

第4篇综合篇

第1章绪论379

1.1综合设计内容380

1.2综合设计报告格式381第2章综合任务383

2.1个人乐库管理系统383

2.1.1问题描述383

2.1.2分析与设计提示383

2.1.3性能要求384

2.2高校学生信息快速查询系统384

2.2.1问题描述384

2.2.2分析与设计提示384

2.2.3性能要求386

2.3纸牌游戏386

2.3.1问题描述386

2.3.2分析与设计提示387

2.3.3性能要求388

2.4排雷游戏388

2.4.1问题描述388

2.4.2分析与设计提示389

2.4.3性能要求390

2.5迷宫问题390

2.5.1问题描述390

2.5.2分析与设计提示391

2.5.3性能要求393

2.6校园导游系统393

2.6.1问题描述393

2.6.2分析与设计提示393

2.6.3性能要求395

2.7打印任务管理395

2.7.1问题描述395

2.7.2分析与设计提示396

2.7.3性能要求396

2.8教学计划编制397

2.8.1问题描述397

2.8.2分析与设计提示398

2.8.3性能要求398

2.9基于哈夫曼编码的编码译码问题398

2.9.1问题描述398

2.9.2分析与设计提示398

2.9.3性能要求399

2.10校园优秀学生的推荐与评比400

2.10.1问题描述400

2.10.2分析与设计提示400

2.10.3性能要求401

参考文献403附录实验报告示例405

实验学生基本信息管理405

1问题描述与分析405

2数据结构设计406

3算法设计407

4运行与测试409

5小结410