RTOS双向链表数据结构

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

　　1.什么是双向链表

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

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

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

 typedef struct _tNode

 {

     int data;

     struct _tNode * pre;

     struct _tNode * next;

 }tNode;

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

 typedef struct _tList

 {

     tNode HeadNode;

     int NodeCount;

 }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 = ;

}

int tListCount(tList *list)//返回链表节点数量

{

    return list->NodeCount;

}

节点数据的插入和删除：

tNode* FirstNode(tList *list)//返回首节点

{

    tNode* node = (tNode*);

    if (list->NodeCount != )

    {

        node = list->HeadNode.next;

    }

    return node;

}

tNode* LastNode(tList *list)//返回最后一个节点

{

    tNode* node = (tNode*);

    if (list->NodeCount != )

    {

        node = list->HeadNode.pre;

    }

    return node;

}

tNode* tListPre(tList* list,tNode* node)//返回一个节点的前一个节点

{

    if (node->pre == node)

    {

        return (tNode*);

    }

    else

    {

        return node->pre;

    }

}

tNode* tListNext(tList* list, tNode* node)//返回节点的后一个节点

{

    if (node->next == node)

    {

        return (tNode*);

    }

    else

    {

        return node->next;

    }

}

void RemoveAll(tList* list)//删除所有节点

{

    tNode* CurrentNode, *NextNode;

    int count;

    NextNode = list->HeadNode.next;

    for (count=list->NodeCount;count > ;count --)

    {

        CurrentNode = NextNode;

        NextNode = CurrentNode->next;

        CurrentNode->pre = CurrentNode;

        CurrentNode->next = CurrentNode;

    }

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

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

    list->NodeCount = ;

}

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 *);

    if (list->HeadNode.next != )

    {

        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 = ;

    tListInit(&list);

    for (i = ; i < ; 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 = ; i < ; i++)

    {

        printf("%d ",node->data);

        node = node->next;

    }

    printf("\n");

    getch();

    return ;

}

实现效果为：

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

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

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

巴特西

RTOS双向链表数据结构

最新文章

热门文章