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

实验三 使用动态分区分配方式的模拟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 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 && a>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("没有找到这样的作业!");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->address>c->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->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; 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<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;第 22 页