C语言不使用malloc实现链表式内存分配与复用方案求助

问题分析 #

你的原代码存在几个不符合需求的核心问题：

• 用MemoryBlock结构管理空闲内存，却调用mymalloc分配该结构，形成循环依赖且占用额外内存
• 节点的next存储指针地址，无法满足内存窗口中数值从1递增的要求
• 内存池采用int数组，可能引发内存对齐问题，且无法精确控制字节级分配

核心实现思路 #

针对你的需求，调整后的方案如下：

• 固定内存池：用1MB的char数组作为初始内存，完全替代堆内存分配
• 节点结构优化：将next成员改为存储节点索引（从1开始），而非指针，确保内存中存储的数值连续递增
• 空闲链表复用：直接用空闲的Node节点自身组成空闲链表，无需额外管理结构
• 分配规则：优先从空闲链表取节点，无空闲节点时从内存池末尾依次分配，保证data和next数值从1开始递增

完整实现代码 #

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stddef.h>

#define MEMORY_SIZE (1024 * 1024) // 1MB内存池大小
#define NODE_SIZE sizeof(Node)    // 单个节点的字节大小

// 节点结构：next存储节点索引（从1开始，0表示NULL）
typedef struct Node {
    int data;
    int next; // 用索引代替指针，保证内存中数值递增
} Node;

// 全局内存池：预分配1MB内存
char memory_pool[MEMORY_SIZE];
// 已分配节点的计数（用于保证data和next从1递增）
int node_count = 0;
// 空闲链表的头节点索引（0表示无空闲节点）
int free_list_head = 0;

// 根据索引获取内存池中对应的节点地址
static Node* get_node_by_index(int index) {
    if (index <= 0 || index * NODE_SIZE > MEMORY_SIZE) {
        return NULL;
    }
    return (Node*)(memory_pool + (index - 1) * NODE_SIZE);
}

// 内存分配函数：返回节点地址，优先复用空闲节点
void* mymalloc() {
    Node* new_node = NULL;

    // 优先从空闲链表取节点
    if (free_list_head != 0) {
        new_node = get_node_by_index(free_list_head);
        // 更新空闲链表头为当前节点的next索引
        free_list_head = new_node->next;
        // 清空节点原有数据
        new_node->data = 0;
        new_node->next = 0;
    } else {
        // 检查内存池剩余空间是否足够分配一个节点
        if ((node_count + 1) * NODE_SIZE > MEMORY_SIZE) {
            return NULL; // 内存不足
        }
        node_count++;
        new_node = get_node_by_index(node_count);
        // 初始化data和next为节点计数，满足从1递增的要求
        new_node->data = node_count;
        new_node->next = node_count + 1;
    }

    return new_node;
}

// 内存释放函数：将节点加入空闲链表，实现内存复用
void myfree(void* ptr) {
    if (ptr == NULL) {
        return;
    }

    // 计算当前节点的索引
    int node_index = ((char*)ptr - memory_pool) / NODE_SIZE + 1;
    Node* free_node = (Node*)ptr;

    // 将节点插入空闲链表头部
    free_node->next = free_list_head;
    free_list_head = node_index;
}

// ------------------------------ 业务链表操作示例 ------------------------------
typedef struct {
    int head_index; // 业务链表的头节点索引（0表示空链表）
} LinkedList;

void initLinkedList(LinkedList* list) {
    list->head_index = 0;
}

// 创建节点（自动分配内存）
int createNode(int data) {
    Node* new_node = (Node*)mymalloc();
    if (new_node == NULL) {
        return 0; // 分配失败
    }
    new_node->data = data; // 覆盖初始递增数值，业务数据优先
    new_node->next = 0;
    // 返回节点索引
    return ((char*)new_node - memory_pool) / NODE_SIZE + 1;
}

