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

实验三使用动态分区分配方式的模拟1、实验目的了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。2、实验内容(1)用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过空闲分区链来管理：在进行内存分配时，系统优先使用空闲区低端的空间。(2)假设初始状态下，可用的内存空间为640KB,并有下列的请求序列：作业1申请130KB。作业2申请60KB。作业3申请100KB。作业2释放60KB。作业4申请200KB。作业3释放100KB。作业1释放130KB。作业5申请140KB。作业6申请60KB。作业7申请50KB。作业6释放60KB。请分别采用首次适应算法和最佳适应算法，对内存块进行分配和回收，要求每次分配和回收后显示出空闲分区链的情况。专业.专注程序代码一C语言实#include<stdio.h>#include<stdlib.h>structnode 〃空闲分区链结点的定义(node*before;node*after;intsize;intaddress;intstate;);nodeL;structusenode(usenode*next;intnum;intadd;intsize;}U,*n;专业.专注voidInit() 〃空闲分区链的初始化(node*p;p二(node*)malloc(sizeof(node));p->before=&L;p->after=NULL;p->size=640;p->address=0;p->state=0;L.after=p;L.before=NULL;L.size=0;U.next=NULL;n=&U;)node*search(inta)(node*p=L.after;if(p二二NULL)(printf("没有空闲的区域厂)；专业.专注p=NULL;returnp;)else(while(p!=NULL&&a>p->size)p=p->after;if(p二二NULL)(printf("没有找到合适的空闲空间厂);p=NULL;returnp;)elsereturnp;))voidrecovery(inta,intb) 〃内存回收算法(node*c,*s,*r=L.after;专业.专注node*d=L.after,*e;usenode*k=U.next,*h=&U;while(k!=NULL&&a!=k->num)(h=k;k=k->next;)if(k二二NULL)printf("没有找到这样的作业厂)；else(h->next=k->next;if(h->next=二NULL)n=h;)while(r!=NULL) //若回收得到的空闲块的前方有空闲块合并此空闲块(if(k->add==r->address+r->size)(r->size=r->size+k->size;专业.专注break;)elser=r->after;)if(r二二NULL) 〃若回收得到的空闲块的后面有空闲块合并此空闲块(r=L.after;while(r!=NULL)(if(k->add+k->size==r->address)(r->address=k->add;r->size=r->size+k->size;break;)elser=r->after;)专业.专注while(d!=NULL) 〃保证空闲链表中没有相邻的空闲空间(if(d->after!=NULL)e=d->after;elsebreak;if(d->address+d->size==e->address)(d->after=e->after;while(e->after!=NULL)e->after->before=d;d->size=d->size+e->size;free(e);break;elsed=d->after;专业.专注if(r二二NULL)(r=L.after;c二(node*)malloc(sizeof(node));c->size=b;c->address=k->add;if(L.after二二NULL)(c->after=L.after;c->before=&L;L.after=c;)else(r=L.after;while(r!=NULL)(if(r->address>c->address)(c->after=r;c->before=r->before;专业.专注r->before->after=c;r->before=c;free(k);return;)elser=r->after;)))free(k);)voidalloc(inta,intb)〃分配内存算法(node*p,*q=L.after;usenode*m;p=search(b);if(p二二NULL)return;m=(usenode*)malloc(sizeof(usenode));〃生成一个被占用链表的结点并插入到该链表的尾部专业.专注m->add=p->address;m->size=b;m->num=a;m->next=n->next;n->next=m;n=m; 〃保证n始终指向被占用链表的尾部，方便以后新生成结点的插入if(p->size>b)〃如果申请空间的大小小于找到空闲空间的大小的处理(p->size=p->size-b;p->address=p->address+b;)else 〃如果申请空间的大小等于找到空闲空间的大小的处理(p->before->after=p->after;if(p->after!=NULL)p->after->before=p->before;free(p);))专业.专注voidsort()〃对空闲链表进行排序(intmax;node*p,*q,*r,*s;nodea;p=L.after;while(p!=NULL) 〃让指针q指向链表的最后一个结点(q=p;p=p->after;)if(L.after->after二二NULL)return;else(while(p!=q)(s=r=p=L.after;max=r->size;专业.专注while(s!=q->after)(if(s->size>max)(max=s->size;r=s;s=s->after;)elses=s->after;)a.size=q->size;a.address=q->address;q->size=r->size;q->address=r->address;r->size=a.size;r->address=a.address;if(q->before->before=二&L)return;else专业.专注q=q->before;voidPrint()(node*p=L.after;usenode*q=U.next;inti=1;printf("\n空闲区域列表:\n");printf("FREEIDaddresssizeWn");while(p!=NULL)(printf("%-10d",i);printf("%-10d",p->address);printf("%dWn",p->size);p=p->after;专业.专注i++；if(q二二NULL)return;else(printf("\n已分配区域列表:\n");printf("WORKIDaddresssizeWn");while(q!=NULL)(printf("%-10d",q->num);printf("%-10d",q->add);printf("%dWn",q->size);q=q->next;)))voidfirstfit() 〃首次适应算法(inta,b,i;专业.专注Init();Print();while(1){printf("\n1、申请空间\n");printf("2、释放空间\n");printf("3、退出首次适应算法\n");printf("请输入你的选择:")；scanf("%d",&i);switch(i){{printf("请输入申请空间的作业号:");scanf("%d",&a);printf("请输入申请空间的大小:")；scanf("%d",&b);alloc(a,b);Print();break;){专业.专注printf("请输入释放空间的作业号:");scanf("%d",&a);printf("请输入释放空间的大小:")；scanf("%d",&b);recovery(a,b);Print();break;)case3:printf("\n");return;)))voidbestfit()(inta,b,i;Init();Print();while(1){printf("\n1、申请空间\n");printf("2、释放空间\n");专业.专注printf("3、退出最佳适应算法\n");printf("请输入你的选择:")；scanf("%d",&i);switch(i)((printf("请输入申请空间的作业号:");scanf("%d",&a);printf("请输入申请空间的大小:")；scanf("%d",&b);alloc(a,b);sort();Print();break;)(printf("请输入释放空间的作业号:");scanf("%d",&a);printf("请输入释放空间的大小:")；scanf("%d",&b);专业.专注recovery(a,b);sort();Print();break;)case3:printf("\n");return;)))voidmain()(inti;while(1)(printf("1、首次适应算法Wn");printf("2、最佳适应算法Wn");printf("3、退出Wn");printf("请输入你的选择:")；scanf("%d",&i);switch(i)专业.专注(case1:firstfit();break;case2:bestfit();break;case3:return;)))运行结果①开始界面・EM++程序设计雁便2时”1莉态分区分配方式的模拟f 0回—1,首次适应算法2、最佳适应篁法3、退出请输入你的选择:I彳I 肝 I .②首次适应算法专业.专注

