动态分区算法（头歌实验）第1关：首次适应算法。第2关：最佳适应算法。

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

题目：

第1关：首次适应算法

任务描述

假设初始状态下可用的内存空间为55MB，并有如下的请求序列： 作业1申请15MB 作业2申请30MB 作业1释放15MB 作业3分配8MB 作业4分配6MB 作业2释放30MB 请采用首次适应算法进行内存块的分配和回收，并打印出空闲内存分区链的情况

相关知识

内存分配

空闲分区链按地址递增的顺序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区。然后再按照作业的大小，从该分区中划出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中。若从链首到链尾都找不到一个能满足要求的分区，则表明系统没有足够大的内存分配给该进程，内存分配失败返回。

内存回收

当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一：

(1) 回收区与插入点的前一个空闲分区F1相邻接，此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小。

(2) 回收分区与插入点的后一空闲分区F2相邻接，此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。

(3) 回收区同时与插入点的前、后两个分区F1和F2邻接，此时将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和。

(4) 回收区前后没有空闲分区。这时应为回收区单独建立一个新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置

编程要求

空闲分区采用带头结点的双向链表来管理，主函数、链表初始化函数和打印函数已实现，只需要补充首次适应算法分配内存的函数 first_fit以及内存回收的函数recycle()即可。

bool first_fit(int id,int m_size)//使用首次适应算法给作业分配内存，id为作业号，m_size为作业大小 void recycle(int id)//回收内存,id为释放内存的作业号

代码：

#include #include const int Max_length=55;//最大内存struct areaNode//管理分区的结构体{int ID;//分区号 int size;//分区大小 int address;//分区地址 int flag;//使用状态，0为未占用，1为已占用};typedef struct DuNode//双向链表结点{struct areaNode data;//数据域 struct DuNode *prior;//指针域 struct DuNode *next;}*DuLinkList;DuLinkList m_head = new DuNode, m_last = new DuNode;//双向链表首尾指针void init()//分区链表初始化{m_head->prior = NULL;m_head->next = m_last;m_last->prior = m_head;m_last->next = NULL;m_head->data.size = 0;m_last->data.address = 0;m_last->data.size = Max_length;m_last->data.ID = 0;m_last->data.flag = 0;}void show(){DuNode *p = m_head->next;//指向空闲区队列的首地址 printf("+++++++++++++++++++++++++++++++++++++++\n");while (p){printf("分区号："); if (p->data.ID == 0) printf("FREE\n"); else printf("%d\n",p->data.ID); printf("分区起始地址：%d\n",p->data.address); printf("分区大小：%d\n",p->data.size); printf("分区状态："); if (p->data.flag) printf("已被占用\n"); else printf("空闲\n"); printf("——————————————————\n"); p = p->next;}}bool first_fit(int id,int m_size)//首次适应算法,id为作业号，m_size为作业大小 { //请补充使用首次适应算法给作业分配内存的函数代码DuLinkList p = m_head;while(p != m_last) {DuLinkList n = p->next;if(!n->data.flag && n->data.size >= m_size) {DuLinkList t = new DuNode();t->data.ID = id;t->data.size = m_size;t->data.address = n->data.address;t->data.flag = 1;n->data.address += m_size;n->data.size -= m_size;t->prior = p;t->next = n;p->next = t;n->prior = t;}p = n;}}void recycle(int id)//回收内存,id为释放内存的作业号 {DuLinkList p = m_head;while(p != m_last) {DuLinkList n = p->next;if(n->data.ID == id) {p->next = n->next;n->next->prior = p;n->next->data.address -= n->data.size;m_last->data.size += n->data.size;delete n;n = n->next;}if(n != m_last)n->next->data.address = n->data.address + n->data.size;p = n;}}int main(){ init();printf("首次适应算法：\n"); first_fit(1,15); first_fit(2,30); recycle(1); first_fit(3,8); first_fit(4,6); recycle(2); show(); DuNode *p = m_head; while(p != NULL) {DuNode *temp =p;p = p->next;delete(temp);temp = NULL; } return 0;}

效果截图：

第2关：最佳适应算法

