C語言基礎(chǔ)課件1第3章 棧

棧的基本概念定義數(shù)據(jù)元素之間是一對(duì)一的關(guān)系

順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)

只能在棧頂運(yùn)算，且訪問結(jié)點(diǎn)時(shí)依照后進(jìn)先出（LIFO）或先進(jìn)后出（FILO）的原則存儲(chǔ)結(jié)構(gòu)運(yùn)算規(guī)則邏輯結(jié)構(gòu)只能在表的一端進(jìn)行插入和刪除的線性表基本操作建棧、判斷棧滿或棧空、入棧、出棧、取棧頂元素值棧的示意圖棧是僅在表尾進(jìn)行插入、刪除操作的線性表表尾(即an端)稱為棧頂(top)

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

將帶頭結(jié)點(diǎn)的單鏈表（a1,a2,…,an）逆置

棧的順序存儲(chǔ)結(jié)構(gòu)(順序棧)順序棧:利用一組地址連續(xù)的存儲(chǔ)單元依次存放從棧底到棧頂?shù)臄?shù)據(jù)元素C語言中預(yù)設(shè)較大的數(shù)組空間棧底設(shè)為0棧頂隨插入和刪除元素而變化用一個(gè)整型變量top來指示棧頂?shù)奈恢胊1a2……an順序棧Sai……0n棧底棧頂top壓入(PUSH):

S[top++]=an+1彈出(POP):e=S[--top]順序棧存儲(chǔ)結(jié)構(gòu)的描述#defineMAXSIZE100typedefintelemtype;typedefstructstack{elemtypeelem[MAXSIZE];inttop；//棧頂指針}sqstacktp；//順序棧類型定義sqstacktp*s；

//s為順序棧類型變量的指針s=(sqstacktp*)malloc(sizeof(sqstacktp));123450?？諚ｍ斨羔榯op,可初始化為0，指向?qū)嶋H棧頂后的空位置.top123450進(jìn)棧Atop出棧BCDEF設(shè)數(shù)組大小為MAXSIZEs->top==0,?？眨藭r(shí)出棧則下溢s->top==MAXSIZE,棧滿，此時(shí)入棧上溢toptoptoptoptop123450ABCDEFtoptoptoptoptoptoptop設(shè)MAXSIZE=6順序棧的幾種情況棧空棧滿top順序棧上實(shí)現(xiàn)的操作初始化（棧置空）操作voidini_sqstack(sqstacktp*s)；判棧空函數(shù)intempty_sqstack(sqstacktp*s)；進(jìn)棧操作voidpush_sqstack(sqstacktp*s，elemtypex)；出棧函數(shù)elemtypepop_sqstack(sqstacktp*s)；求棧深函數(shù)intsize_sqstack(sqstacktp*s)；讀棧頂元函數(shù)elemtypetop_sqstack(sqstacktp*s)；棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)定義棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，簡稱鏈棧組織形式與單鏈表類似，鏈表的尾部是棧底，鏈表的頭部是棧頂FtopdatanextEDANULL棧頂棧底棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈棧的類型定義：typedefstructstacknode{elemtypedata；

structstacknode*next；

}stacknode;typedefstruct{stacknode*top;

//棧頂指針

}linkstack;linkstack*ls;ls=(linkstack*)malloc(sizeof(linkstack));ls->top=?初始化操作voidinit_linkstack(linkstack*ls)；

進(jìn)棧操作voidpush_linkstack(linkstack*ls,elemtypex)；出棧操作elemtypepop_linkstack(linkstack*ls)；鏈棧上實(shí)現(xiàn)的操作對(duì)算術(shù)表達(dá)式求值：

1+2*4-9/3遵循先乘除后加減、先左后右及先括號(hào)內(nèi)，后括號(hào)外的四則運(yùn)算法則，其計(jì)算順序應(yīng)為：1+2*4-9/3└─┘└┘①②└─┘③└───┘④棧的應(yīng)用實(shí)例—表達(dá)式求值采用“運(yùn)算符優(yōu)先數(shù)法”對(duì)每種運(yùn)算符賦于一個(gè)優(yōu)先數(shù)，如：運(yùn)算符：*/+-#優(yōu)先數(shù)：22110其中#是表達(dá)式結(jié)束符對(duì)表達(dá)式求值時(shí)，一般設(shè)立兩個(gè)棧運(yùn)算符棧（OPTR)操作數(shù)棧(OPND)分別存放表達(dá)式中的運(yùn)算符和操作數(shù)？擴(kuò)展：多位數(shù)、（）

