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

实验三 使用动态分区分配方式的模拟1、 实验目的了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。2、 实验容用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc()和回收过程fiee()o其中，空闲分区通过空闲分区链来管理：在进行存分配时，系统优先使用空闲区低端的空间。假设初始状态下，可用的存空间为640KB,并有下列的请求序列：•作业1申请130KB。•作业2申请60KBo•作业3申请100KB。•作业2释放60KBo•作业4申请200KBo•作业3释放lOOKBo•作业1释放130KBo•作业5申请140KB。•作业6申请60KBo•作业7申请50KBo•作业6释放60KB。请分别采用首次适应算法和最佳适应算法，对存块进行分配和回收，要求每次分配和回收后显示出空闲分区链的情况。程序代一~C语言实现#iiiclude<stdio.h>#iiiclude<stdlib.h>stiuctnode 〃空闲分区链结点的定义(node*befbre;node*after;intsize;intaddress;intstate;｝；nodeL;structusenode(usenode*next;intnum;intadd;intsize;voidImt() 〃空闲分区链的初始化(node*p;p=(node*)malloc(sizeof(node));p->befbre=&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*search(iiita)(node*p=L.after;if(p=NULL){pnntf(”没有空闲的区域!”)；p=NULL;returnp;}else{wliile(p!=NULL&&a>p->size)p=p->after;if(p—NULL){pnntf(”没有找到合适的空闲空fuj!”);p=NULL;returnp;}elsereturnp;}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)pnntf(”没有找到这样的作业!)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;}elser=r->after;}if(r==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-i->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-re->size;fiee(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->befbre=c;fiee(k);return;}else1=1->after;}}}fiee(k);voidalloc(iiita,intb)//分配存算法(node*p,*q=L.after;usenode*m;p=search(b);iftp==NULL)return;m=(usenode*)malloc(sizeof(usenode))J/生成一个被占用链表的结点，并插入到该链表的尾部m->add=p->address;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->address=p->addiess-rb;}else 〃如果申请空间的大小等于找到空闲空间的大小的处理{p->befbre->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->after=NULL)return;else{wlule(p!=q){s=r=p=L.after;max=r->size;wliile(s!=q->after)fif(s->size>max)(max=s->size;r=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->addiess=a.address;if(q->befbie->befdre==&L)return;elseq=q->befbre;voidPriiitQ(node*p=L.after;usenode*q=U.next;inti=l;pnntf(”\n空闲区域列表:\n”)；printfV'FREEIDaddresssize\nM);wlule(p!=NULL){pnntf(”％.10d”,i);printf(M%-1Od*\p->addiess);printR"%d\n”,p・>size);p=p->after;1++;}if(q=NULL)return;else{pnntf(M\n己分配区域列表:\n”)；printfV'WORKEDaddresssizeW);wlule(q!=NULL){printf(M%-1Od*\q->num);pnntf(M%-lOd*\q->add);pnntf(M%d'n,\q->size);q=q->next;}}1voidfirstfit() 〃首次适应算法inta,b,i;ImtQ;PrmtO;wlule(l){prmtf(H\iil.申请空间山”)；pnntf("2、释放空间"”);pnntf(”3、退出首次适应算法\n”)；pnntf(”请输入你的选择:”)；scanf(”％d”,&i);switch(i)(case1:(pimtfC请输入申请空间的作业号:”);scanff'%d”,&a);prmtf("请输入申请空间的大小:”)；scaiW'%d”,&b);alloc(a,b);Pnnt();break;}case2:(prmtfC'请输入释放空间的作业号;scanf(”％d",&a);pnntf(”请输入释放空间的大小:”)；scanf(”％d",&b);recoveiy(a.b);Pnnt();break;}case3:}}}voidbestfitQ(inta,b,i;ImtQ;PrmtO;wlule(l){prmtf(H\iil.申请空间山”)；pnntf("2、释放空间瑚);pnntf(”3、退出最佳适应算法\n”)；pnntf(”请输入你的选择:”)；scanf(”％d”,&i);switch(i)(case1:(pruitfC请输入申请空间的作业号：，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:)}voidmain。(inti;wlule(l)(printfC'1、首次适应算法\11”)；printf("2、最佳适应算法寸)；pnntf(”3、退出\n”)；pnntf(”请输入你的选择：，scanff%d”,&i);switch(i){case1:fustfit();break;case2:bestfit();break;case3:return;}蠢尚果①开始界面②首次适应算法bE:\Ci程序设计、随便\Debug\动态分区分配方式的模拟exe1、 首次适应算法2、 最佳适应算法3、 退出请输入你的选择：1空闲区域列表：FREEID address size1 Q 6401、 申请空间2、 释放空间3、 退出首次适应算法请输入你的选择：③最佳适应算法bE:\Ci程序设计、随便\Debug\动态分区分配方式的模拟exe1、 首次适应算法2、 最佳适应算法3、 退出请输入你的选择：2空闲区域列表：FREEID addresssize1 Q 6401、 申请空间2、 释放空间3、 退出最枝适应算法请输入你的选择：L程序代_i语言实现俨*******动态分区分配方式的模拟*********#iiiclude<iostreain.h>#iiiclude<stdlib.h>#defiiieFree0//空闲状态#defiiieBusy1〃已用状态#defiiieOK1//完成#defiiieERROR0〃出错#defiiieMAXJength640〃最大存空间为640KBtypedefintStatus;typedefstiuctfreearea//定义一个空闲区说明表结构(intID;〃分区号longsize;〃分区大小longaddress;〃分区地址intstate;〃状态}ElemType;// 线性表的双向链表存储结构 typedefstiuctDuLNode//doubleluikedlist(ElemTypedata;structDuLNode*piior;〃前趋指针stiuctDuLNode*next;〃后继指针)DuLNode,*DuLuikList;DuLinkListblock_fkst;〃头结点DuLinkListblockjast;〃尾结点Statusalloc(iiit);//存分配Statusfiee(mt);〃存回收Status 首次适应算法StatusBest_fit(mt.mt);//最佳适应算法voidshow。;〃查看分配StatusInitblockOy/开创空间表StatusInitblockQ//开创带头结点的存空间链表block_first=(DuLuikList)malloc(sizeof(DuLNode));block_last=(DuLnikList)malloc(sizeof(DuLNode));block_first->piioi=NULL;block_first->next=block_last;block_last->prioi-block_fiist;biock_last->next=NULL;block_last->data.addiess=0;block_last->data.size=MAX_length;block_last->data.ED=0;block_last->data.state=Free;returnOK;i// 分配主存 Statusalloc(iiitch)(intIDdequest;coutvv”请输入作业(分区号)：”；cin»ID;cout«"请输入需要分配的主存大小(单位:KB)：”；cin»iequest;if(request<O||iequest==0)(cout«H分配大小不合适，请重试！“vvendl;returnERROR;if(ch==2)〃选择最佳适应算法(if(Best_fit(ID,fequest)=OK)cout«"分配成功！M«endl;elsecout«H存不足，分配失败！H«endl;returnOK;else//^认首次适应算法(if(First_fit(ID,request)=OK)cout«"分配成功!M«endl;elsecout«H存不足，分配失败！H«endl;returnOK;i1j// 首次适应算法 Status IDantrequest)//传入作业名及申请量〃为申请作业开辟新空间且初始化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.ID=ID;returnOK;break;if(p->data.state=Free&&p->data.size>request){〃有空闲块能满足需求且有剩余”temp->prioi-p->prior;temp->next=p;temp->data.address=p->data.address;p->prior->next=temp;p->pnoi-tenip;p->data.address=temp->data.addiess+temp->data.size;p->data.size-=request;returnOK;break;p=p->next;returnERROR;1)// 最佳适应算法 StatusBesCfit(iiitIDantrequest)(intch;〃记录最小剩余空间DuLuikListtemp=(DuLinkList)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==request))q=p;ch=p->data.size-request;break;p=p->next;while(p)(if(p->data.state=Free&&p->data.size=request){//空闲块大小恰好合适p->data.ID=ID;p->data.state=Busy；returnOK;break:if(p->data.state=Free&&p->data.size>request){//空闲块大于分配需求if(p->data.size-iequest<ch)//剩余空间比初值还小(ch=p->data.size-request;//更新剩余最小值q=p；〃更新最佳位置指向p=p->next;if(q==NULL)returnERROR;//没有找到空闲块else{〃找到了最佳位置并实现分配temp->prioi-q->prior;temp->next=q;temp->data.addiess=q->data.address;q->prior->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.ID=Fiee;if(p->piior->data.state==Free)//与前面的空闲块相连(p->piior->data.size+=p->data.size;p->pnor->next=p->next;p->next->prioi-p->prioi;if(p->next->data.state=Free)//与后面的空闲块相连(p->data.size-r=p->next->data.size;p->next->next->prioi=p;p->next=p->next->next;break;p=p->next;returnOK;// 显示主存分配情况 voidshowQ(cout«"+++主存分配情况+++\n”；coutvv”+++++++++++++++++++++++++++++++++++++++\n”；DuLNode