链表文件夹C语言,FreeRTOS 笔记之③：数据结构-- 列表和表项（链表和节点）

太过爱你忘了你带给我的痛 2022-10-15 01:54 34阅读 0赞

1. C语言链表

1.1 单向链表

1.2 双向链表

1.3 链表的操作

1.4 链表与数组的对比

2. FreeRTOS中链表的实现

2.1 实现链表节点

2.2 实现链表根节点

2.2.1 根节点数据结构

2.2.2 链表根节点的初始化

2.2.3 将节点插入到链表的尾部

2.2.4 将节点按照升序排列插入到链表

2.2.5 将节点从链表删除

2.2.6 节点带参宏小函数

3. 链表节点插入实验

在FreeRTOS中存在着大量的基础数据结构列表和列表项的操作，要想读懂FreeRTOS的源码或者从0到1开始实现FreeRTOS，就必须弄懂列表和列表项的操作，其实也没那么难。

列表和列表项是直接从FreeRTOS源码的注释中的list 和 list item翻译过来的，其实就是对应我们C语言当中的链表和节点，在后续的讲解中，我们说的链表就是列表，节点就是列表项。

1. C语言链表

链表作为C语言中一种基础的数据结构，在平时写程序的时候用的并不多，但在操作系统里面使用的非常多。链表就好比一个圆形的晾衣架，晾衣架上面有很多钩子，钩子首尾相连。链表也是，链表由节点组成，节点与节点之间首尾相连。

晾衣架的钩子本身不能代表很多东西，但是钩子本身却可以挂很多东西。同样，链表也类似，链表的节点本身不能存储太多东西，或者说链表的节点本来就不是用来存储大量数据的，但是节点跟晾衣架的钩子一样，可以挂很多数据。

链表分为单向链表和双向链表，单向链表很少用，使用最多的还是双向链表。

1.1 单向链表

单向链表示意图。该链表中共有n个节点，前一个节点都有一个箭头指向后一个节点，首尾相连，组成一个圈。

节点本身必须包含一个节点指针，用于指向后一个节点，除了这个节点指针是必须有的之外，节点本身还可以携带一些私有信息，怎么携带？

节点都是一个自定义类型的数据结构，在这个数据结构里面可以有单个的数据、数组、指针数据和自定义的结构体数据类型等等信息。

struct node \{

struct node \*pNext;     /\* 指向链表的下一个节点 \*/

char cData;             /\* 单个数据 \*/

unsigned char array\[\];  /\* 数组数据 \*/

unsigned long \* ptr;    /\* 指针数据 \*/

struct usrStruct xData; /\* 自定义结构体数据 \*/

/\* ... ...  \*/

\};

除了struct node \*next 这个节点指针之外，剩下的成员都可以理解为节点携带的数据，但是这种方法很少用。通常的做法是节点里面只包含一个用于指向下一个节点的指针。要通过链表存储的数据内嵌一个节点即可，这些要存储的数据通过这个内嵌的节点即可挂接到链表中，就好像晾衣架的钩子一样，把衣服挂接到晾衣架中。

struct node \{

struct node \*pNext;     /\* 指向链表的下一个节点 \*/

\};

1.2 双向链表

双向链表与单向链表的区别就是节点中有两个节点指针，分别指向前后两个节点，其它完全一样。有关双向链表的文字描述参考单向链表小节即可。

1.3 链表的操作

链表常规的操作就是节点的插入和删除，为了顺利的插入，通常一条链表我们会人为地规定一个根节点，这个根节点称为生产者。通常根节点还会有一个节点计数器，用于统计整条链表的节点个数。

有关链表节点的删除和操作的代码讲解这里先略过，具体的可参考本章接下来的“FreeRTO中链表的实现”小节，在这个小节里面会有非常详细的讲解，这里我们先建立概念为主。

1.4 链表与数组的对比

两者的示意图

链表是通过节点把离散的数据链接成一个表，通过对节点的插入和删除操作从而实现对数据的存取。而数组是通过开辟一段连续的内存来存储数据，这是数组和链表最大的区别。

数组的每个成员对应链表的节点，成员和节点的数据类型可以是标准的C类型或者是用户自定义的结构体。

数组有起始地址和结束地址，而链表是一个圈，没有头和尾之分，但是为了方便节点的插入和删除操作会人为的规定一个根节点。

2. FreeRTOS中链表的实现

FreeRTOS中与链表相关的操作均在list.h和list.c这两个文件中实现，list.h第一次使用需要在include文件夹下面新建然后添加到工程freertos/source这个组文件，list.c第一次使用需要在freertos文件夹下面新建然后添加到工程freertos/source这个组文件。

