这是一个非常完美的程序,输出显示的格式也很棒,里面包含首次适应算法,最佳适应算法,最坏适应算法
 
#include
 
#include
 
#define Free 0 //空闲状态
 
#define Busy 1 //已用状态
 
#define OK 1 //完成
 
#define ERROR 0 //出错
 
#define MAX_length 640 //最大内存空间为640KB
 
typedef int Status;
 
int flag;
 
typedef struct freearea//定义一个空闲区说明表结构
 
{
 
long size; //分区大小
 
long address; //分区地址
 
int state; //状态
 
}ElemType;
 
// 线性表的双向链表存储结构
 
typedef struct DuLNode
 
{
 
ElemType data;
 
struct DuLNode *prior; //前趋指针
 
struct DuLNode *next; //后继指针
 
}
 
DuLNode,*DuLinkList;
 
DuLinkList block_first; //头结点
 
DuLinkList block_last; //尾结点
 
Status alloc(int);//内存分配
 
Status free(int); //内存回收
 
Status First_fit(int);//首次适应算法
 
Status Best_fit(int); //最佳适应算法
 
Status Worst_fit(int); //最差适应算法
 
void show();//查看分配
 
Status Initblock();//开创空间表
 
Status Initblock()//开创带头结点的内存空间链表
 
{
 
block_first=(DuLinkList)malloc(sizeof(DuLNode));
 
block_last=(DuLinkList)malloc(sizeof(DuLNode));
 
block_first->prior=NULL;
 
block_first->next=block_last;
 
block_last->prior=block_first;
 
block_last->next=NULL;
 
block_last->data.address=0;
 
block_last->data.size=MAX_length;
 
block_last->data.state=Free;
 
return OK;
 
}
 
//分配主存
 
Status alloc(int ch)
 
{
 
int request = 0;
 
cout<
 
cin>>request;
 
if(request<0 ||request==0)
 
{
 
cout<
 
return ERROR;
 
}
 
if(ch==2) //选择最佳适应算法
 
{
 
if(Best_fit(request)==OK) cout<
 
else cout<
 
return OK;
 
}
 
if(ch==3) //选择最差适应算法
 
{
 
if(Worst_fit(request)==OK) cout<
 
else cout<
 
return OK;
 
}
 
else //默认首次适应算法
 
{
 
if(First_fit(request)==OK) cout<
 
else cout<
 
return OK;
 
}
 
}
 
//首次适应算法
 
Status First_fit(int request)
 
{
 
//为申请作业开辟新空间且初始化
 
DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));
 
temp->data.size=request;
 
temp->data.state=Busy;
 
DuLNode *p=block_first->next;
 
while(p)
 
