C语言编程实现空闲表法，位示图法连续分配，成组链接法代码

以下是C语言实现三种分配方式的代码：

1. 空闲表法

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

#define MAXSIZE 1024 // 空间总大小
#define MINISIZE 16 // 最小分配单位

typedef struct node {
    int addr; // 起始地址
    int size; // 大小
    struct node *next; // 指向下一个节点
} Node;

Node *freeList = NULL; // 空闲表头指针

// 初始化空闲表
void initFreeList() {
    freeList = (Node*) malloc(sizeof(Node));
    freeList->addr = 0;
    freeList->size = MAXSIZE;
    freeList->next = NULL;
}

// 分配
int allocate(int size) {
    Node *p = freeList, *prev = freeList;
    while (p != NULL) {
        if (p->size >= size) { // 找到合适的空闲块
            if (p->size - size >= MINISIZE) { // 剩余空间足够大，可以继续分割
                Node *newNode = (Node*) malloc(sizeof(Node));
                newNode->addr = p->addr + size;
                newNode->size = p->size - size;
                newNode->next = p->next;
                p->next = newNode;
                p->size = size;
            }
            if (p == freeList) { // 分配的是第一个节点
                freeList = p->next;
            } else {
                prev->next = p->next;
            }
            free(p);
            return p->addr;
        }
        prev = p;
        p = p->next;
    }
    printf("No enough space.\n");
    return -1;
}

// 释放
void deallocate(int addr, int size) {
    Node *p = freeList, *prev = freeList;
    while (p != NULL && p->addr < addr) { // 找到释放位置前面的节点
        prev = p;
        p = p->next;
    }
    if (p == NULL) { // 释放位置在空闲链表末尾
        Node *newNode = (Node*) malloc(sizeof(Node));
        newNode->addr = addr;
        newNode->size = size;
        newNode->next = NULL;
        prev->next = newNode;
    } else {
        if (prev == p) { // 释放位置在空闲链表开头
            freeList = (Node*) malloc(sizeof(Node));
            freeList->addr = addr;
            freeList->size = size;
            freeList->next = p;
        } else { // 释放位置在空闲链表中
            Node *newNode = (Node*) malloc(sizeof(Node));
            newNode->addr = addr;
            newNode->size = size;
            newNode->next = p;
            prev->next = newNode;
        }
        // 合并相邻的空闲块
        if (prev != freeList && prev->addr + prev->size == addr) {
            prev->size += size;
            if (p != NULL && addr + size == p->addr) {
                prev->size += p->size;
                prev->next = p->next;
                free(p);
            }
        } else if (p != NULL && addr + size == p->addr) {
            p->addr = addr;
            p->size += size;
        }
    }
}

// 打印空闲表
void printFreeList() {
    printf("Free List:\n");
    Node *p = freeList;
    while (p != NULL) {
        printf("Address: %d, Size: %d\n", p->addr, p->size);
        p = p->next;
    }
}

int main() {
    initFreeList();
    int addr1 = allocate(256);
    int addr2 = allocate(512);
    int addr3 = allocate(128);
    int addr4 = allocate(64);
    printFreeList();
    deallocate(addr2, 512);
    printFreeList();
    deallocate(addr3, 128);
    printFreeList();
    deallocate(addr1, 256);
    printFreeList();
    deallocate(addr4, 64);
    printFreeList();
    return 0;
}

2. 位示图法

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

#define MAXSIZE 1024 // 空间总大小
#define MINISIZE 16 // 最小分配单位
#define INTSIZE sizeof(int) // int类型的大小

int *bitmap = NULL; // 位示图指针
int bitCount = 0; // 位示图的位数

// 初始化位示图
void initBitmap() {
    bitCount = MAXSIZE / MINISIZE;
    bitmap = (int*) malloc(bitCount * INTSIZE);
    for (int i = 0; i < bitCount; i++) {
        bitmap[i] = 0;
    }
}

// 分配
int allocate(int size) {
    int index = -1;
    int count = 0;
    for (int i = 0; i < bitCount; i++) {
        if (bitmap[i] == 0) { // 找到一个未被占用的位
            count++;
            if (count == size / MINISIZE || count * MINISIZE == size) { // 找到连续的若干个未被占用的位
                index = i - count + 1;
                break;
            }
        } else {
            count = 0;
        }
    }
    if (index == -1) {
        printf("No enough space.\n");
        return -1;
    }
    for (int i = index; i < index + size / MINISIZE || i == index && size % MINISIZE != 0; i++) {
        bitmap[i] = 1;
    }
    return index * MINISIZE;
}

