实验内容:
用链式存储结构,实现教材定义的队列的基本操作。
实验步骤:
(1)按照实验要求编写代码,构造队列。
(2)输入验收用例,验证其输出结果。
#include <iostream>
#include <bits/stdc++.h>
#define OK 1
#define ERROR 0
using namespace std;
typedef int QElemType;
typedef int Status;
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
void Help()
{
cout << "1.初始化队列" << endl;
cout << "2.销毁队列" << endl;
cout << "3.清空队列" << endl;
cout << "4.判断队列是否为空" << endl;
cout << "5.返回队列元素个数" << endl;
cout << "6.返回队列对头元素" << endl;
cout << "7.插入新的队尾元素" << endl;
cout << "8.删除对头元素" << endl;
cout << "9.初始化并创建队列" << endl;
cout << "10.输出队列元素" << endl;
cout << "11.退出" << endl;
}
//初始化队列
Status InitQueue(LinkQueue &Q)
{
Q.front=Q.rear=new QNode;
Q.front->next=NULL;
return OK;
}
//销毁队列
Status DestroyQueue(LinkQueue &Q)
{
while(Q.front)
{
Q.rear=Q.front->next;
delete Q.front;
Q.front=Q.rear;
}
cout << "已销毁队列" << endl;
return OK;
}
//清空队列
Status Clear(LinkQueue &Q)
{
QueuePtr p,q;
p=Q.front;
while(p!=Q.rear)
{
q=p->next;
delete p;
p=q;
}
Q.front=Q.rear;
return OK;
}
//判断队列是否为空
bool QueueEmpty(LinkQueue Q)
{
return (Q.front==Q.rear);
}
//返回队列元素个数
int Length(LinkQueue Q)
{
QueuePtr p;
p=Q.front->next;
int count=0;
while(p)
{
count++;
p=p->next;
}
return count;
}
//返回队列对头元素
Status GetHead(LinkQueue Q,QElemType &e)
{
if(Q.front==Q.rear)
return ERROR;
e=Q.front->next->data;
return OK;
}
//插入新的队尾元素
Status EnQueue(LinkQueue &Q,QElemType e)
{
QueuePtr p=new QNode;
p->data=e;
p->next=NULL;
Q.rear->next=p;//修改队尾节点指针
Q.rear=p;//移动队尾指针
return OK;
}
//删除对头元素
Status DeQueue(LinkQueue &Q,QElemType &e)
{
if(Q.front==Q.rear)
return ERROR;
QueuePtr p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
delete p;
return OK;
}
//初始化并创建队列
Status Create_Insert(LinkQueue &Q,QElemType n)
{
InitQueue(Q);
QElemType m[n];
for(int i=0;i<n;i++)
{
cin >> m[i];
}
for(int i=0;i<n;i++)
{
EnQueue(Q,m[i]);
}
return OK;
}
//输出队列元素
void Print(LinkQueue Q)
{
QueuePtr p;
p=Q.front->next;
while(p)
{
cout << p->data << " " ;
p=p->next;
}
}
int main()
{
LinkQueue Q;
Help();
int n;
bool flag=false;
while(1)
{
cout<<"请输入你的选择:";
cin>>n;
if(n==1)
{
InitQueue(Q);
cout << "初始化成功" << endl;
flag=true;
}
else if(n==2)
{
if(flag==false)
{
cout << "请先初始化队列" << endl;
}
else
{
DestroyQueue(Q);
flag=false;
}
}
else if(n==3)
{
if(flag==false)
{
cout << "请先初始化队列" << endl;
}
else
{
Clear(Q);
cout << "已清空队列" << endl;
}
}
else if(n==4)
{
if(flag==false)
{
cout << "请先初始化队列" << endl;
}
else
{
if(QueueEmpty(Q))
cout << "队列为空" << endl;
else
cout << "队列非空" << endl;
}
}
else if(n==5)
{
if(flag==false)
{
cout << "请先初始化队列" << endl;
}
else
{
cout << "该队列元素个数为:" << Length(Q) << endl;
}
}
else if(n==6)
{
if(flag==false)
{
cout << "请先初始化队列" << endl;
}
else
{
QElemType e;
if(GetHead(Q,e))
cout << "对头元素为:" << e << endl;
else
cout << "队列为空" << endl;
}
}
else if(n==7)
{
if(flag==false)
{
cout << "请先初始化队列" << endl;
}
else
{
QElemType e;
cout << "输入插入元素:";
cin >> e;
EnQueue(Q,e);
cout << "插入成功" << endl;
}
}
else if(n==8)
{
if(flag==false)
{
cout << "请先初始化队列" << endl;
}
else
{
QElemType e;
if(!DeQueue(Q,e))
cout << "队列为空" << endl;
else
cout << "数据" << e << "已删除" << endl;
}
}
else if(n==9)
{
int m;
cout << "插入数据数量:";
cin >> n;
cout << "请输入数据(数据之间空格隔开):";
if(Create_Insert(Q,n))
cout << "初始化并创建成功" << endl;
flag=true;
}
else if(n==10)
{
if(flag==false)
{
cout << "请先初始化队列" << endl;
}
else
{
Print(Q);
cout<<endl;
}
}
else if(n==11)
{
return 0;
}
else
{
cout << "操作有误" << endl;
}
}
return 0;
}