2.1 实现链表节点

链表节点的数据结构在list.h中定义

/\* 节点结构体定义 \*/

struct xLIST\_ITEM

TickType\_t xItemValue;              /\* 辅助值，用于帮助节点做顺序排列 \*/

struct xLIST\_ITEM \*  pxNext;        /\* 指向链表下一个节点 \*/

struct xLIST\_ITEM \*  pxPrevious;    /\* 指向链表前一个节点 \*/

void \* pvOwner;                /\* 指向拥有该节点的内核对象，通常是TCB \*/

void \*  pvContainer;            /\* 指向该节点所在的链表 \*/

\};

typedef struct xLIST\_ITEM ListItem\_t;       /\* 节点数据类型重定义 \*/

链表节点初始化

/\* 节点初始化 \*/

void vListInitialiseItem( ListItem\_t \* const pxItem )

/\* 初始化该节点所在的链表为空，表示节点还没有插入任何链表 \*/

pxItem->pvContainer = NULL;

链表节点ListItem\_t总共有5个成员，但是初始化的时候只需将pvContainer初始化为空即可，表示该节点还没有插入到任何链表。

2.2 实现链表根节点

2.2.1 根节点数据结构

链表根节点的数据结构在list.h中定义

/\* 链表结构体定义 \*/

typedef struct xLIST

UBaseType\_t uxNumberOfItems;            /\* 链表节点计数器 \*/

ListItem\_t \*  pxIndex;            /\* 链表节点索引指针 \*/

MiniListItem\_t xListEnd;        /\* 链表最后一个节点 \*/

\} List\_t;

链表节点计数器，用于表示该链表下有多少个节点，根节点除外。 链表节点索引指针，用于遍历节点链表最后一个节点。我们知道，链表是首尾相连的，是一个圈，首就是尾，尾就是首，这里从字面上理解就是链表的最后一个节点，实际也就是链表的第一个节点，我们称之为生产者。该生产者的数据类型是一个精简的节点，也在list.h中定义

/\* mini节点结构体定义，作为双向链表的结尾

因为双向链表是首尾相连的，头即是尾，尾即是头 \*/

struct xMINI\_LIST\_ITEM

TickType\_t xItemValue;                      /\* 辅助值，用于帮助节点做升序排列 \*/

struct xLIST\_ITEM \*  pxNext;                /\* 指向链表下一个节点 \*/

struct xLIST\_ITEM \*  pxPrevious;            /\* 指向链表前一个节点 \*/

\};

typedef struct xMINI\_LIST\_ITEM MiniListItem\_t;      /\* 最小节点数据类型重定义 \*/

2.2.2 链表根节点的初始化

初始化函数在list.c中实现

/\* 链表根节点初始化 \*/

void vListInitialise( List\_t \* const pxList )

/\* 将链表索引指针指向最后一个节点 \*/

pxList->pxIndex = ( ListItem\_t \* ) &( pxList->xListEnd );

/\* 将链表最后一个节点的辅助排序的值设置为最大，确保该节点就是链表的最后节点 \*/

pxList->xListEnd.xItemValue = portMAX\_DELAY;

/\* 将最后一个节点的pxNext和pxPrevious指针均指向节点自身，表示链表为空 \*/

pxList->xListEnd.pxNext = ( ListItem\_t \* ) &( pxList->xListEnd );

pxList->xListEnd.pxPrevious = ( ListItem\_t \* ) &( pxList->xListEnd );

/\* 初始化链表节点计数器的值为0，表示链表为空 \*/

pxList->uxNumberOfItems = ( UBaseType\_t ) 0U;

将链表索引指针指向最后一个节点，即第一个节点，或者第零个节点更准确，因为这个节点不会算入节点计数器的值。 将链表最后(也可以理解为第一)一个节点的辅助排序的值设置为最大，确保该节点就是链表的最后节点(也可以理解为第一)将最后一个节点(也可以理解为第一)的pxNext和pxPrevious指针均指向节点自身，表示链表为空。初始化链表节点计数器的值为0，表示链表为空。

2.2.3 将节点插入到链表的尾部

将节点插入到链表的尾部(可以理解为头部)就是将一个新的节点插入到一个空的链表

/\* 将节点插入到链表的尾部 \*/

void vListInsertEnd( List\_t \* const pxList, ListItem\_t \* const pxNewListItem )

ListItem\_t \* const pxIndex = pxList->pxIndex;

pxNewListItem->pxNext = pxIndex;

