【重拾C语言】十三、动态数据组织（二）链表（创建、遍历检索、插入、删除、交换）

前言

链表是一种常见的动态数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。在C语言中，可以使用指针和动态内存分配函数来实现链表的创建、遍历、插入、删除和交换操作。

十三、动态数据组织

13.1~2 动态数据组织、动态变量

【重拾C语言】十三、动态数据组织_QomolangmaH的博客-CSDN博客

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

13.3 链表

13.3.1 单向链表—创建

创建一个单向链表的基本步骤包括定义节点结构和使用动态内存分配函数分配节点内存。节点结构通常包含两个成员：数据成员（用于存储数据）和指针成员（用于指向下一个节点）。通过将节点链接在一起，形成链表的结构。

代码语言：javascript复制

// 定义节点结构
struct Node {
    int data;           // 数据成员
    struct Node* next;  // 指针成员
};

// 创建链表
struct Node* createLinkedList() {
    struct Node* head = NULL;  // 头指针，指向链表的第一个节点
    struct Node* temp = NULL;  // 临时指针，用于创建新节点
    
    // 创建节点1
    struct Node* node1 = (struct Node*)malloc(sizeof(struct Node));
    node1->data = 1;
    node1->next = NULL;
    
    // 将节点1设为头节点
    head = node1;
    
    // 创建节点2
    struct Node* node2 = (struct Node*)malloc(sizeof(struct Node));
    node2->data = 2;
    node2->next = NULL;
    
    // 将节点2链接到节点1后面
    node1->next = node2;
    
    // 创建节点3
    struct Node* node3 = (struct Node*)malloc(sizeof(struct Node));
    node3->data = 3;
    node3->next = NULL;
    
    // 将节点3链接到节点2后面
    node2->next = node3;
    
    return head;  // 返回头指针
}

13.3.2 单向链表—遍历检索

遍历链表的过程是按顺序访问链表中的每个节点，并执行相应的操作。通过使用一个指针依次指向链表中的节点，可以遍历整个链表。

代码语言：javascript复制

// 遍历链表并打印节点数据
void traverseLinkedList(struct Node* head) {
    struct Node* current = head;  // 从头节点开始遍历
    
    while (current != NULL) {
        printf("%d ", current->data);  // 打印节点数据
        current = current->next;      // 移动到下一个节点
    }
}

13.3.3 单向链表—插入、删除与交换

在链表中插入、删除和交换节点是常见的操作，可以通过更新节点的指针来实现。

插入

代码语言：javascript复制

