C语言位示图实现磁盘空间管理：详解连续与离散分配算法

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

#define MAX_ROW 10 // 位示图行数 
#define MAX_COL 10 // 位示图列数 

int bitmap[MAX_ROW][MAX_COL]; // 位示图数组，模拟磁盘块的使用情况，0表示空闲，1表示已占用 
int file_blocks = 0; // 文件所占块数 

// 初始化位示图，将所有块设置为'空闲'状态
void init_bitmap() {
    int i, j;
    for (i = 0; i < MAX_ROW; i++) {
        for (j = 0; j < MAX_COL; j++) {
            bitmap[i][j] = 0; // 初始状态所有块都为空闲
        }
    }
}

// 显示位示图，直观地展示磁盘块的使用情况
void show_bitmap() {
    int i, j;
    printf('当前位示图：\n');
    for (i = 0; i < MAX_ROW; i++) {
        for (j = 0; j < MAX_COL; j++) {
            printf('%d ', bitmap[i][j]);
        }
        printf('\n');
    }
}

// 连续分配算法，尝试在位示图中找到足够大小的连续空闲块
int allocate_continuous(int file_size, int block_size) {
    int i, j, k, flag = 0;
    file_blocks = (file_size + block_size - 1) / block_size; // 计算文件所占块数，向上取整
    for (i = 0; i < MAX_ROW; i++) {
        for (j = 0; j < MAX_COL; j++) {
            if (bitmap[i][j] == 0) { // 遇到空闲块
                flag++; // 连续空闲块计数加一
                if (flag == file_blocks) { // 找到足够的连续空闲块
                    for (k = j - file_blocks + 1; k <= j; k++) { 
                        bitmap[i][k] = 1; // 将这些块标记为'已占用'
                    }
                    return i * MAX_COL + j - file_blocks + 1; // 返回分配的第一个块号
                }
            } else { // 遇到已占用块，连续计数中断
                flag = 0; 
            }
        }
        flag = 0; // 换行时，连续计数也要中断
    }
    return -1; // 没有找到足够的连续空闲块
}

// 离散分配算法，找到足够数量的空闲块，不要求连续
int allocate_discrete(int file_size, int block_size) {
    int i, j, count = 0; // 已分配块数计数
    file_blocks = (file_size + block_size - 1) / block_size; // 计算文件所占块数
    for (i = 0; i < MAX_ROW; i++) {
        for (j = 0; j < MAX_COL; j++) {
            if (bitmap[i][j] == 0 && count < file_blocks) { // 找到空闲块且分配未完成
                bitmap[i][j] = 1; // 标记为'已占用'
                count++; // 已分配块数加一
            }
            if (count == file_blocks) { // 分配完成
                return i * MAX_COL + j - file_blocks + 1; // 返回分配的第一个块号
            }
        }
    }
    return -1; // 没有足够的离散空闲块
}

// 分配磁盘块，根据用户选择调用不同的分配算法
int allocate_blocks() {
    int file_size, block_size;
    printf('请输入文件大小：');
    scanf('%d', &file_size);
    printf('请输入块大小：');
    scanf('%d', &block_size);
    printf('请选择分配方式（1.连续分配 2.离散分配）：');
    int choice;
    scanf('%d', &choice);
    int block_num;
    if (choice == 1) {
        block_num = allocate_continuous(file_size, block_size); // 调用连续分配算法
    } else if (choice == 2) {
        block_num = allocate_discrete(file_size, block_size); // 调用离散分配算法
    } else {
        printf('输入不合法！\n');
        return -1;
    }
    if (block_num == -1) {
        printf('磁盘空间不足！\n');
        return -1;
    }
    printf('文件分配成功，分配的第一个块号为：%d\n', block_num);
    return block_num;
}

// 回收磁盘块，将指定的块标记为空闲
void free_blocks() {
    printf('请输入要回收的块号：');
    int block_num;
    scanf('%d', &block_num);
    if (block_num < 0 || block_num >= MAX_ROW * MAX_COL) { // 判断块号是否合法
        printf('输入不合法！\n');
        return;
    }
    int row = block_num / MAX_COL;
    int col = block_num % MAX_COL;
    if (bitmap[row][col] == 0) { // 判断该块是否已经被回收
        printf('该块未被分配！\n');
        return;
    }
    bitmap[row][col] = 0; // 修改位示图，标记为空闲
    printf('块号 %d 回收成功！\n', block_num);
}

int main() {
    init_bitmap(); // 初始化位示图
    int choice;
    while (1) { // 循环提供文件分配和回收功能
        printf('请选择操作（1.分配磁盘块 2.回收磁盘块 3.显示位示图 4.退出程序）：');
        scanf('%d', &choice);
        switch (choice) {
            case 1:
                allocate_blocks(); // 调用分配磁盘块函数
                break;
            case 2:
                free_blocks(); // 调用回收磁盘块函数
                break;
            case 3:
                show_bitmap(); // 显示当前位示图
                break;
            case 4:
                exit(0); // 退出程序
            default:
                printf('输入不合法！\n');
                break;
        }
    }
    return 0;
}