数据结构专业课程设计任务计划书(2).doc

《数据结构》课程设计任务书
年学期：-第三学期
专业班级：14软件（工程技术）
指导老师：林开标
设计时间：-7-6至-7-10
课时周数：1周
一、设计目标
1、培养学生利用算法和数据结构基础知识处理实际编程中数据结构设计和算法设计问题。
2、培养学生独立设计程序和处理问题能力，培养学生团体协作集成程序模块及调试能力。
3、培养学生初步软件设计及软件测试能力。
二、设计任务及要求
基础要求：
学生必需仔细阅读《数据结构》课程设计指导书，认真主动完成课程设计要求。有问题立即主动经过多种方法和老师联络沟通。学生要发挥自主学习能力，充足利用时间，安排好课设时间计划，并在课程设计过程中不停检测自己计划完成情况，有困难立即向老师汇报。
课程设计根据教学要求需要一周时间完成，一周中天天（按每七天5天）上机调试程序时间不少于4小时，总共最少要上机调试程序15小时。
依据设计汇报要求编写设计汇报，关键内容包含目标、意义、原理和实现方法介绍、过程分析及说明、试验结果情况说明、结论。
每位同学必需有可运行程序，学生能清楚解释各自编写程序，并回复老师提问，学生回复问题和程序运行结果作为评分关键衡量标准；（周三开始逐一检验）。
内容：
此次课程设计完成以下模块（共10个模块，学生能够在其中最少挑选3个功效块完成，但有**号模块是必需要选择,多做能够加分）

（1-2必需选做1题）**
1．航班查询系统
飞机航班信息包含：航班号、起点站、终点站、起飞时间、抵达时间、机型和票价，实例以下：

设计航班查询系统要求能对飞机航班信息进行增加、删除、排序和查找。可按航班航班号、起点站、终点站、起飞时间和抵达时间进行查询。

2．停车场管理系统
某停车场能够停放n辆汽车，该停车场只有一个大门， 每辆汽车离开停车场全部要求之前汽车必需先退出停车场为它让道，以后让道汽车再次驶入停车场，停车场示意图以下：

要求设计停车管理系统，实现车辆进入、离开并依据停车时间计费。

3、字符串操作
任务：字符串采取数组存放，建立两个字符串String1和String2.输出两个字符串。
将字符串String2头n个字符添加到String1尾部，输出结果。
查找String3在串String1中位置，若String3在String1中不存在，则插入String3在String1中m位置上。输出结果。

4、设有一元多项式Am(x)和Bm(x)。

任务：能够根据指数降序排列建立并输出多项式；
能够完成两个多项式相加M(x)= Am(x)+Bm(x)，并将结果输出；
能够完成两个多项式相减M(x)= Am(x)-Bm(x)，并将结果输出；
在上交资料中请写明：存放结构、多项式相加基础过程算法（能够使用程序步骤图） 、源程序、测试数据和结果、算法时间复杂度、另外能够提出算法改善方法；

5、迷宫求解
任务：能够输入一个任意大小迷宫数据，用非递归方法求出一条走出迷宫路径，并将路径输出；
要求：在上交资料中请写明：存放结构、基础算法（能够使用程序步骤图）、源程序、测试数据和结果、算法时间复杂度、另外能够提出算法改善方法；

6、文章编辑
功效：输入一页文字，程序能够统计出文字、数字、空格个数。静态存放一页文章，每行最多不超出80个字符，共N行。
要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现次数，并输出该次数；（3）删除某一子串，并将后面字符前移。
存放结构使用线性表，分别用多个子函数实现对应功效；
输入数据形式和范围：能够输入大写、小写英文字母、任何数字及标点符号。
输出形式：（1）分行输出用户输入各行字符；（2）分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"（3）输出删除某一字符串后文章；

7、敢死队问题
任务：有M个敢死队员要砸掉敌人一碉堡，谁全部不愿意去，排长决定采取轮回数数措施来决定哪个战士去实施任务。假如前一个战士灭洋完成任务，则要派另一个战士上去。先给每个战士一个编号，大家围坐成一圏，随便从某个战士开始计数，当数到5时，对应战士就去实施任务，且此战士不再参与下一轮计数。假如战士没有完成任务，再从下一个战士开始数数，被数到5时，此战士接着去实施任务，以这类推，直到任务完成为止。
排长是不愿意去，假设排长为1号，请你设计一个程序，求出从几号战士开始计数才能让排长最终一个留下而不去实施任务。
要求：
最少采取两种不一样数据结构方法完成。假如有采取三种以上，可加分。
输入数据：输入M ，M为大于1正整数。
输出形式：汉字提醒根据M个战士，数5，从几号战士开始计数，排长为最终一个留下 ，建立一个函数来实现此功效。

（8-9必需选做1题）**
8、二叉树运算1
任务：求二叉树中指定两个结点共同最近祖先。

9、二叉树运算2
任务 ：请设计一个算法，把二叉树叶子结点按从左到右次序连成一个单链表。二叉树用二叉链存放，链接时用叶子结点rchild 域存放指针。

注：在上交资料中请写明：存放结构、 基础算法（能够使用程序步骤图） 、输入输出、源程序、测试数据和结果、算法时间复杂度、另外能够提出算法改善方法；

10、多种排序
任务：随机产生N个整数（1000以下），用程序实现插入法排序、起泡法改善算法排序；
利用插入排序和冒泡法改善算法,将用户随机输入一列数按递增次序排好。
输入数据形式为任何一个正整数，大小不限。
输出形式：数字大小逐一递增数列。

三、设计时间进度安排
星期一----星期二： 代码设计
星期三----星期五： 程序调试、代码演示、考评答辩
星期五： 编写课程设计汇报、提交资料
四、成绩考评
每个人必需有可运行程序，学生能对自己程序面对老师提问并能熟练地解释清楚，学生回复问题和程序运行结果作为评分关键衡量标准；
1、 程序可用性、通用性：30%
2、 编程动手能力：30%
3、 课程设计汇报：20%
4、 回复问题：20%

五、汇报书写格式
课程设计提交材料由以下部分组成，缺一不可，提交电子内容放在服务器中“数据结构课程设计”目录中。
1．上交源程序：学生根据课程设计具体要求所开发全部源程序（应该放到一个文件夹“code”中）；.
2．上交程序说明文件：（保留在文件名根据“文件清单+学号+姓名.txt“中）在说明文档中应该写明：实现题目及上交程序所在目录，上交程序文件名，假如需要安装，要有程序安装使用说明；
3．课程设计汇报：（保留在word 文档中，文件名要求根据"学号+姓名"起名，如文件名为："110101+张三.doc" ）根据课程设计具体要求建立功效模块，所选每个题目要求根据以下多个内容认真完成。（课程设计结束后每人要求打印课程设计汇报，两个工作日内学习委员负责搜集上交课程设计汇报打印材料。）
一、题目内容描述
1.1 应用程序功效具体说明
1.2 输入数据类型、格式和内容限制；
1.3 关键模块算法描述
–以程序步骤图方法给出
–简明语言描述
1.4 运行结果截图及其说明

六、参考资料
[1] 严蔚敏,吴伟民.数据结构(C语言版) [M].北京:清华大学出版社. .
[2] 陈元春等编著，实用数据结构基础，中国铁道出版社
[3] 黄翠兰，高级语言程序设计，厦门大学出版社

指导老师（署名）：
年 月 日