《棧隊列和遞歸》PPT課件.ppt

《《棧隊列和遞歸》PPT課件.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、第三章棧、隊列和遞歸特殊線性表棧隊列串⑴棧的定義⑵操作特性⑶ADT定義⑴隊列定義⑵操作特性⑶ADT定義⑴串的定義⑵基本概念⑶ADT定義順序棧鏈棧循環(huán)隊列鏈隊列順序存儲鏈接存儲邏輯結構存儲結構邏輯結構邏輯結構存儲結構存儲結構比較模式匹配比較比較⑴基本操作的實現(xiàn)⑵時間復雜度⑴基本操作的實現(xiàn)⑵時間復雜度3.1棧（Stack）3.2隊列（Queue）１.邏輯結構２.存儲結構與實現(xiàn)３.應用實例１.邏輯結構２.存儲結構與實現(xiàn)３.應用實例３.1棧1、棧的邏輯結構空棧：不含任何數(shù)據(jù)元素的棧。（a1,a2,……,an）棧：限定僅在一端進行插入和刪除操作的線性表。棧頂棧底允許

2、插入和刪除的一端稱為棧頂，另一端稱為棧底。數(shù)據(jù)元素之間的邏輯關系：一對一。注：棧的運算規(guī)則只能在棧頂運算，且訪問結點時依照后進先出（LIFO）或先進后出（FILO）的原則。入棧：插入元素到棧頂（即表尾）的操作。出棧：從棧頂（即表尾）刪除最后一個元素的操作。問：棧與一般線性表有什么不同？一般線性表（堆）棧邏輯結構：一對一邏輯結構：一對一存儲結構：順序表、鏈表存儲結構：順序棧、鏈棧運算規(guī)則：隨機存取運算規(guī)則：后進先出(LIFO)入棧操作演示出棧操作演示a1a2a3入棧棧底棧頂插入：入棧、進棧、壓棧棧頂棧頂入棧的操作示圖：棧頂a1a2a3棧底棧頂刪除：出棧、彈棧

3、棧頂棧頂出棧的操作示圖：棧頂棧的操作特性：后進先出出棧思考題１：一個棧的輸入序列為123，若在入棧的過程中允許出棧，且每個元素只允許進一次棧，則可能得到的出棧序列有哪些？答：可以通過窮舉所有可能性來求解：①1入1出，2入2出，3入3出，即123；②1入1出，2、3入3、2出，即132；③1、2入，2出，3入3出，即231；④1、2入，2、1出，3入3出，即213；⑤1、2、3入，3、2、1出，即321；合計有5種可能性。思考題２：設依次進入一個棧的元素序列為c，a，b，d，則可得到出棧的元素序列是：Ａ）a，b，c，dＢ）c，d，a，bＣ）b，c，d，aＤ）

4、a，c，d，bA、D可以（B、C不行）。討論：有無通用的判別原則？有。若輸入序列i，j，k，則不存在輸出序例k、i、j;答：2、棧的存儲結構順序棧、鏈式棧（１）順序棧——棧的順序存儲結構(重點)如何改造數(shù)組實現(xiàn)棧的順序存儲？012345678a1確定用數(shù)組的哪一端表示棧底。附設指針top指示棧頂元素在數(shù)組中的位置。topS進棧核心語句：top++;S[top]=a1;?？眨簍op==-1012345678topa1topa2top進棧的操作步驟如何？012345678a1a2棧滿：top==MAX_SIZE-1棧滿的如何判斷？topa3a4a5a6a7a8

5、a9動態(tài)棧類的定義：template//定義模板類DSeqStackclassDSeqStack{public:DSeqStack(intsize);//構造函數(shù)，棧的初始化~DSeqStack(){delete[]S;}//析構函數(shù)voidPush(consttype&item);//將元素item入棧typePop();//將棧頂元素彈出typeGetTop();//取棧頂元素（并不刪除）intEmpty(){returntop==-1;}//判斷棧是否為空intfull()const{returntop==MaxSize-1;}

6、//為滿則返回1，否則返回0voidclear(){top=-1;}//清空棧private:type*S;//存放棧元素的數(shù)組起始地址inttop;//棧頂指針，指示棧頂元素在數(shù)組中的下標intMaxSize;//棧最大可容納元素個數(shù)};順序棧的構造函數(shù)算法實現(xiàn)templateDSeqStack::DSeqStack(intsize):top(-1),MaxSize(size){//建立一個最大尺寸為size的空棧S=newtype[MaxSize];//創(chuàng)建存儲棧的數(shù)組if(S==NULL)//分配不成功{cerr<<

7、"動態(tài)存儲失敗！"<DSeqStack::DSeqStack(intsize);算法實現(xiàn)：順序棧的入棧操作算法實現(xiàn)templatevoidDSeqStack::Push(consttype&item){if(top==MaxSize-1)throw"棧滿！";top++;//棧未滿，則入棧S[top]=item;}操作接口：templatevoidDSeqStack::Push(

8、consttype&item)算法實現(xiàn)：時間復雜度？O(1)出棧核