东北大学打印机管理数据结构设计作业.doc

实 验 报 告课程名称：数据结构班级：软件赴日1101实验成绩：实验名称：模拟打印机学号：20112271批阅教师签字：实验编号：实验一姓名：贾志远实验日期：2013年5月21日指导教师： 组号：实验时间：18时30分8时11分一、实验目的让我们更加深入的理解队列和栈，并且学会使用STL优先队列容器的适配器，主要是为了运用栈和队列。二、实验内容与实验步骤（1） 简短明确地写出实验的内容 设计一个程序，模拟打印机，随时间变化打印队列不断进入并且当打印任务完成时又会把打印任务一个个释放掉，一旦打印任务为空，则会有后一个打印任务跟进，直到打印完成才会结束，释放掉所有空间。（2） 简短描述抽象数据类型或设计的函数描述，说明为什么要使用这种抽象数据类型，并说明你的解决设想 job对象主要是建立工作任务，其中number_of_pages为打印的页数，user描述的是打印人，event对象主要是描述将要打印的任务，其中wait_until表示等待的时间，j描述即将打印的任务，simulator对象表示打印机的性质（表示打印的页数和打印任务、打印量等），其中seconds_per_page表示的是每页所需打印时间，workload是由文件读取即将打印的任务，fifo对象是对simulator中的函数进行实现，其中waitlist为等待队列，worker表示正在进行的任务,time表示时间,resttime描述打印当前任务剩余所需时间,waittime表示任务总共需要的时间,totaljob表示已经进行过的任务数量。（3） 简短明确地写出你实验所采用的存储结构及其用途，详细说明其中的属性的含义。 该实验使用了队列的存储结构，存储数据方式采用的是先进先出，元素从队列末尾进入，队列头部删除（插入元素法）。该实验主要用了以下几个方法：empty（判断队列是否为空）、front(返回队列头元素)、back（返回队列尾元素）、delete（删除队列的头元素）、add（添加元素到队列末尾）。三、实验环境操作系统、调试软件名称、版本号，上机地点，机器台号操作系统为WIN7，调试软件名称：Microsoft Visual Studio 2012，上机地点：寝室四、实验过程与分析（1） 描述你在进行实现时，主要的函数或操作内部的主要算法，分析这个算法的时、空复杂度，并说明你设计的巧妙之处。 用time来记述元素不间断转移（进出队列）。时间复杂度上，只有一个while循环，所以时间复杂度为O(n)，n为总时间。空间复杂度上，总空间使用度等于总的事件数目*事件的大小。（2） 你在调试过程中发现了怎样的问题？又做了怎样的改进？ 没什么太大的问题，主要是参数设置出现了问题，对参数设置不太了解，查下网就解决了，还有对栈中数据要及时清空，不然会有程序不间断运行，占用内存。（3） 你的抽象数据类型的实现是否具有可扩展性？ 队列可在参数中实现数据类型上的扩展。五、实验结果总结回答以下问题：（1） 你的测试充分吗？为什么？你是怎样考虑的？ 输出文件名为print，测试arbitrary.run文件时与arbitrary.out的输出相同，将参数改为bigfirst.run时输出结果与bigfirst.out的输出结果也相同。（2） 用一段简短的代码及说明论述你的应用中主要的函数的主要处理部分。 void simulate(string f)string outf=print;ofstream fout(outf.c_str();foutFIFO Simulation endl;loadworkload(f);while(!(workload.empty()&waitlist.empty()&worker=0)time+;while(!workload.empty()&workload.front().arrival_time()=time)waitlist.add(workload.front().getjob();foutArriving :waitlist.back()attimesecondsendl;workload.delete();if(!worker&!waitlist.empty()worker=new job(waitlist.front();foutServicing: *workerattimesecondsgetnumpages()*seconds_per_page-1; totaljob+=1;if(!waitlist.empty()waittime+=waitlist.size();if(worker)if(resttime)resttime-;else delete worker;worker=0; 运行结果为： （3） 为什么你要选用栈或队列或字符串或数组等抽象数据类型作为你应用的数据结构？ 因为动态数组可以自动调节大小，这样可以最大限度的降低空间复杂度。 （4）源程序的大致的执行过程是怎样的？是否为空 是是是否有任务任务加入到等待打印队列否否是否有任务正在进行添加任务到工作进行区，准备打印是打印结束请清晰、准确、详细地回答上面的问题，要求标点符号正确无误，图表表示符合规范。你的报告应至少超出一页的文字描述，注意你描述的文字一定要叙述流畅，具有较好的逻辑性。六、附录（1） 如果你对这个实验还有其他的解决方案或设想，或对我们的实验方案有什么意见，请在此描述。用多线程模拟打印机，同时打印时可以用获取本地时间的方式来记下打印时间等，这样可以有效利用各种方面的条件。（2） 回答思考题a) 栈和队列在计算机系统中有哪些应用？写出你知道的系统中，这两种抽象数据类型的应用。 停车系统、内存调用数据或释放数据、铁路调度中用到栈、火车票订购用的是队列。b) 在程序调用的时侯，需要进行函数的切换，你认为函数在进行切换时系统要做那些工作？ 现将要切出来的函数和返回参数出栈，然后将不用的函数和返回参数压栈。（3）选作：查询以下内容的有关知识a)函数调用、返回时，系统对栈进行的操作。1、指令指针的地址加1，指向函数调用后的下一条指令。这个地址会被记入堆栈中，它将作为函数返回时的返回地址。2、在堆栈中给声明的返回值建立空间。3、当前堆栈的栈顶被记录下来并存储在一个叫做栈帧的特殊指针中，从记录开始到函数运行结束加入堆栈的所有数据都被视为函数的局部变量。4、