数据结构与算法习题及答案

精心整理

{//出队,把头结点之后的元素摘下

Datatypet;

QueueNode*p;

if(EmptyQueue(Q))

Error(\

p=Q->rear->next->next;//p指向将要摘下的结点 x=p->data;//保存结点中数据 if(p==Q->rear) {//当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点 Q->rear=Q->rear->next;Q->rear->next=p->next;} else? Q->rear->next->next=p->next;//摘下结点p free(p);//释放被删结点 returnx; } （7）假设以数组Q[m]存放循环队列中的元素,同时设置一个标志tag，以tag==0和tag==1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。

【解答】

循环队列类定义

#include

templateclassQueue{ public: Queue(int=10); ~Queue(){delete[]Q;}

//循环队列的类定义

精心整理

精心整理

voidEnQueue(Type&item); TypeDeQueue(); TypeGetFront();

voidMakeEmpty(){front=rear=tag=0;}

//置空队列

intIsEmpty()const{returnfront==rear&&tag==0;} //判队列空否 intIsFull()const{returnfront==rear&&tag==1;} //判队列满否 private: intrear,front,tag; Type*Q; intm; }

//队尾指针、队头指针和队满标志

//存放队列元素的数组 //队列最大可容纳元素个数

构造函数 template Queue::Queue(intsz):rear(0),front(0),tag(0),m(sz){ //建立一个最大具有m个元素的空队列。 Q=newType[m]; assert(Q!=0); } //创建队列空间 //断言:动态存储分配成功与否

插入函数 template voidQueue::EnQueue(Type&item){ } assert(!IsFull()); rear=(rear+1)%m; Q[rear]=item; tag=1; //判队列是否不满，满则出错处理 //队尾位置进1,队尾指针指示实际队尾位置 //进队列 //标志改1，表示队列不空

删除函数 template TypeQueue::DeQueue(){ assert(!IsEmpty()); front=(front+1)%m; tag=0; returnQ[front]; //判断队列是否不空，空则出错处理 //队头位置进1,队头指针指示实际队头的前一位置 //标志改0,表示栈不满 //返回原队头元素的值 }

读取队头元素函数 template TypeQueue::GetFront(){ }

assert(!IsEmpty());

//判断队列是否不空，空则出错处理

//返回队头元素的值

returnQ[(front+1)%m];

(8）如果允许在循环队列的两端都可以进行插入和删除操作。要求： ①写出循环队列的类型定义；

②写出“从队尾删除”和“从队头插入”的算法。

[题目分析]用一维数组v[0..M-1]实现循环队列，其中M是队列长度。设队头指针front和队尾指针rear，约定front指向队头元素的前一位置，rear指向队尾元素。定义front=rear时为队空，(rear+1)%m=front为队满。约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展。 精心整理

精心整理

（1）#defineM队列可能达到的最大长度 typedefstruct {elemtpdata[M]; intfront,rear; }cycqueue;

（2）elemtpdelqueue(cycqueueQ)

//Q是如上定义的循环队列，本算法实现从队尾删除，若删除成功，返回被删除元素，否则给出出错信息。

{if(Q.front==Q.rear){printf(“队列空”);exit(0);} Q.rear=(Q.rear-1+M)%M;//修改队尾指针。

return(Q.data[(Q.rear+1+M)%M]);//返回出队元素。 }//从队尾删除算法结束

voidenqueue(cycqueueQ,elemtpx) //Q是顺序存储的循环队列，本算法实现“从队头插入”元素x。 {if(Q.rear==(Q.front-1+M)%M){printf(“队满”;exit(0);) Q.data[Q.front]=x;//x入队列 Q.front=(Q.front-1+M)%M;//修改队头指针。 }//结束从队头插入算法。 （9）已知Ackermann函数定义如下: ①写出计算Ack(m,n)的递归算法，并根据此算法给出出Ack(2,1)的计算过程。 ②写出计算Ack(m,n)的非递归算法。 intAck(intm,n) {if(m==0)return(n+1); elseif(m!=0&&n==0)return(Ack(m-1,1)); elsereturn(Ack(m-1,Ack(m,m-1)); }//算法结束 （1）Ack(2,1)的计算过程 Ack(2,1)=Ack(1,Ack(2,0))//因m<>0,n<>0而得 =Ack(1,Ack(1,1))//因m<>0,n=0而得 =Ack(1,Ack(0,Ack(1,0)))//因m<>0,n<>0而得 =Ack(1,Ack(0,Ack(0,1)))//因m<>0,n=0而得 =Ack(1,Ack(0,2))//因m=0而得 =Ack(1,3)//因m=0而得 =Ack(0,Ack(1,2))//因m<>0,n<>0而得 =Ack(0,Ack(0,Ack(1,1)))//因m<>0,n<>0而得 =Ack(0,Ack(0,Ack(0,Ack(1,0))))//因m<>0,n<>0而得 =Ack(0,Ack(0,Ack(0,Ack(0,1))))//因m<>0,n=0而得 =Ack(0,Ack(0,Ack(0,2)))//因m=0而得 =Ack(0,Ack(0,3))//因m=0而得 =Ack(0,4)//因n=0而得 =5//因n=0而得

（2）intAckerman(intm,intn) {intakm[M][N];inti,j;

for(j=0;j

{akm[i][0]=akm[i-1][1]; for(j=1;j

精心整理

akm[i][j]=akm[i-1][akm[i][j-1]]; }

return(akm[m][n]); }//算法结束

（10）已知f为单链表的表头指针,链表中存储的都是整型数据，试写出实现下列运算的递归算法： ①求链表中的最大整数； ②求链表的结点个数； ③求所有整数的平均值。

#include classList; friendclassList; private:

}; classList{ private:

};

}

voidList::NewList(constintretvalue){

first=NULL;intvalue;ListNode*q; cout<<\; cin>>value;

while(value!=retvalue){

//提示 //输入 //输入有效

//建立包含value的新结点

//建立链表,以输入retvalue结束

ListNode*first,current; intMax(ListNode*f); intNum(ListNode*f); floatAvg(ListNode*f,int&n); List():first(NULL),current(NULL){} ~List(){} ListNode*NewNode(constintitem); voidNewList(constintretvalue); voidPrintList(); //构造函数 //析构函数 //创建链表结点,其值为item //链表类 intdata; //结点数据 //结点指针 //构造函数 ListNode*link;

//链表结点类

classListNode{

//定义在头文件\中

ListNode(constintitem):data(item),link(NULL){} public: //建立链表,以输入retvalue结束 //输出链表所有结点数据 //求链表所有数据的最大值 //求链表中数据个数 //求链表所有数据的平均值 //创建新链表结点 intGetMax(){returnMax(first);} intGetNum(){returnNum(first);} floatGetAvg(){returnAvg(first);} ListNode*List::NewNode(constintitem){ returnnewnode; ListNode*newnode=newListNode(item); q=NewNode(value);

if(first==NULL)first=current=q; else{current->link=q;current=q;}

//空表时,新结点成为链表第一个结点 //非空表时,新结点链入链尾

精心整理