#include <malloc.h>
#include <stdio.h>
#include <string.h>
#define NULL 0
typedef struct table
  {int address;        /*存儲(chǔ)分區(qū)起始地址*/
   int length;         /*存儲(chǔ)分區(qū)長度*/
   int flag;           /*存儲(chǔ)分區(qū)標(biāo)志，0為空閑，1為被作業(yè)占據(jù)*/
   char name[10];      /*存儲(chǔ)分區(qū)占用標(biāo)志作業(yè)名*/
   struct table *next;
 }node;
int success=0;/*回收成功與否的標(biāo)志*/
node *work;
node *creat()   /*定義函數(shù)，建立主存分配表*/
 { node *head;
   node *p1,*p2;
   int n=0;
   printf("address length flag(0..1)\n");
   p1=p2=(node *)malloc(sizeof(node));
   scanf("%d%d%d",&p1->address,&p1->length,&p1->flag);
   if(p1->flag==1&&p1->length>0)
      {printf("\tinput job_name:");scanf("%s",p1->name);}
   else strcpy(p1->name,"nil");
   head=NULL;
   while (p1->length!=0)
   {n=n+1;
    if (n==1) head=p1;
    else p2->next=p1;
    p2=p1;
    p1=(node *) malloc (sizeof(node));
    scanf("%d%d%d",&p1->address,&p1->length,&p1->flag);
    if(p1->flag==1&&p1->length>0)
      {printf("\t input job_name:");scanf("%s",p1->name);}
    else strcpy(p1->name,"nil");
   }
   p2->next=NULL;
   return(head);
 }
 node *found(node *head,char workn[10])/*查找已分配表中要回收的分區(qū)位置*/
 { node *p,*pre;
   p=head;
   while(p&&strcmp(p->name,workn)!=0)
    {pre=p;p=p->next;}
   if(!p)
     printf("要回收的分區(qū)不存在！\n");
   else   /*保留當(dāng)前分區(qū)信息并刪除當(dāng)前分區(qū)*/
    {printf("要回收的分區(qū)存在！\n");
     success=1;
     work=(node *)malloc(sizeof(node));
     work->address=p->address;work->length=p->length;
     work->flag=0;strcpy(work->name,"nil");work->next=NULL; 
     if(p==head)
        head=head->next;
     else    
        pre->next=p->next;
    }
   return(head);    
 }
 node *release(node *head,node *work) /*分四種情況完成空閑分區(qū)回收過程*/
 { node *q,*pre;
   int addr;
   q=head;success=0;
   while(q)
    {
      if(q->address==work->address+work->length)/*第一種有下鄰*/
        {success++;q->address=work->address;addr=work->address;
         q->length=q->length+work->length; work->length=q->length;
        }
      q=q->next;
    }
   q=head;
   while(q)
    { if(q->address+q->length==work->address)
        {success++;
         if(success==1)/*第二種有下鄰*/
          q->length=q->length+work->length;
         if(success==2)/*第三種有上、下鄰*/
          q->length=q->length+work->length;  
         break;
        }  
      q=q->next;
    }
  if(success==2)/*刪除原下鄰分區(qū)*/
   { q=head;pre=head;
     if(q->address==addr)
       head=head->next;
     else
       {q=q->next;
        while(q->address!=addr)
          {pre=q;q=q->next;}
        pre->next=q->next;
      }
   }
  if(!success)/*第四種無鄰接，直接添加到鏈尾*/
    {pre=head;
     while(pre->next)
        pre=pre->next;
     pre->next=work;
     pre=work;
    }
  return(head);
}
void print(node *head)  /*輸出鏈表信息*/
 { node *p;
   p=head;
   if(head !=NULL)
    do{printf("%d,%d,%d,%s\n",p->address,p->length,p->flag,p->name);
       p=p->next;}
    while(p!=NULL);
 }
void main()
 { int a,i;
   struct table *q,*p,*p1,*q1;
   char workn[10];
   printf("The distributed table is:\n");  
   p=p1=creat();              /*輸入已分配情況表*/
   printf("the free table is:\n");
   q=q1=creat();              /*輸入未分配情況表*/
   printf("the released work name is:");
   scanf("%s",workn);
   p=found(p1,workn);
   if(success)/*待回收分區(qū)存在,則分四種情況將回收分區(qū)加入到空閑分區(qū)表中*/
   q=release(q1,work);
   printf("\ndistribute table is !\n");
   print(p);
   printf("\nfree table is !\n");
   print(q);

}