第3章棧和隊列

2023年3月4日

3.1棧和隊列的定義和特點3.2案例引入3.3棧的表示和操作的實現(xiàn)3.4棧與遞歸3.5隊列的的表示和操作的實現(xiàn)3.6案例分析與實現(xiàn)教學(xué)內(nèi)容

2023年3月4日

第3章棧和隊列掌握棧和隊列的特點，并能在相應(yīng)的應(yīng)用問題中正確選用熟練掌握棧的兩種存儲結(jié)構(gòu)的基本操作實現(xiàn)算法，特別應(yīng)注意棧滿和?？盏臈l件熟練掌握循環(huán)隊列和鏈隊列的基本操作實現(xiàn)算法，特別注意隊滿和隊空的條件理解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程掌握表達(dá)式求值方法

教學(xué)目標(biāo)

2023年3月4日

棧（Stack）1.定義2.邏輯結(jié)構(gòu)3.存儲結(jié)構(gòu)4.運算規(guī)則5.實現(xiàn)方式隊列（Queue）1.定義2.邏輯結(jié)構(gòu)3.存儲結(jié)構(gòu)4.運算規(guī)則5.實現(xiàn)方式

2023年3月4日

用鐵路調(diào)度站表示棧棧

2023年3月4日

3.1棧和隊列的定義和特點1.定義用順序?；蜴湕４鎯桑皂樞驐８Ｒ?.存儲結(jié)構(gòu)與線性表相同，仍為一對一關(guān)系2.邏輯結(jié)構(gòu)只能在表的一端（棧頂）進(jìn)行插入和刪除運算的線性表棧

2023年3月4日

只能在棧頂運算，且訪問結(jié)點時依照后進(jìn)先出（LIFO）或先進(jìn)后出（FILO）的原則4.運算規(guī)則關(guān)鍵是編寫入棧和出棧函數(shù)，具體實現(xiàn)依順序棧或鏈棧的不同而不同基本操作有入棧、出棧、讀棧頂元素值、建棧、判斷棧滿、棧空等5.實現(xiàn)方式

2023年3月4日

隊列是一種先進(jìn)先出(FIFO)的線性表.在表一端插入,在另一端刪除a1a2a3an...入隊列隊頭隊尾隊列用例

2023年3月4日

2023年3月4日

a1a2a3an...隊頭隊尾出隊列

2023年3月4日

a1a2a3an...隊頭隊尾出隊列

2023年3月4日

a1a2a3an...隊頭隊尾出隊列

2023年3月4日

3.1棧和隊列的定義和特點1.定義用順序隊列或鏈隊存儲均可3.存儲結(jié)構(gòu)與線性表相同，仍為一對一關(guān)系2.邏輯結(jié)構(gòu)只能在表的一端（隊尾）進(jìn)行插入，在另一端（隊頭）進(jìn)行刪除運算的線性表隊列

2023年3月4日

先進(jìn)先出（FIFO）4.運算規(guī)則關(guān)鍵是編寫入隊和出隊函數(shù)，具體實現(xiàn)依順序隊或鏈隊的不同而不同5.實現(xiàn)方式

2023年3月4日

棧、隊列是一種特殊（操作受限）的線性表區(qū)別：僅在于運算規(guī)則不同一般線性表

邏輯結(jié)構(gòu)：一對一存儲結(jié)構(gòu)：順序表、鏈表運算規(guī)則：隨機(jī)、順序存取棧邏輯結(jié)構(gòu)：一對一存儲結(jié)構(gòu)：順序棧、鏈棧運算規(guī)則：后進(jìn)先出棧、隊列與一般線性表的區(qū)別隊列邏輯結(jié)構(gòu)：一對一存儲結(jié)構(gòu)：順序隊、鏈隊運算規(guī)則：先進(jìn)先出3.2案例引入案例3.1：數(shù)制的轉(zhuǎn)換案例3.2：括號匹配的檢驗案例3.3：表達(dá)式求值案例3.4：舞伴問題

2023年3月4日

3.3棧的表示和操作的實現(xiàn)“進(jìn)”＝壓入=PUSH（)“出”＝彈出=POP()

2023年3月4日

順序棧的表示空棧base==top

是棧空標(biāo)志stacksize=4topAbasebasetopABABCtopbasetopbaseABCDbasetop3120top指示真正的棧頂元素之上的下標(biāo)地址棧滿時的處理方法：1、報錯,返回操作系統(tǒng)。2、分配更大的空間，作為棧的存儲空間,將原棧的內(nèi)容移入新棧。

2023年3月4日

#defineMAXSIZE100typedefstruct{

SElemType*base; SElemType*top; intstacksize;}SqStack;順序棧的表示

2023年3月4日

構(gòu)造一個空棧步驟：(1)分配空間并檢查空間是否分配失敗，若失敗則返回錯誤順序棧初始化basestacksizetops(2)設(shè)置棧底和棧頂指針

S.top=S.base;(3)設(shè)置棧大小

2023年3月4日

