双链表数据结构

只看该作者 · 2019-6-30 18:07

双链表在RTOS操作系统中是很重要的一个数据结构，我们需要熟练使用双链表，其中包括以下，当然也可以自己再扩展，本人认为掌握这些足够应付RTOS。

只看该作者 · 2019-6-30 18:08

0. 节点与链表的定义
//链表节点类型
typedef struct _tNode
{
struct _tNode *prenode;  //该节点执行前一个节点
struct _tNode *nextnode; //该节点执行后一个节点
}tNode;
//定义链表结构体
typedef struct _tList
{
tNode  headNode;       //链表的头结点
uint32_t nodecount;    //链表的数量
}tList;

只看该作者 · 2019-6-30 18:08

1. 节点和链表的初始化
//节点初始化
void NodeInit(tNode *node)
{
node->nextnode = node;
node->prenode = node;
}
//链表初始化
void ListInit(tList *list)
{
list->headNode.nextnode = &(list->headNode);
list->headNode.prenode = &(list->headNode);
list->nodecount = 0;
}

只看该作者 · 2019-6-30 18:08

2. 返回链表中节点的个数
//返回链表节点数量
uint32_t ListCount(tList *list)
{
return list->nodecount;
}

只看该作者 · 2019-6-30 18:09

3. 返回链表首个节点
//返回链表的首个节点
tNode *ListFirst(tList *list)
{
tNode *node = (tNode *)0;
if(list->nodecount!=0)
{
node = list->headNode.nextnode;
}
return node;
}

只看该作者 · 2019-6-30 18:09

4. 返回链表最后一个节点
//返回链表的最后一个节点
tNode *ListLast(tList *list)
{
  tNode *node = (tNode *)0;
if(list->nodecount!=0)
{
   node = list->headNode.prenode;
}
  return node;
}

只看该作者 · 2019-6-30 18:09

5. 返回链表指定节点的前一个节点
//返回链表指定节点的前一节点
// list:查询链表
// node：参考节点
tNode *ListPre(tList *list,tNode *node)
{
  if(node->prenode == node)
{
   return (tNode *)0;
}
else
{
   return node->prenode;
}
}

只看该作者 · 2019-6-30 18:10

6. 返回链表指定节点的后一个节点
//返回链表中指定节点的后一个节点
// list:查询链表
// node：参考节点
tNode *ListNext(tList *list,tNode *node)
{
  if(node->nextnode ==node)
{
   return (tNode *)0;
}
else
{
   return node->nextnode;
}
}

只看该作者 · 2019-6-30 18:10

7. 清空链表中的所有节点
//删除链表中的所有节点
//list：需要删除的链表
void ListRemoveAll(tList *list)
{
int i;
tNode *nextNode;
//遍历所有节点
nextNode = list->headNode.nextnode;
for(i=list->nodecount;i!=0;i--)
{
//记录当前节点和下以节点
tNode *currentNode;
currentNode = nextNode;
nextNode = nextNode->nextnode;
//重置节点信息
currentNode->nextnode = currentNode;
currentNode->prenode = currentNode;
}
list->headNode.nextnode = &(list->headNode);
list->headNode.prenode = &(list->headNode);
list->nodecount = 0;
}

只看该作者 · 2019-6-30 18:11

8. 将指定节点添加到链表头部
//将指定节点添加到链表的头部
//list:待插入的链表
//node:待插入的节点
void ListAddFirst(tList *list,tNode *node)
{

node->prenode = &(list->headNode);
node->nextnode = list->headNode.nextnode;

list->headNode.nextnode->prenode = node;
list->headNode.nextnode = node;

list->nodecount++;
}

只看该作者 · 2019-6-30 18:12

9. 将指定节点添加到链表尾部
//将指定节点添加到链表尾部
//list：待插入的链表
//node：待插入的节点
void ListAddLast(tList *list,tNode *node)
{
node->prenode = list->headNode.prenode;
node->nextnode = &(list->headNode);

list->headNode.prenode->nextnode = node;
list->headNode.prenode = node;
list->nodecount++;
}

只看该作者 · 2019-6-30 18:12

10. 移除链表中的第一个节点
//移除链表中的第一个节点
//list：要移除的链表
//返回值：如果链表为空，返回0，否则返回第一个节点
tNode *tListRemoveFist(tList *list)
{
tNode *node = (tNode *)0;
if(list->nodecount != 0)
{
node =list->headNode.nextnode;

node->nextnode->prenode = &(list->headNode);
list->headNode.nextnode = node->nextnode;
list->nodecount--;
}
return node;
}

只看该作者 · 2019-6-30 18:12

11. 将指定节点插入到某一个节点后面
//在指定节点后插入节点
//list：需要插入的链表
//afternode：参考节点
//insertnode:待插入的节点
void ListInsertAfter(tList *list,tNode *afternode,tNode *insertnode)
{
   insertnode->prenode = afternode;
      insertnode->nextnode = afternode->nextnode;
      afternode->nextnode = insertnode;
      afternode->nextnode->prenode =insertnode;
      list->nodecount++;
}

只看该作者 · 2019-6-30 18:13

12. 将指定节点插入到某一节点前面
//在指定节前插入节点
//list：需要插入的链表
//beforenode：参考节点
//insertnode:待插入的节点
void ListInsertBefore(tList *list,tNode *beforenode,tNode *insertnode)
{
   insertnode->prenode = beforenode->prenode;
   insertnode->nextnode = beforenode;
   beforenode->prenode = insertnode;
   beforenode->prenode->nextnode = insertnode;
   list->nodecount++;
}

只看该作者 · 2019-6-30 18:13

13. 将指定节点从链表中移除
//将指定节点从链表中移除
//list:待移除的链表
//node：待移除的节点
void ListRemoveNode(tList *list,tNode *node)
{
node->prenode->nextnode = node->nextnode;
node->nextnode->prenode = node->prenode;
list->nodecount--;
}

只看该作者 · 2019-6-30 18:13

扯了这么多没用的，不如真枪实弹的测试一把，将刚刚我们写的对双链表的操作函数放到任务1中来测试一下，这里只要举几个函数，其余的留个大家来测试。

只看该作者 · 2019-6-30 18:14

tList  list;
tNode  node[10];

// 任务实现函数
void task1(void *param)
{
int i;
SetSysTickperiod(10);//以10ms为一个周期的时间片调度
for(;;)
{

/***************************该代码段用于测试链表***************************/
ListInit(&list); //初始化链表
for(i=0;i<10;i++)
{
   NodeInit(&node[i]);
ListAddFirst(&list,&node[i]); //往链表头部添加节点
}
for(i=0;i<10;i++)
{
   tListRemoveFist(&list); //删除链表的头节点
}

/***************************该代码段用于测试链表***************************/
task1Flag = 1;
TaskDelay(10);
task1Flag = 0;
TaskDelay(10);
}
}

只看该作者 · 2019-6-30 18:14

进入debug调试模式，在第一个for循环处设置断点。

只看该作者 · 2019-6-30 18:14

便于调试，将list链表添加到watch1窗口。

只看该作者 · 2019-6-30 18:15

在第二个for循环处设置断点，全速运行到该处，观察list结构的值，list中的链表节点的个数nodecount 已经增加到10个，初始化的10个节点已经被成功被链接到表中。