棧和上機作業(yè)

1、2021/3/1313.1.1 3.1.1 棧的定義棧的定義 3.1.2 3.1.2 棧的順序存儲結(jié)構(gòu)及棧的順序存儲結(jié)構(gòu)及 其基本運算實現(xiàn)其基本運算實現(xiàn)3.1.3 3.1.3 棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其 基本運算的實現(xiàn)基本運算的實現(xiàn)3.1.4 3.1.4 棧的應(yīng)用例子棧的應(yīng)用例子3.1 3.1 棧棧 2021/3/132 棧棧是一種只能在一端進(jìn)行插入或刪除操是一種只能在一端進(jìn)行插入或刪除操作的線性表。作的線性表。 表中允許進(jìn)行插入、刪除操作的一端稱表中允許進(jìn)行插入、刪除操作的一端稱為為棧頂棧頂。 棧頂?shù)漠?dāng)前位置是動態(tài)的棧頂?shù)漠?dāng)前位置是動態(tài)的, ,棧頂?shù)漠?dāng)前棧頂?shù)漠?dāng)前位置由一個稱為

2、棧頂指針的位置指示器指示。位置由一個稱為棧頂指針的位置指示器指示。表的另一端稱為表的另一端稱為棧底棧底。 當(dāng)棧中沒有數(shù)據(jù)元素時當(dāng)棧中沒有數(shù)據(jù)元素時, ,稱為稱為空棧空棧。 棧的插入操作通常稱為棧的插入操作通常稱為進(jìn)棧進(jìn)?；蚧蛉霔Ｈ霔? ,棧棧的刪除操作通常稱為的刪除操作通常稱為退棧退?；蚧虺鰲３鰲?。3.1.1 3.1.1 棧的定義棧的定義 2021/3/133圖圖3-1 3-1 順序棧示意圖順序棧示意圖a a1 1a a2 2a ai ia an n bottombottomtoptop進(jìn)棧（進(jìn)棧（pushpush）出棧出棧(pop)(pop)2021/3/134順序棧進(jìn)棧和出棧示意圖順序棧進(jìn)

3、棧和出棧示意圖2021/3/135棧的幾種基本運算如下棧的幾種基本運算如下: :(1) (1) 初始化棧初始化棧InitStack(&s):InitStack(&s):構(gòu)造一個構(gòu)造一個空棧空棧s s。(2) (2) 銷毀棧銷毀棧ClearStack(&s):ClearStack(&s):釋放棧釋放棧s s占占用的存儲空間。用的存儲空間。(3) (3) 求棧的長度求棧的長度StackLength(s):StackLength(s):返回返回棧棧s s中的元素個數(shù)。中的元素個數(shù)。(4) (4) 判斷棧是否為空判斷棧是否為空StackEmpty(s):StackEmpty(s):若若棧棧s s為空為

4、空, ,則返回真則返回真; ;否則返回假。否則返回假。2021/3/136 (5) (5) 進(jìn)棧進(jìn)棧Push(&S,e):Push(&S,e):將元素將元素e e插入到棧插入到棧s s中作為棧頂元素。中作為棧頂元素。 (6) (6) 出棧出棧Pop(&s,&e):Pop(&s,&e):從棧從棧s s中退出棧頂中退出棧頂元素元素, ,并將其值賦給并將其值賦給e e。 (7) (7) 取棧頂元素取棧頂元素GetTop(s,&e):GetTop(s,&e):返回當(dāng)返回當(dāng)前的棧頂元素前的棧頂元素, ,并將其值賦給并將其值賦給e e。 (8) (8) 顯示棧中元素顯示棧中元素DispStack(s):D

5、ispStack(s):從棧從棧頂?shù)綏５醉樞蝻@示棧中所有元素。頂?shù)綏５醉樞蝻@示棧中所有元素。2021/3/1373.1.2 3.1.2 棧的順序存儲結(jié)構(gòu)及其基本運算實現(xiàn)棧的順序存儲結(jié)構(gòu)及其基本運算實現(xiàn) 假設(shè)棧的元素個數(shù)最大不超過正整數(shù)假設(shè)棧的元素個數(shù)最大不超過正整數(shù)MaxSize,MaxSize,所有的元素都具有同一數(shù)據(jù)類型所有的元素都具有同一數(shù)據(jù)類型ElemType,ElemType,則可用下列方式來定義棧類型則可用下列方式來定義棧類型SqStack:SqStack: typedef struct typedef struct ElemType dataMaxSize; ElemType d

