嵌入式系统与单片机|技术阅读
登录|注册

您现在的位置是：嵌入式系统与单片机 > 技术阅读 > 超级精简系列之六:超级精简的单向链表实现

超级精简系列之六:超级精简的单向链表实现

2024-06-22

一. 前言

链表可以说是嵌入式开发中最常见的数据结构了,RTOS中的任务管理,定时器管理,堆管理等几乎都是用的链表实现。所以我们超级精简系列也有必要准备一个自己趁手的链表的”轮子”,为以后实现自己的超级精简的堆管理，定时器管理等做准备。

二. 实现过程

2.1 数据结构

定义节点值类型,这样可以根据需求配置不同的类型。

typedef uint32_t list_itemvalue_t; /**< 节点值类型 */

定义函数返回值类型枚举

/**
* \enum list_res_e
* 返回结果枚举.
*/
typedef enum
{
 LIST_OK = 0, /**< 成功 */
 LIST_PARAM_ERR = 1, /**< 参数错误 */
 LIST_NOTEXIST_ERR = 2, /**< 不存在 */
}list_res_e;

定义节点结构

/**
* \struct list_item
* 链表节点结构体.
*
* 通过next_item_pst连接后续节点.
*/
struct list_item
{
 struct list_item *next_item_pst; /**< 指向下一个节点,构成单向链表 */
 list_itemvalue_t itemvalue_t; /**< 节点值,链表按照节点值从小到大排列;值一样时遵循FIFO,即插入到后面,从前面移出. */
 void* itemobj_p; /**< 指向节点负载对象(有效数据),比如TCB等 */
};

重定义节点结构

typedef struct list_item list_item_st; /**< 重定义节点类型 */

定义链表机构

/**
* \struct list_st
* 链表结构体.
** 链表结构体实际上是一个简化的节点结构体,
* 即只有next_item_pst成员用于指向头节点
* 而链表节点的next_item_pst指向后续节点,
* 从这个意义上说也可以理解链表结构体本身是头节点,它是固定的
* 后续接的节点可以动态改变.
*/
typedef struct
{
 list_item_st *next_item_pst; /**< next_item_pst用于指向头节点,链表为空时next_item_pst为0. */
}list_st;

2.2 接口定义

根据一般需求定义以下接口

插入到末尾,和从末尾出列

插入到开头,和从开头出列

出列指定的节点

根据值从小到达顺序插入

出列指定值的节点

/**
* \fn res_e list_enqueuetail(list_st *list_pst, list_item_st *item_pst)
** \brief 插入节点到链表尾,如果链表为空更新链表指针.
** \note list_pst->next_item_pst 可能更新.
** \param[in,out] list_pst \ref list_st 链表指针.
* \param[in] item_pst \ref list_item_st 待插入的节点指针.
** \retval 0 成功.
* \retval 1 参数错误.
*/
list_res_e list_enqueuetail(list_st *list_pst, list_item_st *item_pst);
/**
* \fn list_item_st* list_dequeuetail(list_st *list_pst)
** \brief 移除链表的尾节点,返回移除的节点的指针.
** \note list_pst->next_item_pst 更新.
** \param[in,out] list_pst \ref list_st 链表指针.
** \retval 0 链表为空或者参数错误.
* \retval list_item_st* 移出的节点(尾节点)的指针.
*/
list_item_st* list_dequeuetail(list_st *list_pst);
/**
* \fn res_e list_enqueuehead(list_st *list_pst, list_item_st *item_pst)
** \brief 插入节点到链表头,更新链表指针.
** \note list_pst->next_item_pst 更新.
** \param[in,out] list_pst \ref list_st 链表指针.
* \param[in] item_pst \ref list_item_st 待插入的节点.
** \retval 0 成功.
* \retval 1 参数错误.
*/
list_res_e list_enqueuehead(list_st *list_pst, list_item_st *item_pst);
/**
* \fn list_item_st *list_dequeuehead(list_st *list_pst)
** \brief 移出链表头节点,更新链表指针.
** \note list_pst->next_item_pst 更新.
** \param[in,out] list_pst \ref list_st 链表指针.
* \param[in] item_pst \ref list_item_st 节点指针.
** \retval 0 空链表或参数错误.
* \retval list_item_st* 移出的节点指针.
*/
list_item_st *list_dequeuehead(list_st *list_pst);
/**
* \fn res_e list_dequeueitem(list_st *list_pst, list_item_st *item_pst)
** \brief 移出指定节点,更新链表指针.
** \note list_pst->next_item_pst 更新.
** \param[in,out] list_pst \ref list_st 链表指针.
* \param[in] item_pst \ref list_item_st 节点指针.
** \retval 1 参数错误或者指定节点不属于链表.
* \retval 0 成功.
*/
list_res_e list_dequeueitem(list_st *list_pst, list_item_st *item_pst);
/**
* \fn res_e list_enqueueitemvalue(list_st *list_pst, list_item_st *item_pst)
** \brief 按指定节点值从小到大插入到链表,如果值大小一样则插入到后面,更新链表指针.
** \note list_pst->next_item_pst 更新.
** \param[in,out] list_pst \ref list_st 链表指针.
* \param[in] item_pst \ref list_item_st 节点指针.
** \retval 1 参数错误.
* \retval 0 成功.
*/
list_res_e list_enqueueitemvalue(list_st *list_pst, list_item_st *item_pst);
/**
* \fn list_item_st *list_dequeueitemvalue(list_st *list_pst, list_itemvalue_t value)
** \brief 移出链表中节点值小于等于指定值的节点,并更新链表指针,如果所有节点值都大于指定值或者链表为空则返回0.
** 由于节点值本身是按照从小到大的顺序排列所以只需要比较头节点即可.
** \note list_pst->next_item_pst 更新.
** \param[in,out] list_pst \ref list_st 链表指针.
* \param[in] value \ref list_itemvalue_t 节点值.
** \retval 0 参数错误或者没有节点数值小于等于指定值的节点.
* \retval \ref list_item_st 指向移出的节点.
*/
list_item_st *list_dequeueitemvalue(list_st *list_pst, list_itemvalue_t value);

