隊列應(yīng)用實驗

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

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

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