数据结构队列的实现--链式

柔情只为你懂 2022-12-13 09:53 153阅读 0赞

## 数据结构c语言链式队列的实现与表示 ##

代码如下：

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct QNode
    { 
    	int data;
    	struct QNode *next;
    }QNode,*QueuePtr;
    typedef struct
    { 
    	QueuePtr front;//队头指针 
    	QueuePtr rear;//队尾指针 
    }LinkQueue;
    
    void InitQueue(LinkQueue &Q)//初始化队列，构造一个空队列Q 
    { 
    	Q.front = Q.rear = (QNode*)malloc(sizeof(QNode));//生成新结点作为头结点，队头和队尾指针指向此结点 
    	Q.front -> next = NULL;//头结点的指针域置空 
    }
    
    int EnQueue(LinkQueue &Q,int e)//入队,链式队列没有存满的问题，所以不用考虑队列已满 
    { 
    	QNode* s = (QNode*)malloc(sizeof(QNode));//申请一个野结点 
    	s->data = e;//使野结点的数据赋值为e 
    	Q.rear->next = s;//使结点s连上队列， 
    	Q.rear = s;//并使尾指针指向结点s，以保持尾指针一直指向队尾 
    	return 0;
    } 
    
    void DeQueue(LinkQueue &Q)//进队 
    { 
    	if(Q.front == Q.rear)//首先判断队列是否为空 
    		printf("队列为空！\n");
    	else
    	{ 
    		QNode* p;
    		p = Q.front->next;//定义一个指针p并指向头结点的下一个结点 
    		printf("%d\n",p->data);
    		Q.front->next = p->next;//依次输出从队头到队尾的数据 
    	}
    }
    
    int Length(LinkQueue Q)//求队列的长度 
    { 
    	if(Q.front == Q.rear)//判断队列是否为空 
    	{ 
    		printf("空队列！\n");
    		return 0;
    	}
    	int i = 0;
    	QNode* p;//申请一个指针，并指向头结点， 
    	p = Q.front;
    	while(1)//利用死循环使指针p依次从头到尾的每一个结点，并计算个数 
    	{ 
    		p = p->next;
    		i++;//计数 
    		if(p == Q.rear)//死循环终止条件 
    			break;
    	}
    	return i;//返回队列长度 
    }
    
    int main()
    { 
    	int i;
    	LinkQueue Q;
    	InitQueue(Q);//对队列的初始化 
    	for(i=1;i<100;i++)//使数1,2,3,4,5,分别依次进队 
    		EnQueue(Q,i);
    	printf("当前队列长： %d\n",Length(Q));//出队之前队列的长 
    	DeQueue(Q);
    	printf("当前队列长： %d\n",Length(Q));//出队之后队列的长 
    	free(Q.front); 
    	return 0;
    }

（完）