2.3 实现

将指定节点插入到链表尾的实现。

先进行了参数检查。

这里使用了指向指针的指针，初始化为指向头节点的指针地址。

即list_item_st **curr=&(list_pst -> next_item_pst)。

这样直接修改*curr则对应的直接修改的指针的指向。

然后遍历到尾巴

while(*curr != 0)不为空继续往后走

curr = &((*curr) -> next_item_pst);

最后直接修改尾巴指针指向的新的节点即可

*curr = item_pst;

注:该实现方法参照了linus在某邮件内点评的链表实现方法，有兴趣的可以去搜索原内容。

list_res_e list_enqueuetail(list_st *list_pst, list_item_st *item_pst)
{
 list_item_st **curr; /* curr用于遍历节点的next_item_pst成员的地址 其值*curr为next_item_pst即节点指针 */
 /* 参数检查 */
 if((list_pst == 0) || (item_pst == 0))
 {
 return LIST_PARAM_ERR;
 }
 /* curr初始化为链表指针的next_item_pst成员的地址,此时*curr表示头节点指针.
 * *curr用于遍历节点指针,从头节点开始,链表list_pst可理解为简化的节点.
 */
 curr = &(list_pst -> next_item_pst);
/* 遍历到链表尾 */
 while(*curr != 0)
 {
 /* 1) 如果链表为空,即list_pst -> next_item_pst == 0(*curr==0),
 * 则直接更新链表头*curr(list_pst -> next_item_pst) = item_pst 指向待插入的节点;
 * 2) 如果链表不为空,则使用*curr遍历节点,直到某个节点的next_item_pst为0,说明该节点即为尾节点,
 * 修改该尾节点的后续节点为待插入的节点item_pst.
 */
 curr = &((*curr) -> next_item_pst);
 }
 /* 某个节点的next_item_pst(*curr)为0则表示他是尾结点,
 * 空链表本身也可以表示为尾结点,找到尾节点后,插入新节点到该节点后.
 */
 *curr = item_pst;
 return LIST_OK;
}

从尾部出列节点的实现，和插入的实现思想差不多，

找到尾巴节点，指向空*curr = 0;

list_item_st* list_dequeuetail(list_st *list_pst)
{
 list_item_st **curr = 0; /* curr用于遍历节点的next_item_pst成员的地址 其值为next_item_pst */
 list_item_st *item = 0; /* 移出的节点指针(尾节点指针) */
 /* 参数检查 */
 if(list_pst == 0)
 {
 return 0;
 }
 /* curr初始化为链表指针的next_item_pst成员的地址,此时*curr表示头节点指针.
 * *curr用于遍历节点指针,从头节点开始,链表list_pst可理解为简化的节点.
 */
 curr = &(list_pst -> next_item_pst);
 /* 1) 如果链表为空,即list_pst -> next_item_pst == 0(*curr==0),则直接返回0;
 * 2) 如果链表不为空,则使用*curr遍历节点,直到某个节点的next_item_pst成员为0,
 * 说明该节点即为尾节点, 修改该节点的后续节点为0,即截断尾结点.
 */
 while(*curr != 0)
 {
 item = *curr;
if((item -> next_item_pst) != 0)
{
 /* 当前节点有后续节点继续
 */
 curr = &(item -> next_item_pst);
 }
 else
 {
 /* 当前节点无后续节点,当前节点即为尾节点.*curr表示的是前一个节点的next_item_pst.
 * 修改前一个节点的next_item_pst即给*curr赋值.
 */
 *curr = 0;
 }
 }
 /* item指向的是尾节点,返回该尾节点. */
 return item;
}

