循环链表简单介绍

循环链表 1、循环链表长什么样

将单链表中终端结点的指针端自空指针改为指向头结点，就使整个单链表形成个环，这种头尾相接的单链表称单循环链表，简称循环链表

如图，就是尾巴指向头结点

2、有什么用？

当需要访问最后一个节点时，需要遍历整个单链表，有没有可能用 0(1) 的时间由链表指针访问到最后一个结点呢?当然可以。只需要在最后一个结点的指针域指向头结点就行，

终端结点用尾指针 rear 示，则查找终端结点是 0(1)，而开始结点其实就是 rear->next->next ，其时间复杂也为 0(1)

3、实现 3.1实现概览

#include 
#include 

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef struct Node
{
    int data;
    struct Node *next;
} Node, *LinkList;

int createListTail(LinkList *L, int n);
int listInsert(LinkList *L, int i, int e);
int listDelete(LinkList *L, int i, int *e);
int listLength(LinkList L);
void traverse(LinkList L);
LinkList mergeTwoList(LinkList *A, LinkList *B);

3.2尾插法创建循环链表

int createListTail(LinkList *L, int n)
{
    LinkList p, q;
    (*L) = (LinkList)malloc(sizeof(Node));
    p = (*L);
    for (int i = 1; i <= n; i++)
    {
        q = (LinkList)malloc(sizeof(Node));
        q->data = i;
        p->next = q;
        p = q;
    }

    p->next = (*L);//尾结点的指针域指向了头结点(*L是头结点，L存放*L的地址，是头指针)
    return OK;
}

3.3插入元素

int listInsert(LinkList *L, int i, int e)
{
    LinkList p = (*L), q;
    int j = 1;
    while (p && j < i)
    {
        p = p->next;
        j++;
    }

    if (!p || j > i)
        return ERROR;
    q = (LinkList)malloc(sizeof(Node));
    q->data = e;
    q->next = p->next;
    p->next = q;

    return OK;
}

3.4删除元素

int listDelete(LinkList *L, int i, int *e)
{
    LinkList p = (*L), temp;
    int j = 1;
    while ((p->next) && j < i)
    {
        p = p->next;
        j++;
    }

    if (!(p->next) || j > i)
        return ERROR;

    temp = p->next; // temp存放待删除的结点
    p->next = temp->next;
    *e = temp->data;
    free(temp);

    return OK;
}

注意：这里的插入删除都和单链表一样

3.5合并两个循环链表

引用的是大话数据结构的图

LinkList mergeTwoList(LinkList *A, LinkList *B)
{
    LinkList p = (*A)->next, tailA, tailB;
    //找到A链表的最后一个结点
    while (p->next != *A) //p->next != *A,当p->next == *A时， 说明此时p结点是最后一个结点
        p = p->next;
    tailA = p;// 保存A的尾结点

    p = (*B)->next;
    while (p->next != *B)
        p = p->next;
    tailB = p;// 保存B的尾结点

    LinkList headA, headB;
    headA = tailA->next; // 1，保存A的头结点
    headB = tailB->next; // 1，保存B的头结点

    tailA->next = headB->next; // 2, A的尾结点的指针域，指向了B的第一个的结点
    tailB->next = headA;       // 3， B的尾结点的指针域，指向了A的头结点

    return headA;//返回合并后的双向链表
}

3.6求循环链表的长度

int listLength(LinkList L)
{
    LinkList p = L->next;
    int k = 0;
    while (p)
    {
        k++;
        p = p->next;
    }

    return k;
}

3.7遍历双向链表

void traverse(LinkList L)
{
    LinkList p = L->next;
    while (p != L)//为什么不是p->next != L?，p == L时，说明不满足条件，此时p是最后一个结点
    {
        printf("%d ", p->data);//先打印数据第一个结点的数据，所以放在p = p->next;前面
        p = p->next;
    }
}

4.完整代码

