上堂課要點(diǎn)回顧棧棧的定義、特征*、抽象數(shù)據(jù)類型順序棧類及實(shí)現(xiàn)SeqStack.h單鏈棧類及實(shí)現(xiàn)LinStack.h棧的應(yīng)用*1、計(jì)算算術(shù)表達(dá)式的值第六次課閱讀：，第133-153頁（遞歸），第64-83頁（隊(duì)列）練習(xí)：作業(yè)53.2

棧的應(yīng)用3、實(shí)現(xiàn)遞歸算法（運(yùn)行時(shí)棧）P133~153多個(gè)函數(shù)的嵌套調(diào)用例：main()sub1(

) sub2(

) sub3(

)RSTTSR需要保存返回地址后調(diào)用先返回采用棧保存存：R，S，T?。篢，S，R遞歸(recursive)函數(shù)——是自己（直接或間接地）調(diào)用自己的函數(shù)例2：2階Fibonacci數(shù)列的遞歸定義n

0n

1Fib(n1)

Fib(n

2) n

10Fib(n)

1n

0n

Fact(n

1)

n

0Fact(n)

1例1：階乘的遞歸定義遞歸示例：n!遞歸函數(shù)必須包含一個(gè)遞歸出口。遞歸調(diào)用部分所使用的參數(shù)值應(yīng)比函數(shù)的參數(shù)值要小，以便重復(fù)調(diào)用能最終獲得基本部分所提供的值。n

0n

Fact(n

1)

n

0Fact(n)

1long

fact(int

n)//使用循環(huán)迭代方法，計(jì)算n!的函數(shù){

long

m=1;int

i;if(n>0)for(i=1;i<=n;i++)m=m*i;return

m;}//時(shí)間復(fù)雜度：O(n)long

Fact(int

n){

long

y;if

(n<0)

reurn

-1;if

(n==0)

return

1;else{

y=Fact(n-1);return

n*y;}}//時(shí)間復(fù)雜度：O(n)遞歸示例：2階斐波那契數(shù)列遞歸函數(shù)必須包含一個(gè)遞歸出口。遞歸調(diào)用部分所使用的參數(shù)值應(yīng)比函數(shù)的參數(shù)值要小，以便重復(fù)調(diào)用能最終獲得基本部分所提供的值。n

1Fib(n

1)

Fib(n

2)

n

1Fib(n)

1int

fibonacci(int

n)0

n

0

{if(n==0)

return

0;if(n==1)

return

1;int

oneBack=1;int

twoBack=0;for(int

i=2;i<=n;i++){ int

current=oneBack+twoBack;twoBack=oneBack;oneBack=current;}returncurrent;}//時(shí)間復(fù)雜度：O(n)int

Fibonacci(int

n){ if(n==0)

return

0;if(n==1)

return

1;

return

Fibonacci(n-1)+Fibonacci(n-2);}//時(shí)間復(fù)雜度為O(2n)遞歸原理每一次遞歸調(diào)用時(shí)，需要為過程中使用的參數(shù)、局部變量等另外分配

空間。每層遞歸調(diào)用需分配的空間形成遞歸工作記錄，按后進(jìn)先出的棧——遞歸工作棧組織。局部變量返回地址參數(shù)活動(dòng)記錄框架遞歸工作記錄main(

)4

ny=Fact(3)返回4*63

ny=Fact(2)返回3*2y=Fact(1)返回2*1y=Fact(0)Fact(4)2

n

1

n

0

n返回1遞歸調(diào)用子遞歸調(diào)用子遞歸調(diào)用子遞歸調(diào)用子程序Fact(3)

程序Fact(2)

程序Fact(1)

程序Fact(0)結(jié)果返回返回1*1結(jié)果返回結(jié)果返回結(jié)果返回結(jié)果返回int

Fact(int

n){

int

y;if

(n<0)

return

-1;if

(n==0) return

1;else{

y=Fact(n-1);return

n*y;}}void

main(

){

int

fn=Fact(4);cout<<fn;}main(

)4

ny=Fact(3)返回4*63

ny=Fact(2)返回3*2y=Fact(1)返回2*1返回1*1Fact(4)2

n

1

n

0

