040. 使用动态内存分配创建数据结构

在C语言中，动态内存分配是创建和管理复杂数据结构（如链表、树、图等）的关键技术。通过动态内存分配，可以在运行时根据需要分配和释放内存，从而实现灵活的数据结构。C语言提供了几个标准库函数来管理动态内存分配，包括malloc、calloc、realloc和free。

以下将通过具体示例展示如何使用动态内存分配创建常见的数据结构，如链表、二叉树等。

1. 动态内存分配函数

• malloc：分配指定大小的内存，返回指向分配内存的指针。

void *malloc(size_t size);

• calloc：分配指定大小的内存，并初始化为零。

void *calloc(size_t num, size_t size);

• realloc：调整已分配内存的大小。

void *realloc(void *ptr, size_t size);

• free：释放之前分配的内存。

void free(void *ptr);

2. 创建链表

链表是一种常见的动态数据结构，由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。

定义链表节点

#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 == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void insertAtHead(struct Node **head, int data) {
    struct Node *newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

void printList(struct Node *head) {
    struct Node *current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

void freeList(struct Node *head) {
    struct Node *current = head;
    while (current != NULL) {
        struct Node *temp = current;
        current = current->next;
        free(temp);
    }
}

int main() {
    struct Node *head = NULL;
    insertAtHead(&head, 3);
    insertAtHead(&head, 2);
    insertAtHead(&head, 1);

    printList(head);

    freeList(head);
    printf("Memory freed\n");

    return 0;
}

输出结果

1 -> 2 -> 3 -> NULL
Memory freed

3. 创建二叉树

二叉树是一种常见的树形数据结构，每个节点最多有两个子节点（左子节点和右子节点）。

定义二叉树节点

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

struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
};

创建二叉树

struct TreeNode* createNode(int data) {
    struct TreeNode *newNode = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

void insert(struct TreeNode **root, int data) {
    if (*root == NULL) {
        *root = createNode(data);
    } else {
        struct TreeNode *current = *root;
        while (1) {
            if (data < current->data) {
                if (current->left == NULL) {
                    current->left = createNode(data);
                    break;
                } else {
                    current = current->left;
                }
            } else {
                if (current->right == NULL) {
                    current->right = createNode(data);
                    break;
                } else {
                    current = current->right;
                }
            }
        }
    }
}

void inorderTraversal(struct TreeNode *root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

void freeTree(struct TreeNode *root) {
    if (root != NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

int main() {
    struct TreeNode *root = NULL;
    insert(&root, 5);
    insert(&root, 3);
    insert(&root, 7);
    insert(&root, 2);
    insert(&root, 4);
    insert(&root, 6);
    insert(&root, 8);

    printf("Inorder traversal: ");
    inorderTraversal(root);
    printf("\n");

    freeTree(root);
    printf("Memory freed\n");

    return 0;
}

输出结果

Inorder traversal: 2 3 4 5 6 7 8 
Memory freed

4. 创建动态数组

动态数组可以在运行时分配和调整大小，使用malloc和realloc可以实现。

创建动态数组

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

int main() {
    int *arr = (int *)malloc(5 * sizeof(int)); // 分配5个整数的内存
    if (arr == NULL) {
        printf("Memory allocation failed\n");
        return 1;
    }

    // 初始化数组
    for (int i = 0; i < 5; i++) {
        arr[i] = i + 1;
    }

    // 打印数组
    for (int i = 0; i < 5; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    // 调整数组大小
    int *newArr = (int *)realloc(arr, 10 * sizeof(int));
    if (newArr == NULL) {
        printf("Memory reallocation failed\n");
        free(arr);
        return 1;
    }
    arr = newArr;

    // 初始化新分配的内存
    for (int i = 5; i < 10; i++) {
        arr[i] = i + 1;
    }

    // 打印新数组
    for (int i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    // 释放内存
    free(arr);
    printf("Memory freed\n");

    return 0;
}

输出结果

1 2 3 4 5 
1 2 3 4 5 6 7 8 9 10 
Memory freed

通过上述示例，你可以看到如何在C语言中使用动态内存分配创建和管理复杂的数据结构：

1. 链表：通过动态分配内存创建节点，并将节点连接起来。
2. 二叉树：通过动态分配内存创建节点，并根据规则插入节点。
3. 动态数组：使用malloc和realloc动态分配和调整数组大小。

视频讲解

BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)