C语言实现简单的链表队列

使用C语言简单实现链表队列的操作

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define SIZE (4)

// 节点
typedef struct sNode
{
 struct sNode *prev;		// 前指针
 unsigned char data[SIZE];	// 数据
 struct sNode *next;		// 后指针
}SNODE;
// 链表队列
typedef struct sListQueue
{
 SNODE ListHead;		// 链表头节点
 SNODE ListTail;		// 链表尾节点
 int Num;			// 计数
}QLIST;
// 初始化链表队列
int InitQList(QLIST *qList);
// 从队列头部压入数据
int PutQList(QLIST *qList, unsigned char data[SIZE]);
// 从队列尾部取出数据
int PopQList(QLIST *qList, unsigned char *data);
// 清空队列
int ClearQList(QLIST *qList);
           

初始化：将头节点的后指针指向尾节点，尾节点的前指针指向头节点，计数值赋为0。注意：头尾节点不用于存储数据。代码实现如下：

// 初始化链表队列
int InitQList(QLIST *qList)
{
 if (NULL == qList)
 {
  return -1;
 }
 // 链表头节点的前指针赋值为空
 qList->ListHead.prev = NULL;
 // 链表头节点的后指针指向尾节点
 qList->ListHead.next = &(qList->ListTail);
 // 链表尾节点的前指针指向头节点
 qList->ListTail.prev = &(qList->ListHead);
 // 链表尾节点的后指针赋值为空
 qList->ListTail.next = NULL;
 // 其余数据清零
 memset(qList->ListHead.data, 0, SIZE);
 memset(qList->ListTail.data, 0, SIZE);
 qList->Num = 0;
 return 0;
}
           

输入数据，从队列头部压入数据：先分配一个节点（N）的内存空间存放数据，声明一个临时节点（T）记录头节点（H）的后一个节点。

将N插入到T和H中间，原本H的后指针是指向T的，现在需要改为指向N，同时N的前指针需要指向H；T的前指针原本指向H的，同样要改为指向N，N的后指针也要指向T。H和T之间的两个挂钩分别断开接向N，N的前后两个挂钩分别勾上H和T。代码如下：

// 从队列头部压入数据
int PutQList(QLIST *qList, unsigned char data[SIZE])
{
 if (!qList)
 {
  return -1;
 }
 // 先分配一个节点（N）的内存空间存放数据
 SNODE *node = (SNODE *)malloc(sizeof(SNODE));
 if (node == NULL)
 {
  return -2;
 }
 memset(node, 0, sizeof(SNODE));
 memcpy(node->data, data, SIZE);
 // 临时节点（T）记录头节点（H）的后一个节点
 SNODE *tem_node = qList->ListHead.next;
 // H 的后指针指向 N
 qList->ListHead.next = node;
 // N 的前指针指向 H
 node->prev = &(qList->ListHead);
 // T 的前指针指向 N
 tem_node->prev = node;
 // N 的后指针指向 T
 node->next = tem_node;
 // 队列计数加一
 qList->Num++;
 return 0;
}
           

取出数据，从队列尾部取出数据：尾节点记为TA，先声明两个节点，分别为TN和TP，TN记录TA的前一个节点，TP记录TN的前一个节点。取出数据则将TN的数据传出去，然后将TN从队列中移出。移出过程：将TA的前指针指向TP，TN的后指针指向空（TA和TN断开）；将TP的后指针指向TA，TN的前指针指向空（TA和TP断开）。注意，如果TP为空，那么TA的前一节点就是头节点，则队列无数据可提取。代码如下：

