計算機軟件技術基礎34-棧-課件

計算機軟件技術基礎3.4棧3.4棧一、棧的定義二、棧的運算三、棧的存儲結構及算法四、棧的應用一、棧的定義棧是限定只能在表的一端進行插入和刪除操作的線性表。允許插入和刪除的一端稱為棧頂(top)，另一端稱為棧底(bottom)。設棧s=(a1,a2,...,an)，a1稱為棧底元素，an稱為棧頂元素。棧中元素按a1,a2,...,an次序進棧，又按an,...,a2,a1次序退棧。因此棧的操作特點是：后進先出（LIFO）；n=0時稱為空棧。anan-1a1stack[n-1]top

棧頂

進棧

stack[0]棧底

出棧二、棧的運算1.初始化棧 INISTACK(S)

將棧S置成空棧2.判空棧 ISEMPTY(S) 若棧S是空棧，返回“真”，

否則返回“假”3.進棧 PUSH(S,x) 在棧S頂部插入（壓入）元素x4.出棧 POP(S) 若棧S不空，刪除頂部元素5.取棧頂 GETTOP(S) 取棧頂元素，并不改變棧中內容三、棧的存儲結構及算法1.順序棧1)類型定義順序棧用向量作為棧的存儲結構，可用一維數(shù)組s[1:m]表示。其中m表示棧的最大容量。用一個簡單變量top來指示棧頂位置，稱為棧頂指示器。top=0表示?？眨瑃op=m表示棧滿。類型定義structSeqStack{ elemtypestack[MAXSIZE]; inttop;};三、棧的存儲結構及算法2）順序棧初始化

⑴操作:

建一空棧，將棧頂位設置為-1

⑵接口： 入口和出口參數(shù)均為堆棧指針s

⑶算法描述：令棧頂位s.top為-1

⑷函數(shù)實現(xiàn)：voidiniStack(SeqStack&s){ s.top=-1;} 三、棧的存儲結構及算法3)進棧算法

⑴操作:先將棧頂位置加一將數(shù)據(jù)放入棧頂位置

⑵接口：

入口參數(shù)：堆棧指針s，新數(shù)據(jù)元素x出口參數(shù):堆棧指針s函數(shù)值： 成功則返回1(用true表示),

失敗則返回0(用false表示)三、棧的存儲結構及算法 (3)算法描述大家學習辛苦了，還是要堅持繼續(xù)保持安靜三、棧的存儲結構及算法(4)函數(shù)實現(xiàn)intpush(SeqStack&s,elemtypex){ if(s.top>=MAXSIZE-1)return(false); s.top++; s.stack[s.top]=x; return(true);} 三、棧的存儲結構及算法4)出棧算法

(1)操作取棧頂位置內數(shù)據(jù).再將棧頂位置減一(2)接口

入口參數(shù)：堆棧指針s出口參數(shù):堆棧指針s函數(shù)值：成功則返回數(shù)據(jù)元素x,失敗則返回NULL三、棧的存儲結構及算法 (3)算法描述三、棧的存儲結構及算法(4)函數(shù)實現(xiàn)elemtypepop(SeqStack&s){ if(s.top<0) returnNULL; s.top--; returns.stack[s.top+1];}三、棧的存儲結構及算法5)雙棧操作順序棧的缺點：棧滿后不能進行進棧操作，否則將產生“上溢”錯誤同時使用同類的兩個棧，充分利用剩余空間 兩棧共用一個存儲空間，分別從兩端向中間增長a1a2……

an……

bm……

b2b101n-1出棧MAXSIZE-m

MAXSIZE-2

MAXSIZE-1棧1底棧1頂入棧棧2頂棧2底三、棧的存儲結構及算法2.鏈棧鏈棧是用鏈表作為棧的存儲結構，top為棧頂指針，指示棧頂元素位置，若top=NULL,則表示?？铡ｆ湕Ｒ话悴粫霈F(xiàn)上溢，除非內存中已不存在可用空間。使用單鏈表，不設頭結點插入和刪除僅在表頭一端棧頂top：指始結點，浮動空棧用top=NULL實現(xiàn)鏈棧結點動態(tài)分配，空間無限鏈棧定義與單鏈表相同

