数据结构–循环队列的c语言实现(超详细注释/实验报告)

知识小回顾

队列(Queue)是另一种限定性的线性表,它只允许再表的一端插入元素,而再另一端删除元素,多以队列具有先进先出(First In First Out,FIFO)的特性。这与我们日常生活中的排队是一样的,最早进入队列的人最早离开,新来的人总是加入到队尾。在队列中,允许插入的一端称为队尾(Rear),允许删除的一端则称为队头(Front)。

队列在程序设计中也经常出现。一个最典型的例子就是操作系统中的作业排队。在允许多道程序运行的计算机系统中,同时有几个作业在运行。如果运行的结果都需要通过通道输出,那么就要按请求输出的先后次序排队。凡是申请输出的作业都从队尾进入队列。

循环队列是队列的一种顺序表示和实现方法。与顺序栈类似,在队列的顺序存储结构中,用一组地址连续的存储单元依次存放从队头到队尾的元素。此外,由于队列中队头和队尾的位置都是动态变化的,因此需要附设两个指针front和rear,分别知识队头元素和队尾元素在数组中的位置。

普通的顺序队列会有假溢出,一个巧妙的办法就是将顺序队列的数组看成一个环状的空间,即规定最后一个单元的后继为第一个单元,我们形象地称之为循环队列。

实验题目

实现循环队列基本运算

实验目的

  1. 掌握队列的逻辑结构和操作规则,能在相应的实际问题中正确选用。
  2. 熟练掌握循环队列基本运算的实现

实验要求

  1. 以循环队列作为存储结构;
  2. 实现循环队列的建立;
  3. 实现循环队列的入队运算;
  4. 实现循环队列的出队运算。

实验内容和实验步骤

1.需求分析

 以菜单的形式作为用户与程序的接口,用户输入菜单号来实行相应的操作。

2. 概要设计

 设计几个函数来实现初始化、插入、删除和查找的功能,然后再主函数中调用函数来实现操作。

3. 详细设计

导入一些库,并定义队列的大小以及队列中元素的类型。

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define MAXSIZE 50//队列最大长度
循环队列类型定义如下
typedef int QueueElementType;
typedef struct
{
    QueueElementType element[MAXSIZE];//队列的元素空间(一个数组)
    int front;//头指针(指示器)
    int rear;//尾指针(指示器)
}SeqQueue;

循环队列初始化操作
//循环队列初始化操作
SeqQueue*InitQueue()
{
    //将Q初始化为一个空的循环队列
    SeqQueue *Q;
    Q=(SeqQueue*)malloc(sizeof(SeqQueue));
    Q->front=Q->rear=0;//一开始两个指示器都在最前面
    return Q;
}
循环队列入队操作
  • 在非空循环队列中,队头指针始终指向当前队头元素,而队尾指针始终指向真正队尾与那苏后面的单元。当队列空间被占满时,队尾指针追上队头指针,所以有:front=rear。反之,队列是空的时候,队头指针追上队尾指针,此时也有:front=rear。可见,只凭front=rear无法判断队列是“满”还是“空”。解决这个问题的办法就是:损失一个元素,当队尾指针所指向的空单元的后继单元是队头元素所在的单元时,则停止入队。
//循环队列入队操作
void EnterQueue(SeqQueue *Q,QueueElementType x)
{
    //printf("入队开始\n");
    if((Q->rear+1)%MAXSIZE==Q->front)//牺牲了一个空间
    {
        printf("循环队列已满");
    }
    else
    {
        //printf("入队else开始\n");
        Q->element[Q->rear]=x;
        Q->rear=(Q->rear+1)%MAXSIZE;
    }
    //printf("入队结束\n");
}
循环队列出队操作
//循环队列出队操作
void DeleteQueue(SeqQueue *Q)
{
    if(Q->front==Q->rear)
    {
        printf("队列为空");
    }
    else
    {
        Q->front=(Q->front+1)%MAXSIZE;
    }
}
循环队列显示操作
//循环队列显示操作
void DisplayQueue(SeqQueue *Q)
{
    //printf("display开始\n");
    int i;
    for(i=Q->front;i!=Q->rear;i=(i+1)%MAXSIZE)
    {
        printf("%d   ",Q->element[i]);
    }
    //printf("display结束\n");
}

主函数部分,用一种“菜单”的形式使线性表的操作更加地清晰地展示出来。
在这里插入图片描述

