数据结构：不带头结点的链式队列的实现

骑猪看日落 2022-05-24 07:37 217阅读 0赞

/*----------------------------------------------------------------
    
    * 设立一个队首指针front ，一个队尾指针rear ，分别指向队首和队尾元素。
    * ◆ 初始化：LQ->front = LQ->rear = NULL;将队列的尾指针和头指针置空，
    * 由于不带头结点，所有不需要为头结点开辟空间
    * ◆ 判断队列是否为空：LQ->front ==  NULL
    * ◆ 队满：链式队列的结点是动态开辟的，一般情况下不存在队满
    * ◆ 入队：将新结点插入rear所指下一个结点，然后rear指向新插入的结点
    * ◆ 出队：删去front所指的元素，并返回被删元素。
    * ◆ 取队头元素：返回队头元素的值 return *data = LQ->front->_data;
    * ◆ 清空队列：从头结点开始，依次销毁结点的空间
    * ◆ 打印队列中的元素：pCur指向头结点，打印pCur指向的结点元素，pCur
    * 后移直到pCur==NULL
    
    ------------------------------------------------------------------*/
    
    
                     /* 不带头结点的队列实现源代码*/
    /*----------------------------------------------------------------*/
    
    #include <stdio.h>
    #include <Windows.h>
    #include <stdlib.h>
    #include <assert.h>
    
    typedef int DataType;
    typedef struct Node
    {
    	DataType _data;       
    	struct Node* _next;
    }LinkQueueNode;
    
    typedef struct
    {
    	LinkQueueNode* front;
    	LinkQueueNode* rear;
    }LinkQueue;
    
    //初始化链队列
    void InitLinkQueue(LinkQueue* LQ)
    {
    	LQ->front = LQ->rear = NULL;
    }
    
    //判断队列是否为空，如果队列为空返回1，否则返回0
    int IsEmpty(LinkQueue* LQ)
    {
    	if (LQ->front ==  NULL)
    	{
    		return 1;
    	}
    	else
    	{
    		return 0;
    	}
    }
    
    //入队操作
    
    void EnterQueue(LinkQueue* LQ, DataType data)
    {
    	LinkQueueNode* pNewNode = (LinkQueueNode*)malloc(sizeof(LinkQueueNode));
    	assert(pNewNode);
    	pNewNode->_data = data;
    	pNewNode->_next = NULL;
    	//如果队列为空，则是头指针和尾指针都指向要插入的结点
    	if (IsEmpty(LQ))
    	{
    		LQ->front = pNewNode;
    		LQ->rear = pNewNode;
    		return;
    	}
    	LQ->rear->_next = pNewNode;
    	LQ->rear = pNewNode;
    }
    
    //出队操作
    
    int DeleteQueue(LinkQueue* LQ,DataType* data)
    {
    	if (IsEmpty(LQ))
    	{
    		printf("队列为空!\n");
    		return 0;
    	}
    	LinkQueueNode* pDel;
    	//出队是对队头，进行操作使pDel指向队头指针
    	pDel = LQ->front;
    	//将要出队的元素值赋给data
    	*data = pDel->_data;
    	LQ->front->_next = pDel->_next;
    	LQ->front = pDel->_next;
    	//释放pDel指向的空间
    	free(pDel);
    	return *data;
    }
    
    //取队头元素
    
    int GetHead(LinkQueue* LQ,DataType* data)
    {
    	if (IsEmpty(LQ))
    	{
    		printf("队列为空！\n");
    		return 0;
    	}
    	//将队头元素的值赋给data
    	*data = LQ->front->_data;
    	//返回队头元素值
    	return *data;
    }
    
    //打印队列中的元素
    
    void PrintLinkQueue(LinkQueue* LQ)
    {
    	assert(LQ);
    	//pCur指向队头
    	LinkQueueNode* pCur = LQ->front;
    	while (pCur)
    	{
    		//打印pCur指向的结点值
    		printf("%-3d", pCur->_data);
    		//pCur指针后移
    		pCur = pCur->_next;
    	}
    	printf("\n");
    }
    
    //清空队列，销毁队列中结点的空间
    void ClearQueue(LinkQueue* LQ)
    {
    	while (LQ->front != NULL)
    	{
    		//队尾指针指向队头指针指向的下一个结点
    		LQ->rear = LQ->front->_next;
    		//释放队头指针指向的结点
    		free(LQ->front);
    		//队头指针指向队尾指针
    		LQ->front = LQ->rear;
    	}
    }
    int main()
    {
    	LinkQueue LQ;
    	DataType data;
    	InitLinkQueue(&LQ);
    	printf("1,2,3,5,7,8,10,15依此入队\n");
    	EnterQueue(&LQ, 1);
    	EnterQueue(&LQ, 2);
    	EnterQueue(&LQ, 3);
    	EnterQueue(&LQ, 5);
    	EnterQueue(&LQ, 7);
    	EnterQueue(&LQ, 8);
    	EnterQueue(&LQ, 10);
    	EnterQueue(&LQ, 15);
    	printf("\n");
    	printf("队列中的元素为：");
    	PrintLinkQueue(&LQ);
    	printf("\n");
    	data = GetHead(&LQ, &data);
    	printf("队头元素为：%d\n", data);
    	printf("\n");
    	printf("队头元素第一次出队：\n");
    	data = DeleteQueue(&LQ,&data);
    	printf("出队的元素为：%d\n", data);
    	printf("\n");
    	printf("\n");
    	printf("队头元素第二次出队：\n");
    	data = DeleteQueue(&LQ, &data);
    	printf("出队的元素为：%d\n", data);
    	printf("\n");
    	printf("队列中的元素为：");
    	PrintLinkQueue(&LQ);
    	data = GetHead(&LQ, &data);
    	printf("队头元素为：%d\n", data);
    	printf("\n");
    	printf("20入队\n");
    	EnterQueue(&LQ, 20);
    	printf("25入队\n");
    	EnterQueue(&LQ, 25);
    	printf("\n");
    	printf("队列中的元素为：");
    	PrintLinkQueue(&LQ);
    	ClearQueue(&LQ);
    	system("pause");
    	return 0;
    }

**运行结果**

1,2,3,5,7,8,10,15依此入队
    
    队列中的元素为：1  2  3  5  7  8  10 15
    
    队头元素为：1
    
    队头元素第一次出队：
    出队的元素为：1
    
    
    队头元素第二次出队：
    出队的元素为：2
    
    队列中的元素为：3  5  7  8  10 15
    队头元素为：3
    
    20入队
    25入队
    
    队列中的元素为：3  5  7  8  10 15 20 25
    请按任意键继续. . .