版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、3.1 棧 ( Stack )3.1.1 棧的定義及運算假設(shè)棧S=(a1,a2,a3,an),則棧底元素?棧頂元素?棧中元素按a1,a2,a3,an的次序進棧,退棧的第一個元素? 只允許在一端插入和刪除的順序表 允許插入和刪除 的一端稱為棧頂 (top), 另一端稱為棧底(bottom) 特點 后進先出 (LIFO)棧的示意圖出棧進棧棧頂棧底ana2a1例:對于一個棧,給出輸入項A、B、C,如果輸入項序列由A B C組成,試給出所有可能的輸出序列。A進 A出 B進 B出 C進 C出 ABCA進 A出 B進 C進 C出 B出 ACBA進 B進 B出 A出 C進 C出 BACA進 B進 B出 C進
2、 C出 A出 BCAA進 B進 C進 C出 B出 A出 CBA不可能產(chǎn)生輸出序列CAB棧的順序存儲結(jié)構(gòu)順序棧的定義typedef int DataType;#define maxsize 64typedef struct DataType datamaxsize; int top;SeqStack; 設(shè)s是SeqStack類型的指針變量。 sdata0是棧底元素 進棧時需將stop加1,退棧時需將stop 減1相關(guān)概念:空棧和棧滿 因此: stoptop =stacksize-1 表示棧滿。 當(dāng)棧滿時再做進棧運算必定產(chǎn)生空間溢出,簡稱“上溢” 當(dāng)??諘r再做退棧運算也將產(chǎn)生溢出,簡稱“下溢”。相
3、關(guān)概念:上溢和下溢進出棧示例toptoptopAABCDEAB空棧 A進棧 B C D E 進棧E D C 出棧toptop-1約定棧頂指針指向棧頂元素的位置注意:棧的基本操作1、初始化2、判棧是否非空3、進棧4、退棧5、取棧頂元素(1)InitStack(&s) 初始化:初始化一個新的棧。(2)StackEmpty(s) 棧空判斷:若棧s空,則返回TRUE;(3)Push(&s,x) 入棧:在棧s的頂部插入元素x,若棧滿,則返回FALSE;(4)Pop(&s) 出棧:若棧s不空,則返回棧頂元素,并從棧頂中刪除該元素;否則,返回空元素NULL。(5)GetTop(s,x
4、) 取棧元素:若棧s不空,則返回棧頂元素;棧的基本操作void InitStack(SeqStack *s) s-top-1; 置空棧void ClearStack(SeqStack *s) s-top-1; 棧的基本運算判??読nt StackEmpty(SeqStack *s) if (s-top=0) return 0; else return 1;int Push(SeqStack *s,DataType x) s-top+; s-datas-topx; return 1; if (s-top=maxsize-1) printf(“overflown”); return 0; else
5、進棧DataType Pop(SeqStack *s) DataType x x= s-datas-top; s-top-; return(x); if (StackEmpty(s) printf(“underflown”); return 0; else出棧DataType GetTop(SeqStack *s, DataType x) x= s-datas-top; return(x); if (StackEmpty(s) printf(“underflown”); return 0; else 取棧頂元素3.2 棧的應(yīng)用舉例 由于棧結(jié)構(gòu)具有的后進先出的固有特性,致使棧成為程序設(shè)計中常用的
6、工具。以下是幾個棧應(yīng)用的例子。 3.2.1 數(shù)制轉(zhuǎn)換 十進制N和其它進制數(shù)的轉(zhuǎn)換是計算機實現(xiàn)計算的基本問題,其解決方法很多。 原理: N=(N div d)*d+ N mod d ( 其中:div為整除運算,mod為求余運算) n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2計算順序輸出順序(2504)8(1348)10數(shù)制轉(zhuǎn)換算法:void conversion( ) InitStack(s); /建空棧 scanf(“%d”,&x); /輸入一個非負十進制整數(shù) while(x!=0) / x不等于零 循環(huán) push(s, x% 8
7、); / x/8第一個余數(shù)進棧 x=x/8; /整除運算 while(! StackEmpty(s) ) x=pop(s); printf(“%d”,x); /依次輸出棧頂元素 3.2.4中綴表達式求值表達式由操作數(shù)(operand)、運算符(operator)和界限符組成的。 在處理表達式前,首先設(shè)置兩個棧:(1)操作數(shù)棧(OPND):存放操作數(shù)(2)運算符棧(OPTR):存放運算符。 在運算符棧中先壓入結(jié)束符“#”。運算符可以是算術(shù)運算符、關(guān)系運算符和邏輯符;界限符為左右括號和標(biāo)識表達式結(jié)束的結(jié)束符。算符優(yōu)先關(guān)系表 表達式中任何相鄰運算符c1、c2的優(yōu)先關(guān)系有: c1c2:c1的優(yōu)先級高于
8、c2+ c2 c1 -*/()#+ - * / ( ) # = 算符間的優(yōu)先關(guān)系表注: c1 c2是相鄰算符, c1在左, c2在右讀出一個符號后,作如下處理:(1)是操作數(shù):將其壓入操作數(shù)棧,讀下一個符號。中綴表達式求值算法 (2)是運算符:1)比棧頂高:壓入運算符棧,并讀下一個符號。與棧頂運算符的優(yōu)先級比較2)比棧頂?shù)停簞t從操作數(shù)棧連續(xù)退出兩個操作數(shù)從運算符棧中退出一個運算符,然后作相應(yīng)的運算,并將運算結(jié)果壓入操作數(shù)棧。此時讀出的運算符下次重新考慮3)假如讀出的是“)”,則:A)若運算符棧棧頂不是“(”,連續(xù)退出兩操作數(shù),退出一個運算符,作相應(yīng)的運算,將結(jié)果壓操作數(shù)棧,然后繼續(xù)執(zhí)行AB)若
9、運算符棧棧頂為“(”,則消去括號,依次讀下一個符號 int express ( ) /運算數(shù)棧,OP為運算符集合。 InitStack(OPTR); Push (OPTR, # ); InitStack(OPND); c=getchar( ); 在算法中,建立了兩個工作棧。一個是OPTR棧,用以保存運算符一個是OPND棧,用以保存操作數(shù)或運算結(jié)果。 while(c!= # | GetTop(OPTR)!=#) if(! In(c,OP) / In(c, OP)判斷c是否 是運算符的函數(shù) Push(OPND,c); /不是運算符則進棧 c=getchar(); else續(xù) switch (Pre
10、cede(GetTop(OPTR), c) case : /棧頂算符優(yōu)先權(quán)高,出棧并將運算結(jié)果入棧OPND op=Pop(OPTR); b=Pop(OPND); a= Pop(OPND); Push(OPND,Operate(a, op, b); break; return GetTop(OPND);char Precede (char sym1,char sym2) /*比較兩操作符優(yōu)先級*/int i; char chl2; int ind2;char re77=, , , , ,=; chl0=sym1; chl1=sym2; for(i=0;i2;i+) switch(chli) case +:indi=0;break; case -:indi=1;break; case *:indi=2;break; case /:indi=3;break; case (:indi=4;break; case ):indi=5;break; case #:indi=6;break; defaul:printf(Error!n);return(0); return(reind0ind1);double Operate(double a,char sym,doubl
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 業(yè)務(wù)技術(shù)工作總結(jié)范文
- 慶陽市政務(wù)服務(wù)中心招聘工作人員考試試卷及答案
- 廣州市天河區(qū)招聘事業(yè)單位人員考試試卷及答案
- 愛崗敬業(yè)的演講稿范例集錦七篇
- 第一學(xué)期的工作計劃四篇
- 范文父母感恩演講稿范文集合九篇
- 會計類實習(xí)報告模板七篇
- 新學(xué)期的計劃范文錦集10篇
- 二級建造師之二建建設(shè)工程法規(guī)及相關(guān)知識題庫帶答案(基礎(chǔ)題)
- 有理數(shù)的減法教案2024-2025學(xué)年七年級人教版數(shù)學(xué)
- 2024二十屆三中全會知識競賽題庫及答案
- -投標(biāo)技術(shù)標(biāo)書范文模板-人員配備與團隊構(gòu)建
- 2024年輔警招聘考試試題庫及完整答案(全優(yōu))
- 統(tǒng)編版高一語文必修上冊期末復(fù)習(xí):文言文閱讀 練習(xí)題匯編(含答案解析)
- 一年級數(shù)學(xué)專項練習(xí)(大括號問題、求總數(shù)、求部分數(shù)、一圖四式)
- 檔案整理及數(shù)字化服務(wù)方案
- 《色彩基礎(chǔ)知識》PPT課件(詳解)
- 腹部超聲標(biāo)準ppt課件
- 全球4G頻段劃分和各運營商頻段
- 利雅路燃燒器常見故障及維修方法
- 垃圾分類日常檢查細則附垃圾分類檢查記錄表
評論
0/150
提交評論