StatusInitStack(SqStack&S){

S.base=newSElemType[MAXSIZE]；

if(!S.base) returnOVERFLOW;

S.top=S.base; S.stackSize=MAXSIZE; returnOK;}順序棧初始化

2023年3月4日

判斷順序棧是否為空boolStackEmpty(SqStackS){ if(S.top==S.base)returntrue;elsereturnfalse;}basetop3120

2023年3月4日

求順序棧的長度intStackLength(SqStackS){ returnS.top–S.base;}basetopAB

2023年3月4日

StatusClearStack(SqStackS){ if(S.base)S.top=S.base; returnOK;}清空順序棧basetop3120

2023年3月4日

StatusDestroyStack(SqStack&S){ if(S.base) { deleteS.base;

S.stacksize=0; S.base=S.top=NULL; }returnOK;}銷毀順序棧

2023年3月4日

(1)判斷是否棧滿，若滿則出錯(2)元素e壓入棧頂(3)棧頂指針加1順序棧進(jìn)棧StatusPush(SqStack&S,SElemTypee){ if(S.top-S.base==S.stacksize)//棧滿

returnERROR;

*S.top++=e; returnOK;}*S.top=e;S.top++;ABCtopbase

2023年3月4日

(1)判斷是否?？?，若空則出錯(2)獲取棧頂元素e(3)棧頂指針減1順序棧出棧StatusPop(SqStack&S,SElemType&e){ if(S.top==S.base)//?？?/p>

returnERROR;

e＝*--S.top; returnOK;}--S.top;e=*S.top;ABCtopbase

2023年3月4日

判斷是否空棧，若空則返回錯誤否則通過棧頂指針獲取棧頂元素取順序棧棧頂元素StatusGetTop(SqStackS,SElemType&e){ if(S.top==S.base) returnERROR; //?？?/p>

e=*(S.top–1); returnOK;}

e=*(S.top--);???ABCtopbase

2023年3月4日

435612中到了12順序不能實現(xiàn)；135426可以實現(xiàn)。1.如果一個棧的輸入序列為123456，能否得到435612和135426的出棧序列？練習(xí)

2023年3月4日

練習(xí)Ａ．iＢ．n-iＣ．n-i+1Ｄ．不確定Ｃ2.若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為

2023年3月4日

練習(xí)Ａ．top不變Ｂ．top=0Ｃ．top++

Ｄ．top--D3.在一個具有n個單元的順序棧中，假設(shè)以地址高端作為棧底，以top作為棧頂指針，則當(dāng)作進(jìn)棧處理時，top的變化為

2023年3月4日

考研試題b[0]t[0]t[1]b[1]0m-1V雙棧共享一個棧空間優(yōu)點：互相調(diào)劑，靈活性強(qiáng)，減少溢出機(jī)會

2023年3月4日

將編號為0和1的兩個棧存放于一個數(shù)組空間V[m]中，棧底分別處于數(shù)組的兩端。當(dāng)?shù)?號棧的棧頂指針top[0]等于-1時該棧為空，當(dāng)?shù)?號棧的棧頂指針top[1]等于m時該棧為空。兩個棧均從兩端向中間增長（如下圖所示）。考研試題bot[0]top[0]top[1]bot[1]0m-1V

2023年3月4日

