数据结构 C语言实现循环单链表的实例

首先，在开始讲解数据结构中循环单链表的实现前，需要明确循环单链表的概念以及其与单链表的区别。

循环单链表是一种链式存储结构，与单链表不同的是，在循环单链表的尾部也可以指向链表的头部，形成一个环。因此，我们可以通过尾部的指针来遍历整个循环单链表。

接下来，为了方便理解和学习，我们将使用C语言来实现循环单链表的实例。下面分几个步骤来讲解。

1. 定义结构体和创建循环单链表

首先，我们需要定义结构体来存储每个节点的数据和指向下一个节点的指针。此外，还需要定义一个头节点，用于记录链表的头部位置。

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

Node *head = NULL;

在定义好结构体和头节点后，我们需要编写一个函数来创建循环单链表，可以根据用户输入的数据，依次插入链表节点。

void createList()
{
    int n, i, data;
    Node *prevNode, *currNode;
    printf("Input the number of nodes: ");
    scanf("%d", &n);

    head = (Node*) malloc(sizeof(Node));

    if(head == NULL)
    {
        printf("Memory can not be allocated.");
        return;
    }

    // Head node does not contain any data, its next points to first node
    head->data = 0;
    head->next = NULL;

    prevNode = head;
    for(i = 0; i < n; i++)
    {
        printf("Input data for node %d: ", i + 1);
        scanf("%d", &data);

        currNode = (Node*) malloc(sizeof(Node));

        if(currNode == NULL)
        {
            printf("Memory can not be allocated.");
            break;
        }

        currNode->data = data;
        currNode->next = NULL;

        prevNode->next = currNode;
        prevNode = currNode;

        // Set the last node next to the head node
        if(i == n - 1)
        {
            currNode->next = head;
        }
    }
}

2. 遍历循环单链表

遍历循环单链表与遍历单链表的方式基本相同，只需要将遍历的终止条件做出相应的改变即可。

void printList()
{
    Node *currNode = head->next;
    printf("\nPrint List:\n");
    do
    {
        printf("%d\n", currNode->data);
        currNode = currNode->next;
    }while(currNode != head->next);
}

3. 插入节点

通过上面的代码，我们已经实现了循环单链表的创建和遍历操作，但是链表数据可能会动态增加，因此需要编写函数来插入新的节点。

void insertNode()
{
    Node *currNode = head->next;
    int data, loc, i = 1;

    printf("Enter location to insert a node: ");
    scanf("%d", &loc);

    while(i < loc-1 && currNode != head)
    {
        currNode = currNode->next;
        i++;
    }

    if(currNode == head && i != loc)
    {
       printf("Invalid location.\n");
       return;
    }

    printf("Enter data to insert a node at location %d: ", loc);
    scanf("%d", &data);

    Node *newNode=(Node *)malloc(sizeof(Node));
    newNode->data=data;

    newNode->next=currNode->next;
    currNode->next=newNode;

    if(currNode==head && loc!=1)
    {
       printf("Invalid location.\n");
       return;
    }
}

示例说明

假设我们要构建一个包含三个节点的循环单链表，并按顺序输入三个整数。

Input the number of nodes: 3
Input data for node 1: 10
Input data for node 2: 20
Input data for node 3: 30

执行完上述代码后，我们已经成功创建了一个包含三个节点的循环单链表。

接下来，让我们遍历链表，查看节点数据。

Print List:
10
20
30

我们可以看到，成功遍历了整个链表。

接着，我们尝试在第二个位置插入一个新的节点，并将数据设置为40。

Enter location to insert a node: 2
Enter data to insert a node at location 2: 40

最后，再次遍历链表，查看新的节点是否成功插入。

Print List:
10
40
20
30

可以看到，我们成功地在指定位置插入了一个新节点，并且数据正确。