1、2020/8/3,1,第3章 棧結(jié)構(gòu),教學(xué)目的：掌握棧結(jié)構(gòu)的特點(diǎn),了解棧的應(yīng)用 教學(xué)重點(diǎn)：順序棧的實(shí)現(xiàn),2020/8/3,2,3.1.1 棧的定義及邏輯特性 棧（stack）是限定僅在表尾進(jìn)行插入或刪除操作的線性表。其中表尾稱為棧頂（top），表頭則稱為棧底（bottom）。 將插入元素的操作稱為入棧（push），刪除元素的操作稱為出棧（pop）。 由于限定插入或刪除操作僅在棧頂進(jìn)行，因此，元素的出棧順序與入棧順序相反，最先入棧的元素最后出棧。因此棧又稱為后進(jìn)先出（Last In First Out，簡(jiǎn)寫為L(zhǎng)IFO）的線性表.,3.1 棧的定義和基本操作,2020/8/3,3,2020/8/3

2、,4,2棧的基本運(yùn)算 初始化棧InitStack(S) 設(shè)置一個(gè)空棧S。 銷毀棧 DestroyStack(S); 釋放棧s所占的存儲(chǔ)空間 入棧Push(S,x) 將元素x插入棧S中，使x成為棧S的棧頂元素。 出棧Pop(S,x) 當(dāng)棧S不空時(shí)，由x返回棧頂元素，并從棧中刪除棧頂元素 取棧頂元素GetTop(S,x) 若棧S不空，則由x返回棧頂元素（棧指針不變）。 判棧空Empty(S) 判斷棧S是否為空棧。,2020/8/3,5,3.1.2 棧的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 棧結(jié)構(gòu)的實(shí)現(xiàn)也可以有兩種：順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)。 由于棧的插入、刪除操作限定僅在表尾進(jìn)行，不需要移動(dòng)元素，因此，棧結(jié)構(gòu)的實(shí)現(xiàn)以順序

3、結(jié)構(gòu)為主。即利用一組地址連續(xù)的存儲(chǔ)單元作為棧的存儲(chǔ)空間，依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)設(shè)兩指針分別指示棧頂和棧底的位置。 實(shí)際上，順序棧的實(shí)現(xiàn)有兩種形式：一種是靜態(tài)棧，?？臻g的大小一經(jīng)定義不能再改變，可用數(shù)組描述；另一種是浮動(dòng)棧（動(dòng)態(tài)棧），即在初始化時(shí)先為棧分配一基本空間，當(dāng)在應(yīng)用過程中出現(xiàn)?？臻g不足時(shí)，再逐漸擴(kuò)大棧的存儲(chǔ)空間。,順序棧的靜態(tài)實(shí)現(xiàn)： # define StackSize 100 /*?？臻g大小 */ /*順序棧的結(jié)構(gòu)類型定義*/ typedef struct Datatype dataStacksize; /*棧空間 */ int top; /*棧頂“指針” */ Seq

