【数据结构】线性表（三）循环链表的各种操作（创建、插入、查找、删除、修改、遍历打印、释放内存空间）

线性表的定义及其基本操作（顺序表插入、删除、查找、修改）

一个线性表是由零个或多个具有相同类型的结点组成的有序集合。

按照线性表结点间的逻辑顺序依次将它们存储于一组地址连续的存储单元中的存储方式被称为线性表的顺序存储方式。按顺序存储方式存储的线性表具有顺序存储结构，一般称之为顺序表。换言之，在程序中采用定长的一维数组，按照顺序存储方式存储的线性表，被称为顺序表。

【数据结构】线性表（一）线性表的定义及其基本操作（顺序表插入、删除、查找、修改）-CSDN博客

https://blog.csdn.net/m0_63834988/article/details/132089038?spm=1001.2014.3001.5501

四、线性表的链接存储结构

1. 单链表

顺序表的优点是存取速度快。但是，无论是插入一个结点，还是删除一个结点，都需要调整一批结点的地址。要克服该缺点，就必须给出一种不同于顺序存储的存储方式。用链接存储方式存储的线性表被称为链表，可以克服上述缺点。

链表中的结点用存储单元（若干个连续字节）来存放，存储单元之间既可以是（存储空间上）连续的，也可以是不连续的，甚至可以零散地分布在存储空间中的任何位置。换言之，链表中结点的逻辑次序和物理次序之间并无必然联系。最重要的是，链表可以在不移动结点位置的前提下根据需要随时添加删除结点，动态调整。

【数据结构】线性表（二）单链表及其基本操作（创建、插入、删除、修改、遍历打印）-CSDN博客

https://blog.csdn.net/m0_63834988/article/details/133914875?spm=1001.2014.3001.5501

2. 循环链表

从单链表的一个结点出发，只能访问到链接在它后面的结点，而无法访问位于它前面的结点，这对一些实际应用很不方便。解决的办法是把链接结构“循环化”，即把表尾结点的next域存放指向哨位结点的指针，而不是存放空指针NULL，这样的单链表被称为循环链表。循环链表使用户可以从链表的任何位置开始，访问链表中的任意结点。

a. 循环链表节点结构体

代码语言：javascript复制

typedef struct Node {
    int data;           // 数据域
    struct Node *next;  // 指针域
} Node;

包含一个整型数据域 data 和一个指向下一个节点的指针域 next。

b. 创建新节点

代码语言：javascript复制

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

• 创建一个新的节点并返回指向该节点的指针：
  • 使用 malloc 分配了节点的内存空间；
  • 将传入的数据赋值给节点的 data 字段，并将 next 字段设置为 NULL。

c. 在循环链表末尾插入节点

代码语言：javascript复制

void insert(Node** head, int data) {
    Node* newNode = createNode(data);

    if (*head == NULL) {
        *head = newNode;
        (*head)->next = *head;  // 将尾节点指向头节点，形成循环
    } else {
        Node* temp = *head;
        while (temp->next != *head) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->next = *head;
    }
}

• 调用 createNode 函数创建一个新节点，并将新节点的指针保存在 newNode 中。
• 检查链表是否为空
  • 如果为空，则将 head 指向新节点，并将新节点的指针域 next 设置为指向自己，这样形成一个只有一个节点的循环链表。

    

  • 如果链表不为空，遍历链表找到尾节点，将尾节点的指针域 next 指向新节点，新节点的指针域 next 指向头节点，完成节点的插入操作。

d. 删除循环链表中指定值的节点

代码语言：javascript复制

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

    Node* currNode = *head;
    Node* prevNode = NULL;

    while (currNode->next != *head) {
        if (currNode->data == data) {
            if (prevNode == NULL) {
                Node* lastNode = *head;
                while (lastNode->next != *head) {
                    lastNode = lastNode->next;
                }
                *head = currNode->next;
                lastNode->next = *head;
            } else {
                prevNode->next = currNode->next;
            }
            free(currNode);
            return;
        }

        prevNode = currNode;
        currNode = currNode->next;
    }

    if (currNode->data == data) {
        if (prevNode == NULL) {
            *head = NULL;
        } else {
            prevNode->next = *head;
        }
        free(currNode);
    }
}