步驟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))

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

地圖四染色問題“四染色”定理可以用不多于四色對(duì)地圖著色，使相鄰的地區(qū)不重色算法思想：“回溯”法從第一號(hào)地區(qū)開始逐一染色，每一個(gè)地區(qū)逐次用色數(shù)1、2、3、4進(jìn)行試探若當(dāng)前所取的色數(shù)與周圍已染色的地區(qū)不重色，則用棧記下該地區(qū)的色數(shù)，否則依次用下一色數(shù)進(jìn)行試探若出現(xiàn)用1..4色均與相鄰地區(qū)發(fā)生重色，則需退?；厮?，修改當(dāng)前棧頂?shù)纳珨?shù)。地圖四染色問題算法實(shí)現(xiàn)“四染色”定理數(shù)據(jù)結(jié)構(gòu)r[n][n]n*n的關(guān)系矩陣r[i][j]=0表示i與j不相鄰r[i][j]=1表示i與j相鄰。s[n]棧的順序存儲(chǔ)S[i]表示i號(hào)地區(qū)的染色數(shù)。(1)(2)(4)(5)(6)(7)(3)r[7][7]12345671234567100001001111101010110101101011011001001100000000012345671223414334231#

紫色

2#黃色3#

紅色4#

綠色地圖四染色算法棧與函數(shù)調(diào)用由于程序設(shè)計(jì)都采用模塊化程序設(shè)計(jì)方法，模塊（函數(shù)、過程）是完成功能相對(duì)獨(dú)立的一個(gè)程序段，在主函數(shù)（主程序）中調(diào)用模塊來解決復(fù)雜的實(shí)際問題由于函數(shù)調(diào)用后，需返回調(diào)用處，所以，在調(diào)用時(shí)，需用棧記錄斷點(diǎn)的地址以及有關(guān)信息，以便返回。

棧的應(yīng)用-函數(shù)調(diào)用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());}函數(shù)調(diào)用棧與函數(shù)編譯器一般使用堆棧實(shí)現(xiàn)函數(shù)調(diào)用堆棧是存儲(chǔ)器的一個(gè)區(qū)域每個(gè)函數(shù)占用的連續(xù)區(qū)域被稱作函數(shù)的棧幀（frame）函數(shù)調(diào)用時(shí)，為被調(diào)用的函數(shù)分配棧幀，用于存放函數(shù)的參數(shù)、局部變量和返回地址等信息。函數(shù)嵌套調(diào)用時(shí)，在同一時(shí)刻，堆棧中會(huì)有多個(gè)函數(shù)的棧幀，每個(gè)函數(shù)占用一個(gè)連續(xù)的區(qū)域返回地址(下一條指令)局部變量參數(shù)棧與函數(shù)棧與函數(shù)函數(shù)棧幀中，一般包含以下幾類重要信息。局部變量：為函數(shù)局部變量開辟的內(nèi)存空間函數(shù)參數(shù)：為函數(shù)形式參數(shù)開辟的內(nèi)存空間函數(shù)返回地址保存當(dāng)前函數(shù)調(diào)用前的“斷點(diǎn)”信息在函數(shù)返回時(shí)能夠恢復(fù)到函數(shù)被調(diào)用前的代碼空間中，繼續(xù)執(zhí)行指令返回地址(下一條指令)局部變量參數(shù)r主程序srrrs子過程1rst子過程2rst子過程3棧與函數(shù)調(diào)用的圖示遞歸的定義若一個(gè)對(duì)象部分地包含它自己,或用它自己給自己定義,則稱這個(gè)對(duì)象是遞歸的二叉樹是結(jié)點(diǎn)的有限集合，這個(gè)集合或者是空的，或者由一個(gè)根結(jié)點(diǎn)或兩棵互不相交的稱為左子樹的和右子樹的二叉樹組成若一個(gè)過程直接地或間接地調(diào)用自己,則稱這個(gè)過程是遞歸的過程。直接遞歸fun_a(){

…

fun_a()

…}

間接遞歸fun_a(){

…

fun_b()

…}

