《數(shù)據(jù)結(jié)構(gòu)、代碼》第3章 棧和隊列ppt課件

1、第3章 棧和隊列張成文張成文北京郵電大學(xué)計算機學(xué)院北京郵電大學(xué)計算機學(xué)院概述兩種特殊的線性表。邏輯構(gòu)造和線性表一樣。比起線性表其運算受限制，故又稱它們?yōu)檫\算受限的線性表。棧和隊列運用在各種程序設(shè)計中尤其棧的運用更廣1. 棧1.1 棧的定義1.2 順序棧1.3 鏈棧1.1 棧的定義 棧Stack是限制僅在表的一端進展插入 和刪除運算的線性表。(1)通常稱插入、刪除的這一端為棧頂Top，另一端稱為棧底Bottom。(2)當表中沒有元素時稱為空棧。(3)棧的插入操作被籠統(tǒng)地稱為進?；蛉霔＃瑒h除操作稱為出?；蛲藯?。 每次進棧的元素都被放在原棧頂元素之上而成為每次進棧的元素都被放在原棧頂元素之上而成為新

2、的棧頂，而每次出棧的總是當前棧中新的棧頂，而每次出棧的總是當前棧中“最新的元最新的元素，即最后進棧的元素。因此，棧又稱為后進先出的素，即最后進棧的元素。因此，棧又稱為后進先出的線性表。簡稱為線性表。簡稱為LIFOLIFO表。表。棧的表示圖a1a2an棧頂表尾棧底bottomtop入棧入棧pushpush出棧出棧pop 棧在計算機中主要有兩種根本的存儲棧在計算機中主要有兩種根本的存儲構(gòu)造：順序存儲構(gòu)造和鏈式存儲構(gòu)造。構(gòu)造：順序存儲構(gòu)造和鏈式存儲構(gòu)造。 順序存儲的棧為順序棧順序存儲的棧為順序棧 鏈式存儲的棧為鏈棧鏈式存儲的棧為鏈棧棧的存儲方式1.2 順序棧 棧的順序存儲構(gòu)造簡稱為順序棧,它是運算受

3、限的順序表。順序棧利用一組地址延續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。 順序棧的類型定義#define TRUE 1#define FALSE 0#define Stack_Size 50 typedef struct StackElementType elemStack_Size; /* 一維數(shù)組*/ int top; /*用來存放棧頂元素的下標*/SeqStack; top空棧toptoptoptoptopa 進棧進棧b 進棧進棧aababcdee 進棧進棧abcdef 進棧溢出進棧溢出abdee 退棧退棧ctopc 退棧退棧b 退棧退棧abaa 退棧退?？諚？諚opabdd 退棧

4、退棧ctopabctoptop 留意順序棧中元素用向量存放棧底位置是固定不變的，可設(shè)置在向量兩端的恣意一個端點棧頂位置是隨著進棧和退棧操作而變化的，用一個整型量top通常稱top為棧頂指針來指示當前棧頂位置順序棧的根本運算1 置?？粘跏蓟? 判棧空3 判棧滿4 進棧操作5 退棧操作6 取棧頂元素 1置棧空初始化 void InitStackSeqStack *S /將順序棧置空 S-top=-1; (2) 判?？?int StackEmptySeqStack *S /*判棧S為空棧時前往值為真，反之為假*/ return S-top=-1; 3判棧滿 int StackFullSeqStack

