循环首次适应算法介绍

每次为进程分配空间的时候，从上一次刚分配过的空闲区的下一块开始寻找，比如，初始化的内存空闲区是用户输入的max大小，没有进行回收之前之前必定是只有最后一块是空闲的，但是经过回收之后，你设定的表（这里是设定了一张表，也可以用俩张，但是一张就可以解决的没必要俩张），从是空闲区的区号开始分配之后，标记此块,下次分配从标记的这一块开始向下寻找，符合就分配，然后标记分配的空闲区区号，与首次适应算法的区别就在这

代码

#include #include #include #define Free 0 //空闲状态 #define Busy 1 //已用状态 #define OK 1    //完成 #define ERROR 0 //出错 typedef int Status; int flag; /**  *设置空闲块  *有三个标识符  *address起始地址  *size空闲块大小  *state空闲块状态  */ typedef struct freearea {     int address;//空闲区地址     int size;//作业空间大小     int state;//空闲去状态 }ElemType; /**  *设置链表指针  */ typedef struct DuLNode {     ElemType data;     struct DuLNode *prior;     struct DuLNode *next; }DuLNode, *DuLinkList; /**  *block_first  *链表首地址  *block_last  *链表尾地址  */ DuLinkList block_first; DuLinkList lastfind; DuLinkList block_last; void alloc(int); void free(int); Status NF(int); void show(); void initblock(); /**  *初始化内存  *传入用户需设置的内存大小MAX_length  */ void initblock(int MAX_length) {     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; } /**  *输入进程请求的空闲块大小  *调用分配空闲块大小的算法NF（response）  */ void alloc() {     int request;     printf("请您输入进程所需分配的空间大小：");     scanf("%d",&request);     if(request         if(NF(request)==OK)             {                 printf("分配成功！");             }         else             {                 printf("内存不足分配失败！");             }     } } /**  *循环首次适应算法  *lastfind为上次分配空闲的位置，如果是首次分配就不存在lastfind  *request为用户输入的进程请求空闲块的大小  *寻找内存中空闲块大于等于请求的空闲块  *即size>response&&state=Free  *等于则直接修改该状态  *大于则分配response大小后把剩余的存为空闲块  *找到则标记为lastfind  */ Status NF(int request) {     DuLinkList temp = (DuLinkList)malloc(sizeof(DuLNode));     temp->data.size=request;     temp->data.state=Busy;     if(lastfind)     {         while(lastfind)         {             if(lastfind->data.state==Free&&lastfind->data.size==request)             {                 lastfind->data.state=Busy;                 lastfind=lastfind->next;                 return OK;                 break;             }             if(lastfind->data.state==Free&&lastfind->data.size>request)             {                 temp->prior=lastfind->prior;                 temp->next=lastfind;                 temp->data.address=lastfind->data.address;                 lastfind->prior->next=temp;                 lastfind->prior=temp;                 lastfind->data.address=temp->data.address+temp->data.size;                 lastfind->data.size=lastfind->data.size-request;                 lastfind=lastfind->next;                 return OK;                 break;             }             lastfind=lastfind->next;         }     }     else     {         DuLNode *p = block_first->next;         while(p)         {             if(p->data.state==Free&&p->data.size==request)             {                 p->data.state=Busy;                 lastfind=p->next;                 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=p->data.size-request;                 lastfind=p->next;                 return OK;                 break;             }             p=p->next;         }     } } /**  *回收内存算法  *若回收的区号的左右指针均为空闲块，则三块回收为一块  *若只有左指针为空闲块，则俩块合并为一块  *若只有右指针为空闲块，则俩块合并为一块  *若左右均不是空闲块，则只改变该区号的状态为空闲  */ void free(int flag) {     DuLNode *p = block_first;     for(int i=0;i             p=p->next;         }     }     p->data.state=Free;     if(p->prior->data.state==Free&&p->next->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->prior->data.state!=Free&&p->next->data.state==Free)     {         p->next->data.size+=p->data.size;         p->next->data.address=p->data.address;         p->next->prior=p->prior;         p->prior->next=p->next;         p=p->next;     }     if(p->prior->data.state==Free&&p->next->data.state==Free)     {         p->next->data.size+=p->data.size+=p->prior->data.size;         p->next->data.address=p->prior->data.address;         p->next->prior=p->prior->prior;         p->prior->prior->next=p->next;         p=p->next;     } } /**  *显示内存分配函数  *从链表的首指针开始  *依次显示  */ void show() {     int flag=0;     printf("主存分配情况：\n");     DuLNode *q=block_first->next;     printf("分区号\t起始地址 分区大小\t状态\n\n");     while(q)     {         printf("%d\t",flag);         flag++;         printf("%d\t",q->data.address);         printf("%dKB\t",q->data.size);         if(q->data.state==Free)         {             printf("      空闲\n\n");         }         else         {             printf("      已分配\n\n");         }         q=q->next;     }     printf("++++++++++++++++++++++++++++\n"); } int main() {     int c=1;     int MAX_length;     printf("**********您现在操作的是循环首次适应分配算法*****************\n");     printf("***请输入初始空闲片的大小：");     scanf("%d",&MAX_length);     initblock(MAX_length);     int choice;     while(c==1)     {         printf("\n1: 分配内存   2:回收内存  3:退出系统  4:显示内存分配情况\n");         printf("*******请输入您将进行的操作：");         scanf("%d",&choice);         if(choice==1)         {             alloc();             c=1;         }         else if(choice==2)         {             printf("请输入您想要回收的空闲块区号：");             scanf("%d",&flag);             free(flag);             c=1;         }         else if(choice==3)         {             exit(1);         }         else if(choice==4)         {             show();             c=1;         }         else         {             printf("操作不存在 请重新输入！");             c=1;         }     }     return 0; }