C语言数据结构链表队列的实现_C/C++

C语言数据结构链表队列的实现

2021-05-20 16:11MrSaber C/C++

这篇文章主要介绍了C语言数据结构链表队列的实现的相关资料,需要的朋友可以参考下

1.写在前面

　　队列是一种和栈相反的，遵循先进先出原则的线性表。

　　本代码是严蔚敏教授的数据结构书上面的伪代码的C语言实现代码。

　　分解代码没有包含在内的代码如下：

				?

									#include <stdio.h>

									#include <stdlib.h>

									#define OK 1

									#define ERROR 0

									typedef int QElemtype;

									typedef int status;

2.代码分解

2.1对队列和节点的结构定义

				?

									typedef struct QNode //对节点的结构定义

									{

									  QElemtype data;

									  struct QNode *next;

									}QNode,*QueuePtr;

									typedef struct{   //对队列的结构定义

									  QueuePtr head;

									  QueuePtr rear;

									}LinkQueue;

　　|说明：

　　　　1.队列的节点首先要保存元素，其次要指引下一个元素的位置，这是实现线性存储的基础也是关键。

　　　　2.队列中定义了两个节点指针，第一个 head 用来表示队头，允许移除元素。与之相反的是 rear 用来表示队尾，允许插入元素。

　　　　3.为什么这么定义？

2.2 初始化和回收队列

				?

									status initQueue(LinkQueue* que) //初始化队列

									{

									  que->head=que->rear=(QueuePtr)malloc(sizeof(QNode));

									  if(!que->head) //这段代码对队列里面的用户自定义数据类型进行了初始化

									    return ERROR;

									  return OK;

									}

									status destoryQueue(LinkQueue* que) //回收队列

									{

									  while(que->head)

									  {

									    que->rear = que->head->next;

									    free(que->head);

									    que->head=que->rear;

									  }

									  return OK;

									}

　　|说明：

　　　　1.初始化很简单，就是为队列内的两个重要节点分配空间。

　　　　2.队列的回收，思路很巧妙

				?

									循环条件是  队列的队头节点 head 存在

									　　　{

									　　　　　此处rear起到临时变量的作用，不断指向head->next的同时，释放head。这样处理可以干净的把包含头节点在内的队列清理干净。

									　　 　}

2.3 添加和删除元素

				?

									status enQueue(LinkQueue* que,QElemtype e)

									{

									  QueuePtr p = (QueuePtr)malloc(sizeof(QNode));

									  if(!p) //若未能申请到空间，便退出

									    return ERROR;

									  p->data=e;

									  p->next=NULL;

									  que->rear->next = p;

									  que->rear=p;

									  return OK;

									}

									status delQueue(LinkQueue* que,QElemtype *t)

									{

									  if(que->rear==que->head)

									    return ERROR; //队列为空

									  QueuePtr p = que->head->next;

									  *t=p->data;

									  que->head->next=p->next;

									  if(que->rear==p) //这个判断是 确保在清空队列的时候，让rear指针归位。

									    que->rear=que->head;

									  free(p);

									  return OK;

									}

　　|说明：

　　　　1.添加元素的思路：新建一个节点，并给其赋值（data，next）。让队列的尾部相接此节点，同时更新尾部节点。

　　　　2.删除元素的思路：首先判断节点是否为空？然后用临时节点从队头获取到第一个节点，即head->next，（我们的head节点并不保存元素），获取其地址后，更新队头节点所指的第一个节点获取值后释放该地址空间。

2.4 遍历队列和测试方法

				?

									status viewQueue(LinkQueue* que)

									{

									  if(que->rear == que->head)

									    return ERROR;

									  QueuePtr p =que->head->next;

									  while(p)

									  {

									    printf("val:%d",p->data);

									    p=p->next;

									  }

									  return OK;

									}

									int main(int argc, char **argv)

									{

									  LinkQueue myQueue;

									  initQueue(&myQueue);

									  for(int i=1;i<=5;i++)

									    enQueue(&myQueue,i);

									  viewQueue(&myQueue);

									  QElemtype a;

									  for(int i=0;i<5;i++)

									  {

									    delQueue(&myQueue,&a);

									    printf("%d\n",a);

									  }

									  destoryQueue(&myQueue);

									  printf("fuck !");  

									  return 0;

									}