循环链表前言

之前写了，双链表和单链表的代码模板，基于此结构的循环链表代码具体实现想偷懒了，主要是因为我觉得考的可能性不大。

循环单链表的类型描述

1
2
3
4
typedef struct LNode{    //定义循环链表结点类型
	int data;            //数据域
	struct LNode * next;  //指针域
}LNode, * LinkList;

初始化

1
2
3
4
5
6
//初始化
void InitList(LinkList & list){
    // 头结点初始化
    list = (LNode *)malloc(sizeof(LinkList));
    list -> next = list; // 指向自己
}

判空

1
2
3
4
5
6
//判空
bool Empty(LinkList list){
    // 如果头结点的下一个结点，依旧是头结点，那么说明是空表
    if(list -> next == list) return true;
    else return false;
}

判断表尾节点

1
2
3
4
5
6
//判断结点p是否是表尾结点
bool isTail(LinkList list, LNode * p){
    // 如果是表尾节点，它的next一定指向头结点
    if(p -> next == list) return true;
    else return false;
}

插入和删除

循环单链表的插入、删除算法与单链表几乎一样，不同的是如果在表尾进行，那么要让单链表继续保持循环的性质，即让尾结点的next域指向头结点。

循环双链表的类型描述

1
2
3
4
typedef struct DNode{
    int data;  //数据域
    struct DNode * prior, * next;  //前驱和后继指针
}DNode, * DLinkList;

初始化

1
2
3
4
5
void InitList(DLinkList & list){
    list = (LNode *)malloc(sizeof(LNode));
    list -> prior = list;
    list -> next = list;
}

判空

1
2
3
4
5
6
//判空
bool Empty(DLinkList list){
    // 如果头结点的下一个结点，依旧是头结点，那么说明是空表
    if(list -> next == list) return true;
    else return false;
}

判断表尾节点

1
2
3
4
5
6
//判断结点p是否是表尾结点
bool isTail(DLinkList list, LNode * p){
    // 如果是表尾节点，它的next一定指向头结点
    if(p -> next == list) return true;
    else return false;
}

插入和删除

循环双链表的插入、删除算法与双链表几乎一样，不同的是如果在表尾进行，那么要让双链表继续保持循环的性质，即让尾结点的next域指向头结点，同时让头结点的prior域指向尾结点。