structlink*top；.a2top

aia1NULL四、棧的應用表達式求值

1）高級語言中的表達式是用人們熟悉的公式形式書寫的，編譯系統(tǒng)要根據(jù)表達式的運算順序將它翻譯成機器指令序列。

2）為解決運算順序問題，把運算符分成若干等級，稱為優(yōu)先數(shù)。

3）為進行表達式的翻譯，需設立兩個棧，分別存放操作數(shù)(NS)和運算符(OS)。四、棧的應用4）首先在OS中放入表達式結束符“#”，然后自左至右掃描表達式，根據(jù)掃描的每一個符號作如下不同處理：①若為操作數(shù)，將其壓入NS棧②若為運算符，需看當前OS的棧頂元素：若OS棧頂運算符小于或等于當前運算符的優(yōu)先數(shù)，則將當前運算符壓入OS棧。若OS棧頂運算符大于當前運算符的優(yōu)先數(shù)，則從NS棧中彈出兩個操作數(shù)，設為x、y，再從OS棧中彈出一個運算符，設為θ，由此構成一條機器指令：yθx→T，并將結果T送入NS棧。③若當前運算符為“#”，且OS棧頂也為“；”，則表示表達式處理結束，此時NS棧頂?shù)脑丶礊榇吮磉_式的值。四、棧的應用5)算符優(yōu)先+-*/()#+>><<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=四、棧的應用 6)函數(shù)實現(xiàn)doubleExp(){

inistack(OS);inistack(NS);//初始化棧OS和NS push(OS,’#’);//在OS棧中壓入結束符

t=0;//t=0表示掃描下一個符號

while(t!=2){//當處理沒有結束時循環(huán)

if(t==0)w=getchar();//讀取一個符號

if(w為操作數(shù))push(NS,w);//操作數(shù)壓NS棧

else{

q=top(OS);//查看OS棧頂元素

if(q<=w){push(OS,w);t=0;}//不大于時

else{//處理結束,t=2

if(q==‘#’&&w==‘#’){z=pop(NS);t=2;}

else{//計算,t=1

x=pop(NS);y=pop(NS);

q=pop(OS);x=yqx;

push(NS,x);t=1;}}}}}inttop(seqstack&s)

{

if(s.top==-1)return(NULL);

return(s.data[s.top]);

}需編寫函數(shù)實現(xiàn)四、棧的應用7)舉例

設表達式為：3*(7-2)#

步驟操作符棧操作數(shù)棧輸入字符操作1#3*(7-2)#壓入“3”2#3*(7-2)#壓入“*”3#*3(7-2)#壓入“(”4#*(37-2)#壓入“7”5#*(37-2)#壓入“-”6#*(-372)#壓入“2”7#*(-372)#彈出“-”壓入7-28#*(35)#彈出“(”9#*35#計算3*510#15#操作符棧空，結束3.4棧五、小結

1、理解棧的概念和特點

2、掌握進/出棧的算法

3、了解棧的應用：表達式求值，背包問題3.5隊列一、隊列的定義及運算二、順序隊列三、鏈隊列四、隊列的應用3.5隊列 一、隊列的定義及基本操作1、隊列的定義隊是限定在表的一端進行插入，在表的另一端進行刪除的線性表。允許插入的一端稱為隊尾(rear)，允許刪除的一端稱為隊頭(front)。隊用移動rear和front指示器進行插入和刪除。隊中元素按a1,a2,…,an次序入隊和出隊。因此隊的操作特點是：先進先出（FIFO）；n=0時稱為空隊。A1A2A3A4A5……An入隊出隊隊頭（front）隊尾（rear）一、隊列的定義及運算2、隊列的基本操作初始化隊列iniqueue(Q) 將隊列Q置成空判空隊列 empty(Q) 若隊列Q是空，返回“真”，否則返回“假”入隊列 enqueue(Q,x)在隊列Q尾部插入元素x出隊列 dlqueue(Q,x)若隊列Q不空，刪除頭部元素取隊頭 gethead(Q,x)取隊列Q頭元素，但不改變隊列Q中內容3.5隊列 二、順序隊列順序隊用向量作為隊的存儲結構，可用一維數(shù)組Q[1:m]表示。其中m表示隊的最大容量。初始狀態(tài)rear=front=0，隊空，入隊時rear增1，出隊時front增1，當front=rear時隊空，當rear=m時無法再繼續(xù)入隊，但此時隊中空間并不一定滿(只有當rear-front=m時才真正滿)，這種現(xiàn)象稱為“假溢出”。rear=3front=3a5a4a3a2a1rear=5front=0a5a4rear=5front=3隊空 隊滿 假溢出循環(huán)隊列51