// 从队列尾部取出数据
int PopQList(QLIST *qList, unsigned char *data)
{
 if (!qList)
 {
  return -1;
 }
 // 尾节点记为TA
 // 声明节点TN，记录TA的前一个节点
 SNODE *tem_node = qList->ListTail.prev;
 // 声明节点TP，记录TN的前一个节点
 SNODE *tem_prev = tem_node->prev;
 // 如果TP为空，那么TA的前一节点就是头节点，则队列无数据可提取
 if (!tem_prev)
 {
  return -2;
 }
 // data不为空，则需要取出数据
 // data为空则表示不需要取出数据，直接删除最后一个有效数据
 if (data)
 {
  memcpy(data, tem_node->data, SIZE);
 }
 // TA和TN断开的过程：
 // 将TA的前指针指向TP
 qList->ListTail.prev = tem_prev;
 // TN的后指针指向空
 tem_node->next = NULL;
 // TA和TP断开的过程：
 // 将TP的后指针指向TA
 tem_prev->next = &(qList->ListTail);
 // TN的前指针指向空
 tem_node->prev = NULL;
 // 将TN节点内存释放
 free(tem_node);
 tem_node = NULL;
 // 队列计数减一
 qList->Num--;
 return 0;
}
           

清空队列，代码如下：

// 清空队列
int ClearQList(QLIST *qList)
{
 int ret = 0;
 if (!qList)
 {
  return -1;
 }
 do{
  // 队列无法法弹出有效数据后结束
  ret = PopQList(qList, NULL);
 } while (ret >= 0);
 return 0;
}
           

测试代码如下：

int main(void)
{
 int tick = 0, LogNum = 0;
 int recv = 0, ret = 0;
 QLIST list = { 0 };
 InitQList(&list);
 // 测试输入后弹出
 while (tick < 5)
 {
  tick++;
  ret = PutQList(&list, (unsigned char*)&tick);
  if (ret == 0)
  {
   printf("%d.输入数据成功：%d\n", LogNum++, tick);
  }
  else if (ret == -2)
  {
   printf("%d.输入数据失败；失败数据是：%d\n", LogNum++, tick);
  }
  ret = PopQList(&list, (unsigned char*)&recv);
  if (ret == 0)
  {
   printf("%d.获取数据成功：%d\n", LogNum++, recv);
  }
  else if (ret == -2)
  {
   printf("%d.获取数据失败......\n", LogNum++, recv);
  }
 }
 printf("%d.队列剩余数据个数：%d\n", LogNum++, list.Num);
 // 测试连续输入7个数
 while (tick < 5 + 7)
 {
  tick++;
  ret = PutQList(&list, (unsigned char*)&tick);
  if (ret == 0)
  {
   printf("%d.输入数据成功：%d\n", LogNum++, tick);
  }
  else if (ret == -2)
  {
   printf("%d.输入数据失败；失败数据是：%d\n", LogNum++, tick);
  }
 }
 printf("%d.队列剩余数据个数：%d\n", LogNum++, list.Num);
 // 测试连续弹出10个数
 while (tick < 5 + 7 + 10)
 {
  tick++;
  ret = PopQList(&list, (unsigned char*)&recv);
  if (ret == 0)
  {
   printf("%d.获取数据成功：%d\n", LogNum++, recv);
  }
  else if (ret == -2)
  {
   printf("%d.获取数据失败......\n", LogNum++, recv);
  }
 }
 printf("%d.队列剩余数据个数：%d\n", LogNum++, list.Num);
 // 继续输入3个数
 while (tick < 5 + 7 + 10 + 3)
 {
  tick++;
  ret = PutQList(&list, (unsigned char*)&tick);
  if (ret == 0)
  {
   printf("%d.输入数据成功：%d\n", LogNum++, tick);
  }
  else if (ret == -2)
  {
   printf("%d.输入数据失败；失败数据是：%d\n", LogNum++, tick);
  }
 }
 printf("%d.队列剩余数据个数：%d\n", LogNum++, list.Num);
 // 清空队列
 ClearQList(&list);
 printf("%d.队列剩余数据个数：%d\n", LogNum++, list.Num);
 printf("测试完成\n");
 getchar();
 return 0;
}