棧和隊(duì)列市公開(kāi)課一等獎(jiǎng)省賽課獲獎(jiǎng)?wù)n件

第三章棧和隊(duì)列3.1棧3.2棧應(yīng)用3.3棧與遞歸實(shí)現(xiàn)3.4隊(duì)列

棧和隊(duì)列第1頁(yè)3.1棧棧和隊(duì)列是特殊線性表，其基本操作是線性表操作子集，是操作受限線性表。3.1.1抽象數(shù)據(jù)結(jié)構(gòu)類(lèi)型棧定義棧（stack）是限定在表尾進(jìn)行插入或刪除操作線性表。插入元素叫入棧，刪除元素叫出棧。表尾稱(chēng)為棧頂（top），表頭稱(chēng)為棧底（bottom）。不含元素空表稱(chēng)為空棧。例：棧S=(a1,a2,….,an)，a1為棧底元素，an為棧頂元素。棧操作是后進(jìn)先出（LIFO）。棧和隊(duì)列第2頁(yè)棧和隊(duì)列第3頁(yè)棧抽象類(lèi)型定義棧和隊(duì)列第4頁(yè)3.1.2棧表示和實(shí)現(xiàn)棧存放表示兩種方法：

1、次序棧（棧次序存放結(jié)構(gòu)）：利用一組地址連續(xù)存放單元依次存放自棧底到棧頂數(shù)據(jù)元素。

Top=0表示空棧。

在初始化空棧時(shí)不應(yīng)該限定棧最大空間，應(yīng)該先為棧分配一個(gè)基本容量，然后在應(yīng)用過(guò)程中，當(dāng)棧空間不夠使用時(shí)再逐段擴(kuò)大。

兩個(gè)常量：

STACK_INIT_SIZE:存放空間初始分配量；

STACKINCREMENT:存放空間分配增量。棧和隊(duì)列第5頁(yè)次序棧定義：說(shuō)明：1）stacksize指示棧當(dāng)前可使用最大容量。2）棧初始化操作為：按設(shè)定初始分配量進(jìn)行第一次存放分配，base是棧底指針，一直指向棧底位置，若base=NULL，表明棧結(jié)構(gòu)不存在。3）Top為棧頂指針，初始值指向棧底，即top=base表明空棧；插入元素top+1，刪除元素top-1，非空棧中棧頂指針一直在棧頂元素下一個(gè)位置。top-base=stacksize表明棧滿棧和隊(duì)列第6頁(yè)棧和隊(duì)列第7頁(yè)棧和隊(duì)列第8頁(yè)棧和隊(duì)列第9頁(yè)棧和隊(duì)列第10頁(yè)棧和隊(duì)列第11頁(yè)2、棧鏈?zhǔn)奖硎緱２僮魇蔷€性表操作特例，故鏈棧操作易于實(shí)現(xiàn)棧和隊(duì)列第12頁(yè)3.2棧應(yīng)用舉例3.2.1數(shù)制轉(zhuǎn)換十進(jìn)制數(shù)N和其它d進(jìn)制數(shù)轉(zhuǎn)換N=(Ndivd)×d+Nmodd(其中：div為整除運(yùn)算，mod為求余運(yùn)算）比如：（1348)10=(2504)8，其運(yùn)算過(guò)程以下：N

Ndiv8

Nmod81348

168

4

168

21

0

21

2

5

2

0

2棧和隊(duì)列第13頁(yè)voidconversion(intNum){//對(duì)于輸入任意一個(gè)非負(fù)十進(jìn)制整數(shù)，打印輸出與其等值八進(jìn)制數(shù)ElemTypee;SqStackS;InitStack(S);//結(jié)構(gòu)空棧while(Num){Push(S,Num%8);Num=Num/8;}while(!StackEmpty(S)){Pop(S,e);printf("%d",e);}printf("\n");}//conversion棧和隊(duì)列第14頁(yè)3.2.2括號(hào)匹配檢驗(yàn)假設(shè)表示式中允許包含兩種括號(hào)：圓括號(hào)和方括號(hào)，其嵌套次序隨意，即（［］（））或［（［］［］）］等為正確格式，［（］）或（［（））或(()])均為不正確格式。檢驗(yàn)括號(hào)是否匹配方法可用"期待緊迫程度"這個(gè)概念來(lái)描述。比如考慮以下括號(hào)序列：[([][])]12345678

分析可能出現(xiàn)不匹配情況:到來(lái)右括弧非是所“期待”;到來(lái)是“不速之客”;直到結(jié)束，也沒(méi)有到來(lái)所“期待”。

棧和隊(duì)列第15頁(yè)statusmatching(string&exp){//檢驗(yàn)表示式中所含括弧是否正確嵌套，是，返回OK，不然返回ERROR

intstate=1; while(i<=length(exp)&&state){ swithofexp[i]{ case左括弧:{Push(S,exp[i]);i++;break;} case右括弧: {if(NOTStackEmpty(S)&&GetTop(S)=左括號(hào)) {Pop(S,e);i++;}else{state=0} break; } ……} } if(state&&StackEmpty(S))returnOK elsereturnERROR;}棧和隊(duì)列第16頁(yè)3.2.3行編輯程序一個(gè)簡(jiǎn)單行編輯程序功效是：接收用戶從終端輸入程序或數(shù)據(jù)，并存入用戶數(shù)據(jù)區(qū)。每接收一個(gè)字符即存入用戶數(shù)據(jù)區(qū)”不恰當(dāng)。很好做法是，設(shè)置一個(gè)輸入緩沖區(qū)，用以接收用戶輸入一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)。允許用戶輸入出差錯(cuò)，并在發(fā)覺(jué)有誤時(shí)能夠及時(shí)更正。whli##ilr#e（s#*s)outcha@putchar(*s=#++);則實(shí)際有效是以下兩行：while(*s)putchar(*s++);棧和隊(duì)列第17頁(yè)voidLineEdit(){//利用字符棧S，從終端接收一行并傳送至調(diào)用過(guò)程數(shù)據(jù)區(qū)。charch,*temp;SqStackS;InitStack(S);//結(jié)構(gòu)空棧Sprintf("請(qǐng)輸入一行(#:退格；@:清行):\n");ch=getchar();//從終端接收第一個(gè)字符while(ch!=EOF){//EOF為全文結(jié)束符while(ch!=EOF&&ch!='\n'){switch(ch){case'#':Pop(S,ch);break;//僅當(dāng)棧非空時(shí)退棧case'@':ClearStack(S);break;//重置S為空棧default:Push(S,ch);break;//有效字符進(jìn)棧,未考慮棧滿情形}

棧和隊(duì)列第18頁(yè)ch=getchar();//從終端接收下一個(gè)字符} temp=S.base;while(temp!=S.top){printf("%c",*temp); ++temp;} //將從棧底到棧頂棧內(nèi)字符傳送至調(diào)用過(guò)程數(shù)據(jù)區(qū)；ClearStack(S);//重置S為空棧printf("\n");if(ch!=EOF){printf("請(qǐng)輸入一行(#:退格；@:清行):\n");ch=getchar();}}DestroyStack(S);}棧和隊(duì)列第19頁(yè)3.2.5表示式求值限于二元運(yùn)算符表示式定義:表示式::=(操作數(shù))+(運(yùn)算符)+(操作數(shù))操作數(shù)::=簡(jiǎn)單變量|表示式簡(jiǎn)單變量::=標(biāo)識(shí)符|無(wú)符號(hào)整數(shù)在計(jì)算機(jī)中，表示式能夠有三種不一樣標(biāo)識(shí)方法設(shè)Exp=S1+OP+S2則稱(chēng)OP+S1+S2為表示式前綴表示法稱(chēng)S1+OP+S2為表示式中綴表示法稱(chēng)S1+S2+OP為表示式后綴表示法可見(jiàn)，它以運(yùn)算符所在不一樣位置命名。棧和隊(duì)列第20頁(yè)棧和隊(duì)列第21頁(yè)3.3棧與遞歸實(shí)現(xiàn)棧遞歸調(diào)用：直接調(diào)用自己或經(jīng)過(guò)一系列調(diào)用語(yǔ)句間接調(diào)用自己函數(shù)叫遞歸函數(shù)。經(jīng)過(guò)棧能夠?qū)崿F(xiàn)非遞歸。遞歸調(diào)用數(shù)學(xué)函數(shù)：階乘函數(shù)1n=0Fact(n)=n.Fact(n-1)n>0Fibonacci數(shù)列0n=0Fib(n)=1n=1Fib(n-1)+Fib(n-2)其它情況棧和隊(duì)列第22頁(yè)例：(n階Hanoi塔問(wèn)題)要求：將X軸上n個(gè)圓盤(pán)移動(dòng)到Z上。

