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

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

2、 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 usenodeusenode *

3、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(" 没有空闲的区域!&q

4、uot;);p=NULL;return p;elsewhile(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=

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

6、;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=

7、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;elser=L.after;while(r!=NULL)if(r->address>c->address)c->after=r;c-&g

8、t;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

9、=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);

10、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;elsewhile(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

11、;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("FREEIDaddresssizen");

12、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("WORKIDaddresssizen");while(q!=NULL)printf("%-10d",q->num);printf("%-10d"

13、,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(" 请输

14、入申请空间的作业号:");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

15、: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"

16、,&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");r

17、eturn;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+语言实现/*/*动态分区分配方式的模拟*

18、/*#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;/-线性表的双向

19、链表存储结构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)

20、; / 最佳适应算法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;blo

21、ck_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<<" 请输入需要分配的主存大小cin>>request;if(request<0 |request=

22、0)(单位 :KB) ： "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<<"分配成功！

23、 "<<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-&

24、gt;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->d

25、ata.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-

26、>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(

27、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->n

28、ext;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-

29、>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-&

30、gt;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<<" 起始地址： "<&