// 追加节点到业务链表
void appendNode(LinkedList* list, int data) {
    int new_node_idx = createNode(data);
    if (new_node_idx == 0) {
        printf("内存分配失败\n");
        return;
    }

    if (list->head_index == 0) {
        list->head_index = new_node_idx;
        return;
    }

    // 遍历到链表末尾
    Node* current = get_node_by_index(list->head_index);
    int current_idx = list->head_index;
    while (current->next != 0) {
        current_idx = current->next;
        current = get_node_by_index(current_idx);
    }
    // 更新末尾节点的next为新节点索引
    current->next = new_node_idx;
}

// 删除业务链表中指定data的节点
void deleteNode(LinkedList* list, int data) {
    if (list->head_index == 0) {
        printf("链表为空\n");
        return;
    }

    int current_idx = list->head_index;
    int prev_idx = 0;
    Node* current = get_node_by_index(current_idx);

    while (current != NULL && current->data != data) {
        prev_idx = current_idx;
        current_idx = current->next;
        current = get_node_by_index(current_idx);
    }

    if (current == NULL) {
        printf("未找到数据\n");
        return;
    }

    // 调整业务链表指针
    if (prev_idx == 0) {
        list->head_index = current->next;
    } else {
        Node* prev = get_node_by_index(prev_idx);
        prev->next = current->next;
    }

    // 释放节点到空闲链表
    myfree(current);
}

// 打印业务链表
void printList(LinkedList* list) {
    int current_idx = list->head_index;
    Node* current = get_node_by_index(current_idx);
    while (current != NULL) {
        printf("%d ", current->data);
        current_idx = current->next;
        current = get_node_by_index(current_idx);
    }
    printf("\n");
}

// 打印内存池前N个节点的内存内容（用于验证数值递增）
void printMemoryWindow(int count) {
    printf("\n内存窗口内容（data | next）：\n");
    for (int i = 1; i <= count && i <= node_count; i++) {
        Node* node = get_node_by_index(i);
        printf("%d: %08X %08X\n", i, node->data, node->next);
    }
}

int main() {
    LinkedList linkedList;
    int choice, data;

    initLinkedList(&linkedList);

    do {
        printf("\n\n1. 添加节点\n");
        printf("2. 删除节点\n");
        printf("3. 打印链表\n");
        printf("4. 查看内存窗口\n");
        printf("0. 退出\n");
        printf("请输入选择：");
        scanf("%d", &choice);

        switch (choice) {
        case 1:
            printf("输入节点数据：");
            scanf("%d", &data);
            appendNode(&linkedList, data);
            printf("当前链表：");
            printList(&linkedList);
            break;
        case 2:
            printf("输入要删除的数据：");
            scanf("%d", &data);
            deleteNode(&linkedList, data);
            printf("当前链表：");
            printList(&linkedList);
            break;
        case 3:
            printf("当前链表：");
            printList(&linkedList);
            break;
        case 4:
            printf("输入要查看的节点数量：");
            scanf("%d", &data);
            printMemoryWindow(data);
            break;
        case 0:
            printf("退出程序\n");
            break;
        default:
            printf("无效选择，请重新输入\n");
            break;
        }

    } while (choice != 0);

    return 0;
}

关键细节说明 #

1. 内存池与节点索引：用char数组保证字节级对齐，通过索引计算节点地址，避免指针存储的地址值不连续的问题，确保内存中next成员的数值从1开始递增。
2. 空闲链表复用：释放节点时直接将其加入空闲链表头部，下次分配优先复用，完全符合“不真正释放内存，只复用”的要求。
3. 数值递增保证：初始分配节点时，data和next默认设为节点的计数（从1开始），即使业务修改data，next在链表逻辑中仍保持连续递增的索引值，满足内存窗口的查看需求。
4. 无malloc依赖：所有内存操作均在预分配的1MB数组内完成，完全不调用标准库的malloc/free函数。

内容的提问来源于stack exchange，提问作者yejinchoe24