linknode * rear;//尾指针
linknode * work;//标记指针
public:若图片无法显示请联系QQ752018766
first_fit_link()//初始化
{
head=NULL;
rear=NULL;
work=NULL;
}
~first_fit_link()//析构函数
{
linknode * point1;
while(head!=NULL)
{
point1=head;
head=head->next;
delete point1;
}
}
void init(int address,int size);//初始化建空区表
Job returnjob();//返回链表元素
int allot(int size);//分配,成功返回地址，否则返回无穷大
void free(int address,int size);//释放
bool over();//判断是否输出完节点元素
};
//空区表的建立
void first_fit_link::init(int address,int size)
{
if(head==NULL)//如果是空链，新建一个链
{
head=rear=work=new linknode(size,address,NULL,NULL);//申请新的节点
}
else
{
linknode * point1=head;
linknode * point2;
while(point1!=NULL)
{
if(address<point1->address)
{
point2=new linknode(size,address,NULL,NULL);
if(point1==head)//如果是首部，则改动头指针
{
point2->next=head;
head->forward=point2;
head=point2;
work=point2;
}
else//如果插入点在链中
{
point2->forward=point1->forward;
point2->next=point1;
point1->forward->next=point2;
point1->forward=point2;
}
break;//插入完成，退出
}
else
{
point1=point1->next;//寻找下一个位置
}
}
if(point1==NULL)//如果插入点在链尾，改动尾指针
{
point2=new linknode(size,address,rear,NULL);
rear->next=point2;
rear=point2;
}
}
}
//分配函数，如果分配成功，返回作业地址，否则返回1000
int first_fit_link::allot(int size)
{
int address=1000;
linknode * point1=head;
linknode * point2;
while(point1!=NULL)
{
if(size<point1->size)//如果申请空间小于该节点，对该节点改动
{
address=point1->address;
point1->size=point1->size-size;
point1->address=point1->address+size;
return address;//分配成功，返回address
}
if(size==point1->size)//如果申请空间与该节点大小一致，删除该节点
{
if(point1==head)//如果是头节点
{
address=head->address;
point2=head;
head=head->next;
head->forward=NULL;
work=head;
delete point2;
return address;//分配成功，返回address
}
{
address=rear->address;
point2=rear;
rear=rear->forward;
rear->next=NULL;
delete point2;
}
if(point1!=head&&point1!=rear)
{
address=point1->address;
point2=point1->forward;
linknode * point3=point1->next;
point2->next=point3;
point3->forward=point2;
delete point1;
return address;//分配成功，返回address
}
}
point1=point1->next;//寻找下一个位置
}
if(point1==NULL)
{
return address;//没有合适的空间，分配不成功，返回1000
}
}
//释放空间函数
void first_fit_link::free(int address,int size)
{
linknode * point1=head;
linknode * point2;
while(point1!=NULL)
{
if(address<point1->address)
{
if(point1==head)//如果point1是头指针
{
if((address+size)==point1->address)
{
head->address=address;
head->size=head->size+size;
break;
}
else
{
point2=new linknode(size,address,NULL,head);
head->forward=point2;
head=point2;
break;
}
}
if((point1->forward->address+point1->forward->size)==address)//如果与前一个相邻
{
if((address+size)==point1->address)//如果同时与后一个相邻, 合并三者，删除point1
{
point2=point1->forward;
point2->size=point2->size+size+point1->size;
if(point1==rear)//如果point1是尾指针
{
rear=point2;
delete point1;
break;
}
else
{
point2->next=point1->next;
delete point1;
break;
}
}
else
{ //只与前一个相邻，则与前一个合并
point1->forward->size=point1->forward->size+size;