#include<iostream.h>
#include<stdlib.h>
#define Free 0 //空閑狀態(tài)
#define Busy 1 //已用狀態(tài)
#define OK 1    //完成
#define ERROR 0 //出錯
#define MAX_length 32767 //最大內存空間為32767KB
typedef int Status;
int n=0; 
typedef struct freearea//定義一個空閑區(qū)說明表結構
{
int ID;   //分區(qū)號
long size;   //分區(qū)大小
long address; //分區(qū)地址
int state;   //狀態(tài)
}ElemType;

//---------- 線性表的雙向鏈表存儲結構 ------------
typedef struct DuLNode //double linked list
{
ElemType data; 
struct DuLNode *prior; //前趨指針
struct DuLNode *next; //后繼指針
}DuLNode,*DuLinkList;

DuLinkList block_first; //頭結點
DuLinkList block_last; //尾結點

Status alloc(int);//內存分配
Status free(int); //內存回收
Status First_fit(int,int);//首次適應算法
Status Best_fit(int,int); //最佳適應算法
void show();//查看分配
Status Initblock();//開創(chuàng)空間表

Status Initblock()//開創(chuàng)帶頭結點的內存空間鏈表
{
block_first=(DuLinkList)malloc(sizeof(DuLNode));
block_last=(DuLinkList)malloc(sizeof(DuLNode));
block_first->prior=NULL;
block_first->next=block_last;
block_last->prior=block_first;
block_last->next=NULL;
block_last->data.address=0;
block_last->data.size=MAX_length;
block_last->data.ID=0;
block_last->data.state=Free;
return OK;
}

//----------------------- 分 配 主 存 -------------------------
Status alloc(int ch)
{
int ID,request;
cout<<"請輸入作業(yè)(分區(qū)號)："; 
cin>>ID;
cout<<"請輸入需要分配的主存大小(單位:KB)："; 
cin>>request;
if(request<0 ||request==0) 
{
   cout<<"分配大小不合適，請重試!"<<endl;
   return ERROR;
}


   if(First_fit(ID,request)==OK) cout<<"分配成功!"<<endl;
   else cout<<"內存不足，分配失敗!"<<endl;
   return OK;

}
//------------------ 首次適應算法 -----------------------
Status First_fit(int ID,int request)//傳入作業(yè)名及申請量
{
//為申請作業(yè)開辟新空間且初始化
DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode)); 
temp->data.ID=ID; 
temp->data.size=request;
temp->data.state=Busy;

DuLNode *p=block_first->next;
while(p)
{
   if(p->data.state==Free && p->data.size==request)
   {//有大小恰好合適的空閑塊
    p->data.state=Busy;
    p->data.ID=ID;
    return OK;
    break;
   }
   if(p->data.state==Free && p->data.size>request)
   {//有空閑塊能滿足需求且有剩余"
    temp->prior=p->prior;
    temp->next=p;      
    temp->data.address=p->data.address;
    p->prior->next=temp; 
    p->prior=temp;
    p->data.address=temp->data.address+temp->data.size;
    p->data.size-=request;
    return OK;
    break;
   }
   p=p->next;
}
return ERROR;
}



//-----------------------   主 存 回 收   --------------------
Status free(int ID)
{
DuLNode *p=block_first;
while(p)
{
   if(p->data.ID==ID)
   {
    p->data.state=Free;
    p->data.ID=Free;
    if(p->prior->data.state==Free)//與前面的空閑塊相連
    {
     p->prior->data.size+=p->data.size;
     p->prior->next=p->next;
     p->next->prior=p->prior;
    }
    if(p->next->data.state==Free)//與后面的空閑塊相連
    {
    p->data.size+=p->next->data.size;
     p->next->next->prior=p;
     p->next=p->next->next;    
    }
     break; 
   }
   p=p->next;
}
return OK;
}

//--------------- 顯示主存分配情況 ------------------
void show()
{
cout<<"***********-----------------************\n";
cout<<"****       主 存 分 配 情 況        ****\n";
cout<<"***********-----------------************\n";
DuLNode *p=block_first->next;
while(p)
{
   cout<<"分 區(qū) 號：";
   if(p->data.ID==Free) cout<<"Free"<<endl;
   else cout<<p->data.ID<<endl;
   cout<<"起始地址："<<p->data.address<<endl;
   cout<<"分區(qū)大?。?quot;<<p->data.size<<" KB"<<endl;
   cout<<"狀    態(tài)：";
   if(p->data.state==Free) cout<<"空 閑"<<endl;
   else cout<<"已分配!"<<endl;
   cout<<"-----------------------"<<endl;
   p=p->next;
}
}

//----------------------- 主 函 數---------------------------
void main()
{
int ch=1;
cout<<"***********-----------------************\n";
cout<<"****       首 次 適 應 算 法        ****\n";
cout<<"***********-----------------************\n";

if(ch==0) exit(0);
if(n==0) Initblock(); //開創(chuàng)空間表
int choice; //操作選擇標記
while(1)
{
    cout<<"********************************************\n";
    cout<<"**    1: 分配內存        2: 回收內存      **\n";
    cout<<"**    3: 查看分配        0: 返    回      **\n";
    cout<<"********************************************\n";
    cout<<"請輸入您的操作 ：";
    cin>>choice;
   if(choice==1) 
   {
    alloc(ch); // 分配內存
    n++;
   }
   else if(choice==2) // 內存回收
   {
    int ID;
    cout<<"請輸入您要釋放的分區(qū)號：";
    cin>>ID;
    free(ID);
    n++;
   }
   else if(choice==3) 
   {
    show();//顯示主存
    n++;
   }
   else if(choice==0) 
   {
    main(); //退出
    n++;
   }
   else //輸入操作有誤
   {
    cout<<"輸入有誤，請重試!"<<endl;
    continue;
   }
}
}