插入节点到头的实现，这个就比较简单了，链表头指向新的节点，新的节点后续节点指向原来的头即可。

list_res_e list_enqueuehead(list_st *list_pst, list_item_st *item_pst)
{
 /* 参数检查 */
 if((list_pst == 0) || (item_pst == 0))
 {
 return LIST_PARAM_ERR;
 }
 item_pst->next_item_pst = list_pst->next_item_pst; /* 原来的头节点成为了新头节点后续节点 */
 list_pst->next_item_pst = item_pst; /* 链表头是插入的新的节点 */
 return LIST_OK;
}

从头出列节点，也比较简单，如果是空链表则返回空，否则返回链表头，新的链表头指向原来链表头的后续节点。

list_item_st *list_dequeuehead(list_st *list_pst)
{
 list_item_st* pitem = 0;
 /* 参数检查 */
 if(list_pst == 0)
 {
 return 0;
 }
 pitem = list_pst -> next_item_pst; /* 头节点 */
 if(pitem != 0)
 {
 list_pst -> next_item_pst = pitem -> next_item_pst; /* 链表指针指向头节点的下一节点,即移出头节点*/
 }
 else
 {
 /* 空链表,直接返回0 */
 }
 return pitem;
}


出列指定节点，直接遍历，比较匹配时返回指定节点。

还是利用了指针的指针直接修改指针的方式。

list_res_e list_dequeueitem(list_st *list_pst, list_item_st *item_pst)
{
 list_item_st **curr = 0; /* curr用于遍历节点的next_item_pst成员的地址 其值为next_item_pst */
 list_item_st *item = 0; /* 遍历节点指针 */
 /* 参数检查 */
 if((list_pst == 0) || (item_pst == 0))
 {
 return LIST_PARAM_ERR;
 }
 /* curr初始化为链表指针的next_item_pst成员的地址,此时*curr表示头节点指针.
 * *curr用于遍历节点指针,从头节点开始,链表list_pst可理解为简化的节点.
 */
 curr = &(list_pst ->next_item_pst);
 /* 1) 如果链表为空,即list_pst -> next_item_pst == 0(*curr == 0),则直接返回0;
 * 2) 如果链表不为空,则使用*curr遍历节点,直到某个节点为需要移出的节点.
 */
 while(*curr != 0)
 {
 item = *curr;
/* item表示当前节点 item -> next_item_pst表示当前节点后续节点 */
if(item != item_pst)
{
 /* 当前节点不是待移出节点,继续遍历.
 */
 curr = &(item -> next_item_pst);
 }
 else
 {
 /* 当前节点是需要删除的节点,
 * curr表示上一节点的next_item_pst的地址,其值*curr表示当前节点,
 * 同时也可以给*curr赋值改变上一节点的next_item_pst值,即改变上一节点的后续节点,这里通过指向next_item_pst的指针去操作
 * next_item_pst是精妙所在,因为不需要获取当前节点的指针再通过next_item_pst成员去访问,而是直接通过指向next_item_pst的指针curr去操作,
 * 即可修改链接的后续指针.
 */
 *curr = item -> next_item_pst; /* 将上一节点的next_item_pst即(*curr)赋值为待移出节点的下一节点,即移除待移出节点 */
 break;
 }
 }
 /* item指向的是移出的节点.
 * 如果移出的节点等于待移出的节点返回成功0,
 * 否则返回失败1 */
 return (item == item_pst) ? LIST_OK : LIST_NOTEXIST_ERR;
}


根据值出列

list_item_st *list_dequeueitemvalue(list_st *list_pst, list_itemvalue_t value)
{
 list_item_st* pitem = 0;
 /* 参数检查 */
 if(list_pst == 0)
 {
 return 0;
 }
 pitem = list_pst -> next_item_pst; /* 链表头 */
 if(pitem != 0)
 {
 if((pitem -> itemvalue_t) <= value)
 {
 list_pst -> next_item_pst = pitem -> next_item_pst; /* 移出链表头 */
 }
 else
 {
 pitem = 0;
 /* 链表头节点数值大于指定值,返回0 */
 }
 }
 else
 {
 /* 空链表返回0 */
 }
 return pitem;
}


根据值大小插入

