動(dòng)態(tài)分區(qū)分配方式地模擬C語(yǔ)言代碼和C++代碼

實(shí)驗(yàn)三 使用動(dòng)態(tài)分區(qū)分配方式的模擬1、 實(shí)驗(yàn)?zāi)康牧私鈩?dòng)態(tài)分區(qū)分配方式中使用的數(shù)據(jù)結(jié)構(gòu)和分配算法，并進(jìn)一步加深對(duì)動(dòng)態(tài)分區(qū)存儲(chǔ)管理方式及其實(shí)現(xiàn)過(guò)程的理解。2、 實(shí)驗(yàn)容用C語(yǔ)言分別實(shí)現(xiàn)采用首次適應(yīng)算法和最佳適應(yīng)算法的動(dòng)態(tài)分區(qū)分配過(guò)程alloc()和回收過(guò)程fiee()o其中，空閑分區(qū)通過(guò)空閑分區(qū)鏈來(lái)管理：在進(jìn)行存分配時(shí)，系統(tǒng)優(yōu)先使用空閑區(qū)低端的空間。假設(shè)初始狀態(tài)下，可用的存空間為640KB,并有下列的請(qǐng)求序列：?作業(yè)1申請(qǐng)130KB。?作業(yè)2申請(qǐng)60KBo?作業(yè)3申請(qǐng)100KB。?作業(yè)2釋放60KBo?作業(yè)4申請(qǐng)200KBo?作業(yè)3釋放lOOKBo?作業(yè)1釋放130KBo?作業(yè)5申請(qǐng)140KB。?作業(yè)6申請(qǐng)60KBo?作業(yè)7申請(qǐng)50KBo?作業(yè)6釋放60KB。請(qǐng)分別采用首次適應(yīng)算法和最佳適應(yīng)算法，對(duì)存塊進(jìn)行分配和回收，要求每次分配和回收后顯示出空閑分區(qū)鏈的情況。程序代一~C語(yǔ)言實(shí)現(xiàn)#iiiclude<stdio.h>#iiiclude<stdlib.h>stiuctnode 〃空閑分區(qū)鏈結(jié)點(diǎn)的定義(node*befbre;node*after;intsize;intaddress;intstate;｝；nodeL;structusenode(usenode*next;intnum;intadd;intsize;voidImt() 〃空閑分區(qū)鏈的初始化(node*p;p=(node*)malloc(sizeof(node));p->befbre=&L;p->aftei-NULL;p->size=640;p->addiess=O;p->state=O;L.after=p;L.befbre=NULL;L.size=0;U.next=NULL;n=&U;node*search(iiita)(node*p=L.after;if(p=NULL){pnntf(”沒有空閑的區(qū)域!”)；p=NULL;returnp;}else{wliile(p!=NULL&&a>p->size)p=p->after;if(p—NULL){pnntf(”沒有找到合適的空閑空f(shuō)uj!”);p=NULL;returnp;}elsereturnp;}node*c,*s,*r=L.after;node*d=L.aftei\*e;usenode*k=U.next,*h=&U;while(k?=NULL&&a!=k->num){h=k;k=k->next;}if(k=NULL)pnntf(”沒有找到這樣的作業(yè)!)else{h->next=k->next;if(h->next==NULL)n=h;}wlule(r!=NULL) 〃若回收得到的空閑塊的前方有空閑塊合并此空閑塊{if(k->add==i?->addiess+r->size){r->size=i->size+k->size;break;}elser=r->after;}if(r==NULL) 〃若回收得到的空閑塊的后面有空閑塊合并此空閑塊{r=L.after;wlule(r!=NULL)if(k->add+k->size=r->address){r->address=k->add;r->size=i?->size+k->size;break;}elsei-i->after;}wlule(d!=NULL) //保證空閑鏈表中沒有相鄰的空閑空間{if(d->after!=NULL)e=d->after;elsebreak;ifi(d->addiess+d->size==e->addiess){d->after=e->after;while(e->after!=NULL)e->after->befbre=d;d->size=d->size-re->size;fiee(e);break;}elsed=d->after;}if(i-==NULL){r=L.after;c=(node*)malloc(sizeof(node));c->size=b;c->addiess=k->add;if(L.after=NULL){c->aftei-L.after;c->befbre=&L;L.after=c;}else{i-L.after;wlule(r!=NULL)if(r->address>c->address)c->after=r;c->before=r->befbie;r->befbre->aftei-c;r->befbre=c;fiee(k);return;}else1=1->after;}}}fiee(k);voidalloc(iiita,intb)//分配存算法(node*p,*q=L.after;usenode*m;p=search(b);iftp==NULL)return;m=(usenode*)malloc(sizeof(usenode))J/生成一個(gè)被占用鏈表的結(jié)點(diǎn)，并插入到該鏈表的尾部m->add=p->address;m->size=b;m->num=a;m->next=n->next;n->next=m;n=m; 〃保證n始終指向被占用鏈表的尾部，方便以后新生成結(jié)點(diǎn)的插入!f(p->size>b)〃如果申請(qǐng)空間的大小小于找到空閑空間的大小的處理{p->size=p->size-b;p->address=p->addiess-rb;}else 〃如果申請(qǐng)空間的大小等于找到空閑空間的大小的處理{p->befbre->aftei-p->after;if(p->after!=NULL)p->after->befbre=p->befbre;free(p);voidsort() 〃對(duì)空閑鏈表進(jìn)行排序(intmax;node*p,*q,*r,*s;nodea;p=L.after;wlule(p!=NULL)//讓指針q指向鏈表的最后一個(gè)結(jié)點(diǎn){q=p;p=p->after;}if(L.after->after=NULL)return;else{wlule(p!=q){s=r=p=L.after;max=r->size;wliile(s!=q->after)fif(s->size>max)(max=s->size;r=s;s=s->after;)elses=s->after;}a.size=q->size;a.addiess=q->addiess;q->size=r->size;q->addiess=r->address;r->size=a.size;r->addiess=a.address;if(q->befbie->befdre==&L)return;elseq=q->befbre;voidPriiitQ(node*p=L.after;usenode*q=U.next;inti=l;pnntf(”\n空閑區(qū)域列表:\n”)；printfV'FREEIDaddresssize\nM);wlule(p!=NULL){pnntf(”％.10d”,i);printf(M%-1Od*\p->addiess);printR"%d\n”,p?>size);p=p->after;1++;}if(q=NULL)return;else{pnntf(M\n己分配區(qū)域列表:\n”)；printfV'WORKEDaddresssizeW);wlule(q!=NULL){printf(M%-1Od*\q->num);pnntf(M%-lOd*\q->add);pnntf(M%d'n,\q->size);q=q->next;}}1voidfirstfit() 〃首次適應(yīng)算法inta,b,i;ImtQ;PrmtO;wlule(l){prmtf(H\iil.申請(qǐng)空間山”)；pnntf("2、釋放空間"”);pnntf(”3、退出首次適應(yīng)算法\n”)；pnntf(”請(qǐng)輸入你的選擇:”)；scanf(”％d”,&i);switch(i)(case1:(pimtfC請(qǐng)輸入申請(qǐng)空間的作業(yè)號(hào):”);scanff'%d”,&a);prmtf("請(qǐng)輸入申請(qǐng)空間的大小:”)；scaiW'%d”,&b);alloc(a,b);Pnnt();break;}case2:(prmtfC'請(qǐng)輸入釋放空間的作業(yè)號(hào);scanf(”％d",&a);pnntf(”請(qǐng)輸入釋放空間的大小:”)；scanf(”％d",&b);recoveiy(a.b);Pnnt();break;}case3:}}}voidbestfitQ(inta,b,i;ImtQ;PrmtO;wlule(l){prmtf(H\iil.申請(qǐng)空間山”)；pnntf("2、釋放空間瑚);pnntf(”3、退出最佳適應(yīng)算法\n”)；pnntf(”請(qǐng)輸入你的選擇:”)；scanf(”％d”,&i);switch(i)(case1:(pruitfC請(qǐng)輸入申請(qǐng)空間的作業(yè)號(hào)：，scanf(”％d",&a);prmtf("請(qǐng)輸入申請(qǐng)空間的大小:”)；scanf(”％d",&b);alloc(a,b);sort。；Prmt();break;)case2:(pnntf(”請(qǐng)輸入釋放空間的作業(yè)號(hào):scanf(”％d",&a);prmtf("請(qǐng)輸入釋放空間的大小:”)；scanf(”％d",&b);recoveiy(a.b);sort。；Prmt();break;)case3:)}voidmain。(inti;wlule(l)(printfC'1、首次適應(yīng)算法\11”)；printf("2、最佳適應(yīng)算法寸)；pnntf(”3、退出\n”)；pnntf(”請(qǐng)輸入你的選擇：，scanff%d”,&i);switch(i){case1:fustfit();break;case2:bestfit();break;case3:return;}蠢尚果①開始界面②首次適應(yīng)算法bE:\Ci程序設(shè)計(jì)、隨便\Debug\動(dòng)態(tài)分區(qū)分配方式的模擬exe1、 首次適應(yīng)算法2、 最佳適應(yīng)算法3、 退出請(qǐng)輸入你的選擇：1空閑區(qū)域列表：FREEID address size1 Q 6401、 申請(qǐng)空間2、 釋放空間3、 退出首次適應(yīng)算法請(qǐng)輸入你的選擇：③最佳適應(yīng)算法bE:\Ci程序設(shè)計(jì)、隨便\Debug\動(dòng)態(tài)分區(qū)分配方式的模擬exe1、 首次適應(yīng)算法2、 最佳適應(yīng)算法3、 退出請(qǐng)輸入你的選擇：2空閑區(qū)域列表：FREEID addresssize1 Q 6401、 申請(qǐng)空間2、 釋放空間3、 退出最枝適應(yīng)算法請(qǐng)輸入你的選擇：L程序代_i語(yǔ)言實(shí)現(xiàn)儼*******動(dòng)態(tài)分區(qū)分配方式的模擬*********#iiiclude<iostreain.h>#iiiclude<stdlib.h>#defiiieFree0//空閑狀態(tài)#defiiieBusy1〃已用狀態(tài)#defiiieOK1//完成#defiiieERROR0〃出錯(cuò)#defiiieMAXJength640〃最大存空間為640KBtypedefintStatus;typedefstiuctfreearea//定義一個(gè)空閑區(qū)說(shuō)明表結(jié)構(gòu)(intID;〃分區(qū)號(hào)longsize;〃分區(qū)大小longaddress;〃分區(qū)地址intstate;〃狀態(tài)}ElemType;// 線性表的雙向鏈表存儲(chǔ)結(jié)構(gòu) typedefstiuctDuLNode//doubleluikedlist(ElemTypedata;structDuLNode*piior;〃前趨指針stiuctDuLNode*next;〃后繼指針)DuLNode,*DuLuikList;DuLinkListblock_fkst;〃頭結(jié)點(diǎn)DuLinkListblockjast;〃尾結(jié)點(diǎn)Statusalloc(iiit);//存分配Statusfiee(mt);〃存回收Status 首次適應(yīng)算法StatusBest_fit(mt.mt);//最佳適應(yīng)算法voidshow。;〃查看分配StatusInitblockOy/開創(chuàng)空間表StatusInitblockQ//開創(chuàng)帶頭結(jié)點(diǎn)的存空間鏈表block_first=(DuLuikList)malloc(sizeof(DuLNode));block_last=(DuLnikList)malloc(sizeof(DuLNode));block_first->piioi=NULL;block_first->next=block_last;block_last->prioi-block_fiist;biock_last->next=NULL;block_last->data.addiess=0;block_last->data.size=MAX_length;block_last->data.ED=0;block_last->data.state=Free;returnOK;i// 分配主存 Statusalloc(iiitch)(intIDdequest;coutvv”請(qǐng)輸入作業(yè)(分區(qū)號(hào))：”；cin?ID;cout?"請(qǐng)輸入需要分配的主存大小(單位:KB)：”；cin?iequest;if(request<O||iequest==0)(cout?H分配大小不合適，請(qǐng)重試！“vvendl;returnERROR;if(ch==2)〃選擇最佳適應(yīng)算法(if(Best_fit(ID,fequest)=OK)cout?"分配成功！M?endl;elsecout?H存不足，分配失敗！H?endl;returnOK;else//^認(rèn)首次適應(yīng)算法(if(First_fit(ID,request)=OK)cout?"分配成功!M?endl;elsecout?H存不足，分配失??！H?endl;returnOK;i1j// 首次適應(yīng)算法 Status IDantrequest)//傳入作業(yè)名及申請(qǐng)量〃為申請(qǐng)作業(yè)開辟新空間且初始化DuLnikListtemp=(DuLinkList)malloc(sizeof(DuLNode));tenip->data.ID=ID:tenip->data.size=request;tenip->data.state=Busy;DuLNode*p=block_fiist->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->prioi-p->prior;temp->next=p;temp->data.address=p->data.address;p->prior->next=temp;p->pnoi-tenip;p->data.address=temp->data.addiess+temp->data.size;p->data.size-=request;returnOK;break;p=p->next;returnERROR;1)// 最佳適應(yīng)算法 StatusBesCfit(iiitIDantrequest)(intch;〃記錄最小剩余空間DuLuikListtemp=(DuLinkList)malloc(sizeof(DuLNode));tenip->data.ID=ID;tenip->data.size=request;tenip->data.state=Busy;DuLNode*p=block_fiist->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；returnOK;break:if(p->data.state=Free&&p->data.size>request){//空閑塊大于分配需求if(p->data.size-iequest<ch)//剩余空間比初值還小(ch=p->data.size-request;//更新剩余最小值q=p；〃更新最佳位置指向p=p->next;if(q==NULL)returnERROR;//沒有找到空閑塊else{〃找到了最佳位置并實(shí)現(xiàn)分配temp->prioi-q->prior;temp->next=q;temp->data.addiess=q->data.address;q->prior->next=temp;q->prior=temp;q->data.addiess+=request;q->data.size=ch;returnOK;// 主存回收 StatusID)(DuLNode*p=block_fiist;while(p)if(p->data.ID==ID)(p->data.state=Free;p->data.ID=Fiee;if(p->piior->data.state==Free)//與前面的空閑塊相連(p->piior->data.size+=p->data.size;p->pnor->next=p->next;p->next->prioi-p->prioi;if(p->next->data.state=Free)//與后面的空閑塊相連(p->data.size-r=p->next->data.size;p->next->next->prioi=p;p->next=p->next->next;break;p=p->next;returnOK;// 顯示主存分配情況 voidshowQ(cout?"+++主存分配情況+++\n”；coutvv”+++++++++++++++++++++++++++++++++++++++\n”；DuLNode