程序設(shè)計教案 程序設(shè)計——數(shù)據(jù)結(jié)構(gòu)

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

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

3、.........................................................................................................................33.2棧的應(yīng)用...........................................................................................

4、.......................................33.2.1數(shù)制轉(zhuǎn)換：將十進制數(shù)N轉(zhuǎ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隊列與棧的應(yīng)用...................................................................

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

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

12、個位置；刪除操作（出棧）：刪除棧頂元素；取元素操作：取棧頂元素的值。各操作的操作位置與棧頂元素的位置或其下一個位置相關(guān)，希望在O(1)時間內(nèi)能獲取操作位置，故可設(shè)置專門的棧頂指針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)制約。約定不同，相應(yīng)的判定和處理也不一樣。如假設(shè)top就指向棧頂元素，此時4)5)6)如何？2、取棧頂元素GetTop_Sq1)算法設(shè)計參數(shù)：順序棧S、取得的棧頂元素e=(S.top1)returnOK3、入棧操作Push_Sq1)算法設(shè)計參數(shù)：順序棧算法算法2StatusPush_Sq(SqStack&SElemTypee)判斷棧是否為滿if(S.top–S.base=S.stacks