ny=Fact(0)

返回1結(jié)果返回結(jié)果返回結(jié)果返回結(jié)果返回結(jié)果返回ny

Fact434n

n234n1234y

Fact

y

Fact

y

Fact

ny

Fact011234ny

Factny

Fact3264ny

Fact4

6

24ny

Fact遞歸調(diào)用子遞歸調(diào)用子遞歸調(diào)用子遞歸調(diào)用子程序Fact(3)

程序Fact(2)

程序Fact(1)

程序Fact(0)ny

Fact11121223344適宜于用遞歸算法求解的問題的充分必要條件是：問題可借用類同自身的子問題進(jìn)行描述；某一有限步的子問題（也稱作本原問題）有直接的解存在。當(dāng)一個(gè)問題存在上述兩個(gè)基本要素時(shí)，該問題的遞歸算法的設(shè)計(jì)方法是：把對(duì)原問題的求解設(shè)計(jì)成包含有對(duì)子問題求解的形式；設(shè)計(jì)遞歸出口。3.3

隊(duì)列隊(duì)列（Queue）的基本概念定義：限定所有的操作在表的一端進(jìn)行，而刪除操作在表的另一端進(jìn)行的線性表。a0

a1

…an-1隊(duì)頭隊(duì)尾/入隊(duì)a0,a1

,

…

,

an-1例：

刪除/出隊(duì)a0,a1

,

…

,

an-1特征：先進(jìn)先出（InOut,

FIFO）3.3.2

隊(duì)列的抽象數(shù)據(jù)類型ADT

Queue數(shù)據(jù)元素：ai，i=0,1,…,n-1

(n≥0)，類型為DataType結(jié)構(gòu)：對(duì)所有的數(shù)據(jù)元素ai

(0≤i≤n-2)存在次序關(guān)系<ai，ai+1>, a0無前趨，an-1無后繼。邏輯操作：設(shè)Q為Queue

型Initiate(Q)

//構(gòu)造一個(gè)空隊(duì)列Q。NotEmpty(Q)/*判斷隊(duì)列Q非空否，若Q非空，則返回1，否則返回0。*/入一值為xAppend(Q,x)

/*在隊(duì)列Q的隊(duì)的元素。*/Delete(Q)/*刪除隊(duì)列Q的隊(duì)頭元素，被刪除的隊(duì)頭元素通過函數(shù)帶回。*/GetFront(Q)//取隊(duì)列Q的隊(duì)頭元素并由函數(shù)返回。約定隊(duì)頭指示器指向?qū)嶋H隊(duì)頭元素；隊(duì)尾指示器指向?qū)嶋H隊(duì)尾元素的下一個(gè)位置例如：MaxQueueSize-101n-1……frontrearna0a1…an-1…3.3.3

順序隊(duì)列順序隊(duì)列入隊(duì)、出隊(duì)時(shí)指針的變化情況：隊(duì)空frontrear元素A、B、C入隊(duì)后443rear322110front0CBA順序隊(duì)列入隊(duì)、出隊(duì)時(shí)指針的變化情況（續(xù)）：front43210rearEDA、B、C出隊(duì)，隊(duì)空43210rearfront元素D、E入隊(duì)，隊(duì)滿F入隊(duì)，“假溢出”CBA為解決“假溢出”現(xiàn)象，將隊(duì)列設(shè)想成環(huán)形。3.3.4

順序循環(huán)隊(duì)列0frontDrear123E44front

32rear10EDF順序循環(huán)隊(duì)列入隊(duì)、出隊(duì)時(shí)指針的變化0frontDrear123E40frontDrear13E4FG2H0Dfrontrear123E4順序循環(huán)隊(duì)列入隊(duì)、出隊(duì)時(shí)指針的變化①入隊(duì)描述：rear++；if

(rear==MaxQueueSize)rear=0；還可利用數(shù)學(xué)上的“模(%)運(yùn)算”來實(shí)現(xiàn)上述過程：rear＝(rear+1)

%

MaxQueueSize

；②出隊(duì)描述：front++；if

(front==MaxQueueSize)front=0；還可利用數(shù)學(xué)上的“模(%)運(yùn)算”來實(shí)現(xiàn)上述過程：front＝(front+1)

