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

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

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

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

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

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

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

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

8、void InitStack(LinkStack *S) S-top=NULL; (2) 判?？?int StackEmpty(LinkStack *S) return S-top=NULL; 3 進(jìn)棧void Push(LinkStack *S,DataType x)/將元素x插入鏈棧頭部 StackNode *p= (StackNode *)malloc(sizeof(StackNode); if(p=NULL) printf(“內(nèi)存空間不夠分配); exit(0);/return /強(qiáng)壯(Robust) p-data=x; p-next=S-top;/將新結(jié)點(diǎn)*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é)點(diǎn)數(shù)據(jù) S-top=p-next; /將棧頂結(jié)點(diǎn)從鏈上摘下 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é)點(diǎn)是動(dòng)態(tài)分配的，所以可以不思索上溢，無須定義StackFull運(yùn)算。 2. 隊(duì)列2.1 隊(duì)列的定義2.2 順序隊(duì)列2.3 鏈隊(duì)列 隊(duì)列是一種特殊的線性表，限定插入和刪除操作分別隊(duì)列是一種特殊的線性表，限定插入和刪除操作分別在表的兩端進(jìn)展。在表的兩端進(jìn)展。 a1 a2 ai an 隊(duì)頭 f隊(duì)尾 r出隊(duì)出隊(duì)入隊(duì)入隊(duì)2.1 隊(duì)列的定義和根本運(yùn)算隊(duì)列的性質(zhì)1允許刪除的一端稱為隊(duì)頭Front。2允許插入的一端稱為隊(duì)尾Rear。3當(dāng)

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

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

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

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

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

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

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

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

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

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

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

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

23、個(gè)空隊(duì)列構(gòu)造一個(gè)空隊(duì)列 * *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 判隊(duì)空 int QueueEmpty(LinkQueue *Q)return Q- front- next =NULL&Q-rear-next=NULL;/*實(shí)踐上只須判別隊(duì)頭指針能否為空即可*/3 入隊(duì)void EnQueue(LinkQueue *Q,DataType x)/將元素x插入鏈隊(duì)列尾部 QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode); /懇求新結(jié)點(diǎn) p-data=x; p-next=NULL; if(QueueEmpty(Q) Q-front-next=p; Q-rear=p;

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

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

27、本函數(shù)參數(shù)、前往地址等信息; 為被調(diào)用函數(shù)的部分變量分配存儲(chǔ)區(qū)傳送參數(shù)為被調(diào)用函數(shù)的部分變量分配存儲(chǔ)區(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)該完成以下三項(xiàng)義務(wù)：三項(xiàng)義務(wù)：保管前往的計(jì)算結(jié)果保管前往的計(jì)算結(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ù)。多個(gè)函數(shù)嵌套調(diào)用的規(guī)那么多個(gè)函數(shù)嵌套調(diào)用的規(guī)那么此時(shí)的內(nèi)存管理

28、實(shí)行此時(shí)的內(nèi)存管理實(shí)行“棧式管理?xiàng)Ｊ焦芾砗笳{(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)用中的作用過程一過程二過程三過程四斷點(diǎn)三斷點(diǎn)一斷點(diǎn)二斷點(diǎn)一斷點(diǎn)二斷點(diǎn)三stack調(diào)用子程序前往斷點(diǎn)程序執(zhí)行 數(shù)據(jù)構(gòu)造-第3章 棧和隊(duì)列703.2 遞歸、非遞歸遞歸的含義遞歸的含義 函數(shù)、過程或者數(shù)據(jù)構(gòu)造的內(nèi)部又直接或者間接函數(shù)、過程或者數(shù)據(jù)構(gòu)造的內(nèi)部又直接或者間接地由本身定義。地由本身定義。適宜于運(yùn)用遞歸的場所適宜于運(yùn)用遞歸的場所規(guī)模較大的問題可以化解為規(guī)

29、模較小的問題，且二者處規(guī)模較大的問題可以化解為規(guī)模較小的問題，且二者處置置(或定義或定義)的方式一致；的方式一致；當(dāng)問題規(guī)模降低到一定程度時(shí)是可以直接求解的當(dāng)問題規(guī)模降低到一定程度時(shí)是可以直接求解的(終止條終止條件件) 例例1. 階乘階乘 n!= 1 n=0 n(n-1)! n0數(shù)據(jù)構(gòu)造-第3章 棧和隊(duì)列71寫遞歸算法應(yīng)留意的問題寫遞歸算法應(yīng)留意的問題 遞歸算法本身不可以作為獨(dú)立的程序運(yùn)轉(zhuǎn)，需在其它的程序中設(shè)置調(diào)用初值，進(jìn)展調(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章 棧和隊(duì)列72遞歸算法的實(shí)現(xiàn)原理遞歸算法的實(shí)現(xiàn)原理123s123- 利用棧，棧中每個(gè)元素稱為任務(wù)記錄，分成三個(gè)部分： 前往地址 實(shí)踐參數(shù)表(變參和值參) 部分變量- 發(fā)生調(diào)用時(shí)，維護(hù)現(xiàn)場，即當(dāng)前的任務(wù)記錄入棧，然后 轉(zhuǎn)入被調(diào)用的過程- 一個(gè)調(diào)用終了時(shí)，恢復(fù)現(xiàn)場，即假設(shè)棧不空，那么退棧，從 退出的前往地址處繼續(xù)執(zhí)行下去73遞歸時(shí)系統(tǒng)任務(wù)原理例如遞歸時(shí)系統(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章 棧和隊(duì)列74遞歸算法的用途遞歸算法的用途 求解遞歸定義的數(shù)學(xué)函數(shù) 在以遞歸方式定義的數(shù)據(jù)構(gòu)造上的運(yùn)算/操作 可用遞歸方式描畫的處理過程 遞歸算法的特點(diǎn) 遞歸算法簡單明了，直觀易懂 時(shí)間效率低，空間開銷大，算法不易優(yōu)化數(shù)據(jù)構(gòu)造-第3章 棧和隊(duì)列75遞歸轉(zhuǎn)換為非遞歸的方法遞歸轉(zhuǎn)換為非遞歸的方法1采用迭代算法采用迭代算法 遞歸遞歸從頂究竟從頂究竟 迭代迭代從底到頂從底到頂 例：求例：求n！ int fact(int n) m=1; for ( i=1; idata); linklist_output(p-next) /linklist_output運(yùn)用跳轉(zhuǎn)語句：void linklist_output1(