• 检查链表是否为空，如果为空则直接返回。
• 定义两个指针 currNode 和 prevNode
  • currNode 指向当前节点，初始时指向头节点
  • prevNode指向前一个节点，初始为 NULL
• 遍历链表，如果找到了与指定值相等的节点，则判断该节点是否为头节点，
  • 如果是头节点，则需要找到尾节点将其指向新的头节点，并更新 *head 的值为删除节点的下一个节点，最后释放删除节点的内存。
  • 如果不是头节点，直接将前一个节点的指针域 next 指向删除节点的下一个节点，然后释放删除节点的内存。

e. 在循环链表中查找指定值的节点

代码语言：javascript复制

Node* search(Node* head, int data) {
    if (head == NULL) {
        return NULL;
    }

    Node* currNode = head;

    while (currNode->next != head) {
        if (currNode->data == data) {
            return currNode;
        }
        currNode = currNode->next;
    }

    if (currNode->data == data) {
        return currNode;
    }

    return NULL;
}

• 链表是否为空，如果为空则返回 NULL。
• 定义一个指针 currNode，初始时指向头节点。
• 遍历链表，如果找到了与指定值相等的节点，则返回该节点的指针。
• 如果遍历完整个链表都没找到相等的节点，则返回 NULL。

f. 修改循环链表中指定节点的值

代码语言：javascript复制

void modify(Node* head, int oldData, int newData) {
    Node* nodeToModify = search(head, oldData);

    if (nodeToModify != NULL) {
        nodeToModify->data = newData;
    }
}

• 调用上述e中 search 函数查找指定值的节点，并将返回的节点指针保存在 nodeToModify 中
• 如果找到了节点，则将该节点的数据域 data 更新为 newData。

g. 打印循环链表

代码语言：javascript复制

void printList(Node* head) {
    if (head == NULL) {
        printf("循环链表为空n");
        return;
    }

    Node* currNode = head;

    do {
        printf("%d ", currNode->data);
        currNode = currNode->next;
    } while (currNode != head);

    printf("n");
}

• 检查链表是否为空，如果为空则打印提示信息并返回。
• 定义一个指针 currNode，初始时指向头节点。
• 使用 do-while 循环遍历链表，打印当前节点的数据，然后将指针移动到下一个节点，直到回到头节点为止。

h. 释放循环链表内存空间

代码语言：javascript复制

void freeList(Node** head) {
    if (*head == NULL) {
        return;
    }

    Node* currNode = *head;
    Node* nextNode = NULL;

    while (currNode->next != *head) {
        nextNode = currNode->next;
        free(currNode);
        currNode = nextNode;
    }

    free(currNode);
    *head = NULL;
}

• 检查链表是否为空，如果为空则直接返回。
• 定义两个指针 currNode 和 nextNode
  • currNode 指向当前节点，初始时指向头节点
  • nextNode指向下一个节点，初始为 NULL
• 使用 while 循环遍历链表，将 nextNode 指向 currNode 的下一个节点，释放 currNode 指向的节点的内存，然后将 currNode 更新为 nextNode。重复以上步骤，直到遍历完整个链表，并最后释放头节点的内存。

i. 主函数

代码语言：javascript复制

int main() {
    Node* head = NULL;

    // 在循环链表中插入节点
    insert(&head, 10);
    insert(&head, 20);
    insert(&head, 30);
    insert(&head, 40);

    // 打印循环链表
    printf("循环链表: ");
    printList(head);

    // 删除循环链表中的节点
    deleteNode(&head, 20);

    // 打印删除节点后的循环链表
    printf("删除节点后的循环链表: ");
    printList(head);

    // 在循环链表中查找节点
    Node* searchResult = search(head, 30);
    if (searchResult != NULL) {
        printf("找到节点 %dn", searchResult->data);
    } else {
        printf("未找到节点n");
    }

    // 修改循环链表中的节点值
    modify(head, 30, 50);

    // 打印修改节点值后的循环链表
    printf("修改节点值后的循环链表: ");
    printList(head);

    // 释放循环链表内存空间
    freeList(&head);

    return 0;
}