遵照標(biāo)準(zhǔn)：

1)每次只能移動(dòng)一個(gè)圓盤(pán)；

2)圓盤(pán)能夠插在X、Y、Z中任一塔座上；

3)任何時(shí)刻都不能將一個(gè)較大圓盤(pán)壓在較小圓盤(pán)之上。棧和隊(duì)列第23頁(yè)分析：n=1時(shí)，將編號(hào)為1圓盤(pán)從X直接移動(dòng)到Z上即可；n>1時(shí)，需要利用塔座Y作輔助塔座，若能設(shè)法將壓在編號(hào)為n圓盤(pán)之上n-1個(gè)圓盤(pán)從塔座X移至塔座Y上，則可先將編號(hào)為n圓盤(pán)從塔座X移至塔座Z上，然后再將塔座Y上n-1個(gè)圓盤(pán)移至塔座Z上。棧和隊(duì)列第24頁(yè)調(diào)用函數(shù)和被調(diào)用函數(shù)之間鏈接及信息交換需經(jīng)過(guò)棧來(lái)進(jìn)行。當(dāng)一個(gè)函數(shù)運(yùn)行期間調(diào)用另一個(gè)函數(shù)，在運(yùn)行被調(diào)用函數(shù)之前，系統(tǒng)需要完成3件事：

1)將全部實(shí)在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保留；

2)為被調(diào)用函數(shù)局部變量分配存放區(qū)；

3)將控制轉(zhuǎn)移到被調(diào)函數(shù)入口。被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，系統(tǒng)應(yīng)完成3件事：

1)保留被調(diào)函數(shù)計(jì)算結(jié)果；

2)釋放被調(diào)函數(shù)數(shù)據(jù)區(qū)；

3)依照被調(diào)函數(shù)保留返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。棧和隊(duì)列第25頁(yè)為了確保遞歸函數(shù)正確執(zhí)行，系統(tǒng)需要設(shè)置一個(gè)遞歸工作棧作為整個(gè)遞歸函數(shù)運(yùn)行期間使用數(shù)據(jù)存放區(qū)。每一層遞歸所需信息組成一個(gè)工作統(tǒng)計(jì)，其中包含全部是在參數(shù)、全部局部變量以及上一層返回地址。每進(jìn)入一層遞歸，就產(chǎn)生一個(gè)新工作統(tǒng)計(jì)壓入棧頂。棧和隊(duì)列第26頁(yè)棧和隊(duì)列第27頁(yè)3.4隊(duì)列3.4.1抽象數(shù)據(jù)類(lèi)型隊(duì)列定義隊(duì)列是一個(gè)先進(jìn)先出（FIFO）線性表。只允許在表一端（隊(duì)尾rear）進(jìn)行插入，在表另一端（對(duì)頭front）刪除元素。

