搜索
#includestdio.h#includestdlib.h#includeiostream.h#defineFree0//¿ÕÏÐ״̬#defineBusy1//ÒÑÓÃ״̬#defineOK1//Íê³É#defineERROR0//³ö´í#defineMAX_length100//×î´óÄÚ´æ¿Õ¼äΪ100MtypedefintStatus;intflag;//±êÖ¾typedefstructfreearea//¶¨ÒåÒ»¸ö¿ÕÏÐÇø˵Ã÷±í½á¹¹{longsize;//·ÖÇø´óСlongaddress;//·ÖÇøµØÖ·intstate;//״̬}ElemType;//ÔªËØÀàÐÍ//ÏßÐÔ±íµÄË«ÏòÁ´±í´æ´¢½á¹¹typedefstructDuLNode//½á¹¹Ö¸Õë{ElemTypedata;structDuLNode*prior;//Ç°Ç÷Ö¸ÕëstructDuLNode*next;//ºó¼ÌÖ¸Õë}DuLNode,*DuLinkList;//Ö¸ÕëÁ´±íDuLinkListblock_first;//Í·½áµãDuLinkListblock_last;//β½áµãStatusalloc(int);//ÄÚ´æ·ÖÅäStatusfree(int);//ÄÚ´æ»ØÊÕStatusBest_fit(int);//×î¼ÑÊÊÓ¦Ëã·¨StatusWorst_fit(int);//×î²îÊÊÓ¦Ëã·¨voidshow();//²é¿´·ÖÅäStatusInitblock();//¿ª´´¿Õ¼ä±íStatusInitblock()//¿ª´´´øÍ·½áµãµÄÄÚ´æ¿Õ¼äÁ´±í{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;returnOK;}//·ÖÅäÖ÷´æStatusalloc(intch){intrequest=0;coutÇëÊäÈëÐèÒª·ÖÅäµÄÖ÷´æ´óС(µ¥Î»:M)£º;cinrequest;if(request0||request==0){cout·ÖÅä´óС²»ºÏÊÊ£¬ÇëÖØÊÔ£¡endl;returnERROR;}if(ch==2)//Ñ¡Ôñ×î²îÊÊÓ¦Ëã·¨{if(Worst_fit(request)==OK)cout·ÖÅä³É¹¦£¡endl;elsecoutÄÚ´æ²»×㣬·ÖÅäʧ°Ü£¡endl;returnOK;}}//×î¼ÑÊÊÓ¦Ëã·¨StatusBest_fit(intrequest){intch;//¼Ç¼×îСʣÓà¿Õ¼äDuLinkListtemp=(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;}elseif(q-data.sizep-data.size){q=p;ch=p-data.size-request;}}p=p-next;}if(q==NULL)returnERROR;//ûÓÐÕÒµ½¿ÕÏпéelseif(q-data.size==request){{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;returnOK;}returnOK;}//×î²îÊÊÓ¦Ëã·¨StatusWorst_fit(intrequest){intch;//¼Ç¼×î´óÊ£Óà¿Õ¼äDuLinkListtemp=(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;}elseif(q-data.sizep-data.size){q=p;ch=p-data.size-request;}}p=p-next;}if(q==NULL)returnERROR;//ûÓÐÕÒµ½¿ÕÏпéelseif(q-data.size==request){q-data.state=Busy;returnOK;}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;returnOK;}returnOK;}//Ö÷´æ»ØÊÕStatusfree(intflag){DuLNode*p=block_first;for(inti=0;i=flag;i++)if(p!=NULL)p=p-next;elsereturnERROR;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;}returnOK;}//ÏÔʾÖ÷´æ·ÖÅäÇé¿övoidshow(){intflag=0;cout\nÖ÷´æ·ÖÅäÇé¿ö:\n;cout++++++++++++++++++++++++++++++++++++++++++++++\n\n;DuLNode*p=block_first-next;cout·ÖÇøºÅ\tÆðʼµØÖ·\t·ÖÇø´óС\t״̬\n\n;while(p){coutflag++\t;coutp-data.address\t\t;coutp-data.sizeM\t\t;if(p-data.state==Free)cout¿ÕÏÐ\n\n;elsecoutÒÑ·ÖÅä\n\n;p=p-next;}cout++++++++++++++++++++++++++++++++++++++++++++++\n\n;}//Ö÷º¯Êývoidmain(){intch;//Ë㷨ѡÔñ±ê¼Çl1:coutÇëÊäÈëËùʹÓõÄÄÚ´æ·ÖÅäËã·¨£º\n;cout(1)×î¼ÑÊÊÓ¦Ëã·¨\n(2)×î²îÊÊÓ¦Ëã·¨\n;cinch;while(ch1||ch2){coutÊäÈë´íÎó£¬ÇëÖØÐÂÊäÈëËùʹÓõÄÄÚ´æ·ÖÅäËã·¨£º\n;cinch;}Initblock();//¿ª´´¿Õ¼ä±íintchoice;//²Ù×÷Ñ¡Ôñ±ê¼Çwhile(1){show();coutÇëÊäÈëÄúµÄ²Ù×÷£º;cout\n1:·ÖÅäÄÚ´æ\n2:»ØÊÕÄÚ´æ\n3:·µ»ØÉÏÒ»²ã\n0:Í˳ö\n;cinchoice;if(choice==3){gotol1;}elseif(choice==1)alloc(ch);//·ÖÅäÄÚ´æelseif(choice==2)//ÄÚ´æ»ØÊÕ{intflag;coutÇëÊäÈëÄúÒªÊͷŵķÖÇøºÅ£º;cinflag;free(flag);}elseif(choice==0)break;//Í˳öelse//ÊäÈë²Ù×÷ÓÐÎó{coutÊäÈëÓÐÎó£¬ÇëÖØÊÔ£¡endl;continue;}}}