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

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

2、。作业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 *next;int num;int add;int size;U,*n;void Init() /空闲分

3、区链的初始化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 && a

4、>p->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("没有找到这样的作业!"

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

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

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

8、fore->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

9、;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() /对空闲链表进行排序

10、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; else s=s->after; a.size=q->size; a.addre

11、ss=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");

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("WORKID address sizen");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();

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

16、f("%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; c

17、ase 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; 运行结果 开始界面 首次适

18、应算法 最佳适应算法程序代码C+语言实现/*/*             动态分区分配方式的模拟          */* #include<iostream.h>#include<stdlib.h> #define Free 0 /空闲状态#define Busy 1 /已用状态#define OK 1 

19、0;  /完成#define ERROR 0 /出错#define MAX_length 640 /最大内存空间为640KBtypedef int Status; typedef struct freearea/定义一个空闲区说明表结构    int ID;   /分区号    long size;   /分区大小    long address; /分区地址  &#

20、160; int state;   /状态ElemType; /-  线性表的双向链表存储结构  -typedef struct DuLNode /double linked list    ElemType data;    struct DuLNode *prior; /前趋指针    struct DuLNode *next;  /后继指针DuLNode,*Du

21、LinkList; 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()/开创带头结点的内存空间链表   

22、60;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;  

23、0; 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; /- 分

24、 配 主 存 -Status alloc(int ch)    int ID,request;    cout<<"请输入作业(分区号)："    cin>>ID;    cout<<"请输入需要分配的主存大小(单位:KB)："    cin>>request;   &#

25、160;if(request<0 |request=0)            cout<<"分配大小不合适，请重试！"<<endl;        return ERROR;         if(ch=2) /选择最佳适应算法  

26、60;         if(Best_fit(ID,request)=OK) cout<<"分配成功！"<<endl;        else cout<<"内存不足，分配失败！"<<endl;        return OK;  

27、60;     else /默认首次适应算法            if(First_fit(ID,request)=OK) cout<<"分配成功！"<<endl;        else cout<<"内存不足，分配失败！"<<endl; 

28、0;      return OK;    /- 首次适应算法 -Status First_fit(int ID,int request)/传入作业名及申请量    /为申请作业开辟新空间且初始化    DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode);    temp->data.ID=ID;

29、60;   temp->data.size=request;    temp->data.state=Busy;     DuLNode *p=block_first->next;    while(p)            if(p->data.state=Free && p

30、->data.size=request)        /有大小恰好合适的空闲块            p->data.state=Busy;            p->data.ID=ID;     

31、0;      return OK;            break;                if(p->data.state=Free && p->data.size>request)  

32、60;     /有空闲块能满足需求且有剩余"            temp->prior=p->prior;            temp->next=p;          

33、       temp->data.address=p->data.address;            p->prior->next=temp;            p->prior=temp;     

34、       p->data.address=temp->data.address+temp->data.size;            p->data.size-=request;            return OK;   &

35、#160;        break;                p=p->next;        return ERROR;/-  最佳适应算法  -Status Best_fit(int ID,int request)

36、60;   int ch; /记录最小剩余空间    DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode);    temp->data.ID=ID;    temp->data.size=request;    temp->data.state=Busy;    DuLNode *p=block_fi

37、rst->next;    DuLNode *q=NULL; /记录最佳插入位置    while(p) /初始化最小空间和最佳位置            if(p->data.state=Free &&            (p->data.

38、size>request | p->data.size=request) )                    q=p;            ch=p->data.size-request;     

39、60;      break;                p=p->next;        while(p)            if(p->data.stat

40、e=Free && p->data.size=request)        /空闲块大小恰好合适            p->data.ID=ID;            p->data.state=Busy;   

41、;         return OK;            break;                if(p->data.state=Free && p->data.size>reques

42、t)        /空闲块大于分配需求            if(p->data.size-request<ch)/剩余空间比初值还小                     

43、;       ch=p->data.size-request;/更新剩余最小值                q=p;/更新最佳位置指向                   

44、;         p=p->next;        if(q=NULL) return ERROR;/没有找到空闲块    else    /找到了最佳位置并实现分配        temp->prior=q->prior;  

45、      temp->next=q;        temp->data.address=q->data.address;        q->prior->next=temp;        q->prior=temp;   &#

46、160;    q->data.address+=request;        q->data.size=ch;        return OK;     /-   主 存 回 收   -Status free(int ID)    

47、DuLNode *p=block_first;    while(p)            if(p->data.ID=ID)                    p->data.state=Free;  

48、;          p->data.ID=Free;            if(p->prior->data.state=Free)/与前面的空闲块相连                 &

49、#160;          p->prior->data.size+=p->data.size;                p->prior->next=p->next;          

50、0;     p->next->prior=p->prior;                        if(p->next->data.state=Free)/与后面的空闲块相连        

51、;                    p->data.size+=p->next->data.size;                p->next->next->prior=p; 

52、60;              p->next=p->next->next;                              &#

53、160;          break;                 p=p->next;        return OK; /-  显示主存分配情况 -void show()  

54、;  cout<<"+n"    cout<<"+        主 存 分 配 情 况        +n"    cout<<"+n"    DuLNode *p=block_first->ne

55、xt;    while(p)            cout<<"分 区 号："        if(p->data.ID=Free) cout<<"Free"<<endl;        els

56、e cout<<p->data.ID<<endl;        cout<<"起始地址："<<p->data.address<<endl;        cout<<"分区大小："<<p->data.size<<" KB"<<endl; &#

57、160;      cout<<"状    态："        if(p->data.state=Free) cout<<"空  闲"<<endl;        else cout<<"已分配"<

58、<endl;        cout<<""<<endl;        p=p->next;     /- 主  函  数-void main()    int ch;/算法选择标记    cout&l

59、t;<"       动态分区分配方式的模拟       n"    cout<<"*n"    cout<<"* 1)首次适应算法  2)最佳适应算法 *n"    cout<<"*n"    cout<<"请选择分配算法："    cin>>ch;    Initblock(); /开创空间表    int choice;  /操作