%

MaxQueueSize；如何判隊(duì)滿、隊(duì)空？01frontMaxQueueSize-1rear隊(duì)空解決方法：設(shè)置計(jì)數(shù)器count，表示表長當(dāng)count>0

&&

rear==

front

時(shí)，隊(duì)滿當(dāng)count==0

時(shí)，隊(duì)空front==rear隊(duì)滿？隊(duì)空？MaxQueueSize-101front

rear隊(duì)滿順序隊(duì)列類定義：class

Se

ueue{private:DataType

data[MaxQueueSize];//順序隊(duì)列數(shù)組//隊(duì)頭指示器，指向?qū)嶋H隊(duì)頭元素位置*///隊(duì)尾指示器，指向?qū)嶋H隊(duì)尾元素的下一個(gè)位置*///當(dāng)前表長intfront;int

rear;intcount;Public:ueue(void)

{front

=

rear

=

0;

count

=

0;};//構(gòu)造函數(shù)Se~Se

ueue(void){};void

Append(const

DataType&

item);DataType

Delete(void);DataType

GetFront(void)const;//析構(gòu)函數(shù)//入隊(duì)列//出隊(duì)列//取隊(duì)頭數(shù)據(jù)元素//非空否int

NotEmpty(void)

const

{return

count

!=

0;};};#define

MaxQueueSize

<隊(duì)列允許存放的最大元素?cái)?shù)>typedef

char

DataType;S

ueue.h文件實(shí)現(xiàn)順序循環(huán)隊(duì)列類【順序循環(huán)隊(duì)列的入隊(duì)算法】void

Se ueue::Append(const

DataType&

item)//把數(shù)據(jù)元素item

隊(duì)列作為當(dāng)前的新隊(duì)尾{if(count

>

0&&

front

==

rear){ cout<<"隊(duì)列已滿!"<<endl;data[rear]

=

item;exit(0);

}//把元素item加在隊(duì)尾rear

=

(rear

+1)

%

MaxQueueSize;//隊(duì)尾指示器加1count++;//計(jì)數(shù)器加1}【順序循環(huán)隊(duì)列的出隊(duì)算法】DataType

Se

ueue::Delete(void)//把隊(duì)頭元素出隊(duì)列，出隊(duì)列元素由函數(shù)返回{if(count

==

0){ cout

<<

"隊(duì)列已空!"

<<

endl;

exit(0);

}DataType

temp

=

data[front];front

=

(front

+

1)

%

MaxQueueSize;//保存原隊(duì)頭元素//隊(duì)頭指示器加1count--;return

temp;//計(jì)數(shù)器減1//返回原隊(duì)頭元素}【順序循環(huán)隊(duì)列的取隊(duì)頭算法】ueue::GetFront(

)

constDataType

Se{if(count

==

0){ cout<<“隊(duì)列已空!"<<endl;exit(0);

}return

data[front]；}3.3.5

單鏈隊(duì)列及其實(shí)現(xiàn)邏輯描述frontdata

next……隊(duì)尾結(jié)點(diǎn)rear∧frontrear∧空鏈隊(duì)列滿足Q->front==Q->rear非空鏈隊(duì)列：空鏈隊(duì)列：刪除隊(duì)頭位置結(jié)點(diǎn)位置a0an-1//定義類LinQueue<T>為友元//指針//數(shù)據(jù)元素{ friend

class

LinQueue<T>;private:QueueNode<T>

*next;T

data;public://構(gòu)造函數(shù)

（不含頭結(jié)點(diǎn)）QueueNode(const

T&

item,

QueueNode<T>

*ptrNext

=NULL)

:data(item),

next(ptrNext){}~QueueNode(){};//析構(gòu)函數(shù)};鏈隊(duì)列結(jié)點(diǎn)類定義template<class

T>

class

LinQueue;//前視定義,否則友元無法定義template<class

T>class

QueueNode//隊(duì)頭指針//隊(duì)尾指針//計(jì)數(shù)器，表長public:LinQueue(void){front=rear=NULL;count

=

0;};//構(gòu)造函數(shù)~LinQueue(void);//析構(gòu)函數(shù)void

