棧和隊列課件

第三章棧和隊列棧棧的存儲結構及應用隊列隊列的存儲結構及應用第三章棧和隊列棧棧的基本概念定義數據元素之間是一對一的關系順序存儲或鏈式存儲只能在棧頂運算，且訪問結點時依照后進先出（LIFO）或先進后出（FILO）的原則存儲結構運算規(guī)則邏輯結構只能在表的一端進行插入和刪除的線性表基本操作建棧、判斷棧滿或棧空、入棧、出棧、取棧頂元素值棧的基本概念定義數據元素之間是一對一的關系順序存儲或鏈棧的示意圖棧是僅在表尾進行插入、刪除操作的線性表表尾(即an端)稱為棧頂(top)

表頭(即a1端)稱為棧底(bottom)插入元素到棧頂的操作，稱為入棧從棧頂刪除元素的操作，稱為出棧棧S=(a1,a2,a3,……….,an-1,an)棧頂元素棧底元素插入和刪除都只在表的一端（棧頂）進行棧的示意圖棧是僅在表尾進行插入、刪除操作的線性表棧S=棧的基本操作INISTACK(S)：初始化操作。設置一個空棧S。EMPTY(S)：判?？蘸瘮?。若S為空棧，函數值為1，否則為0SIZE(S)：求棧深函數。函數值為棧中當前的元素個數。TOP(S)：讀棧頂元函數。若棧S不空，函數值為棧頂元素，否則為空元素NULL。PUSH(S,x)：進棧操作。將元素x插入棧S中，使x成為棧S的棧頂元素。POP(S):出棧函數。若棧S不空，函數值為棧頂元素，且從棧中刪除當前棧頂元素，否則函數值為空元素NULL。CLEAR(S):棧置空操作。不論棧S是否為空棧，將S置為空棧棧的基本操作INISTACK(S)：初始化操作。設置一個空35178421011001余數結果：10011十進制數轉換成二進制數把所有的余數按出現的逆序排列起來（先出現的余數排在后面，后出現的余數排在前面）,十進制數35轉換成二進制數

3517842101余數結果：10011十進制數轉換成二進制將帶頭結點的單鏈表（a1,a2,…,an）逆置將帶頭結點的單鏈表（a1,a2,…,an）逆置

棧的順序存儲結構(順序棧)順序棧:利用一組地址連續(xù)的存儲單元依次存放從棧底到棧頂的數據元素C語言中預設較大的數組空間棧底設為0棧頂隨插入和刪除元素而變化用一個整型變量top來指示棧頂的位置a1a2……an順序棧Sai……0n棧底棧頂top壓入(PUSH):

S[top++]=an+1彈出(POP):e=S[--top]棧的順序存儲結構(順序棧)順序棧:利用一組地址連續(xù)的存儲順序棧存儲結構的描述#defineMAXSIZE100typedefintelemtype;typedefstructstack{elemtypeelem[MAXSIZE];inttop；//棧頂指針}sqstacktp；//順序棧類型定義sqstacktp*s；//s為順序棧類型變量的指針s=(sqstacktp*)malloc(sizeof(sqstacktp));順序棧存儲結構的描述#defineMAXSIZE100123450?？諚ｍ斨羔榯op,可初始化為0，指向實際棧頂后的空位置.top123450進棧Atop出棧BCDEF設數組大小為MAXSIZEs->top=0,?？?，此時出棧則下溢s->top=MAXSIZE,棧滿，此時入棧上溢toptoptoptoptop123450ABCDEFtoptoptoptoptoptoptop設MAXSIZE=6順序棧的幾種情況棧空棧滿top123450?？諚ｍ斨羔榯op,可初始化為0，指向實際棧頂后順序棧上實現的操作初始化（棧置空）操作voidini_sqstack(sqstacktp*s)；判?？蘸瘮礽ntempty_sqstack(sqstacktp*s)；進棧操作voidpush_sqstack(sqstacktp*s，elemtypex)；出棧函數elemtypepop_sqstack(sqstacktp*s)；求棧深函數intsize_sqstack(sqstacktp*s)；讀棧頂元函數elemtypetop_sqstack(sqstacktp*s)；順序棧上實現的操作初始化（棧置空）操作棧的鏈式存儲結構定義棧的鏈式存儲結構，簡稱鏈棧組織形式與單鏈表類似，鏈表的尾部是棧底，鏈表的頭部是棧頂棧的鏈式存儲結構定義FtopdatanextEDANULL棧頂棧底棧的鏈式存儲結構鏈棧的類型定義：typedefstructstacknode{elemtypedata；structstacknode*next；}stacknode;typedefstruct{stacknode*top;