③最佳适应算法・EM++程序谩计雁便\DeMg恸态分区分配方式的模拟e烬 口回，首次适应算法2、最佳适应算法3,退出请输入你的选择：2空闲区域列表：FREEIO address size1 0 6401、申请空间2、释放空间3、退出最佳适应算法请输入你的选择：专业.专注程序代码C++语言实/尸*************************************************************//********动态分区分配方式的模拟*********//********动态分区分配方式的模拟*********/尸*************************************************************#include<iostream.h>#include<stdlib.h>defineFree0〃空闲状态defineBusy1〃已用状态defineOK1 //完成defineERROR0〃出错defineMAX_length640//最大内存空间为640KBtypedefintStatus;typedefstructfreearea/淀义一个空闲区说明表结构(intID;〃分区号longsize;//分区大小longaddress;//分区地址intstate;//状态}ElemType;专业.专注

//线性表的双向链表存储结构//线性表的双向链表存储结构typedefstructDuLNode//doublelinkedlist(ElemTypedata;structDuLNode*prior;〃前趋指针structDuLNode*next;//后继指针}DuLNode,*DuLinkList;DuLinkListblock_first;//头结点DuLinkListblock_last;//尾结点Statusalloc(int);//内存分配Statusfree(int);〃内存回收StatusFirst_fit(int,int);//首次适应算法StatusBest_fit(int,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.ID=0;block_last->data.state=Free;returnOK;)// 分配主存 Statusalloc(intch)(intID,request;cout<<"请输入作业(分区号)：";cin>>ID;cout<<"请输入需要分配的主存大小(单位:KB)：";cin>>request;if(request<0||request==0)(专业.专注cout<<"分配大小不合适,请重试！"<<endl;returnERROR;)if(ch==2)〃选择最佳适应算法(if(Best_fit(ID,request)==OK)8口卜<"分配成功！"<<endl;elsecout<<"内存不足，分配失败！"<<endl;returnOK;)else〃默认首次适应算法(if(First_fit(ID,request)==OK)8a<<"分配成功！"<<endl;elsecout<<"内存不足，分配失败！"<<endl;returnOK;))// 首次适应算法 StatusFirst_fit(intID,int©4口0$1)//传入作业名及申请量(〃为申请作业开辟新空间且初始化DuLinkListtemp=(DuLinkList)malloc(sizeof(DuLNode));专业.专注temp->data.ID=ID;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;p->data.ID=ID;returnOK;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;returnOK;break;)p=p->next;)returnERROR;)// 最佳适应算法 StatusBest_fit(intID,intrequest)(intch;〃记录最小剩余空间DuLinkListtemp=(DuLinkList)malloc(sizeof(DuLNode));temp->data.ID=ID;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||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-request<ch)〃剩余空间比初值还小{ch=p->data.size-request;〃更新剩余最小值q=p;〃更新最佳位置指向专业.专注p=p->next;)if(q==NULL)returnERROR;〃没有找到空闲块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;))// 主存回收 Statusfree(intID){DuLNode*p=block_first;专业.专注while(p)(if(p->data.ID==ID)(p->data.state=Free;p->data.ID=Free;if(p->prior->data.state二二Free)//与前面的空闲块相连(p->prior->data.size+=p->data.size;p->prior->next=p->next;p->next->prior=p->prior;)if(p->next->data.state二二Free)//与后面的空闲块相连(p->data.size+=p->next->data.size;p->next->next->prior=p;p->next=p->next->next;)break;)p=p->next;)专业.专注returnOK;)// 显示主存分配情况 voidshow()(cout<<"+++++++++++++++++++++++++++++++++++++++\n";cout<<"+++主存分配情况+++\n";cout<<"+++++++++++++++++++++++++++++++++++++++\n";DuLNode*p=block_first->next;while(p)(8仇<<"分区号：”；