实验5-递归及队列.doc

《实验5-递归及队列.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验报告五递归及队列一、实验目的：（1）掌握递归的基本思想。（2）掌握链式队列及循环队列的基本操作算法。（3）应用队列先进先出的特点，解决一些实际问题。二、实验内容：1、p(a-b，b)+1当a>=bp(a,b)=其中a,b为正整数。0当aintp(inta,intb){if(a

2、<intakm(intm,intn){if(m==0)returnn+1;if(m&&!n)returnakm(m-1,1);else{returnakm(m-1,akm(m,n-1));}}voidmain(){ints,t,l;s=akm(0,8);cout<

3、<"结果为:"<usingnamespacestd;intmaxsize=100;template//定义模板类DCirQueueclassDCirQ

4、ueue{public:DCirQueue(intsize=10);//构造函数，置空队~DCirQueue(){delete[]queue;};//析构函数voidEnQueue(Tx);//将元素x入队TDeQueue();//将队头元素出队TGetQueue();//取队头元素（并不删除）intIsEmpty();//判断队列是否为空intlength();//求队列元素个数voiddisplay();//遍历队列intdestroy();//清空队列private:T*queue;//存放队列元素的数组intfront,rear;//队头和队

5、尾指针，分别指向队头元素的前一个位置和队尾元素的位置intmaxsize;//队列最大可容纳元素个数为maxsize-1};（1）构造一个空的循环队列输入：队列元素存储区域的大小size;动作：初始化队列，队头及队尾指示器,申请存储队列的数组，设置队列存储区域的大小templateDCirQueue::DCirQueue(intsize):front(0),rear(0),maxsize(size){queue=newT[maxsize];if(queue==NULL)cout<<"动态分配失败!";}（2）入队操作算法实现：输

6、入：要入队的元素x;前置条件：队列未满动作：把x插入队尾输出：无后置条件：队列中增加了一个元素templatevoidDCirQueue::EnQueue(Tx){if((rear+1)%maxsize==front)cout<<“队满";rear=(rear+1)%maxsize;//队尾指针在循环意义下加1queue[rear]=x;//在队尾处插入元素}（3）求队列的元素个数算法输入：无前置条件：无；动作：求队列的元素个数，含表空返回个数为零的情况。输出：返回队列的元素个数。templateintDCirQ

7、ueue::length(){intlength;length=（maxsize＋rear－front）%maxsize;returnlength;}（4）出队操作算法输入：无前置条件：队列非空动作：删除队头元素输出：返回队头元素的值后置条件：队列中删除了一个元素templateTDCirQueue::DeQueue(){if(rear==front)cout<<"下溢!";front=(front+1)%maxsize;//队头指针在循环意义下加1returnqueue[front];//读取并返回出队前的队头元素，注意

8、队头指针}（5）遍历队列算法输入：无前置条件：队列非空动作：输出队列中的各元素输出：无后置条件：无templ