【数据结构】队列的基本操作_给出一个队列和要查找的数值,找出数值在队列中的位置,队列位置从1开始 要求使用带

分别定义两个结构体——数值链队列、头尾结点队

typedef struct Qnode{
	QElemType data; 
	struct Qnode *next;
}Qnode,*QueuePtr;

typedef struct{
	Qnode *front;
	Qnode *rear;
}LinkQueue;

问题：

1、编写函数，实现链式队列的基本操作；

2、编写函数，实现循环队列的基本操作。

一、各函数代码如下

 解题一：

//链队的初始化
int InitQueue(LinkQueue &Q){
	Q.front = Q.rear = new Qnode;//生成一个新结点，队头队尾指针指向此结点 
	Q.front->next = NULL;//头结点的指针域置空 
	return 1;
}

//入队
int enQueue(LinkQueue &Q,int e){
	Qnode *p = new Qnode;
	p->data = e;
	p->next = NULL;
	Q.rear->next = p;
	Q.rear = p;
	return 1;
} 

//出队
void deQueue(LinkQueue &Q){
    int a;
    Qnode *temp;
    if(Q.front==Q.rear)               //队为空，出队失败 
    {
        printf("An empty Queue error!!!!\n");
    }
    else
    {
        temp=Q.front->next;
        a=temp->data;
        Q.front->next=temp->next;
        if(Q.front==temp)           //如果队中只有一个元素X，则X出队后成为空队 
        {
            Q.rear=Q.front;
        }
        delete temp;                            //释放存储空间 
        printf("队头元素%d，出队成功.\n",a);   
    }  
}

//取队头元素
int getHead(LinkQueue Q){
	if(Q.front != Q.rear){
		return Q.front->next->data;
	}
} 

/判断队列为空性
int judgeQueue(LinkQueue Q){
	return (Q.rear == Q.front);
} 

//链队长度 
int queueLength(LinkQueue Q){
	int count=0;
	Qnode *p=Q.front->next;
	while(p!=NULL){
	count++;
	p=p->next;
	}
	return count;
}

//遍历队列
void show_queue(LinkQueue Q){
	Qnode *p=Q.front->next;
	cout<<"当前元素从头到尾:";
	while(p!=NULL){
		printf("%d ",p->data);
		p=p->next;
	}
}

//清除队列 
void clearQueue(LinkQueue &Q){//除头结点外,对所有结点进行清除
	if(Q.front==Q.rear)//如果头指针与尾指针指向相同,则链队为空
	return;//无需清除
	Qnode *p=Q.front->next;//指针p指向头结点后第一个有效结点
	while(p!=NULL)
	{
		Q.front->next=p->next;//头结点的指针域保存第二个有效结点的地址
		delete p;//释放第一个有效结点
		p=Q.front->next;//指针p重新指向头结点后第一个有效结点
	}
//释放完成后,对尾部指针进行修改
	Q.rear=Q.front;//队尾指针指向头结点
}

//销毁队列 
void destroyQueue(LinkQueue &Q){//清除的前提下释放头结点实现销毁
	clearQueue(Q);
	delete Q.front;//释放头结点
	Q.front=Q.rear=NULL;//队头和队尾指针都赋空,预防野指针
}

//设置一个选择，实现与用户交互
void switchice(LinkQueue &Q){
	int i;
	cout<<"\n1.继续出队		2.清空队列元素"<<endl<<"3.销毁队列"<<endl<<"请输入选项：";
	cin>>i;
	switch(i)
	{
		case 1:deQueue(Q);break;
		case 2:clearQueue(Q);	cout<<"清空链队成功！！！"<<endl;	break;
		case 3:destroyQueue(Q); cout<<"已销毁链队！！！结束所有操作！！！"<<endl;		break;
	}
	if(i==1 || i==2){
		switchice(Q);
	}
	else return;
} 

解题一完整代码：

#include <iostream.h>
typedef struct Qnode{
	int data;//本项目将对int型数据进行操作 
	struct Qnode *next;
}Qnode,*QueuePtr;
typedef struct{
	Qnode *front;
	Qnode *rear;
}LinkQueue;
 