4、Stack; 根據(jù)以上定義寫出實(shí)現(xiàn)基本操作的代碼：,約定：top指向新元素要入棧的位置 因此空棧 top=0; /棧底base隱含為0 /初始化空棧: Status InitStack(SeqStack ,/入棧：將元素e插入棧S中 Status Push(SeqStack s,Datatype e) if (s.top=StackSize) /棧滿 return(StackOverflow); s.datas.top+=e; return (ok); ,約定：top指向新元素要入棧的位置,/出棧: 當(dāng)棧S不空時(shí)，由x返回棧頂元素 Status Pop(SeqStack s,Datatype

5、,約定：top指向新元素要入棧的位置,/返回棧頂元素的值，棧指針不改變 Status GetTop(SeqStack s,Datatype ,約定：top指向新元素要入棧的位置,2020/8/3,11,所謂動(dòng)態(tài)棧是指先分配一個(gè)基本的?？臻g，運(yùn)行中?？臻g滿時(shí)再追加存儲(chǔ)空間。因此動(dòng)態(tài)棧的實(shí)現(xiàn)需要?jiǎng)討B(tài)存儲(chǔ)分配函數(shù)支持 具有動(dòng)態(tài)特點(diǎn)的順序棧定義如下： # define StackInitSize 100 /* 初始棧空間 */ # define Increment 10/* 存儲(chǔ)分配增量值 */ /*棧的結(jié)構(gòu)類型定義*/ typedef struct Datatype *base;/* ?？臻g的首地址

6、（基址） */ Datatype *top;/* 棧頂指針 */ int stacksize;/* 當(dāng)前實(shí)際?？臻g */ SqStack;,3.1.2 順序棧的動(dòng)態(tài)結(jié)構(gòu),2020/8/3,12,順序棧示意圖圖3.2,注意棧指針的約定：棧頂指針Top指向的是新元素將存放的位置； 所以入棧操作是：先存放元素，再移動(dòng)棧頂指針。, c b a,空棧,a,b,c順序入棧后,c, b 順序出棧后,判斷?？盏臈l件：s.top=s.base 判斷棧滿的條件：s.top-s.base=s.stacksize,2020/8/3,13,算法3.1 動(dòng)態(tài)順序棧初始化 status InitStack (SqStack

7、 *s) /* 初始化?？臻g，成功返回1否則返回0 */ s-base=(Datatype *)malloc(StackInitSize *sizeof(Datatype); if ( s-base=null ) return (overflow); /* 內(nèi)存空間不足 */ s-top=s-base; s-stacksize=StackInitSize; return (ok); Initstack函數(shù)的調(diào)用方法: SqStack s; /*聲明一個(gè)棧結(jié)構(gòu)的變量s*/ Status Result; Result=InitStack( /*調(diào)用初始化函數(shù)*/,3.1.2 順序棧的操作實(shí)現(xiàn),20

8、20/8/3,14,算法3.2 入棧操作 status push (SqStack s, Datatype e) /* 將元素e入棧，操作成功返回ok, 否則返回error */ Datatype *p=.base; if (s.top-s.base=s.stacksize) /* 棧滿,重新分配棧空間 */ p=(Datatype*)realloc(s-base,(s-stacksize+increment)*sizeof(Datatype); if (!p) return (error); /* ?？臻g分配失敗 */ s-base=p; /* ?？臻g分配成功，修改棧底指針 */ s-top

9、=p+s-StackSize; /*修改棧頂指針 */ s-stacksize +=Increment; /* 修改?？臻g值*/ *s-top+=e; /*元素e入棧,并修改棧頂指針*/ return (ok); *s-top+=e; 等價(jià)于: *(s-top)=e; (s-top)+; 這里運(yùn)算符“-”的優(yōu)先級(jí)最高；其次是 * ；最后是+,2020/8/3,15,算法3.3銷毀棧操作 status DestroyStack (SqStack *s) /* 釋放棧s的空間 */ if (s) /*棧指針有效*/ free (s-base) ; /*先釋放棧s所分配的空間*/ free (s)

10、; /*釋放變量s所占的空間-黃色部分*/ return (ok); else return (error); , c b a,s,2020/8/3,16,算法3.4 出棧操作 Status Pop(SqStack *s,Datatype *e) /* 將棧頂元素出棧,由變量e返回 若成功返回ok，否則返回error */ if (s-top=s-base) printf(“stack_empty”); return(error); *e=*(-s-top); /*先修改top指針，然后返回棧頂元素*/ return (ok); s-top-; *e=*(s-top); /*先修改top指針，

11、然后返回棧頂元素*/,2020/8/3,17,算法3.5 取棧頂元素 Status GetTop(SqStack *s,Datatype *e) /* 取棧頂元素由變量e返回,但不改變棧指針top */ Datatype *p=s-top; if (p=S-base) return (error); *e=*(-p); return (ok); ,2020/8/3,18,3.1.3 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 棧的鏈?zhǔn)綄?shí)現(xiàn)是以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，并在這種存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)棧的基本運(yùn)算。棧的鏈?zhǔn)綄?shí)現(xiàn)稱為鏈?zhǔn)綏！?棧的操作將用鏈表的操作實(shí)現(xiàn)。,鏈棧結(jié)構(gòu)示意圖,2020/8/3,19,討論：多個(gè)棧共用存儲(chǔ)空間問

