#include "stdafx.h"
#include<stdio.h>
#include<iostream.h>
#include<string.h>
#include<iomanip.h>
const int MAXJOB=100;//定義表最大記錄數
typedef struct node
{
 int front;
 int length;
 char data[20];
}job;
job frees[MAXJOB];//定義空閑區表
int free_quantity;
job occupys[MAXJOB];//定義已分配區表
int occupy_quantity;
//初始化函數
void initial()
{
 int i;
 for(i=0;i<MAXJOB;i++)
 {
  frees[i].front=-1;
  frees[i].length=0;
  strcpy(frees[i].data,"free");
  occupys[i].front=-1;
  occupys[i].length=0;
  strcpy(occupys[i].data," ");
 }
 free_quantity=0;
 occupy_quantity=0;
}
//創建空閑分區表
int creatfree()
{
 FILE *fp;
 char fname[20];
 cout<<"請輸入空閑區數據文件來源的文件名:";
 cin>>fname;
 if((fp=fopen(fname,"r"))==NULL){
  cout<<"錯誤,文件打不開,請檢查文件名"<<endl;
 }
 else{
  while(!feof(fp))
  {
   fscanf(fp,"%d\t%d\n",&frees[free_quantity].front,&frees[free_quantity].length);
   free_quantity++;
  }
        cout<<"空閑的分區表已建立！\n";
  return 1;
 }
 return 0;

}
void sort()//將free空間安首地址從小到大的順序排列
{
 int i,j,p;
 for(i=0;i<free_quantity-1;i++)
 {
  p=i;
  for(j=i+1;j<free_quantity;j++)
  {
   if(frees[j].front<frees[p].front)
   {
    p=j;
   }
  }
  if(p!=i)
  {
   frees[free_quantity]=frees[i];
   frees[i]=frees[p];
   frees[p]=frees[free_quantity];
  }
 }
}
//顯示函數
void show()
{
 int i;
 cout<<endl<<"----------------------------------------------------------"<<endl;
 cout<<"當前空閑表:"<<endl;
 cout<<"起始地址    長度      狀態"<<endl;
 for(i=0;i<free_quantity;i++){
  cout.setf(2);
  cout.width(12);
  cout<<frees[i].front;
  cout.width(10);
  cout<<frees[i].length;
  cout.width(8);
  cout<<frees[i].data<<endl;
 }
 cout<<endl<<"----------------------------------------------------------"<<endl;
 cout<<"當前已分配表:"<<endl;
 cout<<"起始地址    長度   占用作業名"<<endl;
 for(i=0;i<occupy_quantity;i++)
 {
  cout.setf(2);
  cout.width(12);
  cout<<occupys[i].front;
  cout.width(10);
  cout<<occupys[i].length;
  cout.width(8);
  cout<<occupys[i].data<<endl;
 }
 cout<<endl<<"----------------------------------------------------------"<<endl;
}
//最先適應分配算法
void assign()
{
 char job_name[20];
 int job_length;
 int i,j,flag,t;
 cout<<"請輸入新申請內存空間的作業名和空間大小:";
 cin>>job_name;
 cin>>job_length;
 flag=0;
 for(i=0;i<free_quantity;i++)
 {
  if(frees[i].length>=job_length)//如果空閑空間I的長度〉作業長度
  {
   flag=1;     //空閑標志位就置1
  }
 }
 if(flag==0)
 {
  cout<<endl<<"對不起,當前沒有能滿足你申請長度的空閑內存,請稍候再試！"<<endl;
 }
 else{
  t=0;
  i=0;
  while(t==0)//為空閑區間的時候
  {
   if(frees[i].length>=job_length)
   {
    t=1;
   }
   i++;//如果空閑空間I的長度不大于作業長度，I加一，判斷下一個空間
  }
  i--;
  occupys[occupy_quantity].front=frees[i].front;//把已用的空閑空間的首地址負給已用空間的首地址
  strcpy(occupys[occupy_quantity].data,job_name);//已用空間的內容為作業名
  occupys[occupy_quantity].length=job_length;//已用空間的長度為作業的長度
  occupy_quantity++;     //已用空間數量加一
  if(frees[i].length>job_length)//如果空間的長度大于作業的長度，
  {
   frees[i].front+=job_length;//空閑空間的起始首地址=原空閑區間的起始長度加作業長度
   frees[i].length-=job_length;//空閑區間的長度=原空閑區間的長度-作業的長度
  }
  else//如果空間的長度=作業的長度
&nbsp; {
   for(j=i;j<free_quantity-1;j++)
   {
    frees[j]=frees[j+1];//空閑區間前移一位
   }
   free_quantity--;//空閑區間的數量減一
   cout<<"內存空間成功:)"<<endl;
  }
 }
}

//撤消作業   
void cancel()
{
 char job_name[20];
 int i,j,flag,p=0;
 int front;
 int length;
 cout<<"請輸入要撤消的作業名:";
 cin>>job_name;
 flag=-1;
 for(i=0;i<occupy_quantity;i++)
 {
  if(!strcmp(occupys[i].data,job_name))//當輸入作業名匹配時
  {
   flag=i;//把i的值賦給flag;
   front=occupys[i].front;//把已用空間的首地址賦給start
   length=occupys[i].length;//把已用空間的長度賦給length
  }
 }
 if(flag==-1)
 {
  cout<<"沒有這個作業名"<<endl;
 }
 else
 {//加入空閑表
  for(i=0;i<free_quantity;i++)
  {
   if((frees[i].front+frees[i].length)==front)//上空
   {
    if(((i+1)<free_quantity)&&(frees[i+1].front==front+length))//下空
    {
     frees[i].length=frees[i].length+frees[i+1].length+length;//第i個空閑區間的長度=第i個空閑區間的長度+第i+1個空閑區間的長度（下空閑區）+length
     for(j=i+1;j<free_quantity;j++)
     {
      frees[j]=frees[j+1];//后移一位
     }
     free_quantity--;//空閑區的數量漸少了一個
     p=1;
    }
    else{
     frees[i].length+=length;//（上空下不空）第i個空閑區間的長度=第i個空閑區間的長度+length，空閑區個數不變
     p=1;
    }
   }
   if(frees[i].front==(front+length))//下空上不空
   {
    frees[i].front=front;//起始地址等于待回收地址
    frees[i].length+=length;//第i個空閑區間的長度=第i個空閑區間的長度+length
    p=1;
   }
  }
  if(p==0)//上下空閑區都不空（直接在空閑區表中找一個空表目，將其內容插入）
  {
   frees[free_quantity].front=front;
   frees[free_quantity].length=length;
   free_quantity++;//空閑區的數量加一
  }
  //刪除分配表中的該作業
  for(i=flag;i<occupy_quantity;i++)
  {
   occupys[i]=occupys[i+1];
  }
  occupy_quantity--;//已用的區的數量
 }
}
void main()
{
 int flag=0;
 int t=1;
 int chioce=0;
 initial();
 flag=creatfree();
 while(flag==1)
 {
  sort();
  cout<<"           可變分區存儲管理模擬系統"<<endl;
     cout<<"   1.申請空間  "<<endl;
        cout<<"   2.撤消作業  "<<endl;
        cout<<"   3.顯示空閑表和分配表  "<<endl; 
        cout<<"   0.退出"<<endl;
  cout<<"請選擇:";
  cin>>chioce;
  switch(chioce)
  {
  case 1:
   assign();
   break;
  case 2:
   cancel();
   break;
  case 3:
   show();
   break;
  case 0:
   flag=0;
   break;
  default:
   cout<<"選擇錯誤!"<<endl;
  }
 }
}