/*********************各个子函数的定义*********************/ 
int InitQueue(LinkQueue &Q);//链队的初始化
int enQueue(LinkQueue &Q,int e);//入队
void deQueue(LinkQueue &Q);//出队
int getHead(LinkQueue Q);//取队头元素
int judgeQueue(LinkQueue Q);//判断队列为空性
int queueLength(LinkQueue Q);//链队长度 
void show_queue(LinkQueue Q);//遍历队列
void clearQueue(LinkQueue &Q);//清除队列 
void destroyQueue(LinkQueue &Q);//销毁队列 
void switchice(LinkQueue &Q);//设置一个选择，实现与用户交互
 
int main()
{
	int num,i,e;
	LinkQueue Q;
	if(InitQueue(Q) != 0){
		cout<<"初始化成功！！！"<<endl;
		if(judgeQueue(Q)){
			cout<<"此队列为空！！！"<<endl;
		}
	}
	cout<<"入队的个数：";
	cin>>num;
	for(i=0;i<num;i++){
		printf("请输入第%d个元素：",i+1);
		cin>>e;
		enQueue(Q,e);//依次入队 
	}
	cout<<"入队成功！！！"<<endl;
	cout<<"队头元素为："<<getHead(Q)<<endl;
	show_queue(Q);//遍历队列并打印 
	cout<<endl<<"本队列长度为："<<queueLength(Q)<<endl;
	cout<<"\n出队：";
	deQueue(Q);
	switchice(Q);//含出队，清空链队和销毁链队操作 
	return 0;
}
 
/*********************各个子函数功能的实现*********************/ 
//链队的初始化
int InitQueue(LinkQueue &Q){
	Q.front = Q.rear = new Qnode;//生成一个新结点，队头队尾指针指向此结点 
	Q.front->next = NULL;//头结点的指针域置空 
	return 1;
}
 
//入队
int enQueue(LinkQueue &Q,int e){
	Qnode *p = new Qnode;
	p->data = e;
	p->next = NULL;
	Q.rear->next = p;
	Q.rear = p;
	return 1;
} 
 
//出队
void deQueue(LinkQueue &Q){
    int a;
    Qnode *temp;
    if(Q.front==Q.rear)               //队为空，出队失败 
    {
        printf("An empty Queue error!!!!\n");
    }
    else
    {
        temp=Q.front->next;
        a=temp->data;
        Q.front->next=temp->next;
        if(Q.front==temp)           //如果队中只有一个元素X，则X出队后成为空队 
        {
            Q.rear=Q.front;
        }
        delete temp;                            //释放存储空间 
        printf("队头元素%d，出队成功.\n",a);   
    }  
}
 
//取队头元素
int getHead(LinkQueue Q){
	if(Q.front != Q.rear){
		return Q.front->next->data;
	}
} 
 
//判断队列为空性
int judgeQueue(LinkQueue Q){
	return (Q.rear == Q.front);
} 
 
//链队长度 
int queueLength(LinkQueue Q){
	int count=0;
	Qnode *p=Q.front->next;
	while(p!=NULL){
	count++;
	p=p->next;
	}
	return count;
}
 
//遍历队列
void show_queue(LinkQueue Q){
	Qnode *p=Q.front->next;
	cout<<"当前元素从头到尾:";
	while(p!=NULL){
		printf("%d ",p->data);
		p=p->next;
	}
}
 
//清除队列 
void clearQueue(LinkQueue &Q){//除头结点外,对所有结点进行清除
	if(Q.front==Q.rear)//如果头指针与尾指针指向相同,则链队为空
	return;//无需清除
	Qnode *p=Q.front->next;//指针p指向头结点后第一个有效结点
	while(p!=NULL)
	{
		Q.front->next=p->next;//头结点的指针域保存第二个有效结点的地址
		delete p;//释放第一个有效结点
		p=Q.front->next;//指针p重新指向头结点后第一个有效结点
	}
//释放完成后,对尾部指针进行修改
	Q.rear=Q.front;//队尾指针指向头结点
}
 
//销毁队列 
void destroyQueue(LinkQueue &Q){//清除的前提下释放头结点实现销毁
	clearQueue(Q);
	delete Q.front;//释放头结点
	Q.front=Q.rear=NULL;//队头和队尾指针都赋空,预防野指针
}
 
