數(shù)據(jù)結(jié)構(gòu)-實(shí)驗(yàn)3 棧和隊(duì)列

第1頁(yè)共6頁(yè)實(shí)驗(yàn)（實(shí)訓(xùn)）報(bào)告項(xiàng)目名稱實(shí)驗(yàn)3棧和隊(duì)列所屬課程名稱數(shù)據(jù)結(jié)構(gòu)項(xiàng)目類型驗(yàn)證性實(shí)驗(yàn)(實(shí)訓(xùn))日期2013.10.班級(jí)學(xué)號(hào)姓名指導(dǎo)教師朱凌浙江財(cái)經(jīng)學(xué)院教務(wù)處制一、實(shí)驗(yàn)（實(shí)訓(xùn)）概述：【實(shí)驗(yàn)?zāi)康摹空莆諚５膬煞N存儲(chǔ)實(shí)現(xiàn)方法：順序棧和鏈?zhǔn)綏?；掌握STL棧的使用方法，能用棧求解問(wèn)題。掌握隊(duì)列的兩種存儲(chǔ)實(shí)現(xiàn)方法：順序隊(duì)列和鏈?zhǔn)疥?duì)列；掌握STL隊(duì)列的使用方法，能用隊(duì)列求解問(wèn)題?！緦?shí)驗(yàn)要求】新建文件夾，并命名為“學(xué)號(hào)姓名實(shí)驗(yàn)1數(shù)據(jù)結(jié)構(gòu)概論”，如“0901042001**×××實(shí)驗(yàn)1數(shù)據(jù)結(jié)構(gòu)概論”（**和×××部分用自己的學(xué)號(hào)和姓名替換），該文件夾用于存放實(shí)驗(yàn)程序和實(shí)驗(yàn)報(bào)告。實(shí)驗(yàn)報(bào)告完成后，請(qǐng)將該文件夾壓縮后提交，壓縮前請(qǐng)刪除各程序的debug目錄。認(rèn)真記錄實(shí)驗(yàn)過(guò)程及結(jié)果，認(rèn)真回答實(shí)驗(yàn)報(bào)告中的問(wèn)題。及時(shí)提交實(shí)驗(yàn)報(bào)告。【實(shí)施環(huán)境】（使用的材料、設(shè)備、軟件）VisualC++6.0注意：所有回答的內(nèi)容用紅色字體標(biāo)明?。?！二、實(shí)驗(yàn)（實(shí)訓(xùn)）內(nèi)容：實(shí)驗(yàn)任務(wù)一棧第1題回答以下問(wèn)題(1)在日常生活中，除課件中提到的例子（超市存放購(gòu)物車的軌道、折反型的火車站）外，還有哪些事物“處理數(shù)據(jù)”的方式是按照棧的方式進(jìn)行的?；卮穑?2)請(qǐng)根據(jù)你的理解，回答在什么情況下可以用棧來(lái)存儲(chǔ)數(shù)據(jù)？回答：(3)棧具有后進(jìn)先出（LIFO）的特性，是因?yàn)樗褂玫拇鎯?chǔ)結(jié)構(gòu)具有這樣的特性嗎？還是因?yàn)槠渌颍吭蛴质鞘裁?？回答：?題棧的應(yīng)用－計(jì)算表達(dá)式的值(1)請(qǐng)將下列中綴表達(dá)式轉(zhuǎn)換成等值的后綴表達(dá)式。(2+3)×(19-7)+(6–9)–66/375–23+(19–11)/(5–1)–15回答：(2)求解(1)中得到的后綴表達(dá)式，要求將求解過(guò)程列出來(lái)?；卮穑旱?題順序棧請(qǐng)寫出順序棧的實(shí)現(xiàn)的主要代碼，分別粘貼在下方。回答：第4題鏈?zhǔn)綏Ｕ?qǐng)寫出鏈?zhǔn)綏５膶?shí)現(xiàn)的主要代碼，分別粘貼在下方?；卮穑旱?題掌握STL棧stack的使用。(1)請(qǐng)寫出階乘函數(shù)的遞歸實(shí)現(xiàn)。（主要代碼粘貼在下方）回答：(2)請(qǐng)寫出階乘函數(shù)的迭代實(shí)現(xiàn)。（主要代碼粘貼在下方）回答：(2)請(qǐng)寫出階乘函數(shù)的非遞歸實(shí)現(xiàn)，要求使用STL棧stack，及其成員函數(shù)（主要代碼粘貼在下方）回答：第6題掌握STL棧stack的使用。請(qǐng)編寫一個(gè)程序，測(cè)試STL棧stack的使用，要求用到stack的成員函數(shù)。編寫一個(gè)代碼段，彈出棧中所有結(jié)點(diǎn)，用STL中的棧實(shí)現(xiàn)。stack<int>S;//假設(shè)棧里已經(jīng)有結(jié)點(diǎn)了請(qǐng)將代碼粘貼在下方。回答：實(shí)驗(yàn)任務(wù)二隊(duì)列第1題回答以下問(wèn)題(1)請(qǐng)根據(jù)你的理解，回答在什么情況下可以用隊(duì)列來(lái)存儲(chǔ)數(shù)據(jù)？回答：(2)本章介紹了四種線性表，分別是順序表、單鏈表、棧和隊(duì)列，請(qǐng)總結(jié)這四種線性表的特點(diǎn)（包括優(yōu)缺點(diǎn)、適用范圍）?；卮穑旱?題順序隊(duì)列請(qǐng)寫出順序隊(duì)列的實(shí)現(xiàn)的主要代碼，分別粘貼在下方?；卮穑旱?題鏈?zhǔn)疥?duì)列請(qǐng)寫出鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)的主要代碼，分別粘貼在下方?；卮穑旱?題掌握STL隊(duì)列queue的使用。請(qǐng)用STL的優(yōu)先級(jí)隊(duì)列模擬Windows操作系統(tǒng)的消息隊(duì)列。每個(gè)消息用一個(gè)字符串表示，為“Keyboard”、“Mouse”、“Timer”，分別表示鍵盤(注意有不同的鍵盤消息，所以不同的Keyboard消息優(yōu)先級(jí)允許不一樣)、鼠標(biāo)和定時(shí)器消息。每個(gè)消息有自己的優(yōu)先級(jí)，用整數(shù)表示，該值越大表示優(yōu)先級(jí)越高。輸入描述：首先是一個(gè)整數(shù)n，表示要處理消息的數(shù)目，接下來(lái)有2n行，每行可能為一個(gè)消息（格式為“消息名稱優(yōu)先級(jí)”），也可能為“Process”，后者表示處理一個(gè)消息(總是處理當(dāng)前優(yōu)先級(jí)高的消息)。輸入數(shù)據(jù)保證不會(huì)出現(xiàn)“在要處理消息時(shí)，優(yōu)先級(jí)隊(duì)列為空”的情形，也能保證在同一時(shí)刻，優(yōu)先級(jí)隊(duì)列中不存在兩個(gè)優(yōu)先級(jí)相同的消息。輸出描述：輸出依次處理的每個(gè)消息，格式如樣例輸出所示。樣例輸入/輸出如下。樣例輸入：8Keyboard12Mouse7ProcessTimer13Keyboard11Timer9ProcessProcessTimer16ProcessProcessKeyboard8Mouse24Proces