數(shù)據(jù)結(jié)構(gòu)(C語言版) 第3章 棧與隊列

《數(shù)據(jù)結(jié)構(gòu)(C語言版) 第3章 棧與隊列》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)(C語言版) 第3章 棧與隊列（25頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第3章 棧與隊列棧與隊列：限定操作的線性表。1 棧1.1 邏輯結(jié)構(gòu)1.1.1 定義限定只能在表的一端進行插入、刪除的線性表。棧頂top，棧底bottom。后進先出LIFO表(Last In First Out)1.1.2 基本操作進棧Push/出棧Pop取棧頂元素GetTop判別棧空isEmpty/棧滿isFull1.1.3 應(yīng)用領(lǐng)域?qū)嵗骸斑M制數(shù)轉(zhuǎn)換”、“表達式求值”、“函數(shù)調(diào)用關(guān)系”、“括號匹配問題”、“漢諾塔問題”、“迷宮問題”、“九連環(huán)” 許多問題的求解分為若干步驟，而當(dāng)前步驟的解答，是建立在后繼步驟的解答基礎(chǔ)上的。=問題分解的步驟和求解的步驟次序恰好相反。1.2 順序棧/ 項目路徑：

2、1順序棧/1.2.1 類的定義const int StackSize=10;template class SeqStack T m_DataStackSize; / 存放棧元素的數(shù)組 int m_Top; / 棧頂指針，表示下一個進棧元素的下標(biāo)public: SeqStack( ); SeqStack(SeqStack &Q); SeqStack( ); void Push(T e); / 進棧 T Pop( ); / 出棧 T GetTop( ); / 取棧頂元素（不刪除） bool isEmpty( ); / 判斷棧是否為空;1.2.2 基本操作1.2.2.1 構(gòu)造/析構(gòu)template

3、SeqStack:SeqStack( ) / 構(gòu)造 m_Top=0; template SeqStack:SeqStack(SeqStack &Q) / 拷貝構(gòu)造 m_Top = Q.m_Top; for(int i=0; im_Top; i+) m_Datai=Q.m_Datai;template SeqStack:SeqStack( ) / 析構(gòu)1.2.2.2 狀態(tài)判斷/ 判斷棧是否為空template bool SeqStack:isEmpty( ) if(m_Top=0) return true; return false;/ 判斷棧是否為滿template bool SeqStack

4、:isFull( ) if(m_Top=StackSize) return true; return false;1.2.2.3 進棧/出棧template void SeqStack:Push(T e) / 進棧 if(m_Top = StackSize) throw 上溢; m_Datam_Top=e; m_Top+;template T SeqStack:Pop( ) / 出棧 if(m_Top=0) throw 下溢; m_Top-; return m_Datam_Top;template T SeqStack:GetTop() / 取棧頂元素值if(m_Top=0) throw 下溢

5、; return m_Datam_Top-1;1.3 順序棧的聯(lián)想缺點：空間浪費思考：二棧合用同一順序空間？ / 項目路徑：1順序棧(2個)/1.4 鏈棧/ 項目路徑：2鏈棧/1.4.1 類的定義template struct LinkNode T data; LinkNode *next; ;template class LinkStack LinkNode *m_Top; / 棧頂指針：鏈表頭指針public: LinkStack( ); LinkStack( ); void Push(T x); / 進棧 T Pop( ); / 出棧 T GetTop( ); / 取棧頂元素（不刪除）

6、bool isEmpty( ); / 判斷鏈棧是否為空棧;/ 棧滿：系統(tǒng)內(nèi)存不夠1.4.2 基本操作1.4.2.1 構(gòu)造/析構(gòu)template LinkStack:LinkStack( ) m_Top = NULL; template LinkStack:LinkStack( ) while(m_Top) LinkNode *p=m_Top-next; delete m_Top; m_Top=p; 1.4.2.2 進棧/出棧/ 進棧template void LinkStack:Push(T e) LinkNode *newp = new LinkNode; newp-data = e; ne

