• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

链表-双向通用链表

开发技术 开发技术 2周前 (10-15) 15次浏览

目录
  • 前言
  • 概念
  • 笔录草稿
  • 双向链表
    • 节点、链表及信息访问 **
    • 操作代码及阐述
      • 1. 初始化链表
      • 2. 获取第一个节点
      • 3. 插入一个节点(头)
      • 4. 插入一个节点(尾)
      • 5. 删除一个节点
      • 6. 判断一个链表是否为空
      • 7. 获取到信息句柄的偏移 *
      • 8. 获取节点所在的信息句柄 *
      • 9. 遍历链表
      • 10. 遍历整个链表并获得信息句柄(宏) *
      • 11. 删除节点并重新初始化
    • 参考

前言

  • 20201014
  • 在阅读 RTOS LiteOS 内核源码时发现该内核使用的链表时通用链表,而 FreeRTOS 内核使用的时非通用链表,所以,有必要记录一下关于链表实现的笔记。
  • 以下内容为个人笔记,涉及一些非官方词汇,敬请谅解,谢谢。

概念

  • 正常表达

    • 链表:
      • 链表为 C 中一种基础的数据结构。
      • 看成环形晾衣架即可。
    • 节点:
      • 节点组成链表
  • 非通用链表自理解概念:节点携带信息

    • 链表:圆形的晾衣架
    • 节点:挂钩
      • 包含上一个
      • 下一个
      • 钩子等其它需要的信息
    • 袜子:挂在到 钩子 的东西
      • 包含被钩子
      • 袜子携带的信息
  • 通用链表自理解概念:信息携带节点

    • 链表:圆形的晾衣架
    • 节点:晾衣架圆形框的一截
      • 仅包含上一个
      • 下一个
    • 袜子:摆到晾衣架圆形框的一截上,使得节点成为袜子的一个成员指针变量
      • 袜子携带的信息
      • 信息中包含节点
  • 通用链表与非通用链表的区别

    • 通用链表节点内容很少一般只有 上一个下一个
    • 通用链表节点被放到信息结构体中,通过偏移找到所在的结构体(即是通过偏移找到袜子头)
    • 而非通用链表是在节点中携带信息结构体的指针的(即是节点就携带信息)。
    • 别人通俗理解,读者不必理会本小点
      • 通用链表是把袜子放到晾衣架的圆形圈上,袜子与圆形圈接触部分为袜子接待的节点。(信息携带节点
      • 非通用链表是。(节点携带信息
      • 通用链表的 链-线 穿插于袜子中(袜子即是信息
      • 非通用链表的 链-线 连在钩子,再由钩子钩袜子

笔录草稿

双向链表

  • 双向链表理解图
    链表-双向通用链表
  • 原理:链表包括 根节点普通节点
    • 根节点 主要管理链表的,一般包括
      • 上一个
      • 下一个
      • 存在多少个等信息
    • 普通节点 主要用于钩住袜子(即是携带信息)

节点、链表及信息访问 **

  • 节点
    • 成员仅有是一个和下一个
      链表-双向通用链表
/*
 *Structure of a node in a doubly linked list.
 */
typedef struct LSS_LIST
{
    struct LSS_LIST *pstPrev;            /**< Current node's pointer to the previous node*/
    struct LSS_LIST *pstNext;            /**< Current node's pointer to the next node*/
} LSS_LIST;
typedef struct LSS_LIST listItem_t;
  • 链表

    • 多个节点组成链表
      链表-双向通用链表
  • 信息访问

    • 操作通用链表的最核心、最重要部分是通过偏移获得信息句柄袜子头
      • 如下图 C 中的长度就是节点与信息句柄的偏移长度,只需知道 节点地址、信息类型(结构体类型)及成员名字(即是当前节点在结构体中的成员名字)即可获得信息句柄
        链表-双向通用链表
/*
 * @param item    Current node's pointer.
 * @param type    Structure name of type.
 * @param member  Member name of the doubly linked list in the structure.
 */
#define LSS_LIST_ENTRY(item, type, member)    
                    ((type *)((char *)(item) - (unsigned long)(&((type *)0)->member)))

操作代码及阐述

  • 以下只是通用链表的一些扩展例子,更多的可以自己象限+实现。

1. 初始化链表

  • 上一个指向自己
  • 下一个指向自己
/**
* @brief  链表初始化
* @param pstList:需要初始化的链表(节点)指针
* @retval none
* @author lzm
*/
void listInit(listItem_t *pstList)
{
    pstList->pstNext = pstList;
    pstList->pstPrev = pstList;
}

2. 获取第一个节点

  • 指向当前节点的下一个节点
  • 第一个即是下一个
/**
* @brief  获取第一个节点
* @param pstObject:当前节点指针
* @retval none
* @author lzm
*/
#define listGetFirst(pstObject) ((pstObject)->pstNext)

3. 插入一个节点(头)

  • 插入当前节点后面
    • 先处理需要插入的节点 外指向
    • 再处理需要插入的节点 内指向
/**
* @brief  插入当前节点后面
* @param pstList:链表(也是当前节点)
* @param pstNode:节点(需要插入的节点)
* @retval none
* @author lzm
*/
void listAdd(LSS_LIST *pstList, LSS_LIST *pstNode)
{
    pstNode->pstNext = pstList->pstNext;
    pstNode->pstPrev = pstList;
    pstList->pstNext->pstPrev = pstNode;
    pstList->pstNext = pstNode;
}

4. 插入一个节点(尾)

  • 插入链表尾部(即是插入当前节点的前面)
/**
* @brief  插入链表尾部
* @param pstList:链表(也是当前节点)
* @param pstNode:节点(需要插入的节点)
* @retval none
* @author lzm
*/
void listTailInsert(LSS_LIST *pstList, LSS_LIST *pstNode)
{
    listAdd(pstList->pstPrev, pstNode); // 把当前节点的前一个节点作为参考即可
}

5. 删除一个节点

  • 删除当前节点
    • 先处理需要删除的节点 内指向
    • 再处理需要删除的节点 外指向
/**
* @brief  删除当前节点
* @param pstNode:节点(需要删除的节点)
* @retval none
* @author lzm
*/
void listDelete(LSS_LIST *pstNode)
{
    pstNode->pstNext->pstPrev = pstNode->pstPrev;
    pstNode->pstPrev->pstNext = pstNode->pstNext;
    pstNode->pstNext = (LSS_LIST *)NULL;
    pstNode->pstPrev = (LSS_LIST *)NULL;
}

6. 判断一个链表是否为空

  • 判断该链表节点是否指向 初始化时的值即可。
/**
* @brief  删除当前节点
* @param pstNode:节点(需要删除的节点)
* @retval TRUE:链表为空
* @retval FALSE:链表不为空
* @author lzm
*/
bool listEmpty(LSS_LIST *pstNode)
{
    return (bool)(pstNode->pstNext == pstNode);
}

7. 获取到信息句柄的偏移 *

  • 通过 信息结构体类型、信息结构体中的成员名字 可以获得该 名字 到信息句柄的偏移。
/**
* @brief  获取到信息句柄的偏移
* @param type:信息结构体类型
* @param member:成员名字,即是字段(域)
* @retval 偏移长度(单位:byte)
* @author lzm
*/
#define getOffsetOfMenber(type, member)    ((uint32_t)&(((type *)0)->member))

8. 获取节点所在的信息句柄 *

  • 即是获取 节点 所在的信息结构体地址
/**
* @brief  获取节点所在的信息句柄
* @param type:信息结构体类型
* @param member:成员名字,即是字段(域)
* @retval 返回节点所在的信息句柄
* @author lzm
*/
#define getItemDataHandle(item, type, member) 
    ((type *)((char *)item - getOffsetOfMenber(type, member))) 

9. 遍历链表

/**
* @brief  删除节点并重新初始化
* @param pstList:需要重新初始化的链表节点
* @retval 
* @author lzm
*/
#define LIST_FOR_EACH(item, list)   
    for ((item) = (list)->pstNext; 
        (item) != (list); 
        (item) = (item)->pstNext)

10. 遍历整个链表并获得信息句柄(宏) *

  • 本宏并非为一个完整的语句,仅仅是一个 for 语句,做一个链表遍历
/**
* @brief 遍历整个链表并获得信息句柄(宏)
* @param handle:保存目标节点信息句柄
* @param item:需要遍历的链表(节点)
* @param type:信息类型(结构体名)
* @param member:该链表在 type 中的名字
* @retval 就是也该for语句
* @author lzm
*/
#define LIST_FOR_EACH_HANDEL(handle, list, type, member) 
    for (handle = getItemDataHandle((list)->pstNext, type, member); 
        &handle->member != (list); 
        handle = getItemDataHandle(handle->member.pstNext, type, member))

11. 删除节点并重新初始化

  • 先从链表中删除本节点
  • 再重新初始化本节点
void osListDel(LSS_LIST *pstPrevNode, LSS_LIST *pstNextNode)
{
    pstNextNode->pstPrev = pstPrevNode;
    pstPrevNode->pstNext = pstNextNode;
}
/**
* @brief  删除节点并重新初始化
* @param pstList:需要重新初始化的链表节点
* @retval 
* @author lzm
*/
void listDelInit(LSS_LIST *pstList)
{
    osListDel(pstList->pstPrev, pstList->pstNext);
    listInit(pstList);
}

参考

  • 链接
    • 我的Gitee
    • 非通用链表完整C语言源码
  • LiteOS 内核源码

喜欢 (0)