C++数组实现Worst Fit算法新增更大内存数组的优先分配逻辑

需求梳理 #

• 现有基于int memory[256]实现的Worst Fit（最坏适配）内存管理算法，已支持内存映射展示、指定内存段删除功能
• 新增int memory2[456]内存数组，要求符合最坏适配规则：优先将数据分配到最大空闲块更大的数组中，当当前数组最大空闲块小于另一数组时自动切换分配目标
• 限制规则：仅可使用数组实现，禁止使用节点、vector、链表等其他数据结构

核心调整思路 #

1. 将原有硬编码256数组长度的工具函数改造为通用版本，新增数组长度入参，可同时适配256和456长度的内存数组
2. 新增最大空闲块查询函数，分配前先对比两个数组的最大空闲块大小，选择块更大的数组执行分配
3. 分配返回值新增数组标识位，删除时可自动识别对应操作的内存数组，无需用户额外输入数组信息

修改后完整代码 #

#include <iostream>
#include <cmath>
#include <cstdlib>

using namespace std;

// 查询指定内存数组的最大空闲块大小
int get_max_free_block(int memory[], int mem_size) {
    int max_block = 0;
    for (int i = 0; i < mem_size; i++) {
        if (memory[i] < 0) {
            int current_block = abs(memory[i]);
            if (current_block > max_block) {
                max_block = current_block;
            }
            i += current_block - 1;
        }
    }
    return max_block;
}

// 通用内存分配函数，新增mem_size参数指定数组长度
int PutInMemory(int memory[], int mem_size, int size) {
    if (size < 1) {
        cout << "Error!" << endl;
        return -1;
    }
    // 最坏适配：先找最大的满足需求的空闲块
    int max_block = 0;
    int j = -1;
    for (int i = 0; i < mem_size; i++) {
        if (memory[i] < 0 && abs(memory[i]) >= size) {
            int current_block = abs(memory[i]);
            if (current_block > max_block) {
                max_block = current_block;
                j = i;
            }
            i += current_block - 1;
        }
    }
    if (j == -1) {
        cout << "Out of Memory" << endl;
        return -1;
    }
    if (j + size <= mem_size) {
        memory[j] = size;
        for (int i = j + 1; i < j + size; i++) {
            memory[i] = 0;
        }
        int i = j + size;
        int count = 0;
        while (memory[i] <= -1 && i < mem_size) {
            count++;
            i++;
        }
        if (count != 0) {
            memory[i - 1] = -count;
            memory[j + size] = -count;
        }
        return j;
    } else {
        cout << "Out of memory" << endl;
        return -1;
    }
}

// 通用内存段删除函数，新增mem_size参数指定数组长度
void DelSeg(int memory[], int mem_size, int n) {
    if (n < 0 || n >= mem_size || memory[n] <= 0) {
        cout << "Invalid address!" << endl;
        return;
    }
    int count = memory[n];
    int prev = 0;
    int next = count - 1;
    int i = n + 1;
    int pos = n;
    if (n != 0 && memory[n - 1] < -1) {
        prev = -memory[n - 1];
        count += prev;
        pos = n - prev;
        i = pos + 1;
    }
    while (true) {
        for (; i < pos + count - 1; i++) {
            memory[i] = -1;
        }
        if (i + 1 < mem_size && memory[i + 1] < -1) {
            int add_block = -memory[i + 1];
            count += add_block;
            next += add_block;
        } else {
            break;
        }
    }
    memory[pos] = 0 - count;
    memory[pos + count - 1] = 0 - count;
}

