数据结构课设题目及要求

1、2014春 佃2121-2班数据结构课程设计【成绩评定】课程设计的最终成绩由平时表现、演示程序并回答问题、课程设计报告三部 分综合评定。“数据结构课程设计”是一门必修的实践课程，和平时上课一样， 要求大家一定要按时到机房上机，不迟到不早退。如果不来上机（累计三次点名 未到）、或者未经老师验收程序并回答提问、或者不交实习报告都将作为“不及 格”处理；此外，如果发现完全抄袭他人实习报告，则抄袭者与被抄袭者的成绩 一律为“不及格”。【时间地点安排】上机时间：2014年2月27日、28日 下午3月1日、6日、7日、8日、13日下午3月14日晚上 3月15日下午下午 14:00-18:00 晚上 18:

2、00-22:00上机地点：综合楼313（地点若有变化，指导老师会另行通知）验收程序时间：3月14日、15日提交课程设计报告时间：3月27日注意：报告纸质双面打印（后面附有报告内容及格式要求），不打印源程序; 同时，每个同学提交报告和源程序的电子档，以班级为单位刻录光盘。【题目及分组情况】本次课程设计的题目共9题，分为三组，每组3题，每人任选一组题目完成。 在第一次课程设计时，每个人必须确定选择哪一组。第一组：1、4、7第二组：2、5、8第三组：3、6、91. 电梯模拟模拟某校九层教学楼的电梯系统。该楼有一个自动电梯，能在每层停留，其中第一层是大楼的进出层，即是电梯的“本垒层”，电梯“空闲”时，

3、将来到该层候命。电梯一共有七个状态，即正在开门（Opening）、已开门（Opened）、正在关门（Closing ）、 已关门(Closed)、等待(Waiting )、移动(Moving )、减速(Decelerate)。乘客可随机地进出于任何层。 对每个人来说， 他有一个能容忍的最长等待时间， 一旦等 候电梯时间过长，他将放弃。模拟时钟从 0 开始，时间单位为 0.1 秒。人和电梯的各种动作均要消耗一定的时间单位(简记为t),比如：有人进出时，电梯每隔40t测试一次，若无人进出，则关门；关门和开门各需要20t ;每个人进出电梯均需要 25t;电梯加速需要 15t;上升时，每一层需要 51

4、t， 减速需要14t；下降时，每一层需要61t，减速需要23t；如果电梯在某层静止时间超过 300t， 则驶回 1 层候命。要求：按时序显示系统状态的变化过程，即发生的全部人和电梯的动作序列。224 点游戏24 点游戏是一种使用扑克牌来进行的益智类游戏，游戏内容是：从一副扑克牌中抽去 大小王剩下 52 张，任意抽取 4 张牌，把牌面上的数( A 代表 1 )运用加、减、乘、除和括 号进行运算得出 24。每张牌都必须使用一次，但不能重复使用。要求：设计算法完成 24 点游戏的计算。 扩展内容：实现 24 点游戏的可视化界面。3洗车仿真 假设洗车站有三个洗车处，每个洗车处可构成一个等待队列。根据系

5、统时间随机生成 每辆车的到达时间，相邻两辆车的到达时间间隔为2,15分钟之间的随机值，每辆车接受服务的时间选项为 10、 15或 25 分钟其中之一(随机产生) 。第一辆车的到达时间在洗车站开 门 30 分钟之内(随机产生) 。平均等待时间是将每辆车的等待时间加起来再除以车的数量。 下面是关于车辆到达和离开的具体条件：( 1 )如果当队列为空且没有车被清洗时， 到达了一辆车， 那么就马上开始清洗这辆车； 它无需进入队列。 每当一辆车通过清洗后， 它就马上离开洗车处， 随之相应队头的车辆出队 进入清洗过程。( 2)每当一辆车到达时，它直接进入三个队列中等待时间最短的队列。( 3)每个队列中每次至

6、多有 5 辆车在等待洗车。当正在清洗并且三个队列中均有 5 辆 车时，如果此时有一辆车到达，那么它将作为“溢出”不准入内且不计算在内。( 4)每辆车的等待时间不含其接受服务的时间。 要求：写一个上述洗车业务的事件驱动模拟系统，并实现以下功能：( 1)产生 6 个小时内车辆的随机到达时刻和接受服务时间。( 2)输出所有车辆(包括未能进队洗车的车辆)的洗车情况(到达时间、所处等待队 列及等待时间、接受服务时间、离开时间等) 。( 3)计算所有车辆的平均等待时间。4文件目录管理与显示 给出目录和文件信息，编程实现将其排列成一棵有一定缩进的树。要求：( 1 )设计文件和目录信息树的存储结构。( 2)从

7、文件或键盘输入目录和文件信息，输入格式采用绝对路径法，即： AAAA1AAA1aa1.doc创建时要检查同一路径下不能有同名的目录或文件名。（3）设计文件和目录信息树的输出格式（以凹入表的形式显示）。（4）查找指定目录和文件。（5）添加新目录或新文件。（6）删除指定目录或文件，子目录能够被删除的前提是其为空，既不包含任何子目录 和文件；根目录不能删除。（7）扩充目录或文件信息，如创建时间、读写权限、文件长度或子目录包含的子目录 和文件数等。（8）对同一层次下的子目录或文件按创建时间有序输出。（9） 通配符的使用。如用“？”代表任意一个字符，用“*”表示任意多个多个任意字符。扩展内容：实现相对路