typedefstruct{ inttop[2],bot[2];//棧頂和棧底指針

SElemType*V;//棧數(shù)組

intm;//棧最大可容納元素個數(shù)}DblStack;數(shù)據(jù)結(jié)構(gòu)定義如下考研試題

2023年3月4日

voidDblpush(DblStack&s,SElemTypex,inti)；//把x插入到棧i的棧intDblpop(DblStack&s,inti,SElemType&x)；

//退掉位于棧i棧頂?shù)脑豬ntIsEmpty(DblStacks,inti)

；//判棧i空否,空返回1,否則返回0intIsFull(DblStacks)

；//判棧滿否,滿返回1,否則返回0試編寫判斷?？?、棧滿、進(jìn)棧和出棧四個算法的函數(shù)(函數(shù)定義方式如下）考研試題

2023年3月4日

b[0]t[0]t[1]b[1]0m-1V棧空：top[i]==bot[i]i表示棧的編號棧滿：top[0]+1==top[1]或top[1]-1==top[0]提示

2023年3月4日

鏈棧的表示運算是受限的單鏈表，只能在鏈表頭部進(jìn)行操作，故沒有必要附加頭結(jié)點。棧頂指針就是鏈表的頭指針

typedefstructStackNode{SElemTypedata;structStackNode*next;}StackNode,*LinkStack;LinkStackS;

datanext棧頂棧底∧S

2023年3月4日

鏈棧的初始化voidInitStack(LinkStack&S){

S=NULL;}∧S

2023年3月4日

判斷鏈棧是否為空StatusStackEmpty(LinkStackS)

{

if(S==NULL)returnTRUE;

elsereturn

FALSE;

}

2023年3月4日

鏈棧進(jìn)棧StatusPush(LinkStack&S,SElemTypee)

{

p=newStackNode;//生成新結(jié)點p

if(!p)exit(OVERFLOW);

p->data=e;p->next=S;S=p;

returnOK;}p∧S

2023年3月4日

鏈棧進(jìn)棧p∧SeStatusPush(LinkStack&S,SElemTypee)

{

p=newStackNode;//生成新結(jié)點p

if(!p)exit(OVERFLOW);

p->data=e;p->next=S;S=p;

returnOK;}

2023年3月4日

鏈棧進(jìn)棧p∧SeStatusPush(LinkStack&S,SElemTypee)

{

p=newStackNode;//生成新結(jié)點p

if(!p)exit(OVERFLOW);

p->data=e;p->next=S;S=p;

returnOK;}

2023年3月4日

鏈棧進(jìn)棧p∧SeSStatusPush(LinkStack&S,SElemTypee)

{

p=newStackNode;//生成新結(jié)點p

if(!p)exit(OVERFLOW);

p->data=e;p->next=S;S=p;

returnOK;}

2023年3月4日

鏈棧出?！腟Ae=‘A’StatusPop(LinkStack&S,SElemType&e){if(S==NULL)returnERROR;

e=S->data;p=S;S=S->next;deletep;returnOK;}

2023年3月4日

鏈棧出棧∧SAe=‘A’pStatusPop(LinkStack&S,SElemType&e){if(S==NULL)returnERROR;

e=S->data;p=S;S=S->next;deletep;returnOK;}

2023年3月4日

鏈棧出?！腟Ae=‘A’pSStatusPop(LinkStack&S,SElemType&e){if(S==NULL)returnERROR;

e=S->data;p=S;S=S->next;deletep;returnOK;}

2023年3月4日

鏈棧出棧StatusPop(LinkStack&S,SElemType&e){if(S==NULL)returnERROR;

e=S->data;p=S;S=S->next;deletep;returnOK;}∧e=‘A’S

2023年3月4日

取鏈棧棧頂元素SElemTypeGetTop(LinkStackS){

if(S==NULL)

exit(1)；

elsereturnS–>data;}

2023年3月4日

3.4棧與遞歸遞歸的定義若一個對象部分地包含它自己,或用它自己給自己定義,則稱這個對象是遞歸的；若一個過程直接地或間接地調(diào)用自己,則稱這個過程是遞歸的過程。longFact(longn){if(n==0)return1;

elsereturnn*Fact(n-1);}

2023年3月4日

voidFindKey(箱子){if(木箱子)return;elseFindKey(下面的箱子)}

2023年3月4日

有人送了我金、銀、銅、鐵、木五個寶箱，我想打開金箱子，卻沒有打開這個箱子的鑰匙。在金箱子上面寫著一句話：“打開我的鑰匙裝在銀箱子里?！庇谑俏襾淼姐y箱子前，發(fā)現(xiàn)還是沒有打開銀箱子的鑰匙。銀箱子上也寫著一句話：“打開我的鑰匙裝在銅箱子里?！庇谑俏以賮淼姐~箱子前，發(fā)現(xiàn)還是沒有打開銅箱子的鑰匙。銅箱子上也寫著一句話：“打開我的鑰匙裝在鐵箱子里。”于是我又來到了鐵箱子前，發(fā)現(xiàn)還是沒有打開鐵箱子的鑰匙。鐵箱子上也寫著一句話：“打開我的鑰匙裝在木箱子里。”

2023年3月4日

我來到木箱子前，打開了木箱，并從木箱里拿出鐵箱子的鑰匙，打開了鐵箱，從鐵箱里拿了出銅箱的鑰匙，打開了銅箱，再從銅箱里拿出銀箱的鑰匙打開了銀箱，最后從銀箱里取出金箱的鑰匙，打開了我想打開的金箱子。暈吧……很啰嗦地講了這么長一個故事。

2023年3月4日

當(dāng)多個函數(shù)構(gòu)成嵌套調(diào)用時,遵循后調(diào)用先返回棧

2023年3月4日

以下三種情況常常用到遞歸方法遞歸定義的數(shù)學(xué)函數(shù)具有遞歸特性的數(shù)據(jù)結(jié)構(gòu)可遞歸求解的問題

2023年3月4日

1.遞歸定義的數(shù)學(xué)函數(shù):階乘函數(shù):

2階Fibonaci數(shù)列:

2023年3月4日

樹

2.具有遞歸特性的數(shù)據(jù)結(jié)構(gòu):RootLchildRchild廣義表

A=(a,A)3.可遞歸求解的問題:迷宮問題Hanoi塔問題

2023年3月4日

分治法：對于一個較為復(fù)雜的問題，能夠分解成幾個相對簡單的且解法相同或類似的子問題來求解1、能將一個問題轉(zhuǎn)變成一個新問題，而新問題與原問題的解法相同或類同，不同的僅是處理的對象，且這些處理對象是變化有規(guī)律的2、可以通過上述轉(zhuǎn)化而使問題簡化3、必須有一個明確的遞歸出口，或稱遞歸的邊界用分治法求解遞歸問題必備的三個條件

2023年3月4日

分治法求解遞歸問題算法的一般形式：

voidp(參數(shù)表){if（遞歸結(jié)束條件）可直接求解步驟；-----基本項

elsep（較小的參數(shù)）；------歸納項

}longFact(longn){if(n==0)return1;//基本項

elsereturnn*Fact(n-1);//歸納項}

2023年3月4日

返回2

參數(shù)2計算2*Fact(1)返回1

參數(shù)1計算1*Fact(0)返回1

參數(shù)0直接定值=1參數(shù)傳遞遞歸調(diào)用結(jié)果返回回歸求值if(n==0)return1;elsereturnn*Fact(n-1);求解階乘n!的過程主程序

main:Fact(4)返回24參數(shù)4計算4*Fact(3)返回6

參數(shù)3計算3*Fact(2)

2023年3月4日

設(shè)有一個遞歸算法如下:intX(intn){if(n<=3)return1;elsereturnX(n-2)+X(n-4)+1}則計算X(X(8))時需要計算X函數(shù)

次.D練習(xí)A.8 B.9C.16 D.18

2023年3月4日

在印度圣廟里，一塊黃銅板上插著三根寶石針。主神梵天在創(chuàng)造世界時，在其中一根針上穿好了由大到小的64片金片，這就是漢諾塔。僧侶不停移動這些金片，一次只移動一片，小片必在大片上面。當(dāng)所有的金片都移到另外一個針上時，世界將會滅亡。

漢諾塔

2023年3月4日

2023年3月4日

規(guī)則:(1)每次只能移動一個圓盤(2)圓盤可以插在A,B和C中的任一塔座上(3)任何時刻不可將較大圓盤壓在較小圓盤之上Hanoi塔問題ABC

2023年3月4日

Hanoi塔問題

n=1，則直接從A移到C。否則(1)用

C柱做過渡，將

A的(n-1)個移到

B(2)將

A最后一個直接移到

C(3)用

A做過渡，將

B的

(n-1)個移到

C

2023年3月4日

#include<iostream.h>intc=0;voidmove(charx,intn,charz){cout<<++c<<","<<n<<","<<x<<","<<z<<endl;}voidHanoi(intn,charA,charB,charC){if(n==1)move(A,1,C);else{Hanoi(n-1,A,C,B);move(A,n,C);Hanoi(n-1,B,A,C);}}voidmain(){Hanoi(3,'a','b','c');}跟蹤程序，給出下列程序的運行結(jié)果，以深刻地理解遞歸的調(diào)用和返回過程

2023年3月4日

3,a,b,c遞歸調(diào)用樹2,a,c,b2,b,a,c③,a->c①,a->c1,a,b,c1,c,a,b②,a->b1,b,c,a1,a,b,c②,b->c①,c->b①,b->a①,a->c

2023年3月4日

調(diào)用前,系統(tǒng)完成:(1)將實參,返回地址等傳遞給被調(diào)用函數(shù)(2)為被調(diào)用函數(shù)的局部變量分配存儲區(qū)(3)將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口調(diào)用后,系統(tǒng)完成:(1)保存被調(diào)用函數(shù)的計算結(jié)果(2)釋放被調(diào)用函數(shù)的數(shù)據(jù)區(qū)(3)依照被調(diào)用函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)函數(shù)調(diào)用過程

2023年3月4日

“層次”主函數(shù)第1次調(diào)用第i次調(diào)用0層1層i層“遞歸工作棧”“工作記錄”實在參數(shù),局部變量,返回地址遞歸函數(shù)調(diào)用的實現(xiàn)

2023年3月4日

空間效率時間效率O(2n)與遞歸樹的結(jié)點數(shù)成正比與遞歸樹的深度成正比O(n)遞歸算法的效率分析

2023年3月4日

1234f(1)=1f(1)+1+f(1)=3f(2)+1+f(2)=7f(3)+1+f(3)=15f(n)=2f(n-1)+1f(n-1)=2f(n-2)+1f(n-2)=2f(n-3)+1......f(3)=2f(2)+1f(2)=2f(1)+120f(n)=21f(n-1)+2021f(n-1)=22f(n-2)+2122f(n-2)=23f(n-3)+22......2n-3f(3)=2n-2f(2)+2n-32n-2f(2)=2n-1f(1)+2n-2f(n)=20+21+…+2n-2+2n-1f(1)=2n-1遞歸算法的效率分析

2023年3月4日

64片金片移動次數(shù)：264-1=15假如每秒鐘一次，共需多長時間呢？一年大約有31536926秒，移完這些金片需要５８００多億年世界、梵塔、廟宇和眾生都已經(jīng)灰飛煙滅……假定計算機(jī)以每秒1000萬個金片的速度進(jìn)行移動，則需要花費58,490年的時間。太陽是在大約45.7億年前在一個坍縮的氫分子云內(nèi)形成。根據(jù)大爆炸宇宙模型推算，宇宙年齡大約138.2億年！

2023年3月4日

優(yōu)點：結(jié)構(gòu)清晰，程序易讀缺點：每次調(diào)用要生成工作記錄，保存狀態(tài)信息，入棧；返回時要出棧，恢復(fù)狀態(tài)信息。時間開銷大。遞歸的優(yōu)缺點遞歸非遞歸

2023年3月4日

(1)尾遞歸、單向遞歸循環(huán)結(jié)構(gòu)

(2)自用棧模擬系統(tǒng)的運行時棧

遞歸非遞歸

2023年3月4日

尾遞歸循環(huán)結(jié)構(gòu)longFact(longn){if(n==0)return1;

elsereturnn*Fact(n-1);}longFact(longn){t=1;

for(i=1;i<=n;i++)

t=t*i;

returnt;}

2023年3月4日

longFib(longn){//Fibonacci數(shù)列

if(n==1||n==2)return1;elsereturnFib(n-1)+Fib(n-2);}單向遞歸循環(huán)結(jié)構(gòu)雖然有一處以上的遞歸調(diào)用語句，但各次遞歸調(diào)用語句的參數(shù)只和主調(diào)函數(shù)有關(guān)，相互之間參數(shù)無關(guān)，并且這些遞歸調(diào)用語句處于算法的最后。

2023年3月4日

尾遞歸、單向遞歸循環(huán)結(jié)構(gòu)longFib(longn){if(n==1||n==2)return1;elsereturnFib(n-1)+Fib(n-2);}longFib(longn){if(n==1||n==2)return1;else{t1=1;t2=1;

for(i=3;i<=n;i++){

t3=t1+t2;

t1=t2;t2=t3;

}returnt3;

}}

2023年3月4日

借助棧改寫遞歸（了解）（1）設(shè)置一個工作棧存放遞歸工作記錄（包括實參、返回地址及局部變量等)。（2）進(jìn)入非遞歸調(diào)用入口（即被調(diào)用程序開始處）將調(diào)用程序傳來的實在參數(shù)和返回地址入棧（遞歸程序不可以作為主程序，因而可認(rèn)為初始是被某個調(diào)用程序調(diào)用)。（3）進(jìn)入遞歸調(diào)用入口：當(dāng)不滿足遞歸結(jié)束條件時，逐層遞歸，將實參、返回地址及局部變量入棧，這一過程可用循環(huán)語句來實現(xiàn)—模擬遞歸分解的過程。（4）遞歸結(jié)束條件滿足，將到達(dá)遞歸出口的給定常數(shù)作為當(dāng)前的函數(shù)值。（5）返回處理：在棧不空的情況下，反復(fù)退出棧頂記錄，根據(jù)記錄中的返回地址進(jìn)行題意規(guī)定的操作，即逐層計算當(dāng)前函數(shù)值，直至?？諡橹埂M遞歸求值過程。