12、題 1.現(xiàn)以順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)一個(gè)雙向棧：用一維數(shù)組的存儲(chǔ)空間實(shí)現(xiàn)兩個(gè)棧，它們的棧頂相對(duì)，棧底分別在數(shù)組的兩個(gè)端點(diǎn)。試設(shè)計(jì)該雙向棧的類型定義，并編寫以下三個(gè)基本操作算法： （1）初始化InitStack(tws)； （2）入棧操作Push(tws,i,e)； （3）出棧操作Pop(tws,i,*e)； 其中變量i為標(biāo)志，指示對(duì)兩個(gè)棧中的哪個(gè)進(jìn)行操作。（例可用i=0表示正向棧，i=1表示逆向棧）,2020/8/3,20,討論：多個(gè)棧共用存儲(chǔ)空間問題 提示：為簡(jiǎn)化操作，用數(shù)組描述（靜態(tài)棧，?？臻g的大小不能再改變） 則可省略棧的base指針。 雙向棧類型定義Tws #define MaxSize 10

13、00 /*雙向棧的最大空間*/ typedef struct Datatype elemMaxSize; /*?？臻g*/ int top1,base1; /*正向棧指針*/ int top2,base2; /*逆向棧指針*/ Tws; /*雙向棧類型*/ 在一個(gè)數(shù)組空間中實(shí)現(xiàn)兩個(gè)棧，從兩端向中間增長(zhǎng)： 正向棧：入棧時(shí) s.elemtop+=e; 出棧時(shí) e=s.elem-top; 逆向棧：入棧時(shí) s.elemtop-=e; 出棧時(shí) e=s.elem+top;,base1 top1 base2 top2,0 1 2 3 997 998 999,2020/8/3,21,作業(yè)：2個(gè)棧共用存儲(chǔ)空間問題

