實(shí)驗(yàn)5遞歸及隊(duì)列

1、實(shí)驗(yàn)報(bào)告五 遞歸及隊(duì)列一、 實(shí)驗(yàn)?zāi)康模海?） 掌握遞歸的基本思想。（2） 掌握鏈?zhǔn)疥?duì)列及循環(huán)隊(duì)列的基本操作算法。（3） 應(yīng)用隊(duì)列先進(jìn)先出的特點(diǎn)，解決一些實(shí)際問題。二、 實(shí)驗(yàn)內(nèi)容：1、 p(a-b，b)+1 當(dāng)a>=bp(a,b)= 其中a,b為正整數(shù)。 0 當(dāng)a<b利用遞歸設(shè)計(jì)此函數(shù)。#include<iostream.h>int p(int a,int b)if(a<b)return 0;elsereturn p(a-b,b)+1; void main() int x;x=p(6,2);cout<<"結(jié)果為: "<<x

2、<<endl;int y;y=p(3,4);cout<<"結(jié)果為: "<<y<<endl;粘貼測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果：2、Ackerman函數(shù)如下： n+1 當(dāng)m=0akm(m,n)= akm(m-1,1) 當(dāng)m0,n=0 akm(m-1,akm(m,n-1) 其它情形利用遞歸設(shè)計(jì)此函數(shù)。試求akm(1，2),akm(2，1)？粘貼#include<iostream.h>int akm(int m,int n)if(m=0)return n+1; if(m && !n)return akm(m-1,1)

3、;else return akm(m-1,akm(m,n-1);void main() int s,t,l;s=akm(0,8);cout<<"結(jié)果為: "<<s<<endl;t=akm(1,2);cout<<"結(jié)果為: "<<t<<endl;l=akm(2,1);cout<<"結(jié)果為: "<<l<<endl;測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果：3、循環(huán)隊(duì)列的實(shí)現(xiàn)（請(qǐng)采用模板類及模板函數(shù)實(shí)現(xiàn)）實(shí)現(xiàn)提示函數(shù)、類名稱等可自定義，部分變量請(qǐng)加上學(xué)號(hào)后

4、3位。也可自行對(duì)類中所定義的操作進(jìn)行擴(kuò)展。所加載的庫函數(shù)或常量定義及類的定義：#include<iostream>using namespace std;int maxsize=100;template <class T> /定義模板類DCirQueueclass DCirQueuepublic: DCirQueue( int size=10); /構(gòu)造函數(shù)，置空隊(duì) DCirQueue( )delete queue; /析構(gòu)函數(shù) void EnQueue(T x); /將元素x入隊(duì) T DeQueue( ); /將隊(duì)頭元素出隊(duì) T GetQueue( ); /取隊(duì)頭元素

5、（并不刪除）int IsEmpty( ); /判斷隊(duì)列是否為空int length(); /求隊(duì)列元素個(gè)數(shù)void display(); /遍歷隊(duì)列int destroy(); /清空隊(duì)列private: T *queue; /存放隊(duì)列元素的數(shù)組 int front, rear; /隊(duì)頭和隊(duì)尾指針，分別指向隊(duì)頭元素的前一個(gè)位置和隊(duì)尾元素的位置 int maxsize; /隊(duì)列最大可容納元素個(gè)數(shù)為maxsize-1;（1）構(gòu)造一個(gè)空的循環(huán)隊(duì)列 輸入：隊(duì)列元素存儲(chǔ)區(qū)域的大小size;動(dòng)作：初始化隊(duì)列，隊(duì)頭及隊(duì)尾指示器,申請(qǐng)存儲(chǔ)隊(duì)列的數(shù)組，設(shè)置隊(duì)列存儲(chǔ)區(qū)域的大小template <class

6、T>DCirQueue<T>:DCirQueue( int size):front(0),rear(0),maxsize(size) queue=new Tmaxsize;if(queue=NULL) cout<<"動(dòng)態(tài)分配失敗!" （2）入隊(duì)操作算法實(shí)現(xiàn)：輸入：要入隊(duì)的元素x;前置條件：隊(duì)列未滿動(dòng)作：把x插入隊(duì)尾輸出：無后置條件：隊(duì)列中增加了一個(gè)元素template <class T> void DCirQueue<T>:EnQueue(T x) if (rear+1) % maxsize =front) cout&l

7、t;<“隊(duì)滿" rear=(rear+1) % maxsize; /隊(duì)尾指針在循環(huán)意義下加1 queuerear=x; /在隊(duì)尾處插入元素（3）求隊(duì)列的元素個(gè)數(shù)算法輸入：無前置條件：無；動(dòng)作：求隊(duì)列的元素個(gè)數(shù)，含表空返回個(gè)數(shù)為零的情況。輸出：返回隊(duì)列的元素個(gè)數(shù)。template <class T> int DCirQueue<T>:length()int length;length=（maxsizerearfront）% maxsize;return length;（4）出隊(duì)操作算法輸入：無前置條件：隊(duì)列非空動(dòng)作：刪除隊(duì)頭元素輸出：返回隊(duì)頭元素的值后置條

8、件：隊(duì)列中刪除了一個(gè)元素template <class T> T DCirQueue<T>:DeQueue( ) if (rear=front) cout<< "下溢!" front=(front+1) % maxsize; /隊(duì)頭指針在循環(huán)意義下加1 return queuefront; /讀取并返回出隊(duì)前的隊(duì)頭元素，注意隊(duì)頭指針（5）遍歷隊(duì)列算法輸入：無前置條件：隊(duì)列非空動(dòng)作：輸出隊(duì)列中的各元素輸出：無后置條件：無template <class T> void DCirQueue<T>:display()whi

9、le(rear！=front) i=(front+1) % maxsize; front+; cout<<queuei-1<<” ”; （7）判隊(duì)列為空算法輸入：無前置條件：隊(duì)列存在動(dòng)作：判是否為空輸出：空返回1，否則返回0后置條件：無template <class T>int DCirQueue<T>:IsEmpty( )if(front=rear)return 1;return 0;（8）獲得隊(duì)列頭結(jié)點(diǎn)輸入：無前置條件：隊(duì)列存在動(dòng)作：獲得隊(duì)頭的元素輸出：返回隊(duì)頭的元素值后置條件：無template <class T>T DCirQ

10、ueue<T>:GetQueue( ) int i; if (rear=front) throw “隊(duì)空!" i=(front+1) % maxsize; /注意不要給隊(duì)頭指針賦值 return queuei;測(cè)試主函數(shù):void main()DCirQueue<int> myqueue(80);int a=3,6,8,78,35,67;int n=6;for(int i=0;i<n;i+)myqueue.EnQueue(ai);cout<<"隊(duì)列長(zhǎng)度為: "<<myqueue.length()<<

11、endl;cout<<"隊(duì)頭元素: "<<myqueue.GetQueue( )<<endl;cout<<"刪除隊(duì)頭元素: "<<myqueue.DeQueue( )<<endl;cout<<"隊(duì)列長(zhǎng)度為: "<<myqueue.length()<<endl;myqueue.EnQueue(9);myqueue.EnQueue(75);cout<<"隊(duì)列長(zhǎng)度為: "<<myqueue.

12、length()<<endl;cout<<"隊(duì)列是否已滿（1表示已滿，0表示未滿）: "<<myqueue.IsEmpty( )<<endl;cout<<"diyichibianli: "myqueue.display();cout<<endl;cout<<"隊(duì)列是否已滿（1表示已滿，0表示未滿）: "<<myqueue.IsEmpty( )<<endl;粘貼測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果：4、鏈?zhǔn)疥?duì)列的基本操作算法實(shí)現(xiàn)（請(qǐng)采用模板類及模板

