实现基于最佳适应算法和最坏适应算法的内存分配与回收

基于最佳适应算法和最坏适应算法的内存分配与回收可以通过以下步骤实现：

1. 首先，需要定义一个数据结构来表示内存块，包括内存块的起始地址、大小和状态（已分配或未分配）等信息。

2. 然后，需要定义一个空闲分区链表来管理空闲内存块。链表中的每个节点表示一个空闲内存块，包括内存块的起始地址、大小和指向下一个空闲内存块的指针等信息。

3. 对于最佳适应算法，当需要分配一个大小为n的内存块时，遍历空闲分区链表，找到大小大于等于n且最小的空闲内存块，将其分配给请求方，并将剩余的空闲内存块插入到空闲分区链表中。

4. 对于最坏适应算法，当需要分配一个大小为n的内存块时，遍历空闲分区链表，找到大小大于等于n且最大的空闲内存块，将其分配给请求方，并将剩余的空闲内存块插入到空闲分区链表中。

5. 当需要回收一个已分配的内存块时，将其标记为未分配状态，并将其与相邻的未分配内存块合并成一个更大的空闲内存块，并更新空闲分区链表。

以下是基于最佳适应算法和最坏适应算法的内存分配与回收的Python代码示例：

# 定义内存块结构体
class MemoryBlock:
    def __init__(self, start_addr, size, is_allocated):
        self.start_addr = start_addr  # 起始地址
        self.size = size  # 大小
        self.is_allocated = is_allocated  # 是否已分配

# 定义空闲分区链表节点
class FreeBlock:
    def __init__(self, start_addr, size, next_block=None):
        self.start_addr = start_addr  # 起始地址
        self.size = size  # 大小
        self.next_block = next_block  # 指向下一个空闲分区

# 定义空闲分区链表
class FreeList:
    def __init__(self):
        self.head = FreeBlock(0, 0)  # 头节点

    # 插入一个空闲分区
    def insert(self, block):
        prev = self.head
        curr = self.head.next_block
        while curr is not None and curr.start_addr < block.start_addr:
            prev = curr
            curr = curr.next_block
        block.next_block = curr
        prev.next_block = block

    # 删除一个空闲分区
    def remove(self, block):
        prev = self.head
        curr = self.head.next_block
        while curr is not None and curr.start_addr != block.start_addr:
            prev = curr
            curr = curr.next_block
        prev.next_block = curr.next_block

    # 查找一个大小大于等于n的空闲分区
    def find_best_fit(self, n):
        best_block = None
        prev = self.head
        curr = self.head.next_block
        while curr is not None:
            if not curr.is_allocated and curr.size >= n:
                if best_block is None or curr.size < best_block.size:
                    best_block = curr
            prev = curr
            curr = curr.next_block
        return best_block

    # 查找一个大小大于等于n的空闲分区
    def find_worst_fit(self, n):
        worst_block = None
        prev = self.head
        curr = self.head.next_block
        while curr is not None:
            if not curr.is_allocated and curr.size >= n:
                if worst_block is None or curr.size > worst_block.size:
                    worst_block = curr
            prev = curr
            curr = curr.next_block
        return worst_block

# 初始化空闲分区链表
free_list = FreeList()
free_list.insert(FreeBlock(0, 1024))

# 分配一个大小为256的内存块（最佳适应算法）
block = free_list.find_best_fit(256)
if block is not None:
    block.is_allocated = True
    if block.size > 256:
        free_list.insert(FreeBlock(block.start_addr + 256, block.size - 256))
    print("Allocated block at address", block.start_addr)
else:
    print("Failed to allocate block")

# 分配一个大小为512的内存块（最坏适应算法）
block = free_list.find_worst_fit(512)
if block is not None:
    block.is_allocated = True
    if block.size > 512:
        free_list.insert(FreeBlock(block.start_addr + 512, block.size - 512))
    print("Allocated block at address", block.start_addr)
else:
    print("Failed to allocate block")

# 回收第一个内存块
block = MemoryBlock(0, 256, True)
free_list.remove(FreeBlock(block.start_addr, block.size))
block.is_allocated = False
free_list.insert(FreeBlock(block.start_addr, block.size))

# 回收第二个内存块
block = MemoryBlock(512, 512, True)
free_list.remove(FreeBlock(block.start_addr, block.size))
block.is_allocated = False
free_list.insert(FreeBlock(block.start_addr, block.size))

# 显示空闲分区链表
curr = free_list.head.next_block
while curr is not None:
    print("Free block at address", curr.start_addr, "size", curr.size)
    curr = curr.next_block