队列应用实验.doc

精品文档，仅供学习与交流，如有侵权请联系网站删除实验八 队列的应用一、实验目的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、 循环队列概述 循环队列是队列的顺序映像的实现，采用顺序存储结构存储队列，会产生假溢出现象，循环队列是解决假溢出的很好途径若队列为空时队头指示器与队尾指示器同时指向某一存储单元，即此时两个指示器的数值相同，若队列非空，队头指示器指向队头元素下标，队尾指示器指向队尾元素的下一个位置的下标；队列由于在一端入队，在另一端出队，故而是一种先进先出的数据结构杨辉三角的输出可用数组解决，通过二维数组来存储，二重循化来生成杨辉三角，但这样做显然掩盖了问题的本质因为杨辉三角的输出具有先进先出的特点，第i行可由第i-1行来生成，那么第i行入队可借助于第i-1行出队，那么通过队列更易实现。

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