#include<stdio.h>
#include<stdlib.h>
#define NULL 0
#define getjcb(type) (type*)malloc(sizeof(type))
#define getsub(type)  (type*)malloc(sizeof(type))

int num,num2;  //要調度的作業數和要回收的區域數
int m=0;     //已分配作業數
int flag;     //分配成功標志
int isup,isdown;   //回收區域存在上鄰和下鄰的標志
int is=0;

struct jcb{
		char name[10];
		char state;
		int ntime; //所需時間
	    int size;  //所需空間大小
        int addr;  //所分配分區的首地址
		struct jcb *link;
	} *ready =NULL, *p,*q,*as=NULL;//作業隊列ready,已分配作業隊列as
		typedef struct jcb JCB;
struct subarea{         //分區塊
	    char name[10];
	    int addr;    //分區首地址
		int size;    //分區大小
		char state;
		struct subarea *link;
  } *sub=NULL,*r,*s,*cur; //空閑分區隊列sub,當前分區指針cur
        typedef struct subarea SUB;


void sort() /* 建立對作業按到達時間進行排列的函數,直接插在隊列之尾*/
{
 JCB *first;
 if(ready==NULL)  ready=p;
 else{
   first=ready;
   while(first->link!=NULL)
       first=first->link;
   first->link=p;
   p->link=NULL;
  }
}

void sort3()      /*建立對已分配作業隊列的排列函數,直接插在隊列之尾*/
{
 JCB *fir;
 if(as==NULL) as=q;
 else{
   fir=as;
   while(fir->link!=NULL)
     fir=fir->link;
   fir->link=q;
   q->link=NULL;
  }
  m++;
}

void input() /* 建立作業控制塊函數*/
{
 int i;
 printf("\n請輸入要調度的總作業數:");
 scanf("%d",&num);
 for(i=0;i<num;i++)
  {
   printf("\n作業號No.%d:\n",i);
   p=getjcb(JCB);
   printf("\n輸入作業名:");
   scanf("%s",&p->name);
   printf("\n輸入作業的大小:");
   scanf("%d",&p->size);
   printf("\n輸入作業所需運行時間:");
   scanf("%d",&p->ntime);
   p->state='w';
   p->link=NULL;
   sort(); /* 調用sort函數*/
  }
 printf("\n 按任一鍵繼續......\n");
 getch();
}





void input2()     /*建立要回收區域的函數*/
{
 JCB *k;
 int has;
 q=getjcb(JCB);
 printf("\n輸入區域名(作業名):");
 scanf("%s",&q->name);
 p=as;
 while(p!=NULL)
  {if(strcmp(p->name,q->name)==0)  /*在已分配作業隊列中尋找*/
       {
        q->addr=p->addr;
        q->size=p->size;
        has=1;    /*輸入作業名存在標志位*/
        if(p==as)  as=p->link;    /*在已分配作業隊列中刪除該作業*/
        else
          {k=as;
	       while(k->link!=p)  k=k->link;
	       k->link=k->link->link;      /*刪除*/
	      }
	    printf("輸出該作業首地址:%d\n",q->addr);
        printf("輸出該作業大小:%d\n\n",q->size);
        q->link=NULL;
        break;
       }
   else
       {p=p->link; has=0;}   /*輸入作業名不存在標志*/
  }
 if(has==0)
  {printf("\n輸入作業名錯誤!請重新輸入!\n");
   input2();
  }  
}



void print()
{printf("\n\n\n\n");
 printf("\t\t**************************************\n");
 printf("\t\t\t三.存儲管理實驗演示\n");
 printf("\t\t**************************************\n\n\n");
 printf("\t\t\t\t藍小花\n");
 printf("\t\t\t\t計算機學院\n");
 printf("\t\t\t\t軟件4班\n");
 printf("\t\t\t\t3204007102\n");
 printf("\t\t\t\t2006年12月\n");
 printf("\n\n\n");
 printf("\t\t\t按任意鍵進入演示");
 getch();
 system("cls");
}