2023年3月4日

輸入一個整數(shù)，輸出對應(yīng)的2進(jìn)制形式voidconversion(intn){

if(n==0) return; else { }}voidmain(){ intn; cin>>n; conversion(n); cout<<endl;}遞歸鞏固練習(xí)1conversion(n/2);cout<<n%2;if(n>0){conversion(n/2);cout<<n%2;}

2023年3月4日

voidconversion(intn){ if(n==1) cout<<n%2; else { conversion(n/2); cout<<n%2; }}if(n>0) { conversion(n/2); cout<<n%2;}

2023年3月4日

if(n==0) return;else { n=n/2; conversion(n); cout<<n%2; }if(n==0) return;else { inti=n%2; conversion(n/2); cout<<i; }

2023年3月4日

組合問題找出從自然數(shù)1、2、……、m中任取k個數(shù)的所有組合。例如m=5，k=3遞歸鞏固練習(xí)2

2023年3月4日

遞歸思想：設(shè)函數(shù)comb(intm,intk)為找出從自然數(shù)1、2、……、m中任取k個數(shù)的所有組合。當(dāng)組合的第一個數(shù)字選定時，其后的數(shù)字是從余下的m-1個數(shù)中取k-1數(shù)的組合。這就將求m個數(shù)中取k個數(shù)的組合問題轉(zhuǎn)化成求m-1個數(shù)中取k-1個數(shù)的組合問題。