13、函數(shù)實(shí)現(xiàn)）實(shí)現(xiàn)提示 同時(shí)可參見教材p98-p99頁的ADT描述及算法實(shí)現(xiàn)及ppt）函數(shù)、類名稱等可自定義，部分變量請(qǐng)加上學(xué)號(hào)后3位。也可自行對(duì)類中所定義的操作進(jìn)行擴(kuò)展。所加載的庫函數(shù)或常量定義及類的定義：（自選擇帶頭結(jié)點(diǎn)或不帶頭結(jié)點(diǎn)）#include<iostream.h>template <class T>class LinkQueue;template <class T>class Node friend class LinkQueue<T>private:T data; Node<T> *next; /此處<T>也可

14、以省略;template <class T>class LinkQueuepublic: LinkQueue( ); /構(gòu)造函數(shù)，初始化一個(gè)空的鏈隊(duì)列 LinkQueue(T a,int n ); /有參構(gòu)造函數(shù) LinkQueue( ) /析構(gòu)函數(shù)，釋放鏈隊(duì)中各結(jié)點(diǎn)的存儲(chǔ)空間 void EnQueue(T x); /將元素x入隊(duì) T DeQueue( ); /將隊(duì)頭元素出隊(duì) T GetQueue( ); /取鏈隊(duì)列的隊(duì)頭元素 int Empty( ); /判斷鏈隊(duì)列是否為空 int length(); /求隊(duì)列長(zhǎng)度 void display(); /遍歷private: Node

