#include<stdio.h>
#include<iostream>
using namespace std;




struct  freelink{  //空闲链表
         int  len, address;  //   len为分区长度 
                             //   address为分区起始地址 
         struct  freelink  *next;
  };

struct  busylink{    //忙碌链表
         char name;         //  作业或进程名  name='S' 表示OS占用
         int  len , address;
         struct  busylink  *next;
  };
//全程量
  struct  freelink   *free_head=NULL;    //空闲链队列（带头结点）队首指针         
  struct  busylink   *busy_head=NULL;    //占用区队列队（带头结点）首指针                 
  struct  busylink   *busy_tail=NULL;    //占用区队列队尾指针





   void  start()     /* 设置系统初始状态*/ 
  {    
	  struct freelink *p;
      struct busylink *q;
      free_head=(struct  freelink*)malloc(sizeof(struct freelink));
      free_head->next=NULL;  // 创建空闲链头结点
      busy_head=busy_tail=(struct busylink*)malloc(sizeof(struct  busylink));
      busy_head->next=NULL;  // 创建忙碌链头结点
      p=(struct freelink *)malloc(sizeof(struct freelink));
      p->address=64;
      p->len=640-64; 
      p->next=NULL; //分配操作系统占用的64K内存
      free_head->next =p;
      q=( struct  busylink *)malloc(sizeof(struct busylink));
      q->name='S';  /*  S表示操作系统占用  */
      q->len=64;  q->address=0;  q->next=NULL;
      busy_head->next=q;  busy_tail=q;
  }




      void requireMemo(char name,int require)     /*模拟内存分配*/
	  {
		  struct freelink *p,*u,*v;
          struct busylink *q;
		  if(free_head->next->len<require)
		  {
			  cout<<"Can't allocate"<<endl;
			  exit(1);
		  }
		  else
		  {
			  q=(struct busylink*)malloc(sizeof(struct busylink));
              q->name=name;
              q->address=free_head->next->address;
              q->len=require; 
			  q->next=NULL;
              busy_tail->next=q;
			  busy_tail=q;

		  }
		  p=free_head->next;
          free_head->next=p->next;
		  if(p->len==require)
		  {
			  free(p);
		  }
		  else
		  {
			  p->address=p->address+require;
              p->len=p->len-require;
              u=free_head;
              v=free_head->next;

		  }

		  while((v!=NULL)&&v->len>p->len)
		  {
			  u=v;
              v=v->next;
		  }
		  u->next=p;
          p->next=v;
}





       void  freeMemo(char name)   // 模拟内存回收 
	  {
         struct freelink *p,*u,*v;
         struct busylink *q,*w;
		 q=busy_head;
         w=q->next;
		 while((w!=NULL)&&(w->name!=name))
		 {
			 q=w;
             w=w->next;
		 }
		 if(w==NULL)
			 printf("%c is not exit",name);
		 else if(w==busy_tail)
		 {
			 busy_tail=q;
             q->next=w->next;
             q->len=w->len;
			 q->address=w->address;
			 free(w);
		 }
		 p=( struct freelink*) malloc(sizeof(struct freelink));
         p->len=p->len+q->len;
         p->address=p->address-q->address;
		 u=free_head;
         v=free_head->next;
		 if((v!=NULL)&&(v->len>p->len))
		 {
			 u=v;
             v=v->next;
		 }
		 else
		 {
			 u->next=p;
             p->next=v;

		 }
	  }


      void  printlink()  /* 输出内存空闲情况（自由链的结点） */ 
	  {
		  struct freelink *p;
		  p=free_head->next;
		  cout<<"分区长度        "<<"分区起始地址"<<endl;
		 while(p!=NULL)
		 {
			 cout<<p->len<<"                "<<p->address<<endl;
			 p=p->next;
		 }
	  }





void main()
{
    int n=1;
	start();
	char time;
	while(n)
	{
		cout<<"输入时刻：";
        cin>>time;
		switch(time)
		{
		case'1':
			 requireMemo('A',8); 
	         requireMemo('B',16); 
             requireMemo('C',64); 
	         requireMemo('D',124);
			  printlink();
			  break;
		case'2':
		  	 requireMemo('A',8); 
	         requireMemo('B',16); 
             requireMemo('C',64); 
	         requireMemo('D',124);
			 freeMemo('C');
             printlink();
			 break;
		case'3':
			 requireMemo('A',8); 
	         requireMemo('B',16); 
             requireMemo('C',64); 
	         requireMemo('D',124);
			 freeMemo('C');
			 requireMemo('E',50);
             printlink();
			 break;
		case'4':
			 requireMemo('A',8); 
	         requireMemo('B',16); 
             requireMemo('C',64); 
	         requireMemo('D',124);
			 freeMemo('C');
			 requireMemo('E',50);
			 freeMemo('D');
             printlink();
			 break;
		default:
            cout<<"选择错误!"<<endl;
			break;

		}
	}
}