程序設計教案 程序設計——數(shù)據(jù)結構

1、程序程序設計設計——數(shù)據(jù)數(shù)據(jù)結構第1頁棧和隊列基本概念及應用文檔編號完成人張昱完成時間修改時間第1頁目錄3.1棧的基本概念..........................................................................................................................13.1.1棧的抽象數(shù)據(jù)類型定義.....................

2、..........................................................................13.1.2順序棧...........................................................................................................................23.1.3鏈棧......

3、.........................................................................................................................33.2棧的應用...........................................................................................

4、.......................................33.2.1數(shù)制轉換：將十進制數(shù)N轉換成其他d進制數(shù).......................................................33.2.2括號匹配的檢驗.......................................................................................

5、....................43.2.3行輸入處理程序...........................................................................................................43.2.4迷宮求解......................................................................

6、.................................................43.2.5表達式求值...................................................................................................................43.3棧與遞歸的實現(xiàn)..................................

7、....................................................................................53.4隊列的基本概念......................................................................................................................63.4.1隊

8、列的抽象數(shù)據(jù)類型定義...........................................................................................63.4.2鏈隊列..............................................................................................................

9、.............73.4.3循環(huán)隊列.......................................................................................................................73.5隊列與棧的應用...................................................................

10、...................................................83.5.1離散事件模擬...............................................................................................................8程序程序設計設計——數(shù)據(jù)數(shù)據(jù)結構第3頁棧和隊列基本概念及應用文檔編號完成人張昱完成時間修改

11、時間第3頁1、增量式順序棧的定義#defineSTACK_INIT_SIZE100存儲空間的初始分配量#defineSTACKINCREMENT10存儲空間的分配增量typedefstructElemTypebase棧底指針ElemTypetop棧頂指針(棧頂元素的下一個位置)intstacksize當前分配的存儲容量SqStack1）和順序表一樣采用增量式的空間分配；2）操作和棧頂相關：插入操作（入棧）：將待插元素插入到棧頂元素的下一

12、個位置；刪除操作（出棧）：刪除棧頂元素；取元素操作：取棧頂元素的值。各操作的操作位置與棧頂元素的位置或其下一個位置相關，希望在O(1)時間內能獲取操作位置，故可設置專門的棧頂指針top。3）約定：約定：top指向棧頂元素的下一個位置（便于表示空棧）。4）棧頂?shù)某跏蓟篠.top=S.base(在上述3)約定下的空棧形式)，5）?？眨篠.base==S.top，棧滿：S.topS.base=S.stacksize6）入棧：S.top=e，

13、出棧：e=S.top注意注意：4)5)6)步受3)制約。約定不同，相應的判定和處理也不一樣。如假設top就指向棧頂元素，此時4)5)6)如何？2、取棧頂元素GetTop_Sq1)算法設計參數(shù)：順序棧S、取得的棧頂元素e=(S.top1)returnOK3、入棧操作Push_Sq1)算法設計參數(shù)：順序棧算法算法2StatusPush_Sq(SqStack&SElemTypee)判斷棧是否為滿if(S.top–S.base=S.stacks