学习贺利坚老师课程,构建链式队列算法库
数据结构之自建算法库——链队（链式队列）_数据结构函数链队列的算法框架有哪些-CSDN博客文章浏览阅读6.2k次，点赞3次，收藏9次。本文针对数据结构基础系列网络课程(3)：栈和队列中第10课时队列的链式存储结构及其基本运算的实现。按照“0207将算法变程序”[视频]部分建议的方法，建设自己的专业基础设施算法库。链队算法库采用程序的多文件组织形式，包括两个文件： 1.头文件：liqueue.h，包含定义链队数据结构的代码、宏定义、要实现算法的函数的声明；#ifndef LIQUEUE_H_INCLUDED#de_数据结构函数链队列的算法框架有哪些https://blog.csdn.net/sxhelijian/article/details/48464501本人详细解析博客
队列的链式存储结构及其基本运算实现_队列结构及运算的实现-CSDN博客文章浏览阅读1.3k次，点赞5次，收藏7次。前面我们介绍了顺序队列的存储 ,是利用数组存储数据 , 然后删除节点数据和添加节点数据都是在数组完成的 , 有一个弊端就是 ,当我们操作的数量很大时 , 如果数组存储结构就很难队列操作了 ,那就需要利用链式存储结构了_队列结构及运算的实现https://blog.csdn.net/qq_57484399/article/details/127365820
版本更新日志:
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_Node; //链队数据节点定义typedef struct
{chain_queue_Node *chain_queue_front;chain_queue_Node *chain_queue_rear;}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 = (chain_queue *)malloc(sizeof(chain_queue));init_queue->chain_queue_front = NULL;init_queue->chain_queue_rear = 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->chain_queue_front;if(delete_Node != NULL){//记录后继节点follow_Node = delete_Node->next;//当后继节点不为空时, 往后走while(follow_Node != NULL){//释放当前节点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->chain_queue_rear == 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;//测量节点measure_Node = measure_queue->chain_queue_front;while(measure_Node != NULL){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->chain_queue_rear == NULL){enter_queue->chain_queue_front = enter_Node;//首尾指针指向入队节点enter_queue->chain_queue_rear = enter_Node;}else{//将入队节点,链接到队尾enter_queue->chain_queue_rear->next = enter_Node;//尾指针指向入队节点enter_queue->chain_queue_rear = enter_Node;}}
/**************************************************
(6)函数名: Out_chain_queue
功 能: 出队
参 数: chain_queue *&out_queue, ElemType &out_value
注 意: 出队则需要注意,队内是否有元素,有元素,也要区分一个元素和多个元素因为只有一个元素,出队,则需要同时修改首尾指针指向空多个元素,则只需要修改队首指针
返回值: bool:是否出队成功? true,成功,队内有元素:false,失败,队内无元素
**************************************************/
bool Out_chain_queue(chain_queue *&out_queue, ElemType &out_value)//出队
{chain_queue_Node *out_Node;//判断链队是否为空if(Empty_chain_queue(out_queue)){return false;}//锁定出队节点out_Node = out_queue->chain_queue_front;//队列只有一个节点if(out_queue->chain_queue_front == out_queue->chain_queue_rear){out_queue->chain_queue_front = out_queue->chain_queue_rear = NULL;}else //队列中有多个节点{out_queue->chain_queue_front = out_queue->chain_queue_front->next;}out_value = out_Node->data;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依次进链队元素a,b,c\n");Enter_chain_queue(test_queue,'a');Enter_chain_queue(test_queue,'b');Enter_chain_queue(test_queue,'c');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)依次进链队元素d,e,f\n");Enter_chain_queue(test_queue,'d');Enter_chain_queue(test_queue,'e');Enter_chain_queue(test_queue,'f');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;
}运行结果