{
 
if(p->data.state==Free && p->data.size==request)
 
{//有大小恰好合适的空闲块
 
p->data.state=Busy;
 
return OK;
 
break;
 
}
 
if(p->data.state==Free && p->data.size>request)
 
{//有空闲块能满足需求且有剩余
 
temp->prior=p->prior;
 
temp->next=p;
 
temp->data.address=p->data.address;
 
p->prior->nex

一、动态分区分配算法(连续分配管理方式)
 
动态分区分配算法：在动态分区分配方式中， 当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配？
 
 
（一）首次适应算法
 
算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
如何实现：空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
 
 
 
 
（二）最佳适应算法
 
算法思想：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即，优先使用更小的空闲区。
如何实现：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
 
 
 
（三）最坏适应算法
 
又称最大适应算法（Largest Fit）
算法思想：为了解决最佳适应算法的问题——即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。
如何实现：空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
 
 
缺点：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了。
 
（四）邻接适应算法
 
算法思想 ：首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。
如何实现：空闲分区以地址递增的顺序排列（可排成一个循环链表）。每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
 
 
 
首次适应算法每次都要从头查找，每次都需要检索低地址的小分区。
但是这种规则也决定了当低地址部分有更小的分区可以满足需求时，会更有可能用到低地址部分的小分区，也会更有可能把高地址部分的大分区保留下来（最佳适应算法的优点）
邻近适应算法的规则可能会导致无论低地址、高地址部分的空闲分区都有相同的概率被使用，也就导致了高地址部分的大分区更可能被使用，划分为小分区，最后导致无大分区可用（最大适应算法的缺点）综合来看，四种算法中，首次适应算法的效果反而更好
 

 
[c++]代码库#include
 
#include
 
using namespace std;
 
#define Free 0 //空闲状态
 
#define Busy 1 //已用状态
 
#define OK 1 //完成
 
#define ERROR 0 //出错
 
#define MAX_length 640 //最大内存空间为640KB
 
typedef int Status;
 
int flag;
 
typedef struct freearea//定义一个空闲区说明表结构
 
{
 
long size; //分区大小
 
long address; //分区地址
 
int state; //状态
 
}ElemType;
 
// 线性表的双向链表存储结构
 
typedef struct DuLNode
 
{
 
ElemType data;
 
struct DuLNode *prior; //前趋指针
 
struct DuLNode *next; //后继指针
 
}
 
DuLNode,*DuLinkList;
 
DuLinkList block_first; //头结点
 
DuLinkList block_last; //尾结点
 
Status alloc(int);//内存分配
 
Status free(int); //内存回收
 
Status First_fit(int);//首次适应算法
 
Status Best_fit(int); //最佳适应算法
 
Status Worst_fit(int); //最差适应算法
 
void show();//查看分配
 
Status Initblock();//开创空间表
 
Status Initblock()//开创带头结点的内存空间链表
 
{
 
block_first=(DuLinkList)malloc(sizeof(DuLNode));
 
block_last=(DuLinkList)malloc(sizeof(DuLNode));
 
block_first->prior=NULL;
 
block_first->next=block_last;
 
block_last->prior=block_first;
 
block_last->next=NULL;
 
block_last->data.address=0;
 
block_last->data.size=MAX_length;
 
block_last->data.state=Free;
 
return OK;
 
}
 
//分配主存
 
Status alloc(int ch)
 
{
 
int request = 0;
 
cout<
 
cin>>request;
 
if(request<0 ||request==0)
 
{
 
cout<
 
return ERROR;
 
}
 
if(ch==2) //选择最佳适应算法
 
{
 
if(Best_fit(request)==OK) cout<
 
else cout<
 
return OK;
 
}
 
if(ch==3) //选择最差适应算法
 
{
 
if(Worst_fit(request)==OK) cout<
 
else cout<
 
return OK;
 
}
 
else //默认首次适应算法
 
{
 
if(First_fit(request)==OK) cout<
 
else cout<
 
return OK;
 
}
 
}
 
//首次适应算法
 
Status First_fit(int request)
 
{
 
//为申请作业开辟新空间且初始化
 
DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));
 
temp->data.size=request;
 
temp->data.state=Busy;
 
DuLNode *p=block_first->next;
 
while(p)
 
{
 
if(p->data.state==Free && p->data.size==request)
 
{//有大小恰好合适的空闲块
 
p->data.state=Busy;
 
return OK;
 
break;
 
}
 
if(p->data.state==Free && p->data.size>request)
 
{//有空闲块能满足需求且有剩余
 
temp->prior=p->prior;
 
temp->next=p;
 
temp->data.address=p->data.address;
 
p->prior->next=temp;
 
p->prior=temp;
 
p->data.address=temp->data.address+temp->data.size;
 
p->data.size-=request;
 
return OK;
 
break;
 
}
 
p=p->next;
 
}
 
return ERROR;
 
}
 
//最佳适应算法
 
Status Best_fit(int request)
 
{
 
int ch; //记录最小剩余空间
 
DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));
 
temp->data.size=request;
 
temp->data.state=Busy;
 
DuLNode *p=block_first->next;
 
DuLNode *q=NULL; //记录最佳插入位置
 
while(p) //初始化最小空间和最佳位置
 
{
 
if(p->data.state==Free && (p->data.size>=request) )
 
{
 
if(q==NULL)
 
{
 
q=p;
 
ch=p->data.size-request;
 
}
 
else if(q->data.size > p->data.size)
 
{
 
q=p;
 
ch=p->data.size-request;
 
}
 
}
 
p=p->next;
 
}
 
if(q==NULL) return ERROR;//没有找到空闲块
 
else if(q->data.size==request)
 
{
 
q->data.state=Busy;
 
return OK;
 
}
 
else
 
{
 
temp->prior=q->prior;
 
temp->next=q;
 
temp->data.address=q->data.address;
 
q->prior->next=temp;
 
q->prior=temp;
 
q->data.address+=request;
 
q->data.size=ch;
 
return OK;
 
}
 
return OK;
 
}
 
//最差适应算法
 
Status Worst_fit(int request)
 
{
 
int ch; //记录最大剩余空间
 
DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));
 
temp->data.size=request;
 
temp->data.state=Busy;
 
DuLNode *p=block_first->next;
 
DuLNode *q=NULL; //记录最佳插入位置
 
while(p) //初始化最大空间和最佳位置
 
{
 
if(p->data.state==Free && (p->data.size>=request) )
 
{
 
if(q==NULL)
 
{
 
q=p;
 
ch=p->data.size-request;
 
}
 
else if(q->data.size < p->data.size)
 
{
 
q=p;
 
ch=p->data.size-request;
 
}
 
}
 
p=p->next;
 
}
 
if(q==NULL) return ERROR;//没有找到空闲块
 
else if(q->data.size==request)
 
{
 
q->data.state=Busy;
 
return OK;
 
}
 
else
 