6、ataMaxSize; int topint top; ;/ /* *棧指針棧指針* */ / SqStack SqStack; ;2021/3/138在順序棧中實現(xiàn)棧的基本運算算法在順序棧中實現(xiàn)棧的基本運算算法: : (1) (1) 初始化棧初始化棧initStack(&s)initStack(&s) 建立一個新的空棧建立一個新的空棧s,s,實際上是將棧頂指針實際上是將棧頂指針指向指向-1-1即可。對應(yīng)算法如下即可。對應(yīng)算法如下: : void InitStack(SqStack void InitStack(SqStack * *&s)&s) s=(SqStack s=(SqStack *

7、 *)malloc(sizeof(SqStack);)malloc(sizeof(SqStack); s-top=-1; s-top=-1; 2021/3/139順序棧進(jìn)棧和出棧示意圖順序棧進(jìn)棧和出棧示意圖2021/3/1310 (2) (2) 銷毀棧銷毀棧ClearStack(&s)ClearStack(&s) 釋放棧釋放棧s s占用的存儲空間。對應(yīng)算法占用的存儲空間。對應(yīng)算法如下如下: : void ClearStack(SqStack void ClearStack(SqStack * *&s)&s) free(s);free(s); 2021/3/1311 (3) (3) 求棧的長度求

8、棧的長度StackLength(s)StackLength(s) 返回棧返回棧s s中的元素個數(shù)中的元素個數(shù), ,即棧指針加即棧指針加1 1的結(jié)果。對應(yīng)算法如下的結(jié)果。對應(yīng)算法如下: : int StackLength(SqStack int StackLength(SqStack * *s)s) return(s-top+1); return(s-top+1); 2021/3/1312 (4) (4) 判斷棧是否為空判斷棧是否為空StackEmpty(s)StackEmpty(s) 棧棧S S為空的條件是為空的條件是s-top=-1s-top=-1。對。對應(yīng)算法如下應(yīng)算法如下: : int

9、StackEmpty(SqStack int StackEmpty(SqStack * *s)s) return(s-top=-1); return(s-top=-1); 2021/3/1313 (5) (5) 進(jìn)棧進(jìn)棧Push(&s,e)Push(&s,e) 在棧不滿的條件下在棧不滿的條件下, ,先將棧指針增先將棧指針增1,1,然后在該位置上插入元素然后在該位置上插入元素e e。對應(yīng)算法如。對應(yīng)算法如下下: : int Push(SqStack int Push(SqStack * *&s,ElemType e)&s,ElemType e) if (s-top=MaxSize-1) retu

10、rn 0;if (s-top=MaxSize-1) return 0;/ /* *棧滿的情況棧滿的情況, ,即棧上溢出即棧上溢出* */ /s-top+;s-top+; s-datas-top=e; s-datas-top=e;return 1;return 1; 2021/3/1314(6) (6) 出棧出棧Pop(&s,&e)Pop(&s,&e) 在棧不為空的條件下在棧不為空的條件下, ,先將棧頂元素先將棧頂元素賦給賦給e,e,然后將棧指針減然后將棧指針減1 1。對應(yīng)算法如下。對應(yīng)算法如下: : int Pop(SqStack int Pop(SqStack * *&s,ElemType

11、&e)&s,ElemType &e) if (s-top=-1) return 0; if (s-top=-1) return 0; / /* *棧為空的情況棧為空的情況, ,即棧下溢出即棧下溢出* */ / e=s-datas-top; e=s-datas-top; s-top-; s-top-; return 1; return 1; 2021/3/1315 (7) (7) 取棧頂元素取棧頂元素GetTop(s)GetTop(s) 在棧不為空的條件下在棧不為空的條件下, ,將棧頂元素賦將棧頂元素賦給給e e。對應(yīng)算法如下。對應(yīng)算法如下: : int GetTop(SqStack int G

12、etTop(SqStack * *s,ElemType &e)s,ElemType &e) if (s-top=-1) return 0; if (s-top=-1) return 0; / /* *棧為空的情況棧為空的情況, ,即棧下溢出即棧下溢出* */ /e=s-datas-top;e=s-datas-top;return 1;return 1; 2021/3/1316 (8) (8) 顯示棧中元素顯示棧中元素DispStack(s)DispStack(s) 從棧頂?shù)綏５醉樞蝻@示棧中所有元從棧頂?shù)綏５醉樞蝻@示棧中所有元素。對應(yīng)算法如下素。對應(yīng)算法如下: : void DispStack(

13、SqStack void DispStack(SqStack * *s)s) int i; int i; for(i=s-top;i=0;i-) for(i=s-top;i=0;i-) printf(%c ,s-datai); printf(%c ,s-datai); printf(n); printf(n); 2021/3/1317例例3.4 3.4 編寫一個算法利用順序棧判斷一個字符串是否編寫一個算法利用順序棧判斷一個字符串是否是對稱串。所謂對稱串是指從左向右讀和從右向左是對稱串。所謂對稱串是指從左向右讀和從右向左讀的序列相同。讀的序列相同。解解 int symmetry(ElemType

14、 str)int symmetry(ElemType str) int i; ElemType e;SqStack int i; ElemType e;SqStack * *st;st; InitStack(st); InitStack(st); For(i=0;stri!=0;i+); For(i=0;stri!=0;i+); Push(st,stri); Push(st,stri); For(i=0;stri!=0;i+); For(i=0;stri!=0;i+); Pop(st,e); Pop(st,e); if(stri!=e) if(stri!=e) Return(0); Retur

