C_char_3棧與隊列

1,第三章棧和隊列3.1棧3.2棧的應(yīng)用舉例3.3棧與遞歸的實現(xiàn)3.4隊列3.5離散事件模擬,線性表棧隊列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1in+1Delete(L,i)Delete(S,n)Delete(Q,1)1in,棧和隊列都屬于線性結(jié)構(gòu),但是是操作受到限制的線性結(jié)構(gòu)。它們的操作集合是線性表操作集合的子集。棧和隊列在程序設(shè)計中被廣泛應(yīng)用，是兩種重要的結(jié)構(gòu)類型。,2,第三章棧和隊列3.1棧1.棧的邏輯結(jié)構(gòu)棧：是限定僅在表尾進(jìn)行插入或刪除操作的線性表棧頂：表尾端（允許插入和刪除操作的一端）稱為棧頂棧底：表頭端稱為棧底。棧的操作特性：后進(jìn)先出（LIFO）,3,3.1棧1.抽象數(shù)據(jù)類型棧的定義,ADTStack數(shù)據(jù)對象：Dai|aiElemSet,i=1,2,.,n,n0數(shù)據(jù)關(guān)系：R1|ai-1,aiD,i=2,.,n約定an端為棧頂，a1端為棧底。,基本操作：,ADTStack,NOTE:下面的基本操作,無論是定義成函數(shù)還是過程,都只是一種形式定義，其實現(xiàn)依賴于棧所采用的存儲結(jié)構(gòu)。,4,2.棧的基本操作InitStack(/棧存儲空間初始分配量#defineSTACKINCREMENT10;/棧存儲空間分配增量typedefstructSElemType*base;/構(gòu)造之前和銷毀之后base=NULLSElemType*top;/棧頂指針intstacksize;/當(dāng)前已分配的存儲空間，以元素為單位。SqStack;,6,下面是順序存儲結(jié)構(gòu)的棧的基本操作的實現(xiàn):1).InitStack(,7,2).GetTop(S,8,3).Push(/Push,9,4).Pop(/Pop,10,4.棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)的棧在高級語言中可以描述成單鏈表.把單鏈表作為棧使用時,把鏈表的表頭位置作為棧的棧頂,并且不設(shè)頭結(jié)點(diǎn).其結(jié)構(gòu)描述如下:,typedefstructLNodeElemTypedata;/數(shù)據(jù)域structLnode*next;/指針域LNode,*LinkList;typedefLinkListLstack,下面是鏈棧操作示意圖:,下面是鏈棧基本操作的實現(xiàn):,11,1).InitStack(,12,3).Push(/Push,13,4).Pop(/Pop,14,3.2棧的應(yīng)用舉例,例一、數(shù)制轉(zhuǎn)換,算法基本原理：N=(Ndivd)d+Nmodd,例如：（1348)10=(2504)8，其運(yùn)算過程如下：NNdiv8Nmod8134816841682102125202,計算順序,輸出順序,15,voidconversion()InitStack(S);scanf(%d,N);while(N)Push(S,N%8);N=N/8;while(!StackEmpty(S)Pop(S,e);printf(%d,e);/conversion,16,例二、括號匹配的檢驗假設(shè)在表達(dá)式中（）或（）等為正確的格式，（）或（）或()均為不正確的格式。,則檢驗括號是否匹配的方法可用“期待的急迫程度”這個概念來描述。,分析可能出現(xiàn)的不匹配的情況:,到來的右括弧非是所“期待”的;,例如：考慮下列括號序列：()12345678,到來的是“不速之客”;,直到結(jié)束，也沒有到來所“期待”的括弧;,17,算法的設(shè)計思想：,1）凡出現(xiàn)左括弧，則進(jìn)棧；,2）凡出現(xiàn)右括弧，首先檢查棧是否空若?？?，則表明該“右括弧”多余否則和棧頂元素比較，若相匹配，則“左括弧出?！狈駝t表明不匹配,3）表達(dá)式檢驗結(jié)束時，若棧空，則表明表達(dá)式中匹配正確否則表明“左括弧”有余,18,例2：假設(shè)算術(shù)表達(dá)式中可包括三種括號，(),可按任意次序嵌套使用，判別給定表達(dá)式中所含括號是否是配對出現(xiàn)的算法。Statusmatch()InitStack(S);while(c=getchar()!=n)if(In(c,”(”)Push(S,c);elseif(In(c,“)”)if(StackEmpty(S)return(ERROR);elsePop(S,a);if(!comp(a,c)return(ERROR);if(!StackEmpty(S)return(ERROR);elsereturn(OK);/match;,19,例三：表達(dá)式求值表達(dá)式求值是程序設(shè)計語言的編譯程序中的一個最基本的問題.表達(dá)式求值有多種方法,利用棧對表達(dá)式求值是其中的一種,也是棧應(yīng)用的一個典型例子.例：表達(dá)式：4+5*4/(2+5);下面介紹的算符優(yōu)先法,就是利用棧結(jié)構(gòu)來對表達(dá)式求值.其步驟如下:1.確定算符運(yùn)算的優(yōu)先順序,即算符的優(yōu)先級這里假設(shè)只處理下面這些運(yùn)算符:+-*/()一般地,假設(shè)表達(dá)式以界限符開始和結(jié)束:#,在運(yùn)算的每一步，任意兩個相繼出現(xiàn)的運(yùn)算符1和2之間的關(guān)系只有以下三種。121212把運(yùn)算符和界限符一起稱算符,確定算符的優(yōu)先級如下:,3*(3+4)+56+4-3*25+6/3-4*2,20,2.按照確定的優(yōu)先級,計算特定表達(dá)式的值.計算方法如下:設(shè)定操作數(shù)棧OPND和運(yùn)算符棧OPTR,OPND初始化為空,OPTR初始化為只包含起始符#自左至右,依次讀入表達(dá)式中每個單詞,若為操作數(shù)則進(jìn)OPND棧,若為運(yùn)算符,則轉(zhuǎn)向比較當(dāng)前讀入的運(yùn)算符(2)和OPTR棧頂運(yùn)算符(1)的優(yōu)先級21:棧頂元素優(yōu)先級低,則將當(dāng)前讀入的運(yùn)算符進(jìn)OPTR棧,然后轉(zhuǎn)向,21,表達(dá)式計算示例(3*(34-28)+7)/5-3對表達(dá)式加上起始符和結(jié)束符:#(3*(34-28)+7)/5-3#,步驟OPNDOPTR當(dāng)前讀入的單詞w操作,初始化#(進(jìn)OPTR棧1#(33進(jìn)OPND棧23#(*進(jìn)OPTR棧33#(*(（進(jìn)OPTR棧43#(*(3434進(jìn)OPND棧5334#(*(-進(jìn)OPTR棧6334#(*(-2828進(jìn)OPND棧733428#(*(-)34和28出棧,-出棧34-28=6進(jìn)OPND棧836#(*()脫括弧936#(*+3和6出棧*出棧3*6=18進(jìn)OPND棧1018#(+進(jìn)OPTR棧,1118#(+77進(jìn)OPND棧,12187#(+)18和7出棧+出棧18+7=25進(jìn)OPND棧1325#()脫括弧1425#/進(jìn)OPTR棧1525#/55進(jìn)OPND棧16255#/-25和5出棧/出棧25/5=5進(jìn)OPND棧175#-進(jìn)OPTR棧185#-33進(jìn)OPND棧1953#-#5和3出棧-出棧5-3=2進(jìn)OPND棧202#運(yùn)算結(jié)束,22,OperandTypeEvaluateExpression()/算法表達(dá)式求值的算符優(yōu)先算法；設(shè)OPTR,OPND為運(yùn)算符棧/和操作數(shù)棧，OP為運(yùn)算符的集合InitStack(OPTR);Push(OPTR,“#”);InitStack(OPND);c=getitem();while(c!=#|GetTop(OPTR)!=#)if(!In(c,OP)Push(OPND,c);c=getitem();/不是運(yùn)算符則進(jìn)棧elseswitch(precede(GetTop(OPTR),c)case:/退棧并將運(yùn)算結(jié)果入棧Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,operate(a,theta,b);break;/switch/whilereturn(GetTop(OPND)/EvaluateExpression,23,3.3棧與遞歸的實現(xiàn),將所有的實在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存;為被調(diào)用函數(shù)的局部變量分配存儲區(qū);將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。,當(dāng)在一個函數(shù)的運(yùn)行期間調(diào)用另一個函數(shù)時，在運(yùn)行該被調(diào)用函數(shù)之前，需先完成三項任務(wù)：,保存被調(diào)函數(shù)的計算結(jié)果;釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū);依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。,從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成下列三項任務(wù)：,24,多個函數(shù)嵌套調(diào)用的規(guī)則是:,此時的內(nèi)存管理實行“棧式管理”,后調(diào)用先返回！,例如：voidmain()voida()voidb()a();b();/main/a/b,Main的數(shù)據(jù)區(qū),函數(shù)a的數(shù)據(jù)區(qū),函數(shù)b的數(shù)據(jù)區(qū),25,遞歸工作棧：遞歸執(zhí)行過程中占用的數(shù)據(jù)區(qū)。遞歸工作記錄：每一層的遞歸參數(shù)合成一個記錄。當(dāng)前活動記錄：棧頂記錄指示當(dāng)前層的執(zhí)行情況。當(dāng)前環(huán)境指針：遞歸工作棧的棧頂指針。,遞歸函數(shù)執(zhí)行的過程可視為同一函數(shù)進(jìn)行嵌套調(diào)用，例如：,26,voidhanoi(intn,charx,chary,charz)/將塔座x上按直徑由小到大且至上而下的1至n/個圓盤按規(guī)則搬到塔座z上，y可用作輔助塔座。12if(n=1)3move(x,1,z);/將個圓盤從x移到z4else5hanoi(n-1,x,z,y);/將x上至n-1個/圓盤移到y(tǒng),z作輔助塔6move(x,n,z);/將第n個圓盤從x移到z7hanoi(n-1,y,x,z);/將y上至n-1個/圓盤移到z,x作輔助塔89,函數(shù)的執(zhí)行過程與遞歸工作棧,27,3.4隊列隊列的邏輯結(jié)構(gòu)隊列:是限定僅在表的一端進(jìn)行插入,而在另一端進(jìn)行刪除的線性表.隊頭:允許刪除的一端稱為隊頭隊尾:允許插入的一端稱為隊尾隊列的操作特性:先進(jìn)先出(FIFO),3.4.1抽象數(shù)據(jù)類型隊列的定義ADTQueue數(shù)據(jù)對象：Dai|aiElemSet,i=1,2,.,n,n0數(shù)據(jù)關(guān)系：R1|ai-1,aiD,i=2,.,n約定其中a1端為隊列頭，an端為隊列尾基本操作：ADTQueue,28,隊列的基本操作：,InitQueue(structQNode*next;QNode,*QueuePtr;,typedefstruct/鏈隊列類型QueuePtrfront;/隊頭指針QueuePtrrear;/隊尾指針LinkQueue;,空隊列,31,下面是鏈?zhǔn)酱鎯Y(jié)構(gòu)的隊列的基本操作的實現(xiàn):1)InitQueue(,32,StatusEnQueue(LinkQueue,33,StatusDeQueue(LinkQueue,if(Q.rear=p)Q.rear=Q.front;,34,3.4.3循環(huán)隊列隊列的順序表示與實現(xiàn),隊列的順序存儲結(jié)構(gòu)中，需要附設(shè)兩個指針front和rear分別指向隊列的頭與隊列的尾，為了在C語言中描述方便，初始化建立隊列時，令front=rear=0;每當(dāng)插入新元素時，尾指針增1，每當(dāng)刪除隊列頭元素時，頭指針增1，因此，隊列頭指針始終指向隊列頭元素，而隊列尾指針始終指向隊列尾元素的下一個位置。,隊列的順序存儲實現(xiàn)存在假溢出現(xiàn)象。,35,所謂循環(huán)隊列,即仍然用一維數(shù)組來描述順序存儲結(jié)構(gòu)的隊列.只不過假設(shè)把數(shù)組的第一個單元看作是最后一個單元的后繼,使數(shù)組首尾相接.下面是循環(huán)隊列的操作示意圖:,順序存儲結(jié)構(gòu)的隊列存在假溢出問題,可用循環(huán)隊列來解決.,A,B,C,為了能夠簡單地區(qū)分隊列滿和空的兩種狀態(tài),當(dāng)隊列中仍存在一個空單元時,認(rèn)為隊列已處于滿狀態(tài).,3.4.3循環(huán)隊列隊列的順序表示與實現(xiàn),36,下面是循環(huán)隊列的結(jié)構(gòu)描述:#defineMAXQSIZE100/最大隊列長度typedefstructQElemType*base;/初始化的動態(tài)分配存儲空間intfront;/頭指針，若隊列不空，指向隊列頭元素intrear;/尾指針,若隊列不空,指向隊列尾元素的下一個位置SqQueu