4.5 习题与上机操作
⒈ 选择题
⑴ C ⑵ Ａ ⑶ Ａ ⑷ Ｂ ⑸ Ｂ
⒉ 填空题
⑴ 队尾 队头 ⑵ 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 ) { 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;
p = (QueueNode *) malloc (sizeof ( QueueNnode ) ); //申请新结点 if (p = = NULL)
{ printf ( “Out of space!\\n”); return (FALSE ); } else {
p->data=x; p->next=NULL; q->end2->next=p; q->end2=p; return (TRUE ); }
}
算法4.10
int OutQueue_Link ( LinkQueue *q , Elemtype *x) { QueueNnode *p;
if ( isEmpty_LinkQueue (q) )
{ printf (＂队空＂)；
return (FALSE);
} //队空，出队失败 else
{ p = q->front->next;
q->front->next=p->next;
*x=p->data ; //队头元素放x中 free ( p );
if (q->end1->next = = NULL) q->end2=q->end1;
//只有一个元素时，出队后队空 return (TRUE ); } }
队列的删除函数
int DeDoubleQueue (LinkQueue *q , Elemtype *x) { if (q->end1 = = q->end2)
return (FLASE) // 队列空, 不能删除 else
{ p = q->end1->next;
q->end1->next=p->next;
*x=p->data ; //队头元素放x中 free ( p );
if (q->end1->next = = NULL) q->end2=q->end1;
//只有一个元素时，出队后队空 return (TRUE ); }
}
⑵ 舞伴问题：假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。
提示：先入队的男士或女士亦先出队配成舞伴。因此该问题具体有典型的先进先出特性，可用队列作为算法的数据结构。在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列
构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他（或她）将是下一轮舞曲开始时第一个可获得舞伴的人。
具体算法及相关的类型定义 typedef struct { char name[20];
char sex; //性别，'F'表示女性，'M'表示男性 }Person;
typedef Person ElemType; //将队列中元素的数据类型改为Person void DancePartner (Person dancer[],int num)
{ //结构数组dancer中存放跳舞的男女，num是跳舞的人数。 int i; Person p;
CirQueue Mdancers,Fdancers;
InitQueue(&Mdancers); //男士队列初始化 InitQueue(&Fdancers);//女士队列初始化 for(i=0;i{ //依次将跳舞者依其性别入队 p=dancer; if(p.sex=='F')EnQueue(&Fdancers.p); //排入女队 else
EnQueue(&Mdancers.p); /排入男队 }
printf(\"The dancing partners are: \\n \\n\");
while(!QueueEmpty(&Fdancers)&&!QueueEmpty(&Mdancers)) { //依次输入男女舞伴名
p=DeQueue(&Fdancers); //女士出队 printf(\"%s \打印出队女士名 p=DeQueue(&Mdancers); //男士出队 printf(\"%s\\n\打印出队男士名 }
if(!QueueEmpty(&Fdancers))
{ //输出女士剩余人数及队头女士的名字
printf(\"\\n There are %d women waitin for the next round.\\n\ p=QueueFront(&Fdancers); //取队头
printf(\"%s will be the first to get a partner. \\n\ } else
if(!QueueEmpty(&Mdancers))
{//输出男队剩余人数及队头者名字
printf(\"\\n There are%d men waiting for the next round.\\n\ p=QueueFront(&Mdancers);
printf(\"%s will be the first to get a partner.\\n\
}
}//DancerPartners