// 释放
void deallocate(int addr, int size) {
    int index = addr / MINISIZE;
    for (int i = index; i < index + size / MINISIZE || i == index && size % MINISIZE != 0; i++) {
        bitmap[i] = 0;
    }
}

// 打印位示图
void printBitmap() {
    printf("Bitmap:\n");
    for (int i = 0; i < bitCount; i++) {
        printf("%d ", bitmap[i]);
    }
    printf("\n");
}

int main() {
    initBitmap();
    int addr1 = allocate(256);
    int addr2 = allocate(512);
    int addr3 = allocate(128);
    int addr4 = allocate(64);
    printBitmap();
    deallocate(addr2, 512);
    printBitmap();
    deallocate(addr3, 128);
    printBitmap();
    deallocate(addr1, 256);
    printBitmap();
    deallocate(addr4, 64);
    printBitmap();
    return 0;
}

3. 成组链接法

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

#define MAXSIZE 1024 // 空间总大小
#define MINISIZE 16 // 最小分配单位
#define GROUPSIZE 4 // 成组链接的组数

typedef struct node {
    int addr; // 起始地址
    int size; // 大小
    int next; // 指向下一个节点，-1表示没有下一个节点
} Node;

Node *groupList = NULL; // 成组链表头指针
int *bitmap = NULL; // 位示图指针
int bitCount = 0; // 位示图的位数

// 初始化成组链表和位示图
void initGroupList() {
    groupList = (Node*) malloc(GROUPSIZE * sizeof(Node));
    for (int i = 0; i < GROUPSIZE; i++) {
        groupList[i].addr = i * MAXSIZE / GROUPSIZE;
        groupList[i].size = MAXSIZE / GROUPSIZE;
        groupList[i].next = -1;
    }
    bitCount = groupList[0].size / MINISIZE * GROUPSIZE;
    bitmap = (int*) malloc(bitCount * sizeof(int));
    for (int i = 0; i < bitCount; i++) {
        bitmap[i] = 0;
    }
}

// 分配
int allocate(int size) {
    int count = 0;
    int index = -1;
    for (int i = 0; i < GROUPSIZE && index == -1; i++) {
        int curr = i;
        while (curr != -1) {
            int j = 0;
            for (; j < groupList[curr].size / MINISIZE; j++) {
                if (bitmap[i * groupList[curr].size / MINISIZE + j] == 0) {
                    count++;
                    if (count == size / MINISIZE || count * MINISIZE == size) {
                        index = i * groupList[curr].size / MINISIZE + j - count + 1;
                        break;
                    }
                } else {
                    count = 0;
                }
            }
            curr = groupList[curr].next;
        }
    }
    if (index == -1) {
        printf("No enough space.\n");
        return -1;
    }
    int curr = index / (groupList[0].size / MINISIZE);
    int offset = index % (groupList[0].size / MINISIZE);
    for (int i = curr * groupList[0].size / MINISIZE + offset; i < curr * groupList[0].size / MINISIZE + offset + size / MINISIZE || i == curr * groupList[0].size / MINISIZE + offset && size % MINISIZE != 0; i++) {
        bitmap[i] = 1;
    }
    return index * MINISIZE;
}

// 释放
void deallocate(int addr, int size) {
    int curr = addr / (groupList[0].size / MINISIZE);
    int offset = addr % (groupList[0].size / MINISIZE);
    for (int i = curr * groupList[0].size / MINISIZE + offset; i < curr * groupList[0].size / MINISIZE + offset + size / MINISIZE || i == curr * groupList[0].size / MINISIZE + offset && size % MINISIZE != 0; i++) {
        bitmap[i] = 0;
    }
}

// 打印成组链表和位示图
void printGroupList() {
    printf("Group List:\n");
    for (int i = 0; i < GROUPSIZE; i++) {
        printf("Group %d:\n", i);
        int curr = i;
        while (curr != -1) {
            printf("Address: %d, Size: %d, Next: %d\n", groupList[curr].addr, groupList[curr].size, groupList[curr].next);
            curr = groupList[curr].next;
        }
    }
    printf("Bitmap:\n");
    for (int i = 0; i < bitCount; i++) {
        printf("%d ", bitmap[i]);
    }
    printf("\n");
}

int main() {
    initGroupList();
    int addr1 = allocate(256);
    int addr2 = allocate(512);
    int addr3 = allocate(128);
    int addr4 = allocate(64);
    printGroupList();
    deallocate(addr2, 512);
    printGroupList();
    deallocate(addr3, 128);
    printGroupList();
    deallocate(addr1, 256);
    printGroupList();
    deallocate(addr4, 64);
    printGroupList();
    return 0;
}