設(shè)隊(duì)列q=（a1,a2,……,an）,a1是對(duì)頭，an是隊(duì)尾。棧和隊(duì)列第28頁(yè)抽象數(shù)據(jù)類(lèi)型隊(duì)列定義：棧和隊(duì)列第29頁(yè)棧和隊(duì)列第30頁(yè)雙端隊(duì)列雙端隊(duì)列是限定插入和刪除操作在表兩端進(jìn)行線性表。還有輸出受限雙端隊(duì)列和輸入受限雙端隊(duì)列。假如限定雙端隊(duì)列從某個(gè)端點(diǎn)插入元素只能從該端點(diǎn)刪除，則該雙端隊(duì)列就變成兩個(gè)棧底相鄰棧了。棧和隊(duì)列第31頁(yè)3.4.2鏈隊(duì)列---隊(duì)列鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)鏈隊(duì)列：用鏈表示隊(duì)列。一個(gè)鏈隊(duì)列需要指向隊(duì)頭和隊(duì)尾2個(gè)指針才能唯一確定。為了操作方便，也給鏈隊(duì)列加一個(gè)頭結(jié)點(diǎn)?？真滉?duì)列判定條件是頭指針和尾指針均指向頭結(jié)點(diǎn)。即Q.rear=Q.front棧和隊(duì)列第32頁(yè)棧和隊(duì)列第33頁(yè)棧和隊(duì)列第34頁(yè)棧和隊(duì)列第35頁(yè)棧和隊(duì)列第36頁(yè)3.4.3循環(huán)隊(duì)列---隊(duì)列次序表示和實(shí)現(xiàn)在隊(duì)列次序存放結(jié)構(gòu)中，用一組地址連續(xù)存放單元依次存放從隊(duì)列頭道隊(duì)列尾元素，附設(shè)兩個(gè)指針front和rear分別指示隊(duì)列頭元素和隊(duì)列尾元素位置。初始化建空隊(duì)列時(shí)，令front=rear=0，每當(dāng)插入新隊(duì)列尾元素，尾指針增1，每當(dāng)刪除隊(duì)列頭元素，頭指針增1。在非空隊(duì)列中，頭指針一直指向隊(duì)列頭元素，尾指針一直指向隊(duì)列尾元素下一個(gè)位置。圖d即使有空間，不過(guò)不能插入新元素。棧和隊(duì)列第37頁(yè)（1）采取平移元素方法，當(dāng)發(fā)生假溢出時(shí)，就把整個(gè)隊(duì)列元素平移到存放區(qū)首部，然后再插入新元素。這種方法需移動(dòng)大量元素，因而效率是很低。（2）將次序隊(duì)列存放區(qū)假想為一個(gè)環(huán)狀空間。當(dāng)發(fā)生假溢出時(shí)，將新元素插入到第一個(gè)位置上，這么做，即使物理上隊(duì)尾在隊(duì)首之前，但邏輯上隊(duì)首依然在前。入列和出列仍按“先進(jìn)先出”標(biāo)準(zhǔn)進(jìn)行，這就是循環(huán)隊(duì)列。很顯然，方法二中不需要移動(dòng)元素，操作效率高，空間利用率也很高。處理方法：棧和隊(duì)列第38頁(yè)循環(huán)隊(duì)列不能用隊(duì)頭指針和隊(duì)尾指針相等來(lái)判斷隊(duì)列是否滿。C語(yǔ)言不能用動(dòng)態(tài)分配一維數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，必須設(shè)定一個(gè)最大隊(duì)列；若無(wú)法預(yù)計(jì)最大長(zhǎng)度，宜用鏈隊(duì)列。棧和隊(duì)列第39頁(yè)判斷堆是空還是滿有兩種方法：1）另設(shè)一個(gè)標(biāo)志位以區(qū)分對(duì)壘是空還是滿；2）少用一個(gè)元素，約定以隊(duì)列頭指針在隊(duì)列尾指針下一位置上作為隊(duì)列呈滿狀態(tài)標(biāo)志。隊(duì)空條件：Q.rear=Q.front隊(duì)滿條件：(Q.rear+1)%MAXSIZE=Q.front棧和隊(duì)列第40頁(yè)棧和隊(duì)列第41頁(yè)棧和隊(duì)列第42頁(yè)作業(yè)：1、假設(shè)表示式中允許包含3種括號(hào)：圓括號(hào)、方括號(hào)和大括號(hào)。設(shè)計(jì)一個(gè)算法采取次序棧判斷表示式中括號(hào)是否正確配對(duì)。81Intmatch(charexp[],intn){charst[Maxsize];inttop=-1;inti=0,tag=1;while(i<n&&ta