循环链表(Circular LinkList)

循环链表有以下两种:

循环单链表: 从一个结点出发只能找到后续的各个结点.
循环双链表: 从一个结点出发可以找到其他任何一个结点.

0x01 循环单链表

单链表和循环单链表的区别:

单链表: 表尾结点的next指针指向NULL

循环单链表: 表尾结点的next指针指向头结点

循环单链表的定义和单链表一样, 如下所示:

struct LNode{	//定义单链表结点类型
  ElemType data;//每个节点存放一个数据元素
  struct LNode *next; //指针指向下一个节点
};
typedef struct LNode LNode;
typedef struct LNode *LinkList;

或者,

typedef struct LNode{ //定义单链表结点类型
  ElemType data;//每个节点存放一个数据元素
  struct LNode *next; //指针指向下一个节点
}LNode, *LinkList;

两者等价。

0x0101 循环单链表的初始化

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

初始化: 头结点的next指针指向自己.

0x0102 循环单链表的判空

所以判断一个循环单链表是否为空值时只需要判断是否 L->next == L即可(头结点的next指针指向自己).

/*** 
 * @description: 判断一个循环单链表是否为空
 * @param {LinkList} L
 * @return {*}
 */
bool isEmpty(LinkList L) {
    if (L->next == L)
        return true;
    else
        return false;
}

0x0103 循环单链表的判尾

同理, 判断一个结点是否为循环单链表的表尾结点只需要判断:

该结点的next指针是否指向头结点

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

循环单链表的插入和删除操作和单链表类似, 由于篇幅不宜过长, 就不展开叙述了.

0x02 循环双链表

双链表和循环双链表的区别:

双链表:

表头结点的prior指向NULL

表尾结点的next指向NULL

循环双链表:

表头结点的prior指向表尾结点

表尾结点的next指向表头结点

循环双链表的定义和双链表一样, 如下所示:

typedef struct DNode { //定义双链表结点类型
    int data; //数据域
    struct DNode* prior, * next; //前驱指针和后继指针
}DNode, * DLinklist;

或者:

struct DNode { //定义双链表结点类型
    int data; //数据域
    struct DNode* prior, * next; //前驱指针和后继指针
};
typedef struct DNode Dnode;
typedef struct DNode * DLinklist;

两者等价.

0x0201 循环双链表的初始化

初始化一个循环双链表: 头结点的prior指针指向头结点, 且头结点的next指针也指向头结点.

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

0x0202 循环双链表的判空

判断一个循环双链表是否为空:

/**
 * @description: 判断循环双链表是否为空
 * @param {DLinklist} L
 * @return {*}
 */
bool isEmpty(DLinklist L) {
    if (L->next == L)
        return true;
    else
        return false;
}

0x0203 循环双链表的判尾

判断一个结点是否为循环双链表的表尾结点:

/**
 * @description: 判断结点p是否为循环双链表的表尾结点
 * @param {DLinklist} L
 * @param {DNode*} p
 * @return {*}
 */
bool isTail(DLinklist L, DNode* p) {
    if (p->next == L)
        return true;
    else
        return false;
}