用C++编译实现连续分配，索引分配，链接分配三种外存分配方式

外存分配是指在磁盘等外部存储器上对文件进行分配的方式，常用的外存分配方式有连续分配、索引分配和链接分配三种。下面是用C++编译实现这三种外存分配方式的示例代码：

1. 连续分配

#include <iostream>
#include <fstream>
using namespace std;

const int BLOCK_SIZE = 512; // 每个物理块大小为512字节
const int FILE_SIZE = 1024; // 文件大小为1024字节
const int BLOCK_NUM = FILE_SIZE / BLOCK_SIZE; // 物理块数

// 文件控制块
struct FCB {
    char filename[20]; // 文件名
    int start_block; // 起始盘块号
    int block_num; // 占用盘块数
};

// 空闲盘块表
struct FAT {
    int block_num; // 盘块号
    bool free; // 是否空闲
};

int main() {
    FCB file;
    file.block_num = FILE_SIZE / BLOCK_SIZE;
    FAT fat[BLOCK_NUM];
    char buffer[BLOCK_SIZE] = {'\0'};
    int i, j, k, n;

    // 初始化空闲盘块表
    for (i = 0; i < BLOCK_NUM; i++) {
        fat[i].block_num = i;
        fat[i].free = true;
    }

    // 连续分配
    cout << "请输入文件名：";
    cin >> file.filename;
    for (i = 0; i < BLOCK_NUM; i++) {
        n = 0;
        if (fat[i].free) {
            for (j = i; j < BLOCK_NUM && fat[j].free; j++) {
                n++;
            }
            if (n == file.block_num) {
                file.start_block = i;
                for (k = i; k < i + n; k++) {
                    fat[k].free = false;
                }
                break;
            }
        }
    }
    if (i == BLOCK_NUM) {
        cout << "磁盘空间不足，分配失败！" << endl;
        return 0;
    }

    // 写入数据
    ofstream fout;
    fout.open(file.filename, ios::binary);
    for (i = 0; i < file.block_num; i++) {
        fout.seekp((file.start_block + i) * BLOCK_SIZE);
        fout.write(buffer, BLOCK_SIZE);
    }
    fout.close();

    // 显示空闲盘块表
    cout << "空闲盘块表：" << endl;
    for (i = 0; i < BLOCK_NUM; i++) {
        cout << fat[i].block_num << " " << (fat[i].free ? "空闲" : "占用") << endl;
    }

    return 0;
}

2. 索引分配

#include <iostream>
#include <fstream>
using namespace std;

const int BLOCK_SIZE = 512; // 每个物理块大小为512字节
const int FILE_SIZE = 1024; // 文件大小为1024字节
const int BLOCK_NUM = FILE_SIZE / BLOCK_SIZE; // 物理块数
const int INDEX_BLOCK_NUM = 2; // 索引块数
const int INDEX_SIZE = BLOCK_SIZE / sizeof(int); // 每个索引块可存放的索引数

// 文件控制块
struct FCB {
    char filename[20]; // 文件名
    int start_block; // 起始盘块号
    int block_num; // 占用盘块数
    int index_block[INDEX_BLOCK_NUM]; // 索引块号
};

// 空闲盘块表
struct FAT {
    int block_num; // 盘块号
    bool free; // 是否空闲
};

