数据结构课程设计任务书.DOC

1、 东华理工大学 软件学院 软件工程系 1数据结构课程设计任务书（2008-2009 学年第 2 学期用）一、课程设计目的本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。二、课程设计题目共 7 题，每个学生一题，单独完成。 （选法为根据学生所在班级名册的自然顺序，第1-7 名同学分别做第 1 到第 7 题，然后循环，第 8-14 名同学分别做第 1 到第 7 题，依次类推。 ）1、 运动会分数统计系统任务：参加运动会有 n 个学校，学校编号为 1n。比赛分成 m 个

2、男子项目，和 w 个女子项目。项目编号为男子 1m，女子 m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。 （m=20,n=20）功能要求：1).可以输入各个项目的前三名或前五名的成绩；2)能统计各学校总分，3)可以按学校编号、学校总分、男女团体总分排序输出；4).可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。规定：输入数据形式和范围：20 以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）输出形式：有中文提示，各学校分数为整形界面要求：有合理

3、的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计。请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用 1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；2、 航班订票系统任务：通过此系统可以实现如下功能：1） 、录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）2） 、查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓） ；可以输入起飞抵达城市，查询飞机航班情况；3

4、） 、订票：（订票情况可以存在一个数据文件中，结构自己设定）东华理工大学 软件学院 软件工程系 2可以订票，如果该航班已经无票，可以提供相关可选择航班；4） 、退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。5） 、修改航班信息：当航班信息改变可以修改航班数据文件要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计。请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用 1、全部合法数据；2、整

5、体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；3、 迷宫问题非递归求解任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；要求：在上交资料中请写明：存储结构、基本算法（可以使用程序流程图） 、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；4、 文本编辑和串查找统计任务：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过 80 个字符，共 N 行；功能要求：1） 、分别统计出其中英文字母数和空格数及整篇文章总字数；2） 、统计某一字符串在文章中出

6、现的次数，并输出该次数；3） 、删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能（要求用菜单选择操作） ；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分 4 行输出“全部字母数“ 、“数字个数“ 、“ 空格个数“、“ 文章总字数“（3）输出删除某一字符串后的文章；5、 各种内部排序性能比较任务：用程序实现插入法排序、起泡法、选择法、快速法、合并法排序；输入的数据形式为任何一个正整数，大小不限。输出的形式：数字大小逐个递增的数列。功能要求：给出多组不同元素个数的输入数据(可考虑用随机

7、函数生成整数，而不用人工输入)，并用列表打印出每种排序下的各趟排序结果。每个排序法结束时应打印出其元素比较的次数和交换的次数。此程序需将结果用列表打印，一定要将其打印结果排列好。6、题目：图的遍历和拓扑排序任务：给定一个有向图，实现图的深度优先, 广度优先遍历算法，拓扑有序序列，并输出相关结果。功能要求：输入图的基本信息，并建立图存储结构（有相应提示） ，输出遍历序列，然后进行拓扑排序，并测试该图是否为有向无环图，并输出拓扑序列。7、题目： 哈夫曼树和编码应用任务和功能：东华理工大学 软件学院 软件工程系 3（1）从终端读入字符集大小 n，以及 n 个字符和 n 个权值，建立哈夫曼树的存储结构

8、；（2）利用已经建好的哈夫曼树（如不在内存，则从文件 htmTree 中读入） ，对给定的 n 个字符正文进行编码，并输出结果。（3）利用已建好的哈夫曼树，对给定的一个哈夫曼编码进行译码，判断此编码对应的字符，并输出结果。三、课程设计要求：1、每人一题，且需独立完成。2、每人的设计程序必须为可执行的 exe 文件，且需指导教师验收合格。学生程序必须在课程设计的最后一天交由指导教师验收合格。过期不再验收程序，如程序验收不合格或在规定时间内未经指导教师验收，则视为该生程序没有完成。3、每人必须在规定时间内到机房做程序，指导老师将严格考勤，上机期间严禁做与课程设计无关的事情。指导教师将随时抽查。4、

9、每人必须撰写课程设计报告（格式附后） 。并上交程序代码电子稿（每位同学先建立一个文件夹，取名规则为“学号+姓名” ，文件夹里存放上交电子内容，每班取一文件夹名，取名规则为班级号，内放该班同学上交内容，每班学习委员统一收齐后拷贝给指导老师） 。四、课程设计评分标准：1程序设计质量（占 40%）2课程设计报告质量（占 30%）3平时表现（占 30%）五、上机时间安排表课程设计的时间及教师安排专业 班级 周次 机房安排 上机时间 指导老师软件工程 071101-3 第 13 周 504/506 星期一星期四， 1-4 节 许志文/刘琳软件工程 071104-6 第 13 周 504/506 周一周三

10、 5-8 节，周四9-12 节 许志文/刘琳附：课程设计报告格式。1、 需求分析说明（说明为何做该题目，从其需求上说明。 ）2、 总体设计（从总体上说明该题目的框架，用文字和图表说明）3、 详细设计（写出程序中所有的类及其对象，以及类与类之间的继承关系等，并把每个类及其所有成员函数的功能说明，参数接口等描述清楚。对于关键算法需用程序流程图描述出来，并写出其算法步骤。并写出该算法的时间、空间复杂充。并用 UML 图画出其各类和对象以及用例图等。 ）4、 代码5、 程序测试（给出各测试数据及其对应的测试结果，和程序运行图贴于此处。并能对程序运行结果分析之，且需提出改进算法。 ）6、 总结东华理工大学 软件学院 软件工程系 4