关于#数据结构#的问题，如何解决？

Question

1. 内存碎片整理
   问题描述：由于频繁的内存申请和释放，会产生大量的内存碎片，假设用链
   表管理内存的分配与回收，要求实现对存在内存碎片内存进行整理，将不连续的
   已释放的内存合并成大块内存。（要求在原链表上操作）
   管理内存的节点定义如下：
   Struct Node{
   Int length；//内存大小
   Int flag； //1 表示被占用，0 表示已释放
   Struct Node*next;
   };
   【输入形式】
   输入第一行为整数 n，表示要输入 n 对数；
   第二行输入 n 对整，每一对数字中，第一个为内存大小，第二个为是占用还
   是释放。例如：23 1 21 0，输入了两对数字，第一对表示内存大小为 23，被占用，
   第二对表示内存大小为 21，已经释放。
   【输出形式】
   对内存碎片进行整理后的管理链表
   【样例输入】
   5
   12 0 23 1
   最好用c描述一下

Answer 1

该回答引用GPTᴼᴾᴱᴺᴬᴵ
以下是一个 C 语言实现的示例代码，用于对存在内存碎片的链表进行整理，将不连续的已释放的内存合并成大块内存：

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

typedef struct Node {
    int length;  // 内存大小
    int flag;    // 1 表示被占用，0 表示已释放
    struct Node* next;
} Node;

Node* merge_memory(Node* head) {
    if (!head || !head->next) {
        return head;
    }

    Node* p = head->next;
    Node* prev = head;

    while (p) {
        if (prev->flag == 0 && p->flag == 0) {  // 连续的已释放内存块
            prev->length += p->length;
            prev->next = p->next;
            free(p);
            p = prev->next;
        } else {
            prev = p;
            p = p->next;
        }
    }

    return head;
}

Node* insert_memory(Node* head, int length, int flag) {
    Node* p = (Node*)malloc(sizeof(Node));
    p->length = length;
    p->flag = flag;
    p->next = NULL;

    Node* prev = head;
    Node* cur = head->next;

    while (cur) {
        if (cur->length > p->length) {  // 按内存大小从小到大插入
            p->next = cur;
            prev->next = p;
            break;
        } else {
            prev = cur;
            cur = cur->next;
        }
    }

    if (!cur) {  // 插入到链表尾部
        prev->next = p;
    }

    return head;
}

void print_memory(Node* head) {
    if (!head || !head->next) {
        printf("链表为空！");
        return;
    }

    Node* p = head->next;
    while (p) {
        printf("%d ", p->length);
        if (p->flag == 1) {
            printf("被占用\n");
        } else {
            printf("已释放\n");
        }
        p = p->next;
    }
}

int main() {
    int n;
    scanf("%d", &n);

    Node* head = (Node*)malloc(sizeof(Node));
    head->next = NULL;

    for (int i = 0; i < n; i++) {
        int length, flag;
        scanf("%d %d", &length, &flag);
        head = insert_memory(head, length, flag);
    }

    head = merge_memory(head);
    print_memory(head);

    return 0;
}

该示例代码的基本思路是：先按内存大小从小到大将内存块插入到链表中，然后遍历链表，将相邻的已释放内存块合并成大块内存。需要注意的是，要在原链表上进行操作，因此需要用指针来操作链表节点。