假设初始状态下可用的内存空间为55MB，并有如下的请求序列： 作业1申请15MB 作业2申请30MB 作业1释放15MB 作业3分配8MB 作业4分配6MB 作业2释放30MB 请采用最佳适应算法进行内存块的分配和回收，并打印出空闲内存分区链的情况

编程要求

空闲分区采用带头结点的双向链表来管理，主函数、链表初始化函数和打印函数已实现，只需要补充最佳适应算法分配内存的函数 best_fit以及内存回收的函数recycle()即可。

bool best_fit(int id,int m_size)//使用最佳适应算法给作业分配内存，id为作业号，m_size为作业大小 void recycle(int id)//回收内存,id为释放内存的作业号

代码：

#include #include const int Max_length=55;//最大内存struct areaNode//管理分区的结构体{int ID;//分区号 int size;//分区大小 int address;//分区地址 int flag;//使用状态，0为未占用，1为已占用};typedef struct DuNode//双向链表结点{struct areaNode data;//数据域 struct DuNode *prior;//指针域 struct DuNode *next;}*DuLinkList;DuLinkList m_head = new DuNode, m_last = new DuNode;//双向链表首尾指针void init()//分区链表初始化{m_head->prior = NULL;m_head->next = m_last;m_last->prior = m_head;m_last->next = NULL;m_head->data.size = 0;m_last->data.address = 0;m_last->data.size = Max_length;m_last->data.ID = 0;m_last->data.flag = 0;}void show(){DuNode *p = m_head->next;//指向空闲区队列的首地址 printf("+++++++++++++++++++++++++++++++++++++++\n");while (p){printf("分区号："); if (p->data.ID == 0) printf("FREE\n"); else printf("%d\n",p->data.ID); printf("分区起始地址：%d\n",p->data.address); printf("分区大小：%d\n",p->data.size); printf("分区状态："); if (p->data.flag) printf("已被占用\n"); else printf("空闲\n"); printf("——————————————————\n"); p = p->next;}}bool best_fit(int id, int m_size)//最佳适应算法，其中需要查找最佳的存放位置{//请补充使用最佳适应算法给作业分配内存的函数代码DuLinkList p = m_head;DuLinkList t = nullptr;while(p != m_last) {DuLinkList n = p->next;if(!n->data.flag && n->data.size >= m_size) {if(t == nullptr || t->data.size > n->data.size){t = n;}}p = n;}if(t == nullptr)return false;if(t->data.size == m_size) {t->data.flag = 1;t->data.ID = id;}else {DuLinkList t2 = new DuNode();t2->next = t;t2->prior = t->prior;t->prior->next = t2;t->prior = t2;t2->data.ID = id;t2->data.flag = 1;t2->data.address = t->data.address;t->data.address += m_size;t2->data.size = m_size;t->data.size -= m_size;}return true;}void recycle(int id)//回收内存,id为释放内存的作业号 { //请补充回收作业内存的函数代码DuLinkList p = m_head;DuLinkList n = nullptr;while(p != m_last) {n = p->next;if(n->data.ID == id) {break;}p = n;}if(n == nullptr || n == m_last)return;n->data.flag = 0;n->data.ID = 0;DuLinkList np = n->prior;DuLinkList nn = n->next;if(np != m_head && np->data.flag == 0) {np->prior->next = n;n->prior = np->prior->next;n->data.address = np->data.address;n->data.size += np->data.size;delete np;}if((nn != nullptr || nn != m_last) && nn->data.flag == 0) {nn->next->prior = n;n->next = nn->next->prior;n->data.size += nn->data.size;delete nn;}}int main(){ init();//最佳适应算法 printf("最佳适应算法：\n"); init(); best_fit(1,15); best_fit(2,30); recycle(1); best_fit(3,8); best_fit(4,6); recycle(2); show(); DuNode *p = m_head; while(p != NULL) {DuNode *temp =p;p = p->next;delete(temp);temp = NULL; } return 0;}

效果截图：

总结

提示：这里对文章进行总结：
例如：以上就是今天要讲的内容，本文仅仅简单介绍了动态分区算法（头歌实验）第1关：首次适应算法。第2关：最佳适应算法。