8、径表示法。5. 基于Huffman编码的压缩软件准备一个源文件（可以是你的源程序），统计该文件中各种字符出现的频率，对各字符进行Huffman编码，将该源文件压缩成编码文件，再将Huffman编码文件译码成源文件。要求：（1）设计合适的哈夫曼树存储结构，并设计编码和译码方法；（2） 将输入的源文件（比如l.cpp）压缩到文件2.txt中，输出源文件字符数（一个字 符是8位二进制数）和压缩后字符数，并计算压缩比；（3）将压缩文件2.txt再还原到文件3.txt，比较3.txt与源文件是否一致。扩展内容：采用范式哈夫曼编码（ Canonical Huffman Code ）实现文件压缩。6. 取火

9、柴游戏在盘中放着n根火柴，A和B两人轮流从盘中取火柴，规定每次可取一根、二根或三 根，不可不取也不可多取，谁拿走最后一根便算谁输。这就是所谓的取火柴游戏。其实，这 种游戏如同下棋，双方都有可能取胜。为了自己取胜，就必须每走一步（即取一次火柴）都 要动动脑筋，为自己的最后胜利创造条件，也就是说，每走一步都要有个较好的对策。我们可以利用树结构，把取火柴游戏的过程描述出来。为方便起见，假定n=6。开始时有六根火柴，A先走的话，他可有拿 1根、2根或3根火柴三种不同的走法。如果把原始状 态一一6根火柴，作为根结点，A的三种不同走法将产生盘中剩5根、4根、3根火柴三种状态，可用根结点的三个子结点表示（图

10、 1 ）。A走以后，不论 A走哪一步，B接着走时， 他也可在A取剩的火柴中拿走 1根、2根或3根，因此共有3X3= 9种可能性，再可产生 9 个子结点，接下来 A再走，。由于火柴的根数是有限的，而且每走一步都要减少些火 柴，因此火柴总会取完， 游戏随之结束。整个过程可用一棵树来表示。这课树反映了 A和B双方所有可能的对策，因此可以称为对策树。图1要求：设计程序实现两个人或人与计算机的取火柴游戏。7 农夫过河问题一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北 岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在 场，则狼不能吃羊，羊不能吃

11、白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白 菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。要求：利用图的存储结构和图的搜索算法，求出农夫将所有的东西运过河的方案。8. 全国交通咨询模拟出于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中 的时间尽可能短，出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。 编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。要求：（1）提供对城市信息进行编辑（如添加或删除）的功能。（2）城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑 （增设或删除）的功能。（3）提

12、供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具。（4）旅途中耗费的总时间应该包括中转站的等候时间。（5）咨询以用户和计算机的对话方式进行。9. 研究生入学考试成绩处理假设某大学计算机应用技术专业招收研究生n名，现在要根据报考者的考试成绩择优录取。考试课程有政治、英语、数学、专业综合四门。考试成绩分为两类：第一类为每门课 程都达到最低录取线；第二类为有一门或多门课程未达到最低录取线。录取方法是在每门课程达到最低录取线的考生中按总分从高到低录取。试设计一个成绩处理程序实现以上功能。要求：根据录取方法，打印输出n份录取通知书，列出录取者四门课程的成绩及总分（要求采用堆排序）。并能实现对

13、任一考生或任一门课程成绩的查找（要求两种查找方式，根据考号 或姓名进行查找，采用高效的查找算法）。录取通知书的格式如下：ADMISSION NOTICEXX XX XX （姓名）：You have bee n admittedYour scores:PoliticsXX（成绩）En glishXXMathematicsXXMajorXXTotalXXXXXUNIVERSITY数据结构课程设计报告格式封面包括：数据结构课程设计报告，班级，学号，学生姓名，指导老师，日期(写 年3月)报告内容：针对自己做的每个题目分别按下面内容写：题号题目：1 需求分析2设计2.1设计思想(1) 数据结构设计包括逻

14、辑结构设计和存储结构设计(2) 算法设计2.2设计表示(1) 函数调用关系图(2) 函数接口规格说明2.3详细设计3 .调试分析4用户手册5 测试数据及测试结果6 源程序清单说明：1、正文文字请使用 5号宋体单倍行距，其它标题类按上述字体大小。2、需求分析的内容：描述问题，简述题目要解决的问题是什么。规定程序的功能，输入和输出的形式。条件不足时补全。3、设计部分的内容：(1)设计思想数据结构设计主要介绍在实验中采用(或设计)的数据结构，以及原因。算法设计主要包括总体设计思路和主要算法的基本思想。总体设计包括划分为几个模 块，每个模块要完成的主要功能等等，还可画出主程序的流程图。(2 )设计表示

15、画出函数的调用关系图，定义每个模块对应的函数接口。(3 )详细设计主要算法的实现用伪码和图示描述。关键的地方添加注释。注意：此部分不是源代码的直接拷贝；要写出主要操作的伪码算法。4、调试分析：(1)调试过程中遇到的问题是如何解决的以及对设计和编码的回顾讨论与分析；(2 )算法的时间空间复杂度分析；(3) 不局限于题目要求使用的算法，探讨更多解决问题的途径，或者提出自己的见解， 给出改进算法以得到更好结果的建议。5、用户手册：2014原题用户使用该系统或程序的详细说明/步骤。6、测试数据及测试结果：设计一张测试用例表，每个测试用例包括以下内容： 测试输入：设计一组输入数据； 测试目的：设计该输入的目的在于测试程序在哪方面可能存在漏洞； 正确输出：对应该输入，若程序正确，应该输出的内容； 实际输出：该数据输入后，实际测试得到的输出内容； 错误原因：如果实际输出与正确输出不符，分