第3章棧和隊(duì)列1

2023年7月28日

數(shù)據(jù)結(jié)構(gòu)

Friday,July28,2023

2023年7月28日

信息學(xué)院3.1

棧3.2棧的應(yīng)用3.3棧與遞歸3.4隊(duì)列3.5隊(duì)列的應(yīng)用教學(xué)內(nèi)容

Friday,July28,2023

2023年7月28日

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

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

Friday,July28,2023

2023年7月28日

信息學(xué)院棧（Stack）1.定義2.邏輯結(jié)構(gòu)3.存儲結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式隊(duì)列（Queue）1.定義2.邏輯結(jié)構(gòu)3.存儲結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式

Friday,July28,2023

2023年7月28日

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

Friday,July28,2023

2023年7月28日

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

Friday,July28,2023

2023年7月28日

信息學(xué)院棧是一種特殊的線性表，它只能在表的一端（棧頂）進(jìn)行插入和刪除運(yùn)算棧與一般線性表的區(qū)別：僅在于運(yùn)算規(guī)則不同“進(jìn)”＝壓入=PUSH（)“出”＝彈出=POP()一般線性表

邏輯結(jié)構(gòu)：一對一存儲結(jié)構(gòu)：順序表、鏈表運(yùn)算規(guī)則：隨機(jī)、順序存取棧邏輯結(jié)構(gòu)：一對一存儲結(jié)構(gòu)：順序棧、鏈棧運(yùn)算規(guī)則：后進(jìn)先出棧與一般線性表的區(qū)別

Friday,July28,2023

2023年7月28日

信息學(xué)院“進(jìn)”＝壓入=PUSH（)“出”＝彈出=POP()

Friday,July28,2023

2023年7月28日

信息學(xué)院a1a2……an順序棧Sai……表頭表尾棧底base棧頂top低地址高地址寫入：v[i]=ai讀出：x=v[i]壓入：PUSH(an+1)彈出：POP(x)前提：一定要預(yù)設(shè)棧頂指針top！低地址高地址v[i]a1a2

aian

……順序表V[n]

……an+1順序棧與順序表

Friday,July28,2023

順序棧的表示topAbasebasetopABbasetop312002113320top指示真正的棧頂元素之上的下標(biāo)地址

2023年7月28日

信息學(xué)院#defineMAXSIZE100typedefstruct{

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

Friday,July28,2023

2023年7月28日

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

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

Friday,July28,2023

2023年7月28日

