計(jì)算機(jī)軟件技術(shù)基礎(chǔ)34-棧-課件

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

棧頂

進(jìn)棧

stack[0]棧底

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

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

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

⑴操作:

建一空棧，將棧頂位設(shè)置為-1

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

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

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

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

⑵接口：

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

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

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

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

an……

bm……

b2b101n-1出棧MAXSIZE-m

MAXSIZE-2

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

structlink*top；.a2top

aia1NULL四、棧的應(yīng)用表達(dá)式求值

1）高級語言中的表達(dá)式是用人們熟悉的公式形式書寫的，編譯系統(tǒng)要根據(jù)表達(dá)式的運(yùn)算順序?qū)⑺g成機(jī)器指令序列。

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

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

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

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

while(t!=2){//當(dāng)處理沒有結(jié)束時循環(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{//處理結(jié)束,t=2

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

else{//計(jì)算,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ù)實(shí)現(xiàn)四、棧的應(yīng)用7)舉例

設(shè)表達(dá)式為：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#計(jì)算3*510#15#操作符棧空，結(jié)束3.4棧五、小結(jié)

1、理解棧的概念和特點(diǎn)

2、掌握進(jìn)/出棧的算法

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

42

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

structSeqQueue{ elemtypequeue[MAXSIZE+1]；

intfront；

intrear；

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

⑴操作:

建一空隊(duì)列，隊(duì)頭隊(duì)尾均置零

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

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

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

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

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

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

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

return(true);}

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

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

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