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

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

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

img

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

循环链表的操作和线性表基本一致,差别仅在于算法中的循环条件不是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表头即可

img链接前

img链接后

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

本文链接:

https://nullcode.fun/9.html
1 + 2 =
快来做第一个评论的人吧~