1、1，4.1堆棧實(shí)現(xiàn)4.2堆棧實(shí)現(xiàn)4.3堆棧的應(yīng)用4.4隊(duì)列實(shí)現(xiàn)4.5隊(duì)列4.6隊(duì)列的應(yīng)用，堆棧和隊(duì)列是運(yùn)算限制的線(xiàn)性表。第四章堆棧和隊(duì)列、2、3.1堆棧、3.1.1堆棧的概念和運(yùn)算3.1.3堆棧、3、3.1.1堆棧的概念和運(yùn)算、堆棧限制只在一端進(jìn)行插入和刪除運(yùn)算(2)判定堆?？読sempty tack () 如果st是空堆棧，則函數(shù)值為“真”，否則函數(shù)值為“假”。 (3)堆棧push(st，x ) :在ST的頂部插入要素x (也稱(chēng)為壓入)。 (4)堆棧pop(st ) :刪除(彈出)堆棧st的頂層要素(5)堆棧頂層top(st ) :取堆棧st的頂層要素、堆棧的5種基本運(yùn)算、3.1.1堆棧的概

2、念和運(yùn)算、5、3.1.1順序堆棧、#define MAXNUM 100 /*堆?？蛇_(dá)到的最大容量*/typedef int DataType； /*定義堆棧元素的數(shù)據(jù)類(lèi)型*/struct SeqStack /*順序堆棧類(lèi)型定義*/DataType sMAXNUM； 英特爾； 棧頂*/； 條紋序列，*PSeqStack； 普斯特克派斯特克； /*順序堆棧的指針變量*/，6，注意：t是int型簡(jiǎn)單變量，指堆棧頂部元素在堆棧中的位置(序列號(hào))，1，如果堆棧為空，則t=-1 2，如果堆棧滿(mǎn)，則t“溢出”，7 生成a，b，c，d，堆棧，9，1 .空堆棧(修正法4.1 )，pseqstackcreatee

3、mptystack _ seq (void ) pseqstackpastack。 pasta CK=小空格(sizeof (結(jié)構(gòu)序列) ):if (pasta CK=空格)打印機(jī)(超空格！ n )； 埃爾斯帕斯特克- t=-1； 返回路徑CK； ?？张卸?算法4.2 )，intisemptystack _ seq (pasta CK ) pseqstackpastack； 返回失敗(路徑CK-t=0)。 激活恢復(fù)真； 進(jìn)入堆棧(算法4.3 )，修改t值，然后進(jìn)入數(shù)據(jù)，t，st=x，(*pastack).t，(*pastack) datatype x； if (過(guò)量)打印(過(guò)量)。 埃爾斯帕斯

4、特克- t； 派斯塔克-斯帕斯塔克- t=x； 暫存(演算法4.3 )，13，4 .暫存(演算法4.4 )，pop_seq(pastack )，修正值if (pasta CK-t=-1 )打印(下載流程)。 else pastack-t-； /* pop_seq */，4 .堆棧回復(fù)(算法4.4 )，15，5 .堆棧頂部要素(算法4.5 )，數(shù)據(jù)頂部_ seq (pasta CK ) p if (pasta CK-t=-1 )打印(堆棧ist ) 返回空值； 回復(fù)，回復(fù)，回復(fù)，回復(fù)。 /* top_seq */，16，多個(gè)堆棧共享存儲(chǔ)空間，、時(shí)、的、16，多個(gè)堆棧共享存儲(chǔ)空間，、的、上述第一個(gè)

