數(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 判別?？読sEmpty/棧滿isFull 1.1.3 應(yīng)用領(lǐng)域 實例：“進制數(shù)轉(zhuǎn)換”、“表達式求值”、“函數(shù)調(diào)用關(guān)系”、“括號匹配問題”、“漢諾塔問題”、“迷宮問題”、“九連環(huán)”…… 許多問題的求解分為若干步驟，而當前步驟的解答，是建立在后繼步驟的

2、解答基礎(chǔ)上的。=》問題分解的步驟和求解的步驟次序恰好相反。 1.2 順序棧 ///////////////////////////////// // 項目路徑：1順序棧 ///////////////////////////////// 1.2.1 類的定義 const int StackSize=10; template class SeqStack { T m_Data[StackSize]; // 存放棧元素的數(shù)組 int m_Top; // 棧頂指針，表示下一個進棧元素的下標 public: SeqStack( )

3、; 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 SeqStack::SeqStack( ) // 構(gòu)造 { m_Top=0; } template Seq

4、Stack::SeqStack(SeqStack &Q) // 拷貝構(gòu)造 { m_Top = Q.m_Top; for(int i=0; i SeqStack::~SeqStack( ){} // 析構(gòu) 1.2.2.2 狀態(tài)判斷 // 判斷棧是否為空 template bool SeqStack::isEmpty( ) { if(m_Top==0) return true; return

5、false; } // 判斷棧是否為滿 template bool SeqStack::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_Data[m_Top]=e; m_Top++; } template T

6、SeqStack::Pop( ) // 出棧 { if(m_Top==0) throw "下溢"; m_Top--; return m_Data[m_Top]; } template T SeqStack::GetTop() // 取棧頂元素值 { if(m_Top==0) throw "下溢"; return m_Data[m_Top-1]; } 1.3 順序棧的聯(lián)想 缺點：空間浪費 思考：二棧合用同一順序空間？ ///////////////////////////////// /

7、/ 項目路徑：1順序棧(2個) ///////////////////////////////// 1.4 鏈棧 ///////////////////////////////// // 項目路徑：2鏈棧 ///////////////////////////////// 1.4.1 類的定義 template struct LinkNode { T data; LinkNode *next; }; template class LinkStack { LinkNode *m_Top; //

8、 棧頂指針：鏈表頭指針 public: LinkStack( ); ~LinkStack( ); void Push(T x); // 進棧 T Pop( ); // 出棧 T GetTop( ); // 取棧頂元素（不刪除） bool isEmpty( ); // 判斷鏈棧是否為空棧 }; // 棧滿：系統(tǒng)內(nèi)存不夠 1.4.2 基本操作 1.4.2.1 構(gòu)造/析構(gòu) template LinkStack::LinkStack( ) { m_Top = NULL; } temp

9、late 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; newp->next = m_Top; m_T

10、op = 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取余的過程

