#include<iostream>
#include<string>
using namespace std;
#define n 30
#define m 30
#define minisize 120
struct file_user
{
	string name;
	float address;
	float lentth;
	int flag;
};file_user used_table[n];
struct file_left
{
	string name;
	float address;
	float length;
	int flag;
};file_left free_table[m];
void allocate(string nam, char job,float xk)//文件分配函數(shù)，為文件name分配大小為xk大小的塊
{
	int i,k;
	float ad;
	k=-1;
	//采用最優(yōu)分配算法分配xk大小的塊
	for(i=0;i<=m;i++)
		if(free_table[i].length>=xk&&free_table[i].flag==1)
			if(k==-1||free_table[i].length<free_table[k].length)//
				k=i;
			if(k==-1)
			{
				cout<<"文件分配失敗!\n"<<endl;
				return;
			}
			if(free_table[k].length-xk<=minisize)
			{
				free_table[k].flag=0;
				ad=free_table[k].address;
				xk=free_table[k].length;
			}
			else 
			{
				free_table[k].length=free_table[k].length-xk;
				ad=free_table[k].address+free_table[k].length;
			}
			//修改已分配的文件表
			i=0;
			while(used_table[i].flag!=0&&i<n) i++;
			if(i>=n)//一分配文件表滿
			{
				cout<<"沒有空閑的文件!\n"<<endl;
				//修正空閑文件表
				if(free_table[k].flag==0)
					free_table[k].flag=1;
				else
				{
					free_table[k].length=free_table[k].length+xk;
					return;
				}
			}
			else//修改已分配文件表
			{
				used_table[i].address=ad;
				used_table[i].lentth=xk;
				used_table[i].flag=job;
				used_table[i].name=nam;
			}
			return;

}
void reclaim(string job)//文件回收函數(shù)
{
	int i,k,j,s=0,t;
	float S,l;
	while((used_table[s].name!=job||used_table[s].flag==0)&&s<n) s++;//尋找一分配分區(qū)表中對(duì)應(yīng)的登記項(xiàng)
	if(s>=n)
	{
		cout<<"該文件不存在，回收失敗!\n"<<endl;
		return;
	}
	used_table[s].flag=0;
	//取得回收文件塊的起事地址s和塊的個(gè)數(shù)l
	S=used_table[s].address;
	l=used_table[s].lentth;
	j=-1;
	k=-1;
	i=0;
	//尋找回收空間的上下相鄰文件塊，上鄰文件表目k，下鄰文件表目j
	while(i<m&&(j==-1||k==-1))
	{
		if(free_table[i].flag==1)
		{
			if(free_table[i].address+free_table[i].length==S)
				k=i;//尋找到上鄰空閑文件塊
			if(free_table[i].address==(S+l))
				j=i;//尋找到下鄰空閑文件塊
		}
		i++;
	}
	if(k!=-1)
		if(j!=-1)//合并三個(gè)空間為一個(gè)空間
		{
			free_table[k].length=free_table[j].length+free_table[k].length+l;
			free_table[j].flag=0;
		}
		else  free_table[k].length=free_table[k].length+l;
	else if(j!=1)//將下鄰空閑空間合并進(jìn)來，組成一個(gè)新的空閑文件組塊
	{
		free_table[j].address=S;
		free_table[j].length+=l;
	}
	else
	{
		t=0;
		while(free_table[t].flag==1&&t<m) t++;//在空閑文件塊中尋找空欄目
		if(t>m)
		{
			cout<<"沒有空閑的文件塊!\n"<<endl;
			used_table[s].flag=used_table[s].flag;//恢復(fù)已分配文件表內(nèi)容
			return;
		}
		free_table[t].address=S;
		free_table[t].length=l;
		free_table[t].flag=1;
	}
	cout<<"文件回收成功!\n"<<endl;
	return;
}
void main()//主函數(shù)
{
	int i;
	float xk;
	char job;
	string name;
	free_table[0].address=10240;
	free_table[0].length=102400;
	free_table[0].flag=1;
	for(i=1;i<m;i++)//空閑文件表初始化
		free_table[i].flag=0;
	for(i=1;i<n;i++)//已分配文件表初始化 
		used_table[i].flag=0;
	while(true)
	{
		char a;
		cout<<"            **********************  菜單   ******************* "<<endl;
		cout<<"            *     0-退出       1-文件分配;       2-文件回收  *"<<endl;
		cout<<"            *     3-瀏覽已分配的文件                         *"<<endl;
		cout<<"            *     請(qǐng)選擇(0--3)                               *"<<endl;
		cout<<"            ************************************************** "<<endl;
		cin>>a;
		if(a=='0') break;
		switch(a)
		{
		case '1': 
			cout<<"請(qǐng)輸入文件的名字..."<<endl;
			cin>>name;
			cout<<"請(qǐng)輸入文件的標(biāo)號(hào)...";
			cout<<"注意：文件的標(biāo)號(hào)是一個(gè)字符，否則系統(tǒng)會(huì)進(jìn)入死循環(huán)!"<<endl;
			cin>>job;
			cout<<"請(qǐng)輸入文件塊的大小... "<<endl;
			cin>>xk;
			allocate(name,job,xk);
			break;
		case '2':cout<<"請(qǐng)輸入你要回收的文件名... "<<endl;
			cin>>name;
			reclaim(name);
			break;
		case '3':
			cout<<"已分配文件的信息如下：  "<<endl;
			cout<<"文件名          起始?jí)K     已用塊的個(gè)數(shù)        標(biāo)志"<<endl;
			for(i=0;i<n;i++)
				if(used_table[i].flag!=0)
					cout<<used_table[i].name<<"\t\t"<<used_table[i].address<<"\t\t"<<used_table[i].lentth<<"\t\t"<<used_table[i].flag<<endl;
			break;
		default:cout<<"輸入有誤，請(qǐng)重新輸入!"<<endl;
		}
	}

}