欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

循环队列的建立及基本操作-数据结构-C语言

程序员文章站 2022-03-08 19:00:10
...

实验项目名称:队列的建立及操作

一、 实验目的
1.掌握队列存储结构的表示和实现方法。
2.掌握队列的入队和出队等基本操作的算法实现。
二、 实验题
建立顺序循环队列,并在顺序循环队列上实现入队、出队基本操作。
三、 实验过程及结果
基本思路

  1. 建立顺序循环队列:
    定义一个结构体,成员有三个:数组、头指针(用来表示数组的下标,用于删除元素,即出队)、尾指针(用来表示数组的下标,用于插入元素,即入队)。
  2. 入队:
    需要判断队列是否满了,若不满,则可入队。
  3. 出队:
  4. 需要判断队列是否为空
  5. 思路:
    循环队列的引入:解决队列是假溢出的问题
    建立一个顺序队列,当rear+1=MAXQSIZE时,front有两种情况:
    (1) front=0
    此时是队列真溢出,即队列已满;
    (2) front不等于0
    此时队列是假溢出;
    解决方法:
    引入循环队列,当rear+1=MAXQSIZE时,rear指向数组下标为零的位置,再次利用没有元素的空间,front同理;
    由rear+1变为rear=0的方法:
    取模运算:(rear+1)%MAXQSIZE;
  6. 判断循环队列空和满的条件问题:
    循环队列的建立及基本操作-数据结构-C语言解决方案:
    (1) 另设一个标志元素,以区分队空,队满;
    (2) 另设一个变量,记录元素个数;
    (3)少用一个元素空间;
    解决方案(3)的实现:
    循环队列的建立及基本操作-数据结构-C语言
    全部程序代码:
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define MAXQSIZE 100
#define OVERFLOW 0
typedef int QElemType;
typedef int Status;
typedef struct
{
	QElemType *base;//动态分配数组空间 
	int front;//头指针,若队列不为空,指向队列头元素 
	int rear;//尾指针,若队列不为空,指向尾元素的下一个位置 
}SqQueue;
SqQueue Q;

//循环队列的初始化 
Status InitQueue(SqQueue &Q)
{
	Q.base=new QElemType[MAXQSIZE];//分配数组空间  
	/*Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType))*/ 
	if(!Q.base)exit(OVERFLOW);//存储分配失败 
	Q.front=Q.rear=0;
	return OK; 
}

//求队列的长度
int QueueLength(SqQueue Q)
{
	if(!Q.base)return ERROR;
	else
	return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
//入队
Status EnQueue(SqQueue &Q,int n)
{
	QElemType e;
	while(n)
	{
		if((Q.rear+1)%MAXQSIZE==Q.front)return ERROR;//队满
		scanf("%d",&e);
	    Q.base[Q.rear]=e;//新元素加入队尾 
	    Q.rear=(Q.rear+1)%MAXQSIZE;//队尾指针加一 
	    n--;
	}
	return OK;
}
//出队
Status DeQueue(SqQueue &Q,int n)
{
	QElemType e;
	if(n<0||n>QueueLength(Q))return ERROR;//出队元素个数不合理 
	while(n)
	{
		if(Q.rear==Q.front)return ERROR;//队空
	    e=Q.base[Q.front];//将此时头元素的值赋给e
	    printf("The DeQueue element is %d\n",e);
	    Q.front=(Q.front+1)%MAXQSIZE;
	    //头指针的值加一
		/*当头指针(Q.front+1)==MAXQSIZE时,如果直接取模运算,则可指向下标为零的位置
		构成一个循环队列*/  
	    n--;
	}
	
	return OK; 
}
//取队头元素
QElemType GetHead(SqQueue Q)
{
	if(Q.rear!=Q.front)//队列不为空 
	return Q.base[Q.front];//直接返回队头指针所指向的元素的值,队头指针不变 
}
//主函数测试
int main()
{
	QElemType e;
	int x,y; 
	if(InitQueue(Q))
	printf("InitQueue success\n");
	printf("请输入入队的元素个数:\n");
	scanf("%d",&x);
	if(EnQueue(Q,x))
	printf("EnQueue success\n");
	printf("The head Element is %d\n",GetHead(Q));
    printf("The length of Queue element is %d\n",QueueLength(Q));
	printf("请输入出队的元素个数:\n");
	scanf("%d",&y);
	if(DeQueue(Q,y));
	printf("DeQueue success\n");
	return 0;	
 }

实验结果:
循环队列的建立及基本操作-数据结构-C语言

相关标签: 队列