链队列的基本操作

素颜马尾好姑娘i 2022-04-23 04:58 288阅读 0赞

**一、链队列的数据类型定义：**

#include<stdio.h>
    #include<stdlib.h>
    #include<assert.h> 
    
    #define  ERROR  0
    #define  OK     1 
    #define  TRUE   1
    #define  FALSE  0
    
    typedef int  Status;
    typedef int  Elemtype;
    typedef struct QNode{
    	Elemtype data;
    	struct QNode *next;
    }QNode,*QueuePtr;
    
    typedef struct{
    	QueuePtr front;  //队头指针 
    	QueuePtr rear;   //队尾指针 
    }LinkQueue;

**二、链队列的初始化：**

void InitQueue(LinkQueue *Q)
    {
    	Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));//生成头结点 
    	assert(Q->front !=NULL);                         //检查生成头结点是否成功 
    	Q->front->next=NULL;
    }

**三、入队操作：**

void EnQueue(LinkQueue *Q,Elemtype e)
    {
    	QueuePtr p;
    	p=(QueuePtr)malloc(sizeof(QNode));
    	assert(p!=NULL);
    	p->data=e;           //将e的值赋给新结点 
    	p->next=NULL;        //新结点的指针为空 
    	Q->rear->next=p;    //原队尾结点的指针指向新结点 
    	Q->rear=p;          //队尾指针指向新结点 
    }

**四、出队列操作：**

Status DeQueue(LinkQueue *Q,Elemtype *e)
    {
    	QueuePtr p;
    	if(Q->front == Q->rear)//队列为空 
    	{
    		return ERROR;
    	}
    	p=Q->front->next;        //p指向队头结点 
    	*e=p->data;             //将对头结点的元素赋给e 
    	Q->front->next=p->next; //将队头结点指针指向下一个结点 
    	if(Q->rear==p)          //如果删除的是队尾结点 
    	{
    		Q->rear=Q->front;   //修改队尾指针，使之指向头结点 
    	}
    	free(p);
    	return OK;
    }

**五、获取队头元素值：**

Status GetHead(LinkQueue *Q,Elemtype *e)
    {
    	QueuePtr p;
    	if(Q->front == Q->rear)
    	{
    		return ERROR;
    	}
    	p=Q->front->next;
    	*e=p->data;
    	return OK;	
    }

**六、清空队列：**

void ClearQueue(LinkQueue *Q)
    {
    	/*将队列清空*/
    	Q->front->next=NULL;
    }

**七、销毁队列：**

Status DestroyQueue(LinkQueue *Q)
    {    /*销毁队列*/
    	while(Q->front)
    	{
    		Q->rear=Q->front->next;
    		free(Q->front);
    		Q->front=Q->rear;
    	}
    	return OK;
    }

**八、求队列长度：**

Status QueueLength(LinkQueue *Q)
    {  /*求队列长度*/
    	int len=0;
    	QueuePtr p=Q->front->next;
    	while(p)
    	{
    		len++;
    		p=p->next; 
    	}
    	return len;
    }

**九、判断队列是否为空：**

Status QueueEmpty(LinkQueue *Q)
    {   /*判断队列是否为空*/
    	if(Q->front == Q->rear)
    	{
    		return TRUE;
    	}
    	return FALSE;
    }

**十、遍历队列：**

void QueueTraverse(LinkQueue *Q,void(*visit)(Elemtype))
    {   /*遍历队列*/
    	QueuePtr p=Q->front->next;
    	while(p)
    	{
    		visit(p->data);
    		p=p->next;
    	}
    	printf("\n");
    } 
    void Print(Elemtype e)
    {
    	printf("%d ",e);
    }

**十一、主函数：**

int main()
    {
    	Elemtype k,d,e;
    	LinkQueue Q;
    	InitQueue(&Q);
    	printf("请输入初始化队列数据(输入0结束):\n");
    	scanf("%d",&d);
    	while(d)
    	{
    		EnQueue(&Q,d);
    		scanf("%d",&d);
    	}
    	printf("队列元素为:\n");
    	QueueTraverse(&Q,Print);
    	
    	k=QueueEmpty(&Q);
    	printf("判断队列是否为空：k=%d \t(1:为空;0:不为空)\n",k); 
    	
    	k=GetHead(&Q,&e);
    	printf("队头元素为:%d\n",e);
    	
    	DeQueue(&Q,&e);
    	printf("删除队头元素：%d\n",e);
    	
    	k=GetHead(&Q,&e);
    	printf("新的队头元素为:%d\n",e);
    	
    	printf("此时队列长度为：%d\n",QueueLength(&Q));
    	
    	ClearQueue(&Q);
    	printf("清空队列后:Q.front=%u,Q.rear=%u,Q.front->next=%d\n",Q.front,Q.rear,Q.front->next);
    	
    	DestroyQueue(&Q);
    	printf("销毁队列后:Q.front=%u,Q.rear=%u\n",Q.front,Q.rear);
    	
    	return 0;
    }

**十二、运行效果截图：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyNTMz_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyNTMz_size_16_color_FFFFFF_t_70]: /images/20220323/4e55178d3b7a481c8a1d906e7de5a9cf.png