list_res_e list_enqueueitemvalue(list_st *list_pst, list_item_st *item_pst)
{
 list_item_st **curr = 0; /* curr用于遍历链表节点的next_item_pst成员的地址 其值*curr为next_item_pst */
 list_item_st *item = 0; /* 插入到item指向的节点之前 */
 list_itemvalue_t value; /* 当前节点值 */
 /* 参数检查 */
 if((list_pst == 0) || (item_pst == 0))
 {
 return LIST_PARAM_ERR;
 }
 value = item_pst -> itemvalue_t;
 /* curr初始化为链表指针的next_item_pst成员的地址,此时*curr表示头节点指针.
 * *curr用于遍历节点指针,从头节点开始,链表list_pst可理解为简化的节点.
 */
 curr = &(list_pst -> next_item_pst);
 /* 1) 如果链表为空,即list_pst -> next_item_pst == 0(*curr==0),则直接插入,插入节点称为头节点;
 * 2) 如果链表不为空,则使用*curr遍历节点,直到某个节点*curr的值大于待插入节点值.则插入到该节点之前.
 */
 while(*curr != 0)
 {
 item = *curr;
/* item表示当前节点 item -> next_item_pst表示当前节点后续节点 */
if(item -> itemvalue_t <= value)
{
 /* 当前节点值小于等于待插入节点值,所以不应该插入该节点之前,继续遍历.
 */
 curr = &(item -> next_item_pst);
 }
 else
 {
 /* 当前节点值大于待插入节点的值,则插入到当前节点*curr前 */
 break;
 }
 }
 /* 插入到*curr之前
 */
 item_pst -> next_item_pst = *curr; /* 插入到*curr之前,待插入节点的后续节点是*curr */
 *curr = item_pst; /* 前一个节点的后续节点是待插入节点 */
 return LIST_OK;
}

三. 测试

List_main.c