• 定义一个指向头节点的指针 head，初始时为 NULL。
• 通过调用 insert 函数，在循环链表中插入了四个节点，其数据分别为 10、20、30 和 40。
• 调用 deleteNode 函数删除了值为 20 的节点，并再次调用 printList 函数打印删除节点后的循环链表。
• 调用 search 函数查找值为 30 的节点，并根据返回结果打印相应的信息。
• 调用 modify 函数修改值为 30 的节点的数据为 50，
• 最后调用 freeList 函数释放循环链表占用的内存空间。

j. 代码整合

代码语言：javascript复制

#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));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 在循环链表末尾插入节点
void insert(Node** head, int data) {
    Node* newNode = createNode(data);

    if (*head == NULL) {
        *head = newNode;
        (*head)->next = *head;  // 将尾节点指向头节点，形成循环
    } else {
        Node* temp = *head;
        while (temp->next != *head) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->next = *head;
    }
}

// 删除循环链表中指定值的节点
void deleteNode(Node** head, int data) {
    if (*head == NULL) {
        return;
    }

    Node* currNode = *head;
    Node* prevNode = NULL;

    while (currNode->next != *head) {
        if (currNode->data == data) {
            if (prevNode == NULL) {
                Node* lastNode = *head;
                while (lastNode->next != *head) {
                    lastNode = lastNode->next;
                }
                *head = currNode->next;
                lastNode->next = *head;
            } else {
                prevNode->next = currNode->next;
            }
            free(currNode);
            return;
        }

        prevNode = currNode;
        currNode = currNode->next;
    }

    if (currNode->data == data) {
        if (prevNode == NULL) {
            *head = NULL;
        } else {
            prevNode->next = *head;
        }
        free(currNode);
    }
}

// 在循环链表中查找指定值的节点
Node* search(Node* head, int data) {
    if (head == NULL) {
        return NULL;
    }

    Node* currNode = head;

    while (currNode->next != head) {
        if (currNode->data == data) {
            return currNode;
        }
        currNode = currNode->next;
    }

    if (currNode->data == data) {
        return currNode;
    }

    return NULL;
}

// 修改循环链表中指定节点的值
void modify(Node* head, int oldData, int newData) {
    Node* nodeToModify = search(head, oldData);

    if (nodeToModify != NULL) {
        nodeToModify->data = newData;
    }
}

// 打印循环链表
void printList(Node* head) {
    if (head == NULL) {
        printf("循环链表为空n");
        return;
    }

    Node* currNode = head;

    do {
        printf("%d ", currNode->data);
        currNode = currNode->next;
    } while (currNode != head);

    printf("n");
}

// 释放循环链表内存空间
void freeList(Node** head) {
    if (*head == NULL) {
        return;
    }

    Node* currNode = *head;
    Node* nextNode = NULL;

    while (currNode->next != *head) {
        nextNode = currNode->next;
        free(currNode);
        currNode = nextNode;
    }

    free(currNode);
    *head = NULL;
}

int main() {
    Node* head = NULL;

    // 在循环链表中插入节点
    insert(&head, 10);
    insert(&head, 20);
    insert(&head, 30);
    insert(&head, 40);

    // 打印循环链表
    printf("循环链表: ");
    printList(head);

    // 删除循环链表中的节点
    deleteNode(&head, 20);

    // 打印删除节点后的循环链表
    printf("删除节点后的循环链表: ");
    printList(head);

    // 在循环链表中查找节点
    Node* searchResult = search(head, 30);
    if (searchResult != NULL) {
        printf("找到节点 %dn", searchResult->data);
    } else {
        printf("未找到节点n");
    }

    // 修改循环链表中的节点值
    modify(head, 30, 50);

    // 打印修改节点值后的循环链表
    printf("修改节点值后的循环链表: ");
    printList(head);

    // 释放循环链表内存空间
    freeList(&head);

    return 0;
}

指针 数据结构 遍历 函数 链表

0 人点赞