pxNewListItem->pxPrevious = pxIndex->pxPrevious;

pxIndex->pxPrevious->pxNext = pxNewListItem;

pxIndex->pxPrevious = pxNewListItem;

/\* 记住该节点所在的链表 \*/

pxNewListItem->pvContainer = ( void \* ) pxList;

/\* 链表节点计数器++ \*/

( pxList->uxNumberOfItems )++;

2.2.4 将节点按照升序排列插入到链表

将节点按照升序排列插入到链表，如果有两个节点的值相同，则新节点在旧节点的后面插入

/\* 将节点按照升序排列插入到链表 \*/

void vListInsert( List\_t \* const pxList, ListItem\_t \* const pxNewListItem )

ListItem\_t \*pxIterator;

/\* 获取节点的排序辅助值 \*/

const TickType\_t xValueOfInsertion = pxNewListItem->xItemValue;

/\* 寻找节点要插入的位置 \*/

if( xValueOfInsertion == portMAX\_DELAY )

pxIterator = pxList->xListEnd.pxPrevious;

else

for( pxIterator = ( ListItem\_t \* ) &( pxList->xListEnd );

pxIterator->pxNext->xItemValue <= xValueOfInsertion;

pxIterator = pxIterator->pxNext )

/\* 没有事情可做，不断迭代只为了找到节点要插入的位置 \*/

pxNewListItem->pxNext = pxIterator->pxNext;

pxNewListItem->pxNext->pxPrevious = pxNewListItem;

pxNewListItem->pxPrevious = pxIterator;

pxIterator->pxNext = pxNewListItem;

/\* 记住该节点所在的链表 \*/

pxNewListItem->pvContainer = ( void \* ) pxList;

/\* 链表节点计数器++ \*/

( pxList->uxNumberOfItems )++;

2.2.5 将节点从链表删除

将节点从链表删除具体实现见代码。假设将一个有三个节点的链表中的中间节点节点删除

/\* 将节点从链表中删除 \*/

UBaseType\_t uxListRemove( ListItem\_t \* const pxItemToRemove )

/\* 获取节点所在的链表 \*/

List\_t \* const pxList = ( List\_t \* ) pxItemToRemove->pvContainer;

pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;

pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;

/\* Make sure the index is left pointing to a valid item. \*/

if( pxList->pxIndex == pxItemToRemove )

pxList->pxIndex = pxItemToRemove->pxPrevious;

/\* 初始化该节点所在的链表为空，表示节点还没有插入任何链表 \*/

pxItemToRemove->pvContainer = NULL;

/\* 链表节点计数器-- \*/

( pxList->uxNumberOfItems )--;

/\* 返回链表中剩余节点的个数 \*/

return pxList->uxNumberOfItems;

2.2.6 节点带参宏小函数

/\* 初始化节点的拥有者 \*/

\#define listSET\_LIST\_ITEM\_OWNER( pxListItem, pxOwner )        ( ( pxListItem )->pvOwner = ( void \* ) ( pxOwner ) )

/\* 获取节点拥有者 \*/

\#define listGET\_LIST\_ITEM\_OWNER( pxListItem )    ( ( pxListItem )->pvOwner )

/\* 初始化节点排序辅助值 \*/

\#define listSET\_LIST\_ITEM\_VALUE( pxListItem, xValue )    ( ( pxListItem )->xItemValue = ( xValue ) )

/\* 获取节点排序辅助值 \*/

\#define listGET\_LIST\_ITEM\_VALUE( pxListItem )    ( ( pxListItem )->xItemValue )

/\* 获取链表根节点的节点计数器的值 \*/

\#define listGET\_ITEM\_VALUE\_OF\_HEAD\_ENTRY( pxList )    ( ( ( pxList )->xListEnd ).pxNext->xItemValue )

/\* 获取链表的入口节点 \*/

\#define listGET\_HEAD\_ENTRY( pxList )    ( ( ( pxList )->xListEnd ).pxNext )

/\* 获取链表的第一个节点 \*/

\#define listGET\_NEXT( pxListItem )    ( ( pxListItem )->pxNext )

/\* 获取链表的最后一个节点 \*/

\#define listGET\_END\_MARKER( pxList )    ( ( ListItem\_t const \* ) ( &( ( pxList )->xListEnd ) ) )

/\* 判断链表是否为空 \*/

\#define listLIST\_IS\_EMPTY( pxList )    ( ( BaseType\_t ) ( ( pxList )->uxNumberOfItems == ( UBaseType\_t ) 0 ) )

/\* 获取链表的节点数 \*/