5、第一個(gè)第一個(gè)第一個(gè)第一個(gè)第一個(gè)第一個(gè)第一、17，多棧共享存儲(chǔ)空間，多棧共享：鏈接棧采用，Typedef struct datatype sMAXNUM； int top1、top2； d堆棧； Push(x，i) Pop(i )，18，3.1.3鏈?zhǔn)蕉褩?，堆棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)為鏈?zhǔn)蕉褩?這是修正運(yùn)算受到限制的單鏈表. 鏈接棧不需要像單鏈接表那樣添加標(biāo)頭節(jié)點(diǎn)，因?yàn)樗荒茉阪溄颖淼拈_(kāi)頭處操作。 棧頂指針top是鏈表的標(biāo)頭指針head。、19、類(lèi)型無(wú)數(shù)據(jù)類(lèi)型； 結(jié)構(gòu)節(jié)點(diǎn)； 類(lèi)型結(jié)構(gòu)節(jié)點(diǎn)*節(jié)點(diǎn)； 結(jié)構(gòu)節(jié)點(diǎn)/*單鏈路表節(jié)點(diǎn)結(jié)構(gòu)*/DataType info； 節(jié)點(diǎn)鏈接； 鏈路堆棧/*鏈路堆棧類(lèi)型定義*

6、/節(jié)點(diǎn)頂點(diǎn)； 堆疊頂層節(jié)點(diǎn)*/； typedefstructlinkstack *打印堆棧； 3.1.3鏈接堆棧、鏈接堆棧pl堆棧； 變量宣言*/，plstack，top，info，link，堆棧的鏈接表示，21，3.1 p=(節(jié)點(diǎn)) malloc (sizeof (結(jié)構(gòu)節(jié)點(diǎn)) ):if (p=null )打印(out of sof )。 n )； 激活信息=x； p鏈路=堆棧頂部； pl堆棧頂點(diǎn)=p； 堆棧算法(算法4.8 )、23、void pop _ link (鏈接堆棧) pnodep； if (安全堆棧鏈接(pl堆棧) )打印機(jī)(企業(yè)堆棧pop.n )。 普通堆棧頂部； 堆棧頂部=堆

7、棧頂部鏈路。 自由(p )； 堆棧算法(算法4.9 )、24、3.2堆棧的應(yīng)用、堆棧的應(yīng)用非常廣泛，只要問(wèn)題滿(mǎn)足LIFO原則，就可以將堆棧作為數(shù)據(jù)結(jié)構(gòu)使用。 我們來(lái)看幾個(gè)例子例子3.1文本編輯器例子3.2堆棧遞歸例子3.3數(shù)變換例子3.4括號(hào)匹配的檢查例子3.5式評(píng)價(jià)，25，例子3.1設(shè)定簡(jiǎn)單的文本編輯器，使之具有刪除錯(cuò)誤的文字的功能。 刪除前面的字符*刪除輸入結(jié)束，“abc#defg*”，使用堆棧實(shí)現(xiàn)此功能的文本編輯器，每次讀取一個(gè)字符，堆棧，空堆棧，編輯結(jié)束，26，PSeqStack str； 序列堆棧str是全過(guò)程變量*/EDIT() /*編輯后的字符串在str中為*/char c； s

