实验三使用动态分区分配方式的模拟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>struct node //空闲分区链结点的定义{node *before;node *after;int size;int address;int state;};node L;struct usenode{usenode *next;int num;int add;int size;}U,*n;void Init() //空闲分区链的初始化{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(int a){node *p=L.after;if(p==NULL){printf("没有空闲的区域!");p=NULL;return p;}else{while(p!=NULL && a>p->size)p=p->after;if(p==NULL){printf("没有找到合适的空闲空间!");p=NULL;return p;}elsereturn p;}}void recovery(int a,int b) //内存回收算法{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);}void alloc(int a ,int b) //分配内存算法{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);}}void sort() //对空闲链表进行排序{int max;node *p,*q,*r,*s;node a;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;elseq=q->before;}}}void Print(){node *p=L.after;usenode *q=U.next;int i=1;printf("\n空闲区域列表:\n");printf("FREEID address size\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("WORKID address size\n");while(q!=NULL){printf("%-10d",q->num);printf("%-10d",q->add);printf("%d\n",q->size);q=q->next;}}}void firstfit() //首次适应算法{int a,b,i;Init();Print();while(1){printf("\n1、申请空间\n");printf("2、释放空间\n");printf("3、退出首次适应算法\n");printf("请输入你的选择:");scanf("%d",&i);switch(i){case 1:{printf("请输入申请空间的作业号:");scanf("%d",&a);printf("请输入申请空间的大小:");scanf("%d",&b);alloc(a,b);Print();break;}case 2:{printf("请输入释放空间的作业号:");scanf("%d",&a);printf("请输入释放空间的大小:");scanf("%d",&b);recovery(a,b);Print();break;}case 3:printf("\n");return;}}}void bestfit(){int a,b,i;Init();Print();while(1){printf("\n1、申请空间\n");printf("2、释放空间\n");printf("3、退出最佳适应算法\n");printf("请输入你的选择:");scanf("%d",&i);switch(i){case 1:{printf("请输入申请空间的作业号:");scanf("%d",&a);printf("请输入申请空间的大小:");scanf("%d",&b);alloc(a,b);sort();Print();break;}case 2:{printf("请输入释放空间的作业号:");scanf("%d",&a);printf("请输入释放空间的大小:");scanf("%d",&b);recovery(a,b);sort();Print();break;}case 3:printf("\n");return;}}}void main(){int i;while(1){printf("1、首次适应算法\n");printf("2、最佳适应算法\n");printf("3、退出\n");printf("请输入你的选择:");scanf("%d",&i);switch(i){case 1:firstfit();break;case 2:bestfit();break;case 3:return;}}}运行结果①开始界面②首次适应算法③最佳适应算法程序代码——C++语言实现//*************************************************************** //******** 动态分区分配方式的模拟 *********//***************************************************************#include<iostream.h>#include<stdlib.h>#define Free 0 //空闲状态#define Busy 1 //已用状态#define OK 1 //完成#define ERROR 0 //出错#define MAX_length 640 //最大内存空间为640KBtypedef int Status;typedef struct freearea//定义一个空闲区说明表结构{int ID; //分区号long size; //分区大小long address; //分区地址int state; //状态}ElemType;//---------- 线性表的双向链表存储结构 ------------typedef struct DuLNode //double linked list{ElemType data;struct DuLNode *prior; //前趋指针struct DuLNode *next; //后继指针}DuLNode,*DuLinkList;DuLinkList block_first; //头结点DuLinkList block_last; //尾结点Status alloc(int);//内存分配Status free(int); //内存回收Status First_fit(int,int);//首次适应算法Status Best_fit(int,int); //最佳适应算法void show();//查看分配Status Initblock();//开创空间表Status Initblock()//开创带头结点的内存空间链表{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;return OK;}//----------------------- 分配主存 ------------------------- Status alloc(int ch){int ID,request;cout<<"请输入作业(分区号)：";cin>>ID;cout<<"请输入需要分配的主存大小(单位:KB)：";cin>>request;if(request<0 ||request==0){cout<<"分配大小不合适，请重试！"<<endl;return ERROR;}if(ch==2) //选择最佳适应算法{if(Best_fit(ID,request)==OK) cout<<"分配成功！"<<endl; else cout<<"内存不足，分配失败！"<<endl;return OK;}else //默认首次适应算法{if(First_fit(ID,request)==OK) cout<<"分配成功！"<<endl; else cout<<"内存不足，分配失败！"<<endl;return OK;}}//------------------ 首次适应算法 -----------------------Status First_fit(int ID,int request)//传入作业名及申请量{//为申请作业开辟新空间且初始化DuLinkList temp=(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;return OK;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;return OK;break;}p=p->next;}return ERROR;}//-------------------- 最佳适应算法 ------------------------ Status Best_fit(int ID,int request){int ch; //记录最小剩余空间DuLinkList temp=(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;return OK;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) return ERROR;//没有找到空闲块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;return OK;}}//----------------------- 主存回收 --------------------Status free(int ID){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;}return OK;}//--------------- 显示主存分配情况 ------------------void show(){cout<<"+++++++++++++++++++++++++++++++++++++++\n"; cout<<"+++ 主存分配情况 +++\n";cout<<"+++++++++++++++++++++++++++++++++++++++\n"; DuLNode *p=block_first->next;while(p){cout<<"分区号：";if(p->data.ID==Free) cout<<"Free"<<endl;else cout<<p->data.ID<<endl;cout<<"起始地址："<<p->data.address<<endl;cout<<"分区大小："<<p->data.size<<" KB"<<endl;cout<<"状态：";if(p->data.state==Free) cout<<"空闲"<<endl;else cout<<"已分配"<<endl;cout<<"——————————————"<<endl;p=p->next;}}//----------------------- 主函数---------------------------void main(){int ch;//算法选择标记cout<<" 动态分区分配方式的模拟 \n";cout<<"************************************\n";cout<<"** 1)首次适应算法 2)最佳适应算法 **\n";cout<<"************************************\n";cout<<"请选择分配算法：";cin>>ch;Initblock(); //开创空间表int choice; //操作选择标记while(1){cout<<"********************************************\n"; cout<<"** 1: 分配内存 2: 回收内存 **\n";cout<<"** 3: 查看分配 0: 退出 **\n";cout<<"********************************************\n"; cout<<"请输入您的操作：";cin>>choice;if(choice==1) alloc(ch); // 分配内存else if(choice==2) // 内存回收{int ID;cout<<"请输入您要释放的分区号：";cin>>ID;free(ID);}else if(choice==3) show();//显示主存else if(choice==0) break; //退出else //输入操作有误{cout<<"输入有误，请重试！"<<endl; continue;}}}。