队列应用实验.doc

《队列应用实验.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验八队列的应用一、实验目的1、掌握用VC工具上机调试队列的存储方式和基本操作。2、掌握队列的顺序存储结构；3、掌握队列先进先出运算原则在解决实际问题中的应用。二、实验学时2学时三、实验类型验证型四、实验内容利用循环顺序队列打印杨辉三角形。打印的杨辉三角形如下所示：11   11  2  11  3  3  11  4  6  4  11  5  10 10 5  11  6  15 20 15 6  1……五、实验原理1、循环队列概述循环队列是队列的顺序映像的实现，采用顺序存储结构存储队列，会产生假溢出现象，循环队列是解决假溢出的很好途径

2、。若队列为空时队头指示器与队尾指示器同时指向某一存储单元，即此时两个指示器的数值相同，若队列非空，队头指示器指向队头元素下标，队尾指示器指向队尾元素的下一个位置的下标；队列由于在一端入队，在另一端出队，故而是一种先进先出的数据结构。杨辉三角的输出可用数组解决，通过二维数组来存储，二重循化来生成杨辉三角，但这样做显然掩盖了问题的本质。因为杨辉三角的输出具有先进先出的特点，第i行可由第i-1行来生成，那么第i行入队可借助于第i-1行出队，那么通过队列更易实现。2、杨辉三角程序的基本算法(1)SeqQueueInitiate(Q)；初始化循环队列

3、Q。(2)SeqQueueEmpty(Q)；判断循环队列Q非空否操作。(3)EnSeqQueue(Q,x)；循环队列入队操作，在队列Q的队尾插入数据元素x。(4)DeSeqQueue(Q,d)；循环队列出队操作，把队列Q的队头元素删除并由参数d带回。(5)GetHead(Q)；取队列Q队头元素。(6)YangHuiTriangle()；生成且输出杨辉三角。3、模块层次图要求画出循环队列的模块层次图。如图所示图15杨辉三角程序模块层次图4、关键算法NS图六、实验步骤及要求用VC语言编程实现建立一个队列Q，借助于栈队列Q进行打印杨辉三角。1.队

4、列Q初始化；2.输入杨辉三角规模的数值n；3.输出经过程序运行后的规模n的杨辉三角；4.程序完成。七、运行结果图16杨辉三角程序运行图八、思考问题结合实验过程，回答下列问题：1、杨辉三角输出问题使用数组与队列有何区别?时间复杂度与空间复杂度有何区别？2、数组与队列来解决杨辉三角问题那种选择为最佳选择？为什么？九、实验报告要求1、根据对队列的先进先出特点的理解，如何应用队列的基本操作；1、何时选用队列去解决实际问题；2、采用队列解决问题的特点;3、调试程序过程中遇到的问题及解决方案；4、本次实验的结论与体会。