ZZU的学弟学妹们不要抄作业哦~(｀Д)
一、实验目的
1．掌握队列存储结构的表示和实现方法。
2．掌握队列的入队和出队等基本操作的算法实现。
3．了解队列在解决实际问题中的简单应用。
二、实验内容
1．建立顺序循环队列，并在顺序循环队列上实现入队、出队基本操作。
2．建立循环链队列，并在循环链队列上实现入队、出队基本操作（选做）。
三、实验要求
1．建立顺序循环队列，并在顺序循环队列上实现入队、出队基本操作。
（1）根据输入的队列长度n和各元素值建立一个循环顺序表表示的队列（循环队列），并输出队列中各元素值。
（2）将数据元素e入队，并输出入队后的队列中各元素值。
（3）将循环队列的队首元素出队，并输出出队元素的值和出队后队列中各元素值。
2．编程实现对循环链队列的入队和出队操作。
（1）根据输入的队列长度n和各元素值建立一个带头结点的循环链表表示的队列（循环链队列），并且只设一个尾指针来指向尾结点，然后输出队列中各元素值。
（2）将数据元素e入队，并输出入队后的队列中各元素值。
（3）将循环链队列的队首元素出队，并输出出队元素的值和出队后队列中各元素值。
四、详细程序清单
//1.顺序循环队列
#include<stdio.h>
#include<stdlib.h>
#define MAXQSIZE 100
typedef struct{
int *base;
int front;
int rear;
}SqQueue;
SqQueue Q;
int Create(SqQueue &Q,int n) //创建
{
int e;
Q.base=(int *)malloc(MAXQSIZE*sizeof(int));
if(n>MAXQSIZE-1)
{
printf("超出最大值\n");
return 0;
}
Q.front=Q.rear=0;
printf("输入队列的元素: \n");
for(Q.rear=0;Q.rear<n;Q.rear++)
{
scanf("%d",&e);
Q.base[Q.rear]=e;
}
}
int Show(SqQueue Q)//显示
{
printf("当前顺序队列元素为： ");
if (Q.front==Q.rear)
{
printf("队列为空\n");
return 0;
}
int p;
p=Q.front;
while (p!=Q.rear)
{
printf("%d ",Q.base[p%MAXQSIZE]);
p++;
}
printf("\n");
}
int EnQueue(SqQueue &Q, int e)//入队列
{
if((Q.rear+1)%MAXQSIZE==Q.front)
{
printf("队列满\n");
return 0;
}
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXQSIZE;
}
int DeQueue(SqQueue &Q)//出队列
{
int e;
if (Q.front==Q.rear)
{
printf("队列为空\n");
return 0;
}
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
printf("出队列元素为： %d\n",e);
}
int main()
{
int select,e,n;
printf("1.创建队列\t2.入队列\t3.出队列\t4.退出\n");
while(1)
{
printf("选择操作： ");
scanf("%d",&select);
switch(select)
{
case 1:
printf("输入队列的长度（小于%d）: ",MAXQSIZE);
scanf("%d",&n);
Create(Q,n);
Show(Q);
break;
case 2:
printf("输入入队列元素： ");
scanf("%d",&e);
EnQueue(Q,e);
Show(Q);
break;
case 3:
DeQueue(Q);
Show(Q);
break;
case 4:
return 0;
default:
printf("输入错误\n");
break;
}
}
return 0;
}
//2.链循环队列（头结点为空）
#include<stdio.h>
#include<stdlib.h>
typedef struct QNode{
int data;
struct QNode *next;
}QNode,*LinkQueue;
LinkQueue rear,head;//尾指针和头结点，这里没有用front而是head，因为这里的头结点不是动态的，而是固定的，用head以区分顺序循环队列的front
int EnQueue(int e)//入队列
{
LinkQueue p;
p=(LinkQueue)malloc(sizeof(QNode));
p->data=e;
rear->next=p;
rear=p;
rear->next=head;
}
int Create(int n)//创建
{
LinkQueue p;
int e;
head=(LinkQueue)malloc(sizeof(QNode));
rear=head;
head->next=rear;
rear->next=head;
rear->data=head->data=NULL;
printf("输入队列元素： ");
while(n--)
{
scanf("%d",&e);
EnQueue(e);//这里直接调用入队函数了，代码是一样的
}
}
int Show()//显示
{
LinkQueue p;
printf("当前队列元素为： ");
p=head->next;
if(head==rear)//队列为空时
{
printf("队列为空\n");
return 0;
}
for (;p!=rear;p=p->next)
{
printf("%d ",p->data);
}
printf("%d\n",p->data);
}
int DeQueue()//出队列
{
int e;
LinkQueue p;
p=head->next;
e=p->data;
if(head==rear)//队列为空时
{
printf("队列为空\n");
return 0;
}
head->next=head->next->next;
if(head->next==head)
{
rear=head;
}
free(p);
printf("出队列元素为： %d\n",e);
}
int main()
{
int select,e,n;
printf("1.创建队列\t2.入队列\t3.出队列\t4.退出\n");
while(1)
{
printf("选择操作： ");
scanf("%d",&select);
switch(select)
{
case 1:
printf("输入队列的长度： ");
scanf("%d",&n);
Create(n);
Show();
break;
case 2:
printf("输入入队列元素： ");
scanf("%d",&e);
EnQueue(e);
Show();
break;
case 3:
DeQueue();
Show();
break;
case 4:
return 0;
default:
printf("输入错误\n");
break;
}
}
return 0;
}
五、程序运行结果
1.顺序循环队列：
2.链循环队列
六、实验心得体会
1.通过这次的操作，我对顺序队列中的“假上溢”有了更好的理解，让顺序队列进行循环操作可以防止“假上溢”；
2.但是对于链循环队列，我不明白为什么要让它循环，因为链队列不存在“上溢”的情况，而且队列只能尾进头出，不能像链表一样在任意位置插入新元素，所以我觉得让链队列进行循环操作好像没有意义？？
3.链队列的头指针我用的是head而不是front，因为这里的头结点不是动态的，而是固定的，用head以区分顺序循环队列的动态头结点front；
4.链队列的头结点我没有赋值，是空的。开始的时候是想把头结点也赋值的，但是这样会出现很多问题：创建、入队、判空、全部出队后的重新入队都很麻烦，于是为了方便头结点没有赋值；
5.之前几次实验的运行结果看起来太乱，这次我给改简洁了；
6.错误很多，调试很烦，要有耐心。
| 
转播
