东北大学 数据结构 模拟队列打印 实验报告.doc

实 验 报 告课程名称：数据结构班级：会计1203实验成绩：实验名称：打印机模拟程序的设计学号：20120577批阅教师签字：实验编号：实验一姓名：柳思杨实验日期：2014年 06月 22日指导教师：张明卫组号：实验时间： 时 分 时 分一、实验目的写出你认为比较重要的实验目的1、了解和掌握队列的数据类型描述及其特点。2、掌握队列初始化、入队、出队等相关基本操作的实现方法，从而达到能灵活运用队列解决应用问题的目的。二、实验内容与实验步骤（1） 简短明确地写出实验的内容1.首先,在一个名为fifo.h的文件声明类fifo。声明类fifo适当模型下面的关系:一个fifo是一种模拟器。2.接下来,完整的实现fifo:模拟。这个成员函数应该首先使用继承loadworkload加载数据文件,那么它应该实现仿真如上所述。使用继承seconds_per_page数据成员,以帮助确定打印作业需要打印多久。你的解决方案的输出应该匹配的输出示例解决方案。为了清楚起见,延迟秒数,间隔打印作业时,当它到达开始打印。总延迟是所有打印作业的总延迟,和平均延迟是所有打印作业的平均延时。（2） 简短描述抽象数据类型或设计的函数描述，说明为什么要使用这种抽象数据类型，并说明你的解决设想queue a;建立一个存放event的队列对象a。把按wait_until顺序从workload中的event导出，再依次把event对应的job任务计算出打印的时间点printtime，存入新构造的event的wait_until域中，最后这些event按打印时间将存入a队列中。（3） 简短明确地写出你实验所采用的存储结构及其用途，详细说明其中的属性的含义。存储结构：Queue。即存放event对象的队列。用途：其先进先出的特点符合实际打印业务的需求。主要属性：Queue();/构造函数Queue();/析构函数void push(T & e);/入队void pop();/出队T front();/返回第一个存储对象int size();/队列中存储对象的数量bool empty();/判断是否为空 三、实验环境操作系统、调试软件名称、版本号，上机地点，机器台号操作系统：win7旗舰版调试软件名称：VS2010版本号：2010上机地点：寝室机器台号：笔记本四、实验过程与分析（1） 描述你在进行实现时，主要的函数或操作内部的主要算法，分析这个算法的时、空复杂度，并说明你设计的巧妙之处。第一步：定义一个int变量time，在大循环内逐次加一，模拟时间的递增。第二步：定义一个queque对象a，用于保存已到达并正在等待打印的event。定义一个int变量printtime，计算每一次到达的event的打印时间点。当time等于workload中顶端元素的wait_until时，弹出event对象，在屏幕上打印出这项任务到达的信息，如：“Arriving: 100 pages from giraffe at 1 seconds”。算出这个event对应的job的打印时间，并保存在printtime变量里，在把这个job和printtime构造成新的event时间存入定义的queue对象a中。第三步：当time等于a中顶端元素的wait_until时，说明此项任务打印完毕，弹出event对象，在屏幕上打印出这项任务已打印的信息，如：“Servicing: 100 pages from giraffe at 1 seconds”。第四步：当workload和a都为空了以后，以break退出循环。第五步：通过在循环内定义number，latency等int型变量，累加算出Total jobs， Aggregate latency，Mean latency等值并打印在屏幕上。时间复杂度：O(n)空间复杂度：O(n)巧妙之处：说实话，不巧妙，算法性能还可以略微提高。（2） 你在调试过程中发现了怎样的问题？又做了怎样的改进（要求写出具体的事例）有些event的wait_until是同时的，所以每次入队后直接把time+1是不对的，可能漏掉一个event。改进，每次弹出一个event后不要立即改变time值，当下一循环time不再等于顶端元素的wait_until时再加1.（3） 你的实现是否具有可扩展性，如针对多个打印队列的仿真程序？稍微改一下是可以的。五、实验结果总结回答以下问题：（1） 你的测试充分吗？为什么？你是怎样考虑的？用了试验给出的ARBITRARY和BIGFIRST两组数据，结果均正确。（2） 为什么你要选用队列作为你应用的数据结构？其先进先出的特性符合打印业务的要求。（3） 用一段简短的代码及说明论述你的应用中主要的函数的主要处理部分。while(true)if(!workload.empty()if(time=workload.front().arrival_time()cout Arriving:workload.front().getjob().getnumpages() pages from workload.front().getjob().getuser() at workload.front().arrival_time()secondsendl;/当time等于workload中顶端元素的wait_until时，弹出event对象，在屏幕上打印出这项任务到达的信息，如：“Arriving: 100 pages from giraffe at 1 seconds”。a.push(event(job(workload.front().getjob().getnumpages(),workload.front().getjob().getuser(),printtime);/算出这个event对应的job的打印时间，并保存在printtime变量里，在把这个job和printtime构造成新的event时间存入定义的queue对象a中。number+=1;latency-=workload.front().arrival_time();printtime=printtime +workload.front().getjob().getnumpages()*seconds_per_page;workload.pop();time-;/当time等于a中顶端元素的wait_until(即它的printtime)时，说明此项任务打印完毕，弹出event对象，在屏幕上打印出这项任务已打印的信息，如：“Servicing: 100 pages from giraffe at 1 seconds”if(a.empty()time+;continue;if(time=a.front().arrival_time()cout Servicing:a.front().getjob().getnumpages() pages from a.front().getjob().getuser() at isecondsendl;latency+=a.front().arrival_time();a.pop();if(a.empty() & workload.empty() )break;i+;/通过在循环内定义number，latency等int型变量，累加算出Total jobs，Aggregate latency，Mean latency等值并打印在屏幕上。coutTotal jobs:numberendl;coutAggregate latency: latency secondsendl;coutMean latency: (double)latency/number) secondsendl;（4） 用结构化图表或者结构化代码描述源程序的大致的执行过程。Queue workloadQueue await_untilnumber_of_pagesuserwait_untilnumber_of_pagesuser51giraffe41falcon36herring22platypus File - Queue workloadQueue await_untilnumber_of_pagesuserwait_untilnumber_of_pagesuser51giraffe41falcon36herring22platypus - Arriving: 2 pages from platypus at 2 secondsQueue workloadQueue await_untilnumber_of_pagesuserwait_untilnumber_of_pagesuser51giraffe41falcon36herring- Servicing: 2 pages from platypus at 2 seconds Queue workloadQueue await_untilnumber_of_pagesuserwait_untilnumber_of_pagesuser51giraffe41falcon66herring- Arriving: 6 pages from herring at 3 secondsQueue workloadQueue await_untilnumber_of_pagesuserwait_untilnumber_of_pagesuser51giraffe181falcon66herring- Arriving: 1 page from falcon at 4 secondsQueue workloadQueue await_untilnumber_of_pagesuserwait_untilnumber_of_pagesuser201giraffe181falcon66herring- Arriving: 1 page from giraffe at 5 secondsQueue workloadQueue await_untilnumber_of_pagesuserwait_untilnumber_of_pagesuser201giraffe181falcon- Servicing: 6 pages from herring at 6 secondsQueue workloadQueue await_untilnumber_of_pagesuserwait_untilnumber_of_pagesuser201giraffe- Servicing: 1 page from falcon at 18 secondsQueue workloadQueue await_untilnumber_of_pagesuserwait_untilnumber_of_pagesuser- Servicing: 1 page from giraffe at 20 seconds请清晰、准确、详细地回答上面的问题，要求标点符号正确无误，图表表示符合规范。你的报告应至少超出一页的文字描述，注意你描述的文字一定要叙述流畅，具有较好的逻辑性。六、附录（1） 如果你对这个实验还有其他的解决方案或设想，或对我们的实验方案有什么意见，请在此描述。无。（2） 实验参考的资料数据结构（面向对象方法与c+语言描述）第2版百度文库（3） 回答思考题a) 栈和队列在计算机系统中有哪些应用？写出你知道的系统中，这两种抽象数据类型的应用。不太清楚。或许在俄罗斯方块游戏中运用了栈，而在网络下载中运用了队列。b