《数据结构与算法》课程设计任务书(大纲)
学年学期：2013-2014学年第三学期
专业班级：13软金
指导教师：谢彦麒
设计时间：2014-7-7至2014-7-11
学时周数：1周
一、设计目的
1、培养学生运用算法与数据结构的基本知识解决实际编程中的数据结构设计和算法设计问题。
2、培养学生独立设计程序与解决问题的能力，培养学生团队协作集成程序模块及调试能力。
3、培养学生初步的软件设计及软件测试的能力。
二、设计任务及要求
基本要求：
学生必须仔细阅读《数据结构与算法》课程设计指导书，认真主动完成课程设计的要求。有问题及时主动通过各种方式与教师联系沟通。学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时的向教师汇报。
课程设计按照教学要求需要一周时间完成，一周中每天（按每周5天）至少要上3-4小时的机来调试C语言设计的程序，总共至少要上机调试程序15小时。
根据设计报告要求编写设计报告，主要内容包括目的、意义、原理和实现方法简介、过程分析及说明、实验结果情况说明、结论。
每个人必须有可运行的程序，学生能对自己的程序面对教师提问并能熟练地解释清楚，学生回答的问题和程序运行的结果作为评分的主要衡量标准；（周三开始逐一检查）
内容：
本次课程设计完成如下模块（共10个模块，学生可以在其中至少挑选4个功能块完成，但有**号的模块是必须要选择的,多做可以加分）
（1-2必须选做1题）**
1．火车票查询系统
火车票信息包括：车次、出发站、到达站、出发时间、到达时间、历时、一等座、二等座、无座以及票价，实例如下：
设计火车票预订系统实现如下功能“
① 要求能对火车票信息进行查询；
② 预订火车票；
③ 修改行程；
④ 退票；
选择实现如下功能：
①根据历时按照升序将所有车次排序；
②筛选所有D字头（动车）或G字头（高铁）车次；
③设计一个双程方案，让用户输入在目的地和在目的地呆的时间，输出最
优的车次及时间。如：在福州南呆3个小时，最优方案（D3118 7:22-8:52
前往福州南，D6411 12:00-13:37返回厦门北）
2．通讯录系统
设计一个通讯录系统，包括编号、姓名、手机号码、性别、地址，实现功能如下：
① 插入
② 查询
③ 删除
④ 更新
选择实现如下功能：
①排序
②筛选出所有姓林的联系人
③设计一个速配方案，给定一个联系人，在通讯录中为其速配一个有缘人。
要求一：异性；
要求二：手机号码各位之和尽可能接近
如：张三男137******** 速配王舞女158******** 各位之和均为
46
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%
五、报告书写格式
提交电子资料(提供文档质量共20分，若不按要求提交，指导教师可不提供考核分数)：
由以下两个部分组成，缺一不可，提交的电子内容放在一文件夹中，文件夹名要求按照“学号+姓名”起名（要求完整学号）。
1．学生按照课程设计的具体要求开发的所有源程序应该放到一个文件夹中并压缩成rar文件（压缩文件名要求按照"学号+姓名+数据结构课程设计源程序"起名，如文件夹名为：" ***01+张三+数据结构课程设计源程序.rar" ），文件夹中的文件只需要存储“题目名.cpp”；
2．课程设计报告：（保存在word 文档中，文件名要求按照"学号+姓名+数据结构课程设计报告"起名，如文件名为：" ***01+张三+数据结构课程设计报告.doc" ）按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成。
六、参考资料
[1] 严蔚敏,吴伟民.数据结构(C语言版) [M].北京:清华大学出版社. 1997.4.
[2] 陈元春等编著，实用数据结构基础，中国铁道出版社
[3] 黄翠兰，高级语言程序设计，厦门大学出版社
指导教师（签名）：
年月日