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

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

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

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

4、.......................................33.2.1數(shù)制轉(zhuǎn)換：將十進(jìn)制數(shù)N轉(zhuǎn)換成其他d進(jìn)制數(shù).......................................................33.2.2括號(hào)匹配的檢驗(yàn).......................................................................................

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

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

7、....................................................................................53.4隊(duì)列的基本概念......................................................................................................................63.4.1隊(duì)

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

9、.............73.4.3循環(huán)隊(duì)列.......................................................................................................................73.5隊(duì)列與棧的應(yīng)用...................................................................

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

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

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

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