数据结构之线性表——队列的链式存储

逃离我推掉我的手 2022-05-29 13:28 218阅读 0赞

1 基本概念

队列是一种特殊的线性表，也可以用线性表的链式存储来模拟队列的链式存储。链队列的表述如下图所示:

![Center][]

2 链式队列存储的设计与实现

其中链式队列的实现是基于链式链表设计的基础上实现的，链表的链式存储设计实现请参考上篇

//LinkQueue.h
    #ifndef _LINKQUEUE_H_
    #define _LINKQUEUE_H_
    
    typedef void LinkQueue;
    
    //创建队列
    LinkQueue* LinkQueue_Create();
    //销毁队列
    void LinkQueue_Destroy(LinkQueue * queue);
    //清空队列
    void LinkQueue_Clear(LinkQueue * queue);
    //队列追加
    int LinkQueue_Append(LinkQueue * queue, void * item);
    //出队操作
    void* LinkQueue_Retrieve(LinkQueue * queue);
    //获取队列头
    void* LinkQueue_Header(LinkQueue * queue);
    //队列长度
    int LinkQueue_Length(LinkQueue * queue);
    #endif

//LinkQueue.c
    #include "LinkQueue.h"
    #include "LinkList.h"
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    /*
    基础知识：
    但是，平时使用的时候建议加上#include<string.h>（尤其在以下情况下）
    1、使用string类型
    2、使用cin、cout语句来输入输出string类型变量（注意，同时还需要 #include<iostream>）
    3、使用memset()、strlen()、strcpy()等函数时
    
    只要用到stdio里面定义的库函数，就要包含它
    这些库函数包括scanf，printf等等
    
    是引用stdlib.h头文件，即#include <stdlib.h>。这里的.h是不可缺少的。
    stdlib.h中，包含了C语言的一些常用库函数。如
    动态内存相关的malloc, realloc,zalloc,calloc,free等。
    随机数相关的rand,srand等。
    系统相关的system, getenv,setenv等。
    字符串转数值函数，atoi, atof,strtoul等。
    如果在代码中，调用了这个头文件中的函数或者宏定义，则需要引用该头文件。
    */
    //链式队列的结点定义
    typedef struct _tag_LinkQueueNode
    {
    	LinkListNode node;//包含着链表的结点
    	void *item;//自身的元素
    }TLinkQueueNode;
    
    //创建一个队列：相当于创建一个链表
    LinkQueue* LinkQueue_Create()
    {
    	return LinkList_Create();
    }
    //销毁队列
    void LinkQueue_Destroy(LinkQueue * queue)
    {
    	LinkQueue_Clear(queue);
    	LinkList_Destroy(queue);
    }
    
    //清空队列 需要显示的把队列中的所有结点 搞出来
    //释放每一个节点
    void LinkQueue_Clear(LinkQueue * queue)
    {
    	while (LinkQueue_Length(queue))
    	{
    		LinkQueue_Retrieve(queue);
    	}
    	LinkList_Clear(queue);
    }
    //队列追加:相当于在链表的尾部进行元素的添加
    int LinkQueue_Append(LinkQueue *queue, void *item)
    {
    	int ret = 0;
    	//把队列节点转化成链表节点
    	TLinkQueueNode *tmp = NULL;
    	tmp = (TLinkQueueNode *)malloc(sizeof(TLinkQueueNode));
    	if (tmp == NULL)
    	{
    		return -1;
    	}
    	memset(tmp,0,sizeof(TLinkQueueNode));//初始化
    	tmp->item = item;//节点转换适配过程
    	//需要把队列的业务结点 转化成链表的结点
    	ret = LinkList_Insert(queue, (LinkListNode *)tmp, LinkList_Length(queue));
    	if (ret != 0)
    	{
    		printf("func LinkList_Insert() error %d \n", ret);
    		if (tmp!=NULL)
    		{
    			free(tmp);
    		}
    		return ret;
    	}
    	return ret;
    }
    //出队操作 相当于 从线性表的头部删除元素
    void* LinkQueue_Retrieve(LinkQueue * queue)
    {
    	TLinkQueueNode *tmp = NULL;
    	void *item = NULL;
    	tmp = (TLinkQueueNode *)LinkList_Delete(queue, 0);
    	if (tmp == NULL)
    	{
    		printf("func LinkList_Delete() error\n");
    		return NULL;
    	}
    	//删除之前缓存
    	item = tmp->item;
    	if (tmp != NULL)
    	{
    	  free(tmp);//出队列时 不要忘记释放节点
    	}
    	return item;
    }
    //获取队列头 相当于从线性表的0号位置 拿数据
    void* LinkQueue_Header(LinkQueue * queue)
    {
    	TLinkQueueNode *tmp = NULL;
    	tmp = (TLinkQueueNode *)LinkList_Get(queue, 0);
    	if (tmp == NULL)
    	{
    		printf("func LinkList_Get() error \n");
    		return NULL;
    	}
    	return tmp->item;
    }
    //队列长度
    int LinkQueue_Length(LinkQueue * queue)
    {
    	return LinkList_Length(queue);
    }

//队列的链式存储实现与设计测试框架.c

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include "LinkQueue.h"
    
    int main()
    {
    	int ret = 0;
    	int a[5];
    	//1 建立一个空的队列
    	LinkQueue *linkqueue = NULL;
    	linkqueue = LinkQueue_Create();
    	if (NULL == linkqueue)
    	{
    		ret = -1;
    		printf("func err LinkQueue_Create():%d\n");
    		return ret;
    	}
    	//往队列添加元素
    	for (int i = 0; i < 5; i++)
    	{
    		a[i] = i + 1;
    		ret = LinkQueue_Append(linkqueue,&a[i]);
    		if (ret!=0)
    		{
    			ret = -2;
    			printf("func err LinkQueue_Append():%d\n");
    			return ret;
    		}
    	}
    	//队列的属性
    	printf("队列的长度:%d\n",LinkQueue_Length(linkqueue));
    	ret = *((int *)LinkQueue_Header(linkqueue));
    	printf("队列队长是:%d\n",ret);
    
    	//出队列 
    	while (LinkQueue_Length(linkqueue) > 0)
    	{
    		int tmp = *((int *)LinkQueue_Retrieve(linkqueue));
    		printf("%d\n",tmp);
    	}
    
    	//销毁队列
    	LinkQueue_Destroy(linkqueue);
    	system("pause");
    	return 0; 
    }

[Center]: /images/20220529/f9bf9c98c17f4c148236ddd0e7e8283b.png