資源描述：
《棧和隊(duì)列課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第三章棧和隊(duì)列3.1棧3.2棧的應(yīng)用舉例3.3遞歸3.4隊(duì)列3.5隊(duì)列應(yīng)用舉例【教學(xué)目的】掌握特殊的線性表?xiàng)C與隊(duì)列的工作原理，桟與隊(duì)列的順序、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下操作的實(shí)現(xiàn)，理解計(jì)算機(jī)系統(tǒng)中桟和隊(duì)列的重要作用和應(yīng)用【教學(xué)重點(diǎn)】桟與隊(duì)列的工作原理及其操作實(shí)現(xiàn)【教學(xué)難點(diǎn)】入棧和出棧時(shí)的?？蘸蜅M，進(jìn)棧和出棧時(shí)棧頂指針修改的先后順序，理解多棧，應(yīng)用棧和利用棧來理解遞歸，處理循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿的確定，隊(duì)列應(yīng)用。3.1棧一棧的定義及基本操作棧：限定僅在表的一端進(jìn)行插入和刪除操作的線性表?xiàng)ｍ敚涸试S進(jìn)行插入和刪除的一端棧底：不允許進(jìn)行插入和刪除的一端空棧：不含元素的空表入/壓/進(jìn)棧：棧的插入操作退/出棧：棧的刪
2、除操作例：棧s=(a1,a2,a3……an)即：元素按a1……an順序依次進(jìn)棧，則第一個(gè)出棧的元素？棧的特點(diǎn):先進(jìn)后出/后進(jìn)先出（FirstInLastOut）又稱為FILO/LIFO線性表ADTStack{數(shù)據(jù)對(duì)象：D＝{ai
3、ai∈ElemSet,i=1,2,...,n,n≥0}數(shù)據(jù)關(guān)系：R1＝{
4、ai-1,ai∈D,i=2,...,n}約定an端為棧頂，a1端為棧底。基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧S。DestroyStack(&S)初始條件：棧S已存在。操作結(jié)果：棧S被銷毀。ClearStack(&S)初始條件：棧S已存在。操作結(jié)果：將S清為
5、空棧。StackEmpty(S)初始條件：棧S已存在。操作結(jié)果：若棧S為空棧，則返回TRUE，否則FALE。StackLength(S)初始條件：棧S已存在。操作結(jié)果：返回S的元素個(gè)數(shù)，即棧的長度。GetTop(S,&e)初始條件：棧S已存在且非空。操作結(jié)果：用e返回S的棧頂元素。Pop(&S,&e)初始條件：棧S已存在且非空。操作結(jié)果：刪除S的棧頂元素，并用e返回其值。Push(&S,e)初始條件：棧S已存在。操作結(jié)果：插入元素e為新的棧頂元素。StackTraverse(S,visit())初始條件：棧S已存在且非空，visit()為元素的訪問函數(shù)。操作結(jié)果：從棧底到棧頂依次對(duì)S的每個(gè)元素
6、調(diào)用函數(shù)visit()，一旦visit()失敗，則操作失敗。}ADTStack棧結(jié)構(gòu)的基本操作：1、棧初始化：Init_Stack(S)初始條件：棧S不存在操作結(jié)果：構(gòu)造了一個(gè)空棧。2、銷毀棧：Destroy_Stack(S)初始條件：棧S已存在操作結(jié)果：銷毀一個(gè)已存在的棧。3、判?？眨篍mpty_Stack(S)操作結(jié)果：若S為空棧返回為1，否則返回為0。4、入棧：Push_Stack(S，x)初始條件：棧S已存在操作結(jié)果：在棧s的頂部插入一個(gè)新元素x，x成為新的棧頂元素。棧發(fā)生變化5、出棧：Pop_Stack(S)初始條件：棧S存在且非空操作結(jié)果：棧S的頂部元素從棧中刪除，棧中少了一個(gè)元素
7、。棧發(fā)生變化6、取棧頂元素：GetTop_Stack(S)初始條件：棧S存在且非空操作結(jié)果：棧頂元素作為結(jié)果返回，棧不變化二、棧的順序存儲(chǔ)及操作的實(shí)現(xiàn)用一組連續(xù)的存儲(chǔ)單元依次存放棧中的每個(gè)數(shù)據(jù)元素，并用起始端作為棧底。（順序棧）類型定義如下所示：#defineMAXSIZE100typedefstruct{DataTypedata[MAXSIZE];inttop;}SeqStack,*PSeqStack;1、初始化棧：PSeqStackInit_SeqStack(void){//創(chuàng)建一順序棧，入口參數(shù)無，返回一個(gè)指向順序棧的指針，為零表示分配空間失敗PSeqStackS;S=(PSeqStac
8、k)malloc(sizeof(SeqStack));if(S)S->top=-1;returnS;}2、銷毀棧：順序棧的銷毀操作是初始化操作的逆運(yùn)算。由于要修改棧的指針變量，所以要將指針地址傳給該函數(shù)。voidDestroy_SeqStack(PSeqStack*S){//銷毀順序棧，入口參數(shù)：為要銷毀的順序棧指針地址if(*S)free(*S);*S=NULL;//return;}主程序中如何調(diào)用main(){PSeqStackS;S=Init_SeqStack();……Destroy_SeqStack(&S);}3、判?？眨号袛鄺Ｖ惺欠裼性兀恍枧袛鄑op是否等于-1intEmpty_
9、SeqStack(PSeqStackS){//判斷棧是否為空，入口參數(shù)：順序棧，返回值：1表示為空，0表示非空if(S->top==-1)return1;elsereturn0;}清空：s->top=-1求棧的長度：s->top+14、入棧入棧操作是在棧的頂部進(jìn)行插入一個(gè)元素。首先判斷棧是否已滿，若滿退出，否則，由于棧的top指向棧頂，只要將入棧元素賦到top+1的位置同時(shí)top++即可intPu