2023年3月4日

設(shè)數(shù)組a[]存放求出的組合的數(shù)字，將確定的k個數(shù)字組合的第一個數(shù)字放在a[k]中當(dāng)一個組合求出后，才將a[]中的一個組合輸出第一個數(shù)可以是m、m-1、……、k函數(shù)將確定組合的第一個數(shù)字放入數(shù)組后，有兩種可能的選擇還未確定組合的其余元素，繼續(xù)遞歸已確定組合的全部元素，輸出這個組合

2023年3月4日

//一般的遞歸算法#include<stdio.h>#define MAXN 100int a[MAXN];void comb(intm,intk){ inti,j; for(i=m;i>=k;i--) { a[k]=i; if(k>1)comb(i-1,k-1); else { for(j=a[0];j>0;j--) printf("%4d",a[j]); printf("\n"); } }}voidmain(){ a[0]=3;//用來表示k comb(5,a[0]);}

2023年3月4日

c(5,3)c(4,2)c(2,2)c(3,1)c(3,2)c(1,1)54343a[3]=5a[2]=4a[1]=3a[1]=1c(2,1)a[1]=22

2023年3月4日

//簡單的枚舉算法：#include<stdio.h>voidmain(){intn,x,y,z,s=0;scanf("%d",&n);for(x=1;x<=n;x++)for(y=1;y<=n;y++) for(z=1;z<=n;z++) if(x<y&&y<z) {s++; printf("%5d%5d%5d\n",x,y,z);} printf("s=%d\n",s);}