7、wp-next = m_Top; m_Top = newp; / 出棧template T LinkStack:Pop( ) if(m_Top=NULL) throw 下溢; T e = m_Top-data; / 暫存棧頂元素 LinkNode *p = m_Top; m_Top = m_Top-next; delete p; / 刪除首結(jié)點 return e;2 棧的應(yīng)用 常識體驗：函數(shù)調(diào)用棧2.1 進制轉(zhuǎn)換示例數(shù)據(jù)： (1348)10=(2504)8，除8取余的過程：Nn div 8n mod 8134816841682102125202void Conversion(int n,int

8、 k) LinkStack S; while( n!=0 ) S.Push(n%8); / 進棧次序: 個位、十位 .高位 n=n/8; while(!S.isEmpty() coutS.Pop(); / 出棧次序: 高位.個位2.2 檢驗括號匹配示例數(shù)據(jù)：Equal( (a)(b) ) : 0Equal( (a)(b) ) : 1Equal( (a)(b) ) : -1int Equal(char s) LinkStack S; for(int i=0; si; i+) switch(si) case (: S.Push(si); break; case ): if(S.isEmpty()

9、return(-1); / )多 S.Pop(); break; if( !S.isEmpty() ) return(1); / (多 return(0); / 完全匹配2.3 迷宮算法(思考) 2.4 后綴表達式求值中綴表達式后綴表達式A+B*CABC*+B*(D-C)+ABDC-*A+2*(3-4)+5234-*5+算符在運算數(shù)之間算符在運算數(shù)之后，沒有括號，算符沒有優(yōu)先級按“算符優(yōu)先級”求值按“順序計算法”求值輔助數(shù)據(jù)結(jié)構(gòu)：一個運算數(shù)棧OPND。算法：自左向右掃描后綴表達式，直至遇到結(jié)束符為止。 遇算數(shù)：進棧， 遇算符：退棧二數(shù)，運算結(jié)果再進棧，/ 只能處理1位數(shù)運算數(shù)float Pos

10、tExpression(char s) LinkStack OPND; / 運算數(shù)棧 for(int i=0; si; i+) if(si=0 & sipre_op：op進棧； 若oppre_op：退棧，pre_op加入Post； 若op=pre_op：退棧。技術(shù)細(xì)節(jié)： #：優(yōu)先級最低的運算符。 為保證第一個運算符有“上一個運算符”：OPTR.Push(#); 為保證最后一個運算符能被執(zhí)行： 3*5+2#分析：Mid =2*(3-4/5)+6# = Post=2345/-*6+c=*c=(c=- c=/ c=)c=)C=)c=+c=+c=+C=#void MidToPost(char Mid,

11、char Post) LinkStack OPTR; / 運算符棧 OPTR.Push(#); int iMid=0,iPost=0; char c=MidiMid+; while(c!=# | OPTR.GetTop()!=#) if(c=0 & c=9) PostiPost+=c; c=MidiMid+; continue; char pre_op=OPTR.GetTop(); switch( Precede(pre_op,c) ) / 比較算符優(yōu)先級 case : / pre_op : / pre_op c OPTR.Pop(); PostiPost+=pre_op; PostiPost

12、=0;/ 算符優(yōu)先級比較的代碼分析：先乘除，后加減；從左到右；先括號內(nèi)，再括號外。后算符前算符()#(#, , , , , , / + , , , , , , / - , , , , , , / * , , , , , , / / , , , , , , , , 0, , , / ) , , , , pre_op：OPTR.Push(c); 若oppre_op：OPTR.Pop(); OPND退棧兩次，計算，再進棧 若op=pre_op：OPTR.Pop();跟蹤示例：3*(7-2)#c=3C=*c=(c=7c=-c=2C=)c=)c=#float MidExpression(char s)

13、/ 3*(7-2) LinkStack OPND; / 運算數(shù)棧 LinkStack OPTR; OPTR.Push(#); / 運算符棧 int i=0; while(si!=# | OPTR.GetTop()!=#) char c=si; if(c=0 & c=9) OPND.Push(c-0); i+; continue; char pre_op=OPTR.GetTop(); switch( Precede(pre_op, c) ) case : / pre_op : / pre_op c 執(zhí)行pre_op OPTR.Pop(); float opd1=OPND.Pop(); float

14、 opd2=OPND.Pop(); OPND.Push( Eval(opd2,pre_op,opd1) ); return(OPND.GetTop(); 測試案例：#， 3#，3+5#，3+5+2#3*5+2#， 3+5*2#，(3+5)*2#， (3+5)*(2+1)#，(3+5)/2+1)*2# 作業(yè)與上機實現(xiàn)棧類和中綴表達式求值功能。層次1：運算數(shù)可以實數(shù)、負(fù)數(shù)層次2：表達式語法檢查、報錯誤位置層次3：多個表達式依次求值（含變量）層次4：超長運算數(shù)的表達式求值附錄：九連環(huán)的玩法void down_1(int n) printf(%2ddown,n); /下第n個環(huán)void down_12

15、() printf(12down,); /下1、2環(huán)void up_1(int n) printf(%2dup, ,n); /上第n個環(huán)void up_12() printf(12up, ); /上1、2環(huán)void huan_down(int n) /下前n個環(huán) if(n=1) down_1(n); return; if(n=2) down_12(); return; huan_down(n-2); down_1(n); huan_up(n-2); huan_down(n-1);void huan_up(int n) /上前n個環(huán) if(n=1) up_1(n); return; if(n=2

16、) up_12(); return; huan_up(n-1); huan_down(n-2); up_1(n); huan_up(n-2);/打印下九連環(huán)的步驟main() huan_down(9); 3 隊列3.1 邏輯結(jié)構(gòu)只能在一端(隊尾rear)插入，在另一端(隊頭front)刪除的線性表。先進先出表FIFO(First In First Out)基本操作：進隊列Enter/出隊列Leave 判別隊列空isEmpty/隊列滿isFull應(yīng)用領(lǐng)域：排隊模型。排隊問題無處不在，各種服務(wù)行業(yè)、甚至生產(chǎn)管理中都存在排隊問題。3.2 鏈隊列/ 項目路徑：3鏈隊列/ 3.2.1 類的定義templ

17、ate struct LinkNode T data; LinkNode *next; ;template class LinkQueue LinkNode *m_Front; / 隊頭指針 LinkNode *m_Rear; / 隊尾指針public: LinkQueue( ); LinkQueue( ); void Enter(T e); / 進隊列 T Leave( ); / 出隊列 T GetFront( ); / 取隊列的隊頭元素 bool isEmpty( ); / 判斷隊列是否為空;3.2.2 基本操作3.2.2.1 構(gòu)造/析構(gòu)template LinkQueue:LinkQue

18、ue() m_Front = m_Rear = NULL; template LinkQueue:LinkQueue( ) /* 銷毀隊列 */ 3.2.2.2 進/出隊列/ 進隊列template void LinkQueue:Enter(T e) LinkNode *newp = new LinkNode; newp-data=e; newp-next=NULL; if(m_Front=NULL) m_Front=m_Rear=newp; else m_Rear-next=newp; m_Rear=newp; / 出隊列template T LinkQueue:Leave() if(m_F

19、ront=NULL) throw 下溢; LinkNode *p=m_Front; T e=p-data; /暫存隊頭元素 m_Front=p-next; delete p; if(m_Front=NULL) m_Rear=NULL; return e;/取隊頭元素template T LinkQueue:GetFront() if(m_Front=NULL) throw 下溢; return m_Front-data; 3.2 順序隊列/ 項目路徑：4循環(huán)隊列/3.2.1 類的定義const int QueueSize=6; / 隊列存儲空間的長度template class CirQueu

20、e T m_DataQueueSize; / 存放隊列元素的數(shù)組 int m_Front; / 隊頭指針 int m_Rear; / 隊尾指針public: CirQueue( ); CirQueue( ); void Enter(T e); / 進隊列 T Leave( ); / 出隊列 T GetFront( ); / 取隊頭元素（不刪除） bool isEmpty( ); / 判斷隊列是否為空 bool isFull( ); / 判斷隊列是否為滿; 3.2.2 隊頭/尾指針的取值討論=循環(huán)隊列 以往的常識：進隊列m_Rear+； 出隊列m_Front+ 常識中隱藏了陷阱：假溢出！ 循環(huán)隊

21、列： 進隊列m_Rear =(m_Rear +1)% QueueSize； 出隊列m_Front=(m_Front+1)% QueueSize； 約定：m_Rear下一個進隊列元素的位置m_Front隊列不空時，指向首元素；隊列為空時，等于rear隊列空時m_Front=m_Rear隊列滿時(m_Rear+1) % QueueSize=m_Front=必須浪費一個結(jié)點空間3.2.3 基本操作3.2.3.1 構(gòu)造/析構(gòu)template CirQueue:CirQueue( ) m_Front = m_Rear = 0; template CirQueue:CirQueue( ) 3.2.3.2

22、進/出隊列/ 進隊列template void CirQueue:Enter(T e) if(m_Rear+1) % QueueSize=m_Front) throw 上溢; m_Datam_Rear = e; m_Rear = (m_Rear+1) % QueueSize; / 出隊列template T CirQueue:Leave() if(m_Rear=m_Front) throw 下溢; T e = m_Datam_Front; m_Front = (m_Front+1) % QueueSize; return e;/ 隊列長度template int CirQueue:Length

23、() return (m_Rear-m_Front+QueueSize)% QueueSize; 3.2.4 循環(huán)隊列的其他設(shè)計方案方法一：增加成員變量m_Flag （0:非滿，1:非空）方法二：增加成員變量m_Length（表示隊列長度）4 隊列的實例：離散事件的模擬4.1 逐行打印二項展開式(a + b)n的系數(shù)(楊輝三角形)void YANGVI(int n, vector &coefs) LinkQueue Q; / 整數(shù)隊列 Q.Enter(1); Q.Enter(1); /第1行 for(int i=2; i=n; i+) / 逐行計算 Q.Enter(1); int e1=Q.L

24、eave(); for(int j=1; ji; j+) int e2=Q.Leave(); Q.Enter(e1+e2); e1=e2; Q.Enter(1); for(i=0; !Q.isEmpty(); i+) coefs.push_back( Q.Leave() );4.2 最簡單的排隊問題某加油站只有一臺加油機，平均為每輛車加油需要5分鐘，假定一個小時內(nèi)，有20輛車隨機進入加油站加油，計算每輛車的平均等待時間。/ ServiceTime: 每輛車加油需要的時間/ TotalTime: 總的時間段/ n: 在TotalTime內(nèi),n輛車隨機進入加油站/ 返回平均等待時間float Oi

25、lStation(int n,int TotalTime,float ServiceTime) / 生成模擬數(shù)據(jù) vector ArriveTimes; for(int i=0; in; i+) ArriveTimes.push_back(rand()%TotalTime); sort( ArriveTimes.begin(), ArriveTimes.end() ); / 模擬數(shù)據(jù)全部進隊列 LinkQueue Q; for(i=0; i ArriveTime) WaitTime+=BeginOilTime - ArriveTime; / 需要等待 else BeginOilTime = A

26、rriveTime; / 不需等待 BeginOilTime += ServiceTime; / 加油機為下輛車加油的時刻 return WaitTime/n;思考：加油站有二臺加油機的情形？有k臺加油機的情形？4.3 稍微復(fù)雜一些的排隊問題銀行營業(yè)所有n種業(yè)務(wù)，每類業(yè)務(wù)的服務(wù)時間是Ti，每種業(yè)務(wù)量是Ki/日。問每類業(yè)務(wù)應(yīng)該設(shè)置幾個服務(wù)窗口？4.4 優(yōu)先級隊列(Priority Queue) 優(yōu)先級：數(shù)據(jù)元素的某個值。 進隊列：按次序從隊尾進。 出隊列：取隊列中優(yōu)先權(quán)最高的元素。5 棧、隊列的習(xí)題5.1 進棧出棧的組合問題（初級） 已知操作次序：push(1); pop(); push(2);

27、 push(3); pop(); pop( ); push(4); pop( ); 請寫出出棧序列。 設(shè)進棧次序固定為push(1); push(2); push(3); push(4); 請分析1、2、3、4的24種排列中，哪些序列可以通過出棧操作實現(xiàn)，哪些不能實現(xiàn)？12341243132413421423 X143221342143231423412413 X24313124 X3142 X321432413412 X342141234132 X4213 X4231 X4312 X4321 X5.2 兩個棧組合一個隊列的問題/ 項目路徑：5兩個鏈棧組合一個隊列/a0,ai進隊列a0出隊列a

28、i+1,an-1進隊列a1,ai出隊列ai+1出隊列template class LinkQueue LinkStack S1,S2;public: LinkQueue( ) LinkQueue( ) void Enter(T e); / 進隊列 T Leave( ); / 出隊列;template void LinkQueue:Enter(T e) / 進隊列 S1.Push(e); template T LinkQueue:Leave( ) / 出隊列 T e; if( !S2.isEmpty() ) return( S2.Pop() ); while( !S1.isEmpty() ) S

29、2.Push( S1.Pop() ); return( S2.Pop() );5.3 進棧出棧的組合問題（高級）已知進棧次序為1n，要求窮舉出所有可能的出棧序列。/ 項目路徑：6棧的棧/5.3.1 數(shù)據(jù)結(jié)構(gòu)小棧SeqStack s;特殊的數(shù)據(jù)成員m_Output：儲存出棧序列大棧SeqStackSeqStack S;5.3.2 算法思想：取出大棧中的小棧，進行“進?！?、“出?！弊兓?，再次進棧。當(dāng)某小棧已經(jīng)進棧n次、出棧n次時，其中的數(shù)據(jù)成員m_Output就已儲存了一種出棧序列。5.3.3 算法步驟初始狀態(tài)：s.Push(1); S.Push(s);當(dāng)大棧不空時，循環(huán)執(zhí)行以下語句：大棧出棧，得

30、s=S.Pop(), 記s的進棧次數(shù)為k； 若k=n & s.isEmpty(), 執(zhí)行s.Output()，輸出一種組合序列，轉(zhuǎn)； 若kn，進棧變化：s1=s，s1的下個數(shù)進棧，s1進大棧； 若s不空，出棧變化：s2=s，s2出棧，s2進大棧； 轉(zhuǎn)5.3.4 算法結(jié)果分析i個數(shù)序列個數(shù)Si第1段Ai,1第2段Ai,2第3段Ai,3第4段Ai,4第5段Ai,5第6段Ai,6第7段Ai,7第8段Ai,8第9段Ai,9第10段Ai,102211352214145531542141494161324242281451742913213290482061814304294292971657527719486214301430100157227511035811016796486248623432200210014291544491 3-25