最差算法.docx
- 文档编号:292860
- 上传时间:2023-04-28
- 格式:DOCX
- 页数:18
- 大小:32.82KB
最差算法.docx
《最差算法.docx》由会员分享,可在线阅读,更多相关《最差算法.docx(18页珍藏版)》请在冰点文库上搜索。
最差算法
1.3.7程序源代码
#include
#include
usingnamespacestd;
#defineFree0
#defineBusy1
#defineOK1
#defineERROR0
#defineMAX_length1024
typedefintStatus;
intflag;
typedefstructfreearea
{
longsize;
longaddress;
intstate;
}ElemType;
typedefstructDuLNode
{
ElemTypedata;
structDuLNode*prior;
structDuLNode*next;
}
DuLNode,*DuLinkList;
DuLinkListblock_first;
DuLinkListblock_last;
Statusalloc(int);
Statusfree(int);
StatusWorst_fit(int);
voidshow();
StatusInitblock();
StatusInitblock()
{
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.state=Free;
returnOK;
}
Statusalloc()
{
intrequest=0;
cout<<"请输入需要分配的主存大小(单位:
KB):
";
cin>>request;
if(Worst_fit(request)==OK)cout<<"分配成功!
"< elsecout<<"内存不足,分配失败! "< returnOK; } StatusWorst_fit(intrequest) { intch; DuLinkListtemp=(DuLinkList)malloc(sizeof(DuLNode)); 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)) { if(q==NULL) { q=p; ch=p->data.size-request; } elseif(q->data.size { q=p; ch=p->data.size-request; } } p=p->next; } if(q==NULL)returnERROR; elseif(q->data.size==request) { q->data.state=Busy; returnOK; } 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; returnOK; } returnOK; } Statusfree(intflag) { DuLNode*p=block_first; for(inti=0;i<=flag;i++) //if(p! =NULL) p=p->next; //else //returnERROR; p->data.state=Free; if(p->prior! =block_first&&p->prior->data.state==Free) { p->prior->data.size+=p->data.size; p->prior->next=p->next; p->next->prior=p->prior; p=p->prior; } if(p->next! =block_last&&p->next->data.state==Free) { p->data.size+=p->next->data.size; p->next->next->prior=p; p->next=p->next->next; } if(p->next==block_last&&p->next->data.state==Free) { p->data.size+=p->next->data.size; p->next=NULL; } returnOK; } voidshow() { intflag=0; cout<<"----------------------------------------------\n\n"; DuLNode*p=block_first->next; cout<<"分区号\t起始地址\t分区大小\t状态\n\n"; while(p) { cout<<""< cout<<""< cout<<""< if(p->data.state==Free)cout<<"空闲\n\n"; elsecout<<"已分配\n\n"; p=p->next; } cout<<"----------------------------------------------\n\n"; } voidmain() { Initblock(); intchoice; while (1) { show(); cout<<"请输入您的操作: "; cout<<"\n1: 分配内存\n2: 回收内存\n0: 退出\n"; cin>>choice; if(choice==1)alloc(); elseif(choice==2) { intflag; cout<<"请输入您要释放的分区号: "; cin>>flag; free(flag); } elseif(choice==0)break; else {cout<<"输入有误,请重试! "< continue; } }} 1.5调试分析(代码截图) 初始界面 ---------------------------------------------- 分区号起始地址分区大小状态 001024KB空闲 ---------------------------------------------- 测试数据: 分配12KB 分配23KB 分配34KB 分配45KB 分配56KB ---------------------------------------------- 分区号起始地址分区大小状态 0012KB已分配 11223KB已分配 23534KB已分配 36945KB已分配 411456KB已分配 5170854KB空闲 ---------------------------------------------- 请输入您的操作: 1: 分配内存 2: 回收内存 0: 退出 回收内存: 回收1号分区的23KB 请输入您的操作: 1: 分配内存 2: 回收内存 0: 退出 请输入您要释放的分区号: 1 ---------------------------------------------- 分区号起始地址分区大小状态 0012KB已分配 11223KB空闲 23534KB已分配 36945KB已分配 411456KB已分配 5170854KB空闲 ---------------------------------------------- 此时,内存中空闲区有两块,不相邻。 再次分配内存,则选满足条件的长度较大的空闲区进行分割。 分配11KB内存 请输入您的操作: 1: 分配内存 2: 回收内存 0: 退出 1 请输入需要分配的主存大小(单位: KB): 11 分配成功! ---------------------------------------------- 分区号起始地址分区大小状态 0012KB已分配 11223KB空闲 23534KB已分配 36945KB已分配 411456KB已分配 517011KB已分配 6181843KB空闲 ---------------------------------------------- 全部回收 回收23KB的分区 请输入您的操作: 1: 分配内存 2: 回收内存 0: 退出 2 请输入您要释放的分区号: 1 ---------------------------------------------- 分区号起始地址分区大小状态 0012KB已分配 11223KB空闲 23534KB已分配 36945KB已分配 411456KB已分配 517011KB已分配 6181843KB空闲 回收12KB的分区 请输入您的操作: 1: 分配内存 2: 回收内存 0: 退出 2 请输入您要释放的分区号: 0 ---------------------------------------------- 分区号起始地址分区大小状态 0035KB空闲 13534KB已分配 26945KB已分配 311456KB已分配 417011KB已分配 5181843KB空闲 ---------------------------------------------- 回收34KB的分区 请输入您的操作: 1: 分配内存 2: 回收内存 0: 退出 2 请输入您要释放的分区号: 1 ---------------------------------------------- 分区号起始地址分区大小状态 0069KB空闲 16945KB已分配 211456KB已分配 317011KB已分配 4181843KB空闲 ---------------------------------------------- 回收45KB的分区: 请输入您的操作: 1: 分配内存 2: 回收内存 0: 退出 请输入您要释放的分区号: 1 ---------------------------------------------- 分区号起始地址分区大小状态 00114KB空闲 111456KB已分配 217011KB已分配 3181843KB空闲 ---------------------------------------------- 回收56KB的分区: ---------------------------------------------- 分区号起始地址分区大小状态 00170KB空闲 117011KB已分配 2181843KB空闲 ---------------------------------------------- 请输入您的操作: 1: 分配内存 2: 回收内存 0: 退出 回收11KB的分区: 1: 分配内存 2: 回收内存 0: 退出 2 请输入您要释放的分区号: 1 ---------------------------------------------- 分区号起始地址分区大小状态 001024KB空闲 程序设计: #include #include #include #include #include usingnamespacestd; booltools[5]; CRITICAL_SECTIONcs; classPhilosopher { private: intnumber; intstatus; public: Philosopher(intnum=0): status (2),number(num){} constintfind() { returnnumber; } constintgetinfo() {returnstatus;} voidChange(); voiddead_lock(); }; voidPhilosopher: : dead_lock() { EnterCriticalSection(&cs); strings; if(status==1) { tools[number%5]=true; status=2;} elseif(status==2) {status=0; } elseif(status==0) {tools[number%5]=false; tools[(number-1)%5]=false; status=1; } LeaveCriticalSection(&cs); } voidPhilosopher: : Change() { EnterCriticalSection(&cs); if(status==1) { tools[number%5]=true; tools[(number-1)%5]=true; status=2; } elseif(status==2) { status=0; } elseif(status==0) { if(tools[number%5]&&tools[(number-1)%5]) { tools[number%5]=false; tools[(number-1)%5]=false; status=1; } } LeaveCriticalSection(&cs); } stringprint(Philosopher*pA) { inti=pA->getinfo(); stringstr; if(i==0) str="等待"; elseif(i==1) str="就餐"; elsestr="思考"; returnstr; } stringtoolstatus(boola) { stringstate; if(a==true) state="闲"; if(a==false) state="用"; returnstate; } intmain() { for(inti=0;i<5;i++) tools[i]=true; PhilosopherP1 (1),P2 (2),P3(3),P4(4),P5(5); InitializeCriticalSection(&cs); while (1) { cout<<"-----------------------状态说明示意图: -----------------------"< cout< cout<<""<<"哲学家1号"<<""< cout<<""< cout<<"筷子0"<<""<<"筷子1"< cout<<""< cout<<"哲学家5号"<<""<<"哲学家2号"< cout<<""< cout<<"筷子4"<<""<<"筷子2"< cout<<""< cout<<"哲学家4号"<<""<<"哲学家3号"< cout<<""< cout<<""<<"筷子3"< cout<<""< cout<<"筷子的状态,用表示使用中,闲表示空闲中。 "< cout<<"--------------------------------------------------------------"< cout< P1.Change();P2.Change();P3.Change();P4.Change();P5.Change(); cout<<"当前状态为: "< cout<<""< cout<<""< cout<<"0"< cout<<""< cout<<""< cout<<""< cout<<"4"< cout<<""< cout<<""< cout<<""< cout<<"3"< Sleep(20);} DeleteCriticalSection(&cs); return0;} 调试分析(代码截图)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最差 算法
![提示](https://static.bingdoc.com/images/bang_tan.gif)