2023年3月4日

//加速的枚舉算法：#include<stdio.h>voidmain(){intn,x,y,z,s=0;scanf("%d",&n);for(x=1;x<=n-2;x++)for(y=x+1;y<=n-1;y++) for(z=y+1;z<=n;z++) {s++; printf("%5d%5d%5d\n",x,y,z);} printf("s=%d\n",s);}

2023年3月4日

輸出一個正整數(shù)n的所有整數(shù)和形式。如n=4

遞歸鞏固練習(xí)3

2023年3月4日

//源程序1：#include<stdio.h>ints=0,a[10]={0};voidf(intn,intk){ inti; if(n>0)for(i=n;i>=1;i--) {a[k]=i;f(n-i,k+1);} else {for(i=0;i<k;i++)printf("%5d",a[i]); printf("\n"); s++; } }voidmain(){ intn; scanf("%d",&n); f(n,0); printf("s=%d\n",s);}

2023年3月4日

遞歸調(diào)用樹f(0,1)f(4,0)f(1,1)f(3,1)f(0,3)f(0,2)f(0,3)f(1,3)f(0,2)f(2,1)f(0,2)f(1,2)f(1,2)f(2,2)f(0,4)143211f(0,3)322112111

2023年3月4日

//源程序2：#include<stdio.h>ints=0,a[10]={0};voidf(intn,intk){ for(inti=1;i<=n;i++) { a[k]=i; if(n-i>0) f(n-i,k+1); elseif(n-i==0) { for(intj=0;j<=k;j++) printf("%5d",a[j]); printf("\n"); s++; } }}voidmain(){ intn; scanf("%d",&n);f(n,0); printf("s=%d\n",s);}

2023年3月4日

輸出一個正整數(shù)n的分解形式。例如,當(dāng)n=4時：

4=4 4=3+1 4=2+2 4=2+1+1 4=1+1+1+1共計5種形式 。當(dāng)n=7時，共有15種形式。當(dāng)n=10時，共有42種形式。

注意：與練習(xí)3的區(qū)別

遞歸鞏固練習(xí)4

2023年3月4日

#include<stdio.h>ints=0,a[10]={0};voidf(intn,intk){for(inti=1;i<=n;i++){a[k]=i;if(n-i>0&&a[k-1]<=i)f(n-i,k+1); elseif(n-i==0&&a[k-1]<=a[k]) {for(intj=1;j<=k;j++)printf("%5d",a[j]); printf("\n"); s++; }}}voidmain(){ intn; scanf("%d",&n);f(n,1); printf("s=%d\n",s);}

2023年3月4日

3.5隊列的表示和操作的實現(xiàn)設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次通過S，一個元素出棧后即進(jìn)入Q，若6個元素出隊的序列是e2、e4、e3、e6、e5和e1，則棧S的容量至少應(yīng)該是（）。（A）2（B）3（C）4（D）6練習(xí)B

2023年3月4日

數(shù)據(jù)對象:數(shù)據(jù)關(guān)系:基本操作:

(1)

InitQueue(&Q)//構(gòu)造空隊列

(2)DestroyQueue(&Q)//銷毀隊列

(3)ClearQueue(&S)//清空隊列

(4)QueueEmpty(S)//判空.空--TRUE,ADTQueue{隊列的抽象數(shù)據(jù)類型

2023年3月4日

(5)QueueLength(Q)//取隊列長度

(6)GetHead(Q,&e)//取隊頭元素,(7)EnQueue(&Q,e)//入隊列

(8)DeQueue(&Q,&e)//出隊列

(9)QueueTraverse(Q,visit())//遍歷}ADTQueue隊列的抽象數(shù)據(jù)類型

2023年3月4日

#defineM100//最大隊列長度Typedefstruct{QElemType*base;//初始化的動態(tài)分配存儲空間

intfront;//頭指針

intrear;//尾指針}SqQueue;

隊列的順序表示－－用一維數(shù)組base[M]

2023年3月4日

隊列的順序表示－－用一維數(shù)組base[M]Q.front012345Q.rearQ.frontQ.rearJ1J2J3Q.frontQ.rearJ3Q.frontQ.rearJ5J6front=rear=0空隊標(biāo)志：front==rear入隊：base[rear++]=x;出隊：x=base[front++];

2023年3月4日

Q.frontQ.rearJ5J6Q.front012345Q.rearJ5J6J1J2J3J4存在的問題設(shè)大小為Mfront=0rear=M時再入隊—真溢出front0rear=M時再入隊—假溢出

2023年3月4日

2023年3月4日