fun_b(){

…

fun_a()

…}遞歸的定義遞歸條件解決問題時(shí)，可以把一個(gè)問題轉(zhuǎn)化為一個(gè)新的問題，這個(gè)新問題的解決方法，與原問題的解法相同，只是所處理的對(duì)象有所不同。這些被處理的對(duì)象之間有規(guī)律的遞增或遞減要有一個(gè)明確的結(jié)束遞歸的條件，否則遞歸將會(huì)無止境地進(jìn)行下去，直到耗盡系統(tǒng)資源.必須要有終止遞歸的條件適用遞歸技術(shù)的問題以下三種情況常常用到遞歸方法定義是遞歸的數(shù)據(jù)結(jié)構(gòu)是遞歸的問題的解法是遞歸的求解階乘函數(shù)的遞歸算法longFactorial(longn){if(n==0)return1;elsereturnn*Factorial(n-1);}例如，階乘函數(shù)定義是遞歸的

例如，單鏈表結(jié)構(gòu)f

f

數(shù)據(jù)結(jié)構(gòu)是遞歸的一個(gè)結(jié)點(diǎn)，它的指針域?yàn)镹ULL，是一個(gè)單鏈表一個(gè)結(jié)點(diǎn)，它的指針域指向單鏈表，仍是一個(gè)單鏈表搜索鏈表最后一個(gè)結(jié)點(diǎn)打印其值voidPrint(ListNode*f){if(f->link==NULL)

printf(“%d\n”,f->data);elsePrint(f->link);}ffffa0a1a2a3

a4f遞歸找鏈尾數(shù)據(jù)結(jié)構(gòu)是遞歸的問題的解法是遞歸的漢諾塔(TowerofHanoi)問題的解法如果n=1，則將這一個(gè)盤子直接從A柱移到C柱，否則，執(zhí)行以下三步：用C柱做過渡，將A柱上的(n-1)個(gè)盤子移到B柱上：將A柱上最后一個(gè)盤子直接移到C柱上；用A柱做過渡，將B柱上的(n-1)個(gè)盤子移到C柱上。遞歸模型遞歸是把一個(gè)不能或不好直接求解的“大問題”轉(zhuǎn)化為一個(gè)或幾個(gè)“小問題”再把這些“小問題”進(jìn)一步分解成更小的“小問題”來解決直到遞歸出口為止遞歸模型反映一個(gè)遞歸問題的遞歸結(jié)構(gòu)遞歸模型由遞歸出口和遞歸體兩部分組成前者確定遞歸到何時(shí)為止后者確定遞歸的方式遞歸模型例如，階乘函數(shù)遞歸出口遞歸體主程序

main:fact(4)參數(shù)4計(jì)算4*fact(3)

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

參數(shù)2計(jì)算2*fact(1)

參數(shù)1計(jì)算1*fact(0)參數(shù)0直接定值=1

參數(shù)傳遞結(jié)果返回遞歸調(diào)用回歸求值求解n!的過程返回1返回1返回2返回6返回24運(yùn)行結(jié)果：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”);}}主程序(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結(jié)束(1)遞歸調(diào)用執(zhí)行情況如下

如果n=1，則將這一個(gè)盤子直接從A柱移到C柱上。否則，執(zhí)行以下三步：①用C柱做過渡，將A柱上的(n-1)個(gè)盤子移到B柱上：②將A柱上最后一個(gè)盤子直接移到C柱上；③用A柱做過渡，將B柱上的(n-1)個(gè)盤子移到C柱上。漢諾塔(TowerofHanoi)問題的解法及執(zhí)行過程main(){intm;printf("Inputnumberofdisks”);scanf("%d",&m);printf(”Steps:%3ddisks”,m);hanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC1233ABC03ABC02ACB63ABC02ACB61ABC6ABC3ABC02ACB6main(){intm;printf("Inputthenumberofdisksscanf("%d",&m);printf("Thestepstomoving%3dhanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC3ABC02ACB61CAB8ABC3ABC02ACB63ABC03ABC02ACB6main(){intm;printf("Inputthenumberofdisksscanf("%d",&m);printf("Thestepstomoving%3dhanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC3ABC02BAC83ABC02BAC81BCA6ABC3ABC02BAC83ABC0main(){intm;printf("Inputthenumberofdisksscanf("%d",&m);printf("Thestepstomoving%3dhanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC3ABC02