說明：
部分代碼參考《數據結構》書。
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
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; // 回收區尾部：tag
if (NULL == pav)
{
pav = p;
p->leftLink = p; // 回收區頭部：leftLink
p->rightLink = p; // 回收區頭部：rightLink
}
else
{
// 將p插到pav之前（雙向鏈表的插入操作）
p->rightLink = pav; // 回收區頭部：rightLink
p->leftLink = pav->leftLink; // 回收區頭部：leftLink
pav->leftLink->rightLink = p; // pav的前驅頭部：rightLink
pav->leftLink = p; // pav的頭部：leftLink
pav = p; // 令剛釋放的結點為下次分配時的最先查詢的結點
}
}
// 2、前空閒，後作業
void Recycle_FA(Word *&p)
{
unsigned int n = p->size; // 釋放塊的大小
Word *s = (p - 1)->upLink; // 左鄰空閒區的頭部地址
s->size += n; // 設置新的空閒塊大小
Word *f = p + n - 1; // 設置新的空閒塊底部
f->upLink = s;
f->tag = FREE;
}
// 3、前作業，後空閒
void Recycle_AF(Word *&p)
{
Word *t = p + p->size; // t指向右鄰空閒區的頭部
FootLoc(t)->upLink = p; // 右鄰空閒區頭部：upLink
p->size += t->size; // 回收區頭部：size
p->tag = FREE; // 回收區頭部：tag
p->leftLink = t->leftLink; // 回收區頭部：leftLink
t->leftLink->rightLink = p; // 原來右鄰區的前驅頭部：rightLink
p->rightLink = t->rightLink;// 回收區頭部：rightLink
t->rightLink->leftLink = p; // 原來右鄰區的後繼頭部：leftLink
}
// 4、前後相鄰區都是空閒區
void Recycle_FF(Word *&p)
{
unsigned int n = p->size; // 回收區大小
Word *s = (p - 1)->upLink; // 指向左鄰塊，即新結點頭部
Word *t = p + p->size; // 指向右鄰塊
s->size += n + t->size; // 設置新結點大小
// 刪除右鄰空閒塊結點（雙向鏈表的刪除操作）
t->leftLink->rightLink = t->rightLink; // s不一定等於t->leftLink
t->rightLink->leftLink = t->leftLink;
FootLoc(t)->upLink = s; // 新結點尾部：upLink指向其頭部
}
// 釋放首地址為p的作業（頭部中含該作業的大小信息）
void Recycle(Word *&pav, Word *p)
{
if (!(memory <= p && p < memory + MEMORY_SIZE))
{
cout << "釋放區首地址越界！" << endl;
return;
}
Word *low = p - 1; // 與其低地址緊鄰的內存區的底部地址
Word *high = p + p->size; // 與其高地址緊鄰的內存區的頭部地址
State lowTag = low->tag;
State highTag = high->tag;
if (low < memory) // 當p是內存的第一塊時
{
lowTag = ALLOC;
}
if (high >= memory + MEMORY_SIZE) // 當p是內存的最後一塊時
{
highTag = ALLOC;
}
// 前後相鄰區都是作業
if (ALLOC == lowTag && ALLOC == highTag)
{
Recycle_AA(pav, p);
}
// 前空閒，後作業
else if (FREE == lowTag && ALLOC == highTag)
{
Recycle_FA(p);
}
// 前作業，後空閒
else if (ALLOC == lowTag && FREE == highTag)
{
Recycle_AF(p);
}
// 前後相鄰區都是空閒區
else if (FREE == lowTag && FREE == highTag)
{
Recycle_FF(p);
}
}
// 輸出內存中各區的信息
void PrintMInfo(map<Word *, string> &jobAddrToName)
{
cout << "\n************************************" << endl;
cout << "起址\t大小\t狀態\t（作業名）" << endl;
for (Word *p = memory; p < memory + MEMORY_SIZE; p += p->size)
{
cout << p - memory << "\t"
<< p->size << "\t"
<< p->tag << "\t"
<< (p->tag == ALLOC ? jobAddrToName[p] : "（空閒）")
<< endl;
}
cout << "************************************\n" << endl;
}
int Flag(const string &option)
{
if (option == "1") return 1;
if (option == "2") return 2;
if (option == "3") return 3;
return 0;
}
int main(int argc, char **argv)
{
freopen("cin.txt", "r", stdin);
map<string, Word *> jobNameToAddr; // 根據作業名得到它的地址
map<Word *, string> jobAddrToName; // 根據作業地址得到它的名稱
Word *pav = NULL; // pav為查詢指針
Initiate(pav);
string option;
do
{
PrintMInfo(jobAddrToName);
cout << "請選擇：1、分配內存 2、回收內存 3、退出" << endl;
cin >> option;
switch (Flag(option))
{
case 1:
{ // 防止error C2374：初始化操作由“case”標簽跳過
cout << "請輸入作業名和作業大小：" << endl;
Job myJob;
cin >> myJob.name >> myJob.size;
Word *addr = AllocBoundTag(pav, myJob.size);
if (addr == NULL) // 分配失敗
{
break;
}
jobNameToAddr[myJob.name] = addr;
jobAddrToName[addr] = myJob.name;
break;
}
case 2:
{
cout << "請輸入要回收的作業名稱：" << endl;
string name;
cin >> name;
Word *addr = jobNameToAddr[name]; // 用戶釋放的內存區的頭部地址為addr
if (NULL == addr)
{
cout << "作業" << name << "不存在，無法釋放！" << endl;
break;
}
Recycle(pav, addr);
int cnt = jobAddrToName.erase(addr);
assert(cnt == 1);
cnt = jobNameToAddr.erase(name);
assert(cnt == 1);
break;
}
case 3:
return 0;
default:
cout << "輸入錯誤！請重新輸入。" << endl;
break;
}
} while (true);
return 0;
}
/* cin.txt
1
J5 96
1
J2 6
1
J4 12
1
J3 4
1
J1 5
1
OS 5
2
J4
2
J5
2
J3
1
J6 20
3
*/
5、運行結果：
[cpp] view plaincopyprint?
************************************
起址 大小 狀態 （作業名）
0 128 0 （空閒）
************************************
請選擇：1、分配內存 2、回收內存 3、退出
請輸入作業名和作業大小：
************************************
起址 大小 狀態 （作業名）
0 32 0 （空閒）
32 96 1 J5
************************************
請選擇：1、分配內存 2、回收內存 3、退出
請輸入作業名和作業大小：
************************************
起址 大小 狀態 （作業名）
0 26 0 （空閒）
26 6 1 J2
32 96 1 J5
************************************
請選擇：1、分配內存 2、回收內存 3、退出
請輸入作業名和作業大小：
************************************
起址 大小 狀態 （作業名）
0 14 0 （空閒）
14 12 1 J4
26 6 1 J2
32 96 1 J5
************************************
請選擇：1、分配內存 2、回收內存 3、退出
請輸入作業名和作業大小：
************************************
起址 大小 狀態 （作業名）
0 10 0 （空閒）
10 4 1 J3
14 12 1 J4
26 6 1 J2
32 96 1 J5
************************************
請選擇：1、分配內存 2、回收內存 3、退出
請輸入作業名和作業大小：
************************************
起址 大小 狀態 （作業名）
0 5 0 （空閒）
5 5 1 J1
10 4 1 J3
14 12 1 J4
26 6 1 J2
32 96 1 J5
************************************
請選擇：1、分配內存 2、回收內存 3、退出
請輸入作業名和作業大小：
************************************
起址 大小 狀態 （作業名）
0 5 1 OS
5 5 1 J1
10 4 1 J3
14 12 1 J4
26 6 1 J2
32 96 1 J5
************************************
請選擇：1、分配內存 2、回收內存 3、退出
請輸入要回收的作業名稱：
************************************
起址 大小 狀態 （作業名）
0 5 1 OS
5 5 1 J1
10 4 1 J3
14 12 0 （空閒）
26 6 1 J2
32 96 1 J5
************************************
請選擇：1、分配內存 2、回收內存 3、退出
請輸入要回收的作業名稱：
************************************
起址 大小 狀態 （作業名）
0 5 1 OS
5 5 1 J1
10 4 1 J3
14 12 0 （空閒）
26 6 1 J2
32 96 0 （空閒）
************************************
請選擇：1、分配內存 2、回收內存 3、退出
請輸入要回收的作業名稱：
************************************
起址 大小 狀態 （作業名）
0 5 1 OS
5 5 1 J1
10 16 0 （空閒）
26 6 1 J2
32 96 0 （空閒）
************************************
請選擇：1、分配內存 2、回收內存 3、退出
請輸入作業名和作業大小：
************************************
起址 大小 狀態 （作業名）
0 5 1 OS
5 5 1 J1
10 16 0 （空閒）
26 6 1 J2
32 76 0 （空閒）
108 20 1 J6
************************************
請選擇：1、分配內存 2、回收內存 3、退出
請按任意鍵繼續. . .