// 在链表中插入节点
void insertNode(struct Node* prevNode, int newData) {
    if (prevNode == NULL) {
        printf("Error: Previous node cannot be NULL.n");
        return;
    }
    
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

• 接收一个指向前一个节点的指针prevNode和要插入的新数据newData作为参数。
• 首先检查prevNode是否为NULL
  • 如果是，则打印错误消息并返回。
  • 否则，它创建一个新节点
    • 将newData赋值给新节点的data成员。
    • 将新节点的next指针设置为prevNode的下一个节点，并将prevNode的next指针指向新节点，完成插入操作。

删除

代码语言：javascript复制

// 在链表中删除节点
void deleteNode(struct Node* prevNode) {
    if (prevNode == NULL || prevNode->next == NULL) {
        printf("Error: Node to be deleted cannot be NULL.n");
        return;
    }
    
    struct Node* nodeToDelete = prevNode->next;
    prevNode->next = nodeToDelete->next;
    free(nodeToDelete);  // 释放内存
}

• 接收一个指向前一个节点的指针prevNode作为参数。
• 首先检查prevNode是否为NULL或者prevNode的下一个节点是否为NULL
  • 如果是，则打印错误消息并返回。
  • 否则，它获取要删除的节点的指针nodeToDelete，将prevNode的next指针指向nodeToDelete的下一个节点，然后释放nodeToDelete的内存，完成删除操作。

交换

代码语言：javascript复制

// 在链表中交换两个节点的位置
void swapNodes(struct Node* head, int data1, int data2) {
    if (data1 == data2) {
        printf("Error: Data values are the same.n");
        return;
    }
    
    struct Node* prevNode1 = NULL;
    struct Node* prevNode2 = NULL;
    struct Node* currentNode = head;
    
    while (currentNode != NULL) {
        if (currentNode->next != NULL && currentNode->next->data == data1)
            prevNode1 = currentNode;
        if (currentNode->next != NULL && currentNode->next->data == data2)
            prevNode2 = currentNode;
        
        currentNode = currentNode->next;
    }
    
    if (prevNode1 == NULL || prevNode2 == NULL) {
        printf("Error: Data values not found in the list.n");
        return;
    }
    
    struct Node* node1 = prevNode1->next;
    struct Node* node2 = prevNode2->next;
    
    if (prevNode1 != NULL)
        prevNode1->next = node2;
    else
        head = node2;
    
    if (prevNode2 != NULL)
        prevNode2->next = node1;
    else
        head = node1;
    
    struct Node* temp = node1->next;
    node1->next = node2->next;
    node2->next = temp;
}

• 接收链表的头节点指针head以及要交换的两个节点的数据值data1和data2作为参数。
• 首先检查data1和data2是否相等，如果相等，则打印错误消息并返回。然
• 使用三个指针变量prevNode1、prevNode2和currentNode来遍历链表，找到包含data1和data2的节点的前一个节点。
• 它检查prevNode1和prevNode2是否为NULL，如果为NULL，则打印错误消息并返回。
• 获取要交换的两个节点的指针node1和node2。
• 更新前一个节点的next指针，将node1的前一个节点的next指向node2，将node2的前一个节点的next指向node1，实现节点位置的交换。
• 它交换两个节点的next指针，完成交换操作。

13.3.4 单向链表—例题

下面是一个示例，演示了如何使用单向链表来实现一个简单的任务列表：

代码语言：javascript复制

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

struct Task {
    char name[100];
    struct Task* next;
};

struct Task* createTask(const char* name) {
    struct Task* task = (struct Task*)malloc(sizeof(struct Task));
    strcpy(task->name, name);
    task->next = NULL;
    return task;
}

void addTask(struct Task** head, const char* name) {
    struct Task* newTask = createTask(name);
    if (*head == NULL) {
        *head = newTask;
    } else {
        struct Task* current = *head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newTask;
    }
}

void printTasks(struct Task* head) {
    struct Task* current = head;
    while (current != NULL) {
        printf("%sn", current->name);
        current = current->next;
    }
}

int main() {
    struct Task* taskList = NULL;
    
    addTask(&taskList, "Task 1");
    addTask(&taskList, "Task 2");
    addTask(&taskList, "Task 3");
    
    printTasks(taskList);
    
    return 0;
}

任务列表struct Task结构体，包含一个名为name的字符数组和一个指向下一个任务的指针next。

• createTask(const char* name)函数用于创建一个新的任务节点：
  • 接收一个字符串name作为参数，动态分配内存来创建一个struct Task结构体，并将传入的name复制到name成员中。最后，它将next指针设置为NULL，并返回创建的任务节点。
• addTask(struct Task** head, const char* name)函数用于向任务列表中添加一个新的任务：
  • 接收一个指向任务列表头指针的指针head和一个字符串name作为参数。
  • 首先调用createTask函数创建一个新的任务节点。
  • 然后，它检查任务列表是否为空，如果是，则将新节点设置为头节点。否则，它遍历任务列表，找到最后一个节点，并将新节点添加为最后一个节点的下一个节点。
• printTasks(struct Task* head)函数用于打印任务列表中的所有任务：
  • 遍历任务列表，从头节点开始，逐个打印每个任务的名称。
• 在主函数中，首先创建一个空的任务列表taskList。然后，使用addTask函数向任务列表中添加了三个任务。最后，调用printTasks函数打印任务列表中的所有任务的名称。

输出：

代码语言：javascript复制

Task 1
Task 2
Task 3

13.3.5 栈和队列

除了链表，栈和队列也是常见的动态数据结构。栈是一种后进先出（LIFO）的数据结构，可以使用数组或链表来实现。队列是一种先进先出（FIFO）的数据结构，也可以使用数组或链表来实现。关于栈和队列的相关介绍详见后文。

链表 数据 指针 遍历 函数

0 人点赞