42

3rear=3front=5a1a2a3為避免假溢出的發(fā)生，我們假想把存放隊列的數(shù)組形成一個頭尾相接的環(huán)形，稱為循環(huán)隊列。二、順序隊列1、順序隊列的類型定義

structSeqQueue{ elemtypequeue[MAXSIZE+1]；

intfront；

intrear；

}Q; queue[0]不用，實際占用MAXSIZE個單元;隊列空：隊頭=隊尾，即front=rear隊列滿：隊尾=MAX，即rear=MAXSIZE*注意：假滿，若front≠0時，實際還有空間二、順序隊列解決方法：若將整個隊列前挪，至隊頭front=0，花費太大。常用的是：循環(huán)隊列：這種隊列結構首尾相連,當尾指針rear=MAXSIZE時重指向1。(用rear=(rear+1)%MAXSIZE修改rear指針即可)由于queue[0]不用，因此當front=(rear+1)%MAXSIZE時隊列為滿;當front=rear時隊列為空;不使用queue[0]就是為了能夠比較方便地判斷隊列的空與滿二、順序隊列2、順序隊列的初始化

⑴操作:

建一空隊列，隊頭隊尾均置零

⑵接口：隊列指針q(q=&Q) ⑶算法描述：

q－>front=0;q－>rear=0; ⑷函數(shù)實現(xiàn)：

voidiniQueue(SeqQueue&q){ q.front=0; q.rear=0; }二、順序隊列3、循環(huán)隊列的入隊操作

⑴操作:若隊列滿，返回false(q->front=(q->rear+1)%MAXSIZE)隊尾指針加一q->rear=(q->rear+1)%MAXSIZE將數(shù)據(jù)放入隊尾q->queue[q->rear]=x返回true ⑵接口：

入口參數(shù)：隊列指針q，新數(shù)據(jù)元素x出口參數(shù):函數(shù)值：成功true;失敗false二、順序隊列 (3)算法描述二、順序隊列(4)函數(shù)實現(xiàn)intenQueue(SeqQueue&q,elemtypex){ if(q.front=(q.rear+1)%MAXSIZE) return(false);//隊列已滿，入隊錯誤

q.rear=(q.rear+1)%MAXSIZE;//更改尾指針

q.queue[q.rear]=x; //插入數(shù)據(jù)

return(true);}

二、順序隊列3、循環(huán)隊列的出隊操作

⑴操作:若隊列空，返回NULL (q->front==q->rear)隊頭指針加一 q->front=(q->front+1)%MAXSIZE返回隊頭數(shù)據(jù) q->queue[q->front] ⑵接口：入口參數(shù)：隊列指針q，出口參數(shù):函數(shù)返回值：成功：數(shù)據(jù)元素;失敗返回NULL二、順序隊列 (3)算法描述二、順序隊列(4)函數(shù)實現(xiàn)elemtypedlQueue(SeqQueue&q){ if(q.front==q.rear) returnNULL; //隊列為空，返回NULL q.front=(q.front+1)%MAXSIZE;//取隊頭元素

returnq.queue[q.front];}3.5隊列 三、鏈隊列鏈隊列是用鏈表作隊列的存儲結構，當隊列的容量無法預先估計時采用。在鏈隊列中設一個頭結點，頭指針front始終指向頭結點，尾指針rear指向隊尾元素，當rear=front表時隊空。結點動態(tài)分配，不會溢出鏈隊列結點定義與單鏈表一樣qdata指針data指針data指針data指針frontrearQSqdata指針data指針data指針data指針frontrearQS三、鏈隊列1、結點結構定義:structLNode{ elemtype