15、n(0); Return(1); Return(1); 2021/3/13183.1.3 3.1.3 棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其基本運算的棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其基本運算的實現(xiàn)實現(xiàn) 采用鏈?zhǔn)酱鎯Φ臈７Q為鏈棧采用鏈?zhǔn)酱鎯Φ臈７Q為鏈棧, ,這里采這里采用單鏈表實現(xiàn)。用單鏈表實現(xiàn)。 鏈棧的優(yōu)點是不存在棧滿上溢的情況。鏈棧的優(yōu)點是不存在棧滿上溢的情況。我們規(guī)定棧的所有操作都是在單鏈表的表我們規(guī)定棧的所有操作都是在單鏈表的表頭進(jìn)行的頭進(jìn)行的, ,下圖是頭結(jié)點為下圖是頭結(jié)點為* *lheadlhead的鏈棧的鏈棧, ,第一個數(shù)據(jù)結(jié)點是棧頂結(jié)點第一個數(shù)據(jù)結(jié)點是棧頂結(jié)點, ,最后一個結(jié)最后一個結(jié)點是棧底結(jié)點。棧中元素自

16、棧頂?shù)綏５滓傈c是棧底結(jié)點。棧中元素自棧頂?shù)綏５滓来问谴问莂 a1 1、a a2 2、a an n。2021/3/1319鏈棧示意圖鏈棧示意圖2021/3/1320 鏈棧中數(shù)據(jù)結(jié)點的類型鏈棧中數(shù)據(jù)結(jié)點的類型LiStackLiStack定定義如下義如下: : typedef struct linknode typedef struct linknode ElemType data; ElemType data; / /* *數(shù)據(jù)域數(shù)據(jù)域* */ / struct linknode struct linknode * *next;next; / /* *指針域指針域* */ / LiStack; L

