C语言数据结构中单向环形链表怎么实现

概述

单向环形链表是一种特殊的链表结构，它的最后一个节点的指针指向链表的第一个节点，形成一个环。这种数据结构在某些场景下非常有用，比如实现循环队列、约瑟夫问题等。

单向环形链表的定义

在C语言中，单向环形链表可以通过结构体来定义。每个节点包含两个部分：数据域和指针域。数据域用于存储数据，指针域用于指向下一个节点。

struct Node {
    int data;
    struct Node* next;
};

创建单向环形链表

创建一个单向环形链表的过程包括以下几个步骤：

1. 创建头节点。
2. 添加其他节点，并将最后一个节点的指针指向头节点。

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

struct Node {
    int data;
    struct Node* next;
};

// 创建单向环形链表
struct Node* createCircularLinkedList(int n) {
    struct Node *head = NULL, *temp = NULL, *newNode = NULL;
    int i;

    // 创建头节点
    head = (struct Node*)malloc(sizeof(struct Node));
    head->data = 1;
    head->next = NULL;
    temp = head;

    // 添加其他节点
    for (i = 2; i <= n; i++) {
        newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = i;
        newNode->next = NULL;
        temp->next = newNode;
        temp = newNode;
    }

    // 将最后一个节点的指针指向头节点，形成环
    temp->next = head;

    return head;
}

遍历单向环形链表

遍历单向环形链表时，需要注意避免无限循环。可以通过设置一个标志位来判断是否已经遍历完整个链表。

void traverseCircularLinkedList(struct Node* head) {
    struct Node* temp = head;
    if (head != NULL) {
        do {
            printf("%d ", temp->data);
            temp = temp->next;
        } while (temp != head);
    }
    printf("\n");
}

插入节点

在单向环形链表中插入节点时，需要考虑插入位置的不同情况，比如在头部插入、在尾部插入或在中间插入。

void insertNode(struct Node** head, int data, int position) {
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;

    if (*head == NULL) {
        newNode->next = newNode;
        *head = newNode;
        return;
    }

    struct Node* temp = *head;
    if (position == 1) {
        newNode->next = *head;
        while (temp->next != *head) {
            temp = temp->next;
        }
        temp->next = newNode;
        *head = newNode;
    } else {
        for (int i = 1; i < position - 1; i++) {
            temp = temp->next;
        }
        newNode->next = temp->next;
        temp->next = newNode;
    }
}

删除节点

删除节点时，同样需要考虑删除位置的不同情况，比如删除头节点、删除尾节点或删除中间节点。

void deleteNode(struct Node** head, int position) {
    if (*head == NULL) {
        return;
    }

    struct Node *temp = *head, *prev = NULL;
    if (position == 1) {
        while (temp->next != *head) {
            temp = temp->next;
        }
        temp->next = (*head)->next;
        free(*head);
        *head = temp->next;
    } else {
        for (int i = 1; i < position; i++) {
            prev = temp;
            temp = temp->next;
        }
        prev->next = temp->next;
        free(temp);
    }
}

总结

单向环形链表是一种非常有用的数据结构，特别适用于需要循环处理的场景。通过C语言的结构体和指针，我们可以轻松地实现单向环形链表的创建、遍历、插入和删除操作。掌握这些基本操作，可以帮助我们更好地理解和应用链表结构。

亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>