原创 线性表 及在ucos中的应用 2(链表及应用)

1. 双链表

3.1 双链表的结点结构

#define  NULL  ((void*)0) 

typedef  struct  dnode

{

      int   datanode;

      struct dnode  *prior;

      struct dnode  *next;

}dlinklist;

3.2 插入运算

 int DLinkListInsert(dlinklist *head, int i, int x)

{

        int j=0;

        dlinklist *p;

        dlinklist *s;

        p=head;

        while(j<i-1 && p->next !=NULL)

        {

            p=p->next;

            j++;

        }

      if(j!=i-1)

      {

            return 0;

      }

      p=p->next; //p指向 要插入数据的后一个结点  but为什么是后一个结点，前一个结点不行吗?

      s=(dlinklist *) malloc(sizeof(dlinklist));

      s->datanode=x;

      s->prior = p->prior;

      p->prior->next =s;

      p->prior=s;

      s->next= p;

      return 1;

}

3.3 删除运算

int DLinkListDelet(dlinklist * head, int i)

{

        int j=0;

        dlinklist *p;

        p=head;

        while(j<i && p->next !=NULL)

        {

            p=p->next;    //p指向要删除结点

            j++;

        }

      if(j!=i|| i==0)   //带头结点的不能删去头结点

      {

            return 0;

      }

      p->prior->next=p->next;

      p->next->prior=p->prior;

      return 1;

}

2. Ucos-II中线性表的用法

就以任务控制链表为例进行描述：

OSTCBFreeList 及 OSTCBTbl[ ] 的定义

OS_TCB   xdata   *data   OSTCBFreeList; 

OS_TCB   xdata   *data   OSTCBList;

OS_TCB   OSTCBTbl[OS_MAX_TASKS + OS_N_SYS_TASKS];

在OSInit()中有对OSTCBFreelist的初始化操作

    OS_TCB    *ptcb1;

    OS_TCB    *ptcb2;

  ptcb1 = &OSTCBTbl[0];//查找任务控制块列表(0)的对应地址

  ptcb2 = &OSTCBTbl[1];

  for (i = 0; i < (OS_MAX_TASKS + OS_N_SYS_TASKS - 1); i++)

 { 

      ptcb1->OSTCBNext = ptcb2;

 ptcb1++;

 ptcb2++;

 }

ptcb1->OSTCBNext = (OS_TCB *)0;                          

OSTCBFreeList    = &OSTCBTbl[0];

当创建任务时调用OS_TCBInit()，此函数对OSTCB进行操作，它从OSTCBFreeList 单链表最前面取出一个结点， 给结构体中各参数赋值后前插到双链表OSTCBList。

当删除任务时，再将结点从OSTCBList删除，并放回 OSTCBFreeList。

在函数OSTimeTick()中扫描链表对结点结构体中的.OSTCBDly减一操作。

其他的链表还有：

OSEventFreeList

OSQFreeList

OSFlagFreeList

OSMemFreeList