隊(duì)列應(yīng)用實(shí)驗(yàn)

1、實(shí)驗(yàn)八 隊(duì)列的應(yīng)用一、實(shí)驗(yàn)?zāi)康?、 掌握用vc工具上機(jī)調(diào)試隊(duì)列的存儲方式和基本操作。2、 掌握隊(duì)列的順序存儲結(jié)構(gòu)；3、 掌握隊(duì)列先進(jìn)先出運(yùn)算原則在解決實(shí)際問題中的應(yīng)用。二、實(shí)驗(yàn)學(xué)時(shí)2學(xué)時(shí)三、實(shí)驗(yàn)類型驗(yàn)證型四、實(shí)驗(yàn)內(nèi)容利用循環(huán)順序隊(duì)列打印楊輝三角形。打印的楊輝三角形如下所示：1111 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 1五、實(shí)驗(yàn)原理1、 循環(huán)隊(duì)列概述 循環(huán)隊(duì)列是隊(duì)列的順序映像的實(shí)現(xiàn)，采用順序存儲結(jié)構(gòu)存儲隊(duì)列，會(huì)產(chǎn)生假溢出現(xiàn)象，循環(huán)隊(duì)列是解決假溢出的很好途徑。若隊(duì)列為空時(shí)隊(duì)頭指示器與隊(duì)尾指示器同時(shí)指向某一存儲單元，即此時(shí)兩個(gè)指示器的數(shù)值相

2、同，若隊(duì)列非空，隊(duì)頭指示器指向隊(duì)頭元素下標(biāo)，隊(duì)尾指示器指向隊(duì)尾元素的下一個(gè)位置的下標(biāo)；隊(duì)列由于在一端入隊(duì)，在另一端出隊(duì)，故而是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。楊輝三角的輸出可用數(shù)組解決，通過二維數(shù)組來存儲，二重循化來生成楊輝三角，但這樣做顯然掩蓋了問題的本質(zhì)。因?yàn)闂钶x三角的輸出具有先進(jìn)先出的特點(diǎn)，第i行可由第i-1行來生成，那么第i行入隊(duì)可借助于第i-1行出隊(duì)，那么通過隊(duì)列更易實(shí)現(xiàn)。 2、楊輝三角程序的基本算法(1)seqqueueinitiate(q)； 初始化循環(huán)隊(duì)列q 。(2)seqqueueempty(q)； 判斷循環(huán)隊(duì)列q非空否操作 。(3)enseqqueue(q,x)； 循環(huán)隊(duì)列入隊(duì)操作

3、，在隊(duì)列q的隊(duì)尾插入數(shù)據(jù)元素x。 (4)deseqqueue(q,d)； 循環(huán)隊(duì)列出隊(duì)操作，把隊(duì)列q的隊(duì)頭元素刪除并由參數(shù)d帶回。(5)gethead(q)； 取隊(duì)列q隊(duì)頭元素。(6) yanghuitriangle ()； 生成且輸出楊輝三角。3、模塊層次圖要求畫出循環(huán)隊(duì)列的模塊層次圖。如圖所示圖15 楊輝三角程序模塊層次圖4、關(guān)鍵算法ns圖六、實(shí)驗(yàn)步驟及要求用vc語言編程實(shí)現(xiàn)建立一個(gè)隊(duì)列q，借助于棧隊(duì)列q進(jìn)行打印楊輝三角。1. 隊(duì)列q初始化；2. 輸入楊輝三角規(guī)模的數(shù)值n；3. 輸出經(jīng)過程序運(yùn)行后的規(guī)模n的楊輝三角；4. 程序完成。七、運(yùn)行結(jié)果圖16 楊輝三角程序運(yùn)行圖八、思考問題結(jié)合實(shí)驗(yàn)過程，回答下列問題：1、 楊輝三角輸出問題使用數(shù)組與隊(duì)列有何區(qū)別?時(shí)間復(fù)雜度與空間復(fù)雜度有何區(qū)別？2、 數(shù)組與隊(duì)列來解決楊輝三角問題那種選擇為最佳選擇？為什么？九、實(shí)驗(yàn)報(bào)告要求1、 根據(jù)對隊(duì)列的先進(jìn)先出特點(diǎn)的理解，如何應(yīng)用隊(duì)列的基本操作；2、 何時(shí)選用隊(duì)列去解決實(shí)