void init_sub()       /*初始化空閑分區表*/
{
 r=getsub(SUB);
 strcpy(r->name,"one"); r->addr=5; r->size=10; r->state='n';
 sub=r;
 s=getsub(SUB);
 strcpy(s->name,"two"); s->addr=20; s->size=120; s->state='n';
 sub->link=s;r=s;
 s=getsub(SUB);
 strcpy(s->name,"three"); s->addr=160; s->size=40; s->state='n'; 
 r->link=s;r=s;
 s=getsub(SUB);
 strcpy(s->name,"four"); s->addr=220; s->size=10; s->state='n'; 
 r->link=s;r=s;
 s=getsub(SUB);
 strcpy(s->name,"five"); s->addr=250; s->size=20; s->state='n'; 
 r->link=s;r=s;
 s=getsub(SUB);
 strcpy(s->name,"six"); s->addr=300; s->size=80; s->state='n'; 
 r->link=s;r=s;
 s=getsub(SUB);
 strcpy(s->name,"seven"); s->addr=400; s->size=60; s->state='n'; 
 r->link=s;r=s;
 s=getsub(SUB);
 strcpy(s->name,"eight"); s->addr=480; s->size=300; s->state='n'; 
 r->link=s;r=s;
 s=getsub(SUB);
 strcpy(s->name,"nine"); s->addr=850; s->size=150; s->state='n'; 
 r->link=s;r=s;
 s=getsub(SUB);
 strcpy(s->name,"ten"); s->addr=1200; s->size=60; s->state='n'; 
 r->link=s;
}
//--------------------------------------------------------------------------
void disp()    /*空閑分區表的顯示函數*/
{
 printf("\n\n");
 printf("\t\t 分區          首地址           長度          狀態 \n");
 r=sub;
 while(r!=NULL)
   {
    printf("\t\t %s\t\t%d\t\t%d\t\t%c\n",r->name,r->addr,r->size,r->state);
    r=r->link;
   }
 printf("\n");
}

//--------------------------------------------------------------------------
void disp2()   /*顯示已分配內存的作業表函數*/
{
 printf("\n\n");
 printf("\t\t 作業名         首地址          長度          狀態 \n");
 p=as;
 while(p!=NULL)
   {
    printf("\t\t %s\t\t%d\t\t%d\t\t%c\n",p->name,p->addr,p->size,p->state);
    p=p->link;
   }
 printf("\n\n");
}


//--------------------------------------------------------------------------
void assign2(JCB *pr) /*首次適應作業分區*/
{
 SUB *k;
 r=sub;   /*從空閑表頭開始尋找*/
 while(r!=NULL)
  {
   if(((r->size)>(pr->size))&&(r->state=='n'))   /*有空閑分區大于作業大小的情況*/
	  {
	   pr->addr=r->addr;
	   r->size-=pr->size;
	   r->addr+=pr->size;
	   flag=1;       /*分配成功標志位置1*/
	   q=pr;
	   q->state='r';
	   sort3();     /*插入已分配作業隊列*/
	   printf("作業%s的分區為[%s],首地址為%d.\n",p->name,r->name,pr->addr);
	   break;
	  }
   else if(((r->size)==(pr->size))&&(r->state=='n'))    /*有空閑分區等于作業大小的情況*/
	  {
	   pr->addr=r->addr;
	   flag=1;    /*分配成功標志位置1*/
	   q=pr;
	   sort3();	    /*插入已分配作業隊列*/
	   s=sub;       /*空閑分區已完成分配,應刪除*/
	   while(s->link!=r)  s=s->link;
	   s->link=s->link->link;	 /*刪除空閑分區*/
	   printf("作業%s的分區為[%s],首地址為%d.\n",p->name,r->name,pr->addr);
	   break;
	 }
   else
         {r=r->link;  flag=0;}
}
 if(flag==0)           /*作業過大的情況*/
 {
  printf("作業%s長度過大，內存不足，分區分配出錯!\n",p->name);
  is=1;
 }
}