#include 
#include 

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef struct Node
{
    int data;
    struct Node *next;
} Node, *LinkList;

int createListTail(LinkList *L, int n);
int listInsert(LinkList *L, int i, int e);
int listDelete(LinkList *L, int i, int *e);
int listLength(LinkList L);
void traverse(LinkList L);
LinkList mergeTwoList(LinkList *A, LinkList *B);


int createListTail(LinkList *L, int n)
{
    LinkList p, q;
    (*L) = (LinkList)malloc(sizeof(Node));
    p = (*L);
    for (int i = 1; i <= n; i++)
    {
        q = (LinkList)malloc(sizeof(Node));
        q->data = i;
        p->next = q;
        p = q;
    }

    p->next = (*L);//尾结点的指针域指向了头结点(*L是头结点，L存放*L的地址，是头指针)
    return OK;
}


int listInsert(LinkList *L, int i, int e)
{
    LinkList p = (*L), q;
    int j = 1;
    while (p && j < i)
    {
        p = p->next;
        j++;
    }

    if (!p || j > i)
        return ERROR;
    q = (LinkList)malloc(sizeof(Node));
    q->data = e;
    q->next = p->next;
    p->next = q;

    return OK;
}


int listDelete(LinkList *L, int i, int *e)
{
    LinkList p = (*L), temp;
    int j = 1;
    while ((p->next) && j < i)
    {
        p = p->next;
        j++;
    }

    if (!(p->next) || j > i)
        return ERROR;

    temp = p->next; // temp存放待删除的结点
    p->next = temp->next;
    *e = temp->data;
    free(temp);

    return OK;
}


LinkList mergeTwoList(LinkList *A, LinkList *B)
{
    LinkList p = (*A)->next, tailA, tailB;
    //找到A链表的最后一个结点
    while (p->next != *A) //p->next != *A,当p->next == *A时， 说明此时p结点是最后一个结点
        p = p->next;
    tailA = p;// 保存A的尾结点

    p = (*B)->next;
    while (p->next != *B)
        p = p->next;
    tailB = p;// 保存B的尾结点

    LinkList headA, headB;
    headA = tailA->next; // 1，保存A的头结点
    headB = tailB->next; // 1，保存B的头结点

    tailA->next = headB->next; // 2, A的尾结点的指针域，指向了B的第一个的结点
    tailB->next = headA;       // 3， B的尾结点的指针域，指向了A的头结点

    return headA;//返回合并后的双向链表
}


int listLength(LinkList L)
{
    LinkList p = L->next;
    int k = 0;
    while (p)
    {
        k++;
        p = p->next;
    }

    return k;
}


void traverse(LinkList L)
{
    LinkList p = L->next;
    while (p != L)//为什么不是p->next != L?，p == L时，说明不满足条件，此时p是最后一个结点
    {
        printf("%d ", p->data);//先打印数据第一个结点的数据，所以放在p = p->next;前面
        p = p->next;
    }
}

int main()
{
    // LinkList L;
    // int e;
    // createListTail(&L, 5);
    // traverse(L);

    // // printf("n");
    // // listInsert(&L, 6, 22);
    // // traverse(L);

    // printf("n");
    // listDelete(&L, 5, &e);
    // traverse(L);

    LinkList A, B;
    createListTail(&A, 2);
    createListTail(&B, 2);

    LinkList mergeList = mergeTwoList(&A, &B);
    traverse(mergeList);


    // LinkList A, B;
    // createListTail(&A, 2);
    // traverse(A);

    return 0;
}

/ // traverse(L);

// printf("n");
// listDelete(&L, 5, &e);
// traverse(L);

LinkList A, B;
createListTail(&A, 2);
createListTail(&B, 2);

LinkList mergeList = mergeTwoList(&A, &B);
traverse(mergeList);


// LinkList A, B;
// createListTail(&A, 2);
// traverse(A);

return 0;

}

循环链表简单介绍

C/C++/C#相关栏目本月热门文章