队列的基本操作的实现

2023-12-16 14:31:34

队列的基本操作的实现

实验目的
熟练掌握队列的抽象数据类型，能在相应的应用问题中正确选用它，熟练掌握队列的实现方法（顺序和链式），两种存储结构和基本操作的实现算法，注意空和满的判断条件及它们的描述方法，掌握循环队列与其它顺序结构实现上的不同及解决办法，熟悉各种队列的基本操作在循环队列上的实现
实验内容
实现以下菜单功能，根据用户的选择调用以上各函数，检验基本操作的正确性，以备后用。除了初始化和销毁操作外，其它7个队列基本操作以及“退出”分别对应一个菜单项。初始化队列后出现该菜单，根据用户选择执行对应的队列操作，并显示结果。可循环出现菜单，直到用户选择“退出”为止，此时销毁队列，结束。
数据结构定义
我设置了一个队列，队列中的一个每个节点为：Qnode，里面有一个只想Qnode 的指针，还存有有个rear，以及front作为指针。队列是一种先进先出的数据结构，可以使用静态存储的线性结构，也可以采用单链表来进行存储。
算法思想及算法设计
先设计一个菜单界面，这个界面里可以调用各个其他部分的函数，提供各个函数的接口，便于之后的调用。对于每个函数的调用，具体算法如下：

Status InitQueue(Queue &q)
{
   if (!q.base)
       free(q.base);
   q.base = new Elemtype[maxsize];
   if (!q.base)
       exit(OVERFLOW);
   q.front = q.rear = 0;
   return OK;
}
Status DestrotQueue(Queue &q)
{
   q.rear = q.front = 0;
   delete q.base;
   q.base = NULL;
   return OK;
}
Status ClearQueue(Queue &q)
{
   q.rear = q.front = 0;
   return OK;
}
Status QueueEmpty(Queue q)
{
   if (q.front == q.rear)
       return OK;
   else
       return FALSE;
}
Status QueueLength(Queue q)
{
   return (q.rear - q.front + maxsize) % maxsize; //学会如何找到元素个数
}
Status GetHead(Queue q, Elemtype &e)
{
   if (QueueEmpty(q))
       return FALSE;
   e = q.base[q.front];
   return OK;
}
Status EnQueue(Queue &q, Elemtype &e)
{
   if (q.front == (q.rear + 1) % maxsize)
       return OVERFLOW;
   q.base[q.rear] = e; //考虑到闭环的情况
   q.rear = (q.rear + 1) % maxsize;
   return OK;
}
Status Dequeue(Queue &q, Elemtype &e)
{
   if (QueueEmpty(q))
       return FALSE;
   e = q.base[q.front];
   q.front = (q.front + 1) % maxsize;
   return OK;
}
Status visit(Elemtype e)
{
   printf(" %d", e);
   return OK;
}

Status QueueTraverse(Queue Q, Status (*visit)(Elemtype e))
{

   for (int i = Q.front; i != Q.rear; i = (i + 1) % maxsize)
   {
       visit(Q.base[i]);
   }
   printf("\n");

   return OK;
}

实验代码

