从零开始的数据结构与算法（四）：单向循环链表

1 单向循环链表

当链表的最后一个节点的指针指向了首节点时，而不是 NULL 时，那么就构成了一个循环链表。

1.1 定义

typedef int ElementType;    // 自定义数据元素类型
typedef int Status;         // 自定义状态码类型
static int SUCCESS = 0;     // 成功状态码
static int ERROR = -1;      // 失败状态吗

/// 定义单向链表的节点
struct Node {
    ElementType data;       // 数据域
    struct Node *next;      // 指针域，指向逻辑中的下一个节点
};

单向循环链表也是单向链表，定义相同，只是在逻辑上产生了环的结构。

在前一节使用普通的单链表时，创建了一个头结点作为辅助节点。而循环链表由于循环的结构所以不需要创建辅助的节点，但也可以根据需要创建头结点加入链表的循环中。本节降不使用辅助节点创建循环链表

本节中链表的起始位置默认为 0。

1.2 打印

/// 遍历打印循环链表
static void traverseLinkList(LinkList l) {
    // 判断是否为空
    if (l == NULL) {
        printf("LinkList is null!");
        return;
    }
    LinkList p = l;
    printf("LinkList: ");
    do {
        printf("%d ", p->data);
        p = p->next;
    } while (p != l);
    printf("\n");
}

1.3 插入

/// 单向循环链表的插入
static Status insertIntoLinkList(LinkList *l, int i, ElementType e) {
    // 定义 0 为头结点
    // 链表为空则创建链表
    if (*l == NULL) {
        // 创建新的节点
        LinkList temp = (LinkList)malloc(sizeof(LinkList *));
        if (temp == NULL) {
            return ERROR;
        }
        temp->data = e;
        *l = temp;
        temp->next = temp;
        return SUCCESS;
    }
    // 查找目标节点的前驱
    LinkList p;
    if (i == 0) {
        /* 插入位置为 1，则属于插入首节点 */
        // 遍历找到尾节点，也就是首节点的前驱
        p = *l;
        while (p->next != *l) {
            p = p->next;
        }
        // 此时 p->next == *l，p 为首节点 *l 的前驱即尾节点
    } else {
        /* 插入其他的位置（也可能是循环到首节点） */
        // 遍历找到插入位置前的节点
        int j = 0;
        p = *l;
        while (j < i - 1 && p->next != *l) {
            p = p->next;
            j++;
        }
        // i 大于链表的长度，释放节点
        if (j != i - 1) {
            return ERROR;
        }
        // 此时 p 为插入位置的前驱，j == i - 1
    }
    // 创建新的节点
    LinkList temp = (LinkList)malloc(sizeof(LinkList *));
    if (temp == NULL) {
        return ERROR;
    }
    temp->data = e;
    // 将 i 上的内容（原节点或 NULL）作为新节点的后继
    temp->next = p->next;
    // 将新节点作为 p 新的后继
    p->next = temp;
    // 重置首节点
    if (i == 0) {
        *l = temp;
    }
    return SUCCESS;
}

因为是循环链表，所以在插入时需要对头结点进行特殊处理。

• 因为其他位置的节点在寻找的过程中可以将其前驱一并获取到（先找到了其前驱再找到该节点），而头结点的前驱是尾节点，所以需遍历获取尾节点。
• 在头结点插入时需要移动头结点的指针 *l。

若传入的链表为空，则创建了一个新的单节点的循环链表。

1.4 删除

