动态分区分配方式的模拟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语言实现#includestdio.h#includestdlib.hstructnode//空闲分区链结点的定义{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&&ap-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-addressc-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-sizeb)//如果申请空间的大小小于找到空闲空间的大小的处理{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-sizemax){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;elseq=q-before;}}}voidPrint(){node*p=L.after;usenode*q=U.next;inti=1;printf(\n空闲区域列表:\n);printf(FREEIDaddresssize\n);while(p!=NULL){printf(%-10d,i);printf(%-10d,p-address);printf(%d\n,p-size);p=p-after;i++;}if(q==NULL)return;else{printf(\n已分配区域列表:\n);printf(WORKIDaddresssize\n);while(q!=NULL){printf(%-10d,q-num);printf(%-10d,q-add);printf(%d\n,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){case1:{printf(请输入申请空间的作业号:);scanf(%d,&a);printf(请输入申请空间的大小:);scanf(%d,&b);alloc(a,b);Print();break;}case2:{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){case1:{printf(请输入申请空间的作业号:);scanf(%d,&a);printf(请输入申请空间的大小:);scanf(%d,&b);alloc(a,b);sort();Print();break;}case2:{printf(请输入释放空间的作业号:);scanf(%d,&a);printf(请输入释放空间的大小:);scanf(%d,&b);recovery(a,b);sort();Print();break;}case3:printf(\n);return;}}}voidmain(){inti;while(1){printf(1、首次适应算法\n);printf(2、最佳适应算法\n);printf(3、退出\n);printf(请输入你的选择:);scanf(%d,&i);switch(i){case1:firstfit();break;case2:bestfit();break;case3:return;}}}运行结果①开始界面②首次适应算法③最佳适应算法程序代码——C++语言实现//***************************************************************//********动态分区分配方式的模拟*********//***************************************************************#includeiostream.h#includestdlib.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));bl