进阶学习计划：数据结构与算法

第1节：链表

链表是一种基础的数据结构，由一组节点组成，每个节点包含数据和一个指向下一个节点的指针。

学习内容：

1. 单链表：基本概念和实现（插入、删除、遍历）
2. 双向链表：双向链接和双向遍历
3. 循环链表：循环结构的链表
4. 链表操作的复杂度分析

开始学习：单链表

单链表是一种简单的链表，其中每个节点包含数据和一个指向下一个节点的指针。链表的优点是插入和删除操作可以在O(1)时间复杂度内完成，而缺点是需要额外的内存存储指针信息，访问元素的时间复杂度为O(n)。

1.1 单链表的基本实现

首先，我们实现一个简单的单链表，包括插入、删除和遍历操作。

单链表节点的定义：

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

// 定义链表节点
struct Node {
    int data; // 数据域
    struct Node* next; // 指针域，指向下一个节点
};

函数：创建新节点

// 创建新节点
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // 动态分配内存
    if (!newNode) { // 检查内存分配是否成功
        printf("Memory allocation failed\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

函数：插入新节点

// 在链表末尾插入新节点
void insertNode(struct Node** head, int data) {
    struct Node* newNode = createNode(data); // 创建新节点
    if (!newNode) return; // 如果节点创建失败，直接返回

    if (*head == NULL) { // 如果链表为空，新节点作为头节点
        *head = newNode;
        return;
    }

    struct Node* temp = *head;
    while (temp->next != NULL) { // 遍历链表，找到最后一个节点
        temp = temp->next;
    }
    temp->next = newNode; // 在链表末尾插入新节点
}

函数：删除节点

// 删除链表中的一个节点
void deleteNode(struct Node** head, int key) {
    struct Node* temp = *head;
    struct Node* prev = NULL;

    // 如果头节点就是要删除的节点
    if (temp != NULL && temp->data == key) {
        *head = temp->next; // 将头节点指向下一个节点
        free(temp); // 释放旧头节点的内存
        return;
    }

    // 查找要删除的节点
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    // 如果找不到要删除的节点
    if (temp == NULL) return;

    // 从链表中删除节点
    prev->next = temp->next;
    free(temp); // 释放节点的内存
}

函数：打印链表

// 打印链表
void printList(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

完整示例：使用单链表

int main() {
    struct Node* head = NULL; // 初始化链表为空

    insertNode(&head, 1);
    insertNode(&head, 2);
    insertNode(&head, 3);
    insertNode(&head, 4);

    printf("Linked List: ");
    printList(head);

    deleteNode(&head, 3);
    printf("After deleting 3: ");
    printList(head);

    return 0;
}

编译和运行

gcc linked_list.c -o linked_list
./linked_list

你可以从上面的代码开始，自己动手编写和调试单链表的实现，并进一步扩展其功能，比如实现反转链表、查找节点等。

接下来的学习

1. 练习： 实现一个函数来反转单链表。
2. 练习： 实现一个函数来查找链表中的第N个节点。
3. 学习双向链表： 学习如何实现双向链表，包括插入、删除、遍历等操作。
4. 学习循环链表： 学习如何实现循环链表，并理解其应用场景。

完成这些任务后，如果你对链表有了深入的理解，我们可以继续深入学习其他数据结构，如栈、队列、树等。