首次适应算法,最佳适应算法,最坏适应算法

#include

#define Free 0 //¿ÕÏÐ״̬

#define Busy 1 //ÒÑÓÃ״̬

#define OK 1    //Íê³É

#define ERROR 0 //³ö´í

#define MAX_length 0 //×î´óÄÚ´æ¿Õ¼äΪ0KB

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<<"ÇëÊäÈëÐèÒª·ÖÅäµÄÖ÷´æ´óС(µ¥Î»:KB)£º";

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<<"\\nÖ÷´æ·ÖÅäÇé¿ö:\\n";

cout<<"++++++++++++++++++++++++++++++++++++++++++++++\\n\\n";

DuLNode *p=block_first->next;

cout<<"·ÖÇøºÅ\ÆðʼµØÖ·\·ÖÇø´óС\״̬\\n\\n";

    while(p)

    {

cout<<" "< cout<<" "<data.address<<"\\";

cout<<" "<data.size<<"KB\\";

if(p->data.state==Free) cout<<"¿ÕÏÐ\\n\\n";

else cout<<"ÒÑ·ÖÅä\\n\\n";

p=p->next;

    }

cout<<"++++++++++++++++++++++++++++++++++++++++++++++\\n\\n";

}

//Ö÷º¯Êý

void main()

{

    int ch;//Ë㷨ѡÔñ±ê¼Ç

cout<<"ÇëÊäÈëËùʹÓõÄÄÚ´æ·ÖÅäËã·¨£º\\n";

cout<<"(1)Ê×´ÎÊÊÓ¦Ëã·¨\\n(2)×î¼ÑÊÊÓ¦Ëã·¨\\n(3)×î²îÊÊÓ¦Ëã·¨\\n";

cin>>ch;

while(ch<1||ch>3)

    {

     cout<<"ÊäÈë´íÎó£¬ÇëÖØÐÂÊäÈëËùʹÓõÄÄÚ´æ·ÖÅäËã·¨£º\\n";

     cin>>ch;

    }

    Initblock(); //¿ª´´¿Õ¼ä±í

    int choice;  //²Ù×÷Ñ¡Ôñ±ê¼Ç

    while(1)

    {

        show();

     cout<<"ÇëÊäÈëÄúµÄ²Ù×÷£º";

cout<<"\\n1: ·ÖÅäÄÚ´æ\\n2: »ØÊÕÄÚ´æ\\n0: Í˳ö\\n";

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;

        }

    }

}