一、动态数据结构

1. 解决的问题

  • 通过指针将零散的动态分配的内存空间（节点）连接成特定的逻辑结构
    • 内存管物理存储：哪里有空放哪里
    • 指针管逻辑关系：串联不同内存块（节点）之间的关系

2. 构建动态数据结构依赖的核心机制

  1. 自引用结构体：定义了同一数据结构中的内存块（节点）长什么样
  2. 堆内存管理：按需向系统租借与归还空间
  3. 指针链接：不搬动数据，只重画箭头，决定了不同内存块（节点）之间的关系

3. 结构体 struct

3.1 作用

  • 结构体把不同类型的数据打包组合成一个整体

3.2 定义结构体

// 定义一个名为 Student 的结构体类型（设计模具）
struct Student {
    int id;          // 学号 (整型)
    char name[20];   // 姓名 (字符数组)
    float score;     // 成绩 (浮点型)
};

3.3 使用结构体

法1：直接声明与初始化

#include <stdio.h>

struct Student {
    int id;
    char name[20];
    float score;
};

int main() {
    // 1. 声明一个结构体变量 s1，并用 { ... } 依次赋值
    struct Student s1 = {1001, "Alice", 95.5};

    // 2. 使用 点操作符 (.) 访问结构体内部的成员
    printf("学号: %d\n", s1.id);
    printf("姓名: %s\n", s1.name);
    printf("成绩: %.1f\n", s1.score);

    // 3. 修改成员的值
    s1.score = 98.0;
    printf("修改后的成绩: %.1f\n", s1.score);

    return 0;
}

法2：用 typedef 简化写法

// 使用 typedef 给结构体起个别名叫 Student
typedef struct Student {
    int id;
    char name[20];
    float score;
} Student; // 这里的 Student 是别名

int main() {
    // 现在可以直接用 Student 来声明变量了，不用再写 struct 关键字
    Student s2 = {1002, "Bob", 88.0};
    printf("学号: %d, 姓名: %s\n", s2.id, s2.name);
    return 0;
}

3.4 结构体可以嵌套；有结构体数组

3.5 自引用结构体

  • 结构体内部包含了一个指向"与自己同种类型结构体"的指针

经典定义：

typedef struct Node {
    int data;           // 用来存实际的数据
    struct Node *next;  // 存【下一个同类型节点】的内存地址
} Node;

4. 链表（一维线性结构）

  • 每个节点只有一个主方向指针（如 next），把零散的节点串成一条线

4.1 头插法

  • 把新节点添加到最前面，先连后断
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;  
} Node;

/* 头插法函数：修改头指针的指向，需要传递二级指针 (Node **head_ref) */
void insertAtHead(Node **head_ref, int newData) {
    // 1. 动态向系统"租"一块新节点空间
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = newData;

    // 2. 第一步（先连）：新节点的 next 指向当前的头节点
    newNode->next = *head_ref;

    // 3. 第二步（后断）：更新头指针，让它指向新节点
    *head_ref = newNode;
}

4.2 遍历打印链表

// 遍历打印链表
void printList(Node *head) {
    Node *current = head; // 设立临时探针指针，防止丢失头指针
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next; // 沿着指针走一步
    }
    printf("NULL\n");
}

4.3 指针层级说明

  • 一级指针：存普通变量的内存地址，用于修改数据
  • 二级指针：存一级指针的内存地址，用于修改指针

5. 树：层级结构（一种特殊无环的图）

  • 例如二叉树：每个节点有两个分支节点

节点定义：

typedef struct TreeNode {
    int data;                   // 存数据
    struct TreeNode *left;      // 指向左子节点的指针
    struct TreeNode *right;     // 指向右子节点的指针
} TreeNode;

创建与使用示例：

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

// 创建新节点
TreeNode* createNode(int value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

int main() {
    // 手动构建一棵简单的树：
    //       1
    //      / \
    //     2   3
    TreeNode *root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);

    return 0;
}