内存的连续分配与回收算法

说明：
部分代码参考《数据结构》书。
1、采用空闲分区链链接空闲分区，用循环首次适应算法分配内存。

2、假定内存块的大小、地址以“字”为单位计。空闲区、作业区边界采用标识。
“字”的数据结构如下：
leftLink
tag
size
rightLink
空闲空间
upLink
tag

3、分配内存时，将符合要求的空闲区的高地址部分分配给作业，以减少修改指针的操作。

4、源程序：
[cpp]
// 空闲分区链，边界标识法
// 循环首次适应算法

#define _CRT_SECURE_NO_WARNINGS
#define NDEBUG
#include <iostream>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cassert>
using namespace std;

const int MIN_REMAIN = 3;      // 不保留<=MIN_REMAIN的剩余量
const int MEMORY_SIZE = 128;    // 内存空间大小（以字计）

enum State{FREE, ALLOC};        // 块标志：空闲FREE，占用ALLOC

struct Word {
    union {
        Word *leftLink;         // 头部：指向前驱结点
        Word *upLink;           // 尾部：指向本结点头部
    };
    State tag;                  // 头部、尾部：都设块标志
    unsigned int size;          // 头部：块大小
    Word *rightLink;            // 头部：指向后继结点

    // 默认构造函数
    Word()
        :leftLink(NULL),        // 共用体只初始化一个成员即可
        tag(FREE),
        size(0),
        rightLink(NULL){}
}memory[MEMORY_SIZE];           // 假设内存总量为MEMORY_SIZE个字

struct Job {
    string name;
    unsigned int size;
};

// 返回front所指向结点的尾部的地址。
inline Word * FootLoc(Word *front) // inline?
{
    return front + front->size - 1;
}

// 初始只有一块空闲区，初始化它的首字和尾部，pav指向首字。
// 建立双向循环链表，不带头结点。
void Initiate(Word *&pav)
{
    pav = memory;   // 表中不设表头结点，表头指针pav可以指向表中任一结点

    // 头部
    pav->leftLink = memory;
    pav->rightLink = memory;
    pav->size = MEMORY_SIZE;
    pav->tag = FREE;

    // 尾部
    FootLoc(pav)->upLink = memory;
    FootLoc(pav)->tag = FREE;
}

// 若有不小于n的空闲块，则分配相应的存储块，并返回其首地址；
// 否则返回NULL。
// 若分配后可利用空间表不空，则pav指向表中刚分配过的结点的后继结点。
// n应>=3，包括头尾两个字，而实际分配时忽略不计？
Word * AllocBoundTag (Word *&pav, unsigned int n)
{
    if (n <= 2) {
        cout << "n<=2,不能分配空间！" << endl;
        return NULL;
    }
    Word *p = NULL;
    for (p = pav;
        NULL != p && p->size < n && p->rightLink != pav;
        p = p->rightLink);           // 查找不小于n的空闲块
    if (NULL == p || p->size < n)
    {
        cout << "内存可用空间不够，请先释放内存。" << endl;
        return NULL;                // 找不到，返回空指针
    }

    // p指向找到的空闲块
    Word *f = FootLoc(p);           // 指向底部
    pav = p->rightLink;              // “循环”：pav指向*p结点的后继结点
    if (p->size - n <= MIN_REMAIN) { // 整块分配，不保留<=MIN_REMAIN的剩余量
        if (pav == p) {
            pav = NULL;             // 可利用空间表变为空表
        }
        else {                      // 在表中删除分配的结点
            pav->leftLink = p->leftLink;
            p->leftLink->rightLink = pav;
        }
        p->tag = ALLOC;
        f->tag = ALLOC;              // 修改分配结点的头部和底部标志
    }
    else {                          // 分配该块的后n个字使剩余块头部：leftLink, tag, rightLink不变
        f->tag = ALLOC;              // 分配块尾部：tag
        //f->upLink = FootLoc(p) + 1;    // 分配块尾部：upLink
        p->size -= n;               // 剩余块头部：size
        // 剩余块头部：leftLink, tag, rightLink不变
        f = FootLoc(p);             // f指向剩余块尾部
        f->tag = FREE;               // 剩余块尾部：tag
    &n

补充：软件开发 , C++ ,