C语言创建和操作单链表数据结构的实例教程

什么是单链表

单链表是一种常见的动态数据结构，它由一个个节点组成，每个节点包含范围内的数据和指向下一个节点的指针。单链表通常用于需要频繁插入删除节点的情况。

单链表的创建和操作步骤

创建单链表

1. 定义一个链表节点结构体，结构体中包含要存储的数据和指向下一个节点的指针。

2. 定义一个指向链表头部的指针，如果链表为空，则指针为空。

3. 创建链表节点，将数据存储到节点中，并将节点插入链表头部或尾部，直到链表完整。

示例代码：

struct ListNode {
    int val;
    struct ListNode* next;
};

typedef struct ListNode ListNode;

ListNode* createList() {
    ListNode* head = NULL;
    ListNode* tail = NULL;
    // 插入节点并赋值
    for(int i = 1; i <= 5; i++) {
        ListNode* node = (ListNode*)malloc(sizeof(ListNode));
        node->val = i;
        node->next = NULL;
        // 处理头指针和尾指针
        if(head == NULL) {
            head = node;
            tail = node;
        } else {
            tail->next = node;
            tail = node;
        }
    }
    return head;
}

遍历单链表

遍历单链表即是从链表头部开始访问每个节点，并输出节点中存储的数据。

示例代码：

void traverseList(ListNode* head) {
    ListNode* p = head;
    while(p != NULL) {
        printf("%d ", p->val);
        p = p->next;
    }
    printf("\n");
}

插入节点

插入节点可以在指定节点前或后插入，或者插入链表头部或尾部。

示例代码：

在指定节点前插入：

void insertNodeBefore(ListNode* head, ListNode* node, int val) {
    ListNode* p = head;
    while(p->next != NULL && p->next != node) {
        p = p->next;
    }
    if(p->next == NULL) {
        return ;
    }
    ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
    new_node->val = val;
    new_node->next = node;
    p->next = new_node;
}

在链表尾部插入：

void insertNodeAtTail(ListNode* head, int val) {
    ListNode* p = head;
    while(p->next != NULL) {
        p = p->next;
    }
    ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
    new_node->val = val;
    new_node->next = NULL;
    p->next = new_node;
}

删除节点

删除节点也有多种方式，可以删除指定节点或者按照值删除等。

示例代码：

删除指定节点：

void deleteNode(ListNode* head, ListNode* node) {
    ListNode* p = head;
    while(p->next != NULL && p->next != node) {
        p = p->next;
    }
    if(p->next == NULL) {
        return ;
    }
    p->next = node->next;
    free(node);
}

按照值删除：

void deleteNodeByValue(ListNode* head, int val) {
    ListNode* p = head;
    while(p->next != NULL && p->next->val != val) {
        p = p->next;
    }
    if(p->next == NULL) {
        return ;
    }
    ListNode* del_node = p->next;
    p->next = del_node->next;
    free(del_node);
}

示例

示例1：创建一个单链表并遍历

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

struct ListNode {
    int val;
    struct ListNode* next;
};

typedef struct ListNode ListNode;

ListNode* createList() {
    ListNode* head = NULL;
    ListNode* tail = NULL;
    // 插入节点并赋值
    for(int i = 1; i <= 5; i++) {
        ListNode* node = (ListNode*)malloc(sizeof(ListNode));
        node->val = i;
        node->next = NULL;
        // 处理头指针和尾指针
        if(head == NULL) {
            head = node;
            tail = node;
        } else {
            tail->next = node;
            tail = node;
        }
    }
    return head;
}

void traverseList(ListNode* head) {
    ListNode* p = head;
    while(p != NULL) {
        printf("%d ", p->val);
        p = p->next;
    }
    printf("\n");
}

int main() {
    ListNode* head = createList();
    traverseList(head);
    return 0;
}

输出结果如下：

1 2 3 4 5

示例2：在链表中插入一个值为6的节点

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

struct ListNode {
    int val;
    struct ListNode* next;
};

typedef struct ListNode ListNode;

ListNode* createList() {
    ListNode* head = NULL;
    ListNode* tail = NULL;
    // 插入节点并赋值
    for(int i = 1; i <= 5; i++) {
        ListNode* node = (ListNode*)malloc(sizeof(ListNode));
        node->val = i;
        node->next = NULL;
        // 处理头指针和尾指针
        if(head == NULL) {
            head = node;
            tail = node;
        } else {
            tail->next = node;
            tail = node;
        }
    }
    return head;
}

void traverseList(ListNode* head) {
    ListNode* p = head;
    while(p != NULL) {
        printf("%d ", p->val);
        p = p->next;
    }
    printf("\n");
}

void insertNodeAtTail(ListNode* head, int val) {
    ListNode* p = head;
    while(p->next != NULL) {
        p = p->next;
    }
    ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
    new_node->val = val;
    new_node->next = NULL;
    p->next = new_node;
}

int main() {
    ListNode* head = createList();
    insertNodeAtTail(head, 6);
    traverseList(head);
    return 0;
}

输出结果如下：

1 2 3 4 5 6

总结

本文介绍了创建和操作单链表的步骤，以及两个示例。在实际开发中，单链表的应用非常广泛，可以用于数据存储、任务调度等多种场景。