2.c

这个程序可实现最优二分检索树的构造

#include<stdio.h>
#define LEN1 sizeof(struct free)
#define LEN2 sizeof(struct process)

struct free
{   int address;
    int size;
    struct free *next;
};

struct process
{   int number;
    int location;
    int space;
    struct process *next;
}; 

struct free *init1()
{   struct free *head,*p,*q;
    p=q=(struct free *)malloc(LEN1);
    head=p;
    p->address=14;
    p->size=12;
    p=(struct free *)malloc(LEN1);
    q->next=p;
    p->address=32;
    p->size=96;
    return (head);
}

struct process *init2()
{   struct process *head,*p,*q;
    p=q=(struct process *)malloc(LEN2);
    head=p;
    p->number=1;
    p->location=5;
    p->space=5;
    p=(struct process *)malloc(LEN2);
    q->next=p;
    p->number=3;
    p->location=10;
    p->space=4;
    q=p;
    p=(struct process *)malloc(LEN2);
    q->next=p;
    p->number=2;
    p->location=26;
    p->space=6;
    return (head);
}


int judge(struct process *pointer,int No)
{   int judgement=0;
    struct process *p;
    p=pointer;
    while(p->number!=No&&p->next!=NULL)
       p=p->next;
    if(p->number==No)
       judgement=1;
    return (judgement);      
}


void assign(struct free *h1,struct process *h2)
{   struct free *p1,*p2;
    struct process *q1,*q2;
    int need,number;
    printf("\ninput the space your process need:");
    scanf("%d",&need);
    getchar();
    p1=h1;
    while(p1->size<need&&p1->next!=NULL)
       {   p2=p1;
           p1=p1->next;
       }   
    if(p1->size>=need)
       {   printf("\ninput the number of the process:");
           scanf("%d",&number);
           while(judge(h2,number)==1)
              {   printf("\nThe process is already in the memory!\ninput the correct number:");
                  scanf("%d",&number);  
                  getchar();             
              }
           q1=(struct process *)malloc(LEN2);
           q1->number=number;
           q1->location=p1->address;
           q1->space=need;
           q1->next=NULL;
           q2=h2;
           do
              q2=q2->next;      
           while(q2->next!=NULL);
           q2->next=q1;
           if(p1->size>need)
              {   p1->address+=need;
                  p1->size-=need;
              }   
           else if(p1==h1)
              h1=p1->next;
           else   
              p2->next=p1->next;  
       }   
    else
       printf("\nThere isn't enough space!");   
}



void callback(struct free *h1,struct process *h2)
{   struct free *p1,*p2,*p3;
    struct process *q1,*q2;
    int number;
    printf("\ninput the number of the process:");
    scanf("%d",&number);
    q1=h2;
    while(q1->number!=number&&q1->next!=NULL)
       {   q2=q1;
           q1=q1->next;
       }   
    if(q1->number==number)
       {   if(q1==h2)
              h2=q1->next;
           else
              p2->next=p1->next;
           p1=h1;
           p2=NULL;
           while(p1->address<=q1->location&&p1->next!=NULL)
              {   p2=p1;
                  p1=p1->next;
              }
	   if(p1->address>q1->location)
              {   if(p1->address==(q1->location+q1->space))
                     {   p1->address-=q1->space;
                         p1->size+=q1->space;
                         if((p2->address+p2->size)==q1->location)
                            {   p2->size+=p1->size;
                                p2->next=p1->next;
                            }
                     }
                  else
                     {   if((p2->address+p2->size)==q1->location)
                            p2->size+=q1->space;
                         else
                            {   p3=(struct free *)malloc(LEN1);
                                p3->address=q1->location;
                                p3->size=q1->space;
                                p3->next=p1;
                                if(p1==h1)
                                   h1=p3;
                                else if((p2->address+p2->size)<q1->location)
                                   p2->next=p3;
                            }
                     }
              }
           else
              {   if((p1->address+p1->size)==q1->location)
                     p1->size+=q1->space;
                  else
                     {   p3=(struct free *)malloc(LEN1);
                         p3->address=q1->location;
                         p3->size=q1->space;
                         p3->next=NULL;
                         p1->next=p3;
                     }
              }
       }
    else
       printf("\nThe process is not in the memory!");
}


void menu(struct free *p,struct process *q)
{   int choice;
    char yes_not;
    printf("\ninput your request:(1--assign,2--callback)");
    scanf("%d",&choice);
    getchar();
    if(choice==1)
       assign(p,q);
    else if(choice==2)
       callback(p,q);
    else
       printf("\ninvalid command!");
    printf("\ncontinue or not?y(yes),n(not):");
    scanf("%c",&yes_not);
    getchar();
    if(yes_not=='y')
       menu(p,q);
    else 
       return;          
}


main()
{   struct free *head1;
    struct porcess *head2;
    head1=init1();
    head2=init2();
    menu(head1,head2);
}