[线性表](4)循环链表

循环链接(circular linked list)是另一种形式的链式存储结构，它的特点是表中最后一个结点的指针域指向头结点。整个链表形成一个环。

由此，从表中任一结点出发均可找到表中其他结点，如下图所示：

类似的，还可以有多重链的循环链表。

循环链表的操作和线性表基本一致，差别仅在于算法中的循环条件不是p或者p->next为NULL，而是他们是否等于头结点

循环链表中有带头结点和不带头结点之分，不带头节点就是头指针一直指向第一个节点。

主要算法下：声明链表

typedef struct List
{
    int data;
    struct List* next;

}CList;

尾插

void Malloc_CL()
{
    node = (CList*)malloc(sizeof(CList));
    scanf("%d", &node->data);
    if (head == NULL)
    {
        head = node;
        node->next = head;
    }
    else
    {
        p = head;
        while (p->next != head)
        {
            p = p->next;
        }
        node->next = p->next;
        p->next = node;
    }
}

头插：

void Malloc_CL()
{
    node = (CList*)malloc(sizeof(CList));
    scanf("%d", &node->data);
    if (head == NULL)
    {
        head = node;
        node->next = head;
    }
    else
    {
        p = head;
        while (p->next != head)
        {
            p = p->next;
        }
        node->next = head;
        p->next = node;
        head = node;
    }
}

尾删：

void Delete_CL()
{
    p = head;
    s = head;
    while (s->next != head)
    {
        p = s;
        s = s->next;
    }
    free(s);
    p->next = head;
}

头删：

void Delete_CL()
{
    p = head;
    s = head;

    while (s->next != head)
    {
        s = s->next;
    }
    s->next = p->next;
    head = p->next;
    free(p);
}

遍历：

    p = head;
    do
    {
        printf("%d ", p->data);
        p = p->next;
    } while (p != head);

带头结点：初始化

void MalloHead()
{
    head = (CList*)malloc(sizeof(CList));
    head->next = head;
}

尾插：

void Malloc_CL()
{
    node = (CList*)malloc(sizeof(CList));
    scanf("%d", &node->data);
    p = head;
    while (p->next != head)
    {
        p = p->next;
    }
    node->next = head;
    p->next = node;
}

头插：

void Malloc_CL()
{
    node = (CList*)malloc(sizeof(CList));
    scanf("%d", &node->data);
    p = head;

    node->next = p->next;
    p->next = node;

}

尾删：

void Delete_CL()
{
    p = head;
    s = head->next;
    while (s->next != head)
    {
        p = s;
        s = s->next;
    }
    p->next = head;
    free(s);
}

头删

void Delete_CL()
{
    p = head->next;
    head->next = p->next;
    free(p);
}

遍历

    p = head->next;
    while (p != head)
    {
        printf("%d ", p->data);
        p = p->next;
    }

可以看到，循环单链和单链表的操作大致一样。但有的时候，若在循环链表中设立尾指针而不设头指针，可以简化某些操作，如下图所示：链接两表，只需要将A表尾链接到B表头，将B表尾链接到A表头即可

链接前

链接后

只需要修改两个指针域即可

本文链接：