4.4 链表

链表是一种复杂的数据结构，一般语言不提供此类数据结构。例如，C语言就是通过指针和结构体来形成链表的。其特点是在结构体中有一成员变量是指针，用来指向自身的结构体。

例如：

Struct Point
{ int I;
Struct Point * next;
Char p[20];
}

前面µCOS中os_tcb的例子，就是一个链表。

其中，struct os_tcb *OSTCBNext; 就是指向自身的结构体。如果把前面的例子在内存中部署，就应该是图4.3所示的样子。

双向链表也叫双链表，是链表的一种特殊形式，含有两个指针域，一个向后指，一个向前指，从而形成一个双向的链接。双向链表可以用做同数据类型数据的集合，不占用连续内存空间，不需要大量的连续存储空间。与一般链表相比，由于有前后向指针，检索速度较快，尤其是查找邻近节点耗费的时间较短。双向链表在嵌入式操作系统中用得很多，因为这个方式对内存的要求比较低，而且非常方便查找。

下面对链表的操作进行总结，以便在设计和学习嵌入式操作系统代码时参考。

1.线性表的双向链表存储结构定义

typedef struct DuLNode
{
   ElemType data;
   struct DuLNode *prior,*next;
}DuLNode,*DuLinkList;

2.带头节点的双向循环链表的空链表产生

void InitList(DuLinkList *L)
{ /* 产生空的双向循环链表L */
    *L=(DuLinkList)malloc(sizeof(DuLNode));
    if(*L)
        (*L)->next=(*L)->prior=*L;
    else
        exit(OVERFLOW);
}

3.销毁双向循环链表中L节点

void DestroyList(DuLinkList *L)
{
    DuLinkList q,p=(*L)->next; /* p指向第一个节点*/
    while(p!=*L) /* p没到表头*/
    {
        q=p->next;
        free(p);
        p=q;
    }
    free(*L);
    *L=NULL;
}

4.重置链表为空表

void ClearList(DuLinkList L) /* 不改变L */
{
    DuLinkList q,p=L->next; /* p指向第一个节点*/
    while(p!=L) /* p没到表头*/
    {
        q=p->next;
        free(p);
        p=q;
    }
    L->next=L->prior=L; /* 头节点的两个指针域均指向自身*/
}

5.验证是否为空表

Status ListEmpty(DuLinkList L)
{ /* 初始条件：线性表L已存在*/
    if(L->next==L&&L->prior==L)
        return TRUE;
    else
    return FALSE;
}

下面是对元素的操作的示例。

（1）计算表内元素个数。

int ListLength(DuLinkList L)
{ /* 初始条件：L已存在。操作结果：*/
int i=0;
DuLinkList p=L->next; /* p指向第一个节点*/
while(p!=L) /* p没到表头*/
{
    i++;
    p=p->next;
}
return i;
}

（2）赋值。

Status GetElem(DuLinkList L,int i,ElemType *e)
{ /* 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR */
    int j=1; /* j为计数器*/
    DuLinkList p=L->next; /* p指向第一个节点*/
    while(p!=L&&j<i)
    {
        p=p->next;
        j++;
    }
    if(p==L||j>i) /* 第i个元素不存在*/
        return ERROR;
    *e=p->data; /* 取第i个元素*/
    return OK;
}

（3）查找元素。

int LocateElem(DuLinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{ /* 初始条件：L已存在，compare()是数据元素判定函数*/
    /* 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。*/
    /* 若这样的数据元素不存在，则返回值为0 */
    int i=0;
    DuLinkList p=L->next; /* p指向第1个元素*/
    while(p!=L)
    {
        i++;
    if(compare(p->data,e)) /* 找到这样的数据元素*/
        return i;
    p=p->next;
    }
    return 0;
}

（4）查找元素前驱。

Status PriorElem(DuLinkList L,ElemType cur_e,ElemType *pre_e)
{ /* 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，*/
    /* 否则操作失败，pre_e无定义*/
    DuLinkList p=L->next->next; /* p指向第2个元素*/
    while(p!=L) /* p没到表头*/
    {
        if(p->data==cur_e)
        {
            *pre_e=p->prior->data;
            return TRUE;
        }
        p=p->next;
    }
return FALSE;
}

（5）查找元素后继。

Status NextElem(DuLinkList L,ElemType cur_e,ElemType *next_e)
{/* 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，*/
    /* 否则操作失败，next_e无定义*/
    DuLinkList p=L->next->next; /* p指向第2个元素*/
    while(p!=L) /* p没到表头*/
    {
        if(p->prior->data==cur_e)
        {
            *next_e=p->data;
            return TRUE;
        }
        p=p->next;
    }
    return FALSE;
}

（6）查找元素地址。

DuLinkList GetElemP(DuLinkList L,int i) /* 另加*/
{ /* 在双向链表L中返回第i个元素的地址。i为0，返回头节点的地址。若第i个元素不存在，*/
    /* 返回NULL */
    int j;
    DuLinkList p=L; /* p指向头节点*/
    if(i<0||i>ListLength(L)) /* i值不合法*/
        return NULL;
    for(j=1;j<=i;j++)
        p=p->next;
    return p;
}

（7）元素的插入。

Status ListInsert(DuLinkList L,int i,ElemType e)
{ /* 在带头节点的双链循环线性表L中第i个位置之前插入元素e，i的合法值为1≤i≤表长+1 */
    /* 改进算法，否则无法在第表长+1个节点之前插入元素*/
    DuLinkList p,s;
    if(i<1||i>ListLength(L)+1) /* i值不合法*/
        return ERROR;
    p=GetElemP(L,i-1); /* 在L中确定第i个元素前驱的位置指针p */
    if(!p) /* p=NULL,即第i个元素的前驱不存在(设头节点为第1个元素的前驱) */
        return ERROR;
    s=(DuLinkList)malloc(sizeof(DuLNode));
    if(!s)
        return OVERFLOW;
    s->data=e;
    s->prior=p; /* 在第i-1个元素之后插入*/
    s->next=p->next;
    p->next->prior=s;
    p->next=s;
    return OK;
}

（8）元素的删除。

Status ListDelete(DuLinkList L,int i,ElemType *e)
{ /* 删除带头节点的双链循环线性表L的第i个元素，i的合法值为1≤i≤表长*/
    DuLinkList p;
    if(i<1) /* i值不合法*/
        return ERROR;
    p=GetElemP(L,i); /* 在L中确定第i个元素的位置指针p */
    if(!p) /* p=NULL,即第i个元素不存在*/
        return ERROR;
    *e=p->data;
    p->prior->next=p->next;
    p->next->prior=p->prior;
    free(p);
    return OK;
}

（9）正序查找。

void ListTraverse(DuLinkList L,void(*visit)(ElemType))
{ /* 由双链循环线性表L的头节点出发，正序对每个数据元素调用函数visit()*/
    DuLinkList p=L->next; /* p指向头节点*/
    while(p!=L)
    {
        visit(p->data);
        p=p->next;
    }
    printf("\n");
}

（10）逆序查找。

void ListTraverseBack(DuLinkList L,void(*visit)(ElemType))
{ /* 由双链循环线性表L的头节点出发，逆序对每个数据元素调用函数visit()。*/
    DuLinkList p=L->prior; /* p指向尾节点*/
    while(p!=L)
    {
        visit(p->data);
        p=p->prior;
    }
    printf("\n");
}