队列（链式存储结构）

2022-09-05 11:22:29 浏览数 (1)
  • 直接写一个队列和教材上对比
  • 双端队列学习
  • 队列的应用一：报数问题
  • 队列的应用二：求解迷宫
  • 习题板块
代码语言：javascript复制
//自己写的链式结构队列
// 要实现的操作有：  初始化initqueue  ，  销毁destroyqueue  ， 判断为空emptyqueue
// 进队列enqueue  ，  出队列dequeue  打印队列prntqueue
#include<bits/stdc  .h>
using namespace std;
typedef struct qnode{
	int data;
	struct qnode *next;
	
}datanode;
typedef struct{
	datanode *front;
	datanode *rear;
}squeue;
void initqueue(squeue*&q){
	q=(squeue*)malloc(sizeof(squeue));
	q->front=q->rear=NULL;
}
void destroyqueue(squeue*&q){
	datanode*pre=q->front,*p;
	if(pre!=NULL)
	{
		p=pre->next;
		while(p!=NULL){
			free(pre);
			pre=p;p=p->next;
		}
		free(pre);
	}
	free(q);
} 
bool emptyqueue(squeue*&q){
		return (q->rear==NULL);
}
void enqueue(squeue*&q,int e){
	//这里有两种情况，1队列为空，2队列不空 
	datanode *p;
	p=(datanode*)malloc(sizeof(datanode));
	p->data=e;
	p->next=NULL;
	if(q->rear==NULL)
	q->rear=q->front=p;
	else{
		q->rear->next=p;
		q->rear=p;
	}
}
bool dequeue(squeue*&q,int &e){
	//这里有三种情况，1队列为空，2队列中只有一个结点，3队列中有两个及其以上结点
	datanode*p;
	if(q->rear==NULL)
	return false;
	p=q->front;
	if(q->rear==q->front)
		q->rear=q->front=NULL;
	else	
		q->front=q->front->next;	
	e=p->data;
	free(p);
	return true;
}
void printqueue(squeue*q){
	datanode *p=q->front;
	while(p){
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<endl;
}
int main(){
	int e;
	squeue * q;
	initqueue(q);
	for(int i=1;i<10;i  )
	enqueue(q,i);
	printqueue(q);
	dequeue(q,e);
	dequeue(q,e);
	printqueue(q);
	
}

教材标准队列

代码语言：javascript复制
//链队运算算法
#include <stdio.h>
#include <malloc.h>
typedef char ElemType;
typedef struct DataNode
{	
	ElemType data;
	struct DataNode *next;
} DataNode;				//链队数据结点类型
typedef struct
{	
	DataNode *front;
	DataNode *rear;
} LinkQuNode;			//链队类型
void InitQueue(LinkQuNode *&q)
{	
	q=(LinkQuNode *)malloc(sizeof(LinkQuNode));
	q->front=q->rear=NULL;
}
void DestroyQueue(LinkQuNode *&q)
{
	DataNode *p=q->front,*r;//p指向队头数据结点
	if (p!=NULL)			//释放数据结点占用空间
	{	r=p->next;
		while (r!=NULL)
		{	free(p);
			p=r;r=p->next;
		}
	}
	free(p);
	free(q);				//释放链队结点占用空间
}
bool QueueEmpty(LinkQuNode *q)
{
	return(q->rear==NULL);
}
void enQueue(LinkQuNode *&q,ElemType e)
{	DataNode *p;
	p=(DataNode *)malloc(sizeof(DataNode));
	p->data=e;
	p->next=NULL;
	if (q->rear==NULL)		//若链队为空,则新结点是队首结点又是队尾结点
		q->front=q->rear=p;
	else
	{	q->rear->next=p;	//将p结点链到队尾,并将rear指向它
		q->rear=p;
	}
}
bool deQueue(LinkQuNode *&q,ElemType &e)
{	DataNode *t;
	if (q->rear==NULL)		//队列为空
		return false;
	t=q->front;				//t指向第一个数据结点
	if (q->front==q->rear)  //队列中只有一个结点时
		q->front=q->rear=NULL;
	else					//队列中有多个结点时
		q->front=q->front->next;
	e=t->data;
	free(t);
	return true;
}

双端队列

为了节约时间，我就没写了

教材标准双端队列

代码语言：javascript复制
//双端队列算法
#include "sqqueue.cpp"
bool deQueue1(SqQueue *&q,ElemType &e)		//从队尾删除
{
	if (q->front==q->rear)					//队空
		return false;
	e=q->data[q->rear];						//提取队尾元素
	q->rear=(q->rear-1 MaxSize)%MaxSize;	//修改除尾指针
	return true;
}
bool enQueue1(SqQueue *&q,ElemType e)		//从队头插入
{	
	if ((q->rear 1)%MaxSize==q->front)		//队满
		return false;
	q->data[q->front]=e;					//e元素进队
	q->front=(q->front-1 MaxSize)%MaxSize;	//修改队头指针
	return true;
}
int main()
{
	ElemType e;
	int i;
	SqQueue *q;
	InitQueue(q);
	printf("从队尾插入a,b,从队头插入c,d,从队尾插入en");
	enQueue(q,'a');		//从队尾插入'a'
	enQueue(q,'b');		//从队尾插入'b'
	enQueue1(q,'c');	//从队头插入'c'
	enQueue1(q,'d');	//从队头插入'd'
	enQueue(q,'e');		//从队尾插入'e'
	printf("从队头出队两个元素:");
	for (i=1;i<=2;i  )
	{
		deQueue(q,e);		//从队头删除
		printf("%c ",e);
	}
	printf("n从队尾出队其他元素:");
	while (!QueueEmpty(q))
	{
		deQueue1(q,e);		//从队尾删除
		printf("%c ",e);
	}
	printf("n");
	return 1;
}

报数问题

设有n个人站成一排，从左向右的编号分别为1-n，现在从左边往右报数“1，2，1，2，。。。“，数到”1“的人出列，数到”2”的人立即站到队伍的最右端。报数过程反复进行，直到n个人都出列为止。要求给出他们的出列顺序。 例如，当n=8时初始序列为： 1 2 3 4 5 6 7 8 则出列顺序为： 1 3 5 7 2 6 4 8

我就用自己写的队列来做把

代码语言：javascript复制
//自己写的链式结构队列
// 要实现的操作有：  初始化initqueue  ，  销毁destroyqueue  ， 判断为空emptyqueue
// 进队列enqueue  ，  出队列dequeue  打印队列prntqueue
#include<bits/stdc  .h>
using namespace std;
typedef struct qnode{
	int data;
	struct qnode *next;
	
}datanode;
typedef struct{
	datanode *front;
	datanode *rear;
}squeue;
void initqueue(squeue*&q){
	q=(squeue*)malloc(sizeof(squeue));
	q->front=q->rear=NULL;
}
void destroyqueue(squeue*&q){
	datanode*pre=q->front,*p;
	if(pre!=NULL)
	{
		p=pre->next;
		while(p!=NULL){
			free(pre);
			pre=p;p=p->next;
		}
		free(pre);
	}
	free(q);
} 
bool emptyqueue(squeue*&q){
		return (q->rear==NULL);
}
void enqueue(squeue*&q,int e){
	//这里有两种情况，1队列为空，2队列不空 
	datanode *p;
	p=(datanode*)malloc(sizeof(datanode));
	p->data=e;
	p->next=NULL;
	if(q->rear==NULL)
	q->rear=q->front=p;
	else{
		q->rear->next=p;
		q->rear=p;
	}
}
bool dequeue(squeue*&q,int &e){
	//这里有三种情况，1队列为空，2队列中只有一个结点，3队列中有两个及其以上结点
	datanode*p;
	if(q->rear==NULL)
	return false;
	p=q->front;
	if(q->rear==q->front)
		q->rear=q->front=NULL;
	else	
		q->front=q->front->next;	
	e=p->data;
	free(p);
	return true;
}
void printqueue(squeue*q){
	datanode *p=q->front;
	while(p){
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<endl;
}
int main(){
	squeue *q;
	initqueue(q);
	int n;//声明n个人
	n=8;//因为题目中是8个人
	for(int i=1;i<=n;i  )
	enqueue(q,i);
	printqueue(q);
	int e;
	int match=0;//喊一喊二 
	while(q->rear!=NULL){
		match=(match 1)%2;
		if(match){
			dequeue(q,e);
			cout<<e<<" ";
		}
		else{
			dequeue(q,e);
			enqueue(q,e);
		}
	} 
	
}

标准答案

代码语言：javascript复制
//求解报数问题
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef int ElemType;
//----------------------------------------------------------
//-环形队列的基本运算算法-----------------------------------
//----------------------------------------------------------
typedef struct 
{	ElemType data[MaxSize];				//存放队中元素
	int front,rear;						//队头和队尾指针
} SqQueue;								//顺序队类型
void InitQueue(SqQueue *&q)				//初始化队列
{	q=(SqQueue *)malloc (sizeof(SqQueue));
	q->front=q->rear=0;
}
void DestroyQueue(SqQueue *&q)			//销毁队列
{
	free(q);
}
bool QueueEmpty(SqQueue *q)				//判断队列是否为空
{
	return(q->front==q->rear);
}
bool enQueue(SqQueue *&q,ElemType e)	//进队列
{	if ((q->rear 1)%MaxSize==q->front)	//队满上溢出
		return false;
	q->rear=(q->rear 1)%MaxSize;
	q->data[q->rear]=e;
	return true;
}
bool deQueue(SqQueue *&q,ElemType &e)	//出队列
{	if (q->front==q->rear)				//队空下溢出
		return false;
	q->front=(q->front 1)%MaxSize;
	e=q->data[q->front];
	return true;
}
//----------------------------------------------------------
 
void number(int n)
{
	int i;  ElemType e;
	SqQueue *q;					//环形队列指针
	InitQueue(q);				//初始化队列
	for (i=1;i<=n;i  )			//构建初始序列
		enQueue(q,i);
	printf("报数出列顺序:");
	while (!QueueEmpty(q))		//队列不空循环
	{
		deQueue(q,e);			//出队一个元素e
		printf("%d ",e);		//输出元素编号
		if (!QueueEmpty(q))		//队列不空
		{
			deQueue(q,e);		//出队一个元素e
			enQueue(q,e);		//将刚出列的元素进队
		}
	}
	printf("n");
	DestroyQueue(q);			//销毁队列q
}
int main()
{
	int i,n=8;
	printf("初始序列:");
	for (i=1;i<=n;i  )
		printf("%d ",i);
	printf("n");
	number(n);
	return 1;
}

求解迷宫

习题板块

废江博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 转载请注明原文链接：队列（链式存储结构）

队列

0 人点赞