C语言实题讲解快速掌握单链表上

C语言实题讲解快速掌握单链表

什么是单链表？

单链表是一种链式存储的线性数据结构，它由一系列称为节点的组成。每个节点都包括两个部分：数据域和指针域。指针域指示了下一个节点的地址，因此，我们可以通过遍历链表的方式访问所有节点。

单链表的操作

创建一个单链表

我们可以通过以下步骤来创建一个单链表：
1. 定义单链表的节点结构体，包括数据域和指针域。
2. 定义一个指针变量作为头指针，并分配内存空间。
3. 将所有节点依次插入链表中。

// 定义节点结构体
typedef struct Node {
    int data;
    struct Node *next;
} Node;

// 创建单链表
Node* createList(int data[], int length) {
    // 定义头结点
    Node *head = malloc(sizeof(Node));
    head->next = NULL;
    Node *tail = head;

    // 将数据依次插入链表中
    for (int i = 0; i < length; i++) {
        Node *newNode = malloc(sizeof(Node));
        newNode->data = data[i];
        newNode->next = NULL;
        tail->next = newNode;
        tail = tail->next;
    }

    return head;
}

插入节点

在单链表中插入一个新节点通常需要知道两个节点的位置：待插入节点的前驱节点和后继节点。我们可以通过遍历单链表的方式找到这两个节点，并插入新节点。

// 在单链表中插入一个新节点
void insertNode(Node *head, int index, int data) {
    // 找到待插入节点的前驱节点和后继节点
    Node *p = head;
    for (int i = 1; i < index && p; i++) {
        p = p->next;
    }

    if (!p) {
        printf("Error: invalid index\n");
        return;
    }

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

删除节点

在单链表中删除一个节点同样需要知道待删除节点的前驱节点和后继节点。我们可以通过遍历单链表的方式找到这两个节点，并删除待删除节点。

// 在单链表中删除一个节点
void deleteNode(Node *head, int index) {
    // 找到待删除节点的前驱节点和后继节点
    Node *p = head;
    for (int i = 1; i < index && p; i++) {
        p = p->next;
    }

    if (!p || !p->next) {
        printf("Error: invalid index\n");
        return;
    }

    Node *temp = p->next;
    p->next = temp->next;
    free(temp);
}

示例说明

假设我们需要操作以下链表：1 -> 2 -> 3 -> 4 -> 5

示例1：在链表中插入一个新节点

插入一个新节点8到链表的第2个位置，操作后链表为：1 -> 8 -> 2 -> 3 -> 4 -> 5

Node *list = createList((int[]){1, 2, 3, 4, 5}, 5);
insertNode(list, 2, 8);

示例2：删除链表中的一个节点

删除链表的第3个节点，操作后链表为：1 -> 2 -> 4 -> 5

Node *list = createList((int[]){1, 2, 3, 4, 5}, 5);
deleteNode(list, 3);