顺序队列，链队列的基本操作

一、实验目的

1.深入了解队列的定义和特性。
2.掌握队列的数组表示、链表表示以及相应操作的实现，巩固对这两种结构的构造方法的掌握。

会灵活运用队列结构解决某些实际问题。

二、实验内容

顺序队列的基本操作的实现（初始化、赋值、取值、插入、删除等）。
链队列的基本操作的实现（初始化、赋值、取值、插入、删除等）。
舞伴问题（参加教材相关描述）。

三、实验要求

在本题下面提交源程序和实验运行结果截图。

顺序队列的基本操作的实现（初始化、赋值、取值、插入、删除等）。

include

using namespace std;

define ERROR 0

define OK 1

define OVERFLOW -1

define MAXSIZE 100

typedef int QElemType;
typedef int Status;
typedef struct {

QElemType *base;
int front;
int rear;

} SqQueue;
Status InitQueue(SqQueue &Q) {

Q.base = new QElemType[MAXSIZE];
if(!Q.base) {
    cout<<"储存分配失败"<<endl;
    exit(OVERFLOW);
}
Q.front=Q.rear=0;
return OK;

}//初始化
Status EnQueue(SqQueue &Q,QElemType e) {

if((Q.rear+1)%MAXSIZE==Q.front)
    return ERROR;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXSIZE;
return OK;

}//插入新元素
QElemType GetHead(SqQueue Q) {

if(Q.front!=Q.rear)
    return Q.base[Q.front];

}//取元素
Status DeQueue(SqQueue &Q,QElemType &e) {

if(Q.front==Q.rear) return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXSIZE;
return OK;

}//出队
int QueueLenght(SqQueue Q) {

return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;

}//求长度
int main() {

SqQueue Q;
int n,m;
QElemType e;
if(InitQueue(Q)) cout<<"初始化成功"<<endl;
cout<<"请输入队列中元素个数"<<endl;
cin>>n;
for(int i=0; i<n; i++) {
    cin>>e;
    EnQueue(Q,e);
}
cout<<"1,取队头元素"<<endl;
cout<<"2,向队尾插入元素"<<endl;
cout<<"3,出队"<<endl;
cout<<"4,退出"<<endl;
while(~scanf("%d",&m)) {
    if(m==4)
    break;
    switch(m) {
        case 1:
            cout<<"队头元素为"<<GetHead(Q)<<endl;
            break;
        case 2:
            cout<<"请输入要插入的队尾元素:"<<endl;
            cin>>e;
            EnQueue(Q,e);
            cout<<"当前对内元素有："<<QueueLenght(Q)<<"个"<<endl;
            break;
        case 3:
            DeQueue(Q,e);
            cout<<"出队元素为" <<e<<endl;
            cout<<"当前对内元素有："<<QueueLenght(Q)<<"个"<<endl;
            break;
        default:
            break;
    }
}
return 0;

}

在这里插入图片描述

舞伴问题

include

define MAXQSIZE 100

define QueueSize 20

define OK 1

define ERROR 0

define OVERFLOW 0

include

using namespace std;
typedef char QElemType;
typedef int Status;
//typedef char SElemType;
typedef struct
{

char name[QueueSize];
char sex;

}person;
typedef struct
{

person *dancer;
person *base;       //存储空间的基地址
int front;             //头指针
int rear;              //尾指针

}SqQueue;

Status InitQueue(SqQueue &Q)
{

//构造一个空队列Q
Q.base=new person[MAXQSIZE];    //为队列分配一个最大容量为MAXQSIZE的数组空间
if(!Q.base) exit(OVERFLOW);        //存储分配失败
Q.front=Q.rear=0;                  //头指针和尾指针为零，队列为空
return OK;

}
Status EnQueue(SqQueue &Q,person e)
{

//插入元素e为Q的新的队尾元素
 if((Q.rear+1)%MAXQSIZE==Q.front)   //尾指针在循环意义上加1后等于头指针，表明队满
    return ERROR;
Q.base[Q.rear]=e;                //新元素插入队尾
Q.rear=(Q.rear+1)%MAXQSIZE;       //队尾指针加1
return OK;

}
int QueueEmpty(SqQueue &Q)
{

if (Q.front==Q.rear)   return OK;
else return ERROR;

}
Status DeQueue(SqQueue &Q,person &e)
{

//删除Q的队头元素，用e返回其值
 if(Q.front==Q.rear) return ERROR;   //队空
e=Q.base[Q.front];                  //保存队头元素
Q.front=(Q.front+1)%MAXQSIZE;       //队头指针加1 
return OK;

}
person GetHead(SqQueue Q)
{

//返回Q的队列元素，不修改队头指针
if(Q.front!=Q.rear)              //队列非空
    return Q.base[Q.front];      //返回队头元素的值，队头指针不变

}
void DancePartner(person dancer[],int num)
{

//结构数组dancer中存放跳舞的男女，num是跳舞的人数 
person p;
int i;
SqQueue Mdancers,Fdancers;
InitQueue(Mdancers);     //男士队列初始化 
InitQueue(Fdancers);     //女士队列初始化 
for (i=0;i<num;i++)      //根据性别依次将跳舞的人插入相应队列 
{
    p=dancer[i];
    if (p.sex=='F')  EnQueue(Fdancers,p);    //插入男队
    else EnQueue(Mdancers,p);               //插入女队    
 } 
cout<<"The dancing partner are:\n";
while(!QueueEmpty(Fdancers)&&!QueueEmpty(Mdancers)) 
{
//依次输出男女舞伴的姓名 
    DeQueue(Fdancers,p);     //女士出队
    cout<<p.name<<" ";      //输出出队女士姓名
    DeQueue(Mdancers,p);    //男士出队
    cout<<p.name<<endl;     //输出出队男士姓名             
}
if (!QueueEmpty(Fdancers))      //女士队非空，输出队头女士的姓名 
{
    p=GetHead(Fdancers);     // 取女队的头
    cout<<p.name<<" is waiting for a partner."<<endl;   
}
else if (!QueueEmpty(Mdancers))    //男士队非空，输出男士队头的姓名
{
    p=GetHead(Mdancers);     // 取男队的头
    cout<<p.name<<" is waiting for a partner."<<endl;  
}

}
int main()
{

 int i,j;
 person dancer[QueueSize];
 cout<<"请输入跳舞的人数：";
 cin>>j;
 while(j<=0)
 {
     cout<<"输入错误，请重新输入跳舞的人数："; 
     cin>>j;
 }
for(i=1;i<=j;i++)
{
    cout<<"请输入第"<<i<<"舞者的名字:"<<endl;
    cin>>dancer[i-1].name;
    cout<<"请输入第"<<i<<"个人的性别(F/M):"<<endl;
    cin>>dancer[i-1].sex;
    while(dancer[i-1].sex!='F'&&dancer[i-1].sex!='M')
    {
        cout<<"*******输入错误，请重新输入：\n";
        cout<<dancer[i-1].sex;
        cout<<"请输入第"<<i<<"个人的性别(F/M):"<<endl;
        cin>>dancer[i-1].sex;
        break;
    }
}
DancePartner(dancer,j);