{
 
temp->prior=q->prior;
 
temp->next=q;
 
temp->data.address=q->data.address;
 
q->prior->next=temp;
 
q->prior=temp;
 
q->data.address+=request;
 
q->data.size=ch;
 
return OK;
 
}
 
return OK;
 
}
 
//主存回收
 
Status free(int flag)
 
{
 
DuLNode *p=block_first;
 
for(int i= 0; i <= flag; i++)
 
if(p!=NULL)
 
p=p->next;
 
else
 
return ERROR;
 
p->data.state=Free;
 
if(p->prior!=block_first && p->prior->data.state==Free)//与前面的空闲块相连
 
{
 
p->prior->data.size+=p->data.size;
 
p->prior->next=p->next;
 
p->next->prior=p->prior;
 
p=p->prior;
 
}
 
if(p->next!=block_last && p->next->data.state==Free)//与后面的空闲块相连
 
{
 
p->data.size+=p->next->data.size;
 
p->next->next->prior=p;
 
p->next=p->next->next;
 
}
 
if(p->next==block_last && p->next->data.state==Free)//与最后的空闲块相连
 
{
 
p->data.size+=p->next->data.size;
 
p->next=NULL;
 
}
 
return OK;
 
}
 
//显示主存分配情况
 
void show()
 
{
 
int flag = 0;
 
cout<
 
cout<
 
DuLNode *p=block_first->next;
 
cout<
 
while(p)
 
{
 
cout<
 
cout<data.address<
 
cout<data.size<
 
if(p->data.state==Free) cout<
 
else cout<
 
p=p->next;
 
}
 
cout<
 
}
 
//主函数
 
void main()
 
{
 
int ch;//算法选择标记
 
cout<
 
cout<
 
cin>>ch;
 
while(ch<1||ch>3)
 
{
 
cout<
 
cin>>ch;
 
}
 
Initblock(); //开创空间表
 
int choice; //操作选择标记
 
while(1)
 
{
 
show();
 
cout<
 
cout<
 
cin>>choice;
 
if(choice==1) alloc(ch); // 分配内存
 
else if(choice==2) // 内存回收
 
{
 
int flag;
 
cout<
 
cin>>flag;
 
free(flag);
 
}
 
else if(choice==0) break; //退出
 
else //输入操作有误
 
{
 
cout<
 
continue;
 
}
 
}
 
}
 

 
 
学习地址（哔哩哔哩网站——王道论坛）：https://www.bilibili.com/video/BV1YE411D7nH?p=37
 
 
目录
 
1、首次适应算法（First Fit）
 
2、最佳适应算法（Best Fit）
 
3、最坏适应算法（Worst Fit）【又称“最大适应算法”（Largest Fit）】
 
4、临近适应算法（Next Fit）
 
动态分区分配算法总结
 

 
 
 
 
1、首次适应算法（First Fit）
 
 
 
 
 
 
 
2、最佳适应算法（Best Fit）
 
 
 
 
 
 
 
3、最坏适应算法（Worst Fit）【又称“最大适应算法”（Largest Fit）】
 
 
 
 
 
空闲分区链，必须按照容量递减的次序进行排序；若不满足容量递减的次序，则重新进行排序！
 
 
 
 
4、临近适应算法（Next Fit）
 
 
 
 
 
空闲分区以地址递增的顺序进行排列。内存分区的大小发生了变化，并不需要对整个链表重新进行排序。算法开销小。
 
 
 
 
算法总结
 
 
 
 
 
 
算法
 
 
算法思想
 
 
分区排列顺序
 
 
优点
 
 
缺点
 
 
首次适应算法（First Fit）
 
 
从头到尾寻找合适的分区
 
 
空闲分区以地址递增次序排列
 
 
综合看，首次适应算法性能最好。算法开销小，回收分区后，一般不需要对空闲分区队列重新排序
 
 
 
 
 
最佳适应算法（Best Fit）
 
 
优先使用更小的分区，以保留更多的大分区
 
 
空闲分区以容量递增次序排列
 
 
会有更多的大分区被保留下来，更能满足大进程需求
 
 
会产生很多太小的、难以利用的碎片：算法开销大，回收分区后可能需要对空闲分区队列重新排序
 
 
最坏适应算法（Worst Fit）
 
【又称“最大适应算法”（Largest Fit）】
 
 
优先使用更大的分区，以防止产生太小的不可用碎片
 
 
空闲分区以容量递减次序排列
 
 
可以减少难以利用的小碎片
 
 
大分区容易被用完，不利于大进程：算法开销大（原因同上）
 
 
临近适应算法（Next Fit）
 
 
由首次适应算法演变而来，每次从上次查找结束的位置开始查找
 
 
空闲分区以地址递增次序排列（可排列成循环链表）
 
 
不用每次都从低地址的小分区开始检索。算法开销小（原因同首次适应算法）
 
 
会使高地址的大分区也被用完