信息學(xué)院StatusInitStack(SqStack&S){

S.base=newSElemType[MAXSIZE]；

if(!S.base) returnOVERFLOW;

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

Friday,July28,2023

2023年7月28日

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

Friday,July28,2023

2023年7月28日

信息學(xué)院求順序棧的長度intStackLength(SqStackS){ returnS.top–S.base;}basetopAB

Friday,July28,2023

2023年7月28日

信息學(xué)院StatusClearStack(SqStackS){ if(S.base)S.top=S.base; returnOK;}清空順序棧basetop3120

Friday,July28,2023

2023年7月28日

信息學(xué)院StatusDestroyStack(SqStack&S){ if(S.base) { deleteS.base;

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

Friday,July28,2023

2023年7月28日

信息學(xué)院(1)判斷是否棧滿，若滿則出錯(cuò)(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

Friday,July28,2023

2023年7月28日

信息學(xué)院(1)判斷是否棧空，若空則出錯(cuò)(2)獲取棧頂元素e(3)棧頂指針減1順序棧出棧StatusPop(SqStack&S,SElemType&e){ if(S.top==S.base)//棧空

returnERROR;

e＝*--S.top;

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

Friday,July28,2023

2023年7月28日

信息學(xué)院判斷是否空棧，若空則返回錯(cuò)誤否則通過棧頂指針獲取棧頂元素取順序棧棧頂元素StatusGetTop(SqStackS,SElemType&e){ if(S.top==S.base) returnERROR; //棧空

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

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

Friday,July28,2023

2023年7月28日

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

Friday,July28,2023

2023年7月28日

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

Friday,July28,2023

2023年7月28日

信息學(xué)院練習(xí)Ａ．top不變Ｂ．top=0Ｃ．top++Ｄ．top--D3.在一個(gè)具有n個(gè)單元的順序棧中，假設(shè)以地址高端作為棧底，以top作為棧頂指針，則當(dāng)作進(jìn)棧處理時(shí)，top的變化為

Friday,July28,2023

2023年7月28日

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

Friday,July28,2023

2023年7月28日

信息學(xué)院將編號為0和1的兩個(gè)棧存放于一個(gè)數(shù)組空間V[m]中，棧底分別處于數(shù)組的兩端。當(dāng)?shù)?號棧的棧頂指針top[0]等于-1時(shí)該棧為空，當(dāng)?shù)?號棧的棧頂指針top[1]等于m時(shí)該棧為空。兩個(gè)棧均從兩端向中間增長（如下圖所示）?？佳性囶}bot[0]top[0]top[1]bot[1]0m-1V

Friday,July28,2023

2023年7月28日

信息學(xué)院typedefstruct{ inttop[2],bot[2];//棧頂和棧底指針

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

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

Friday,July28,2023

2023年7月28日

信息學(xué)院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)棧和出棧四個(gè)算法的函數(shù)(函數(shù)定義方式如下）考研試題

Friday,July28,2023

2023年7月28日

信息學(xué)院b[0]t[0]t[1]b[1]0m-1V?？眨簍op[i]==bot[i]i表示棧的編號棧滿：top[0]+1==top[1]或top[1]-1==top[0]提示

Friday,July28,2023

2023年7月28日

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

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

datanext棧頂棧底∧S

Friday,July28,2023

2023年7月28日

信息學(xué)院鏈棧的初始化voidInitStack(LinkStack&S){

S=NULL;}∧S

Friday,July28,2023

2023年7月28日

信息學(xué)院判斷鏈棧是否為空StatusStackEmpty(LinkStackS)

{

if(S==NULL)returnTRUE;

elsereturn

FALSE;

}

Friday,July28,2023

2023年7月28日

信息學(xué)院鏈棧進(jìn)棧StatusPush(LinkStack&S,SElemTypee)

{

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

if(!p)exit(OVERFLOW);

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

returnOK;}p∧S

Friday,July28,2023

2023年7月28日

信息學(xué)院鏈棧進(jìn)棧p∧SeStatusPush(LinkStack&S,SElemTypee)

{

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

if(!p)exit(OVERFLOW);

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

returnOK;}

Friday,July28,2023

2023年7月28日

信息學(xué)院鏈棧進(jìn)棧p∧SeStatusPush(LinkStack&S,SElemTypee)

{

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

if(!p)exit(OVERFLOW);

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

returnOK;}

Friday,July28,2023

2023年7月28日

信息學(xué)院鏈棧進(jìn)棧p∧SeSStatusPush(LinkStack&S,SElemTypee)

{

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

if(!p)exit(OVERFLOW);

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

returnOK;}

Friday,July28,2023

2023年7月28日

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

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

Friday,July28,2023

2023年7月28日

信息學(xué)院鏈棧出?！腟Ae=‘A’pStatusPop(LinkStack&S,SElemType&e){if(S==NULL)returnERROR;

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

Friday,July28,2023

2023年7月28日

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

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

Friday,July28,2023

2023年7月28日

信息學(xué)院鏈棧出棧StatusPop(LinkStack&S,SElemType&e){if(S==NULL)returnERROR;

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

Friday,July28,2023

2023年7月28日

信息學(xué)院取鏈棧棧頂元素SElemTypeGetTop(LinkStackS){

if(S==NULL)exit(1)；

elsereturnS–>data;}

Friday,July28,2023

2023年7月28日

信息學(xué)院3.2棧的應(yīng)用例1：數(shù)制轉(zhuǎn)換（十轉(zhuǎn)N）用棧暫存低位值例2：括號匹配的檢驗(yàn)用棧暫存左括號例3：表達(dá)式求值用棧暫存運(yùn)算符例4：迷宮求解用棧實(shí)現(xiàn)遞歸調(diào)用簡化了程序設(shè)計(jì)的問題

Friday,July28,2023

2023年7月28日

信息學(xué)院迷宮求解

Friday,July28,2023

2023年7月28日

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

Friday,July28,2023

2023年7月28日

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

Friday,July28,2023

2023年7月28日

信息學(xué)院1、表示迷宮的數(shù)據(jù)結(jié)構(gòu)表示一個(gè)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）

迷宮求解

Friday,July28,2023

2023年7月28日

信息學(xué)院012345678901111111111110010001012100100010131000011001410111000015100010000161010001001710111011018110001000191111111111

Friday,July28,2023

2023年7月28日

信息學(xué)院迷宮的定義：#definem8

/*迷宮的實(shí)際行*/#definen8

/*迷宮的實(shí)際列*/intmaze[m+2][n+2];2、試探方向表示位置的類型PosType定義如下：typedefstruct{ intx，y;}PosType;迷宮求解

Friday,July28,2023

2023年7月28日

信息學(xué)院試探順序規(guī)定為：從正東沿順時(shí)針方向與點(diǎn)(x，y)相鄰的4個(gè)點(diǎn)及坐標(biāo)(x,y)(x,y+1)(x,y-1)(x+1,y)(x-1,y)迷宮求解

Friday,July28,2023

2023年7月28日

信息學(xué)院3、棧的設(shè)計(jì)棧中每個(gè)元素的組成：通道塊在路徑上的序號坐標(biāo)位置前進(jìn)方向（東為1，南為2，西為3，北為4）棧元素的類型定義：typedefstruct{intord;PosTypeseat;intdi;}SElemType;迷宮求解

Friday,July28,2023

2023年7月28日

信息學(xué)院4、防止重復(fù)到達(dá)某點(diǎn)走過不通之處要加以標(biāo)記（MarkPrint操作）迷宮求解算法思想及算法參見P51迷宮求解

Friday,July28,2023

2023年7月28日

信息學(xué)院表達(dá)式求值算術(shù)四則運(yùn)算規(guī)則(1)先乘除,后加減(2)從左算到右(3)先括號內(nèi),后括號外

Friday,July28,2023

2023年7月28日

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

Friday,July28,2023

2023年7月28日

信息學(xué)院>><<<>>>><<<>>>>>><>>>>>><>><<<<<=>>>>x>><<<<<=xx表3.1算符間的優(yōu)先關(guān)系

Friday,July28,2023

2023年7月28日

信息學(xué)院【算法思想】（1）初始化OPTR棧和OPND棧，將“#”壓入OPTR（2）依次讀入字符ch，循環(huán)執(zhí)行（3）至（5）（3）取出OPTR的棧頂元素，當(dāng)OPTR的棧頂元素和ch均為“#”時(shí)，表達(dá)式求值完畢，OPND棧頂元素為表達(dá)式的值設(shè)定兩棧：OPND-----操作數(shù)或運(yùn)算結(jié)果OPTR------運(yùn)算符（4）if(ch是操作數(shù))則ch進(jìn)OPND，讀入下一字符ch（5）else比較OPTR棧頂元素和ch的優(yōu)先級case‘<’:運(yùn)算符ch進(jìn)OPTR，讀入下一字符chcase‘=’:脫括號（彈出左括號），讀入下一字符chcase‘<’:棧頂運(yùn)算符退棧、計(jì)算，結(jié)果進(jìn)OPND

Friday,July28,2023

2023年7月28日

信息學(xué)院OperandTypeEvaluateExpression(){InitStack(OPND);ch=getchar();while(ch!='#'||GetTop(OPTR)!='#'){if(!In(ch,OP)){Push(OPND,ch);ch=getchar();}//ch不是運(yùn)算符則進(jìn)棧

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

case'<'://當(dāng)前字符ch壓入OPTR棧，讀入下一字符ch

Push(OPTR,ch);ch=getchar();break;

case'>'://彈出OPTR棧頂?shù)倪\(yùn)算符運(yùn)算，并將運(yùn)算結(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

Friday,July28,2023

2023年7月28日

信息學(xué)院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)

Friday,July28,2023

2023年7月28日

信息學(xué)院3.3棧與遞歸遞歸的定義若一個(gè)對象部分地包含它自己,或用它自己給自己定義,則稱這個(gè)對象是遞歸的；若一個(gè)過程直接地或間接地調(diào)用自己,則稱這個(gè)過程是遞歸的過程。

Friday,July28,2023

2023年7月28日

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

Friday,July28,2023

2023年7月28日

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

Friday,July28,2023

2023年7月28日

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

2階Fibonaci數(shù)列:

Friday,July28,2023

2023年7月28日

信息學(xué)院樹

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

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

Friday,July28,2023

2023年7月28日

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

Friday,July28,2023

2023年7月28日

信息學(xué)院分治法求解遞歸問題算法的一般形式：

voidp(參數(shù)表){

if（遞歸結(jié)束條件）可直接求解步驟；-----基本項(xiàng)

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

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

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

Friday,July28,2023

2023年7月28日

信息學(xué)院返回2

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

參數(shù)1計(jì)算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計(jì)算4*Fact(3)返回6

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

Friday,July28,2023

2023年7月28日

信息學(xué)院設(shè)有一個(gè)遞歸算法如下:intX(intn){if(n<=3)return1;

elsereturnX(n-2)+X(n-4)+1}則計(jì)算X(X(8))時(shí)需要計(jì)算X函數(shù)

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

Friday,July28,2023

2023年7月28日

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

漢諾塔

Friday,July28,2023

2023年7月28日

信息學(xué)院規(guī)則:(1)每次只能移動(dòng)一個(gè)圓盤(2)圓盤可以插在A,B和C中的任一塔座上(3)任何時(shí)刻不可將較大圓盤壓在較小圓盤之上Hanoi塔問題ABC

Friday,July28,2023

2023年7月28日

信息學(xué)院Hanoi塔問題

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

C柱做過渡，將

A的(n-1)個(gè)移到

B(2)將

A最后一個(gè)直接移到

C(3)用

A做過渡，將

B的

(n-1)個(gè)移到

C

Friday,July28,2023

2023年7月28日

信息學(xué)院#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');}跟蹤程序，給出下列程序的運(yùn)行結(jié)果，以深刻地理解遞歸的調(diào)用和返回過程

Friday,July28,2023

2023年7月28日

信息學(xué)院3,a,b,c遞歸調(diào)用樹2,a,c,b2,b,a,ca-3->c

Friday,July28,2023

2023年7月28日

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

Friday,July28,2023

2023年7月28日

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

Friday,July28,2023

2023年7月28日

信息學(xué)院程序的具體執(zhí)行過程參見：“Hanoi塔執(zhí)行過程.ppt”

Friday,July28,2023

2023年7月28日

信息學(xué)院空間效率時(shí)間效率O(2n)與遞歸樹的結(jié)點(diǎn)數(shù)成正比與遞歸樹的深度成正比O(n)遞歸算法的效率分析

Friday,July28,2023

2023年7月28日

信息學(xué)院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遞歸算法的效率分析

Friday,July28,2023

2023年7月28日

信息學(xué)院64片金片移動(dòng)次數(shù)：264-1=18446744073709551615

假如每秒鐘一次，共需多長時(shí)間呢？一年大約有31536926秒，移完這些金片需要５８００多億年世界、梵塔、廟宇和眾生都已經(jīng)灰飛煙滅

……!

Friday,July28,2023

2023年7月28日

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

Friday,July28,2023

2023年7月28日

信息學(xué)院3.4隊(duì)列

隊(duì)列是一種先進(jìn)先出(FIFO)的線性表.它只允許在表的一端進(jìn)行插入,而在另一端刪除元素a1a2a3an...入隊(duì)列隊(duì)頭隊(duì)尾

Friday,July28,2023

2023年7月28日

信息學(xué)院a1a2a3an...隊(duì)頭隊(duì)尾出隊(duì)列

Friday,July28,2023

2023年7月28日

信息學(xué)院a1a2a3an...隊(duì)頭隊(duì)尾出隊(duì)列

Friday,July28,2023

2023年7月28日

信息學(xué)院a1a2a3an...隊(duì)頭隊(duì)尾出隊(duì)列

Friday,July28,2023

2023年7月28日

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

Friday,July28,2023

2023年7月28日

信息學(xué)院數(shù)據(jù)對象:數(shù)據(jù)關(guān)系:基本操作:

(1)

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

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

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

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

Friday,July28,2023

2023年7月28日

信息學(xué)院(5)QueueLength(Q)//取隊(duì)列長度

(6)GetHead(Q,&e)//取隊(duì)頭元素,

(7)EnQueue(&Q,e)//入隊(duì)列

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

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

Friday,July28,2023

2023年7月28日

信息學(xué)院#defineM100//最大隊(duì)列長度Typedefstruct{QElemType*base;//初始化的動(dòng)態(tài)分配存儲空間

intfront;//頭指針

intrear;//尾指針}SqQueue;

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

Friday,July28,2023

2023年7月28日

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

Friday,July28,2023

2023年7月28日

信息學(xué)院Q.frontQ.rearJ5J6Q.front012345Q.rearJ5J6J1J2J3J4存在的問題設(shè)數(shù)組大小為Mfront=0rear=M時(shí)再入隊(duì)——真溢出front0rear=M時(shí)再入隊(duì)——假溢出

Friday,July28,2023

2023年7月28日

信息學(xué)院解決的方法－－循環(huán)隊(duì)列10Q.rearQ.front......base[0]接在base[M-1]之后若rear+1==M則令rear=0;實(shí)現(xiàn)：利用“?！边\(yùn)算入隊(duì)：

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

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

Friday,July28,2023

2023年7月28日

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

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

Friday,July28,2023

2023年7月28日

信息學(xué)院循環(huán)隊(duì)列#defineMAXQSIZE100//最大隊(duì)列長度Typedefstruct{QElemType*base;//初始化的動(dòng)態(tài)分配存儲空間

intfront;//頭指針

intrear;//尾指針}SqQueue;

Friday,July28,2023

2023年7月28日

信息學(xué)院StatusInitQueue(SqQueue&Q){

Q.base=newQElemType[MAXQSIZE]

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

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

Friday,July28,2023

2023年7月28日

信息學(xué)院求循環(huán)隊(duì)列的長度intQueueLength(SqQueueQ){

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

}

Friday,July28,2023

2023年7月28日

信息學(xué)院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)隊(duì)列入隊(duì)

Friday,July28,2023

2023年7月28日

信息學(xué)院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)隊(duì)列出隊(duì)

Friday,July28,2023

2023年7月28日

信息學(xué)院...datanext隊(duì)頭隊(duì)尾Q.frontQ.rear鏈隊(duì)列

Friday,July28,2023

2023年7月28日

信息學(xué)院typedefstructQNode{QElemTypedata;structQnode*next;}Qnode,*QueuePtr;typedefstruct{QueuePtrfront;//隊(duì)頭指針

QueuePtrrear;//隊(duì)尾指針}LinkQueue;

鏈隊(duì)列

Friday,July28,2023

2023年7月28日

信息學(xué)院(a)空隊(duì)列(b)元素x入隊(duì)列(d)元素x出隊(duì)列(c)元素y入隊(duì)列鏈隊(duì)列

Friday,July28,2023

2023年7月28日

信息學(xué)院StatusInitQueue(LinkQueue&Q){

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

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

Friday,July28,2023

2023年7月28日

信息學(xué)院StatusDestroyQueue(LinkQueue&Q){while(Q.front){

Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}returnOK;}銷毀鏈隊(duì)列

Friday,July28,2023

2023年7月28日

信息學(xué)院StatusQueueEmpty(LinkQueueQ){return(Q.front==Q.rear);}判斷鏈隊(duì)列是否為空

Friday,July28,2023

2023年7月28日

信息學(xué)院StatusGetHead(LinkQueueQ,QElemType&e){if(Q.front==Q.rear)returnERROR;

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

Friday,July28,2023

2023年7月28日

信息學(xué)院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;}鏈隊(duì)列入隊(duì)p

Friday,July28,2023

2023年7月28日

信息學(xué)院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;free(p);returnOK;}鏈隊(duì)列出隊(duì)p

Friday,July28,2023

2023年7月28日

信息學(xué)院【例】汽車加油站

隨著城市里汽車數(shù)量的急速增長，汽車加油站也漸漸多了起來。通常汽車加油站的結(jié)構(gòu)基本上是：入口和出口為單行道，加油車道可能有若干條。每輛車加油都要經(jīng)過三段路程，第一段是在入口處排隊(duì)等候進(jìn)入加油車道；第二段是在加油車道排隊(duì)等候加油；第三段是進(jìn)入出口處排隊(duì)等候離開。實(shí)際上，這三段都是隊(duì)列結(jié)構(gòu)。若用算法模擬這個(gè)過程，就需要設(shè)置加油車道數(shù)加2個(gè)隊(duì)列。3.5隊(duì)列的應(yīng)用

Friday,July28,2023

2023年7月28日

信息學(xué)院【例】模擬打印機(jī)緩沖區(qū)

在主機(jī)將數(shù)據(jù)輸出到打印機(jī)時(shí)，會出現(xiàn)主機(jī)速度與打印機(jī)的打印速度不匹配的問題。這時(shí)主機(jī)就要停下來等待打印機(jī)。顯然，這樣會降低主機(jī)的使用效率。為此人們設(shè)想了一種辦法：為打印機(jī)設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，當(dāng)主機(jī)需要打印數(shù)據(jù)時(shí)，先將數(shù)據(jù)依次寫入這個(gè)緩沖區(qū)，寫滿后主機(jī)轉(zhuǎn)去做其他的事情，而打印機(jī)就從緩沖區(qū)中按照先進(jìn)先出的原則依次讀取數(shù)據(jù)并打印，這樣做即保證了打印數(shù)據(jù)的正確性，又提高了主機(jī)的使用效率。由此可見，打印機(jī)緩沖區(qū)實(shí)際上就是一個(gè)隊(duì)列結(jié)構(gòu)。

Friday,July28,2023

2023年7月28日

信息學(xué)院【例】CPU分時(shí)系統(tǒng)

在一個(gè)帶有多個(gè)終端的計(jì)算機(jī)系統(tǒng)中，同時(shí)有多個(gè)用戶需要使用CPU運(yùn)行各自的應(yīng)用程序，它們分別通過各自