5、 *S/*判棧S為滿時前往真，否那么前往假*/ return S-top=StackSize-1; 4進棧進棧時，需求將S-top加1 留意： S-top=StackSize-1表示棧滿上溢景象-當棧滿時，再做進棧運算產(chǎn)生空間溢出的景象。 上溢是一種出錯形狀，應(yīng)設(shè)法防止。 void PushSeqStack *S，DataType x if (StackFull(S) Error(“Stack overflow); /上溢，退出運轉(zhuǎn) S-data+S-top=x;/棧頂指針加1后將x入棧5退棧退棧時，需將S-top減1 留意： S-topdataS-top-;/棧頂元素前往后將棧頂指針減1 6

6、取棧頂元素 DataType StackTopS if(StackEmpty(S) Error(Stack is empty); return S-dataS-top; 1.4 鏈棧 鏈棧是采用鏈表作為存儲構(gòu)造實現(xiàn)的棧，是線性鏈棧是采用鏈表作為存儲構(gòu)造實現(xiàn)的棧，是線性鏈表的特例。由于棧的插入和刪除操作僅限制在表頭鏈表的特例。由于棧的插入和刪除操作僅限制在表頭位置進展，所以鏈表的表頭指針就作為棧頂指針。位置進展，所以鏈表的表頭指針就作為棧頂指針。 top top為棧頂指針，一直指向當前棧頂元素結(jié)點。為棧頂指針，一直指向當前棧頂元素結(jié)點。假設(shè)假設(shè)top=NULLtop=NULL，那么代表空棧。，那

7、么代表空棧。留意：鏈棧在運用終了時，應(yīng)該釋放其空間。留意：鏈棧在運用終了時，應(yīng)該釋放其空間。留意留意: 鏈棧中指針的方向是從棧頂指向棧底方向鏈棧中指針的方向是從棧頂指向棧底方向棧頂指針棧頂指針topa1 an-1 an typedef struct stacknode DataType data struct stacknode *next StackNode; StackNode *head=NULL; typedef struct StackNode *top; /棧頂指針 LinkStack;鏈棧的根本運算(1) 置?？?2) 判?？?3) 進棧(4) 退棧(5) 取棧頂元素1 置?？?

