第一关
#include <stdio.h>
#include <stdlib.h>
#include "SeqQueue.h"
SeqQueue* SQ_Create(int maxlen)
// 创建顺序队列, 队列最多存储maxlen个队列元素。
{
SeqQueue* sq=(SeqQueue*)malloc(sizeof(SeqQueue));
sq->data=(T*)malloc(sizeof(T)*(maxlen+1));
sq->front=sq->rear=0;
sq->max=maxlen+1;
return sq;
}
void SQ_Free(SeqQueue* sq)
// 释放队列空间,以删除队列。
{
free(sq->data);
free(sq);
}
void SQ_MakeEmpty(SeqQueue* sq)
// 将队列置空。
{
sq->front=0;
sq->rear=0;
}
bool SQ_IsEmpty(SeqQueue* sq)
// 判断队列是否为空,为空返回true,否则返回false。
{
// 请在Begin-End之间补充代码,完成队列是否为空的判断。
/********** Begin *********/
return sq->front == sq->rear;//当front与rear相等时,队列为空。
/********** End **********/
}
bool SQ_IsFull(SeqQueue* sq)
// 判断队列是否为满。为满返回true,否则返回false。
{
// 请在Begin-End之间补充代码,完成队列是否为满的判断。
/********** Begin *********/
if((sq->rear+1)%(sq->max)==(sq->front))
return true;
/********** End **********/
}
int SQ_Length(SeqQueue* sq)
// 队列长度。
{
// 请在Begin-End之间补充代码,获取队列长度。
/********** Begin *********/
return (sq->rear-sq->front+sq->max)%sq->max;
/********** End **********/
}
bool SQ_In(SeqQueue* sq, T x)
// 将x入队。若入队失败(队列满),则返回false,否则返回true。
{
// 请在Begin-End之间补充代码,将 x 入队。
/********** Begin *********/
if((sq->rear+1)%sq->max==sq->front)
return false;
T* head=sq->data;
head[sq->rear]=x;//新元素插入队尾
sq->rear=(sq->rear+1)%sq->max;//队尾指针加1
/********** End **********/
}
bool SQ_Out(SeqQueue* sq, T& item)
// 从队列sq出队一个元素,返回时item为出队的元素的值。若出队成功(队列不为空),则返回true,否则(队列空),返回false,此时item不会返回有效值。
{
// 请在Begin-End之间补充代码,完成元素出队操作。
/********** Begin *********/
if(sq->front==sq->rear) return false;
T*head=sq->data;//做的时候出错的地方
item=head[sq->front];//保留队头的元素
sq->front=(sq->front+1)%sq->max;//很容易遗漏的一点,队头指针需要加1
return true;
/********** End **********/
}
bool SQ_Head(SeqQueue* sq, T& head)
// 获取队列头结点元素,返回时head保存头结点元素。
// 若获取失败(队列空),则返回值为false,否则返回值为true。
{
if ( SQ_IsEmpty(sq) ){
return false;
}
else {
head = sq->data[sq->front];
return true;
}
}
void SQ_Print(SeqQueue* sq)
// 依次打印出队列中的每个元素。
{
int i=sq->front;
if (SQ_IsEmpty(sq)) {
printf("queue is emtpy");
return;
}
for (i=sq->front; i!=sq->rear; i=(i+1)%sq->max) {
printf("%d ", sq->data[i]);
}
printf("\n");
}
第二关
// 队列的链接存储实现文件。
// 采用循环链表,具有附加头节点,使用尾结点指针。
// CLQ_ Circularly Linked Queue
#include <stdio.h>
#include <stdlib.h>
#include "CLnkQueue.h"
LNode* CLQ_Create()
// 创建一个队列。
{
LNode* rear=(LNode*)malloc(sizeof(LNode));
rear->data = 0;
rear->next = rear;
return rear;
}
void CLQ_Free(LNode* rear)
// rear指向尾结点。
{
CLQ_MakeEmpty(rear);
free(rear);
}
void CLQ_MakeEmpty(LNode* & rear)
// rear指向尾结点。
// 将队列变为空队列。
{
T item;
while(!CLQ_IsEmpty(rear))
CLQ_Out(rear,item);
}
bool CLQ_IsEmpty(LNode* rear)
// 判断队列是否为空。
{
// 请在Begin-End之间补充代码,完成队列是否为空的判断。
/********** Begin *********/
return rear==rear->next;
/********** End **********/
}
int CLQ_Length(LNode* rear)
// 返回队列长度,rear指向尾结点。
{
// 请在Begin-End之间补充代码,获取队列长度。
/********** Begin *********/
return rear->next->data;
/********** End **********/
}
void CLQ_In(LNode* & rear, T x)
// 入队列, 新结点加入链表尾部。rear指向尾结点。
{
// 请在Begin-End之间补充代码,完成新结点入队操作。
/********** Begin *********/
LNode*newNode=new LNode;
newNode->data=x;
newNode->next=rear->next;
rear->next=newNode;
rear=newNode;
rear->next->data++;//为输出做准备
/********** End **********/
}
bool CLQ_Out(LNode* & rear, T& item)
// 出队列。空队列时,返回值为false。rear指向尾结点。
{
// 请在Begin-End之间补充代码,完成结点出队操作。
/********** Begin *********/
if(CLQ_IsEmpty(rear)) return false;
else if(rear->next->data==1)
{
rear=rear->next;
rear->next=rear;
rear->data--;
}
else
{
LNode* addNode=rear->next;
addNode->next=addNode->next->next;
addNode->data--;
return true;
}
/********** End **********/
}
bool CLQ_Head(LNode* rear, T& item)
// rear指向尾结点。
// 获取队列头。空队列时返回值为false。
{
if (CLQ_IsEmpty(rear))
return false;
item = rear->next->next->data;
return true;
}
void CLQ_Print(LNode* rear)
// 打印队列。
{
if (CLQ_IsEmpty(rear)) {
printf("The queue is: empty. \n");
return;
}
LNode* node=rear->next->next;
do {
printf("%d ", node->data);
node = node->next;
} while (node != rear->next);
//printf("\n");
}