2024年4月11日发(作者：)

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)

{ //出队