3_kebian_release.cpp

登台阶（递归法）已经通过实现方便

#include <malloc.h>
#include <stdio.h>
#include <string.h>
#define NULL 0
typedef struct table
  {int address;        /*存储分区起始地址*/
   int length;         /*存储分区长度*/
   int flag;           /*存储分区标志，0为空闲，1为被作业占据*/
   char name[10];      /*存储分区占用标志作业名*/
   struct table *next;
 }node;
int success=0;/*回收成功与否的标志*/
node *work;
node *creat()   /*定义函数，建立主存分配表*/
 { 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])/*查找已分配表中要回收的分区位置*/
 { node *p,*pre;
   p=head;
   while(p&&strcmp(p->name,workn)!=0)
    {pre=p;p=p->next;}
   if(!p)
     printf("要回收的分区不存在！\n");
   else   /*保留当前分区信息并删除当前分区*/
    {printf("要回收的分区存在！\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) /*分四种情况完成空闲分区回收过程*/
 { 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=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=release(q1,work);
   printf("\ndistribute table is !\n");
   print(p);
   printf("\nfree table is !\n");
   print(q);

}