//设置一个选择，实现与用户交互
void switchice(LinkQueue &Q){
	int i;
	cout<<"\n1.继续出队		2.清空队列元素"<<endl<<"3.销毁队列"<<endl<<"请输入选项：";
	cin>>i;
	switch(i)
	{
		case 1:deQueue(Q);break;
		case 2:clearQueue(Q);	cout<<"清空链队成功！！！"<<endl;	break;
		case 3:destroyQueue(Q); cout<<"已销毁链队！！！结束所有操作！！！"<<endl;		break;
	}
	if(i==1 || i==2){
		switchice(Q);
	}
	else return;
} 

 执行效果：

---

---

解题二：

//循环队列初始化
Status InitQueue (SqQueue &Q){
    Q.base =new QElemType[MAXQSIZE];
   if(!Q.base) exit(OVERFLOW);
    Q.front=Q.rear=0;
    return OK;
}

//销毁队列 
void DestroyQueue(SqQueue Q){
    delete Q.base;//直接释放队列指针
    Q.base = NULL;//重置为NULL
    Q.front = Q.rear = 0;//重置为0
}

//清空队列指针，直接使两个标记重置为0
void ClearQueue(SqQueue Q){
    Q.front = Q.rear = 0;
}

//循环队列入队 
Status EnQueue(SqQueue &Q,QElemType e){
    if((Q.rear+1)%MAXQSIZE==Q.front)  return ERROR;
    Q.base[Q.rear]=e;
    Q.rear=(Q.rear+1)%MAXQSIZE;
     return OK;
}

//循环队列出队 
Status DeQueue (SqQueue &Q,QElemType &e){
   if(Q.front==Q.rear) return ERROR;
   e=Q.base[Q.front];
   Q.front=(Q.front+1)%MAXQSIZE;
   return OK;
}

//判断是否为空
Status QueueEmpty(SqQueue Q){
    if(Q.front == Q.rear)
        return 1;
    else
        return 0;
}

//取队头元素
Status GetHead(SqQueue Q){   
    return *(Q.base + Q.front);    
}

//求循环队列的长度
Status  QueueLength(SqQueue Q){
    return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;                             
}

//遍历队列
void Traverse(SqQueue Q){
    if(Q.front == Q.rear)//判断是否为空
        return;
    cout<<"当前队列为：";
    while(Q.front != Q.rear)
    {
        printf("%d ", *(Q.base + Q.front));//遍历操作，这里是简单的打印输出
        Q.front = (Q.front + 1) % MAXQSIZE;//下标后移直到与队尾下标重合，注意这里没有改变两个下标的值，被调函数只是拷贝了一份副本
    }
    cout<<endl;
}

//设置一个选择，实现与用户交互
void switchice(SqQueue &Q){
	int i,e;
	cout<<"\n1.继续出队		2.清空队列元素"<<endl<<"3.销毁队列"<<endl<<"请输入选项：";
	cin>>i;
	switch(i)
	{
		case 1:DeQueue(Q,e);printf("队头元素%d，出队成功！！！\n", e);break;
		case 2:ClearQueue(Q);	cout<<"清空队列成功！！！"<<endl;						break;
		case 3:DestroyQueue(Q); cout<<"已销毁队列！！！结束所有操作！！！"<<endl;		break;
	}
	if(i==1 || i==2){
		switchice(Q);
	}
	else return;
}

解题二完整代码：

#include<iostream.h>
#include<stdio.h>
#define MAXQSIZE  100   //最大队列长度
#define ERROR 0
#define OK 1
#define OVERFLOW -2
typedef int Status;
typedef int QElemType;
typedef struct {
   QElemType *base;  //初始化的动态分配存储空间
   int  front;            //头指针   
   int  rear;             //尾指针
}SqQueue;  
 
