資源描述:
《數(shù)據(jù)結(jié)構(gòu) C語(yǔ)言版 教學(xué)課件 作者 嚴(yán)蔚敏 李冬梅 吳偉民 第3章 棧和隊(duì)列.ppt》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。
1、2021年10月8日北京林業(yè)大學(xué)信息學(xué)院李冬梅數(shù)據(jù)結(jié)構(gòu)2021年10月8日北京林業(yè)大學(xué)信息學(xué)院3.1棧3.2棧的應(yīng)用3.3棧與遞歸3.4隊(duì)列3.5隊(duì)列的應(yīng)用教學(xué)內(nèi)容2021年10月8日北京林業(yè)大學(xué)信息學(xué)院第3章棧和隊(duì)列掌握棧和隊(duì)列的特點(diǎn),并能在相應(yīng)的應(yīng)用問題中正確選用熟練掌握棧的兩種存儲(chǔ)結(jié)構(gòu)的基本操作實(shí)現(xiàn)算法,特別應(yīng)注意棧滿和??盏臈l件熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法,特別注意隊(duì)滿和隊(duì)空的條件理解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程教學(xué)目標(biāo)2021年10月8日北京林業(yè)大學(xué)信息學(xué)院棧(Stack)1.定義2.邏輯結(jié)構(gòu)3.存儲(chǔ)結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式隊(duì)列(Queue)1
2、.定義2.邏輯結(jié)構(gòu)3.存儲(chǔ)結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式2021年10月8日北京林業(yè)大學(xué)信息學(xué)院3.1棧1.定義用順序?;蜴湕4鎯?chǔ)均可,但以順序棧更常見3.存儲(chǔ)結(jié)構(gòu)與線性表相同,仍為一對(duì)一關(guān)系2.邏輯結(jié)構(gòu)只能在表的一端(棧頂)進(jìn)行插入和刪除運(yùn)算的線性表2021年10月8日北京林業(yè)大學(xué)信息學(xué)院只能在棧頂運(yùn)算,且訪問結(jié)點(diǎn)時(shí)依照后進(jìn)先出(LIFO)或先進(jìn)后出(FILO)的原則4.運(yùn)算規(guī)則關(guān)鍵是編寫入棧和出棧函數(shù),具體實(shí)現(xiàn)依順序棧或鏈棧的不同而不同基本操作有入棧、出棧、讀棧頂元素值、建棧、判斷棧滿、??盏?.實(shí)現(xiàn)方式2021年10月8日北京林業(yè)大學(xué)信息學(xué)院棧是一種特殊的線性表,它只能在表
3、的一端(棧頂)進(jìn)行插入和刪除運(yùn)算棧與一般線性表的區(qū)別:僅在于運(yùn)算規(guī)則不同“進(jìn)”=壓入=PUSH()“出”=彈出=POP()一般線性表邏輯結(jié)構(gòu):一對(duì)一存儲(chǔ)結(jié)構(gòu):順序表、鏈表運(yùn)算規(guī)則:隨機(jī)、順序存取棧邏輯結(jié)構(gòu):一對(duì)一存儲(chǔ)結(jié)構(gòu):順序棧、鏈棧運(yùn)算規(guī)則:后進(jìn)先出棧與一般線性表的區(qū)別2021年10月8日北京林業(yè)大學(xué)信息學(xué)院“進(jìn)”=壓入=PUSH()“出”=彈出=POP()2021年10月8日北京林業(yè)大學(xué)信息學(xué)院a1a2……an順序棧Sai……表頭表尾棧底base棧頂top低地址高地址寫入:v[i]=ai讀出:x=v[i]壓入:PUSH(an+1)彈出:POP(x)前提:一定要預(yù)設(shè)棧頂指針t
4、op!低地址高地址v[i]a1a2aian……順序表V[n]……an+1順序棧與順序表2021年10月8日北京林業(yè)大學(xué)信息學(xué)院順序棧的表示空棧base==top是??諛?biāo)志stacksize=4topAbasebasetopABABCtopbasetopbaseABCDbasetop3120top指示真正的棧頂元素之上的下標(biāo)地址棧滿時(shí)的處理方法:1、報(bào)錯(cuò),返回操作系統(tǒng)。2、分配更大的空間,作為棧的存儲(chǔ)空間,將原棧的內(nèi)容移入新棧。2021年10月8日北京林業(yè)大學(xué)信息學(xué)院#defineMAXSIZE100typedefstruct{SElemType*base;SElemType*t
5、op;intstacksize;}SqStack;順序棧的表示2021年10月8日北京林業(yè)大學(xué)信息學(xué)院構(gòu)造一個(gè)空棧步驟:(1)分配空間并檢查空間是否分配失敗,若失敗則返回錯(cuò)誤順序棧初始化basestacksizetops(2)設(shè)置棧底和棧頂指針S.top=S.base;(3)設(shè)置棧大小2021年10月8日北京林業(yè)大學(xué)信息學(xué)院StatusInitStack(SqStack&S){S.base=newSElemType[MAXSIZE];if(!S.base)returnOVERFLOW;S.top=S.base;S.stackSize=MAXSIZE;returnOK;}順序棧初
6、始化2021年10月8日北京林業(yè)大學(xué)信息學(xué)院判斷順序棧是否為空boolStackEmpty(SqStackS){if(S.top==S.base)returntrue;elsereturnfalse;}basetop31202021年10月8日北京林業(yè)大學(xué)信息學(xué)院求順序棧的長(zhǎng)度intStackLength(SqStackS){returnS.top–S.base;}basetopAB2021年10月8日北京林業(yè)大學(xué)信息學(xué)院StatusClearStack(SqStackS){if(S.base)S.top=S.base;returnOK;}清空順序棧basetop3120202
7、1年10月8日北京林業(yè)大學(xué)信息學(xué)院StatusDestroyStack(SqStack&S){if(S.base){deleteS.base;S.stacksize=0;S.base=S.top=NULL;}returnOK;}銷毀順序棧2021年10月8日北京林業(yè)大學(xué)信息學(xué)院(1)判斷是否棧滿,若滿則出錯(cuò)(2)元素e壓入棧頂(3)棧頂指針加1順序棧進(jìn)棧StatusPush(SqStack&S,SElemTypee){if(S.top-S.base==S.stacksize)//棧滿retu