/// 单向循环链表的删除
static Status deleteFromLinkList(LinkList *l, int i, ElementType *e) {
    // 同插入时定义 0 为头结点
    // 只剩一个节点，需要将指针置 NULL
    if ((*l)->next == *l) {
        free(*l);
        *l = NULL;
        return SUCCESS;
    }
    if (i == 0) {
        /* 删除位置为 1，则属于删除首节点 */
        // 遍历找到尾节点，也就是首节点的前驱
        LinkList p = *l;
        while (p->next != *l) {
            p = p->next;
        }
        // 此时 p->next == *l，p 为首节点 *l 的前驱即尾节点
        LinkList temp = *l;
        *e = temp->data;
        // 调整尾节点的后继
        p->next = temp->next;
        // 重置首节点
        *l = temp->next;
        // 释放节点
        free(temp);
    } else {
        /* 删除其他的位置 */
        // 遍历找到删除位置前的节点
        int j = 0;
        LinkList p = *l;
        // 当 i 大于链表的长度时，
        // a. 若直接退出不进行循环删除
        while (j < i - 1 && p->next != *l) {
            p = p->next;
            j++;
        }
        if (j < i - 1) {
            return ERROR;
        }
        /*
        // b. 若进行循环遍历删除特定元素，则直接遍历到指定位置，
        // 此时需要判断删除的是否是首节点，进行头结点的移动操作
        while (j < i - 1) {
            p = p->next;
            j++;
        }
         */
        // 此时 p 为删除位置的前驱，j == i - 1
        // 将 i 上的内容（原节点或 NULL）作为新节点的后继
        LinkList temp = p->next;
        *e = temp->data;
        // 若循环删除并且循环到首节点，则需要重置首节点
        if (temp == *l) {
            *l = temp->next;
        }
        // 调整尾节点的后继
        p->next = temp->next;
        // 释放节点
        free(temp);
    }
    return SUCCESS;
}

1.5 查询

// 查询某个值所在的位置
static Status findIndexWithValue(LinkList l, ElementType e, int *i) {
    int j = 0;
    LinkList p = l;
    // 遍历查找
    while (p->next != l) {
        // 找到位置返回
        if (p->data == e) {
            *i = j;
            return SUCCESS;
        }
        p = p->next;
        j++;
    }
    // 未找到位置
    return ERROR;
}

1.6 使用

int main() {
    
    LinkList l1 = NULL, l2 = NULL;
    for (int i = 0; i < 10; i++) {
        insertIntoLinkList(&l1, i, i * 2);
    }
    printf("构建循环链表 l1\n");
    traverseLinkList(l1);
    
    ElementType e1;
    deleteFromLinkList(&l1, 3, &e1);
    printf("删除了 l1 的 3 号数据元素：%d\n", e1);
    traverseLinkList(l1);
    
    for (int i = 0; i < 10; i++) {
        insertIntoLinkList(&l2, 0, i * 3);
    }
    printf("构建循环链表 l2\n");
    traverseLinkList(l2);
    
    ElementType e2 = 666;
    insertIntoLinkList(&l2, 4, e2);
    printf("在 l2 的 4 号数据元素位置插入：%d\n", e2);
    traverseLinkList(l2);
    
    int i = -1, j = -1;
    findIndexWithValue(l2, e2, &i);
    printf("在 l2 中 %d 所在位置为：%d\n", e2, i);
    ElementType e3 = 777;
    findIndexWithValue(l2, e3, &j);
    printf("在 l2 中 %d 所在位置为：%d\n", e3, j);

    return 0;
}

打印结果：

构建循环链表 l1
LinkList: 0 2 4 6 8 10 12 14 16 18 
删除了 l1 的 3 号数据元素：6
LinkList: 0 2 4 8 10 12 14 16 18 
构建循环链表 l2
LinkList: 27 24 21 18 15 12 9 6 3 0 
在 l2 的 4 号数据元素位置插入：666
LinkList: 27 24 21 18 666 15 12 9 6 3 0 
在 l2 中 666 所在位置为：4
在 l2 中 777 所在位置为：-1

2 总结

• 普通的单链表为了使用方便，采用了一个头结点作为辅助节点，而循环链表因为是循环的所以没有使用辅助节点。
• 单向循环链表对比普通的单链表，除了基本的操作还需要对尾节点的后续进行处理。
• 在对某个位置操作时，若位置大于链表的长度，可根据需要直接返回，或者不返回而是循环到头结点继续遍历。