数据结构

循环链表是一种特殊的链表，其中最后一个节点的next指针指向第一个节点，形成一个闭环。这种结构使得在处理链表时不会出现“空”链表的情况，并且可以在链表末尾和开头之间方便地进行插入和删除操作。

循环链表的特点

  1. 循环性：最后一个节点的next指针指向第一个节点。
  2. 遍历：从任意一个节点开始，可以遍历整个链表直到回到起点。
  3. 插入和删除：由于循环性，插入和删除操作在链表的任意位置都非常方便。

循环链表的基本操作

  1. 创建循环链表
  2. 在头部插入节点
  3. 在尾部插入节点
  4. 删除特定值的节点
  5. 遍历循环链表

下面是一个用C语言实现的简单循环链表：

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 创建一个新的节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 创建循环链表并初始化
void createCircularLinkedList(Node** head, int data) {
    *head = createNode(data);
    (*head)->next = *head; // 形成闭环
}

// 在头部插入节点
void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data);
    if (newNode == NULL) return;

    if (*head == NULL) { // 空链表的情况
        *head = newNode;
        newNode->next = newNode; // 形成闭环
    } else {
        Node* temp = *head;
        while (temp->next != *head) {
            temp = temp->next;
        }
        temp->next = newNode; // 将最后一个节点的next指向新节点
        newNode->next = *head; // 新节点的next指向原来的头节点
        *head = newNode; // 更新头指针
    }
}

// 在尾部插入节点
void insertAtTail(Node** head, int data) {
    Node* newNode = createNode(data);
    if (newNode == NULL) return;

    if (*head == NULL) { // 空链表的情况
        *head = newNode;
        newNode->next = newNode; // 形成闭环
    } else {
        Node* temp = *head;
        while (temp->next != *head) {
            temp = temp->next;
        }
        temp->next = newNode; // 将最后一个节点的next指向新节点
        newNode->next = *head; // 新节点的next指向头节点
    }
}

// 删除特定值的节点
void deleteNode(Node** head, int data) {
    if (*head == NULL) return;

    Node* temp = *head;
    Node* prev = NULL;

    // 找到要删除的节点
    do {
        if (temp->data == data) break;
        prev = temp;
        temp = temp->next;
    } while (temp != *head);

    // 如果没有找到目标节点
    if (temp == *head && temp->next == *head) { // 只有一个节点且等于要删除的值
        free(temp);
        *head = NULL;
        return;
    }

    // 删除头节点
    if (temp == *head) {
        prev = *head;
        while (prev->next != *head) {
            prev = prev->next;
        }
        *head = temp->next; // 更新头指针
        prev->next = *head; // 最后一个节点的next指向新的头节点
    } else { // 删除中间或尾部节点
        prev->next = temp->next;
    }

    free(temp);
}

// 遍历循环链表
void traverseCircularLinkedList(Node* head) {
    if (head == NULL) {
        printf("链表为空\n");
        return;
    }
    Node* temp = head;
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("\n");
}

int main() {
    Node* head = NULL;

    // 创建循环链表
    createCircularLinkedList(&head, 10);
    traverseCircularLinkedList(head);

    // 在头部插入节点
    insertAtHead(&head, 20);
    traverseCircularLinkedList(head);

    // 在尾部插入节点
    insertAtTail(&head, 30);
    traverseCircularLinkedList(head);

    // 删除节点
    deleteNode(&head, 20);
    traverseCircularLinkedList(head);

    return 0;
}

代码解释

  1. 创建节点：createNode函数用于创建一个新的链表节点。
  2. 初始化循环链表：createCircularLinkedList函数用于创建一个只有一个节点的循环链表。
  3. 头部插入：insertAtHead函数用于在链表头部插入新节点。如果链表为空，直接将新节点作为头节点并形成闭环。
  4. 尾部插入：insertAtTail函数用于在链表尾部插入新节点。通过遍历找到最后一个节点，并更新其next指针。
  5. 删除节点：deleteNode函数用于删除指定值的节点。需要处理多种情况，如删除头节点、中间节点或尾部节点。
  6. 遍历循环链表：traverseCircularLinkedList函数用于遍历整个循环链表并打印每个节点的数据。

发表评论