【数据结构与算法】—— * 循环链表 *

存储结构示意图

优点 ： 能够通过任意结点遍历整个链表结构

初始化循环链表

1，循环链表的结点

typedef struct CircularNode {
    ElementType date; //数据域
    struct CircularNode* next; //指向下一个结点的指针域

}CircularNode;

2，循环链表结构

typedef struct CircularLinkList {
    CircularNode* next;   //指向第一个结点的头指针，头指针
    int length;              
}CircularLinkList;

循环链表的插入

需要考虑两种情况

1. 插入的链表长度为 0 node -> next = node;
2. **插入的链表长度不为0 node -> next = clList -> next lastNode -> next = node **

首位置

代码实现

---

其他位置

---

代码实现（总）

void InsertCircularLinkList(CircularLinkList* clList, int pos, ElementType element)
{
    //创建一个空节点
    CircularLinkList* node = (CircularLinkList*)malloc(sizeof(CircularLinkList));
    node->date = element;
    node->next = NULL;
    if (pos == 1) {
        node->next = clList->next;
        if (!node->next) {
            //如果插入的链表长度为0
            node->next = node;
        }
        else {
            //如果长度不为0，就要找到链表的最后一个结点并改变其指针域
            CircularLinkList* lastNode = clList->next;
            for (int i = 1; i < clList->length; i++)
            {
                lastNode = lastNode->next;
            }
            clList->next = node;
            clList->length++;
        }
        return;
    }
    //插入的不是第一个结点
    CircularLinkList* currNode = clList->next;
    for (int i = 1; i < pos - 1; i++)
        currNode = currNode->next;
    if (currNode) {
        node->next = currNode->next;
        currNode->next = node;
        clList->length++;
        if (pos == clList->length) {
            node->next = clList->next;
        }
    }
}

循环链表的删除

1，操作的为第一个元素

代码实现

---

2，操作元素不为第一个元素

代码实现

---

代码实现（总）

ElementType DeleteCircularLinkList(CircularLinkList* clList, int pos)
{
    ElementType element;
    element.id = -999;
    if (pos == 1) {
        CircularLinkList* node = clList->next;
        if (node) {
            //找到最后一个结点，改变其指针域的指向
            CircularLinkList* lastNode = clList->next;
            for (int i = 1; i < clList->length; i++) {
                lastNode = lastNode->next;
            }
            clList->next = node->next;
            lastNode->next = clList->next;
            free(node);
            clList->length--;
        }

        return;
    }

    CircularLinkList* preNode;
    CircularLinkList* node = clList->next;
    for (int i = 1; node && i < pos; i++) {
        preNode = node;
        node = node->next;
    }
    if (node) {
        element = node->date;
        preNode->next = node->next;
        free(node);
        clList->length--;
    }
    return element;
}

循环链表的常见操作

已知 P 结点是循环链表的中间结点，通过该节点遍历循环链表

代码实现

CircularNode* GetCircularLinkListNode(CircularLinkList* clList, ELementType element)
{
    CircularNode* node = clList->next;
    if (!node) return NULL;

    do {
        if (element.id == node->date.id && strcmp(element.name, node->date.name) == 0) {
            return node;
        }

    } while (node == clList->next);

    return NULL;
}