17、iStack;2021/3/1321在鏈棧中在鏈棧中, ,棧的基本運算算法如下棧的基本運算算法如下: :(1) (1) 初始化棧初始化棧initStack(&s)initStack(&s) 建立一個空棧建立一個空棧s s。實際上是創(chuàng)建鏈棧。實際上是創(chuàng)建鏈棧的頭結(jié)點的頭結(jié)點, ,并將其并將其nextnext域置為域置為NULLNULL。對應(yīng)。對應(yīng)算法如下算法如下: :void InitStack(LiStack void InitStack(LiStack * *&s)&s) s=(LiStack s=(LiStack * *)malloc(sizeof(LiStack);)malloc(siz

18、eof(LiStack);s-next=NULL;s-next=NULL; s2021/3/1322(2) (2) 銷毀棧銷毀棧ClearStack(&s)ClearStack(&s)釋放棧釋放棧s s占用的全部存儲空間。對應(yīng)算法占用的全部存儲空間。對應(yīng)算法: : void ClearStack(LiStack void ClearStack(LiStack * *&s)&s) LiStack LiStack * *p=s;p=s;* *q=s-next;q=s-next; while (q!=NULL) while (q!=NULL) free(p);free(p); p=q;p=q; q=

19、p-next;q=p-next; free(p); free(p); 2021/3/1323(3) (3) 求棧的長度求棧的長度StackLength(s)StackLength(s) 從第一個數(shù)據(jù)結(jié)點開始掃描單鏈表從第一個數(shù)據(jù)結(jié)點開始掃描單鏈表, ,用用n n記錄訪問的數(shù)據(jù)結(jié)點個數(shù)記錄訪問的數(shù)據(jù)結(jié)點個數(shù), ,最后返回最后返回n n值。對應(yīng)算法如下值。對應(yīng)算法如下: : int StackLength(LiStack int StackLength(LiStack * *s)s) int n=0; int n=0; LiStack LiStack * *p;p; p=s-next; p=s-n

20、ext; while(p!=NULL) while(p!=NULL) n+;p=p-next; n+;p=p-next; return(n); return(n); 2021/3/1324(4) (4) 判斷棧是否為空判斷棧是否為空StackEmpty(s)StackEmpty(s) 棧棧S S為空的條件是為空的條件是s-next=NULL,s-next=NULL,即即單鏈表中沒有數(shù)據(jù)結(jié)點。對應(yīng)算法如下單鏈表中沒有數(shù)據(jù)結(jié)點。對應(yīng)算法如下: : int StackEmpty(LiStack int StackEmpty(LiStack * *s)s) return(s-next=NULL); r

21、eturn(s-next=NULL); s2021/3/1325(5) (5) 進(jìn)棧進(jìn)棧Push(&s,e)Push(&s,e) 將新數(shù)據(jù)結(jié)點插入到頭結(jié)點之后。對將新數(shù)據(jù)結(jié)點插入到頭結(jié)點之后。對應(yīng)算法如下應(yīng)算法如下: :void Push(LiStack void Push(LiStack * *&s,ElemType e)&s,ElemType e) LiStack LiStack * *p;p;p=(LiStack p=(LiStack * *)malloc(sizeof(LiStack);)malloc(sizeof(LiStack);p-data=e;p-data=e;p-next=s

22、-next; p-next=s-next; / /* *插入插入* *p p結(jié)點作為第一個數(shù)據(jù)結(jié)點結(jié)點作為第一個數(shù)據(jù)結(jié)點* */ /s-next=p;s-next=p; 2021/3/1326(6) (6) 出棧出棧Pop(&s,&e)Pop(&s,&e) 在棧不為空的條件下在棧不為空的條件下, ,將頭結(jié)點后繼數(shù)據(jù)結(jié)點將頭結(jié)點后繼數(shù)據(jù)結(jié)點的數(shù)據(jù)域賦給的數(shù)據(jù)域賦給e,e,然后將其刪除。對應(yīng)算法如下然后將其刪除。對應(yīng)算法如下: :int Pop(LiStack int Pop(LiStack * *&s,ElemType &e)&s,ElemType &e) LiStack LiStack * *

23、p;p;if (s-next=NULL) if (s-next=NULL) return 0; / return 0; /* *棧空的情況?？盏那闆r* */ /p=s-next;p=s-next; / /* *p p指向第一個數(shù)據(jù)結(jié)點指向第一個數(shù)據(jù)結(jié)點* */ /e=p-data;e=p-data;s-next=p-next;s-next=p-next;free(p);free(p);return 1;return 1; 2021/3/1327(7) (7) 取棧頂元素取棧頂元素GetTop(s) GetTop(s) 在棧不為空的條件下在棧不為空的條件下, ,將頭結(jié)點后繼將頭結(jié)點后繼數(shù)據(jù)結(jié)點的

24、數(shù)據(jù)域賦給數(shù)據(jù)結(jié)點的數(shù)據(jù)域賦給e e。對應(yīng)算法如下。對應(yīng)算法如下: : int GetTop(LiStack int GetTop(LiStack * *s,ElemType &e)s,ElemType &e) if (s-next=NULL) if (s-next=NULL) return 0; / return 0; /* *?？盏那闆r棧空的情況* */ / e=s-next-data; e=s-next-data; return 1; return 1; 2021/3/1328(8) (8) 顯示棧中元素顯示棧中元素DispStack(s)DispStack(s) 從第一個數(shù)據(jù)結(jié)點開始掃

25、描單鏈表從第一個數(shù)據(jù)結(jié)點開始掃描單鏈表, ,并輸并輸出當(dāng)前訪問結(jié)點的數(shù)據(jù)域值。對應(yīng)算法如下出當(dāng)前訪問結(jié)點的數(shù)據(jù)域值。對應(yīng)算法如下: : void DispStack(LiStack void DispStack(LiStack * *s)s) LiStack LiStack * *p=s-next;p=s-next; while (p!=NULL) while (p!=NULL) printf(%c ,p-data); printf(%c ,p-data); p=p-next; p=p-next; printf(n); printf(n); 2021/3/1329例例3.5 3.5 編寫一個算

26、法判斷輸入的表達(dá)式中括號是否匹配（假設(shè)編寫一個算法判斷輸入的表達(dá)式中括號是否匹配（假設(shè)只有左、右圓括號）。只有左、右圓括號）。解解 :int Match(char exp,int n):int Match(char exp,int n) int i=0; char e;SqStack int i=0; char e;SqStack * *st;st; InitStack(st); InitStack(st); while(in) while(i=0 & ch=0 & ch=0 & ch=0 & ch=9)/* *為數(shù)字字符為數(shù)字字符* */ / d=10 d=10* *d+ch-0; d+ch-0; ch=postexpt;t+;ch=postexpt;t+; st.top+