//--------------------------------------------------------------------------
void reclaim2(JCB *pr)       /*首次適應與循環首次適應區域回收*/
{
 SUB *k;
 r=sub;
 while(r!=NULL)
 {
  if(r->addr==((pr->addr)+(pr->size)))     /*回收區域有下鄰*/
    {
	  pr->size+=r->size;
	  s=sub;
	  isdown=1;     /*下鄰標志位置1*/
	  while(s!=NULL)
	  {
	   if(((s->addr)+(s->size))==(pr->addr))   /*有下鄰又有上鄰*/
	    {
	     s->size+=pr->size;
	     k=sub;
	     while(k->link!=r)  k=k->link;
	     k->link=k->link->link;
	     isup=1;      /*上鄰標志位置1*/
	     break;
	    }
	   else
	    {s=s->link; isup=0;}    /*上鄰標志位置0*/  
	  }
 	  if(isup==0)               /*有下鄰無上鄰*/
	   { 
	     r->addr=pr->addr;
	     r->size=pr->size;
	   }
	 break;	   
    }
 else 
   {r=r->link; isdown=0;}     /*下鄰標志位置0*/
 }  
 if(isdown==0)              /*區域無下鄰*/
    { 
      s=sub;
      while(s!=NULL) 
	  {
	   if(((s->addr)+(s->size))==(pr->addr))   /*無下鄰但有上鄰*/
	     {
	      s->size+=pr->size; 
	      isup=1;        /*上鄰標志位置1*/
	      break;
	     }
	   else 
	     { s=s->link; isup=0;}     /*上鄰標志位置0*/
	  }
	  if(isup==0)           /*無下鄰且無上鄰*/
	       { 
	         k=getsub(SUB);   /*重新生成一個新的分區結點*/
	         strcpy(k->name,pr->name);
	         k->addr=pr->addr;
	         k->size=pr->size;
	         k->state='n';
	         r=sub;
	         while(r!=NULL)
	         {
	          if((r->addr)>(k->addr))   /*按分區首地址排列,回收區域插在合適的位置*/
	            {
	              if(r==sub)       /*第一個空閑分區首址大于回收區域的情況*/
	                  { k->link=r; sub->link=k; }
	              else
	                 {
	                  s=sub;
	                  while(s->link!=r)  s=s->link;    
	                  k->link=r;
	                  s->link=k;
	                 }
	              break;
	            }
	          else r=r->link;
	         }
	        if(r==NULL)     /*所有空閑分區的首址都大于回收區域首址的情況*/
	           {
	             s=sub;
	             while(s->link!=NULL)  s=s->link;
	             s->link=k;
	             k->link=NULL;
	           }
	       }    
    }
 printf("\n區域%s己回收.",pr->name);
}

menu()
{
  printf("\n\n\n\t\t**************************************\n");
 printf("\t\t\t存儲管理實驗演示\n");
 printf("\t\t**************************************\n\n\n");
 printf("\t\t\t 1. 顯示空閑分區                  \n");
 printf("\t\t\t 2. 分配和回收作業                    \n");
 printf("\t\t\t 0. 退出                    \n");
 printf("\t\t\t請選擇你要的操作:");
 switch(getchar())
{
    case '1':
       system("cls");
        disp();
        getch();
        system("cls");
         menu();
        break;
 case '2':
            system("cls");
            printf("\n首次適應算法");
            input();
            printf("\n");
            while(num!=0)
              {
                p=ready;
                ready=p->link;
                p->link=NULL;
                assign2(p);
                num--;
              }
            printf("\n顯示回收后的空閑分區表和已分配作業表...");
            getch();
            printf("\n\t\t              完成分配后的空閑分區表             \n");
            disp();
            printf("\n\t\t                  已分配作業表                   \n");
            disp2();
            if(is==0)
               printf("\n 全部作業已經被分配內存.");
            else printf("\n 作業沒有全部被分配內存.\n");

            printf("\n\n按任意鍵進行區域回收.");
            printf("\n");

            while(as!=NULL)
              {getch();
               input2();
               printf("按任意鍵繼續...");
               getch();
               printf("\n");
               reclaim2(q);
               printf("\n顯示回收后的空閑分區表和已分配作業表...");
               getch();
               printf("\n\t\t              回收后的空閑分區表             \n");
               disp();
               printf("\n\t\t                已分配作業表                 \n");
               disp2();
               printf("\n繼續回收...(Enter)");
              }
            printf("\n所有已分配作業已完成!");
            printf("\nPress any key to return...");
            getch();
            system("cls");
            menu();
            break;

    case '0':
           system("cls");
           break;
           
    default:
           system("cls");
           menu();
           
}
}




void main()     /*主函數*/
{
 init_sub();
 print();
 menu();
}