#include <stdint.h>
#include <stdio.h>
#include "list.h"
list_res_e list_printf(list_st *list){
 list_item_st *item;
 if(list == 0)
 {
 return LIST_PARAM_ERR;
 }
 if(list->next_item_pst == 0)
 {
 printf("NULL");
 }
 item = list->next_item_pst;
 while(item != 0)
 {
 printf("itemval:%d,itemname=%s\r\n",item->itemvalue_t,(char*)(item->itemobj_p));
 item = item -> next_item_pst;
 }
 return LIST_OK;
}
int main(void){
 list_st list = {0};
 list_item_st *item = 0;
 list_item_st list_item0 = {(list_item_st*)0,1,"item0"};
 list_item_st list_item1 = {0,2,"item1"};
 list_item_st list_item2 = {0,3,"item2"};
 list_item_st list_item3 = {0,4,"item3"};
 list_item_st list_item4 = {0,5,"item4"};
 list_item_st list_item5 = {0,6,"item5"};
 list_item_st list_item6_0 = {0,0,"item6-0"};
 list_item_st list_item7_0 = {0,0,"item7-0"};
 list_item_st list_item8_0 = {0,0,"item8-0"};
 list_item_st list_item9_4 = {0,4,"item9-4"};
 list_item_st list_item10_4 = {0,4,"item10-4"};
 list_item_st list_item11_4 = {0,4,"item11-4"};
 list_item_st list_item12_10 = {0,10,"item12-10"};
 list_item_st list_item13_10 = {0,10,"item13-10"};
 printf("\r\n");
 printf("================\r\n");
 printf("list_enqueuetail test\r\n");
 printf("================\r\n");
 list_enqueuetail(&list,&list_item0);
 list_printf(&list);
 printf("\r\n");
 list_enqueuetail(&list,&list_item1);
 list_printf(&list);
 printf("\r\n");
 list_enqueuetail(&list,&list_item2);
 list_printf(&list);
 printf("\r\n");
 list_enqueuetail(&list,&list_item3);
 list_printf(&list);
 printf("\r\n");
 list_enqueuetail(&list,&list_item4);
 list_printf(&list);
 printf("\r\n");
 list_enqueuetail(&list,&list_item5);
 list_printf(&list);
 printf("\r\n");
 printf("================\r\n");
 printf("list_dequeuetail test\r\n");
 printf("================\r\n");
 do{
 item = list_dequeuetail(&list);
 if(item)
 {
 printf("remove\r\n");
 printf("%s\r\n",(char*)(item->itemobj_p));
 printf("remain\r\n");
 list_printf(&list);
printf("\r\n");
 }
 }while(item != 0);
 printf("\r\n");
 printf("================\r\n");
 printf("list_enqueuehead test\r\n");
 printf("================\r\n");
 list_enqueuehead(&list,&list_item0);
 list_printf(&list);
 printf("\r\n");
 list_enqueuehead(&list,&list_item1);
 list_printf(&list);
 printf("\r\n");
 list_enqueuehead(&list,&list_item2);
 list_printf(&list);
 printf("\r\n");
 list_enqueuehead(&list,&list_item3);
 list_printf(&list);
 printf("\r\n");
 list_enqueuehead(&list,&list_item4);
 list_printf(&list);
 printf("\r\n");
 list_enqueuehead(&list,&list_item5);
 list_printf(&list);
 printf("\r\n");
 printf("================\r\n");
 printf("list_dequeuehead test\r\n");
 printf("================\r\n");
 do{
 item = list_dequeuehead(&list);
 if(item)
 {
 printf("remove\r\n");
 printf("%s\r\n",(char*)(item->itemobj_p));
 printf("remain\r\n");
 list_printf(&list);
printf("\r\n");
 }
 }while(item != 0);
 list_enqueuehead(&list,&list_item0);
 list_enqueuehead(&list,&list_item1);
 list_enqueuehead(&list,&list_item2);
 list_enqueuehead(&list,&list_item3);
 list_enqueuehead(&list,&list_item4);
 list_enqueuehead(&list,&list_item5);
 list_printf(&list);
 printf("================\r\n");
 printf("list_dequeueitem test\r\n");
 printf("================\r\n");
 list_res_e res = list_dequeueitem(&list, &list_item3);
 if(res==0)
 {
 printf("remove\r\n");
 printf("%s\r\n",(char*)(list_item3.itemobj_p));
 printf("remain\r\n");
 list_printf(&list);
printf("\r\n");
 }
 else
 {
 printf("remove list_item3 err\r\n");
 }
 res = list_dequeueitem(&list, &list_item0);
 if(res==0)
 {
 printf("remove\r\n");
 printf("%s\r\n",(char*)(list_item0.itemobj_p));
 printf("remain\r\n");
 list_printf(&list);
printf("\r\n");
 }
 else
 {
 printf("remove list_item0 err\r\n");
 }
 res = list_dequeueitem(&list, &list_item5);
 if(res==0)
 {
 printf("remove\r\n");
 printf("%s\r\n",(char*)(list_item5.itemobj_p));
 printf("remain\r\n");
 list_printf(&list);
printf("\r\n");
 }
 else
 {
 printf("remove list_item5 err\r\n");
 }
 res = list_dequeueitem(&list, &list_item3);
 if(res==0)
 {
 printf("remove\r\n");
 printf("%s\r\n",(char*)(list_item3.itemobj_p));
 printf("remain\r\n");
 list_printf(&list);
printf("\r\n");
 }
 else
 {
 printf("remove list_item3 err\r\n");
 }
 res = list_dequeueitem(&list, &list_item1);
 if(res==0)
 {
 printf("remove\r\n");
 printf("%s\r\n",(char*)list_item1.itemobj_p);
 printf("remain\r\n");
 list_printf(&list);
printf("\r\n");
 }
 else
 {
 printf("remove list_item1 err\r\n");
 }
 res = list_dequeueitem(&list, &list_item4);
 if(res==0)
 {
 printf("remove\r\n");
 printf("%s\r\n",(char*)(list_item4.itemobj_p));
 printf("remain\r\n");
 list_printf(&list);
printf("\r\n");
 }
 else
 {
 printf("remove list_item4 err\r\n");
 }
 res = list_dequeueitem(&list, &list_item2);
 if(res==0)
 {
 printf("remove\r\n");
 printf("%s\r\n",(char*)(list_item2.itemobj_p));
 printf("remain\r\n");
 list_printf(&list);
printf("\r\n");
 }
 else
 {
 printf("remove list_item2 err\r\n");
 }
 printf("================\r\n");
 printf("list_enqueueitemvalue test\r\n");
 printf("================\r\n");
 res = list_enqueueitemvalue(&list, &list_item0);
 if(res==0)
 {
 list_printf(&list);
printf("\r\n");
 }
 else
 {
 printf("enqueueitemvalue list_item0 err\r\n");
 }
 res = list_enqueueitemvalue(&list, &list_item1);
 if(res==0)
 {
 list_printf(&list);
printf("\r\n");
 }
 else
 {
 printf("enqueueitemvalue list_item1 err\r\n");
 }
 res = list_enqueueitemvalue(&list, &list_item2);
 if(res==0)
 {
 list_printf(&list);
printf("\r\n");
 }
 else
 {
 printf("enqueueitemvalue list_item2 err\r\n");
 }
 res = list_enqueueitemvalue(&list, &list_item3);
 if(res==0)
 {
 list_printf(&list);
printf("\r\n");
 }
 else
 {
 printf("enqueueitemvalue list_item3 err\r\n");
 }
 res = list_enqueueitemvalue(&list, &list_item4);
 if(res==0)
 {
 list_printf(&list);
printf("\r\n");
 }
 else
 {
 printf("enqueueitemvalue list_item4 err\r\n");
 }
 res = list_enqueueitemvalue(&list, &list_item5);
 if(res==0)
 {
 list_printf(&list);
printf("\r\n");
 }
 else
 {
 printf("enqueueitemvalue list_item5 err\r\n");
 }
 res = list_enqueueitemvalue(&list, &list_item6_0);
 if(res==0)
 {
 list_printf(&list);
printf("\r\n");
 }
 else
 {
 printf("enqueueitemvalue list_item6_0 err\r\n");
 }
 res = list_enqueueitemvalue(&list, &list_item7_0);
 if(res==0)
 {
 list_printf(&list);
printf("\r\n");
 }
 else
 {
 printf("enqueueitemvalue list_item7_0 err\r\n");
 }
 res = list_enqueueitemvalue(&list, &list_item8_0);
 if(res==0)
 {
 list_printf(&list);
printf("\r\n");
 }
 else
 {
 printf("enqueueitemvalue list_item8_0 err\r\n");
 }
 res = list_enqueueitemvalue(&list, &list_item9_4);
 if(res==0)
 {
 list_printf(&list);
printf("\r\n");
 }
 else
 {
 printf("enqueueitemvalue list_item9_4 err\r\n");
 }
 res = list_enqueueitemvalue(&list, &list_item10_4);
 if(res==0)
 {
 list_printf(&list);
printf("\r\n");
 }
 else
 {
 printf("enqueueitemvalue list_item10_4 err\r\n");
 }
 res = list_enqueueitemvalue(&list, &list_item11_4);
 if(res==0)
 {
 list_printf(&list);
printf("\r\n");
 }
 else
 {
 printf("enqueueitemvalue list_item11_4 err\r\n");
 }
 res = list_enqueueitemvalue(&list, &list_item12_10);
 if(res==0)
 {
 list_printf(&list);
printf("\r\n");
 }
 else
 {
 printf("enqueueitemvalue list_item12_10 err\r\n");
 }
 res = list_enqueueitemvalue(&list, &list_item13_10);
 if(res==0)
 {
 list_printf(&list);
printf("\r\n");
 }
 else
 {
 printf("enqueueitemvalue list_item13_10 err\r\n");
 }
 printf("================\r\n");
 printf("list_dequeueitemvalue test\r\n");
 printf("================\r\n");
 for(int i=15;i>=0;i--)
 {
 item = list_dequeueitemvalue(&list, i);
 if(item !=0 )
 {
 printf("dequeueitemvalue %s\r\n",(char*)(item -> itemobj_p));
 list_printf(&list);
printf("\r\n");
 }
 else
 {
 printf("dequeueitemvalue %d err\r\n",i);
 }
 }
 return 0;
}

