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

实验三 使用动态分区分配方式的模拟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#includestruct node /空闲分区链结点的定义node *before;node *after;int size;int address;int state;node L;struct usenodeusenode *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;elsewhile(p!=NULL & ap-size)p=p-after;if(p=NULL)printf(没有找到合适的空闲空间!);p=NULL;return p;else return 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(没有找到这样的作业!);elseh-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;else r=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; else r=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-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);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-sizemax) max=s-size; r=s; s=s-after; else s=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; void Print()node *p=L.after;usenode *q=U.next;int i=1;printf(n空闲区域列表:n);printf(FREEID address sizen);while(p!=NULL)printf(%-10d,i);printf(%-10d,p-address);printf(%dn,p-size);p=p-after;i+;if(q=NULL)return;elseprintf(n已分配区域列表:n);printf(WORKID address sizen);while(q!=NULL)printf(%-10d,q-num);printf(%-10d,q-add);printf(%dn,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#include#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 listElemType 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;coutID;coutrequest;if(request0 |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内存不足，分配失败！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.sizerequest)/有空闲块能满足需求且有剩余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.sizerequest | 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.sizerequest)/空闲块大于分配需求if(p-data.size-requestdata.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;coutnext;while(p)coutdata.ID=Free) coutFreeendl;else coutdata.IDendl;cout起始地址：data.addressendl;cout分区大小：data.size KBendl;coutdata.state=Free) cout空闲endl;else cout已分配endl;coutnext;/-主函数-void main()int ch;/算法选择标记cout动态分区分配方式的模拟n;cout*n;cout* 1)首次适应算法2)最佳适应算法*n;cout*n;coutch;Initblock(); /开创空间表int choice;/操作选择标记while(1)cout*n;cout*1:分配内存2:回收内存*n;cout*3:查看分配0:退出*n;cout*n;coutchoice;if(choice=1) alloc(ch); /分配内存else if(choice=2)/内存回收int ID;coutID;free(ID);else if(choice=3) show();/显示主存else if(choice=0) break; /退出else /输入操作有误cout输入有误，请重试！endl;continue;