storage.cpp

最佳适应法构造组织空间分配链表的模拟实现

#include<stdio.h> 
#include<iostream.h>
#include<conio.h>
#include<string.h> 
#include <stdlib.h>
const int total=5000;
const int setaddress=2000;
const int min=100;
const int max=10;
char str[10];
typedef struct mat{
	char name[10];
	long int address;
	long int length;
	mat* next;
	mat* back;
}mat,*jobptr;
typedef struct freearea{
	long address;
	long size;
	freearea *next;
	freearea *back ;
}freearea,*freeptr;
freeptr freep;
jobptr jobp;
long totalfree;
int jobnumber;
void initiation()
{
	freep=new freearea;
	freep->size=total;
	freep->address=setaddress;
	freep->next=NULL;
	freep->back=NULL;
	totalfree=total;
	jobp=NULL;
	jobnumber=0;
}
freeptr bubblesort(freeptr head) 
{ 
freeptr q,tail,p; 
p=new freearea; //这里申请了一个头节点，便于操作， 
p->next = head; //如果有头接点的链表，这种操作不需要了，更简单些 
head = p; 
tail = NULL; //tail后面的是已经排好序的，所以刚开始tail置为NULL 
while(tail != head->next) //冒泡排序需要2重循环，这是外层循环，从后往前循环 
{ 
p = head; 
q =p->next; //p->next是前节点，q->next是后节点 
while(q->next != tail) //内层循环，从前往后循环 
{ 
if (p->next->size< q->next->size) //如果前节点的值<后节点的，则交换 
{ 
p->next = q->next; //这几句交换代码是通过指针完成的，而不是交换节点中值 
q->next = q->next->next; //注意：这几句换的是 p->next和q->next，而不是p和q 
p->next->next = q; 
} 
p = p->next; //继续下一个 
q = p->next; 
} 
tail = q; //如果内层循环一圈，tail向前移动一个 
} 
p = head->next; //全部完成后，头指针为头接点的下一个节点 
delete head; //释放辅助的头节点 
return p; 
}
int ffallocation(int j1 ,char * jn )
{ 
	jobptr jp,jp1,jp2 ; 
    freeptr fp;     
    int ja=-1;
    if( totalfree<j1 ) return ja;
    ja=0;
	fp=freep;        
    while(fp)if (fp->size<j1)fp=fp->next;            
    else {
		jobnumber++;             
        totalfree=totalfree-j1;   
        jp2=new mat ;   
        strcpy(jp2->name,jn);                                 
        jp2->length=j1;                             
        jp2->address=fp->address;                         
        ja=jp2->address ;                           
       if(!jobp)                                 
	   {
		   jp2->next=NULL;                             
		   jp2->back=NULL;
		   jobp=jp2;
	   }
	   else                                        
	   {
		   jp=jobp;                               
		   while((jp)&& (jp2->address<jp->address))
		   {	 
			   jp1=jp;
			   jp=jp->next;
		   }
		   jp2->next=jp;
		   if(!jp)                               
		   {
			   jp2->back=jp1;
			   jp1->next=jp2;
		   }                             
		   else {                                  
			   jp2->back=jp->back;
			   if(jp->back )                                  
				   jp1->next=jp2;                  
			   else jobp=jp2;                       
			   jp->back=jp2;
		   }
	   }
	   if (fp->size-j1<min)                       
	   {
		   if(fp->next) fp->next->back=fp->back;              
		   if(fp->back) fp->back->next=fp->next;
		   else freep=fp->next;                      
	   }
	   else 
	   {
		   fp->size=fp->size-j1;
		   fp->address=fp->address+j1;
	   }
	   return ja;
	}
	return ja;
}
int bfallocation(int j1 ,char * jn )
{ 
	jobptr jp,jp1,jp2 ; 
    freeptr fp,fp1;     
    int ja=-1;
    if( totalfree<j1 ) return ja;
    ja=0;
	fp1=freep;
	fp=bubblesort(fp1);
    while(fp)if (fp->size<j1)fp=fp->next;            
    else {
		jobnumber++;             
        totalfree=totalfree-j1;   
        jp2=new mat ;   
        strcpy(jp2->name,jn);                                 
        jp2->length=j1;                             
        jp2->address=fp->address;                         
        ja=jp2->address ;                           
       if(!jobp)                                 
	   {
		   jp2->next=NULL;                             
		   jp2->back=NULL;
		   jobp=jp2;
	   }
	   else                                        
	   {
		   jp=jobp;                               
		   while((jp)&& (jp2->address<jp->address))
		   {	 
			   jp1=jp;
			   jp=jp->next;
		   }
		   jp2->next=jp;
		   if(!jp)                               
		   {
			   jp2->back=jp1;
			   jp1->next=jp2;
		   }                             
		   else {                                  
			   jp2->back=jp->back;
			   if(jp->back )                                  
				   jp1->next=jp2;                  
			   else jobp=jp2;                       
			   jp->back=jp2;
		   }
	   }
	   if (fp->size-j1<min)                       
	   {
		   if(fp->next) fp->next->back=fp->back;              
		   if(fp->back) fp->back->next=fp->next;
		   else freep=fp->next;                      
	   }
	   else 
	   {
		   fp->size=fp->size-j1;
		   fp->address=fp->address+j1;
	   }
	   return ja;
	}
	return ja;
}
void showyou()
{
	jobptr jp;
	if(jobnumber<=0)
		printf(" NO job\n");
	else {
		printf("    name length (b) address\n");
		jp=jobp;
		while(jp)
		{printf("%s,%10d,%10d\n",jp->name,jp->length,jp->address);
		jp=jp->next;}
	}
	printf("the total left is %d bytes\n",totalfree);

}
void ffcollection(char jn[10])
{
	freeptr fp;
	freeptr fp1;
	freeptr fp2=NULL;
	jobptr jp=jobp;
	int f=0;
	while(jp&&jp->name!=jn)jp=jp->next;
	if(jp)
	{
		jobnumber=jobnumber-1;
		totalfree=totalfree+jp->length;
		if(!freep)
		{
			freep=new(freearea);
			freep->address=jp->address;
			freep->size=jp->length;
			freep->next=NULL;
			freep->back=NULL;
		}
		else 
		{
			fp=freep;
			while(fp&&fp->address<jp->address)
			{
				fp1=fp;fp=fp->next;
			}
			if(fp)
			{
				if(fp->next&&fp->next->address==jp->address+jp->length)
					f=f+1;
				if(fp->back&&jp->address==fp1->address+fp1->size)
					f=f+2;
			}
			else if(jp->address=fp1->address+fp1->size)
				f=f+2;
			switch(f)
			{
			case 0:fp2=new(freearea);
				     fp2->address=jp->address;
				     fp2->size=jp->length;
				     fp->next=fp;
				     if(fp){
					 fp2->back=fp->back;
					   if(fp->back)fp1->next=fp2;
					   else freep=fp2;
					   fp->back=fp2;
					 }
				    else {
						fp2->back=fp1;
						fp1->next=fp2;
					}
			    	break;
			case 1:fp->size=fp->size+jp->length;
				     fp->address=jp->address;break;
			case 2:fp1->size=fp1->size+jp->length;break;
			case 3:fp1->size=fp1->size+jp->length+fp->size;
				     fp1->next=fp->next;
				     if(fp->next)fp->next->back=fp2;
				     delete(fp);
			}
		}
	if (jp==jobp)jobp=jp->next;
	if(jp->next)jp->next->back=jp->back;
	if(jp->back)jp->back->next=jp->next;
	delete(jp);
	}
}
void coalesce()
{
	freeptr fp,fp1;
	jobptr jp;
	long bottom;
	if(jobnumber>0)
	{
		jp=jobp;
		bottom=total+setaddress;
		while(jp)
		{
			jp->address=bottom-jp->length;
			bottom=bottom-jp->length;
			jp=jp->next;
		}
		fp=freep;
		while(fp)
		{
			fp1=fp;
			fp=fp->next;
			delete(fp1);
		}
		freep=new(freearea);
		freep->size=totalfree;
		freep->address=setaddress;
		freep->next=NULL;
		freep->back=NULL;
	}
}
void menu()
{
	long length=0,address;int select=0;char name[10];
	do
	{
		printf("You can select one of the following:");
		printf("(1) Require to be allocate.");
		printf("(2) Require to collecte.");
		printf("(3) check the memory.");
		printf("(4) Quit.");
        printf("You select:");
		scanf("%d",&select);
		switch(select)
		{
		case 1:if (jobnumber>=max)printf("The jobs are too many.");
			    else {
					printf("Enter your job name and length:");scanf("%s%d",name,&length);
					address=bfallocation(length,name);
					switch(address){
					case -1:printf("The memory is full.");break;
					case 0:coalesce;
						   address=bfallocation(length,name);
						   showyou();break;
                    default:showyou();cout<<endl;
					}
				}break;
		case 2:printf("Enter the name of the job:");scanf("%s",name);
			   ffcollection(name);
			   showyou();cout<<endl;break;
		case 3:showyou();cout<<endl;break;
		case 4:exit;
		}
	}while (select<4);
}
void main()
{
	initiation();
	menu();
}