11、： N n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 void Conversion(int n,int k) { LinkStack S; while( n!=0 ) { S.Push(n%8); // 進棧次序: 個位、十位 ...高位 n=n/8; } while(!S.isEmpty()) cout<

12、 : 0 Equal( "(((a)(b))" ) : 1 Equal( "((a)(b)))" ) : -1 int Equal(char s[]) { LinkStack S; for(int i=0; s[i]; i++) switch(s[i]) { case '(': S.Push(s[i]); break; case ')': if(S.isEmpty()) return(-1); // )多 S.Pop(); break; } if( !S.isEmpty() )

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

14、1位數(shù)運算數(shù) float PostExpression(char s[]) { LinkStack OPND; // 運算數(shù)棧 for(int i=0; s[i]; i++) if(s[i]>='0' && s[i]<='9') OPND.Push(s[i]-'0'); else { float opd1=OPND.Pop(); float opd2=OPND.Pop(); OPND.Push( Eval(opd2,s[i],opd1) ); } return(OPND.GetTop

15、()); /* 棧中唯一值：表達式值 */ } float Eval(float a, char op, float b) { switch(op) { case '+': return(a+b); case '-': return(a-b); case '/': return(a/b); case '*': return(a*b); } } 2.5 中綴表達式轉(zhuǎn)換為后綴表達式 示例數(shù)據(jù)： Mid[]: "2*(3-4)+5#" Post[]："234-*5+" 輔助數(shù)據(jù)結(jié)構(gòu)：一個運算符棧OPTR。

16、 算法：自左向右掃描Mid[]，直至遇到結(jié)束符#。 遇算數(shù)：加入Post[]。 遇算符op：取棧頂算符pre_op 若op>pre_op：op進棧； 若op

17、 c='*' c='(' c='-' c='/' c=')' c=')' C=')' c='+' c='+' c='+' C='#' void MidToPost(char Mid[],char Post[]) { LinkStack OPTR; // 運算符棧 OPTR.Push('#'); int iMid=0,iPost=0; char c=Mid[iMid++]; while(c!='#' || OPTR.GetTop()!='#') { if(c>='0' && c<='9')

18、 { Post[iPost++]=c; c=Mid[iMid++]; continue; } char pre_op=OPTR.GetTop(); switch( Precede(pre_op,c) ) // 比較算符優(yōu)先級 { case '<': // pre_op < c OPTR.Push(c); c=Mid[iMid++]; break; case '=': OPTR.Pop(); c=Mid[iMid++]; break; case '>': // pre_o

19、p > c OPTR.Pop(); Post[iPost++]=pre_op; } } Post[iPost]=0; } // 算符優(yōu)先級比較的代碼 分析：先乘除，后加減；從左到右；先括號內(nèi)，再括號外。 后算符 前算符 ＋ － × ／ ( ) # ＋ > > < < < > > － > > < < < > > × > > > > < > > ／ > > > > < > > ( < < < < < = ) > > > > >

20、> # < < < < < = char priority[7][7]= // + - * / ( ) # {{'>', '>', '<', '<', '<', '>', '>'}, // + {'>', '>', '<', '<', '<', '>', '>'}, // - {'>', '>', '>', '>', '<', '>', '>'}, // * {'>', '>', '>', '>', '<', '>', '>'}, // / {'<', '<', '<', '<', '

21、<', '=', '0'}, // ( {'>', '>', '>', '>', '0', '>', '>'}, // ) {'<', '<', '<', '<', '<', '0', '='} // # }; int OpID(char op) { switch (op) { case '+' : return(0); case '-' : return(1); case '*' : return(2); case '/' : return(3); case '(' : return(4);

22、 case ')' : return(5); case '#' : return(6); } } char Precede(char op1,char op2) { return(priority[OpID(op1)][OpID(op2)]); } 2.6 中綴表達式求值的算法 示例數(shù)據(jù)： s[]: 1+2*(3+4*(5+6))# 與2.5算法的相似處： 當前運算是否立即執(zhí)行？必須先和“上一個運算符”比較優(yōu)先級。 輔助數(shù)據(jù)結(jié)構(gòu)：運算符棧OPTR，運算數(shù)棧OPND 算法：自左向右掃描s[]，直至遇到結(jié)束符#。 遇算數(shù)

23、：OPND.Push(c-'0'); 遇算符op：取棧頂算符pre_op 若op>pre_op：OPTR.Push(c); 若op

24、kStack OPND; // 運算數(shù)棧 LinkStack OPTR; OPTR.Push('#'); // 運算符棧 int i=0; while(s[i]!='#' || OPTR.GetTop()!='#') { char c=s[i]; if(c>='0' && c<='9') { OPND.Push(c-'0'); i++; continue; } char pre_op=OPTR.GetTop(); switch( Precede(pre_op, c) ) {

25、case '<': // pre_op < c OPTR.Push(c); i++; break; case '=': OPTR.Pop(); i++; break; case '>': // pre_op > c 執(zhí)行pre_op OPTR.Pop(); float opd1=OPND.Pop(); float opd2=OPND.Pop(); OPND.Push( Eval(opd2,pre_op,opd1) );

26、 } } 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ù)、負數(shù) 層次2：表達式語法檢查、報錯誤位置 層次3：多個表達式依次求值（含變量） 層次4：超長運算數(shù)的表達式求值 附錄：九連環(huán)的玩法 void down_1(int n)

27、 { printf("%2ddown,",n); } //下第n個環(huán) void down_12() { 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;

28、} 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) { 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)

29、　　只能在一端(隊尾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 類的定義 template

30、ass T> 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 GetFro

31、nt( ); // 取隊列的隊頭元素 bool isEmpty( ); // 判斷隊列是否為空 }; 3.2.2 基本操作 3.2.2.1 構(gòu)造/析構(gòu) template LinkQueue::LinkQueue() { m_Front = m_Rear = NULL; } template LinkQueue::~LinkQueue( ) { /* 銷毀隊列 */ } 3.2.2.2 進/出隊列 // 進隊列 template void LinkQueue<

32、T>::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_Front==NULL) throw "下溢"; LinkNode *p=m_Front;

33、 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)隊列

34、///////////////////////////////// 3.2.1 類的定義 const int QueueSize=6; // 隊列存儲空間的長度 template class CirQueue { T m_Data[QueueSize]; // 存放隊列元素的數(shù)組 int m_Front; // 隊頭指針 int m_Rear; // 隊尾指針 public: CirQueue( ); ~CirQueue( ); void Enter(T e); //

