Q->rear = Q->rear->next;//将队尾指针指向头结点
while (Q->rear!=Q->rear->next)//当队列非空,将队中元素逐个出队 {s=Q->rear->next; Q->rear->next=s->next; free(s); }//回收结点空间 }
(2)判队空
int EmptyQueue( LinkQueue *Q) { //判队空
//当头结点的next指针指向自己时为空队 return Q->rear->next->next==Q->rear->next; }
(3)入队
void EnQueue( LinkQueue *Q, Datatype x) { //入队
//也就是在尾结点处插入元素
QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode));//申请新结点 p->data=x; p->next=Q->rear->next;//初始化新结点并链入 Q-rear->next=p;
Q->rear=p;//将尾指针移至新结点 }
(4)出队
Datatype DeQueue( LinkQueue *Q) {//出队,把头结点之后的元素摘下 Datatype t; 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);//释放被删结点 return x; }
(7)假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag,以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时,队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。
【解答】
循环队列类定义
#include
template
Queue ( int=10 ); ~Queue ( ) { delete [ ] Q; } void EnQueue ( Type & item ); Type DeQueue ( ); Type GetFront ( );
void MakeEmpty ( ) { front = rear = tag = 0; }
//置空队列
//判队列空否
int IsEmpty ( ) const { return front == rear && tag == 0; } private:
int rear, front, tag; Type *Q; int m; }
//队尾指针、队头指针和队满标志
//存放队列元素的数组 //队列最大可容纳元素个数
//循环队列的类定义
int IsFull ( ) const { return front == rear && tag == 1; } //判队列满否
构造函数
template
Queue
Q = new Type[m]; assert ( Q != 0 ); }
//创建队列空间
//断言: 动态存储分配成功与否
插入函数
template
void Queue
assert ( ! IsFull ( ) ); rear = ( rear + 1 ) % m; Q[rear] = item; tag = 1;
//判队列是否不满,满则出错处理
//队尾位置进1, 队尾指针指示实际队尾位置 //进队列
//标志改1,表示队列不空
位置
删除函数
template
Type Queue
assert ( ! IsEmpty ( ) ); front = ( front + 1 ) % m; tag = 0;
//判断队列是否不空,空则出错处理
//队头位置进1, 队头指针指示实际队头的前一//标志改0, 表示栈不满 //返回原队头元素的值
return Q[front];
}
读取队头元素函数
template
Type Queue
assert ( ! IsEmpty ( ) );
//判断队列是否不空,空则出错处理
//返回队头元素的值
return Q[(front + 1) % m];
(8)如果允许在循环队列的两端都可以进行插入和删除操作。要求: ① 写出循环队列的类型定义;
② 写出“从队尾删除”和“从队头插入”的算法。
[题目分析] 用一维数组 v[0..M-1]实现循环队列,其中M是队列长度。设队头指针 front和队尾指针rear,约定front指向队头元素的前一位置,rear指向队尾元素。定义front=rear时为队空,(rear+1)%m=front 为队满。约定队头端入队向下标小的方向发展,队尾端入队向下标大的方向发展。
(1)#define M 队列可能达到的最大长度 typedef struct
{ elemtp data[M]; int front,rear; } cycqueue;
(2)elemtp delqueue ( cycqueue Q)
//Q是如上定义的循环队列,本算法实现从队尾删除,若删除成功,返回被删除元素,
否则给出出错信息。
{ if (Q.front==Q.rear) {printf(“队列空”); exit(0);} Q.rear=(Q.rear-1+M)%M; //修改队尾指针。
return(Q.data[(Q.rear+1+M)%M]); //返回出队元素。 }//从队尾删除算法结束
void enqueue (cycqueue Q, elemtp x)
// 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)的非递归算法。 int Ack(int m,n)
{if (m==0) return(n+1);
else if(m!=0&&n==0) return(Ack(m-1,1)); else return(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)int Ackerman( int m, int n) {int akm[M][N];int i,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 //链表结点类 class ListNode { friend class List; private: }; class List { private: }; ListNode* List :: NewNode ( const int item ) { } void List :: NewList ( const int retvalue ) { cout << \; cin >> value; while ( value != retvalue ) { q = NewNode ( value ); //建立链表, 以输入retvalue结束 //提示 first = NULL; int value; ListNode *q; //输入 //输入有效 //建立包含value的新结点 ListNode *newnode = new ListNode (item); return newnode; //创建新链表结点 ListNode *first, current; int Max ( ListNode *f ); int Num ( ListNode *f ); float Avg ( ListNode *f, int& n ); List ( ) : first(NULL), current (NULL) { } ~List ( ){ } ListNode* NewNode ( const int item ); void NewList ( const int retvalue ); void PrintList ( ); //构造函数 //链表类 int data; //结点数据 //结点指针 ListNode *link; //定义在头文件\中 ListNode ( const int item ) : data(item), link(NULL) { } //构造函数 public: //析构函数 //创建链表结点, 其值为item //建立链表, 以输入retvalue结束 //输出链表所有结点数据 //求链表所有数据的最大值 //求链表中数据个数 //求链表所有数据的平均值 int GetMax ( ) { return Max ( first ); } int GetNum ( ) { return Num ( first ); } float GetAvg ( ) { return Avg ( first ); }