\#define listCURRENT\_LIST\_LENGTH( pxList )    ( ( pxList )->uxNumberOfItems )

/\* 获取链表节点的OWNER，即TCB \*/

\#define listGET\_OWNER\_OF\_NEXT\_ENTRY( pxTCB, pxList )                                        \\

\{                                                                                            \\

List\_t \* const pxConstList = ( pxList );                                                \\

/\* 节点索引指向链表第一个节点调整节点索引指针，指向下一个节点，

如果当前链表有N个节点，当第N次调用该函数时，pxInedex则指向第N个节点 \*/\\

( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;                            \\

/\* 当前链表为空 \*/                                                                       \\

if( ( void \* ) ( pxConstList )->pxIndex == ( void \* ) &( ( pxConstList )->xListEnd ) )    \\

\{                                                                                        \\

( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;                        \\

\}                                                                                        \\

/\* 获取节点的OWNER，即TCB \*/                                                             \\

( pxTCB ) = ( pxConstList )->pxIndex->pvOwner;                                             \\

\#define listGET\_OWNER\_OF\_HEAD\_ENTRY( pxList )  ( (&( ( pxList )->xListEnd ))->pxNext->pvOwner )

双向链表的插入和删除，理解起来会感觉比较绕，个人认为需要找好基准，这个基准就是根节点，根节点既可以是首，亦可以是尾，通常情况下，遍历整个链表都是从“头”开始，而这个“头”，就是根节点，因此，从这方面考虑的话，理解成头似乎更容易接受！

3. 链表节点插入实验

直接看示例代码，比较简单。

\#include "list.h"

/\*

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

\*                              全局变量

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

\*/

/\* 定义链表根节点 \*/

struct xLIST       List\_Test;

/\* 定义节点 \*/

struct xLIST\_ITEM  List\_Item1;

struct xLIST\_ITEM  List\_Item2;

struct xLIST\_ITEM  List\_Item3;

struct xLIST\_ITEM  List\_Item4;

struct xLIST\_ITEM  List\_Item5;

/\*

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

\*                                main函数

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

\*/

/\*

\* 注意事项：1、该工程使用软件仿真，debug需选择 Ude Simulator

\*           2、在Target选项卡里面把晶振Xtal(Mhz)的值改为25，默认是12，

\*              改成25是为了跟system\_ARMCM3.c中定义的\_\_SYSTEM\_CLOCK相同，确保仿真的时候时钟一致

\*/

int main(void)

/\* 链表根节点初始化 \*/

vListInitialise( &List\_Test );

/\* 节点1初始化 \*/

vListInitialiseItem( &List\_Item1 );

List\_Item1.xItemValue = 1;

//    List\_Item1.xItemValue = 3;

/\* 节点2初始化 \*/

vListInitialiseItem( &List\_Item2 );

List\_Item2.xItemValue = 2;

//    List\_Item2.xItemValue = 2;

/\* 节点3初始化 \*/

vListInitialiseItem( &List\_Item3 );

List\_Item3.xItemValue = 3;

//    List\_Item3.xItemValue = 1;

/\* 节点4初始化 \*/

vListInitialiseItem( &List\_Item4 );

List\_Item4.xItemValue = 4;

/\* 节点5初始化 \*/

vListInitialiseItem( &List\_Item5 );

List\_Item5.xItemValue = 5;

/\* 将节点插入链表，按照升序排列 \*/

vListInsert( &List\_Test, &List\_Item2 );

vListInsert( &List\_Test, &List\_Item1 );

vListInsert( &List\_Test, &List\_Item3 );

vListInsertEnd( &List\_Test, &List\_Item4 );

vListInsertEnd( &List\_Test, &List\_Item5 );

for(;;)

/\* 啥事不干 \*/

屏蔽代码解除屏蔽

https://download.csdn.net/download/xiewinter/11874146

链表文件夹C语言,FreeRTOS 笔记之③：数据结构-- 列表和表项（链表和节点）

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关数据结构之—顺序表和链表

相关 C语言数据结构 - 链表（双向链表实现）

相关数据结构之顺序表(C++和C语言)

相关数据结构之单链表、双向链表和循环链表

相关数据结构C语言代码实战03-顺序表和链表

相关链表文件夹C语言,FreeRTOS 笔记之③：数据结构-- 列表和表项（链表和节点）

相关 C语言链表数据结构实验之链表九：双向链表

相关 C语言链表数据结构实验之链表四：有序链表的归并

相关 C语言链表数据结构实验之链表一：顺序建立链表

相关 (数据结构)顺序表和链表(C实现)