队列应用实验.pdf
实验八实验八队列的应用队列的应用一、实验目的1、掌握用 VC 工具上机调试队列的存储方式和基本操作;2、掌握队列的顺序存储结构；3、掌握队列先进先出运算原则在解决实际问题中的应用;二、实验学时2 学时三、实验类型验证型四、实验内容利用循环顺序队列打印杨辉三角形;打印的杨辉三角形如下所示：11 11211331146411510 10 511615 20 15 61五、实验原理1、循环队列概述循环队列是队列的顺序映像的实现,采用顺序存储结构存储队列,会产生假溢出现象,循环队列是解决假溢出的很好途径;若队列为空时队头指示器与队尾指示器同时指向某一存储单元,即此时两个指示器的数值相同,若队列非空,队头指示器指向队头元素下标,队尾指示器指向队尾元素的下一个位置的下标；队列由于在一端入队,在另一端出队,故而是一种先进先出的数据结构;杨辉三角的输出可用数组解决,通过二维数组来存储,二重循化来生成杨辉三角,但这样做显然掩盖了问题的本质;因为杨辉三角的输出具有先进先出的特点,第i行可由第i-1行来生成,那么第 i 行入队可借助于第 i-1 行出队,那么通过队列更易实现;2、杨辉三角程序的基本算法1SeueueInitiateQ；初始化循环队列 Q;2SeueueEmptyQ；判断循环队列 Q 非空否操作;3EnSeueueQ,x；循环队列入队操作,在队列 Q 的队尾插入数据元素 x;4DeSeueueQ,d；循环队列出队操作,把队列 Q 的队头元素删除并由参数d 带回;5GetHeadQ；取队列 Q 队头元素;6 YangHuiTriangle；生成且输出杨辉三角;3、模块层次图要求画出循环队列的模块层次图;如图所示main()SeqQueueInitiateSeqQueueEmptyEnSeqQueueDeSeqQueueGetHeadYangHuiTriangle图 15 杨辉三角程序模块层次图4、关键算法 NS 图六、实验步骤及要求用 VC 语言编程实现建立一个队列Q,借助于栈队列 Q 进行打印杨辉三角;1.队列 Q 初始化；2.输入杨辉三角规模的数值n；3.输出经过程序运行后的规模n 的杨辉三角；4.程序完成;七、运行结果图 16 杨辉三角程序运行图八、思考问题结合实验过程,回答下列问题：1、杨辉三角输出问题使用数组与队列有何区别时间复杂度与空间复杂度有何区别2、数组与队列来解决杨辉三角问题那种选择为最佳选择 为什么九、实验报告要求1、根据对队列的先进先出特点的理解,如何应用队列的基本操作；2、何时选用队列去解决实际问题；3、采用队列解决问题的特点;4、调试程序过程中遇到的问题及解决方案；5、本次实验的结论与体会;
