課件-數(shù)據(jù)結(jié)構(gòu)

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

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

) sub2(

) sub3(

)RSTTSR需要保存返回地址后調(diào)用先返回采用棧保存存：R，S，T取：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ù)必須包含一個遞歸出口。遞歸調(diào)用部分所使用的參數(shù)值應(yīng)比函數(shù)的參數(shù)值要小，以便重復(fù)調(diào)用能最終獲得基本部分所提供的值。n

0n

Fact(n

1)

n

0Fact(n)

1long

fact(int

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

long

m=1;int

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

m;}//時間復(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;}}//時間復(fù)雜度：O(n)遞歸示例：2階斐波那契數(shù)列遞歸函數(shù)必須包含一個遞歸出口。遞歸調(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;}//時間復(fù)雜度：O(n)int

Fibonacci(int

n){ if(n==0)

return

0;if(n==1)

return

1;

return

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

空間。每層遞歸調(diào)用需分配的空間形成遞歸工作記錄，按后進(jìn)先出的?！f歸工作棧組織。局部變量返回地址參數(shù)活動記錄框架遞歸工作記錄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)一個問題存在上述兩個基本要素時，該問題的遞歸算法的設(shè)計方法是：把對原問題的求解設(shè)計成包含有對子問題求解的形式；設(shè)計遞歸出口。3.3

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

a1

…an-1隊頭隊尾/入隊a0,a1

,

…

,

an-1例：

刪除/出隊a0,a1

,

…

,

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

FIFO）3.3.2

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

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

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

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

型Initiate(Q)

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

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

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

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

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

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

%

MaxQueueSize

；②出隊描述：front++；if

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

%

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

&&

rear==

front

時，隊滿當(dāng)count==0

時，隊空front==rear隊滿？隊空？MaxQueueSize-101front

rear隊滿順序隊列類定義：class

Se

ueue{private:DataType

data[MaxQueueSize];//順序隊列數(shù)組//隊頭指示器，指向?qū)嶋H隊頭元素位置*///隊尾指示器，指向?qū)嶋H隊尾元素的下一個位置*///當(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ù)//入隊列//出隊列//取隊頭數(shù)據(jù)元素//非空否int

NotEmpty(void)

const

{return

count

!=

0;};};#define

MaxQueueSize

<隊列允許存放的最大元素數(shù)>typedef

char

DataType;S

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

Se ueue::Append(const

DataType&

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

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

>

0&&

front

==

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

=

item;exit(0);

}//把元素item加在隊尾rear

=

(rear

+1)

%

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

Se

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

==

0){ cout

<<

"隊列已空!"

<<

endl;

exit(0);

}DataType

temp

=

data[front];front

=

(front

+

1)

%

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

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

)

constDataType

Se{if(count

==

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

}return

data[front]；}3.3.5

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

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

class

LinQueue<T>;private:QueueNode<T>

*next;T

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

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

T&

item,

QueueNode<T>

*ptrNext

=NULL)

:data(item),

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

T>

class

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

T>class

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

=

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

Append(const

T&

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

Delete(void);T

GetFront(void)

const;int

NotEmpty(void)

const{return

count

!=

0;};};鏈隊列類定義template<class

T>class

LinQueue{private:QueueNode<T>

*front;QueueNode<T>

*rear;int

count;【鏈隊列的析構(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;}鏈隊列的運(yùn)算（不結(jié)點）newnode∧itemfront…∧∧rearrear->next=newnode;rear=newnode;【鏈隊列的入隊算法】template

<class

T>void

LinQueue<T>::Append(const

T&

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

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

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

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

=

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

==

NULL)

front

=

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

(p==NULL)

rear=NULL;∧【鏈隊列的出隊算法】template

<class

T>

T

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

if(count

==

0){ cout

<<"隊列已空！"

<<endl;exit(0);

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

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

front;front

=

p;//

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

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

<class

T>DataType

LinQueue<T>::GetFront

(){if(

count==0){ cout

<<"隊列已空！"

<<endl;exit(0);

}return

front->data;}3.3.6

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

B

B

AA

B

C

DE

D

C

B

AA

B

C

D

E

DC

A

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

：采用順序循環(huán)隊列。#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

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

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

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

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

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

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

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

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

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

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

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