软件学院实践教学环节任务书数据结构版文档格式.docx

软件学院实践教学环节任务书数据结构版文档格式.docx

《软件学院实践教学环节任务书数据结构版文档格式.docx》由会员分享，可在线阅读，更多相关《软件学院实践教学环节任务书数据结构版文档格式.docx（20页珍藏版）》请在冰点文库上搜索。

4.进行简单界面设计，能够实现友好的交互；

5.具有清晰的程序流程图和数据结构的详细定义；

6.熟练掌握C语言或者C++语言的各种操作。

创新要求：

在基本要求达到后，可进行创新设计，如系统用户功能控制，改进算法的实现，实现友好的人机交互等等

三、问题描述和求解方法：

1、问题描述（功能要求）：

可以任意定义一个迷宫，用非递归的方法求出走出迷宫的通路，并把路径输出出来。

要求：

存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法。

1）迷宫的存储结构要合理；

2）应该考虑算法的时间和空间复杂度。

3）当确定迷宫的规模以及形态以后要把至少一条能走出迷宫的路径输出出来；

4）程序应当满足正确性、可读性、健壮性和高效率及低存储量等目标要求，遵循代码规范，方便调试和阅读。

2、问题的解决方案：

根据系统功能要求，可以将问题解决分为以下步骤：

（1）迷宫可以采用二维数组来存储，迷宫的通路状态可以用不同的字符来表示；

（2）根据问题描述，设计算法的实现；

（3）建议在解决问题时要采用栈或者队列数据结构；

（4）完成算法的各个功能模块；

（5）功能调试；

（6）完成系统总结报告以及系统使用说明书。

四、解题过程

1.分析程序的功能要求，划分程序功能模块。

2.画出系统流程图。

3.代码的编写。

定义数据结构和各个功能子函数。

4.程序的功能调试。

5.完成系统总结报告以及使用说明书

五、进度安排

此次课程设计时间为一周，分以下几个阶段完成：

1.选题与搜集资料：

每人选择一题，进行课程设计课题的资料搜集。

2.分析与概要设计：

根据搜集的资料，进行程序功能与数据结构分析，并选择合适的数据结构、并在此基础上进行实现程序功能的算法设计。

3.程序设计：

运用掌握C/C++语言编写程序，实现各个模块功能。

4.调试与测试：

调试程序，并记录测试情况。

5.完成课程设计报告。

6.验收与评分：

指导教师对每个同学的开发的系统进行综合验收，并由学院考核小组进行随机抽查评分。

六、撰写课程设计报告或课程设计总结

课程设计报告要求：

课程设计报告要求规范书写，应当包括如下6个部分：

1.问题描述

2.基本要求

3.系统分析与设计

4.测试数据及结果

5.总结

6.附录：

源程序清单

七、答辩与评分标准：

1、作业文档：

50分；

2、基本功能和要求：

20分；

2、设计报告及使用说明书：

10分；

3、设置错误或者按照要求改变结果：

4、回答问题：

10分。

八、参考资料

《数据结构（C语言版）》

网上相关资料（....略）

校园交通导游系统

通过输入一张某公园景点和导游路径，游客通过终端询问可知：

从某一景点到另一景点的最短路径。

1）可以把公园景点和导游路径抽象成为有向图或者无向图，进而把问题转化成为求解最短路径。

2）任意选取Dijkstra算法、Bellman-Ford算法或者Floyd算法求最短路径。

数据结构实践教学环节任务书

一、题目:

哈夫曼编码/译码的设计与实现

首先根据给定的n个权值构造哈夫曼树。

通过遍历此二叉树完成哈夫曼编码。

内部排序算法的性能分析

功能：

设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数。

1）界面友好，函数功能要划分好

2）总体设计应画出流程图

3）程序要加必要的注释

4）要提供程序测试方案

5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值

1）对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较；

2）排序表中数据数目不小于100，表中数据随机产生，至少用5组不同数据集作比较，比较指标有：

关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动）；

3）输出比较结果。

4）用描点法绘出各种排序算法对着问题规模增长关键字比较次数和交换次数的变化趋势，同算法本身时间复杂度进行比较。

7.分析程序的功能要求，划分程序功能模块。

8.画出系统流程图。

9.代码的编写。

10.程序的功能调试。

11.完成系统总结报告以及使用说明书

7.选题与搜集资料：

8.分析与概要设计：

9.程序设计：

10.调试与测试：

11.完成课程设计报告。

12.验收与评分：

表达式翻译

二、目的与要求

编写完整程序，将中缀表达式翻译成后缀表达式。

表达式由操作数（变量）、操作（运算符）以及小括弧“（”和“）”组成，其中：

1）操作包括算术运算、关系运算和逻辑运算三类；

2）操作数为单个字符或由字母和数字任意多个字符构成；

3）能够识别出简单的错误，如括弧不匹配。

输入：

中缀表达式，80个字符以内。

输出：

运算结果

1）利用栈结构实现算数表达式的四则运算

或者

2）利用二叉树把中缀表达式转化为前缀表达式

一元稀疏多项式计算器

1、问题描述

设计一个一元多项式加法器。

输入并建立多项式，实现两个多项式的加法运算。

5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。

1）多项式的表达：

n,c1,e1,c2,e2,…cn,en,其中，n是多项式项数，ci和ei分别是第i项的系数和指数，序列按指数降序或者升序排列；

2）利用线性结构存储多项式的每一项。

3）多项式加法运算即转化为线性表的条件归并运算。

农夫过河问题

要求设计实现农夫过河问题（农夫带着一只狼，一只养，一棵白菜，一次只能带一个东西）如何安全过河。

可以用栈与队列、深度优先搜索算法及广度优先搜索算法相应的原理去解决问题。

1）实现四个过河对象（农夫、白菜、羊和狼）的状态，可以用一个四位二进制数来表示，0表示未过河，1表示已经过河了。

2）过河的对象必须与农夫在河的同一侧，可以设计函数来判断。

3）防止状态往复，即农夫将一个东西带过去又带回来的情况发生，需将所有可能的状态进行标定。

4）可用深度优先搜索算法及广度优先搜索算法去解题。