数据结构课程设计案例教程.pptVIP

5.4编码主要步骤包括：数据结构定义功能函数设计程序实现5.5测试1．设计测试用例2．程序运行结果6.迷宫问题

6.1任务与需求6.2总体设计6.3详细设计6.4编码6.5测试6.1任务与需求本案例要求生成一个迷宫，然后求出迷宫从入口到出口的路径。迷宫求解是常见的智力问题，可以考察被测试者的眼力和反应能力，每走一步时要看到后几步，遇到死胡同要及时回头，重新寻找出路。换做计算机的术语就是回溯，而实现回溯的方法有两种，一是递归方式，二是非递归方式，但是这两种方式的核心在数据结构课程中已有阐述，即都需要使用到堆栈，不同的是递归方式是由编译程序隐式实现，非递归方式则需要程序设计者显式实现。6.2总体设计迷宫生成算法:本设计实现的是“完美迷宫”，它可以归类于基于路径分类的迷宫。所谓完美迷宫是指迷宫中不存在环，且不存在不可访问的区域，也可称为单连通迷宫，如图6.1所示。完美迷宫中的任一点到另一点有且只有唯一的路径，在计算机术语中，可将完美迷宫描述为基于迷宫格子（cell）集合之上的一颗生成树。6.2总体设计（续）迷宫路径求解算法:迷宫已经生成完毕，迷宫路径求解算法与生成算法相似，也是采用回溯的思想，但是没有了拆墙的过程，也不是随机选择方向，而是采用东、南、西、北方向轮询的方式6.3详细设计涉及的知识点（1）栈的建立。（2）栈的操作。6.3详细设计（续）详细的设计思路（1）采用的数据结构（2）采用的算法6.4编码主要步骤包括：数据结构定义功能函数设计程序实现6.5测试1．设计测试用例2．程序运行结果7.哈夫曼树编码解码

7.1任务与需求7.2总体设计7.3详细设计7.4编码7.5测试7.1任务与需求本案例要求运用哈夫曼编码的相关知识对任意文本文件进行编码、解码，并保存相关结果。根据分析，本案例需要完成的具体功能有：（1）根据要编码的文件中字符出现的频率生成对应的哈夫曼编码；（2）得到采用哈夫曼编码后的目标文件，并保存；（3）根据要解码的文件对应的哈夫曼码表对文件进行解码；（4）得到解码后的目标文件并保存。7.2总体设计涉及的知识哈夫曼编码的相关概念哈夫曼树的生成算法哈夫曼编码算法7.3详细设计涉及的知识点（1）哈夫曼树的建立；（2）哈夫曼编码；（3）哈夫曼树的存储；（4）哈夫曼解码。7.3详细设计（续）详细的设计思路:哈夫曼树和哈夫曼编码的过程相对比较简单，但是要转化为程序代码需要花费一番功夫，可以确定的是有以下一些问题需要逐一解决。7.4编码主要步骤包括：数据结构定义功能函数设计程序实现7.5测试1．设计测试用例2．程序运行结果8.图的最短路径

8.1任务与需求8.2总体设计8.3详细设计8.4编码8.5测试8.1任务与需求本案例要求给定一个地图，求出指定地点到另一地点的最短路径。要求采用图的数据结构，能够建立图、保存图文件、读取图文件，能够求解指定地点到另一地点的最短路径。根据分析，本案例需要完成的具体功能有：（1）根据数据建立图；（2）能够保存图文件；（3）能够从保存过的文件中读取图文件；（4）能够求解指定地点到另一地点的最短路径。8.2总体设计涉及的知识根据需求分析结果确定程序的总体设计，首先在每个功能中都有输入和输出，所以设计时需要采用交互方式。\8.3详细设计涉及的知识点图的数据结构表示图的文件存储求解最短路径算法详细的设计思路8.4编码主要步骤包括：数据结构定义功能函数设计程序实现8.5测试1．设计测试用例2．程序运行结果

9.连接城市的最小生成树

9.1任务与需求9.2总体设计9.3详细设计9.4编码9.5测试9.1任务与需求本案例要求给定一个地图，包括若干城市及城市间道路的距离，用Prim算法或Kruskal算法建立最小生成树，求出最小生成树的代价。要求使用邻接矩阵来表示图。根据分析，本案例需要完成的具体功能有：（1）能够创建图（2）为了方便使用，可以把输入的图保存到数据文件中（3）能够读取数据文件中图的信息，创建图（4）能够显示最小生成树，应包括道路两端城市名称、道路长度以及最小生成树的代价2.活期储蓄账目管理系统

2.1任务与需求2.2总体设计2.3详细设计