14、 用長(zhǎng)為n的一塊內(nèi)存實(shí)現(xiàn)雙向棧：棧底分別在兩端，棧頂相對(duì)，從而每個(gè)棧的大小可以n/2，具有1+12的效果。,/*初始化算法*/ /約定：棧頂指針top指向新元素入棧的位置 Void InitStack(Tws *s) s-top1=s-base1=0; s-top2=s-base2=Maxsize-1; ,/入棧 status Push(tws ,/出棧，先判出哪個(gè)棧 status Pop(tws ,2020/8/3,24,教學(xué)目的：學(xué)會(huì)使用棧結(jié)構(gòu)解決問題， 初步掌握遞歸程序設(shè)計(jì)方法 教學(xué)重點(diǎn)：棧的應(yīng)用 教學(xué)難點(diǎn)：利用棧實(shí)現(xiàn)表達(dá)式求值 遞歸算法,3.2 棧的應(yīng)用,2020/8/3,25,本課內(nèi)

15、容,一、棧的典型應(yīng)用 1.表達(dá)式括號(hào)匹配問題 2.表達(dá)式求值問題 二、典型遞歸算法 漢諾塔問題求解,2020/8/3,26,解決問題思路： 假設(shè)表達(dá)式中允許出現(xiàn)兩類括號(hào)：( )、 ，且嵌套的順序隨意，例：( )( )，則檢驗(yàn)括號(hào)是否匹配的算法是： 依次掃描表達(dá)式中的字符，遇到左括號(hào)就進(jìn)棧； 遇到右括號(hào)則與棧頂元素比較，若匹配則棧頂元素出棧，否則說明出現(xiàn)錯(cuò)誤，可指出錯(cuò)誤位置及括號(hào)并停止掃描； 重復(fù)以上過程，直到表達(dá)式處理完，若表達(dá)式語(yǔ)法正確，則棧應(yīng)該和初始狀態(tài)相同，否則一定是表達(dá)式中的括號(hào)不匹配。 注意：當(dāng)前需要匹配的左括號(hào)總是處在棧頂。,3.2.1 棧的應(yīng)用括號(hào)匹配問題,2020/8/3,27

16、,處理表達(dá)式的基本步驟： （1）首先初始化字符棧s為空棧。 （2）依次讀入表達(dá)式字符，當(dāng)表達(dá)式未結(jié)束時(shí)重復(fù)以下步驟： 遇左括號(hào)“( ”或“”則進(jìn)棧；并繼續(xù)讀下一個(gè)字符; 遇其它字符，則跳過； 遇右括號(hào)“)”或“”，與棧頂字符比較，看是否匹配（即同為方括號(hào)或同為圓括號(hào)），相符則棧頂字符出棧并繼續(xù)讀下一個(gè)字符； 若棧為空則顯示錯(cuò)誤并提前結(jié)束掃描。（錯(cuò)誤信息：少左括號(hào)） （3）表達(dá)式處理結(jié)束后，判棧s是否為空棧： 若是，表示括號(hào)匹配成功； 否則表明表達(dá)式中括號(hào)不匹配。 （錯(cuò)誤信息：少右括號(hào)）,3.2.1 括號(hào)匹配問題,2020/8/3,28,表達(dá)式括號(hào)匹配的程序?qū)崿F(xiàn),一、首先定義字符棧 #defin

17、e maxsize 255 /*最大?？臻g*/ typedef struct char *top; /*棧指針*/ char datamaxsize; Stack; /*并聲明以下基本操作*/ void InitStack(Stack *s); /*初始化*/ void Push(Stack *s,char e); /*入棧*/ int Pop(Stack *s,char *e); /*出棧*/ char GetTop(Stack *s); /*取棧頂元素*/,2020/8/3,29,主程序如下：,main() char expmaxsize+1; char ch; int error=0,i

18、; /*error為是否出錯(cuò)標(biāo)記,為1表示括號(hào)不匹配*/ Stack s; /*初始化字符棧*/ InitStack(,2020/8/3,30,while (expi!=#) /*表達(dá)式為結(jié)束*/ swith (expi) case (: /*左括號(hào)入棧*/ case : Push( ,2020/8/3,31,/*實(shí)現(xiàn)棧的基本操作*/ void InitStack(Stack *s) /*初始化*/ s-top=s-data; void Push(Stack *s,char e) /*入棧*/ *(s-top)=e; s-top+; int Pop(Stack *s,char *e) /*出棧

19、,需要判斷?？辗?/ if (s-top=s-data) return (0); else s-top-; *e=*(s-top); return (1); char GetTop(Stack *s) /*取棧頂元素,不成功返回空字符*/ ,2020/8/3,32,1.表達(dá)式運(yùn)算規(guī)則分析 假定四則運(yùn)算表達(dá)式中允許出現(xiàn)的運(yùn)算符有 +、-、*、/、( )，且基本的運(yùn)算規(guī)則是： (1) 先做括號(hào)內(nèi)的運(yùn)算，即括號(hào)的優(yōu)先級(jí)最高； (2) 先乘除、后加減，即 */ 運(yùn)算高于+、- 運(yùn)算； (3) 相同級(jí)別的運(yùn)算（同為加減類或乘除類）按從左向右規(guī)則進(jìn)行。,3.2.2 棧的應(yīng)用表達(dá)式求值問題,2020/8/3

20、,33,根據(jù)以上運(yùn)算規(guī)則，對(duì)表達(dá)式進(jìn)行掃描，遇到一個(gè)運(yùn)算符1時(shí)，并不能確定馬上就執(zhí)行計(jì)算，需向右掃描到下個(gè)運(yùn)算符2，通過比較它們之間的優(yōu)先關(guān)系，才能決定如何操作。1和2的優(yōu)先關(guān)系只有以下三種： 1）12：2優(yōu)先級(jí)低于1，此時(shí)應(yīng)執(zhí)行1規(guī)定的運(yùn)算； 2）12：2優(yōu)先級(jí)等于1，此時(shí)也應(yīng)執(zhí)行1規(guī)定的運(yùn)算； 3）12：2優(yōu)先級(jí)高于1，此時(shí)不能執(zhí)行任何運(yùn)算，需繼續(xù)掃描下一運(yùn)算符。 前兩種情況可統(tǒng)一處理，而最后一種情況則需要將尚不能處理的運(yùn)算符保存起來，待讀入下一個(gè)運(yùn)算符后再用以上規(guī)則處理。而棧結(jié)構(gòu)的后進(jìn)先出特點(diǎn)正好可以用于保存未處理的運(yùn)算符。,3.2.2 棧的應(yīng)用表達(dá)式求值問題,2020/8/3,34,實(shí)

21、現(xiàn)運(yùn)算符優(yōu)先法需要使用兩個(gè)棧： 一個(gè)運(yùn)算符棧 OPR，用于存放暫時(shí)不能處理的運(yùn)算符； 一個(gè)運(yùn)算數(shù)棧OPD，用于存放運(yùn)算數(shù)和中間結(jié)果。 為了使程序能按照優(yōu)先級(jí)對(duì)表達(dá)式自動(dòng)求值，我們可為每個(gè)運(yùn)算符定義一個(gè)優(yōu)先數(shù)，以反映他們之間的優(yōu)先關(guān)系。（見表3.1) 首先，為了使相同級(jí)別的運(yùn)算1、2能夠按從左向右的順序進(jìn)行，人為地使12；其次，增設(shè)一個(gè)表達(dá)式界限符“#”，規(guī)定其優(yōu)先級(jí)低于所有的運(yùn)算符和括號(hào) ，以便于程序統(tǒng)一處理。,3.2.2 棧的應(yīng)用表達(dá)式求值問題,2020/8/3,35,“運(yùn)算符優(yōu)先法” ： 1.初始化運(yùn)算數(shù)棧OPD和運(yùn)算符棧OPR，并將界限符“#”壓入運(yùn)算符棧。 2.依次讀入表達(dá)式中的每一項(xiàng)

22、，是運(yùn)算數(shù)則入運(yùn)算數(shù)棧OPD，是運(yùn)算符則與OPR棧頂元素比較優(yōu)先級(jí)，并根據(jù)以下情況分別處理： (1) 高于棧頂，則當(dāng)前運(yùn)算符入棧； (2) 低于棧頂，則OPR出棧-op，且OPD棧彈出兩個(gè)操作數(shù)a、b，執(zhí)行“a op b”規(guī)定的運(yùn)算，并將運(yùn)算結(jié)果壓入運(yùn)算數(shù)棧OPD； (3) 優(yōu)先級(jí)相同，說明是左右括號(hào)相遇或兩個(gè)“#”相遇，將棧頂元素出棧。 重復(fù)2的操作，當(dāng)運(yùn)算符棧為空時(shí)則表達(dá)式求值結(jié)束，此時(shí)求值結(jié)果在運(yùn)算數(shù)棧中。,3.3.2 棧的應(yīng)用表達(dá)式求值問題,2020/8/3,36,常量表達(dá)式5+12/3- (7-2)*3的求值過程。,2020/8/3,37,遞歸是一種非常重要的數(shù)學(xué)概念和解決問題的方法

23、，在計(jì)算機(jī)科學(xué)和數(shù)學(xué)等領(lǐng)域有著廣泛的應(yīng)用。在計(jì)算機(jī)科學(xué)中，許多數(shù)據(jù)結(jié)構(gòu)，如廣義表、樹和二叉樹等，由于其自身固有的遞歸性質(zhì)，都可通過遞歸方式加以定義并實(shí)現(xiàn)許多其算法設(shè)計(jì)。而遞歸算法的實(shí)現(xiàn)是以棧結(jié)構(gòu)為基礎(chǔ)的，所以遞歸是棧的一個(gè)實(shí)際應(yīng)用。 遞歸的定義：如果在描述一個(gè)事物時(shí)又使用了該事物自身，就稱為遞歸。 遞歸函數(shù)：一個(gè)函數(shù)直接或間接地調(diào)用了自己，則稱為遞歸函數(shù)。,3.3 棧與遞歸,2020/8/3,38,采用遞歸算法求解正整數(shù)n的階乘n! 數(shù)學(xué)定義,求n的階乘的遞歸函數(shù)算法如下: long fact(int n) long f; R1: if (n=0) f=1; /*遞歸終止條件*/ R2: el

24、se f=n*fact(n-1); /*遞歸調(diào)用*/ R3: return f; ,2020/8/3,39,進(jìn)行fact(4)調(diào)用的系統(tǒng)棧的變化情況 需要入棧的包括：參數(shù)n、返回地址,4, r3,3, r3 4, r3,2, r3 3, r3 4, r3,1, r3 2, r3 3, r3 4, r3,1, r3 2, r3 3, r3 4, r3,fect(4) fect(3) fect(2) fect(1) fect(0) 1出棧 2出棧 3出棧 4出棧后 執(zhí)行f=1 執(zhí)行1*1 執(zhí)行2*1 執(zhí)行3*2 執(zhí)行4*6 返回1 返回1 返回2 返回6 返回24,2, r3 3, r3 4, r3,3, r3 4, r3,4, r3,2020/8/3,40,函數(shù)fact(4)的遞歸調(diào)用過程的執(zhí)行流程,f,=,4,*,fact,(,3,),;,n,:,4,return 24,f,=,3,*,fact,(,2,),;,n,:,3,return 6,;,f,=,2,*,fact,(,1,),;,n,:,2,return 2,;,f,=,1,*,fac