#include<stdio.h>#include<time.h>#include<stdlib.h>intmemoryStartAddress=-1;intmemorySize=-1;structjobListintid;/*作業(yè)ID*/intid;intsize;/*作業(yè)大小（需要的存儲空間大小）*/intstatus;/*作業(yè)狀態(tài)0:newjob,1:inthememory,2:finished.*/structjobList*next;};structjobList*next;};structfreeList/*作業(yè)鏈表指針*/{intstartAddress;{intstartAddress;/*分區(qū)起始地址*/intsize;structfreeList*next;intsize;structfreeList*next;};structusedList/*分區(qū)大小*/

/*分區(qū)鏈表指針*/{{intstartAddress;intjobID;structusedList*next;};voiderrorMessage(void)/*分區(qū)起始地址*//*分區(qū)中存放作業(yè)ID*//*分區(qū)鏈表指針*/*//*出現(xiàn)嚴(yán)重錯誤時顯示信息并結(jié)束程序{*/printf("\n\tError!\a");printf("\nPressanykeytoexit!");getch();exit(1);}voidopenFile(FILE**fp,char*filename,char*mode)/*以要求的方式打開文件*/{if((*fp=fopen(filename,mode))==NULL){printf("\nCan'topen%sinmode%s.",filename,mode);errorMessage();}voidmakeFreeNode(structfreeList**empty,intstartAddress,intsize)/*根據(jù)參數(shù)startAddress、size創(chuàng)建空閑節(jié)點，由empty指針返回*/{if((*empty=malloc(sizeof(structfreeList)))==NULL){printf("\nNotenoughtoallocateforthefreenode.");errorMessage();}(*empty)->startAddress=startAddress;(*empty)->size=size;(*empty)->next=NULL;}voidiniMemory(void)/*初始化存儲空間起始地址、大小*/{charMSA[10],MS[10];printf("\nPleaseinputthestartaddressofthememory!");scanf("%s",MSA);memoryStartAddress=atoi(MSA);printf("\nPleaseinputthesizeofthememory!");scanf("%s",MS);memorySize=atoi(MS);}charselectFitMethod(void) /*選擇適應(yīng)算法*/{FILE*fp;charfitMethod;do{printf("\n\nPleaseinputacharasfallowtoselectthefitmethod!\\n1(Bestfit)\\n2(Worstfit)\\n3(Firstfit)\\n4(Lastfit)\n");fitMethod=getche();}while(fitMethod<'1'||fitMethod>'4');openFile(&fp,"d:\\result.cl","a");switch(fitMethod){case'1':fprintf(fp,"\n\n\n\n\tBestfit");

fprintf(fp,"\n**********************************************");fprintf(fp,"\n**********************************************");break;case'2':fprintf(fp,"\n\n\n\n\tWorstfit");fprintf(fp,"\n**********************************************");fprintf(fp,"\n**********************************************");break;case'3':fprintf(fp,"\n\n\n\n\tFirstfit");fprintf(fp,"\n**********************************************");fprintf(fp,"\n**********************************************");break;case'4':fprintf(fp,"\n\n\n\n\tLastfit");fprintf(fp,"\n**********************************************");break;}fclose(fp);returnfitMethod;}voidinputJob(void)/*從鍵盤輸入作業(yè)到D盤的JOB文件*/{int/*id,size,*/status=0,jobnum=0;FILE*fp;charid[10],size[10];openFile(&fp,"d:\\job.cl","w");fprintf(fp,"job_ID\tsize\tstatus");printf("\n\n\n\nPleaseinputthejobsasfallow!\\nEnteraintegersmallerthan1toquit.\njob_ID\tsize\n");do{/*scanf("%d%d",&id,&size);*/scanf("%s\t%s",id,size);if(atoi(id)>0&&atoi(size)>0){fprintf(fp,"\n%s\t%s\t%d",id,size,status);/*fprintf(fp,"\n%d\t%d\t%d",id,size,status);*/jobnum++;}elsebreak;}while(1);if(jobnum)printf("\nFinishedtoinputthejobs!");else{printf("\nNojobwasgiven.");errorMessage();}fclose(fp);}intmakeJobList(structjobList**jobs)/*從JOB文件中讀出作業(yè)并創(chuàng)建作業(yè)鏈表*/{charjobID[10],size[10],status[10];structjobList*rear;FILE*fp;openFile(&fp,"d:\\job.cl","r");fscanf(fp,"%s%s%s",jobID,size,status);if((*jobs=malloc(sizeof(structjobList)))==NULL){printf("\nNotenoughtoallocateforthejob.");fclose(fp);errorMessage();}rear=*jobs;(*jobs)->next=NULL;while(!feof(fp)){structjobList*p;fscanf(fp,"%s%s%s",jobID,size,status);if((p=malloc(sizeof(structjobList)))==NULL){printf("\nNotenoughtoallocateforthejob.");fclose(fp);errorMessage();}p->next=rear->next;rear->next=p;rear=rear->next;rear->id=atoi(jobID);{{rear->size=atoi(size);rear->status=atoi(status);}fclose(fp);return0;}intupdateJobFile(structjobList*jobs) /*更新作業(yè)鏈表中作業(yè)的狀態(tài)*/{FILE*fp;structjobList*p;openFile(&fp,"d:\\job.cl","w");fprintf(fp,"job_ID\tsize\tstatus");for(p=jobs->next;p;p=p->next)fprintf(fp,"\n%d\t%d\t%d",p->id,p->size,p->status);fclose(fp);return0;}intshowFreeList(structfreeList*empty) /*空閑分區(qū)隊列顯示*/{FILE*fp;structfreeList*p=empty->next;intcount=0;openFile(&fp,"d:\\result.cl","a");fprintf(fp,"\n\nNowshowthefreelist...");printf("\n\nNowshowthefreelist...");if(p){fprintf(fp,"\nnumber\tsize\tstartAddress");printf("\nnumber\tsize\tstartAddress");for(;p;p=p->next){fprintf(fp,"\n%d\t%d\t%d",++count,p->size,p->startAddress);printf("\n%d\t%d\t%d",count,p->size,p->startAddress);}fclose(fp);return1;}elsefprintf(fp,"\nThememorywasusedout!");printf("\nThememorywasusedout!");fclose(fp);return0;}}voidgetJobInfo(structjobList*jobs,intid,int*size,int*status)/*獲取作業(yè)的信息*/{structjobList*p=jobs->next;while(p&&p->id!=id)p=p->next;if(p==NULL){printf("\nCan'tfindthejobwhichidis:%d.",id);errorMessage();}else{*size=p->size;*status=p->status;}}voidupdateJobStatus(structjobList**jobs,intid,intstatus){structjobList*p=(*jobs)->next;while(p&&p->id!=id)p=p->next;if(p==NULL){printf("\nCan'tfindthejobwhichidis:%d.",id);errorMessage();}elsep->status=status;}intshowUsedList(structjobList*jobs,structusedList*used)/*作業(yè)占用鏈表顯示*/{FILE*fp;structusedList*p=used->next;intcount=0,size,status;openFile(&fp,"d:\\result.cl","a");fprintf(fp,"\n\nNowshowtheusedlist...");printf("\n\nNowshowtheusedlist...");if(p){fprintf(fp,"\nnumber\tjobID\tsize\tstartAddress");printf("\nnumber\tjobID\tsize\tstartAddress");for(;p;p=p->next){getJobInfo(jobs,p->jobID,&size,&status);fprintf(fp,"\n%d\t%d\t%d\t%d",++count,p->jobID,size,p->startAddress);printf("\n%d\t%d\t%d\t%d",count,p->jobID,size,p->startAddress);}fclose(fp);return1;}else{fprintf(fp,"\nNojobinthememory!Youshouldinputsomejobstoit.");printf("\nNojobinthememory!Youshouldinputsomejobstoit.");fclose(fp);return0;}}intshowJobList(structjobList*jobs)/*顯示作業(yè)鏈表*/{structjobList*p;p=jobs->next;if(p==NULL){printf("\nNojobinthelist!Tryagainnexttime.");return0;}printf("\n\nThejoblistisasfallow:\njob_ID\tsize\tstatus");while(p){printf("\n%d\t%d\t%d",p->id,p->size,p->status);p=p->next;}{{return1;}voidmoveFragment(structjobList*jobs,structfreeList**empty,structusedList**used){intsize,status;structusedList*p;intaddress=memoryStartAddress;/*全局變量，初始化時分配存儲空間始址*/if((*empty)->next==NULL) /*空閑分區(qū)鏈表為空，提示并返回*/{printf("\nThememorywasusedoutatall.\nMaybeyoushouldfinishsomejobsfirstorpressanykeytotryagain!");getch();return;}for(p=(*used)->next;p;p=p->next)/*循環(huán)的修改占用分區(qū)的始址*/{p->startAddress=address;getJobInfo(jobs,p->jobID,&size,&status);/*由作業(yè)ID獲得作業(yè)大小*/address+=size;}(*empty)->next->startAddress=address;/*修改空閑分區(qū)的首節(jié)點始址、大小*/(*empty)->next->size=memorySize-(address-memoryStartAddress);(*empty)->next->next=NULL;/*刪除首節(jié)點后的所有節(jié)點*/}voidorder(structfreeList**empty,intbySize,intinc){structfreeList*p,*q,*temp;intstartAddress,size;for(p=(*empty)->next;p;p=p->next){/*按bySize和inc兩個參數(shù)尋找合適的節(jié)點，用temp指向它*/for(temp=q=p;q;q=q->next)switch(bySize){{{{case0:switch(inc){case0:if(q->size<temp->size)temp=q;break;default:if(q->size>temp->size)temp=q;break;}break;default:switch(inc){case0:if(q->startAddress<temp->startAddress)temp=q;break;default:if(q->startAddress>temp->startAddress)temp=q;break;}break;}}/*交換節(jié)點的成員值*/if(temp!=p){startAddress=p->startAddress;size=p->size;p->startAddress=temp->startAddress;p->size=temp->size;temp->startAddress=startAddress;temp->size=size;}}}intallocate(structfreeList**empty,intsize)/*為作業(yè)分配存儲空間、狀態(tài)必須為0*/{structfreeList*p,*prep;intstartAddress=-1;p=(*empty)->next;while(p&&p->size<size)p=p->next;if(p!=NULL)if(p->size>size){startAddress=p->startAddress;p->startAddress+=size;p->size-=size;}else{startAddress=p->startAddress;prep=*empty;while(prep->next!=p)prep=prep->next;prep->next=p->next;free(p);}}elseprintf("\nMaybeyoushouldmovethefragmenttogether.");/*Unsuccessful!*/returnstartAddress;}voidinsertUsedNode(structusedList**used,intid,intstartAddress) /*插入釋放的空間到used鏈表中(作業(yè)號為 id,startAddress由函數(shù)13返回)*/{structusedList*q,*r,*prer;if((q=malloc(sizeof(structusedList)))==NULL){printf("\nNotenoughtoallocatefortheusednode.");errorMessage();}q->startAddress=startAddress;q->jobID=id;prer=*used;r=(*used)->next;while(r&&r->startAddress<startAddress){prer=r;r=r->next;}q->next=prer->next;prer->next=q;}intfinishJob(structusedList**used,intid,int*startAddress)/*結(jié)束一個作業(yè)號為id的作業(yè)，釋放存儲空間(由*startAddress返回空間的起始地址)*/{structusedList*p,*prep;prep=*used;p=prep->next;while(p&&p->jobID!=id){prep=p;p=p->next;}if(p==NULL){printf("\nThejobwhichidis:%disnotinthememory!",id);return0;}else{*startAddress=p->startAddress;prep->next=p->next;free(p);return1;}}voidinsertFreeNode(structfreeList**empty,intstartAddress,intsize)/*插入回收的空節(jié)點分區(qū)，處理回收分區(qū)與空閑分區(qū)的四種鄰接關(guān)系。 */{structfreeList*p,*q,*r;for(p=*empty;p->next;p=p->next);/*處理鏈表尾部的鄰接情況*/if(p==*empty||p->startAddress+p->size<startAddress)/*與尾部不相鄰*/{makeFreeNode(&r,startAddress,size);/*通過r指針返回創(chuàng)建的空閑節(jié)點*/r->next=p->next; /*插入獨(dú)立的空閑節(jié)點*/p->next=r;return;}if(p->startAddress+p->size==startAddress)/*與尾部上鄰*/{{/*/*合并尾部節(jié)點*/p->size+=size;return;}q=(*empty)->next; /*處理鏈表首節(jié)點的鄰接情況*/if(startAddress+size==q->startAddress)/*與首節(jié)點下鄰*/{q->startAddress=startAddress; /*合并首節(jié)點*/q->size+=size;}elseif(startAddress+size<q->startAddress)/*與首節(jié)點不相鄰*/{makeFreeNode(&r,startAddress,size);r->next=(*empty)->next;(*empty)->next=r;}else{/*處理鏈表中間的鄰接情況*/while(q->next&&q->startAddress<startAddress){p=q;q=q->next;}if(p->startAddress+p->size==startAddress&&\q->startAddress==startAddress+size)/*上下鄰，合并節(jié)點*/{p->size+=size+q->size;p->next=q->next;free(q);/*刪除多余節(jié)點*/}elseif(p->startAddress+p->size==startAddress&&\q->startAddress!=startAddress+size)/*上鄰，增加節(jié)點的大小*/{p->size+=size;}elseif(p->startAddress+p->size!=startAddress&&\q->startAddress==startAddress+size) /*下鄰*/q->startAddress=startAddress;/*修改節(jié)點起始地址*/q->size+=size; /*修改節(jié)點的大小*/}else{/*上下不相鄰*/makeFreeNode(&r,startAddress,size);r->next=p->next;p->next=r;}}}voidmain(void){charfitMethod;FILE*fp;structjobList*jobs;structfreeList*empty;structusedList*used;if((used=malloc(sizeof(structusedList)))==NULL){printf("\nNotenoughtoallocatefortheusednode.");errorMessage();}used->next=NULL;remove("d:\\result.cl");makeFreeNode(&empty,0,0);while(1){charch,step;intid,size,startAddress,status;structjobList*q;printf("\n1 Initializiation.\\n2 Putjobintomemory(allocatememory).\\n3 Finishjob(reusememory).\\n4 Showcurrentfreelist.\\n5 Showcurrentmemoryusedbyjobs.\\n6 Movefragmenttogether.\\n7 Exit.");printf("\nPleaseselectadigittocontinue.\n");step=getche();printf("\n");switch(step){case'1':openFile(&fp,"d:\\result.cl","a");fprintf(fp,"\n\n\tInitializiation:)");used->next=NULL;empty->next=NULL;iniMemory();makeFreeNode(&(empty->next),memoryStartAddress,memorySize);fprintf(fp,"\n\n\nDoyouwanttouseyourjobfiledirectly?\\nDefaultis\'N\'.Y/N:");printf("\n\n\nDoyouwanttouseyourjobfiledirectly?\\nDefaultis\'N\'.Y/N:\n");ch=getche();fprintf(fp,"\n%c",ch);fclose(fp);if(ch!='Y'&&ch!='y'){inputJob();}makeJobList(&jobs);if(ch=='Y'||ch=='y'){for(q=jobs->next;q;q=q->next){if(q->status==1){startAddress=allocate(&empty,q->size);if(startAddress!=-1){insertUsedNode(&used,q->id,startAddress);}}}}fitMethod=selectFitMethod();break;case'2':if(memoryStartAddress<0||memorySize<1){printf("\n\nBadmemoryallocated!\a");break;}openFile(&fp,"d:\\result.cl","a");fprintf(fp,"\n\n\tPutjobintomemory(allocatememory)...");fprintf(fp,"\n\n\nDoyouwanttoallocateforjobfromkeyboard?\\nDefaultis\'N\'.Y/N:");printf("\n\n\nDoyouwanttoallocateforjobfromkeyboard?\\nDefaultis\'N\'.Y/N:\n");ch=getche();fprintf(fp,"\n%c",ch);fclose(fp);if(ch!='Y'&&ch!='y'){for(q=jobs->next;q;q=q->next){if(q->status==0){switch(fitMethod){case'1':order(&empty,0,0);break;case'2':order(&empty,0,1);break;case'3':order(&empty,1,0);break;case'4':order(&empty,1,1);break;}startAddress=allocate(&empty,q->size);if(startAddress!=-1){insertUsedNode(&used,q->id,startAddress);updateJobStatus(&jobs,q->id,1);}}}updateJobFile(jobs);}else{showJobList(jobs);openFile(&fp,"d:\\result.cl","a");fprintf(fp,"\nPleaseinputajobidfromabove.");printf("\nPleaseinputajobidfromabove.");scanf("%d",&id);fprintf(fp,"%d\n",id);getJobInfo(jobs,id,&size,&status);switch(status){case0:printf("\nOk!Thejob'sstatusiscorrect!");fprintf(fp,"\nOk!Thejob'sstatusiscorrect!");fclose(fp);break;case1:printf("\nThejobwasinthememory!");fprintf(fp,"\nThejobwasinthememory!");fclose(fp);gotolabel;case2:printf("\nThejobwasfinished!");fprintf(fp,"\nThejobwasfinished!");fclose(fp);gotolabel;default:printf("\nUnexpectedjobstatus.Pleasecheckyoujobfile.");fprintf(fp,"\nUnexpectedjobstatus.Pleasecheckyoujobfile.");fclose(fp);errorMessage();}switch(fitMethod){case'1':order(&empty,0,0);break;case'2':order(&empty,0,1);break;case'3':order(&empty,1,0);break;case'4':order(&empty,1,1);break;}startAddress=allocate(&empty,size);if(startAddress!=-1){insertUsedNode(&used,id,startAddress);updateJobStatus(&jobs,id,1);updateJobFile(jobs);}