/*********************各个子函数的定义*********************/ 
Status InitQueue (SqQueue &Q);//循环队列初始化
void DestroyQueue(SqQueue Q);//销毁队列 
void ClearQueue(SqQueue Q);//清空队列指针，直接使两个标记重置为0
Status EnQueue(SqQueue &Q,QElemType e);//循环队列入队 
Status DeQueue (SqQueue &Q,QElemType &e);//循环队列出队 
Status QueueEmpty(SqQueue Q);//判断是否为空
Status GetHead(SqQueue Q);//取队头元素
Status  QueueLength(SqQueue Q);//求循环队列的长度
void Traverse(SqQueue Q);//遍历队列
void switchice(SqQueue &Q);//设置一个选择，实现与用户交互
 
int main()
{
    QElemType e,i,num,*s;//*s为取队头元素指针 
    SqQueue Q;
    if(InitQueue(Q)==1){
    	cout<<"循环队列初始化成功！！！"<<endl;
    }
    if(QueueEmpty(Q)==1){
    	cout<<"此队列为空！！！"<<endl;
    }
    else{
    	cout<<"此队列不为空！！！"<<endl;
    }
    cout<<"入队个数：";
	cin>>num; 
    for(i=0;i<num;i++){
    	printf("请输入第%d个元素：",i+1);
		cin>>e;
		EnQueue(Q,e);//依次入队 
    }
    Traverse(Q);//遍历队列 
    cout<<"当前队头元素为："<<GetHead(Q)<<endl;
    cout<<"出队：";
    DeQueue(Q,e);//出队 
    printf("队头元素%d，出队成功！！！\n", e);
	switchice(Q);
}
 
 
/*********************各个子函数功能的实现*********************/ 
//循环队列初始化
Status InitQueue (SqQueue &Q){
    Q.base =new QElemType[MAXQSIZE];
   if(!Q.base) exit(OVERFLOW);
    Q.front=Q.rear=0;
    return OK;
}
 
//销毁队列 
void DestroyQueue(SqQueue Q){
    delete Q.base;//直接释放队列指针
    Q.base = NULL;//重置为NULL
    Q.front = Q.rear = 0;//重置为0
}
 
//清空队列指针，直接使两个标记重置为0
void ClearQueue(SqQueue Q){
    Q.front = Q.rear = 0;
}
 
//循环队列入队 
Status EnQueue(SqQueue &Q,QElemType e){
    if((Q.rear+1)%MAXQSIZE==Q.front)  return ERROR;
    Q.base[Q.rear]=e;
    Q.rear=(Q.rear+1)%MAXQSIZE;
     return OK;
}
 
//循环队列出队 
Status DeQueue (SqQueue &Q,QElemType &e){
   if(Q.front==Q.rear) return ERROR;
   e=Q.base[Q.front];
   Q.front=(Q.front+1)%MAXQSIZE;
   return OK;
}
 
//判断是否为空
Status QueueEmpty(SqQueue Q){
    if(Q.front == Q.rear)
        return 1;
    else
        return 0;
}
 
//取队头元素
Status GetHead(SqQueue Q){   
    return *(Q.base + Q.front);    
}
 
//求循环队列的长度
Status  QueueLength(SqQueue Q){
    return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;                             
}
 
//遍历队列
void Traverse(SqQueue Q){
    if(Q.front == Q.rear)//判断是否为空
        return;
    cout<<"当前队列为：";
    while(Q.front != Q.rear)
    {
        printf("%d ", *(Q.base + Q.front));//遍历操作，这里是简单的打印输出
        Q.front = (Q.front + 1) % MAXQSIZE;//下标后移直到与队尾下标重合，注意这里没有改变两个下标的值，被调函数只是拷贝了一份副本
    }
    cout<<endl;
}
 
//设置一个选择，实现与用户交互
void switchice(SqQueue &Q){
	int i,e;
	cout<<"\n1.继续出队		2.清空队列元素"<<endl<<"3.销毁队列"<<endl<<"请输入选项：";
	cin>>i;
	switch(i)
	{
		case 1:DeQueue(Q,e);printf("队头元素%d，出队成功！！！\n", e);break;
		case 2:ClearQueue(Q);	cout<<"清空队列成功！！！"<<endl;						break;
		case 3:DestroyQueue(Q); cout<<"已销毁队列！！！结束所有操作！！！"<<endl;		break;
	}
	if(i==1 || i==2){
		switchice(Q);
	}
	else return;
}

执行效果：

---

---

分享完毕~

欢迎小伙伴们在文下评论和私信喔~