数据结构 - 循环链表

循环链表分为

• 循环双链表
• 循环单链表

循环单链表

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

定义

// 定义一个循环单链表
typedef struct LNode {  // 定义一个单链表的类型
    int data;            // 每一个节点存放的数据类型为int的数据域
    struct LNode *next; // 指针指向下一个节点 
}LNode,*LinkList;

初始化

// 初始化一个循环单链表
bool InitList(LinkList L) {
    L = (LNode*)malloc(sizeof(LNode)); // 分配一个头节点
    if (L==NULL) {
        return false;        // 内存不足，分配失败
    }
    L->next = L;             // 循环链表的头节点next指向头节点
    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;
    }
}

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

使用循环单链表中在尾部插入一个节点，可以从尾部找一个节点即可，所以这种的方式时间复杂度为O(1)
很多时候对单链表的操作都在表头或者表尾时可以让L指向表尾元素（插入、删除、可能需要修改L）

循环双链表

循环双链表：

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

表尾节点的next指向头节点

定义

// 定义一个双链表
typedef struct DNode {
    int data; // 
    struct DNode *prior, *next;
}DNode,*DLinkList;

初始化

 // 初始化空的循环双链表
bool InitDLinkList(DLinkList L) {
    L = (DNode*)malloc(sizeof(DNode)); // 分配一个头节点
    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;
    }
}

插入节点

// 双链表的插入
// 在p节点之后插入s节点
bool InsertNextDNode(DNode *p,DNode *s) {
    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;
    return true;
}

删除节点

// 删除p的后继节点
bool DeleteNextDNode(DNode *p, DNode *q) {
    p->next = q->next;
    q->next->prior = p;
    free(q);
    return true;
}

版权声明：文章转载请注明来源，如有侵权请联系删除！