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

《动态分区分配方式的模拟C语言代码和C++代码.docx》由会员分享，可在线阅读，更多相关《动态分区分配方式的模拟C语言代码和C++代码.docx（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验三 使用动态分区分配方式的模拟1、实验目的了解动态分区分配方式中使用的数据构造与分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。2、实验内容(1) 用C语言分别实现采用首次适应算法与最正确适应算法的动态分区分配过程alloc( )与回收过程free( )。其中，空闲分区通过空闲分区链来管理：在进展内存分配时，系统优先使用空闲区低端的空间。(2) 假设初始状态下，可用的内存空间为640KB，并有以下的请求序列：作业1申请130KB。作业2申请60KB。作业3申请100KB。作业2释放60KB。作业4申请200KB。作业3释放100KB。作业1释放130KB。作业5申请140K

2、B。作业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 *)mallo

3、c(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;

4、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;else

5、r=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-b

6、efore=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-befo

7、re=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)

8、 /如果申请空间的大小小于找到空闲空间的大小的处理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) r

9、eturn;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.

10、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

11、-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(请输入释放空间的

12、作业号:); 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);

13、 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); prin

14、tf(请输入你的选择:); 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;typede

15、f 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;/尾结点Stat

16、us 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;b

17、lock_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

18、;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

19、-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;re

20、turn 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.sta

21、te=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;/更新剩余

22、最小值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-da

23、ta.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;cou

24、t+主 存 分 配 情 况+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;第 22 页