#include "stdio.h"
#include "stdlib.h"
#include<conio.h>
#define getpch(type)(type*)malloc(sizeof(type))
#define NULL 0

 struct JCB
{   char name[10];
	char state;
	int Arrive_time;
	int Finish_time;
	int Serve_time;
	double Rp;         //高響應優(yōu)先權
	double Turn_time;
	double Carry_time;
    struct JCB *link;
} *ready=NULL,*p;
typedef struct JCB jcb;

void sort()
{
jcb *first,*second;
int insert=0;
if((ready==NULL)||((p->Arrive_time)<(ready->Arrive_time)))
{
	p->link=ready;
	ready=p;
}
else
{
	first=ready;
	second=first->link;
	while(second!=NULL)
	{
		if((p->Arrive_time)<(second->Arrive_time))
		{
			p->link=second;
			first->link=p;
			second=NULL;
			insert=1;
		}
		else
		{
			first=first->link;
			second=second->link;
		}
	}
	if(insert==0)first->link=p;
}
}




void input()
{
 int num,i,t=0;
 printf("\n請輸入作業(yè)個數(shù):");
 scanf("%d",&num);
 for(i=1;i<=num;i++)
 {  
	printf("\n作業(yè) %d",i);
   // p=(jcb*)malloc(sizeof(jcb));
	p=getpch(jcb);
    printf("\n作業(yè)名:");
    scanf("%s",p->name);
    printf("\n到達的時間:");
    scanf("%d",&p->Arrive_time);
    printf("\n作業(yè)運行時間:");
    scanf("%d",&p->Serve_time);
    p->state='w';  p->link=NULL;
	sort();
 }
}


void count()
{
    jcb *p;
	p=ready;
	//double all_turn=0,n=0;
//	double all_carry=0;
	while(p!=NULL)
	{
		p->Turn_time =(p->Finish_time)-(p->Arrive_time) ;
		p->Carry_time =(p->Turn_time)/(p->Serve_time) ;

		p=p->link;
	}

}

void FCFS()//先來先服務
{input();
 jcb *p,*q;
	p=ready;  
	p->Finish_time=p->Arrive_time +p->Serve_time ; 
	//p=p->link;
	while(p->link!=NULL)
	{
		q=p->link;
		q->Finish_time=q->Serve_time +p->Finish_time ;
		p=p->link;
	}
}

void SJF()//短作業(yè)優(yōu)先
{   input();
	int nowtime=0;
	jcb *front=NULL,*back=NULL,*p=NULL,*q=NULL,*temp=NULL;
	nowtime=ready->link->Arrive_time ;
	p=ready;
	while(p->link!=NULL)
	{
		front=p;
		q=front->link;
		while( q!=NULL && q->Arrive_time<=nowtime)
		{
			q=q->link;
			back=q;
		}
		temp=front->link;
		q=front->link;
		while(q!=back)
		{
			if(temp->Serve_time >q->Serve_time )
			{
				temp=q;
			}
			q=q->link;
		}
		if(front->link!=temp)
		{
			q=front;
			while(q->link!=temp)
			{
				q=q->link;
			}
			q->link=temp->link;
			temp->link=front->link;
			front->link=temp;
		}
		temp->Finish_time =nowtime+temp->Serve_time;
		nowtime=temp->Finish_time ;
		p=p->link;
	} 

		p=ready;  
	p->Finish_time=p->Arrive_time +p->Serve_time ; 
	//p=p->link;
	while(p->link!=NULL)
	{
		q=p->link;
		q->Finish_time=q->Serve_time +p->Finish_time ;
		p=p->link;
	}
}


