引言
我们对于队列的处理要灵活运用, 我们只要是在一头进行加入元素, 一头进行出队元素, 那么这个数据结构的处理方式, 就可以被称作队列. 我们之前使用 首尾指针进行 队列的指引, 需要多次操作指针, 我们想了一种方式, 把队首和队尾指针链接起来, 然后只保留一个队尾指针, 队尾指针的下一个节点就是队头指针, 这样就可以减少指针的操作, 也是一种处理方式.
下面是详细解析博客
v1.0 在保留首尾指针的链队列基础上 , 把首尾指针链接成环, 去掉头指针, 尾指针起分隔作用, 从而定位首尾指针, 实现队列的操作方式
V1.0
功能函数
//(1)初始化链队
void Init_chain_queue(chain_queue *&init_queue);
//(2)销毁链队
void Destroy_chain_queue(chain_queue *&destroy_queue);
//(3)判断链队是否为空
bool Empty_chain_queue(chain_queue *judge_queue);
//(4)遍历计算并返回链队的元素个数
int Length_chain_queue(chain_queue *measure_queue);
//(5)入队
void Enter_chain_queue(chain_queue *&enter_queue, ElemType enter_elem);
//(6)出队
bool Out_chain_queue(chain_queue *&out_queue, ElemType &out_value);chain_queue.h头文件
#ifndef _CHAIN_QUEUE_H_INCLUDED_
#define _CHAIN_QUEUE_H_INCLUDED_
typedef char ElemType;
typedef struct chain_queue_Node
{
ElemType data;
struct chain_queue_Node *next;
}chain_queue; //链队数据节点定义
//(1)初始化链队
void Init_chain_queue(chain_queue *&init_queue);
//(2)销毁链队
void Destroy_chain_queue(chain_queue *&destroy_queue);
//(3)判断链队是否为空
bool Empty_chain_queue(chain_queue *judge_queue);
//(4)遍历计算并返回链队的元素个数
int Length_chain_queue(chain_queue *measure_queue);
//(5)入队
void Enter_chain_queue(chain_queue *&enter_queue, ElemType enter_elem);
//(6)出队
bool Out_chain_queue(chain_queue *&out_queue, ElemType &out_value);
#endif // _CHAIN_QUEUE_H_INCLUDED_
chain_queue.cpp库函数文件
#include <stdio.h>
#include <malloc.h>
#include "chain_queue.h"
/**************************************************
(1)函数名: Init_chain_queue
功 能: 初始化链队
参 数: chain_queue *&init_queue
注 意: 我们这里定义同类型的尾指针, 来指向同一个指针,并使用环形链表,尾指针分隔,相当于两端处理
返回值: 无
**************************************************/
void Init_chain_queue(chain_queue *&init_queue)
{
//节点置空即可(此指针起指引尾指针作用)
init_queue = NULL;
}
/**************************************************
(2)函数名: Destroy_chain_queue
功 能: 销毁链队
参 数: chain_queue *&destroy_queue:要进行销毁的队列
思 路: 和数组有区分,我们这里要遍历释放,释放的同时,要记录后继元素
注 意: 我们这里去掉了头指针, 所以尾指针的后继就替代了头指针的位置,相当于环形链表基础上
加入,尾指针来分隔, 实现两端处理
返回值: 无(只有成功,没有失败)
**************************************************/
void Destroy_chain_queue(chain_queue *&destroy_queue)
{
chain_queue_Node *delete_Node; //删除的节点
chain_queue_Node *follow_Node; //删除节点的后继线索节点
//初始要删除的节点, 指向首指针指向的节点
delete_Node = destroy_queue->next;
if(delete_Node != destroy_queue)
{
//记录后继节点
follow_Node = delete_Node->next;
//当后继节点不为空时, 往后走
while(follow_Node != destroy_queue)
{
//释放当前节点
free(delete_Node);
delete_Node = follow_Node;
follow_Node = delete_Node->next;
}
}
//否则
free(delete_Node);//销毁此节点
free(destroy_queue);//销毁首尾指针
}
/**************************************************
(3)函数名: Empty_chain_queue
功 能: 判断链队是否为空
参 数: chain_queue *judge_queue: 要进行判断是否为空的链队的指针
思 路: 尾指针是否都为空(尾指针代表队列)
注 意: 尾指针和队列尾指针,指向同一个节点,当尾指针为空时, 那么队列也为空
返回值: bool: 队列是否为空? true,空:false,非空
**************************************************/
bool Empty_chain_queue(chain_queue *judge_queue) //判断链队是否为空
{
return (judge_queue == NULL);
}
/**************************************************
(4)函数名: Length_chain_queue
功 能: 遍历计算并返回链队的元素个数
参 数:chain_queue *measure_queue: 要进行测量元素个数的链队
思 路: 定义节点,遍历链队, 同步跟随,计算个数
注 意: 对于链队的长度,我们这里是环形链表,所以要注意,避免首尾错位,参考环形链表计数方法
返回值: int: 返回元素个数
**************************************************/
int Length_chain_queue(chain_queue *measure_queue)
{
int counter = 0;
chain_queue_Node *measure_Node;//测量节点
if(Empty_chain_queue(measure_queue))
{
counter = 0;
}
else
if(measure_queue == measure_queue->next)
{
counter = 1;
}
else
{
counter = 1; //补上最后的队尾
measure_Node = measure_queue->next;//从队头开始算
while(measure_Node != measure_queue)
{
counter++;
measure_Node = measure_Node->next; //同步跟随
}
}
return counter;
}
/**************************************************
(5)函数名: Enter_chain_queue
功 能: 链队入队
参 数: (1)chain_queue *&enter_queue: 要入队的链队的指针地址
(2)ElemType enter_elem: 入队的元素值
思 路: 链队入队数量不限制,只是需要区分一下指针指引,当队内无元素, 则需要把队列节点指向本身
如果队列至少有一个元素, 则只需要管队尾节点指向新节点,新节点指向队尾,队尾指针移向新节点
返回值: 无
**************************************************/
void Enter_chain_queue(chain_queue *&enter_queue, ElemType enter_elem)
{
chain_queue_Node *enter_Node; //入队节点
enter_Node = (chain_queue_Node *)malloc(sizeof(chain_queue_Node));
enter_Node->data = enter_elem;
enter_Node->next = NULL;
//分如果一个节点和多个节点,指针指引问题
if(enter_queue == NULL)
{
enter_Node->next = enter_Node;
enter_queue = enter_Node;
}
else
{
enter_Node->next = enter_queue->next;
enter_queue->next = enter_Node;
enter_queue = enter_Node;
}
}
/**************************************************
(6)函数名: Out_chain_queue
功 能: 出队
参 数: chain_queue *&out_queue, ElemType &out_value
注 意: 出队则需要注意,队内是否有元素,
队空,则无法出队
队中有一个元素,则队列尾指针置空
两个元素或多个元素,
(1)锁定出队节点,传出出队元素数值,
(2)把队尾指向出队节点后继节点
(3) 释放出队节点空间
返回值: bool:是否出队成功? true,成功,队内有元素:false,失败,队内无元素
**************************************************/
bool Out_chain_queue(chain_queue *&out_queue, ElemType &out_value)//出队
{
chain_queue *out_Node;
//判断链队是否为空
if(Empty_chain_queue(out_queue))
{
return false;
}
//队列只有一个节点, 尾指针置空
if(out_queue->next == out_queue)
{
out_value = out_queue->data; //只有一个节点
free(out_queue);
out_queue = NULL;
}
else //队列中有多个节点
{
out_Node = out_queue->next;
out_value = out_Node->data;
out_queue->next = out_Node->next;
free(out_Node);
}
return true;
}
main.cpp测试函数
#include <stdio.h>
#include "chain_queue.h"
int main()
{
ElemType test_value;
chain_queue *test_queue;
printf("(1)初始化链队test_queue\n");
Init_chain_queue(test_queue);
printf("\n依次进链队元素x,y,g\n");
Enter_chain_queue(test_queue,'x');
Enter_chain_queue(test_queue,'y');
Enter_chain_queue(test_queue,'g');
printf("\n(3)链队为%s\n",(Empty_chain_queue(test_queue)?"空":"非空"));
if(Out_chain_queue(test_queue,test_value) == 0)
{
printf("\n队空,不能出队\n");
}
else
{
printf("\n(4)出队一个元素%c\n",test_value);
}
printf("\n(5)链队q的元素个数为:%d\n",Length_chain_queue(test_queue));
printf("\n(6)依次进链队元素N,B,6\n");
Enter_chain_queue(test_queue,'N');
Enter_chain_queue(test_queue,'B');
Enter_chain_queue(test_queue,'6');
printf("\n(7)链队test此时的元素个数是%d\n",Length_chain_queue(test_queue));
printf("\n(8)出链队序列:\n");
while(!Empty_chain_queue(test_queue))
{
Out_chain_queue(test_queue,test_value);
printf("\n%c\n",test_value);
}
printf("\n(9)释放队列\n");
Destroy_chain_queue(test_queue);
return 0;
}
运行截图:
