動態(tài)分區(qū)分配方式的模擬C語言代碼和C++代碼

實驗三使用動態(tài)分區(qū)分配方式的模擬1、實驗?zāi)康牧私鈩討B(tài)分區(qū)分配方式中使用的數(shù)據(jù)結(jié)構(gòu)和分配算法，并進(jìn)一步加深對動態(tài)分區(qū)存儲管理方式及其實現(xiàn)過程的理解。2、實驗內(nèi)容(1)用C語言分別實現(xiàn)采用首次適應(yīng)算法和最佳適應(yīng)算法的動態(tài)分區(qū)分配過程alloc()和回收過程free()。其中，空閑分區(qū)通過空閑分區(qū)鏈來管理：在進(jìn)行內(nèi)存分配時，系統(tǒng)優(yōu)先使用空閑區(qū)低端的空間。(2)假設(shè)初始狀態(tài)下，可用的內(nèi)存空間為640KB,并有下列的請求序列：作業(yè)1申請130KB。作業(yè)2申請60KB。作業(yè)3申請100KB。作業(yè)2釋放60KB。作業(yè)4申請200KB。作業(yè)3釋放100KB。作業(yè)1釋放130KB。作業(yè)5申請140KB。作業(yè)6申請60KB。作業(yè)7申請50KB。作業(yè)6釋放60KB。請分別采用首次適應(yīng)算法和最佳適應(yīng)算法，對內(nèi)存塊進(jìn)行分配和回收，要求每次分配和回收后顯示出空閑分區(qū)鏈的情況。專業(yè).專注程序代碼一C語言實#include<stdio.h>#include<stdlib.h>structnode 〃空閑分區(qū)鏈結(jié)點的定義(node*before;node*after;intsize;intaddress;intstate;);nodeL;structusenode(usenode*next;intnum;intadd;intsize;}U,*n;專業(yè).專注voidInit() 〃空閑分區(qū)鏈的初始化(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(inta)(node*p=L.after;if(p二二NULL)(printf("沒有空閑的區(qū)域廠)；專業(yè).專注p=NULL;returnp;)else(while(p!=NULL&&a>p->size)p=p->after;if(p二二NULL)(printf("沒有找到合適的空閑空間廠);p=NULL;returnp;)elsereturnp;))voidrecovery(inta,intb) 〃內(nèi)存回收算法(node*c,*s,*r=L.after;專業(yè).專注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("沒有找到這樣的作業(yè)廠)；else(h->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;專業(yè).專注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;)elser=r->after;)專業(yè).專注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;專業(yè).專注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;專業(yè).專注r->before->after=c;r->before=c;free(k);return;)elser=r->after;)))free(k);)voidalloc(inta,intb)〃分配內(nèi)存算法(node*p,*q=L.after;usenode*m;p=search(b);if(p二二NULL)return;m=(usenode*)malloc(sizeof(usenode));〃生成一個被占用鏈表的結(jié)點并插入到該鏈表的尾部專業(yè).專注m->add=p->address;m->size=b;m->num=a;m->next=n->next;n->next=m;n=m; 〃保證n始終指向被占用鏈表的尾部，方便以后新生成結(jié)點的插入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);))專業(yè).專注voidsort()〃對空閑鏈表進(jìn)行排序(intmax;node*p,*q,*r,*s;nodea;p=L.after;while(p!=NULL) 〃讓指針q指向鏈表的最后一個結(jié)點(q=p;p=p->after;)if(L.after->after二二NULL)return;else(while(p!=q)(s=r=p=L.after;max=r->size;專業(yè).專注while(s!=q->after)(if(s->size>max)(max=s->size;r=s;s=s->after;)elses=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專業(yè).專注q=q->before;voidPrint()(node*p=L.after;usenode*q=U.next;inti=1;printf("\n空閑區(qū)域列表:\n");printf("FREEIDaddresssizeWn");while(p!=NULL)(printf("%-10d",i);printf("%-10d",p->address);printf("%dWn",p->size);p=p->after;專業(yè).專注i++；if(q二二NULL)return;else(printf("\n已分配區(qū)域列表:\n");printf("WORKIDaddresssizeWn");while(q!=NULL)(printf("%-10d",q->num);printf("%-10d",q->add);printf("%dWn",q->size);q=q->next;)))voidfirstfit() 〃首次適應(yīng)算法(inta,b,i;專業(yè).專注Init();Print();while(1){printf("\n1、申請空間\n");printf("2、釋放空間\n");printf("3、退出首次適應(yīng)算法\n");printf("請輸入你的選擇:")；scanf("%d",&i);switch(i){{printf("請輸入申請空間的作業(yè)號:");scanf("%d",&a);printf("請輸入申請空間的大小:")；scanf("%d",&b);alloc(a,b);Print();break;){專業(yè).專注printf("請輸入釋放空間的作業(yè)號:");scanf("%d",&a);printf("請輸入釋放空間的大小:")；scanf("%d",&b);recovery(a,b);Print();break;)case3:printf("\n");return;)))voidbestfit()(inta,b,i;Init();Print();while(1){printf("\n1、申請空間\n");printf("2、釋放空間\n");專業(yè).專注printf("3、退出最佳適應(yīng)算法\n");printf("請輸入你的選擇:")；scanf("%d",&i);switch(i)((printf("請輸入申請空間的作業(yè)號:");scanf("%d",&a);printf("請輸入申請空間的大小:")；scanf("%d",&b);alloc(a,b);sort();Print();break;)(printf("請輸入釋放空間的作業(yè)號:");scanf("%d",&a);printf("請輸入釋放空間的大小:")；scanf("%d",&b);專業(yè).專注recovery(a,b);sort();Print();break;)case3:printf("\n");return;)))voidmain()(inti;while(1)(printf("1、首次適應(yīng)算法Wn");printf("2、最佳適應(yīng)算法Wn");printf("3、退出Wn");printf("請輸入你的選擇:")；scanf("%d",&i);switch(i)專業(yè).專注(case1:firstfit();break;case2:bestfit();break;case3:return;)))運行結(jié)果①開始界面?EM++程序設(shè)計雁便2時”1莉態(tài)分區(qū)分配方式的模擬f 0回—1,首次適應(yīng)算法2、最佳適應(yīng)篁法3、退出請輸入你的選擇:I彳I 肝 I .②首次適應(yīng)算法專業(yè).專注

③最佳適應(yīng)算法?EM++程序謾計雁便\DeMg慟態(tài)分區(qū)分配方式的模擬e燼 口回，首次適應(yīng)算法2、最佳適應(yīng)算法3,退出請輸入你的選擇：2空閑區(qū)域列表：FREEIO address size1 0 6401、申請空間2、釋放空間3、退出最佳適應(yīng)算法請輸入你的選擇：專業(yè).專注程序代碼C++語言實/尸*************************************************************//********動態(tài)分區(qū)分配方式的模擬*********//********動態(tài)分區(qū)分配方式的模擬*********/尸*************************************************************#include<iostream.h>#include<stdlib.h>defineFree0〃空閑狀態(tài)defineBusy1〃已用狀態(tài)defineOK1 //完成defineERROR0〃出錯defineMAX_length640//最大內(nèi)存空間為640KBtypedefintStatus;typedefstructfreearea/淀義一個空閑區(qū)說明表結(jié)構(gòu)(intID;〃分區(qū)號longsize;//分區(qū)大小longaddress;//分區(qū)地址intstate;//狀態(tài)}ElemType;專業(yè).專注

//線性表的雙向鏈表存儲結(jié)構(gòu)//線性表的雙向鏈表存儲結(jié)構(gòu)typedefstructDuLNode//doublelinkedlist(ElemTypedata;structDuLNode*prior;〃前趨指針structDuLNode*next;//后繼指針}DuLNode,*DuLinkList;DuLinkListblock_first;//頭結(jié)點DuLinkListblock_last;//尾結(jié)點Statusalloc(int);//內(nèi)存分配Statusfree(int);〃內(nèi)存回收StatusFirst_fit(int,int);//首次適應(yīng)算法StatusBest_fit(int,int);//最佳適應(yīng)算法voidshow();//查看分配StatusInitblock();//開創(chuàng)空間表StatusInitblock()//開創(chuàng)帶頭結(jié)點的內(nèi)存空間鏈表(block_first=(DuLinkList)malloc(sizeof(DuLNode));專業(yè).專注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;returnOK;)// 分配主存 Statusalloc(intch)(intID,request;cout<<"請輸入作業(yè)(分區(qū)號)：";cin>>ID;cout<<"請輸入需要分配的主存大小(單位:KB)：";cin>>request;if(request<0||request==0)(專業(yè).專注cout<<"分配大小不合適,請重試！"<<endl;returnERROR;)if(ch==2)〃選擇最佳適應(yīng)算法(if(Best_fit(ID,request)==OK)8口卜<"分配成功！"<<endl;elsecout<<"內(nèi)存不足，分配失??！"<<endl;returnOK;)else〃默認(rèn)首次適應(yīng)算法(if(First_fit(ID,request)==OK)8a<<"分配成功！"<<endl;elsecout<<"內(nèi)存不足，分配失??！"<<endl;returnOK;))// 首次適應(yīng)算法 StatusFirst_fit(intID,int?4口0$1)//傳入作業(yè)名及申請量(〃為申請作業(yè)開辟新空間且初始化DuLinkListtemp=(DuLinkList)malloc(sizeof(DuLNode));專業(yè).專注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;returnOK;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;專業(yè).專注p->data.size-=request;returnOK;break;)p=p->next;)returnERROR;)// 最佳適應(yīng)算法 StatusBest_fit(intID,intrequest)(intch;〃記錄最小剩余空間DuLinkListtemp=(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))專業(yè).專注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;returnOK;break;)if(p->data.state二二Free&&p->data.size>request){〃空閑塊大于分配需求if(p->data.size-request<ch)〃剩余空間比初值還小{ch=p->data.size-request;〃更新剩余最小值q=p;〃更新最佳位置指向?qū)I(yè).專注p=p->next;)if(q==NULL)returnERROR;〃沒有找到空閑塊else{〃找到了最佳位置并實現(xiàn)分配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;returnOK;))// 主存回收 Statusfree(intID){DuLNode*p=block_first;專業(yè).專注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;)專業(yè).專注returnOK;)// 顯示主存分配情況 voidshow()(cout<<"+++++++++++++++++++++++++++++++++++++++\n";cout<<"+++主存分配情況+++\n";cout<<"+++++++++++++++++++++++++++++++++++++++\n";DuLNode*p=block_first->next;while(p)(8仇<<"分區(qū)號：”；