解決的方法－－循環(huán)隊列10Q.rearQ.front......base[0]接在base[M-1]之后若rear+1==M則令rear=0;實現(xiàn)：利用“模”運算入隊：

base[rear]=x;rear=(rear+1)%M;出隊：

x=base[front];front=(front+1)%M;

2023年3月4日

J4J5J6012345rearfrontJ9J8J7J7,J8,J9入隊隊空：front==rear隊滿：front==rear解決方案：1.另外設(shè)一個標(biāo)志以區(qū)別隊空、隊滿2.少用一個元素空間：隊空：front==rear

隊滿：(rear+1)%M==frontJ4J5J6012345rearfront012345frontJ4,J5,J6出隊rear

2023年3月4日

J4J5J6012345rearfrontJ8J7J7,J8,J9入隊隊空：front==rear隊滿：front==rear解決方案：1.另外設(shè)一個標(biāo)志以區(qū)別隊空、隊滿2.少用一個元素空間：隊空：front==rear

隊滿：(rear+1)%M==frontJ4J5J6012345rearfront012345frontJ4,J5,J6出隊rear

2023年3月4日

J4J5J6012345rearfrontJ8J7J7,J8,J9入隊隊空：front==rear隊滿：front==rear解決方案：1.另外設(shè)一個標(biāo)志以區(qū)別隊空、隊滿2.少用一個元素空間：隊空：front==rear

隊滿：(rear+1)%M==frontJ4J5J6012345rf012345frontJ4,J5,J6出隊rear

2023年3月4日

循環(huán)隊列#defineMAXQSIZE100//最大長度Typedefstruct{QElemType*base;//初始化的動態(tài)分配存儲空間

intfront;//頭指針

intrear;//尾指針}SqQueue;

2023年3月4日

StatusInitQueue(SqQueue&Q){

Q.base=newQElemType[MAXQSIZE]

if(!Q.base)exit(OVERFLOW);

Q.front=Q.rear=0;returnOK;}循環(huán)隊列初始化

2023年3月4日

求循環(huán)隊列的長度intQueueLength(SqQueueQ){

return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;

}

2023年3月4日

StatusEnQueue(SqQueue&Q,QElemTypee){if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;

Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}循環(huán)隊列入隊

2023年3月4日

StatusDeQueue(LinkQueue&Q,QElemType&e){if(Q.front==Q.rear)returnERROR;

e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;returnOK;}循環(huán)隊列出隊

2023年3月4日

...datanext隊頭隊尾Q.frontQ.rear鏈隊列

2023年3月4日

typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;//隊頭指針

QueuePtrrear;//隊尾指針}LinkQueue;

鏈隊列

2023年3月4日

(a)空隊列(b)元素x入隊列(d)元素x出隊列(c)元素y入隊列鏈隊列

2023年3月4日

StatusInitQueue(LinkQueue&Q){

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);

Q.front->next=NULL;returnOK;}鏈隊列初始化

2023年3月4日

StatusDestroyQueue(LinkQueue&Q){while(Q.front){

Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}returnOK;}銷毀鏈隊列...datanext隊頭隊尾Q.frontQ.rear

2023年3月4日

StatusQueueEmpty(LinkQueueQ){return(Q.front==Q.rear);}判斷鏈隊列是否為空

2023年3月4日

StatusGetHead(LinkQueueQ,QElemType&e){if(Q.front==Q.rear)returnERROR;

e=Q.front->next->data;returnOK;}求鏈隊列的隊頭元素

2023年3月4日

StatusEnQueue(LinkQueue&Q,QElemTypee){p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);

p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}鏈隊列入隊p

2023年3月4日

StatusDeQueue(LinkQueue&Q,QElemType&e){if(Q.front==Q.rear)returnERROR;

p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;deletep;returnOK;}鏈隊列出隊p

2023年3月4日

3.6案例分析與實現(xiàn)案例3.1：數(shù)制的轉(zhuǎn)換【算法步驟】①初始化一個空棧S。②

當(dāng)十進(jìn)制數(shù)N非零時，循環(huán)執(zhí)行以下操作：把N與8求余得到的八進(jìn)制數(shù)壓入棧S；N更新為N與8的商。③

當(dāng)棧S非空時，循環(huán)執(zhí)行以下操作：彈出棧頂元素e；輸出e。

2023年3月4日

