• 动态分区算法（头歌实验）第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为释放内存的作业号

    代码：

    1. #include 
    2. #include 
    3. const int Max_length=55;//最大内存
    4. struct areaNode//管理分区的结构体
    5. {
    6.     int ID;//分区号 
    7.     int size;//分区大小 
    8.     int address;//分区地址 
    9.     int flag;//使用状态，0为未占用，1为已占用
    10. };
    11. typedef struct DuNode//双向链表结点
    12. {
    13.   struct areaNode data;//数据域 
    14.   struct DuNode *prior;//指针域 
    15.   struct DuNode *next;
    16. }*DuLinkList;
    17. DuLinkList m_head = new DuNode, m_last = new DuNode;//双向链表首尾指针
    18. void init()//分区链表初始化
    19. {
    20.   m_head->prior = NULL;
    21.   m_head->next = m_last;
    22.   m_last->prior = m_head;
    23.   m_last->next = NULL;
    24.   m_head->data.size = 0;
    25.   m_last->data.address = 0;
    26.   m_last->data.size = Max_length;
    27.   m_last->data.ID = 0;
    28.   m_last->data.flag = 0;
    29. }
    30. void show()
    31. {
    32.   DuNode *p = m_head->next;//指向空闲区队列的首地址 
    33.   printf("+++++++++++++++++++++++++++++++++++++++\n");
    34.   while (p)
    35.   {
    36.     printf("分区号：");
    37.  if (p->data.ID == 0)
    38.    printf("FREE\n");
    39.  else
    40.    printf("%d\n",p->data.ID);
    41.  printf("分区起始地址：%d\n",p->data.address);
    42.  printf("分区大小：%d\n",p->data.size);
    43.  printf("分区状态：");
    44.  if (p->data.flag)
    45.    printf("已被占用\n");
    46.  else
    47.    printf("空闲\n");
    48.  printf("——————————————————\n");
    49.  p = p->next;
    50.   }
    51. }
    52. bool first_fit(int id,int m_size)//首次适应算法,id为作业号，m_size为作业大小 
    53. {
    54.      //请补充使用首次适应算法给作业分配内存的函数代码
    55.     DuLinkList p = m_head;
    56.     while(p != m_last) {
    57.         DuLinkList n = p->next;
    58.         if(!n->data.flag && n->data.size >= m_size) {
    59.             DuLinkList t = new DuNode();
    60.             t->data.ID = id;
    61.             t->data.size = m_size;
    62.             t->data.address = n->data.address;
    63.             t->data.flag = 1;
    64.             n->data.address += m_size;
    65.             n->data.size -= m_size;
    66.             t->prior = p;
    67.             t->next = n;
    68.             p->next = t;
    69.             n->prior = t;
    70.         }
    71.         p = n;
    72.     }
    73. }
    74. void recycle(int id)//回收内存,id为释放内存的作业号 
    75. {
    76.     DuLinkList p = m_head;
    77.     while(p != m_last) {
    78.         DuLinkList n = p->next;
    79.         if(n->data.ID == id) {
    80.             p->next = n->next;
    81.             n->next->prior = p;
    82.             n->next->data.address -= n->data.size;
    83.             m_last->data.size += n->data.size;
    84.             delete n;
    85.             n = n->next;
    86.         }
    87.         if(n != m_last)
    88.             n->next->data.address = n->data.address + n->data.size;
    89.         p = n;
    90.     }
    91. }
    92. int main()
    93. {
    94.  init();
    95.     printf("首次适应算法：\n");
    96.  first_fit(1,15);
    97.  first_fit(2,30);
    98.  recycle(1);
    99.  first_fit(3,8);
    100.  first_fit(4,6);
    101.  recycle(2);
    102.  show();
    103.  DuNode *p = m_head;
    104.  while(p != NULL)
    105.  {
    106.   DuNode *temp =  p;
    107.   p = p->next;
    108.   delete(temp);
    109.   temp = NULL;
    110.  }
    111.  return 0;
    112. }

    效果截图：

    第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为释放内存的作业号

    代码：

    1. #include 
    2. #include 
    3. const int Max_length=55;//最大内存
    4. struct areaNode//管理分区的结构体
    5. {
    6.     int ID;//分区号 
    7.     int size;//分区大小 
    8.     int address;//分区地址 
    9.     int flag;//使用状态，0为未占用，1为已占用
    10. };
    11. typedef struct DuNode//双向链表结点
    12. {
    13.   struct areaNode data;//数据域 
    14.   struct DuNode *prior;//指针域 
    15.   struct DuNode *next;
    16. }*DuLinkList;
    17. DuLinkList m_head = new DuNode, m_last = new DuNode;//双向链表首尾指针
    18. void init()//分区链表初始化
    19. {
    20.   m_head->prior = NULL;
    21.   m_head->next = m_last;
    22.   m_last->prior = m_head;
    23.   m_last->next = NULL;
    24.   m_head->data.size = 0;
    25.   m_last->data.address = 0;
    26.   m_last->data.size = Max_length;
    27.   m_last->data.ID = 0;
    28.   m_last->data.flag = 0;
    29. }
    30. void show()
    31. {
    32.   DuNode *p = m_head->next;//指向空闲区队列的首地址 
    33.   printf("+++++++++++++++++++++++++++++++++++++++\n");
    34.   while (p)
    35.   {
    36.     printf("分区号：");
    37.  if (p->data.ID == 0)
    38.    printf("FREE\n");
    39.  else
    40.    printf("%d\n",p->data.ID);
    41.  printf("分区起始地址：%d\n",p->data.address);
    42.  printf("分区大小：%d\n",p->data.size);
    43.  printf("分区状态：");
    44.  if (p->data.flag)
    45.    printf("已被占用\n");
    46.  else
    47.    printf("空闲\n");
    48.  printf("——————————————————\n");
    49.  p = p->next;
    50.   }
    51. }
    52. bool best_fit(int id, int m_size)//最佳适应算法，其中需要查找最佳的存放位置
    53. {
    54.       //请补充使用最佳适应算法给作业分配内存的函数代码
    55.     DuLinkList p = m_head;
    56.     DuLinkList t = nullptr;
    57.     while(p != m_last) {
    58.         DuLinkList n = p->next;
    59.         if(!n->data.flag && n->data.size >= m_size) {
    60.             if(t == nullptr || t->data.size > n->data.size){
    61.                 t = n;
    62.             }
    63.         }
    64.         p = n;
    65.     }
    66.     if(t == nullptr)
    67.         return false;
    68.     if(t->data.size == m_size) {
    69.         t->data.flag = 1;
    70.         t->data.ID = id;
    71.     }
    72.     else {
    73.         DuLinkList t2 = new DuNode();
    74.         t2->next = t;
    75.         t2->prior = t->prior;
    76.         t->prior->next = t2;
    77.         t->prior = t2;
    78.         t2->data.ID = id;
    79.         t2->data.flag = 1;
    80.         t2->data.address = t->data.address;
    81.         t->data.address += m_size;
    82.         t2->data.size = m_size;
    83.         t->data.size -= m_size;
    84.     }
    85.     return true;
    86. }
    87. void recycle(int id)//回收内存,id为释放内存的作业号 
    88. {
    89.      //请补充回收作业内存的函数代码
    90.     DuLinkList p = m_head;
    91.     DuLinkList n = nullptr;
    92.     while(p != m_last) {
    93.         n = p->next;
    94.         if(n->data.ID == id) {
    95.             break;
    96.         }
    97.         p = n;
    98.     }
    99.     if(n == nullptr || n == m_last)
    100.         return;
    101.     n->data.flag = 0;
    102.     n->data.ID = 0;
    103.     DuLinkList np = n->prior;
    104.     DuLinkList nn = n->next;
    105.     if(np != m_head && np->data.flag == 0) {
    106.         np->prior->next = n;
    107.         n->prior = np->prior->next;
    108.         n->data.address = np->data.address;
    109.         n->data.size += np->data.size;
    110.         delete np;
    111.     }
    112.     if((nn != nullptr || nn != m_last) && nn->data.flag == 0) {
    113.         nn->next->prior = n;
    114.         n->next = nn->next->prior;
    115.         n->data.size += nn->data.size;
    116.         delete nn;
    117.     }
    118. }
    119. int main()
    120. {
    121.  init();
    122.     //最佳适应算法
    123.  printf("最佳适应算法：\n");
    124.  init();
    125.  best_fit(1,15);
    126.  best_fit(2,30);
    127.  recycle(1);
    128.  best_fit(3,8);
    129.  best_fit(4,6);
    130.  recycle(2);
    131.  show();
    132.  DuNode *p = m_head;
    133.  while(p != NULL)
    134.  {
    135.   DuNode *temp =  p;
    136.   p = p->next;
    137.   delete(temp);
    138.   temp = NULL;
    139.  }
    140.  return 0;
    141. }

    效果截图：

    总结

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

  • 相关阅读:
    【23真题】招600+，太火爆！题目略难！快来挑战！
    MongoDB随记
    涨姿势了，有意思的气泡 Loading 效果
    基于Java的4S店汽车商城系统设计与实现(源码+lw+部署文档+讲解等)
    耳鸣会给患者带来什么影响?
    手写RPC框架
    【TypeScript】语法详解 - 类型操作的补充
    十年JAVA搬砖路——快速排序算法
    跨平台应用开发进阶(四十五)uni-app自定义组包app:checkReleaseDuplicateClasses问题分析及解决
    常用函数式接口：Consumer、Predicate、Function的方法说明解练习
  • 原文地址：https://blog.csdn.net/m0_65420451/article/details/127921681