8、void InitStack(LinkStack *S) S-top=NULL; (2) 判?？?int StackEmpty(LinkStack *S) return S-top=NULL; 3 進棧void Push(LinkStack *S,DataType x)/將元素x插入鏈棧頭部 StackNode *p= (StackNode *)malloc(sizeof(StackNode); if(p=NULL) printf(“內(nèi)存空間不夠分配); exit(0);/return /強壯(Robust) p-data=x; p-next=S-top;/將新結(jié)點*p插入鏈棧頭部 S-top

9、=p; 4 退棧 DataType Pop(LinkStack *S) DataType x; StackNode *p=S-top;/保管棧頂指針 if(StackEmpty(S) Error(Stack underflow.); /下溢 x=p-data; /保管棧頂結(jié)點數(shù)據(jù) S-top=p-next; /將棧頂結(jié)點從鏈上摘下 free(p); return x; 將將x x入棧，修正棧頂入棧，修正棧頂指針指針:top=p:top=panan出棧，修正棧頂指出棧，修正棧頂指針針:top=top-next:top=top-next鏈棧的入棧操作和出棧操作5 取棧頂元素 DataType St

10、ackTop(LinkStack *S) if(StackEmpty(S) Error(Stack is empty.) return S-top-data; 留意 鏈棧中的結(jié)點是動態(tài)分配的，所以可以不思索上溢，無須定義StackFull運算。 2. 隊列2.1 隊列的定義2.2 順序隊列2.3 鏈隊列 隊列是一種特殊的線性表，限定插入和刪除操作分別隊列是一種特殊的線性表，限定插入和刪除操作分別在表的兩端進展。在表的兩端進展。 a1 a2 ai an 隊頭 f隊尾 r出隊出隊入隊入隊2.1 隊列的定義和根本運算隊列的性質(zhì)1允許刪除的一端稱為隊頭Front。2允許插入的一端稱為隊尾Rear。3當

11、隊列中沒有元素時稱為空隊列。4隊列亦稱作先進先出First In First Out的線性表，簡稱為FIFO表隊列的進隊和出隊 front rear空隊列front rearA進隊進隊Afront rearB進隊進隊A Bfront rearC, D進隊進隊A B C Dfront rearA退隊退隊B C Dfront rearB退隊退隊C Dfront rearE,F,G進隊進隊C D E F GC D E F Gfront rearH進隊進隊,溢出溢出隊列的進隊和出隊原那么n 進隊時隊尾指針先進一進隊時隊尾指針先進一 rear = rear + 1，n 再將新元素按再將新元素按 rear

12、 指示位置參與。指示位置參與。n 出隊時隊頭指針先進一出隊時隊頭指針先進一 front = front + 1，n 再將下標為再將下標為 front 的元素取出。的元素取出。n 隊滿時再進隊將溢出出錯；隊滿時再進隊將溢出出錯；n 隊空時再出隊將隊空處置。隊空時再出隊將隊空處置。n 處理方法之一：將隊列元素存放數(shù)組首尾處理方法之一：將隊列元素存放數(shù)組首尾n 相接，構(gòu)成循環(huán)相接，構(gòu)成循環(huán)(環(huán)形環(huán)形)隊列。隊列。 隊列在計算機中主要有兩種根本的存隊列在計算機中主要有兩種根本的存儲構(gòu)造：順序存儲構(gòu)造和鏈式存儲構(gòu)造。儲構(gòu)造：順序存儲構(gòu)造和鏈式存儲構(gòu)造。順序存儲的隊列為順序隊列順序存儲的隊列為順序隊列鏈式

13、存儲的隊列為鏈隊列鏈式存儲的隊列為鏈隊列隊列的存儲方式隊列的根本運算(1)初始化隊列(2)判隊空(3)判隊滿(4)入隊(5)出隊(6)取隊首元素2.2 順序隊列2.2.1 順序隊列的定義2.2.2 順序隊列的根本運算2.2.3 循環(huán)隊列2.2.1 順序隊列的定義 隊列的順序存儲構(gòu)造稱為順序隊列，順序隊列實踐上是運算受限的順序表 frontreara b c da b c d d e f d e f rear front rear 順序隊列的表示和順序表一樣，順序隊列用一個向量空間來存放當前隊列中的元素。由于隊列的隊頭和隊尾的位置是變化的，設(shè)置兩個“指針front和rear分別指示隊頭元素和隊尾

14、元素在向量空間中的位置，它們的初值在隊列初始化時均應(yīng)置為0。2.2.2 順序隊列的根本運算入隊時：將新元素插入rear所指的位置，然后將rear加1。出隊時：刪去front所指的元素，然后將front加1并前往被刪元素。 留意：當頭尾指針相等時，隊列為空。在非空隊列里，隊頭指針一直指向隊頭元素，尾指針一直指向隊尾元素的下一位置。 當Q-front= Q-rear 時,隊列空。 當Q-rear+1MaxSize 時,隊列滿(即上溢出),但此時頭指針指示的元素之前能夠還有空單元,此景象稱為假溢出;假設(shè)把這樣的順序構(gòu)造想象為一個循環(huán)表, 插入時就可以利用這些空單元, 這樣就構(gòu)成循環(huán)隊列。假上溢2.2

15、.3 循環(huán)隊列為充分利用向量空間，抑制“假上溢景象的方法：將向量空間想象為一個首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量。入隊操作時的尾指針運算入隊操作時的尾指針運算: rear=(rear+1)%Maxsize出隊操作時的頭指針運算出隊操作時的頭指針運算: front=(front+1)%Maxaize問題：在循環(huán)隊列中，由于隊空時有問題：在循環(huán)隊列中，由于隊空時有front=rear；隊滿時也有；隊滿時也有front=rear；因；因此我們無法經(jīng)過此我們無法經(jīng)過front=rear來判別隊列是來判別隊列是“空還是空還是“滿。滿。循環(huán)隊列表示圖循環(huán)隊列的幾種形狀循環(huán)隊列的幾種形狀frontrea

16、r循環(huán)隊列隊滿和隊空的描畫方法循環(huán)隊列隊滿和隊空的描畫方法frontrear隊空隊空:隊滿隊滿:frontfrontrearrear rear=front?rear=front循環(huán)隊列邊境條件處置如何判別是“空還是“滿。 處理這個問題的方法至少有三種： 另設(shè)一布爾變量以區(qū)別隊列的空和滿； 少用一個元素的空間。商定入隊前，測試尾指針在循環(huán)意義下加1后能否等于頭指針，假設(shè)相等那么以為隊滿留意：rear所指的單元一直為空；運用一個計數(shù)器記錄隊列中元素的總數(shù)即隊列長度。順序循環(huán)隊列的類型定義#define QueueSize 100 /應(yīng)根據(jù)詳細情況定義該值typedef char DataType;

17、 /DataType的類型依賴于詳細的運用typedef struct int front; /頭指針，隊非空時指向隊頭元素 int rear; /尾指針，隊非空時指向隊尾元素的下一位置 int count; /計數(shù)器，記錄隊中元素總數(shù) DataType dataQueueSize CirQueue;順序循環(huán)隊列的根本運算1.置隊空2.判隊空3.判隊滿4.入隊5.出隊6.取隊頭元素 置隊空置隊空 void InitQueue(CirQueue *Q) Q-front=Q-rear=0; Q-count=0; /計數(shù)器置0 判隊空判隊空 int QueueEmpty(CirQueue *Q) /

18、隊列無元素為空，屬第三種方法 return Q-count=0; int QueueEmpty(CirQueue *Q) /屬第二種方法 return Q-rear=Q-front; 判隊滿判隊滿int QueueFull(CirQueue *Q) return Q-count=QueueSize; /隊中元素個數(shù)等于QueueSize時隊滿，屬第三種方法int QueueFull(CirQueue *Q) return (Q-rear+1)%QueueSize=Q-front ; /隊中元素個數(shù)等于QueueSize時隊滿，屬第二種方法 入隊入隊void EnQueue(CirQueue *

19、Q,DataType x) if(QueueFull(Q) Error(Queue overflow); /隊滿上溢 Q-count +; /隊列元素個數(shù)加1 Q-dataQ-rear=x; /新元素插入隊尾 Q-rear=(Q-rear+1)%QueueSize; /循環(huán)意義下將尾指針加1 出隊出隊DataType DeQueue(CirQueue *Q) DataType temp; if(QueueEmpty(Q) Error(Queue underflow); /隊空下溢 temp=Q-dataQ-front; Q-count-; /隊列元素個數(shù)減1 Q-front=(Q-front+

20、1)%QueueSize; /*循環(huán)意義下的頭指針加1*/ return temp; 取隊頭元素取隊頭元素DataType QueueFront(CirQueue *Q) if(QueueEmpty(Q) Error(Queue if empty.); return Q-dataQ-front; 2.3鏈隊列2.3.1 鏈隊列的定義2.3.2 鏈隊列的根本運算2.3.1 鏈隊列的定義 隊列的鏈式存儲構(gòu)造簡稱為鏈隊列。它是限制僅在表頭刪除和表尾插入的單鏈表。 隊頭在鏈頭，隊尾在鏈尾。隊頭在鏈頭，隊尾在鏈尾。a1anq.frontq.rearq.frontq.rear空隊列空隊列鏈隊列的幾種形狀表

21、示圖此時，front=rear修正rear指針修正頭結(jié)點的指針域鏈隊列為空的特征：鏈隊列為空的特征：front=rear 鏈隊列會滿嗎？鏈隊列會滿嗎？普通不會，由于刪除時有普通不會，由于刪除時有freefree動作，除非內(nèi)存缺乏！動作，除非內(nèi)存缺乏！修正rear指針留意 添加指向鏈表上的最后一個結(jié)點的尾指針，便于在表尾做插入操作 和鏈棧類似，無須思索判隊滿的運算及上溢。在出隊算法中，普通只需修正隊頭指針。但當原隊中只需一個結(jié)點時，該結(jié)點既是隊頭也是隊尾，故刪去此結(jié)點時亦需修正尾指針，且刪去此結(jié)點后隊列變空。以上討論的是無頭結(jié)點鏈隊列的根本運算。和單鏈表類似，為了簡化邊境條件的處置，在隊頭結(jié)點前

22、也可附加一個頭結(jié)點，添加頭結(jié)點的鏈隊列的根本運算定義鏈隊列的存儲構(gòu)造typedef char DataType;typedef struct queuenode DataType data; struct queuenode *next;QueueNode;typedef struct QueueNode * front; QueueNode *rear; LinkQueue;2.3.2 鏈隊列的根本運算1.置空隊2.判隊空3.入隊4.出隊5.取隊頭元素1 置空隊int InitQueue( LinkQueue int InitQueue( LinkQueue * *Q )Q ) / /構(gòu)造一

23、個空隊列構(gòu)造一個空隊列 * *Q Q Q-front = (LQnode Q-front = (LQnode * *)malloc(sizeof(LQnode); )malloc(sizeof(LQnode); if( Q-front = NULL ) if( Q-front = NULL ) return FALSE; / return FALSE; /懇求內(nèi)存失敗前往懇求內(nèi)存失敗前往 Q-rear = Q-front; Q-rear = Q-front; Q-front- next = NULL; Q-front- next = NULL; return TRUE; / return TR

24、UE; /懇求內(nèi)存勝利前往懇求內(nèi)存勝利前往 2 判隊空 int QueueEmpty(LinkQueue *Q)return Q- front- next =NULL&Q-rear-next=NULL;/*實踐上只須判別隊頭指針能否為空即可*/3 入隊void EnQueue(LinkQueue *Q,DataType x)/將元素x插入鏈隊列尾部 QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode); /懇求新結(jié)點 p-data=x; p-next=NULL; if(QueueEmpty(Q) Q-front-next=p; Q-rear=p;

25、 /將x插入空隊列 else /x插入非空隊列的尾 Q-rear-next=p; /*p鏈到原隊尾結(jié)點后 Q-rear=p; /隊尾指針指向新的尾 4 出隊DataType DeQueue (LinkQueue *Q) DataType x; QueueNode *p; if(QueueEmpty(Q) Error(“Queue underflow);/下溢 p=Q-front-next; /指向隊頭結(jié)點 x=p-data; /保管隊頭結(jié)點的數(shù)據(jù) Q-front-next=p-next; /將隊頭結(jié)點從鏈上摘下 if(Q-rear=p)/原隊中只需一個結(jié)點，刪去后隊列變空，此時隊頭指針已為空

26、Q-rear= Q-front; free(p); /釋放被刪隊頭結(jié)點 return x; /前往原隊頭數(shù)據(jù) 5 取隊頭元素 DataType QueueFront(LinkQueue *Q) if(QueueEmpty(Q) Error(Queue if empty.); return Q-front-next-data; 3. 棧的運用3.1 函數(shù)調(diào)用3.2 遞歸、非遞歸 當在一個函數(shù)的運轉(zhuǎn)期間調(diào)用另一個函數(shù)時當在一個函數(shù)的運轉(zhuǎn)期間調(diào)用另一個函數(shù)時, 在運轉(zhuǎn)該被調(diào)用函數(shù)之前在運轉(zhuǎn)該被調(diào)用函數(shù)之前, 需先完成三項義務(wù)：需先完成三項義務(wù)： 保管現(xiàn)場保管現(xiàn)場, 保管本函數(shù)參數(shù)、前往地址等信息保管

27、本函數(shù)參數(shù)、前往地址等信息; 為被調(diào)用函數(shù)的部分變量分配存儲區(qū)傳送參數(shù)為被調(diào)用函數(shù)的部分變量分配存儲區(qū)傳送參數(shù); 將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。3.1 函數(shù)調(diào)用 從被調(diào)用函數(shù)前往調(diào)用函數(shù)之前從被調(diào)用函數(shù)前往調(diào)用函數(shù)之前, 應(yīng)該完成以下應(yīng)該完成以下三項義務(wù)：三項義務(wù)：保管前往的計算結(jié)果保管前往的計算結(jié)果(用函數(shù)名用函數(shù)名,援用參數(shù)援用參數(shù)) ；釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū), 恢復(fù)調(diào)用函數(shù)現(xiàn)場恢復(fù)調(diào)用函數(shù)現(xiàn)場 ;按照被保管的前往地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。按照被保管的前往地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。多個函數(shù)嵌套調(diào)用的規(guī)那么多個函數(shù)嵌套調(diào)用的規(guī)那么此時的內(nèi)存管理

28、實行此時的內(nèi)存管理實行“棧式管理棧式管理后調(diào)用先前往后調(diào)用先前往 ！例如：例如：main( ) void a( ) void b( ) a( ); b( ); /main / a / bmain的數(shù)據(jù)區(qū)函數(shù)a的數(shù)據(jù)區(qū)函數(shù)b的數(shù)據(jù)區(qū) 棧在函數(shù)調(diào)用中的作用過程一過程二過程三過程四斷點三斷點一斷點二斷點一斷點二斷點三stack調(diào)用子程序前往斷點程序執(zhí)行 數(shù)據(jù)構(gòu)造-第3章 棧和隊列703.2 遞歸、非遞歸遞歸的含義遞歸的含義 函數(shù)、過程或者數(shù)據(jù)構(gòu)造的內(nèi)部又直接或者間接函數(shù)、過程或者數(shù)據(jù)構(gòu)造的內(nèi)部又直接或者間接地由本身定義。地由本身定義。適宜于運用遞歸的場所適宜于運用遞歸的場所規(guī)模較大的問題可以化解為規(guī)

29、模較小的問題，且二者處規(guī)模較大的問題可以化解為規(guī)模較小的問題，且二者處置置(或定義或定義)的方式一致；的方式一致；當問題規(guī)模降低到一定程度時是可以直接求解的當問題規(guī)模降低到一定程度時是可以直接求解的(終止條終止條件件) 例例1. 階乘階乘 n!= 1 n=0 n(n-1)! n0數(shù)據(jù)構(gòu)造-第3章 棧和隊列71寫遞歸算法應(yīng)留意的問題寫遞歸算法應(yīng)留意的問題 遞歸算法本身不可以作為獨立的程序運轉(zhuǎn)，需在其它的程序中設(shè)置調(diào)用初值，進展調(diào)用； 遞歸算法應(yīng)有出口(終止條件) 例1. 求n！int Factorial(int n) if (n=0) return(1); return n*Factorial(

30、n-1);/Factorial數(shù)據(jù)構(gòu)造-第3章 棧和隊列72遞歸算法的實現(xiàn)原理遞歸算法的實現(xiàn)原理123s123- 利用棧，棧中每個元素稱為任務(wù)記錄，分成三個部分： 前往地址 實踐參數(shù)表(變參和值參) 部分變量- 發(fā)生調(diào)用時，維護現(xiàn)場，即當前的任務(wù)記錄入棧，然后 轉(zhuǎn)入被調(diào)用的過程- 一個調(diào)用終了時，恢復(fù)現(xiàn)場，即假設(shè)棧不空，那么退棧，從 退出的前往地址處繼續(xù)執(zhí)行下去73遞歸時系統(tǒng)任務(wù)原理例如遞歸時系統(tǒng)任務(wù)原理例如int Factorial( int n) L1: if ( n=0 ) L2: return 1; L3: else return n*Factorial(n-1); L4: /Fact

31、orial void main(void) L0: N=Factorial(3); /main 前往地址 n Factorial NL0 3 / / L3 3 /L3 2 /L3 1 / 1126數(shù)據(jù)構(gòu)造-第3章 棧和隊列74遞歸算法的用途遞歸算法的用途 求解遞歸定義的數(shù)學(xué)函數(shù) 在以遞歸方式定義的數(shù)據(jù)構(gòu)造上的運算/操作 可用遞歸方式描畫的處理過程 遞歸算法的特點 遞歸算法簡單明了，直觀易懂 時間效率低，空間開銷大，算法不易優(yōu)化數(shù)據(jù)構(gòu)造-第3章 棧和隊列75遞歸轉(zhuǎn)換為非遞歸的方法遞歸轉(zhuǎn)換為非遞歸的方法1采用迭代算法采用迭代算法 遞歸遞歸從頂究竟從頂究竟 迭代迭代從底到頂從底到頂 例：求例：求n！ int fact(int n) m=1; for ( i=1; idata); linklist_output(p-next) /linklist_output運用跳轉(zhuǎn)語句：void linklist_output1(