解题思路:
看注释
注意事项:
看注释
参考代码:
#include<stdio.h>
#include<stdlib.h> //同于动态内存分配
typedef int ElemType; //用ElemType代替int便于更改元素类型
typedef struct QNode
{
ElemType data;
struct QNode *next;
}QNode,*QList;
typedef struct Queue
{
QList front; //队首
QList rear; //队尾
int max_len; //最大长度
}Queue;
//函数声明
int InitQueue(Queue *Q,int n);
int LengthQueue(Queue *Q);
int enQueue(Queue *Q,ElemType e);
int deQueue(Queue *Q, ElemType *e);
int EmptyQueue(Queue *Q);
int FullQueue(Queue *Q);
int exist(Queue *Q,ElemType v);
void deleteQueue(Queue *Q,ElemType u);
int deleteRear(Queue *Q);
void print(Queue *Q);
//初始化队列
int InitQueue(Queue *Q,int n)
{
Q->front=Q->rear=NULL;
Q->max_len=n; //记录队列最大长度
return 1;
}
//计算队列长度
int LengthQueue(Queue *Q)
{
int count=0;
QList pre=Q->front; //从队首开始遍历
while(pre!=NULL)
{
count++;
pre=pre->next;
}
return count; //得到队列长度
}
//入队
int enQueue(Queue *Q,ElemType e)
{
if(FullQueue(Q)) //判断队满（可有可无），因为入队前将会先对队列进行调整，队列一定不为满
return 0;
QList pre=(QList)malloc(sizeof(QNode)); //新加入的节点
if(!pre)
return 0;
pre->data=e;
pre->next=Q->front; //放在首位
if(EmptyQueue(Q))
{
Q->rear=pre; //若队列为空，则为节点也指向新加入的节点
}
Q->front=pre; //首节点指向pre（即队首）
return 1;
}
//出队
int deQueue(Queue *Q, ElemType *e)
{
if (EmptyQueue(Q)) return 0;
QList pre = Q->front; //从队首出队
*e = pre->data;
if (Q->front == Q->rear)
{
Q->front = Q->rear = NULL;
}
else
{
Q->front = Q->front->next; //往后遍历
}
free(pre); //释放已出队的元素
return 1;
}
//判断队列是否为空
int EmptyQueue(Queue *Q)
{
if(Q->front==NULL&&Q->rear==NULL) //首位皆为空则队为空
return 1;
else
return 0;
}
//判断队列是否已满
int FullQueue(Queue *Q)
{
return LengthQueue(Q)==Q->max_len; //队列长度等于最大长度即为队满
}
//判断元素是否已经存在于队列中
int exist(Queue *Q,ElemType v) //从头到尾遍历查找
{
QList pre=Q->front;
while(pre)
{
if(v==pre->data)
{
return 1;
}
pre=pre->next;
}
return 0;
}
//删除队列中已存在的相同元素
void deleteQueue(Queue *Q,ElemType u)
{
if (Q->front == NULL) return ; //队列为空，直接return，void函数无返回值（该步骤可有可无，因为该题目删除相同元素则确认队列不为空）
QList pre=NULL,p=Q->front;
if(p->data==u)
{
Q->front=p->next;
if (p == Q->rear) //如果只有一个元素，将尾节点置空，前一步操作首节点已置空
{
Q->rear = NULL;
}
free(p); //释放节点内存
return ; //结束
}
while(p)
{
pre=p;
p=p->next;
if(p!=NULL&&p->data==u)
{
pre->next=p->next;
if (p == Q->rear) // 若删除的是队尾元素，更新队尾指针
{
Q->rear = pre;
}
free(p);
return ;
}
}
}
//队满时删除队尾元素
int deleteRear(Queue *Q)
{
if(EmptyQueue(Q)) //可有可无，原因同上，使用函数时队列确定不为空
return 0;
QList pre=Q->front,p=Q->rear;
int t=p->data;
if (Q->front == Q->rear) //若队列只有一个元素，直接释放内存，并首尾置空
{
free(p);
Q->front = Q->rear = NULL;
}
else //队列为多个元素
{
while(pre->next!=Q->rear) //遍历找到尾节点前一个节点
{
pre=pre->next;
}
Q->rear=pre; //尾节点前移
pre->next=NULL; //尾节点指针域置空
free(p); //释放原来的尾节点
}
return t; //因为从q1中删除的可能要插入q2中，所以用返回保存数据以便插入
}
//输出队列元素
void print(Queue *Q)
{
while(Q->front!=NULL)
{
ElemType e;
deQueue(Q,&e); //采用出队并打印的方式
printf("%d ",e);
}
printf("\n"); //记得换行，或者在主函数书写
}
int main()
{
Queue q1,q2;
int n1,n2,m,e;
scanf("%d%d",&n1,&n2);
scanf("%d",&m);
InitQueue(&q1,n1);
InitQueue(&q2,n2);
while(m--)
{
scanf("%d",&e);
//用inQ1，inQ2表示元素e在q1，q2中，方便后面使用
int inQ1 = exist(&q1, e);
int inQ2 = exist(&q2, e);
if(!inQ1&&!inQ2) //既不在q1又不在q2
{
if(FullQueue(&q2)) //如果q2满了，先删除尾节点
deleteRear(&q2);
enQueue(&q2,e); //在队首插入
}
else
{
if(inQ1) //如果已在q1，删除原来位置的，放在队首
{
deleteQueue(&q1,e);
enQueue(&q1,e);
}
else //在已q2，删除原来的，插入q1首位
{
deleteQueue(&q2,e);
if(FullQueue(&q1)) //若q1是满的
{
int m=deleteRear(&q1); //删除q1队尾并记录元素，将该元素插入q2
enQueue(&q2,m); //这里无需判断q2是否为满，因为上一步删除了已在q2的相同元素，q2一定不为满
enQueue(&q1,e); //新元素插入q1首位
}
else //若q1不满则直接插入
{
enQueue(&q1,e);
}
}
}
}
//输出两个队列的元素
print(&q1);
print(&q2);
return 0;
}
0.0分
0 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复