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

深碍√TFBOYSˉ_ 2022-11-25 13:24 146阅读 0赞

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

一、实验目的

1.深入了解队列的定义和特性。  
2.掌握队列的数组表示、链表表示以及相应操作的实现，巩固对这两种结构的构造方法的掌握。  
3. 会灵活运用队列结构解决某些实际问题。

二、实验内容

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

三、实验要求

1.  在本题下面提交源程序和实验运行结果截图。
2.  顺序队列的基本操作的实现（初始化、赋值、取值、插入、删除等）。

#include<cstdio>
    #include<iostream>
    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;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70]

1.  舞伴问题

#include<stdio.h>
    #define MAXQSIZE 100
    #define QueueSize 20
    #define OK 1
    #define ERROR 0
    #define OVERFLOW 0
    #include <cstdlib>
    #include<iostream>
    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);           
     }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70]: /images/20221124/39d8bb7121bf4964aea3fd457ddfbc0b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70 1]: /images/20221124/9be2738c2af6459e99c6f878f1d8dce3.png