编译gcc list.c list_main.c -o list.exe

运行list.exe打印如下

================
list_enqueuetail test
================
itemval:1,itemname=item0
itemval:1,itemname=item0
itemval:2,itemname=item1
itemval:1,itemname=item0
itemval:2,itemname=item1
itemval:3,itemname=item2
itemval:1,itemname=item0
itemval:2,itemname=item1
itemval:3,itemname=item2
itemval:4,itemname=item3
itemval:1,itemname=item0
itemval:2,itemname=item1
itemval:3,itemname=item2
itemval:4,itemname=item3
itemval:5,itemname=item4
itemval:1,itemname=item0
itemval:2,itemname=item1
itemval:3,itemname=item2
itemval:4,itemname=item3
itemval:5,itemname=item4
itemval:6,itemname=item5
================
list_dequeuetail test
================
remove
item5
remain
itemval:1,itemname=item0
itemval:2,itemname=item1
itemval:3,itemname=item2
itemval:4,itemname=item3
itemval:5,itemname=item4
remove
item4
remain
itemval:1,itemname=item0
itemval:2,itemname=item1
itemval:3,itemname=item2
itemval:4,itemname=item3
remove
item3
remain
itemval:1,itemname=item0
itemval:2,itemname=item1
itemval:3,itemname=item2
remove
item2
remain
itemval:1,itemname=item0
itemval:2,itemname=item1
remove
item1
remain
itemval:1,itemname=item0
remove
item0
remain
NULL
================
list_enqueuehead test
================
itemval:1,itemname=item0
itemval:2,itemname=item1
itemval:1,itemname=item0
itemval:3,itemname=item2
itemval:2,itemname=item1
itemval:1,itemname=item0
itemval:4,itemname=item3
itemval:3,itemname=item2
itemval:2,itemname=item1
itemval:1,itemname=item0
itemval:5,itemname=item4
itemval:4,itemname=item3
itemval:3,itemname=item2
itemval:2,itemname=item1
itemval:1,itemname=item0
itemval:6,itemname=item5
itemval:5,itemname=item4
itemval:4,itemname=item3
itemval:3,itemname=item2
itemval:2,itemname=item1
itemval:1,itemname=item0
================
list_dequeuehead test
================
remove
item5
remain
itemval:5,itemname=item4
itemval:4,itemname=item3
itemval:3,itemname=item2
itemval:2,itemname=item1
itemval:1,itemname=item0
remove
item4
remain
itemval:4,itemname=item3
itemval:3,itemname=item2
itemval:2,itemname=item1
itemval:1,itemname=item0
remove
item3
remain
itemval:3,itemname=item2
itemval:2,itemname=item1
itemval:1,itemname=item0
remove
item2
remain
itemval:2,itemname=item1
itemval:1,itemname=item0
remove
item1
remain
itemval:1,itemname=item0
remove
item0
remain
NULL
itemval:6,itemname=item5
itemval:5,itemname=item4
itemval:4,itemname=item3
itemval:3,itemname=item2
itemval:2,itemname=item1
itemval:1,itemname=item0
================
list_dequeueitem test
================
remove
item3
remain
itemval:6,itemname=item5
itemval:5,itemname=item4
itemval:3,itemname=item2
itemval:2,itemname=item1
itemval:1,itemname=item0
remove
item0
remain
itemval:6,itemname=item5
itemval:5,itemname=item4
itemval:3,itemname=item2
itemval:2,itemname=item1
remove
item5
remain
itemval:5,itemname=item4
itemval:3,itemname=item2
itemval:2,itemname=item1
remove list_item3 err
remove
item1
remain
itemval:5,itemname=item4
itemval:3,itemname=item2
remove
item4
remain
itemval:3,itemname=item2
remove
item2
remain
NULL
================
list_enqueueitemvalue test
================
itemval:1,itemname=item0
itemval:1,itemname=item0
itemval:2,itemname=item1
itemval:1,itemname=item0
itemval:2,itemname=item1
itemval:3,itemname=item2
itemval:1,itemname=item0
itemval:2,itemname=item1
itemval:3,itemname=item2
itemval:4,itemname=item3
itemval:1,itemname=item0
itemval:2,itemname=item1
itemval:3,itemname=item2
itemval:4,itemname=item3
itemval:5,itemname=item4
itemval:1,itemname=item0
itemval:2,itemname=item1
itemval:3,itemname=item2
itemval:4,itemname=item3
itemval:5,itemname=item4
itemval:6,itemname=item5
itemval:0,itemname=item6-0
itemval:1,itemname=item0
itemval:2,itemname=item1
itemval:3,itemname=item2
itemval:4,itemname=item3
itemval:5,itemname=item4
itemval:6,itemname=item5
itemval:0,itemname=item6-0
itemval:0,itemname=item7-0
itemval:1,itemname=item0
itemval:2,itemname=item1
itemval:3,itemname=item2
itemval:4,itemname=item3
itemval:5,itemname=item4
itemval:6,itemname=item5
itemval:0,itemname=item6-0
itemval:0,itemname=item7-0
itemval:0,itemname=item8-0
itemval:1,itemname=item0
itemval:2,itemname=item1
itemval:3,itemname=item2
itemval:4,itemname=item3
itemval:5,itemname=item4
itemval:6,itemname=item5
itemval:0,itemname=item6-0
itemval:0,itemname=item7-0
itemval:0,itemname=item8-0
itemval:1,itemname=item0
itemval:2,itemname=item1
itemval:3,itemname=item2
itemval:4,itemname=item3
itemval:4,itemname=item9-4
itemval:5,itemname=item4
itemval:6,itemname=item5
itemval:0,itemname=item6-0
itemval:0,itemname=item7-0
itemval:0,itemname=item8-0
itemval:1,itemname=item0
itemval:2,itemname=item1
itemval:3,itemname=item2
itemval:4,itemname=item3
itemval:4,itemname=item9-4
itemval:4,itemname=item10-4
itemval:5,itemname=item4
itemval:6,itemname=item5
itemval:0,itemname=item6-0
itemval:0,itemname=item7-0
itemval:0,itemname=item8-0
itemval:1,itemname=item0
itemval:2,itemname=item1
itemval:3,itemname=item2
itemval:4,itemname=item3
itemval:4,itemname=item9-4
itemval:4,itemname=item10-4
itemval:4,itemname=item11-4
itemval:5,itemname=item4
itemval:6,itemname=item5
itemval:0,itemname=item6-0
itemval:0,itemname=item7-0
itemval:0,itemname=item8-0
itemval:1,itemname=item0
itemval:2,itemname=item1
itemval:3,itemname=item2
itemval:4,itemname=item3
itemval:4,itemname=item9-4
itemval:4,itemname=item10-4
itemval:4,itemname=item11-4
itemval:5,itemname=item4
itemval:6,itemname=item5
itemval:10,itemname=item12-10
itemval:0,itemname=item6-0
itemval:0,itemname=item7-0
itemval:0,itemname=item8-0
itemval:1,itemname=item0
itemval:2,itemname=item1
itemval:3,itemname=item2
itemval:4,itemname=item3
itemval:4,itemname=item9-4
itemval:4,itemname=item10-4
itemval:4,itemname=item11-4
itemval:5,itemname=item4
itemval:6,itemname=item5
itemval:10,itemname=item12-10
itemval:10,itemname=item13-10
================
list_dequeueitemvalue test
================
dequeueitemvalue item6-0
itemval:0,itemname=item7-0
itemval:0,itemname=item8-0
itemval:1,itemname=item0
itemval:2,itemname=item1
itemval:3,itemname=item2
itemval:4,itemname=item3
itemval:4,itemname=item9-4
itemval:4,itemname=item10-4
itemval:4,itemname=item11-4
itemval:5,itemname=item4
itemval:6,itemname=item5
itemval:10,itemname=item12-10
itemval:10,itemname=item13-10
dequeueitemvalue item7-0
itemval:0,itemname=item8-0
itemval:1,itemname=item0
itemval:2,itemname=item1
itemval:3,itemname=item2
itemval:4,itemname=item3
itemval:4,itemname=item9-4
itemval:4,itemname=item10-4
itemval:4,itemname=item11-4
itemval:5,itemname=item4
itemval:6,itemname=item5
itemval:10,itemname=item12-10
itemval:10,itemname=item13-10
dequeueitemvalue item8-0
itemval:1,itemname=item0
itemval:2,itemname=item1
itemval:3,itemname=item2
itemval:4,itemname=item3
itemval:4,itemname=item9-4
itemval:4,itemname=item10-4
itemval:4,itemname=item11-4
itemval:5,itemname=item4
itemval:6,itemname=item5
itemval:10,itemname=item12-10
itemval:10,itemname=item13-10
dequeueitemvalue item0
itemval:2,itemname=item1
itemval:3,itemname=item2
itemval:4,itemname=item3
itemval:4,itemname=item9-4
itemval:4,itemname=item10-4
itemval:4,itemname=item11-4
itemval:5,itemname=item4
itemval:6,itemname=item5
itemval:10,itemname=item12-10
itemval:10,itemname=item13-10
dequeueitemvalue item1
itemval:3,itemname=item2
itemval:4,itemname=item3
itemval:4,itemname=item9-4
itemval:4,itemname=item10-4
itemval:4,itemname=item11-4
itemval:5,itemname=item4
itemval:6,itemname=item5
itemval:10,itemname=item12-10
itemval:10,itemname=item13-10
dequeueitemvalue item2
itemval:4,itemname=item3
itemval:4,itemname=item9-4
itemval:4,itemname=item10-4
itemval:4,itemname=item11-4
itemval:5,itemname=item4
itemval:6,itemname=item5
itemval:10,itemname=item12-10
itemval:10,itemname=item13-10
dequeueitemvalue item3
itemval:4,itemname=item9-4
itemval:4,itemname=item10-4
itemval:4,itemname=item11-4
itemval:5,itemname=item4
itemval:6,itemname=item5
itemval:10,itemname=item12-10
itemval:10,itemname=item13-10
dequeueitemvalue item9-4
itemval:4,itemname=item10-4
itemval:4,itemname=item11-4
itemval:5,itemname=item4
itemval:6,itemname=item5
itemval:10,itemname=item12-10
itemval:10,itemname=item13-10
dequeueitemvalue item10-4
itemval:4,itemname=item11-4
itemval:5,itemname=item4
itemval:6,itemname=item5
itemval:10,itemname=item12-10
itemval:10,itemname=item13-10
dequeueitemvalue item11-4
itemval:5,itemname=item4
itemval:6,itemname=item5
itemval:10,itemname=item12-10
itemval:10,itemname=item13-10
dequeueitemvalue item4
itemval:6,itemname=item5
itemval:10,itemname=item12-10
itemval:10,itemname=item13-10
dequeueitemvalue 4 err
dequeueitemvalue 3 err
dequeueitemvalue 2 err
dequeueitemvalue 1 err
dequeueitemvalue 0 err

四. 总结

以上实现了简单的单向链表,后面基于此可以实现更多的组件。比如定时器，堆管理等。


查看全文