循环链表

循环链表分为循环单链表和循环双链表

循环单链表

循环单链表是一种特殊的单链表，其尾节点的 next 指针指向链表的头结点，形成一个环形结构。这种设计在某些情况下是有意义的，具体作用包括：

1. 方便遍历：由于尾节点指向头结点，遍历链表时可以从任意节点开始，遍历到尾节点后直接返回到头结点，形成一个循环遍历，而不需要额外的逻辑来判断是否到达了链表的末尾。

2. 简化操作：在循环单链表中，任何一个节点都可以作为起点，而无需考虑头结点或尾节点的特殊情况。例如，在插入新节点时，不需要单独处理头结点或尾节点的情况，因为它们都遵循相同的规则。

3. 实现算法：某些算法和数据结构的实现会受益于循环单链表的特性。例如，约瑟夫环问题、哈希表的实现等都可以更加简洁和高效地利用循环单链表的特性。

4. 提高效率：循环单链表的头结点与尾节点的连接形成了一个闭环，遍历时可以实现更高的效率，因为不需要检查尾节点的 next 指针是否为 NULL。

总的来说，循环单链表的设计简化了一些操作，提高了效率，并且在特定的问题场景下更容易实现相关算法。

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef  struct  LNode{ //定义单链表结点类型
    ElemType data; //数据域
    struct LNode *next; //指针指向下个结点
}LNode,*LinkList;

//初始化一个循环单链表
bool InitList(LinkList &L){
    L=(LNode *) malloc(sizeof(LNode)); //头结点分配空间
    if(L=NULL) //内存不足，分配失败
    {
        return false;
    }
    L->next=L;
    return true;
}

//判断循环单链表是否为空
bool Empty(LinkList L){
    if(L->next==L)
    {
        return true;
    }else
    {
        return false;
    }
}

//判断结点p是否为循环单链表的表尾节点
bool isTail(LinkList L, LNode *p){
    if(p->next==L)
    {
        return true;
    } else
    {
        return false;
    }
}
int main() {
    return 0;
}

循环单链表从头结点找到尾部，时间复杂度为O(n)，从尾部找到头结点，时间复杂度为O(1)。

循环双链表

循环双链表（circular doubly linked list）和普通双链表（doubly linked list）是两种常见的链表数据结构，它们在存储方式和特性上有一些区别，以下是它们之间的对比：

1. 存储方式：

   • 普通双链表：双链表的最后一个节点的 next 指针通常指向 NULL，而第一个节点的 prior 指针也通常指向 NULL，形成一个线性结构。
   • 循环双链表：循环双链表的最后一个节点的 next 指针指向头结点，而头结点的 prior 指针指向尾节点，形成一个循环。

2. 遍历方式：

   • 普通双链表：遍历普通双链表时，需要单独处理头节点和尾节点，因为它们的 next 和 prior 指针指向的位置不同。
   • 循环双链表：循环双链表中头节点和尾节点的指针关系是相互的，因此在遍历时无需特殊处理头节点和尾节点。

3. 插入和删除操作：

   • 普通双链表：在普通双链表中，插入和删除节点时，需要考虑头节点和尾节点的特殊情况，可能需要单独处理。
   • 循环双链表：由于循环双链表中头节点和尾节点的指针是相互的，插入和删除节点时的操作更加统一和简化。

4. 特性：

   • 普通双链表：普通双链表是一个线性结构，头节点的 prior 指针和尾节点的 next 指针通常为 NULL。
   • 循环双链表：循环双链表形成一个闭环，头节点的 prior 指针指向尾节点，尾节点的 next 指针指向头节点。

5. 应用场景：

   • 普通双链表：适用于需要线性存储结构，但不需要循环特性的场景。
   • 循环双链表：适用于需要循环特性的场景，例如循环遍历、环形缓冲区等。

总的来说，选择普通双链表还是循环双链表取决于具体的需求和应用场景。普通双链表适用于一般的链表操作，而循环双链表适用于需要循环特性的场景。

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef  struct  DNode{
    ElemType data;
    struct DNode *prior,*next; //指针指向下个结点
}DNode,*DLinkList;

//初始化空的循环双链表
bool InitDLinkList(DLinkList &L){
    L=(DLinkList) malloc(sizeof(DLinkList)); //分配一个头结点
    if(L==NULL) //内存不足，分配失败
    {
        return false;
    }
    L->prior=L; //头结点的prior指针指向头结点
    L->next=L; //头结点的next指针指向头结点
    return true;
}

//判断循环双链表是否为空
bool Empty(DLinkList L){
    if(L->next==L)
    {
        return true;
    }else
    {
        return false;
    }
}

//判断结点p是否为循环双链表的表尾节点
bool isTail(DLinkList L, DNode *p){
    if(p->next==L)
    {
        return true;
    } else
    {
        return false;
    }
}
int main() {
    DLinkList L;
    InitDLinkList(L);
    L->next=L;
    return 0;
}

此时对于上一章节对于双链表插入、删除有错误的代码，在循环双链表中反而可以正常执行了。

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef  struct  DNode{
    ElemType data;
    struct DNode *prior,*next; //指针指向下个结点
}DNode,*DLinkList;

//在p结点之后插入s结点
bool InsertNextDNode(DNode *p, DNode *s){
    s->next=p->next;
    p->next->prior=s;
    s->prior=p;
    p->next=s;
}

//删除p的后继结点q
bool DeleteNextDNode(DNode *p){
    if(p==NULL)
    {
        return false;
    }
    DNode *q=p->next;
    p->next=q->next;
    q->next->prior=p;
    free(q);
    return true;
}
int main() {
    return 0;
}