//棧頂指針

}linkstack;linkstack*ls;ls=(linkstack*)malloc(sizeof(linkstack));ls->top=?FtopdatanextEDANULL棧頂棧底棧的鏈式存儲結初始化操作voidinit_linkstack(linkstack*ls)；進棧操作voidpush_linkstack(linkstack*ls,elemtypex)；出棧操作elemtypepop_linkstack(linkstack*ls)；鏈棧上實現的操作初始化操作鏈棧上實現的操作對算術表達式求值：

1+2*4-9/3遵循先乘除后加減、先左后右及先括號內，后括號外的四則運算法則，其計算順序應為：1+2*4-9/3└─┘└┘①②└─┘③└───┘④棧的應用實例—表達式求值采用“運算符優(yōu)先數法”對每種運算符賦于一個優(yōu)先數，如：運算符：*/+-#優(yōu)先數：22110其中#是表達式結束符對表達式求值時，一般設立兩個棧運算符棧（OPTR)操作數棧(OPND)分別存放表達式中的運算符和操作數對算術表達式求值：棧的應用實例—表達式求值采用“運算符優(yōu)先數

步驟OPTR棧OPND棧輸入字符主要操作

──────────────────────────1#1+2*4-9/3#PUSH(OPND,'1')2#1+2*4-9/3#PUSH(OPTR,'+')3#+12*4-9/3#PUSH(OPND,'2')4#+12*4-9/3#PUSH(OPTR,'*')5#+*124-9/3#PUSH(OPND,'4')6#+*124-9/3#operate('2','*','4')7#+18-9/3#operate('1','+','8')8#9-9/3#PUSH(OPTR,'-')9#-99/3#PUSH(OPND,'9')10#-99/3#PUSH(OPTR,'/')11#-/993#PUSH(OPND,'3')12#-/993#operate('9','/','3')13#-93#operate('9','-','3')14#6#RETURN(TOP(OPND))

利用算法對算術表達式求值的操作過程步驟OPTR棧OPND棧棧在回溯法中的應用在某些問題的求解過程中常常采用試探方法，當某一路徑受阻時，需要逆序退回，重新選擇新路徑，這樣必須用棧記錄曾經到達的每一狀態(tài)，棧頂狀態(tài)即是回退的第一站。

棧在回溯法中的應用在某些問題的求解過程中常常采用試探方法，當地圖四染色問題“四染色”定理可以用不多于四色對地圖著色，使相鄰的地區(qū)不重色算法思想：“回溯”法從第一號地區(qū)開始逐一染色，每一個地區(qū)逐次用色數1、2、3、4進行試探若當前所取的色數與周圍已染色的地區(qū)不重色，則用棧記下該地區(qū)的色數，否則依次用下一色數進行試探若出現用1..4色均與相鄰地區(qū)發(fā)生重色，則需退?；厮?，修改當前棧頂的色數。地圖四染色問題“四染色”定理地圖四染色問題算法實現“四染色”定理數據結構graph[n][n]n*n的關系矩陣grph[i][j]=0表示地區(qū)i與地區(qū)j不相鄰graph[i][j]=1表示地區(qū)i與地區(qū)j相鄰。color[n]顏色表：順序存儲color[i]表示i號地區(qū)的染色數。地圖四染色問題算法實現“四染色”定理(1)(2)(4)(5)(6)(7)(3)r[7][7]12345671234567100001001111101010110101101011011001001100000000012345671223414334231#紫色2#黃色3#紅色4#