int main() {
    FCB file;
    file.block_num = FILE_SIZE / BLOCK_SIZE;
    FAT fat[BLOCK_NUM];
    char buffer[BLOCK_SIZE] = {'\0'};
    int i, j, k, n;

    // 初始化空闲盘块表
    for (i = 0; i < BLOCK_NUM; i++) {
        fat[i].block_num = i;
        fat[i].free = true;
    }

    // 索引分配
    cout << "请输入文件名：";
    cin >> file.filename;
    for (i = 0; i < BLOCK_NUM; i++) {
        n = 0;
        if (fat[i].free) {
            for (j = i; j < BLOCK_NUM && fat[j].free; j++) {
                n++;
            }
            if (n >= file.block_num) {
                file.start_block = i;
                for (k = i; k < i + file.block_num; k++) {
                    fat[k].free = false;
                }
                break;
            }
        }
    }
    if (i == BLOCK_NUM) {
        cout << "磁盘空间不足，分配失败！" << endl;
        return 0;
    }
    for (i = 0; i < INDEX_BLOCK_NUM; i++) {
        for (j = 0; j < INDEX_SIZE; j++) {
            if (i * INDEX_SIZE + j < file.block_num) {
                file.index_block[i * INDEX_SIZE + j] = file.start_block + i * INDEX_SIZE + j;
                fat[file.start_block + i].free = false;
            }
            else {
                file.index_block[i * INDEX_SIZE + j] = -1;
            }
        }
    }

    // 写入数据
    ofstream fout;
    fout.open(file.filename, ios::binary);
    for (i = 0; i < INDEX_BLOCK_NUM; i++) {
        fout.seekp(file.index_block[i] * BLOCK_SIZE);
        for (j = 0; j < INDEX_SIZE && i * INDEX_SIZE + j < file.block_num; j++) {
            fout.write(buffer, BLOCK_SIZE);
        }
    }
    fout.close();

    // 显示空闲盘块表
    cout << "空闲盘块表：" << endl;
    for (i = 0; i < BLOCK_NUM; i++) {
        cout << fat[i].block_num << " " << (fat[i].free ? "空闲" : "占用") << endl;
    }

    return 0;
}

3. 链接分配

#include <iostream>
#include <fstream>
using namespace std;

const int BLOCK_SIZE = 512; // 每个物理块大小为512字节
const int FILE_SIZE = 1024; // 文件大小为1024字节
const int BLOCK_NUM = FILE_SIZE / BLOCK_SIZE; // 物理块数

// 文件控制块
struct FCB {
    char filename[20]; // 文件名
    int start_block; // 起始盘块号
    int block_num; // 占用盘块数
    int next_block; // 下一个盘块号
};

// 空闲盘块表
struct FAT {
    int block_num; // 盘块号
    int next_block; // 下一个盘块号
    bool free; // 是否空闲
};

int main() {
    FCB file;
    file.block_num = FILE_SIZE / BLOCK_SIZE;
    FAT fat[BLOCK_NUM];
    char buffer[BLOCK_SIZE] = {'\0'};
    int i, j, k, n;

    // 初始化空闲盘块表
    for (i = 0; i < BLOCK_NUM; i++) {
        fat[i].block_num = i;
        fat[i].next_block = -1;
        fat[i].free = true;
    }

    // 链接分配
    cout << "请输入文件名：";
    cin >> file.filename;
    for (i = 0; i < BLOCK_NUM; i++) {
        if (fat[i].free) {
            file.start_block = i;
            fat[i].free = false;
            fat[i].next_block = -1;
            break;
        }
    }
    if (i == BLOCK_NUM) {
        cout << "磁盘空间不足，分配失败！" << endl;
        return 0;
    }
    for (i = file.start_block + 1; i < file.start_block + file.block_num; i++) {
        for (j = 0; j < BLOCK_NUM; j++) {
            if (fat[j].free) {
                fat[i].free = false;
                fat[i].next_block = j;
                fat[j].free = false;
                fat[j].next_block = -1;
                break;
            }
        }
        if (j == BLOCK_NUM) {
            cout << "磁盘空间不足，分配失败！" << endl;
            return 0;
        }
    }
    file.next_block = -1;

    // 写入数据
    ofstream fout;
    fout.open(file.filename, ios::binary);
    fout.seekp(file.start_block * BLOCK_SIZE);
    fout.write(buffer, BLOCK_SIZE);
    for (i = file.start_block + 1; i < file.start_block + file.block_num; i++) {
        fout.seekp(i * BLOCK_SIZE);
        fout.write(buffer, BLOCK_SIZE);
    }
    fout.close();

    // 显示空闲盘块表
    cout << "空闲盘块表：" << endl;
    for (i = 0; i < BLOCK_NUM; i++) {
        cout << fat[i].block_num << " " << (fat[i].free ? "空闲" : "占用") << " " << fat[i].next_block << endl;
    }

    return 0;
}