8、tr=createEmptyStack ()； c=getchar ()； 威爾！ 編輯結(jié)束符*/if (c=#) POP(str )； else if (c=) str=createemptystack ()； 推送(str，c )； c=getchar ()； /*EDIT*/，示例3.1修訂了具有刪除錯(cuò)誤字符功能的簡(jiǎn)單文本編輯器。 27、如果一個(gè)對(duì)象部分是自己構(gòu)成的，或者是自己定義的，則稱(chēng)為遞歸。 遞歸的定義必須比一步一步簡(jiǎn)單，最后有終點(diǎn)，不能無(wú)限循環(huán)。 在n階乘的定義中，n為0時(shí)定義為1，不再遞歸定義，稱(chēng)為遞歸定義的出口，僅稱(chēng)為遞歸出口。 例3.2堆棧和遞歸、遞歸的定義、28、例3.2

9、堆棧和遞歸、遞歸函數(shù)的特征：可以在函數(shù)內(nèi)部直接或間接地調(diào)用函數(shù)本身。 與階乘函數(shù)一樣：階乘的遞歸校正運(yùn)算(算法4.11 ) intfact (intn ) if (n=0) return 1。 else return(n*fact(n-1 ) ) : r 2主()接口； 傳達(dá)scanf(“%dn”、r1、3、3、r1、2、r2、1、r2(活動(dòng)記錄、數(shù)據(jù)區(qū)域) (2)所有實(shí)參數(shù)、將門(mén)地址傳遞給調(diào)用函數(shù)的實(shí)參與形參的結(jié)合、值。 (3)將控制轉(zhuǎn)移到被調(diào)用的函數(shù)條目。 調(diào)用后跳過(guò)： (1)保存被調(diào)用函數(shù)的修正結(jié)果(2)釋放被調(diào)用函數(shù)的存儲(chǔ)區(qū)域(3)根據(jù)被調(diào)用函數(shù)中保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。

10、中的組合圖層性質(zhì)變更選項(xiàng)。 從遞歸函數(shù)到非遞歸函數(shù)的轉(zhuǎn)換是根據(jù)嵌套調(diào)用函數(shù)時(shí)“后調(diào)用先上門(mén)”的原則進(jìn)行的。 int main() int m，n； first(m，n )； 1:第一次入口(入口、入口)入口。 二十(一)； 2:第二次插入，y； 3:int main() int m，n； int i； 英特爾x、y； 3: 2: 1:函數(shù)嵌套結(jié)構(gòu)，算法4.12階乘的非遞歸校正算法程序員自己管理堆棧并模擬函數(shù)調(diào)用的執(zhí)行過(guò)程。意外事件(意外事件)； 英特雷斯； pSeqStack st； st=createEmptyStack-seq ()； (n0)威爾(！ 快速堆疊快速(ST )推送快速(ST

11、，n )快速(ST )快速(ST )快速(n=n-1； pop-seq(st )； res=1； 自由(ST )； 返回(回)； 階乘遞歸算法： int fact (int n ) if (n=0)返回1。 else return(n*fact(n-1 ) ) : 對(duì)于34，示例3.3中的數(shù)值轉(zhuǎn)換，十進(jìn)制n和其他d進(jìn)制轉(zhuǎn)換，請(qǐng)單擊N=(N div d ) x d N mod d，nn div8mod 8，1348168，16821，2125，202。 由于上述的修正過(guò)程從下到上依次生成8進(jìn)制的各位，所以打印輸出一般應(yīng)該從上到下進(jìn)行，正好與修正過(guò)程相反。 例3.3進(jìn)制轉(zhuǎn)換，因此，如果將修正運(yùn)算中

12、得到的8進(jìn)制的各位按順序放入堆棧，則按每個(gè)堆棧順序打印輸出的是與輸入對(duì)應(yīng)的8進(jìn)制。 36、補(bǔ)償堆棧str； void轉(zhuǎn)換() str=createemptystack ()； 掃描(“% d”，x )； 推送(str，X%8)； X=X/8； 威廉(！ 打印機(jī)(“% d”、頂部(str ) )； 普洛普(str )；/*轉(zhuǎn)換* /，示例3.3數(shù)字轉(zhuǎn)換，37，示例3.3數(shù)字轉(zhuǎn)換，語(yǔ)音轉(zhuǎn)換(int x ) if (x/8！ 轉(zhuǎn)換(x/8 )； 打印(“% d”，X%8)； 用遞歸函數(shù)實(shí)現(xiàn)：使用遞歸編程時(shí)，用戶(hù)不需要自己定義堆棧。 這是由編譯器設(shè)置和處理的。38、示例3.4括號(hào)匹配的檢驗(yàn)假定表達(dá)式允許三個(gè)括號(hào)(、和)，并且嵌套順序是任意的。 驗(yàn)證括號(hào)是否一致的方法可以用“期待的緊迫度”這一概念來(lái)記述。 在算法中設(shè)置堆棧，每次讀取括號(hào)時(shí)，如果是右括號(hào)，則消除放置在堆棧頂部的最緊迫的期待；如果是不合法的情況，則作為新的更緊迫的期待被推入堆棧，當(dāng)然是原始堆棧中所有未解決的期待的() 1234678、39、Judgement() /*判定表達(dá)式是否成對(duì)，表達(dá)式為#結(jié)束*/PSeqStack sta。 茶道，茶點(diǎn)； 保險(xiǎn)杠； SETNULL(/*valid是FALSE表中括號(hào)配對(duì)失敗*/，例如3.4括號(hào)配對(duì)檢查，40，例如3.4括號(hào)配對(duì)檢查，while(ch！ 在讀取文字為左括弧時(shí)，