35、 進隊列 T Leave( ); // 出隊列 T GetFront( ); // 取隊頭元素（不刪除） bool isEmpty( ); // 判斷隊列是否為空 bool isFull( ); // 判斷隊列是否為滿 }; 3.2.2 隊頭/尾指針的取值討論=》循環(huán)隊列 以往的常識：進隊列m_Rear++； 出隊列m_Front++ 常識中隱藏了陷阱：假溢出！ 循環(huán)隊列： 進隊列m_Rear =(m_Rear +1)% QueueSize； 出隊列m_Front=(

36、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 CirQueu

37、e::~CirQueue( ){ } 3.2.3.2 進/出隊列 // 進隊列 template void CirQueue::Enter(T e) { if((m_Rear+1) % QueueSize==m_Front) throw "上溢"; m_Data[m_Rear] = e; m_Rear = (m_Rear+1) % QueueSize; } // 出隊列 template T CirQueue::Leave() { if(m_Rear==m

38、_Front) throw "下溢"; T e = m_Data[m_Front]; m_Front = (m_Front+1) % QueueSize; return e; } // 隊列長度 template int CirQueue::Length() { return (m_Rear-m_Front+QueueSize)% QueueSize; } 3.2.4 循環(huán)隊列的其他設(shè)計方案 方法一：增加成員變量m_Flag （0:非滿，1:非空） 方法二：增加成員變量m_Length（表示隊列長度） 4 隊列的

39、實例：離散事件的模擬 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.Leave(); for(int j=1; j

40、1+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

41、 OilStation(int n,int TotalTime,float ServiceTime) { // 生成模擬數(shù)據(jù) vector ArriveTimes; for(int i=0; i Q; for(i=0; i

42、riveTimes[i]); // 出隊列，仿佛享受加油站的服務(wù) float BeginOilTime=0, WaitTime=0; while( !Q.isEmpty() ) { float ArriveTime=Q.Leave(); if(BeginOilTime > ArriveTime) WaitTime+=BeginOilTime - ArriveTime; // 需要等待 else BeginOilTime = ArriveTime; // 不需等待 BeginOil

43、Time += 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 進棧出棧的組合問題（初級） ①已知操作次序：

44、push(1); pop(); push(2); 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)？ 1234 1243 1324 1342 1423 X 1432 2134 2143 2314 2341 2413 X 2431 3124 X 3142 X 3214 3241 3412 X 3421 4123 41

45、32 X 4213 X 4231 X 4312 X 4321 X 5.2 兩個棧組合一個隊列的問題 ///////////////////////////////// // 項目路徑：5兩個鏈棧組合一個隊列 ///////////////////////////////// a0,…ai進隊列 a0出隊列 ai+1,…an-1進隊列 a1,…ai出隊列 ai+1出隊列 template class LinkQueue { LinkStack S1,S2; public

46、: 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() )

47、 return( S2.Pop() ); while( !S1.isEmpty() ) S2.Push( S1.Pop() ); return( S2.Pop() ); } 5.3 進棧出棧的組合問題（高級） 已知進棧次序為1……n，要求窮舉出所有可能的出棧序列。 ///////////////////////////////// // 項目路徑：6棧的棧 ///////////////////////////////// 5.3.1 數(shù)據(jù)結(jié)構(gòu) 小棧 SeqStack s; 特殊的數(shù)據(jù)成員m_Output：儲存出棧序列 大棧 S

48、eqStack > S; 5.3.2 算法思想： 取出大棧中的小棧，進行“進?！薄ⅰ俺鰲！弊兓俅芜M棧。當某小棧已經(jīng)進棧n次、出棧n次時，其中的數(shù)據(jù)成員m_Output就已儲存了一種出棧序列。 5.3.3 算法步驟 ①初始狀態(tài)：s.Push(1); S.Push(s); ②當大棧不空時，循環(huán)執(zhí)行以下語句： ③大棧出棧，得s=S.Pop(), 記s的進棧次數(shù)為k； ④若k==n && s.isEmpty(), 執(zhí)行s.Output()，輸出一種組合序列，轉(zhuǎn)②； ⑤若k

49、若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,10 2 2 1 1 3 5 2 2 1 　 　 　 　 　 　 　 4 14 5 5 3 1 　 　 　 　 　 　 5 42 14 14 9 4 1 　 　 　 　 　 6 132 42 42 28 14 5 1 　 　 　 　 7 429 132 132 90 48 20 6 1 　 　 　 8 1430 429 429 297 165 75 27 7 1 　 　 9 4862 1430 1430 1001 572 275 110 35 8 1 　 10 16796 4862 4862 3432 2002 1001 429 154 44 9 1 3-25