嵌入式Linux c语言常用数据结构2

循环链表

在循环链表中，可以从任意一个节点P出发找到它的直接前驱，而不是从head出发。其算法C语言描述如下：

typedef struct node
{
    int data;
    struct node *next;
}NODE;
NODE *prev(NODE *head,NODE *p)
{
     NODE *q;
     q=p->next;
     while(q->next!=p)
     q=q->next;
     return (q);
}

循环链表的其他特性。

范例1：将2个线性表链接起来

略

范例2：将单向循环链表倒置

void invert_list(List head)
{
    q=head;
    p=head->next;
    r=p->next;
    do
    {
        p->next=q;
        q=p;
        p=r;
        r=r->next;
    }while(p!=head->next);
}