动态分区分配方式的模拟C语言代码和C代码

实验三使用动态分区分配方式的模拟K实验目的了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。2、实验内容用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc()和回收过程fiee()o其中，空闲分区通过空闲分区链來管理：在进行内存分配时，系统优先使用空闲区低端的空间。假设初始状态下，可用的内存空间为640KB,并有下列的请求序列：•作业1申请130KB。•作业2申请60KB。•作业3申请lOOKBo•作业2释放60KBo•作业4申请200KBo•作业3释放lOOKBo•作业1释放130KBo•作业5申请140KBo•作业6申请60KB。•作业7申请50KB。•作业6释放60KBo请分别采用首次适应算法和最佳适应算法，对内存块进行分配和回收，要求每次分配和回收后显示出空闲分区链的情况。程序代一_C语言实现#iiiclude<stdio.h>#iiiclude<stdlib.h>stmctnode〃空闲分区链结点的定义{node*before;node*after;intsize;intaddress;intstate;}；nodeL;structusenode{usenode*next;intnum;intadd;intsize;}U/n;voidImt()〃空闲分区链的初始化node*p;p=(node*)malloc(sizeof(node));p->before=&L;p->aftei-NULL;p->size=640;p->addiess=O;p->state=O;L.after=p;L.befbre=NULL;L.size=0;U.next=NULL;n=&U;node*seaich(mta){node*p=L.after;if(p=NULL){pmirff没有空闲的区域V);p=NULL;returnp;}else{wliile(p!=NULL&&a>p->size)p=p->after;if(p—NULL){prmtf(”没有找到合适的空闲空间!”);p=NULL;returnp;}elsereturnp;}voidrecovery(intajntb)〃内存回收算法node*c,*s,*r=L.after;node*d=L.aftei\*e;usenode*k=U.next,*h=&U;while(k?=NULL&&a!=k->num){h=k;k=k->next;}if(k=NULL)pmitf(”没有找到这样的作业!”)；else{h->next=k->next;if(h->next==NULL)n=h;}wlule(r!=NULL)〃若回收得到的空闲块的前方有空闲块合并此空闲块{if(k->add==i•->addiess+r->size){r->size=i->size+k->size;break;}elsei-r->after;}if(i-==NULL)〃若回收得到的空闲块的后面有空闲块合并此空闲块{r=L.after;wlule(r!=NULL)if(k->add+k->size=r->address){r->address=k->add;r->size=i•->size+k->size;break;}elsei-r->after;}}wlule(d!=NULL)〃保证空闲链表中没有相邻的空闲空间{if(d->after!=NULL)e=d->after;elsebreak;ifi(d->addiess+d->size==e->addiess){d->after=e->after;while(e->after!=NULL)e->after->befbre=d;d->size=d・>size+e->size;firee(e);break;}elsed=d->after;}if(i-==NULL){r=L.after;c=(node*)malloc(sizeof(node));c->size=b;c->addiess=k->add;if(L.after=NULL){c->aftei-L.after;c->befbre=&L;L.after=c;}else{i-L.after;wlule(r!=NULL){if(r->address>c->address)c->after=r;c->before=r->befbie;r->befbre->aftei-c;r->befdre=c;fiee(k);return;}elsei=r->after;}}}fiee(k);}voidalloc(iiita,intb)//分配内存算法{node*p,*q=L.after;usenode*m;p=search(b);if(p==NULL)leturn;m=(usenode*)nialloc(sizeof(usenode))^/生成一个被占用链表的结点，并插入到该链表的尾部m->add=p・>addess;m->size=b;m->num=a;m->next=n->next;n->next=m;n=m;〃保证n始终指向被占用链表的尾部，方便以后新生成结点的插入!f(p->size>b)〃如果申请空间的大小小于找到空闲空间的大小的处理{p->size=p->size-b;p->addiess=p->addiess+b;}else〃如果申请空间的人小等于找到空闲空间的人小的处理{p->before->aftei-p->after;if(p->after!=NULL)p->after->befbre=p->befbre;free(p);voidsort()〃对空闲链表进行排序{intmax;node*p,*q,*r,*s;nodea;p=L.after;wlule(p!=NULL)//让指针q指向链表的最后一个结点{q=p;p=p->after;}if(L.after->aftei—NULL)return;else{wlule(p!=q){s=r=p=L.after;max=r->size;wliile(s!=q->after)iif(s->size>max){max=s->size;尸s;s=s->after;}elses=s->after;}a.size=q->size;a.addiess=q->addiess;q->size=r->size;q->addiess=r->address;r->size=a.size;r->address=a.addiess;if(q->befdie->befoie==&L)return;elseq=q->before;voidPriiitQ{node*p=L.after;usenode*q=U.next;inti=l;pnntf(”\n空闲区域列表:\n”)；printfl^FREEIDaddresssizdn”)；wlule(p!=NULL){pnntf(M%-lOd*\p->addiess);printf(”％d\n”,p->size);p=p->after;i++;}if(q=NULL)return;else{pnntf(M\n己分配区域列表:\n”)；printf(HWORKLDaddresssize\nn);wlule(q!=NULL){pnntf(M%-lOd*\q->num);pnntf(M%-lOd*\q->add);p】iiitfC%d\iT：q->siz亡)；q=q->next;}}}voidfirstfit()〃首次适应算法inta,bj;IiutQ;PmitQ;wlule（l）{prmtf（n\iil.申请空间®”）；pnntf（”2、释放空间⑴”）;pnntf（”3、退出首次适应算法\n”）；pnntf（”请输入你的选择:”）；scanf（”％dt&i）;switch（i）{case1:{prmtf（"请输入申请空间的作业号:”）;scanfT%d・；&a）;prmtf（"请输入申请空间的人小:”）；scanfT%d・；&b）;alloc（a.b）;Prmt（）;break;}case2:{pnntf（“请输入释放空间的作业号:”）;scanf（”％d",&a）;请输入释放空间的人小:”）；scanf（”％d",&b）;recoveiy（a.b）;Prmt（）;break;}case3:priiitf（H\iiH）;return:}}}voidbestfitQ{inta,bj;IiutQ;PmitQ;wlule（l）{prmtf（n\iil.申请空间®”）；pnntf（”2、释放空间曲）;pnntf（”3、退出最佳适应算法\n”）；pnntf（”请输入你的选择:”）；switch（i）{case1:{请输入申请空间的作业号:”）;scanf（”％d",&a）;prmtf（"请输入申请空间的人小:”）；scanf（”％d",&b）;alloc（a.b）;sort（）;Prmt（）;break;}case2:{pnntf（“请输入释放空间的作业号:”）;scanf（”％d",&a）;prmtf（"请输入释放空间的人小:”）；scanf（”％d",&b）;recoveiy（a.b）;sort（）;Prmt（）;break;}case3:prmtf（H\iiH）;return:}}}voidniainQ{inti;wlule（l）{prmtfC'l、首次适应算法\11”）；pnntf（”2、最佳适应算法5”）；pnntfC3、退出\n”）；pnntf（”请输入你的选择:”）；scanftn%d*\&i）;switch(i)case1:fiistfit();bieak;case2:bestfit();break;case3:retuin;}}}扁§果①开始界面②首次适应算法«E:\C++程序设计噬便\Debug\动态分区分配方式的模拟exe1、首次适应算法2、最佳适应算法3、退出请输入你的选择：1空闲区域列表：FREEIDaddresssize1Q6401、申请空间2、释放空间3、退出首次适应算法请输入你的选择：③最佳适应算法«E:\C++程序设计噬便\Debug\动态分区分配方式的模拟exe1、首次适应算法2、最佳适应算法3、退出请输入你的选择：2空闲区域列表：FREEIDaddresssize1Q6401、申请空间2、释放空间3、退出最雀适应算法请输入你的选择：程序代一++语言实现