【算法描述】voidconversion(intN){//對于任意一個非負(fù)十進(jìn)制數(shù)，打印輸出與其等值的八進(jìn)制數(shù)

InitStack(S); //初始化空棧Swhile(N) //當(dāng)N非零時,循環(huán)

{Push(S,N%8); //把N與8求余得到的八進(jìn)制數(shù)壓入棧SN=N/8; //N更新為N與8的商

}while(!StackEmpty(S))//當(dāng)棧S非空時，循環(huán)

{Pop(S,e); //彈出棧頂元素ecout<<e; //輸出e}}案例3.1：數(shù)制的轉(zhuǎn)換

2023年3月4日

案例3.2：括號的匹配【算法步驟】①初始化一個空棧S。②設(shè)置一標(biāo)記性變量flag，用來標(biāo)記匹配結(jié)果以控制循環(huán)及返回結(jié)果，1表示正確匹配，0表示錯誤匹配，flag初值為1。③掃描表達(dá)式，依次讀入字符ch，如果表達(dá)式?jīng)]有掃描完畢或flag非零，則循環(huán)執(zhí)行以下操作：若ch是左括號“[”或“(”，則將其壓入棧；若ch是右括號“)”，則根據(jù)當(dāng)前棧頂元素的值分情況考慮：若棧非空且棧頂元素是“(”，則正確匹配，否則錯誤匹配，flag置為0；若ch是右括號“]”，則根據(jù)當(dāng)前棧頂元素的值分情況考慮：若棧非空且棧頂元素是“[”，則正確匹配，否則錯誤匹配，flag置為0。④退出循環(huán)后，如果?？涨襢lag值為1，則匹配成功，返回true，否則返回false。

2023年3月4日

算術(shù)四則運算規(guī)則(1)先乘除,后加減(2)從左算到右(3)先括號內(nèi),后括號外案例3.3：表達(dá)式求值

2023年3月4日

表達(dá)式常數(shù)標(biāo)識符操作數(shù)(operand)運算符(operator)界限符(delimiter)算術(shù)邏輯關(guān)系括號結(jié)束符

2023年3月4日

>><<<>>>><<<>>>>>><>>>>>><>><<<<<=>>>>x>><<<<<=xx表3.1算符間的優(yōu)先關(guān)系

2023年3月4日

OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,’3’)

#*(7-2)#3#Push(optr,’*’)#,*3(7-2)#Push(optr,’(’)#,*,(37-2)#Push(opnd,’7’)#,*,(3,7-2)#Push(optr,’-’)#,*,(,－3,72)#Push(opnd,’2’)#,*,(,－3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)

2023年3月4日

【算法步驟】①初始化OPTR棧和OPND棧，將表達(dá)式起始符“#”壓入OPTR棧。②掃描表達(dá)式，讀入第一個字符ch，如果表達(dá)式?jīng)]有掃描完畢至“#”或OPTR的棧頂元素不為“#”時，則循環(huán)執(zhí)行以下操作：若ch不是運算符，則壓入OPND棧，讀入下一字符ch；若ch是運算符，則根據(jù)OPTR的棧頂元素和ch的優(yōu)先級比較結(jié)果，做不同的處理：若是小于，則ch壓入OPTR棧，讀入下一字符ch；若是大于，則彈出OPTR棧頂?shù)倪\算符，從OPND棧彈出兩個數(shù)，進(jìn)行相應(yīng)運算，結(jié)果壓入OPND棧；若是等于，則OPTR的棧頂元素是“(”且ch是“)”，這時彈出OPTR棧頂?shù)摹?”，相當(dāng)于括號匹配成功，然后讀入下一字符ch。③OPND棧頂元素即為表達(dá)式求值結(jié)果，返回此元素。設(shè)定兩棧：OPND-----操作數(shù)或運算結(jié)果OPTR------運算符

2023年3月4日

OperandTypeEvaluateExpression(){

InitStack(OPTR);Push(OPTR，'#');InitStack(OPND);ch=getchar();while(ch!='#'||GetTop(OPTR)!='#'){if(!In(ch)){Push(OPND,ch);ch=getchar();}//ch不是運算符則進(jìn)棧

elseswitch(Precede(GetTop(OPTR),ch)){//比較優(yōu)先權(quán)

case'<'://當(dāng)前字符ch壓入OPTR棧，讀入下一字符chPush(OPTR,ch);ch=getchar();break;case'>'://彈出OPTR棧頂?shù)倪\算符運算，并將運算結(jié)果入棧

Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;case'='://脫括號并接收下一字符

Pop(OPTR,x);ch=getchar();break;}//switch}//whilereturnGetTop(OPND);}//EvaluateExpression

2023年3月4日

迷宮求解

2023年3月4日

從入口出發(fā)，按某一方向向未走過的前方探索若能走通，則到達(dá)新點，否則試探下一方向;若所有的方向均沒有通路，則沿原路返回前一點，換下一個方向再繼續(xù)試探直到所有可能的通路都探索到，或找到一條通路，或無路可走又返回到入口點。求解思想：回溯法迷宮求解

2023年3月4日

需要解決的問題：1、表示迷宮的數(shù)據(jù)結(jié)構(gòu)2、試探方向3、棧的設(shè)計4、防止重復(fù)到達(dá)某點，避免發(fā)生死循環(huán)迷宮求解

2023年3月4日

1、表示迷宮的數(shù)據(jù)結(jié)構(gòu)表示一個m行n列迷宮：用maze[m][n]表示，0≤i<m,0≤j<nmaze[i][j]=0通路maze[i][j]=1不通改進(jìn)：用maze[m+2][n+2]表示且maze[i][j]=1，i=0或m＋1,j=0或n＋1入口坐標(biāo)為（1，1），出口坐標(biāo)為（m，n）

迷宮求解

2023年3月4日

0123456789011