// 通用内存信息查询函数，新增mem_size和数组标识参数
void checkMemory(int memory[], int mem_size, const char* mem_name) {
    cout << "===== " << mem_name << " 内存信息 =====" << endl;
    int countFreeSeg = 0;
    int countFullSeg = 0;
    int countFullMem = 0;
    int countFreeMem = 0;
    
    for (int i = 0; i < mem_size; i++) {
        if (memory[i] < 0) {
            cout << "空闲块起始地址:" << i << ", 大小 = " << abs(memory[i]) << endl;
            int count = abs(memory[i]);
            countFreeSeg++;
            countFreeMem += count;
            i += count - 1;
        }
    }
    cout << "空闲块总数 = " << countFreeSeg << endl;
    cout << "空闲内存总大小 = " << countFreeMem << endl << endl;
    
    for (int i = 0; i < mem_size; i++) {
        if (memory[i] > 0) {
            cout << "已占用块起始地址: " << i << ", 大小 = " << memory[i] << endl;
            countFullMem += memory[i];
            i += memory[i] - 1;
            countFullSeg++;
        }
    }
    cout << "已占用块总数 = " << countFullSeg << endl;
    cout << "已占用内存总大小 = " << countFullMem << endl << endl;
}

// 通用内存打印函数，新增mem_size参数
void print(int memory[], int mem_size) {
    for (int i = 0; i < mem_size; i++) {
        cout << memory[i] << " ";
    }
    cout << endl;
}

int main() {
    const int MEM1_SIZE = 256;
    const int MEM2_SIZE = 456;
    const int MEM2_OFFSET = 1000; // memory2返回地址偏移量，用于区分两个数组
    
    int memory[MEM1_SIZE];
    memory[0] = -MEM1_SIZE;
    for (int i = 1; i < MEM1_SIZE; i++) {
        memory[i] = -1;
    }
    
    int memory2[MEM2_SIZE];
    memory2[0] = -MEM2_SIZE;
    for (int i = 1; i < MEM2_SIZE; i++) {
        memory2[i] = -1;
    }
    
    while (true) {
        system("cls");
        cout << "1.分配内存 \n2.释放内存段\n3.查询内存信息\n4.退出" << endl;
        int choice;
        cin >> choice;
        int m = 0;
        
        switch (choice) {
            case 1:
                system("cls");
                cout << "输入要分配的内存大小:" << endl;
                cin >> m;
                // 先查两个数组的最大空闲块
                int max1, max2;
                max1 = get_max_free_block(memory, MEM1_SIZE);
                max2 = get_max_free_block(memory2, MEM2_SIZE);
                int res;
                if (max2 >= max1 && max2 >= m) {
                    // 优先分配到最大空闲块更大的数组，相等优先分配更大的memory2
                    res = PutInMemory(memory2, MEM2_SIZE, m);
                    if (res != -1) {
                        res += MEM2_OFFSET;
                        cout << "分配成功，地址（memory2）: " << res << " （实际数组内偏移：" << res - MEM2_OFFSET << "）" << endl;
                    }
                } else if (max1 >= m) {
                    res = PutInMemory(memory, MEM1_SIZE, m);
                    if (res != -1) {
                        cout << "分配成功，地址（memory）: " << res << endl;
                    }
                } else {
                    cout << "两个数组均无足够内存" << endl;
                }
                break;
            case 2:
                system("cls");
                cout << "输入要释放的内存段起始地址:" << endl;
                cin >> m;
                if (m >= MEM2_OFFSET) {
                    // 操作memory2
                    DelSeg(memory2, MEM2_SIZE, m - MEM2_OFFSET);
                    cout << "memory2 地址 " << m - MEM2_OFFSET << " 对应的段已释放" << endl;
                } else {
                    // 操作memory
                    DelSeg(memory, MEM1_SIZE, m);
                    cout << "memory 地址 " << m << " 对应的段已释放" << endl;
                }
                break;
            case 3:
                checkMemory(memory, MEM1_SIZE, "memory[256]");
                print(memory, MEM1_SIZE);
                cout << endl;
                checkMemory(memory2, MEM2_SIZE, "memory2[456]");
                print(memory2, MEM2_SIZE);
                break;
            case 4:
                system("cls");
                exit(0);
                break;
            default:
                cout << "输入错误" << endl;
                break;
        }
        system("pause");
    }
    return 0;
}

功能验证说明 #

• 分配逻辑会自动对比两个数组的最大空闲块，优先分配到块更大的数组，符合最坏适配规则
• 释放时只需输入分配时返回的地址，代码会自动识别对应的内存数组执行释放操作
• 内存信息查询会同时输出两个数组的空闲、已占用情况，方便验证分配逻辑

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