学年学期：2011-2012学年第1学期。
专业班级：10软件工程1班。
指导教师：吴芸。
设计时间：2011-12-12至2011-12-16
学时周数：1周。
一、设计目的。
1、培养学生运用算法与数据结构的基本知识解决实际编程中的数据结构设计和算法设计问题。
2、培养学生独立设计程序与解决问题的能力，培养学生团队协作集成程序模块及调试能力。
3、培养学生初步的软件设计及软件测试的能力。
二、设计任务及要求。
基本要求：学生必须仔细阅读《数据结构》课程设计指导书，认真主动完成课程设计的要求。有问题及时主动通过各种方式与教师联系沟通。
学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时的向教师汇报。
课程设计按照教学要求需要一周时间完成，一周中每天（按每周5天）至少要上3-4小时的机来调试c语言设计的程序，总共至少要上机调试程序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 文档中，文件名要求按照"学号+姓名"起名，如文件名为："2011110101+张三。
doc" ）按照课程设计的具体要求建立的功能模块，所选每个题目要求按照如下几个内容认真完成。（课程设计结束后每人要求打印课程设计报告，两个工作日内学习委员负责收集上交课程设计报告的打印材料。）
一、题目内容的描述
1.1 应用程序功能的详细说明
1.2 输入数据类型、格式和内容限制；
1.3 主要模块的算法描述
以程序流程图的方式给出
简要的语言描述
1.4 运行结果截图及其说明。
六、参考资料。
1] 严蔚敏，吴伟民。数据结构(c语言版) [m].北京：清华大学出版社。 1997.4.
2] 陈元春等编著，实用数据结构基础，中国铁道出版社。
3] 黄翠兰，高级语言程序设计，厦门大学出版社。
指导教师（签名。
年月日。
数据结构课程设计任务书
数据结构 课程设计任务书。一 数据结构课程设计要求。仔细阅读 数据结构课程设计指导 一书，选好题目，认真制定课程设计方案，在规定的时间内设计完成并按一定格式以书面形式上交报告。设计报告内容一般包括以下几个方面 1 问题描述 2 设计思路 3 数据结构定义 4 系统功能模块介绍。5 程序清单 6 运行...
数据结构课程设计任务书
题目 哈夫曼树应用功能 1 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmtree中。将已在内存中的哈夫曼树以直观的方式 比如树 显示在终端上 2 利用已经建好的哈夫曼树 如不在内存，则从文件htmtree中读入 对文件tobetran中的正文进行编码，然后将结果存...
钢结构课程设计任务书
建筑结构课程设计任务书。工作平台设计。一 设计资料 一工作平台的布置如图1所示，主次梁采用q235钢材的组合梁和工字型钢梁，用e43型焊条手工焊。次梁上作用的恒载 100mm厚的预制钢筋混凝土板 容重25kn m3 与次梁焊接，预制板上铺有50mm厚的豆石混凝土 容重24kn m3 平台上活载的标准...