最坏适应算法 c语言

最坏适应算法（Worst-Fit Algorithm）是一种内存分配算法，其思想是在所有可用空闲区中，选择最大的空闲区进行分配。该算法的实现思路如下：

1. 初始化分配表，记录内存的总大小和当前可用空闲区的信息。
2. 接收用户申请内存的请求，计算所需内存大小。
3. 遍历可用空闲区列表，找到最大的空闲区，使其能够满足当前申请的内存大小要求。
4. 如果找到了可用的空闲区，则将该区域划分为已分配区和空闲区，记录已分配区的大小和起始地址，并更新空闲区列表。
5. 如果没有找到可用的空闲区，则返回内存分配失败的消息。

以下是一个最坏适应算法的C语言实现示例：

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

#define MAX_SIZE 1000

// 空闲区结构体
typedef struct free_block {
    int size;               // 空闲区大小
    int start_addr;         // 空闲区起始地址
    struct free_block *next;    // 下一个空闲区指针
} FreeBlock;

// 已分配区结构体
typedef struct allocated_block {
    int size;               // 已分配区大小
    int start_addr;         // 已分配区起始地址
    struct allocated_block *next;   // 下一个已分配区指针
} AllocBlock;

// 内存分配表结构体
typedef struct mem_table {
    int mem_size;           // 总内存大小
    FreeBlock *free_list;       // 空闲区列表
    AllocBlock *alloc_list;     // 已分配区列表
} MemTable;

// 初始化内存分配表
void init_mem_table(MemTable *table, int size) {
    table->mem_size = size;
    table->free_list = (FreeBlock *)malloc(sizeof(FreeBlock));
    table->free_list->size = size;
    table->free_list->start_addr = 0;
    table->free_list->next = NULL;
    table->alloc_list = NULL;
}

// 显示内存分配表信息
void show_mem_table(MemTable table) {
    printf("Memory size: %d\n", table.mem_size);
    printf("Free blocks:\n");
    FreeBlock *p = table.free_list;
    while (p != NULL) {
        printf("Size: %d, Address: %d\n", p->size, p->start_addr);
        p = p->next;
    }
    printf("Allocated blocks:\n");
    AllocBlock *q = table.alloc_list;
    while (q != NULL) {
        printf("Size: %d, Address: %d\n", q->size, q->start_addr);
        q = q->next;
    }
}

// 最坏适应算法，申请指定大小的内存
void *wf_malloc(MemTable *table, int size) {
    FreeBlock *p = table->free_list;
    FreeBlock *prev = NULL;
    FreeBlock *max_block = NULL;
    FreeBlock *prev_max_block = NULL;
    int max_size = 0;

    // 遍历空闲区列表，查找最大的空闲区
    while (p != NULL) {
        if (p->size >= size && p->size > max_size) {
            max_block = p;
            prev_max_block = prev;
            max_size = p->size;
        }
        prev = p;
        p = p->next;
    }

    // 如果找到了最大的可用空闲区，则分配内存
    if (max_block != NULL) {
        AllocBlock *new_block = (AllocBlock *)malloc(sizeof(AllocBlock));
        new_block->size = size;
        new_block->start_addr = max_block->start_addr;
        new_block->next = table->alloc_list;
        table->alloc_list = new_block;

        // 更新空闲区列表
        if (max_block->size == size) {
            if (prev_max_block == NULL) {
                table->free_list = max_block->next;
            } else {
                prev_max_block->next = max_block->next;
            }
            free(max_block);
        } else {
            max_block->size -= size;
            max_block->start_addr += size;
        }

        return (void *)(new_block->start_addr);
    } else {
        printf("Memory allocation failed!\n");
        return NULL;
    }
}

// 释放已分配的内存
void wf_free(MemTable *table, void *ptr) {
    AllocBlock *p = table->alloc_list;
    AllocBlock *prev = NULL;

    // 查找待释放的内存块
    while (p != NULL) {
        if ((void *)(p->start_addr) == ptr) {
            break;
        }
        prev = p;
        p = p->next;
    }

    // 如果找到待释放的内存块，则将其加入空闲区列表
    if (p != NULL) {
        FreeBlock *new_block = (FreeBlock *)malloc(sizeof(FreeBlock));
        new_block->size = p->size;
        new_block->start_addr = p->start_addr;

        // 插入到空闲区列表中
        FreeBlock *q = table->free_list;
        FreeBlock *prev_q = NULL;
        while (q != NULL && q->start_addr < new_block->start_addr) {
            prev_q = q;
            q = q->next;
        }
        if (prev_q == NULL) {
            table->free_list = new_block;
        } else {
            prev_q->next = new_block;
        }
        new_block->next = q;

        // 从已分配区列表中删除
        if (prev == NULL) {
            table->alloc_list = p->next;
        } else {
            prev->next = p->next;
        }
        free(p);
    } else {
        printf("Memory free failed!\n");
    }
}

int main() {
    MemTable table;
    init_mem_table(&table, MAX_SIZE);
    show_mem_table(table);

    void *p1 = wf_malloc(&table, 100);
    printf("Allocated memory: %p\n", p1);
    show_mem_table(table);

    void *p2 = wf_malloc(&table, 200);
    printf("Allocated memory: %p\n", p2);
    show_mem_table(table);

    void *p3 = wf_malloc(&table, 300);
    printf("Allocated memory: %p\n", p3);
    show_mem_table(table);

    wf_free(&table, p1);
    printf("Free memory: %p\n", p1);
    show_mem_table(table);

    void *p4 = wf_malloc(&table, 150);
    printf("Allocated memory: %p\n", p4);
    show_mem_table(table);

    wf_free(&table, p2);
    printf("Free memory: %p\n", p2);
    show_mem_table(table);

    void *p5 = wf_malloc(&table, 50);
    printf("Allocated memory: %p\n", p5);
    show_mem_table(table);

    wf_free(&table, p3);
    printf("Free memory: %p\n", p3);
    show_mem_table(table);

    wf_free(&table, p4);
    printf("Free memory: %p\n", p4);
    show_mem_table(table);

    wf_free(&table, p5);
    printf("Free memory: %p\n", p5);
    show_mem_table(table);

    return 0;
}

该示例中，首先定义了空闲区和已分配区的结构体，以及内存分配表的结构体。然后实现了初始化内存分配表、显示内存分配表、最坏适应算法申请内存、释放已分配内存等功能函数。在main函数中，通过不断申请和释放内存的操作，测试了最坏适应算法的实现。