C语言实例真题讲解数据结构中单向环形链表

1. 单向链表简介

单向链表是数据结构中的一种基础数据类型，是由一系列节点组成的，每个节点都包含了数据和指向下一个节点的指针。链表的优点是可以动态地添加和删除元素，但缺点是访问元素的效率相对较低。

2. 单向链表的扩展性

由于链表的动态性，我们可以对其进行扩展，使得其可以满足更复杂的需求。其中一个扩展便是单向环形链表。单向环形链表与单向链表相比，多了一个特点：最后一个节点的指针指向起始节点。

3. 单向环形链表的实现方法

3.1 链表节点的定义

在单向链表中，每个节点包含了数据和指向下一个节点的指针。而在单向环形链表中，最后一个节点的指针指向起始节点。所以，我们可以在单向链表的基础上进行修改，定义每个节点为：

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

3.2 环形链表的初始化

环形链表的初始化需要设置链表的头节点，并将其指向起始节点。我们可以在链表的定义中添加一个指向头节点的指针，代码如下：

typedef struct list{
    Node* head;
}List;

List* createList(){
    List* list = (List*)malloc(sizeof(List));
    list->head = NULL;
    return list;
}

3.3 插入节点

插入节点的过程与单向链表相同，但需要注意的是，插入操作需要修改最后一个节点的指针，使其指向起始节点。代码如下：

void insertNode(List* list, int data){
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    if(list->head == NULL){
        // 链表为空，直接将首节点指向当前节点
        list->head = node;
        // 将尾节点的指针指向首结点
        list->head->next = list->head;
        return;
    }
    Node* tail = list->head;
    while(tail->next != list->head){
        tail = tail->next;
    }
    tail->next = node;
    node->next = list->head;
}

3.4 删除节点

删除节点也需要修改最后一个节点的指针。代码如下：

void deleteNode(List* list, int data){
    if(list->head == NULL){
        return;
    }
    if(list->head->data == data){
        // 删除的是头结点
        Node* p = list->head;
        while(p->next != list->head){
            p = p->next;
        }
        if(p == list->head){
            // 链表中只有一个结点
            list->head = NULL;
            free(p);
            return;
        }
        p->next = list->head->next;
        free(list->head);
        list->head = p->next;
        return;
    }
    Node* p = list->head;
    Node* pre = NULL;
    while(p->next != list->head){
        pre = p;
        p = p->next;
        if(p->data == data){
            break;
        }
    }
    if(p == list->head){
        // 删除的是尾结点
        pre->next = list->head;
    }else{
        pre->next = p->next;
    }
    free(p);
}

4. 示例说明

4.1 插入和删除操作

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

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

typedef struct list{
    Node* head;
}List;

List* createList(){
    List* list = (List*)malloc(sizeof(List));
    list->head = NULL;
    return list;
}

void insertNode(List* list, int data){
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    if(list->head == NULL){
        // 链表为空，直接将首节点指向当前节点
        list->head = node;
        // 将尾节点的指针指向首结点
        list->head->next = list->head;
        return;
    }
    Node* tail = list->head;
    while(tail->next != list->head){
        tail = tail->next;
    }
    tail->next = node;
    node->next = list->head;
}

void deleteNode(List* list, int data){
    if(list->head == NULL){
        return;
    }
    if(list->head->data == data){
        // 删除的是头结点
        Node* p = list->head;
        while(p->next != list->head){
            p = p->next;
        }
        if(p == list->head){
            // 链表中只有一个结点
            list->head = NULL;
            free(p);
            return;
        }
        p->next = list->head->next;
        free(list->head);
        list->head = p->next;
        return;
    }
    Node* p = list->head;
    Node* pre = NULL;
    while(p->next != list->head){
        pre = p;
        p = p->next;
        if(p->data == data){
            break;
        }
    }
    if(p == list->head){
        // 删除的是尾结点
        pre->next = list->head;
    }else{
        pre->next = p->next;
    }
    free(p);
}

void printList(List* list){
    if(list->head == NULL){
        printf("链表为空\n");
        return;
    }
    Node* p = list->head;
    do{
        printf("%d ", p->data);
        p = p->next;
    }while(p != list->head);
    printf("\n");
}

int main(){
    List* list = createList();
    insertNode(list, 1);
    insertNode(list, 2);
    insertNode(list, 3);
    insertNode(list, 4);
    insertNode(list, 5);
    printList(list);
    deleteNode(list, 1);
    deleteNode(list, 5);
    printList(list);
    return 0;
}

输出结果为：

1 2 3 4 5
2 3 4

4.2 约瑟夫问题的解决

约瑟夫问题是一个经典的问题：有 n 个人围成一圈，从某个人开始，从 1 开始报数，每次报到 m 的人出圈，然后从下一个人开始报数，直到剩下最后一个人。可以用单向环形链表来解决这个问题。

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

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

typedef struct list{
    Node* head;
}List;

List* createList(){
    List* list = (List*)malloc(sizeof(List));
    list->head = NULL;
    return list;
}

void createCircle(List* list, int n){
    int i;
    Node* pre = NULL;
    for(i = 1; i <= n; i++){
        Node* node = (Node*)malloc(sizeof(Node));
        node->id = i;
        if(pre != NULL){
            pre->next = node;
        }else{
            list->head = node;
        }
        pre = node;
    }
    pre->next = list->head;
}

void solveJosephProblem(List* list, int m){
    Node* p = list->head;
    Node* pre = NULL;
    while(p != p->next){
        int i = 1;
        while(i < m){
            pre = p;
            p = p->next;
            i++;
        }
        printf("%d 出圈\n", p->id);
        pre->next = p->next;
        Node* tmp = p;
        p = p->next;
        free(tmp);
    }
    printf("%d 为最后一位幸存者\n", p->id);
}

int main(){
    List* list = createList();
    createCircle(list, 6);
    solveJosephProblem(list, 3);
    return 0;
}

输出结果为：

3 出圈
6 出圈
1 出圈
5 出圈
2 出圈
4 为最后一位幸存者

总体来说，实现单向环形链表的过程并不复杂，但需要注意细节处理。可以根据实际需求对链表进行扩展，使得其可以满足更复杂的问题。

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：C语言实例真题讲解数据结构中单向环形链表 - Python技术站

C语言实例真题讲解数据结构中单向环形链表