Append(const

T&

item);//入隊(duì)列//出隊(duì)列//取隊(duì)頭數(shù)據(jù)元素//非空否T

Delete(void);T

GetFront(void)

const;int

NotEmpty(void)

const{return

count

!=

0;};};鏈隊(duì)列類定義template<class

T>class

LinQueue{private:QueueNode<T>

*front;QueueNode<T>

*rear;int

count;【鏈隊(duì)列的析構(gòu)函數(shù)】template

<class

T>void

LinQueue<T>::~LinQueue

(

){ QueueNode<T>

*p,

*q;p=front;while(

p!=

NULL){

q=p;p=p->next;delete

q;

}count=0;front=NULL;rear=NULL;}鏈隊(duì)列的運(yùn)算（不結(jié)點(diǎn)）newnode∧itemfront…∧∧rearrear->next=newnode;rear=newnode;【鏈隊(duì)列的入隊(duì)算法】template

<class

T>void

LinQueue<T>::Append(const

T&

item)//把數(shù)據(jù)元素item

隊(duì)列作為新隊(duì)尾結(jié)點(diǎn){/*構(gòu)造新結(jié)點(diǎn)newNode，newNode的data域值為item，next域值為NULL*/QueueNode<T>*newNode=new

QueueNode<T>(item);if(rear!=NULL)

rear->next=newNode;//新結(jié)點(diǎn)鏈入rear

=

newNode;//隊(duì)尾指針指向新隊(duì)尾結(jié)點(diǎn)//若隊(duì)頭指針原先為空則置為指向新結(jié)點(diǎn)if(front

==

NULL)

front

=

newNode;count++;//計(jì)數(shù)器加1}鏈隊(duì)列的刪除運(yùn)算（不結(jié)點(diǎn)）pfront∧…rearp=front->next;delete(front);front=p;p=NULL∧注意：∧frontrearif

(p==NULL)

rear=NULL;∧【鏈隊(duì)列的出隊(duì)算法】template

<class

T>

T

LinQueue<T>::Delete(void)//把隊(duì)頭結(jié)點(diǎn)刪除并由函數(shù)返回{

if(count

==

0){ cout

<<"隊(duì)列已空！"

<<endl;exit(0);

}QueueNode<T>*p=front->next;//p指向新的隊(duì)頭結(jié)點(diǎn)T

data=front->data;//保存原隊(duì)頭結(jié)點(diǎn)的data域值delete

front;front

=

p;//

原隊(duì)頭結(jié)點(diǎn)空間//front指向新的隊(duì)頭結(jié)點(diǎn)if(front==NULL)rear=NULL;//增加處理rear語句count--;return

data;//計(jì)數(shù)器減1//返回原隊(duì)頭結(jié)點(diǎn)的data域值}【鏈隊(duì)列的取隊(duì)頭函數(shù)】template

<class

T>DataType

LinQueue<T>::GetFront

(){if(

count==0){ cout

<<"隊(duì)列已空！"

<<endl;exit(0);

}return

front->data;}3.3.6

隊(duì)列的應(yīng)用1、回文問題（P80）以中間字符為基準(zhǔn)兩邊字符完全相同的字符序列稱之為回文，編寫一個(gè)函數(shù)判斷字符序列是否是回文。例如：A

B

B

AA

B

C

DE

D

C

B

AA

B

C

D

E

DC

A

BABCDEDCBA隊(duì)列rear->front->ABCDEDCBA棧top->思想：1、自左向右掃描字符串，字符依次進(jìn)棧S；入隊(duì)列Q；2、當(dāng)棧S非空且隊(duì)列Q非空時(shí)，依次若S棧頂元素和Q隊(duì)頭元素相等，則S出棧；Q出隊(duì)列；否則，輸出不是回文，并退出3、輸出字符串是回文，并退出算法：P82-83

：采用順序循環(huán)隊(duì)列。#include

"LinQueue.h"#include

"LinStack.h"void

HuiWen(char

str[]){ LinStack<char>

myStack;LinQueue<char>

myQueue;//求字符序列長度intn

=

strlen(str);for(int

i

=0;

i<n;

i++){

myQueue.Append(str[i]);myStack.Push(str[i]);}while(myQueue.NotEmpty()

&&

myStack.NotEmpty()

){ if(myQueue.Delete()

!=

myStack.Pop()){cout

<<

"不是回文!"

<<endl;

return;}}cout<<"是回文!"<<endl;}3.3.6

隊(duì)列的應(yīng)用操作系統(tǒng)中用到隊(duì)列

1、對(duì)CPU的分配管理：進(jìn)程排隊(duì)、作業(yè)排隊(duì)一般計(jì)算機(jī)只有一個(gè)CPU，采用一個(gè)就緒隊(duì)列管理CPU的分配。

當(dāng)多個(gè)進(jìn)程需要CPU運(yùn)行時(shí)，它的進(jìn)程名就

入到就緒隊(duì)列的隊(duì)尾。CPU總是首先執(zhí)行排在隊(duì)頭的進(jìn)程。一個(gè)進(jìn)程分配到CPU的一段時(shí)間執(zhí)行完了，又將它 到隊(duì)尾等待，CPU轉(zhuǎn)而為執(zhí)行下一個(gè)

隊(duì)頭進(jìn)程。如此，按“先進(jìn)先出”的原則一直進(jìn)行下去，直到執(zhí)行完的進(jìn)程從隊(duì)列中逐個(gè)刪除掉。隊(duì)列的應(yīng)用操作系統(tǒng)中用到隊(duì)列2、主機(jī)與外部設(shè)備之間通信由于外部設(shè)備傳輸速度遠(yuǎn)遠(yuǎn)低于主機(jī)傳輸速度，可以設(shè)定一個(gè)“輸出數(shù)據(jù)隊(duì)列緩沖區(qū)”

。當(dāng)主機(jī)要輸出數(shù)據(jù)時(shí)，將數(shù)據(jù)按塊（例如每塊512B）逐個(gè)添加到“隊(duì)列緩沖區(qū)”的尾端，寫滿后就暫停輸出，繼而去做其它的事情。而外部設(shè)備則依其輸出速度按照先進(jìn)先出的原則依次從隊(duì)首逐個(gè)取出數(shù)據(jù)塊輸出，打印完后再向主機(jī)發(fā)出請(qǐng)求，主機(jī)接到請(qǐng)求后再向緩沖區(qū)寫入打印數(shù)據(jù)，這樣利用隊(duì)列既保證了輸出的數(shù)據(jù)有完全相同的次序，

不致發(fā)生輸出次序的

或數(shù)據(jù)的丟失，同時(shí)保證了主機(jī)的效率。隊(duì)列的應(yīng)用◆事件驅(qū)動(dòng)模擬銀行業(yè)務(wù)模擬每個(gè)來到的顧客發(fā)一個(gè)號(hào)碼，如果哪個(gè)柜臺(tái)空閑了，就叫號(hào)碼最靠前的顧客來辦理業(yè)務(wù)；如果同時(shí)幾個(gè)柜臺(tái)

空閑，就按照一種法則來決定這幾個(gè)柜臺(tái)叫號(hào)的順序（最簡單的是按柜臺(tái)號(hào)碼順序）。這樣，就能保證顧客按照先來后到的順序接受服務(wù)——因?yàn)榇蠹遗旁谝粋€(gè)隊(duì)里。航空客運(yùn)訂票系統(tǒng)對(duì)于預(yù)約客戶 數(shù)據(jù)來說，由于要遵循先到先服務(wù)的原則，因此采用隊(duì)列結(jié)構(gòu)。由于預(yù)約人數(shù)無法預(yù)計(jì)，因此隊(duì)列應(yīng)以鏈表作為

結(jié)構(gòu)。電梯模擬……補(bǔ)充題：設(shè)數(shù)據(jù)元素序列{a,b,c,d,e,f,g}的進(jìn)隊(duì)列操作和出隊(duì)列操作可任意進(jìn)行，請(qǐng)羅列出所有的出隊(duì)列序列。已知K和max，要求輸出K階斐波那契序列前n+1項(xiàng)（

f0,f1,…,fn），其中fn<=max而fn+1>max（max為給定常數(shù)）。算法要求僅采用空間大小為K的數(shù)組實(shí)現(xiàn)。