#include <iostream>
#include "queue.hpp"
#include "constants.h"
void pt(Queue &Q);
using namespace std;
Status InitQueue(Queue &q)
{
   if (!q.base)
       free(q.base);
   q.base = new Elemtype[maxsize];
   if (!q.base)
       exit(OVERFLOW);
   q.front = q.rear = 0;
   return OK;
}
Status DestrotQueue(Queue &q)
{
   q.rear = q.front = 0;
   delete q.base;
   q.base = NULL;
   return OK;
}
Status ClearQueue(Queue &q)
{
   q.rear = q.front = 0;
   return OK;
}
Status QueueEmpty(Queue q)
{
   if (q.front == q.rear)
       return OK;
   else
       return FALSE;
}
Status QueueLength(Queue q)
{
   return (q.rear - q.front + maxsize) % maxsize; //学会如何找到元素个数
}
Status GetHead(Queue q, Elemtype &e)
{
   if (QueueEmpty(q))
       return FALSE;
   e = q.base[q.front];
   return OK;
}
Status EnQueue(Queue &q, Elemtype &e)
{
   if (q.front == (q.rear + 1) % maxsize)
       return OVERFLOW;
   q.base[q.rear] = e; //考虑到闭环的情况
   q.rear = (q.rear + 1) % maxsize;
   return OK;
}
Status Dequeue(Queue &q, Elemtype &e)
{
   if (QueueEmpty(q))
       return FALSE;
   e = q.base[q.front];
   q.front = (q.front + 1) % maxsize;
   return OK;
}
Status visit(Elemtype e)
{
   printf(" %d", e);
   return OK;


Status QueueTraverse(Queue Q, Status (*visit)(Elemtype e))
{

   for (int i = Q.front; i != Q.rear; i = (i + 1) % maxsize)
   {
       visit(Q.base[i]);
   }
   printf("\n");

   return OK;
}

void hanshu2(Queue &q)
{
   printf("请输入要入队的元素\n");
   int x;
   scanf("%d", &x);
   EnQueue(q, x);
}
void hanshu3(Queue &Q)
{
   int e;
   Dequeue(Q, e);
   printf("出队的元素为：%d\n", e);
}
Status init(Queue &Q)
{
   int num = 0;

   do
   { //使用dowhile循环
       printf("菜单\n");
       printf("1----初始化队列\n");
       printf("2----入队\n");
       printf("3----出队\n");
       printf("4----求出队头元素\n");
       printf("5----求出队的长度\n");
       printf("6----销毁队列\n");
       printf("7----清空队列\n");
       printf("8----判断队时是否为空\n");
       printf("9----对队列进行遍历操作\n");
       printf("0----退出\n");
       scanf("%d", &num);
       switch (num)
       {
       case 1:
           InitQueue(Q);
           break;
       case 2:
           hanshu2(Q);
           break;
       case 3:
           hanshu3(Q);
           break;
       case 4:
       {
           int e;
           GetHead(Q, e);
           printf("队头元素为：%d\n", e);
       }
       break;
       case 5:
       {
           printf("队长度为：%d\n", QueueLength(Q));
       }
       break;
       case 6:
       {
           printf("你确定要销毁队列吗？？\n1---YES\n2---NO\n");
           int x;
           scanf("%d", &x);
           if (x == 1)
               DestrotQueue(Q);
       }
       break;
       case 7:
       {
           printf("你确定要清空队列吗？？\n1---YES\n2---NO\n");
           int x;
           scanf("%d", &x);
           if (x == 1)
               ClearQueue(Q);
       }
       break;
       case 8:
       {
           if (QueueEmpty(Q))
               printf("该队列为空\n");
           else

               printf("该队列非空\n");
       }
       break;
       case 9:
       {
           QueueTraverse(Q, visit);
       }
       break;
       default:
           return 0;
       }

   } while (num != 0);
   return OK;
}
void pt(Queue &Q)
{
   for (int i = Q.front; i != Q.rear; i = (i + 1) % maxsize)
       printf("%d ", Q.base[i]);
   printf("\n");
}
int main(int argc, char *argv[])
{
   Queue Q;
   InitQueue(Q);
   //int x=4;
   //EnQueue(Q, x);
   //pt(Q);
   //int y;4
   //GetHead(Q, y);
   //printf("hnbb    %d\n",QueueLength(Q));
   init(Q);
}

算法测试结果
对菜单的每个操作进行演示：具体演示如下：
分析与总结
（1）算法复杂度分析及优、缺点分析
算法的时间复杂度根据各个操作有所不同，除了对队列进行的遍历操作为O（N）之外，其余均为O（1），时间复杂度很低，非常适合操作。算法的优点是每一个都有一个固定的模块，算法结构性很好，对于整体的编程来说非常友好。缺点是由于是线性结构，算法其本身有局限性，入出队列要求高，不是随便出入。
（2）实验总结
写算法时判断队空以及队满的情况，没有分析清楚，不能更加准确的找到如何判断这两个操作，以至于后期出现段错误，导致没法进行程序。还有注意运用循环队列使整个空间能够更加好的运用，更好的利用所有空间。

码农公寓

相关文章