15、<T> *front, *rear; /隊(duì)頭和隊(duì)尾指針，分別指向頭結(jié)點(diǎn)和終端結(jié)點(diǎn);（1）初始化鏈?zhǔn)娇贞?duì)列關(guān)鍵動(dòng)作：初始化隊(duì)列，設(shè)置隊(duì)頭及隊(duì)尾指示器。 template <class T>LinkQueue<T>:LinkQueue( )front=rear=NULL;（2）帶參數(shù)的構(gòu)造函數(shù)，實(shí)現(xiàn)創(chuàng)建鏈?zhǔn)疥?duì)列輸入：存儲(chǔ)放初始數(shù)據(jù)元素的數(shù)組a，元素個(gè)數(shù)n前置條件：隊(duì)列不存在動(dòng)作：把a(bǔ)中的數(shù)據(jù)元素依次插入隊(duì)尾輸出：無后置template <class T> LinkQueue<T>:LinkQueue(T a,int n )front=re

16、ar=NULL; Node<T> *s; s=new Node<T> for(int i=0;i<n;i+) s->data=ai; /申請(qǐng)一個(gè)數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)s s->next=NULL; rear=s; 條件：隊(duì)列中有n個(gè)元素入隊(duì)（3）入隊(duì)操作算法輸入：要入隊(duì)的元素x;前置條件：隊(duì)列未滿動(dòng)作：把x插入隊(duì)尾輸出：無后置條件：隊(duì)列中增加了一個(gè)元素template <class T> void LinkQueue<T>:EnQueue(T x) Node<T> *s; s=new Node<T> s->

17、;data=x; /申請(qǐng)一個(gè)數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)s s->next=NULL;if(front=NULL) /空隊(duì)列，新結(jié)點(diǎn)既是隊(duì)頭，又是隊(duì)尾 front=rear=s;else rear->next=s; /將結(jié)點(diǎn)s插入到隊(duì)尾 rear=s;（4）出隊(duì)操作算法輸入：無前置條件：隊(duì)列非空動(dòng)作：刪除隊(duì)頭元素輸出：返回隊(duì)頭元素的值后置條件：隊(duì)列中刪除了一個(gè)元素template <class T>T LinkQueue<T>:DeQueue() Node <T> *p; int x; if (front=NULL) cout<<"隊(duì)空

18、" p=front; x=p->data; /暫存隊(duì)頭元素 front=front->next; /將隊(duì)頭元素所在結(jié)點(diǎn)摘鏈 if (front=NULL) rear=front; /判斷出隊(duì)前隊(duì)列長(zhǎng)度是否為1 delete p; return x;（5）清空隊(duì)列算法輸入：無前置條件：隊(duì)列存在動(dòng)作：釋放隊(duì)列的存儲(chǔ)空間輸出：無后置條件：隊(duì)列不存在template <class T>Void LinkQueue<T>:destroy( )Node <T> *p,*q;P=front;While(p!=(rear->next)q=p;P=

19、p->next;Delete q;Front=rear=NULL;（6）判隊(duì)列為空算法輸入：無前置條件：隊(duì)列存在動(dòng)作：判是否為空輸出：空返回1，否則返回0后置條件：無template <class T> int LinkQueue<T>:Empty( )if(rear=NULL)return 1;return 0;（7）獲得隊(duì)列頭結(jié)點(diǎn)輸入：無前置條件：隊(duì)列存在動(dòng)作：獲得隊(duì)頭的元素輸出：返回隊(duì)頭的元素值后置條件：無template <class T> T LinkQueue<T>:GetQueue() if (front!=NULL) ret

20、urn front->data;（8）遍歷隊(duì)列中的元素輸入：無前置條件：隊(duì)列非空動(dòng)作：輸出隊(duì)列中的各元素輸出：無后置條件：無template <class T>void LinkQueue<T>:display()while(front!=(rear->next)cout<<front->data<<" " front=front->next;（9）求隊(duì)列數(shù)據(jù)元素個(gè)數(shù)輸入：無前置條件：無；動(dòng)作：求隊(duì)列的元素個(gè)數(shù)，含表空返回個(gè)數(shù)為零的情況。輸出：返回隊(duì)列的元素個(gè)數(shù)。template <class T>int LinkQueue<T>:length