RTOS双向链表数据结构

　　在学习RTOS操作系统时，在任务优先级设置时用到了双向链表，说实话数据结构的东西只是停留在大学上课阶段，并未实践过，在操作系统中看得云里雾里，遂将其单独拿来了进行了一下思考，经过一个上午的摸索逐渐领会到了其中的精华。

　　1.什么是双向链表

百度百科：双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

　　此表中包含两个重要信息：链表结构，节点结构

　　首先定义好节点的结构体：

1 typedef struct _tNode
2 {
3     int data;
4     struct _tNode * pre;
5     struct _tNode * next;
6 }tNode;

然后在定义链表的结构体：

1 typedef struct _tList
2 {
3     tNode HeadNode;
4     int NodeCount;
5 }tList;

　　这个结构体的作用就是可以在工程中创建多个这样的链表结构，结构体里包含头结点HeadNode和此链表节点的数量NodeCount用来对链表进行操作的定位。头结点并不保存数据，只是提供指向节点的指针用来连接整个链表。所以在操作链表时可以很快地进行各种操作。在操作链表时只需要对完成对节点地添加和删除即可，头结点保持不变！

　　基本初始化：

void tNodeInit(tNode *Node)
{
    Node->pre = Node;
    Node->next = Node;
}

void tListInit(tList *list)//初始化链表 
{
    list->HeadNode.pre = &(list->HeadNode);
    list->HeadNode.next = &(list->HeadNode);
    list->NodeCount = 0;
}

int tListCount(tList *list)//返回链表节点数量  
{
    return list->NodeCount;
}

节点数据的插入和删除：

tNode* FirstNode(tList *list)//返回首节点
{
    tNode* node = (tNode*)0;
    if (list->NodeCount != 0)
    {
        node = list->HeadNode.next;
    }
    return node;
}

tNode* LastNode(tList *list)//返回最后一个节点
{
    tNode* node = (tNode*)0;
    if (list->NodeCount != 0)
    {
        node = list->HeadNode.pre;
    }
    return node;
}

tNode* tListPre(tList* list,tNode* node)//返回一个节点的前一个节点
{
    if (node->pre == node)
    {
        return (tNode*)0;
    }
    else
    {
        return node->pre;
    }
}

tNode* tListNext(tList* list, tNode* node)//返回节点的后一个节点
{
    if (node->next == node)
    {
        return (tNode*)0;
    }
    else
    {
        return node->next;
    }
}

void RemoveAll(tList* list)//删除所有节点
{
    tNode* CurrentNode, *NextNode;
    int count;

    NextNode = list->HeadNode.next;
    for (count=list->NodeCount;count > 0;count --)
    {
        CurrentNode = NextNode;
        NextNode = CurrentNode->next;

        CurrentNode->pre = CurrentNode;
        CurrentNode->next = CurrentNode;
    }

    list->HeadNode.pre = &(list->HeadNode);
    list->HeadNode.next = &(list->HeadNode);

    list->NodeCount = 0;
}

void tListHeadAdd(tList *list,tNode *node)//在头部添加节点
{
    node->next = list->HeadNode.next;
    node->pre = list->HeadNode.next->pre;

    list->HeadNode.next = node;
    list->HeadNode.next->pre = node;

    list->NodeCount ++;
    
}


void tListLastAdd(tList *list,tNode *node)//在最后添加节点
{
    node->pre = list->HeadNode.pre;
    node->next = list->HeadNode.pre->next;

    list->HeadNode.pre->next = node;
    list->HeadNode.pre = node;

    list->NodeCount ++;
}

tNode* RemoveFirstNode(tList *list)//移除第一个节点
{
    tNode *node = (tNode *)0;
    if (list->HeadNode.next != 0)
    {
        node = list->HeadNode.next;

        node->next->pre = &(list->HeadNode);
        list->HeadNode.next = node->next;

        list->NodeCount --;

        free(node);
    }
    else
    {
        return node;
    }
}


void tListInsertAfter(tList * list, tNode * nodeAfter, tNode * nodeToInsert)//在一个节点后添加一个节点
{
    nodeToInsert->next = nodeAfter->next;
    nodeToInsert->pre = nodeAfter;

    nodeAfter->next->pre = nodeToInsert;
    nodeAfter->next = nodeToInsert;

    list->NodeCount ++;
}

void tListRemove(tList * list, tNode * node)//移除节点
{
    node->pre->next = node->next;
    node->next->pre = node->pre;

    free(node);

    list->NodeCount --;

}

在这个双向链表的实现过程中可以很好地实现队列操作，先进先出概念如这样验证：

int main()
{
    tList list;
    tNode *node;
    int i = 0;

    tListInit(&list);

    for (i = 0; i < 5; i++)
    {
        node = (tNode*)malloc(sizeof(tNode));

        printf("Please input the number:");
        scanf_s("%d",&node->data);

        tListLastAdd(&list, node);
    }
    
    node = FirstNode(&list);

    printf("List is:");
    for (i = 0; i < 5; i++)
    {
        printf("%d ",node->data);
        node = node->next;
    }
    printf("
");
    getch();
    return 0;
}

实现效果为：

　　在这个基础上还可以用于多种其他用处！

　　PS:今天是自己第一天也是第一次写博客，在实现的过程中遇到很多问题也有很多想法，本来想一一记录但是发现写起来还是很艰辛，也许我现在就是一个小菜鸟，但是希望能够通过自己的努力一点一滴地积累逐渐成长，希望这个博客可以被我一直写下去！

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　写于广东海悟科技有限公司 2017-11-10 22:29:50