void HRN()//最高響應比
{   input();
	int nowtime=0;
	jcb *front=NULL,*back=NULL,*p=NULL,*q=NULL,*temp=NULL;
	nowtime=ready->link->Arrive_time ;
	p=ready;
	while(p->link!=NULL)
	{
		front=p;
		q=front->link;
		while( q!=NULL && nowtime>=q->Arrive_time)
		{
			q=q->link;
			back=q;
		}
		temp=front->link;
		q=front->link;
		while(q!=back)
		{
			q->Rp=(q->Serve_time+nowtime-q->Arrive_time)/q->Serve_time ;
			q=q->link;
		}
		q=front->link;
		while(q!=back)
		{
			if(temp->Rp<q->Rp )
			{
				temp=q;
			}
			q=q->link;
		}
		if(front->link!=temp)
		{
			q=front;
			while(q->link!=temp)
			{
				q=q->link;
			}
			q->link=temp->link;
			temp->link=front->link;
			front->link=temp;
		}
		temp->Finish_time =nowtime+temp->Serve_time;
		nowtime=temp->Finish_time ;
		p=p->link;
	}  
		p=ready;  
	p->Finish_time=p->Arrive_time +p->Serve_time ; 
	//p=p->link;
	while(p->link!=NULL)
	{
		q=p->link;
		q->Finish_time=q->Serve_time +p->Finish_time ;
		p=p->link;
	}
}

void destroy(jcb *p)
{
	printf("\n進程[%s]已經完成\n",p->name);
	free(p);
}

void print(JCB *pr)
{system("cls"); 
printf("-----------------------------以下是算法的演示--------------------------\n\n");
printf("\n***正在運行的作業(yè)是 :%s ",pr->name);
printf("\n進程名\t到達時間\t服務時間\t狀態(tài)\t周轉時間\t帶權周轉時間\n");
printf("%s\t", pr->name);
printf("%d\t\t",   pr->Arrive_time);
printf("%d\t\t",   pr->Serve_time);
printf("r\t"     );
printf("%f\t",    pr->Turn_time);
printf("%f\t\t",      pr->Carry_time);
printf("\n\n***就緒隊列");
for(pr=ready->link;pr!=NULL;pr=pr->link)
{
printf("\n進程名\t到達時間\t服務時間\t狀態(tài)\n");
printf("%s\t",pr->name);
printf("%d\t\t",pr->Arrive_time);
printf("%d\t\t",pr->Serve_time);
printf("%c\t\n",pr->state);
//printf("%f\t",pr->Turn_time);
//printf("%f\t",pr->Carry_time);
}
}

void xlxfw()//先來先服務
{char ch;
 FCFS();
 count();
while(ready!=NULL)
{
ch=getchar();
system("cls"); 
 p=ready;
 print(p);
 printf("\n按任意鍵繼續(xù)");
 ch=getchar();
ready=p->link;
 destroy(p);

}
printf("\n進程已經完成！\n\n");
ch=getchar();
}


void zdzy() //短作業(yè)優(yōu)先
{char ch;
 SJF();
 count();
while(ready!=NULL)
{
ch=getchar();
system("cls"); 
 p=ready;
 print(p);
 printf("\n按任意鍵繼續(xù)");
 ch=getchar();
ready=p->link;
 destroy(p);

}
printf("\n進程已經完成！\n\n");
ch=getchar();
}

void gxyb()//高響應比
{
char ch;
HRN();
 count();
while(ready!=NULL)
{
ch=getchar();
//system("cls"); 
 p=ready;
 print(p);
 printf("\n按任意鍵繼續(xù)");
 ch=getchar();
ready=p->link;
 destroy(p);

}
printf("\n進程已經完成！\n\n");
ch=getchar();
}


void main()
{int i;
 char ch;
 int flag=1;
 while(flag)
 {
	 printf("\n ------------------------操作系統(tǒng)調度算法演示--------------------------\n");
printf("\n<1>先來先服務(FCFS)\n");
printf("\n<2>最短作業(yè)優(yōu)先(SJF)\n");
printf("\n<3>響應比高者優(yōu)先(HRN)\n\n");
printf("請選擇調度算法:\n");
scanf("%d",&i);
system("cls");
switch(i)
{
case 1:xlxfw();
	break;
case 2:zdzy();
	break;
case 3:gxyb();
	break;
default:
	break;
}
 printf("你是否想繼續(xù)(Y or N)?\n");
 scanf("%s",&ch);getchar();
 system("cls");
 if(ch=='Y'||ch=='y')
 {
	 flag=1;
 }
 else
 {flag=0;
  printf("這個世界很無奈!!!!\n");
 }
}
}