*********〃********〃************************************************************************〃********动态分区分配方式的模拟〃***************************************************************#iiiclude<iostreain.h>#iiiclude<stdlib.h>#defiiieFree0〃空闲状态#defiiieBusy1〃已用状态#defiiieOK1〃完成#defiiieERROR0〃出错#defiiieMAXJength640〃最人内存空间为640KBtvpedefintStatus;typedefstiuctfreearea//定义一个空闲区说明表结构{intID;〃分区号longsize;〃分区大小longaddress;〃分区地址intstate;〃状态}ElemTyp亡；//线性表的双向链表存储结构typedefstiuctDuLNode//doubleluikedlist{ElemTvpedata;structDuLNode*piior;//HU趋指针structDuLNode*next;〃后继指针}DuLNode,*DuLuikList;DuLinkListblock.first;〃头结点DuLinkListblock.last;//尾结点Statusalloc(iiit);//内存分配Statusfiee(mt);〃内存回收StatusFnst_fit(iiit.mt);//首次适应算法StatusBest_fit(int,int);//最佳适应算法voidshowQ;//查看分配StatusInitblock()y/开创空间表StatusInitblockQ//开创带头结点的内存空间链表{block_first=(DuLuikList)malloc(sizeof(DuLNode));block_last=(DuLiiikList)malloc(sizeof(DuLNode));block_first->piior=NULL;block_first->next=block_last;block_last->prioi-block_fiist;blockjast->next=NULL;block_last->data.addiess=0;block_last->data.size=MAX_length;block_last->data.ED=0;block_last->data.state=Fiee;returnOK;}//分配主存Statusalloc(iiitch){intIDdequest;cou«请输入作业(分区号)：”；cin»ID;cout«"请输入需要分配的主存人小(单位:KB)：”；cin»iequest;if(iequest<O||request==0){cout«H分配人小不合适，请重试！yvendl;returnERROR;}if(ch=2)//选择最佳适应算法{if(Best_fit(IDdequest)=OK)cout«"分配成功！”《endl;elsecout«M内存不足，分配失败！Yvendl;returnOK;}else//默认首次适应算法{if(FiisCfit(ID,iequest)==OK)cout«H分配成功！elsecout«M内存不足，分配失败！Yvendl;returnOK;}}//首次适应算法StatusFiist_fit(mtIDjntrequest)//传入作业名及申请量{〃为申请作业开辟新空间且初始化DuLnikListtemp=(DuLinkList)malloc(sizeof(DuLNode));tenip->data.ID=ID:tenip->data.size=request;tenip->data.state=Busy;DuLNode*p=block_fiist->next;while(p){if(p->data.state=Free&&p->data.size=request){//有大小恰好合适的空闲块p->data・state=Busy;p->data.ED=ID;returnOK;break:}if(p->data.state=Free&&p->data.size>request){//有空闲块能满足需求且有剩余”temp・>p】io尸p・>piioT；temp->next=p;temp->data.address=p->data.address;p->priof->next=temp;p->piioi-tenip;p->data.address=temp->data.addiess+temp->data.size;p->data.size-=request;returnOK;break:}p=p->next;}returnERROR;1丿//最佳适应算法StatusBest_fit(mtIDantrequest){intch;//记录最小剩余空间DuLuikListtemp=(DuLuikList)malloc(sizeof(DuLNode));tenip->data.ID=ID;tenip->data.size=request;tenip->data.state=Busy;DuLNode*p=block_fiist->next;DuLNode*q=NULL;〃记录最佳插入位置while(p)//初始化最小空间和最佳位置{if(p->data.state=Free&&(p->data.size>request||p->data.size==iequest))q=p;ch=p->data.size-request;break;}p=p->next;}while(p){if(p->data.state=Free&&p->data.size=request){//空闲块大小恰好合适p->data.ED=ID;p->data・state=Busy;returnOK;break:}if(p->data.state=Free&&p->data.size>request){//空闲块大于分配需求if(p->data.size-request<ch)//剩余空间比初值还小{ch=p->data.size-request;//更新剩余最小值q=p；〃更新最佳位置指向}}p=p->next;}if(q==NULL)returnERROR;//没有找到空闲块else{//找到了最佳位置并实现分配temp・>p】io尸q・>piioi;temp->next=q;temp->data.addiess=q->data.address;q->prioi->next=temp;q->prior=temp;q->data.addiess+=request;q->data.size=ch;returnOK;}}//主存回收StatusID){DuLNode*p=block_fiist;while(p)if(p->data.ID==ID){p->data・state=Free;p->data.LD=Fiee;if(p->priof->data.state==Free)//与前面的空闲块相连{p->priof->data.size+=p.size;p->piiof->next=p->next;p->next->prioi-p->prior;}if(p->next->data.state=Free)//4后面的空