4.5习题与上机操作
⒈选择题
⒉填空题
⑴队尾队头
⑵  b
⑶(rear-front+m)%m
⑷L->front = = L->rear
⑸p = (QueueNode *) malloc (sizeof ( QueueNnode ) )；
p->data=x; p->next=NULL; q->rear->next=p; q->rear=p;
⒊程序设计题
⑴假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag，以tag = = 0和tag = = 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为"空"还是"满"。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。
解：
循环队列的数据结构定义：
typeded struct
{int rear, front, tag; //队尾指针、队头指针和队满标志
Elemtype Q[m]; //存放队列元素的数组，队列最大可容纳元素个数为m
} CirQueue
插入函数
int EnQueue ( CirQueue *q, Elemtype x )
{ if (q->tag=1 )
{ printf (＂队满＂);
return (FALSE ); /队满不能入队
}
else
{q->rear = ( q->rear + 1 ) % m; //队尾位置进1, 队尾指针指示实际队尾位置q->Q[q->rear] = x; //进队列
if (q->rear=q->front) tag = 1; //标志改1，表示队列满
return (TRUE);
}
}
删除函数
int DeQueue ( CirQueue *q , Elemtype *x )
{ if (q->tag=0 )
{ printf(＂队空＂)；
return (FALSE ); //队空不能出队
}
else
{ q->front = ( q->front + 1 ) % m;
//队头位置进1, 队头指针指示实际队头的前一位置
*x = q->data[q->front]; //读出队头元素
if (q->rear=q->front) tag = 0; //标志改0，表示队列空
return (TRUE);
}
}
⑵假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空、入队和出队等算法。
解：算法如下：
//先定义链队结构:
typedef struct queuenode{
Elemtype data;
struct queuenode *next;
}QueueNode; //以上是结点类型的定义
typedef struct{
queuenode *rear;
}LinkQueue; //只设一个指向队尾元素的指针
//linkQ.h 相应算法
void InitQueue( LinkQueue *Q)
{ //置空队：就是使头结点成为队尾元素
Q->rear = Q->rear->next;//头结点成为尾结点
Q->rear->next = Q->rear;//形成循环链表
}
int EmptyQueue( LinkQueue *Q)
{ //判队空
//当头结点的next指针指向自己时为空队
return Q->rear->next->next==Q->rear->next;
}
void EnQueue( LinkQueue *Q, Elemtype x)
{ //入队
//也就是在尾结点处插入元素
QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode));//申请新结点
p->data=x; p->next=NULL;//初始化结点
Q-rear->next->next=p; // 将新结点链入
p->next=Q->rear; //形成循环链表
Q->rear=p;//将尾指针移至新结点
}
Elemtype DeQueue( LinkQueue *Q)
{ //出队
/
/把头结点之后的元素摘下
Elemtype t;
QueueNode *p;
if(EmptyQueue( Q ))
Error("Queue underflow");
p=Q->rear->next->next; //将要摘下的结点
x=p->data; //保存结点中数据
Q->rear->next->next=p->next;//摘下结点p
free(p);//释放被删结点
return x;
}
⑶假设循环队列中只设rear和quelen 来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素
解：知道了尾指针和元素个数，当然就能知道队头元素了。算法如下：
int FullQueue( CirQueue *Q)
{
//判队满，队中元素个数等于空间大小
return Q->quelen==QueueSize;
}
void EnQueue( CirQueue *Q, Elemtype x)
{
// 入队
if(FullQueue( Q))
Error("队已满，无法入队");
Q->data[Q->rear]=x;
Q->rear=(Q->rear+1)%QueueSize;//在循环意义上的加1
Q->quelen++;
}
Elemtype DeQueue( CirQueue *Q)
{
//出队
if(Q->quelen==0)
Error("队已空，无元素可出队");
int tmpfront; //设一个临时队头指针
if(Q->rear > Q->quelen)//计算头指针位置
tmpfront=Q->rear - Q->quelen;
else
tmpfront=Q->rear + QueueSize - Q->quelen;
quelen--;
return Q->data[tmpfront];
}
⑷一个双端队列是限定在两端都可以进行插入删除的线性表。若将一个双端队列顺序表示在一维数组V[m]中，两个端点设为end1和end2，并组织成一个循环队列。试写出双端队列所用指针end1和end2的初始化条件及队空与队满条件，并编写基于此结构的相应的插入(enqueue)新元素和删除(dlqueue)算法。
解：
初始化条件end1 = end2 = 0;
队空条件end1 = end2;
队满条件( end1 + 1 ) % m = end2;
//设end1端顺时针进栈，end2端逆时针进栈
循环队列的数据结构定义：
typeded struct
{int end1, end2; //队列两端的指针
Elemtype V[m]; //存放队列元素的数组，队列最大可容纳元素个数为m
} DoubleQueue
插入函数
int EnQueue (DoubleQueue *q, int end )
{ if ((q->end1+1)%m=q->end2)
return ( FLASE); //队满，无法入队
if ( end = = 1 )
{ end1 = ( end1 + 1 ) % m; //end1端指针先进1, 再按指针进队列
q->V[q->end1] = x; //end1指向实际队头位置
return (TRUE);
}
else
{ q->V[q->end2] =x; //end2端先进队列, 指针再进1
end2 = ( end2 - 1 + m ) % m; //end2指向实际队头的下一位置
return (TRUE);
}
}
删除函数
int DeQueue ( DoubleQueue *q, int end, Elemtype *x )
{ if (q->end1=q->end2)
return ( Flase); //队空，无法出队
if ( end = = 1 )
{ *x= q->V[q->end1]; //先保存原队头元素的值, end1端指针退1
q->end1 = ( q->end1 + m - 1 ) % m;
}
else
{ q->end2 = ( q->end2 + 1 ) % m;
*x = q->V[q->end2]; //end2端指针先退1。再保存原队头元素的值
}
}
读取队头元素的值
Elemtype GetFront (int end )
c语言中struct{ if (q->end1=q->end2)
return ; //队空
if ( end = = 1 )
return q->V[q->end1]; //返回队头元素的值
else
return q->V[(q->end2+1) % m];
}
⒋操作题
⑴设用链表表示一个双端队列，要求可在表的两端插入，但限制只能在表的一端删除。试编写基于此结构的队列的插入(enqueue)和删除(dequeue)算法，并给出队列空和队列满的条件。
解：
链式队列的结点类型描述如下：
typedef struct queuenode //结点结构
{ Elemtype data;
struct queuenode *next;
}QueueNode;
为了强调队头和队尾是队列的属性，将队列封装，引入链式队列类型：
typedef struct
{ QueueNode *end1, *end2; //end1在链头, 可插可删; end2在链尾, 可插不可删}LinkDQueue;
队列的插入函数
int EnDoubleQueue1 ( LinlDQueue *q, Elemtype x ) //从队列end1端插入
{ QueueNode *p;
p = (QueueNode *) malloc (sizeof ( QueueNnode ) ); //申请新结点
if (p = = NULL)
{ printf ( “Out of space!\n”);
return (FALSE );
}
else
{ p->data=x; p->next=q->end1->next;
q->end1->next=p;
if (q->end1 = = q->end2)
q->end2=p;
return (TRUE );
}
}
int EnDoubleQueue2 (LinlDQueue *q, Elemtype x) //从队列end2端插入
{ QueueNode *p;