内存的连续分配与回收算法 - c++编程基础

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

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

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

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

#define _CRT_SECURE_NO_WARNINGS
#define NDEBUG
#include
#include
#include
#include
#include
#include
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
f->upLink = p; // 剩余块尾部：upLink
p = f + 1; // p指向分配块头部
p->tag = ALLOC; // 分配块头部：tag
p->size = n; // 分配块头部：size
//p->leftLink = NULL; // 分配块头部：leftLink
//p->rightLink = NULL; // 分配块头部：rightLink
}
return p; // 返回分配块首地址
}

// 1、前后相邻区都是作业
void Recycle_AA(Word *&pav, Word *&p)
{
p->tag = FREE; // 回收区头部：tag
// 回收区头部：size 原来就存在
FootLoc(p)->upLink = p; // 回收区尾部：upLink
FootLoc(p)->tag = FREE;

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