綠色地圖四染色算法(1)(2)(4)(5)(6)(7)(3)r[7][棧與函數調用由于程序設計都采用模塊化程序設計方法，模塊（函數、過程）是完成功能相對獨立的一個程序段，在主函數（主程序）中調用模塊來解決復雜的實際問題由于函數調用后，需返回調用處，所以，在調用時，需用棧記錄斷點的地址以及有關信息，以便返回。

棧與函數調用由于程序設計都采用模塊化程序設計方法，模塊（函數棧的應用-函數調用intfunc_B(intx,inty){intz;z=x+y;returnz;}intfunc_A(){intx=10,y=20,k;k=func_B(x,y);returnk;}voidmain(){printf(“%d”,func_A());}棧的應用-函數調用intfunc_B(intx,int函數調用函數調用棧與函數堆棧是存儲器的一個區(qū)域編譯器一般使用堆棧實現函數調用函數占用的區(qū)域被稱作函數的棧幀函數調用時，為被調用的函數分配棧幀，存放函數的參數、局部變量等信息函數嵌套調用時，堆棧中會同時存在多個函數的棧幀，每個函數占用一個連續(xù)的區(qū)域棧與函數堆棧是存儲器的一個區(qū)域函數獨占自己的棧幀空間當前正在運行的函數的棧幀總是在棧頂兩個特殊的寄存器ESP，EBP棧與函數棧幀中的信息局部變量棧幀狀態(tài)值保存前一棧幀的頂部和底部函數返回地址保存函數調用前的指令位置函數獨占自己的棧幀空間棧與函數棧幀中的信息棧與函數棧與函數r主程序srrrs子過程1rst子過程2rst子過程3棧與函數調用的圖示r主程序srrrs子過程1rst子過程2rst子過程3棧與函遞歸的定義若一個對象部分地包含它自己,或用它自己給自己定義,則稱這個對象是遞歸的二叉樹是結點的有限集合，這個集合或者是空的，或者由一個根結點或兩棵互不相交的稱為左子樹的和右子樹的二叉樹組成若一個過程直接地或間接地調用自己,則稱這個過程是遞歸的過程。遞歸的定義若一個對象部分地包含它自己,或用它自己給自己定義,直接遞歸fun_a(){

…

fun_a()

…}間接遞歸fun_a(){

…

fun_b()

…}fun_b(){

…

fun_a()

…}遞歸的定義直接遞歸間接遞歸fun_b()遞歸的定義遞歸條件解決問題時，可以把一個問題轉化為一個新的問題，這個新問題的解決方法，與原問題的解法相同，只是所處理的對象有所不同。這些被處理的對象之間有規(guī)律的遞增或遞減要有一個明確的結束遞歸的條件，否則遞歸將會無止境地進行下去，直到耗盡系統(tǒng)資源.必須要有終止遞歸的條件遞歸條件解決問題時，可以把一個問題轉化為一個新的問題，這個新適用遞歸技術的問題以下三種情況常常用到遞歸方法定義是遞歸的數據結構是遞歸的問題的解法是遞歸的適用遞歸技術的問題以下三種情況常常用到遞歸方法求解階乘函數的遞歸算法longFactorial(longn){if(n==0)return1;elsereturnn*Factorial(n-1);}例如，階乘函數定義是遞歸的求解階乘函數的遞歸算法例如，階乘函數定義是遞歸的例如，單鏈表結構ff數據結構是遞歸的一個結點，它的指針域為NULL，是一個單鏈表一個結點，它的指針域指向單鏈表，仍是一個單鏈表例如，單鏈表結構ff數據結構是遞歸的一個結點，它的打印單鏈表最后一個結點的值voidPrint(ListNode*f){if(f->link==NULL)

printf(“%d\n”,f->data);elsePrint(f->link);}ffffa0a1a2a3a4f遞歸找鏈尾數據結構是遞歸的打印單鏈表最后一個結點的值ffffa0a1a2a313

321312212313源中間目的123源中間目的64個abcmove(n,a,b,c)move(n-1,a,c,b)acmove(n-1,b,a,c)64個64個問題的解法是遞歸的13321312212313源第三章棧和隊列課件hanoi(3,1,2,3)n=3a=1b=2c=3hanoi(n-1,a,c,b); move(a,c); hanoi(n-1,b,a,c);hanoi(2,1,3,2)n=2a=1b=3c=2hanoi(n-1,a,c,b); move(a,c); hanoi(n-1,b,a,c);hanoi(1,1,2,3)n=1a=1b=2c=3

move(a,c);1->31->21->3hanoi(1,3,1,2)n=1a=3b=1c=2move(a,c);3->2hanoi(2,2,1,3)n=2a=2b=1c=3hanoi(n-1,a,c,b); move(a,c); hanoi(n-1,b,a,c);hanoi(1,2,3,1)n=1a=2b=3c=1move(a,c);2->12->3hanoi(1,1,2,3)n=1a=1b=2c=3move(a,c);1->3voidhanoi(intn,inta,intb,intc){if(n==1) move(a,c);else{hanoi(n-1,a,c,b); move(a,c); hanoi(n-1,b,a,c); }}1->31->23->22->12->31->31->3hanoi(3,1,2,3)n=3a=1b=2c=3h遞歸模型遞歸是把一個不能或不好直接求解的“大問題”轉化為一個或幾個“小問題”再把這些“小問題”進一步分解成更小的“小問題”來解決直到遞歸出口為止遞歸模型反映一個遞歸問題的遞歸結構遞歸模型由遞歸出口和遞歸體兩部分組成前者確定遞歸到何時為止后者確定遞歸的方式遞歸模型遞歸是把一個不能或不好直接求解的“大問題”轉化為一遞歸模型遞歸出口的一般格式為f(s0)=m0這里的s0與m0均為常量，有的遞歸問題可能有幾個遞歸出口。遞歸體的一般格式為f(s)=g(f(s1),f(s2),……,f(sn),c1,c2,……，cm)s是一個遞歸“大問題”s1,s2,……,sn是遞歸“小問題”c1,c2,……，cm是若干個可以直接（用非遞歸方法）解決的問題g是一個非遞歸函數，反映了遞歸問題的結構。遞歸模型遞歸出口的一般格式為遞歸模型例如，階乘函數遞歸出口遞歸體遞歸模型例如，階乘函數遞歸出口遞歸體主程序main:fact(4)參數4計算4*fact(3)

參數3計算3*fact(2)

參數2計算2*fact(1)

參數1計算1*fact(0)參數0直接定值=1

參數傳遞結果返回遞歸調用回歸求值求解n!的過程返回1返回1返回2返回6返回24主程序main:fact(4)參數4計算4運行結果：1，2，2，3，3，3，遞歸過程與遞歸工作棧voidprint(intw){inti;if(w!=0){print(w-1);for(i=1;i<=w;++i)printf(“%3d,”,w);printf(“/n”);}}運行結果：遞歸過程與遞歸工作棧voidprint(i主程序(1)print(w)w=3;3print(2);（1）w=3top(2)輸出：3,3,3w2print(1)（2）w=2（1）w=3top(3)輸出：2,2w1print(0);（3）w=1（2）w=2（1）w=3top(4)輸出：1w0（4）w=0（3）w=1（2）w=2（1）w=3topw(3)輸出：2,2(2)2(1)3top(4)輸出：1(3)1(2)2(1)3top(2)輸出：3,3,3(1)3top返回(3)1(2)2(1)3top(4)0結束(1)遞歸調用執(zhí)行情況如下主程序(1)print(w)w=3;3print(2);遞歸算法的非遞歸描述intfac(intn){if(n==1)return1;else returnn*fac(n-1);}voidmain(){ fac(4);}intfac(intn){ints=1;while(n>=1) push(stack,n--);while(!empty(stack))s*=pop(stack);returns;}voidmain(){ fac(4);}遞歸算法的非遞歸描述intfac(intn)intfa棧和隊列棧和隊列的概念棧和隊列的存儲結構及它們的應用棧和隊列與線性表有著密切的聯(lián)系棧和隊列棧和隊列的概念第三章棧和隊列棧棧的存儲結構及應用隊列隊列的存儲結構及應用第三章棧和隊列棧棧的基本概念定義數據元素之間是一對一的關系順序存儲或鏈式存儲只能在棧頂運算，且訪問結點時依照后進先出（LIFO）或先進后出（FILO）的原則存儲結構運算規(guī)則邏輯結構只能在表的一端進行插入和刪除的線性表基本操作建棧、判斷棧滿或?？?、入棧、出棧、取棧頂元素值棧的基本概念定義數據元素之間是一對一的關系順序存儲或鏈棧的示意圖棧是僅在表尾進行插入、刪除操作的線性表表尾(即an端)稱為棧頂(top)

表頭(即a1端)稱為棧底(bottom)插入元素到棧頂的操作，稱為入棧從棧頂刪除元素的操作，稱為出棧棧S=(a1,a2,a3,……….,an-1,an)棧頂元素棧底元素插入和刪除都只在表的一端（棧頂）進行棧的示意圖棧是僅在表尾進行插入、刪除操作的線性表棧S=棧的基本操作INISTACK(S)：初始化操作。設置一個空棧S。EMPTY(S)：判棧空函數。若S為空棧，函數值為1，否則為0SIZE(S)：求棧深函數。函數值為棧中當前的元素個數。TOP(S)：讀棧頂元函數。若棧S不空，函數值為棧頂元素，否則為空元素NULL。PUSH(S,x)：進棧操作。將元素x插入棧S中，使x成為棧S的棧頂元素。POP(S):出棧函數。若棧S不空，函數值為棧頂元素，且從棧中刪除當前棧頂元素，否則函數值為空元素NULL。CLEAR(S):棧置空操作。不論棧S是否為空棧，將S置為空棧棧的基本操作INISTACK(S)：初始化操作。設置一個空35178421011001余數結果：10011十進制數轉換成二進制數把所有的余數按出現的逆序排列起來（先出現的余數排在后面，后出現的余數排在前面）,十進制數35轉換成二進制數

3517842101余數結果：10011十進制數轉換成二進制將帶頭結點的單鏈表（a1,a2,…,an）逆置將帶頭結點的單鏈表（a1,a2,…,an）逆置

棧的順序存儲結構(順序棧)順序棧:利用一組地址連續(xù)的存儲單元依次存放從棧底到棧頂的數據元素C語言中預設較大的數組空間棧底設為0棧頂隨插入和刪除元素而變化用一個整型變量top來指示棧頂的位置a1a2……an順序棧Sai……0n棧底棧頂top壓入(PUSH):

S[top++]=an+1彈出(POP):e=S[--top]棧的順序存儲結構(順序棧)順序棧:利用一組地址連續(xù)的存儲順序棧存儲結構的描述#defineMAXSIZE100typedefintelemtype;typedefstructstack{elemtypeelem[MAXSIZE];inttop；//棧頂指針}sqstacktp；//順序棧類型定義sqstacktp*s；//s為順序棧類型變量的指針s=(sqstacktp*)malloc(sizeof(sqstacktp));順序棧存儲結構的描述#defineMAXSIZE100123450?？諚ｍ斨羔榯op,可初始化為0，指向實際棧頂后的空位置.top123450進棧Atop出棧BCDEF設數組大小為MAXSIZEs->top=0,?？眨藭r出棧則下溢s->top=MAXSIZE,棧滿，此時入棧上溢toptoptoptoptop123450ABCDEFtoptoptoptoptoptoptop設MAXSIZE=6順序棧的幾種情況棧空棧滿top123450?？諚ｍ斨羔榯op,可初始化為0，指向實際棧頂后順序棧上實現的操作初始化（棧置空）操作voidini_sqstack(sqstacktp*s)；判?？蘸瘮礽ntempty_sqstack(sqstacktp*s)；進棧操作voidpush_sqstack(sqstacktp*s，elemtypex)；出棧函數elemtypepop_sqstack(sqstacktp*s)；求棧深函數intsize_sqstack(sqstacktp*s)；讀棧頂元函數elemtypetop_sqstack(sqstacktp*s)；順序棧上實現的操作初始化（棧置空）操作棧的鏈式存儲結構定義棧的鏈式存儲結構，簡稱鏈棧組織形式與單鏈表類似，鏈表的尾部是棧底，鏈表的頭部是棧頂棧的鏈式存儲結構定義FtopdatanextEDANULL棧頂棧底棧的鏈式存儲結構鏈棧的類型定義：typedefstructstacknode{elemtypedata；structstacknode*next；}stacknode;typedefstruct{stacknode*top;

//棧頂指針

}linkstack;linkstack*ls;ls=(linkstack*)malloc(sizeof(linkstack));ls->top=?FtopdatanextEDANULL棧頂棧底棧的鏈式存儲結初始化操作voidinit_linkstack(linkstack*ls)；進棧操作voidpush_linkstack(linkstack*ls,elemtypex)；出棧操作elemtypepop_linkstack(linkstack*ls)；鏈棧上實現的操作初始化操作鏈棧上實現的操作對算術表達式求值：

1+2*4-9/3遵循先乘除后加減、先左后右及先括號內，后括號外的四則運算法則，其計算順序應為：1+2*4-9/3└─┘└┘①②└─┘③└───┘④棧的應用實例—表達式求值采用“運算符優(yōu)先數法”對每種運算符賦于一個優(yōu)先數，如：運算符：*/+-#優(yōu)先數：22110其中#是表達式結束符對表達式求值時，一般設立兩個棧運算符棧（OPTR)操作數棧(OPND)分別存放表達式中的運算符和操作數對算術表達式求值：棧的應用實例—表達式求值采用“運算符優(yōu)先數

步驟OPTR棧OPND棧輸入字符主要操作

──────────────────────────1#1+2*4-9/3#PUSH(OPND,'1')2#1+2*4-9/3#PUSH(OPTR,'+')3#+12*4-9/3#PUSH(OPND,'2')4#+12*4-9/3#PUSH(OPTR,'*')5#+*124-9/3#PUSH(OPND,'4')6#+*124-9/3#operate('2','*','4')7#+18-9/3#operate('1','+','8')8#9-9/3#PUSH(OPTR,'-')9#-99/3#PUSH(OPND,'9')10#-99/3#PUSH(OPTR,'/')11#-/993#PUSH(OPND,'3')12#-/993#operate('9','/','3')13#-93#operate('9','-','3')14#6#RETURN(TOP(OPND))

利用算法對算術表達式求值的操作過程步驟OPTR棧OPND棧棧在回溯法中的應用在某些問題的求解過程中常常采用試探方法，當某一路徑受阻時，需要逆序退回，重新選擇新路徑，這樣必須用棧記錄曾經到達的每一狀態(tài)，棧頂狀態(tài)即是回退的第一站。

棧在回溯法中的應用在某些問題的求解過程中常常采用試探方法，當地圖四染色問題“四染色”定理可以用不多于四色對地圖著色，使相鄰的地區(qū)不重色算法思想：“回溯”法從第一號地區(qū)開始逐一染色，每一個地區(qū)逐次用色數1、2、3、4進行試探若當前所取的色數與周圍已染色的地區(qū)不重色，則用棧記下該地區(qū)的色數，否則依次用下一色數進行試探若出現用1..4色均與相鄰地區(qū)發(fā)生重色，則需退棧回溯，修改當前棧頂的色數。地圖四染色問題“四染色”定理地圖四染色問題算法實現“四染色”定理數據結構graph[n][n]n*n的關系矩陣grph[i][j]=0表示地區(qū)i與地區(qū)j不相鄰graph[i][j]=1表示地區(qū)i與地區(qū)j相鄰。color[n]顏色表：順序存儲color[i]表示i號地區(qū)的染色數。地圖四染色問題算法實現“四染色”定理(1)(2)(4)(5)(6)(7)(3)r[7][7]12345671234567100001001111101010110101101011011001001100000000012345671223414334231#紫色2#黃色3#紅色4#

綠色地圖四染色算法(1)(2)(4)(5)(6)(7)(3)r[7][棧與函數調用由于程序設計都采用模塊化程序設計方法，模塊（函數、過程）是完成功能相對獨立的一個程序段，在主函數（主程序）中調用模塊來解決復雜的實際問題由于函數調用后，需返回調用處，所以，在調用時，需用棧記錄斷點的地址以及有關信息，以便返回。

棧與函數調用由于程序設計都采用模塊化程序設計方法，模塊（函數棧的應用-函數調用intfunc_B(intx,inty){intz;z=x+y;returnz;}intfunc_A(){intx=10,y=20,k;k=func_B(x,y);returnk;}voidmain(){printf(“%d”,func_A());}棧的應用-函數調用intfunc_B(intx,int函數調用函數調用棧與函數堆棧是存儲器的一個區(qū)域編譯器一般使用堆棧實現函數調用函數占用的區(qū)域被稱作函數的棧幀函數調用時，為被調用的函數分配棧幀，存放函數的參數、局部變量等信息函數嵌套調用時，堆棧中會同時存在多個函數的棧幀，每個函數占用一個連續(xù)的區(qū)域棧與函數堆棧是存儲器的一個區(qū)域函數獨占自己的棧幀空間當前正在運行的函數的棧幀總是在棧頂兩個特殊的寄存器ESP，EBP棧與函數棧幀中的信息局部變量棧幀狀態(tài)值保存前一棧幀的頂部和底部函數返回地址保存函數調用前的指令位置函數獨占自己的棧幀空間棧與函數棧幀中的信息棧與函數棧與函數r主程序srrrs子過程1rst子過程2rst子過程3棧與函數調用的圖示r主程序srrrs子過程1rst子過程2rst子過程3棧與函遞歸的定義若一個對象部分地包含它自己,或用它自己給自己定義,則稱這個對象是遞歸的二叉樹是結點的有限集合，這個集合或者是空的，或者由一個根結點或兩棵互不相交的稱為左子樹的和右子樹的二叉樹組成若一個過程直接地或間接地調用自己,則稱這個過程是遞歸的過程。遞歸的定義若一個對象部分地包含它自己,或用它自己給自己定義,直接遞歸fun_a(){

…

fun_a()

…}間接遞歸fun_a(){

…

fun_b()

…}fun_b(){

…

fun_a()

…}遞歸的定義直接遞歸間接遞歸fun_b()遞歸的定義遞歸條件解決問題時，可以把一個問題轉化為一個新的問題，這個新問題的解決方法，與原問題的解法相同，只是所處理的對象有所不同。這些被處理的對象之間有規(guī)律的遞增或遞減要有一個明確的結束遞歸的條件，否則遞歸將會無止境地進行下去，直到耗盡系統(tǒng)資源.必須要有終止遞歸的條件遞歸條件解決問題時，可以把一個問題轉化為一個新的問題，這個新適用遞歸技術的問題以下三種情況常常用到遞歸方法定義是遞歸的數據結構是遞歸的問題的解法是遞歸的適用遞歸技術的問題以下三種情況常常用到遞歸方法求解階乘函數的遞歸算法longFactorial(longn){if(n==0)return1;elsereturnn*Factorial(n-1);}例如，階乘函數定義是遞歸的求解階乘函數的遞歸算法例如，階乘函數定義是遞歸的例如，單鏈表結構ff數據結構是遞歸的一個結點，它的指針域為NULL，是一個單鏈表一個結點，它的指針域指向單鏈表，仍是一個單鏈表例如，單鏈表結構ff數據結構是遞歸的一個結點，它的打印單鏈表最后一個結點的值voidPrint(ListNode*f){if(f->link==NULL)

printf(“%d\n”,f->data);elsePrint(f->link);}ffffa0a1a2a3a4f遞歸找鏈尾數據結構是遞歸的打印單鏈表最后一個結點的值ffffa0a1a2a313

321312212313源中間目的123源中間目的64個abcmove(n,a,b,c)move(n-1,a,c,b)acmove(n-1,b,a,c)64個64個問題的解法是遞歸的13321312212313源第三章棧和隊列課件hanoi(3,1,2,3)n=3a=1b=2c=3hanoi(n-1,a,c,b); move(a,c); hanoi(n-1,b,a,c);hanoi(2,1,3,2)n=2a=1b=3c=2hanoi(n-1,a,c,b); move(a,c); hanoi(n-1,b,a,c);hanoi(1,1,2,3)n=1a=1b=2c=3

move(a,c);1->31->21->3hanoi(1,3,1,2)n=1a=3b=1c=2move(a,c);3->2hanoi(2,2,1,3)n=2a=2b=1c=3hanoi(n-1,a,c,b); move(a,c); hanoi(n-1,b,a,c);hanoi(1,2,3,1)n=1a=2b=3c=1move(a,c);2->12->3hanoi(1,1,2,3)n=1a=1b=2c=3move(a,c);1->3voidha