//主函数
int main()
{
    SeqQueue *Q;
    //InitQueue(Q);
    Q=InitQueue();
    int a,i=1,x;
    for(a=1;a<5;a++)
    {
        EnterQueue(Q,a);
    }
    //DisplayQueue(Q);
    system("cls");
    while(i)//保证一直进行
    {
        printf("当前的循环队列如下(队首->队尾):\n");
        DisplayQueue(Q);
        printf("\n------------------------------------\n");
        printf("         Main Menu         \n");
        printf("    1   进队    \n");
        printf("    2   出队   \n");
        printf("    3   清屏   \n");
        printf("    0   结束程序   \n");
        printf("------------------------------------\n");
        printf("请输入你选择的菜单号<1, 2, 3, 0>:\n");
        scanf("%d",&i);
        switch(i)
        {
        case 1:
            printf("请输入进队元素:");
            scanf("%d",&x);
            EnterQueue(Q,x);
            printf("\n\n");
            break;
        case 2:
            DeleteQueue(Q);
            printf("\n\n");
            break;
        case 3:
            system("cls");
            break;
        case 0:
            exit(0);
            break;
        default:
            printf("输入有误~\n");
            break;
        }
    }
}

4. 调试分析

遇到的问题及解决方法
  • 教材上的初始化操作报错,用来实验指导书上的代码后就没有报错了。
算法的时空分析
  • 循环链表比较简单,都是依托着数组来实现的,所以整体难度不大,最多也就一层循环
实验结果

实验结果很不错,所有操作都能正常执行,并且自己加入了“清屏”选项,使得界面更加的整洁。

实验总结

循环链表比较简单,多多重复,百炼成钢!

最后附上完整的代码

#include<stdio.h>
#include<stdlib.h>
//#include<malloc.h>
#define MAXSIZE 50//队列最大长度
typedef int QueueElementType;
typedef struct
{
    QueueElementType element[MAXSIZE];//队列的元素空间(一个数组)
    int front;//头指针(指示器)
    int rear;//尾指针(指示器)
}SeqQueue;

//循环队列初始化操作
//void InitQueue(SeqQueue * Q)
SeqQueue*InitQueue()
{
    //将Q初始化为一个空的循环队列
    SeqQueue *Q;
    Q=(SeqQueue*)malloc(sizeof(SeqQueue));
    Q->front=Q->rear=0;//一开始两个指示器都在最前面
    return Q;
}

//循环队列入队操作
void EnterQueue(SeqQueue *Q,QueueElementType x)
{
    //printf("入队开始\n");
    if((Q->rear+1)%MAXSIZE==Q->front)//牺牲了一个空间
    {
        printf("循环队列已满");
    }
    else
    {
        //printf("入队else开始\n");
        Q->element[Q->rear]=x;
        Q->rear=(Q->rear+1)%MAXSIZE;
    }
    //printf("入队结束\n");
}

//循环队列出队操作
void DeleteQueue(SeqQueue *Q)
{
    if(Q->front==Q->rear)
    {
        printf("队列为空");
    }
    else
    {
        Q->front=(Q->front+1)%MAXSIZE;
    }
}

//循环队列显示操作
void DisplayQueue(SeqQueue *Q)
{
    //printf("display开始\n");
    int i;
    for(i=Q->front;i!=Q->rear;i=(i+1)%MAXSIZE)
    {
        printf("%d   ",Q->element[i]);
    }
    //printf("display结束\n");
}

//主函数
int main()
{
    SeqQueue *Q;
    //InitQueue(Q);
    Q=InitQueue();
    int a,i=1,x;
    for(a=1;a<5;a++)
    {
        EnterQueue(Q,a);
    }
    //DisplayQueue(Q);
    system("cls");
    while(i)//保证一直进行
    {
        printf("当前的循环队列如下(队首->队尾):\n");
        DisplayQueue(Q);
        printf("\n------------------------------------\n");
        printf("         Main Menu         \n");
        printf("    1   进队    \n");
        printf("    2   出队   \n");
        printf("    3   清屏   \n");
        printf("    0   结束程序   \n");
        printf("------------------------------------\n");
        printf("请输入你选择的菜单号<1, 2, 3, 0>:\n");
        scanf("%d",&i);
        switch(i)
        {
        case 1:
            printf("请输入进队元素:");
            scanf("%d",&x);
            EnterQueue(Q,x);
            printf("\n\n");
            break;
        case 2:
            DeleteQueue(Q);
            printf("\n\n");
            break;
        case 3:
            system("cls");
            break;
        case 0:
            exit(0);
            break;
        default:
            printf("输入有误~\n");
            break;
        }
    }
}
Logo

开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!

更多推荐