# include <iostream>
# include<string>
# include<stdlib.h>
using namespace std;
int n;//進程的個數
struct JC
{
	double td;//進程到達時間即提交時間
	double ty;//進程運行時間
	char name;//進程名
	double T;//進程周轉時間
	double W;//進程帶權周轉時間
	double Te;//進程完成時間
	//double TQ;//進程平均周轉時間
	//double WQ;//進程平均帶權周轉時間
	JC *next;
};

JC *create(JC *head)//輸入進程信息
{
	JC *p;
	head=new JC;
	p=head;
	p->next=NULL;
	JC *p1;
	cout<<"請輸入您的進程數:";
	cin>>n;
	cout<<"請依次輸入進程名，到達時間和運行時間:"<<endl;
	for(int i=0;i<n;i++)
	{
		p1=new JC;
		p1->next=NULL;
		cin>>p1->name>>p1->td>>p1->ty;
		p->next=p1;
		p=p->next;
	}
	return head;
}

void print(JC *head)//打印出進程信息
{
	JC *p;
	p=head;
	cout<<"進程名："<<"到達時間："<<"運行時間："<<endl;
	while(p->next!=NULL)
	{
		cout<<p->next->name<<"    "<<p->next->td<<"    "<<p->next->ty<<endl;
		p=p->next;
	}
}

JC *copy(JC *head)//復制鏈表
{
	JC *p1,*p2,*p3,*PHead;

	p2 =new JC;
	p2->next=NULL;
	PHead=p2;

	p1=head;

	while(p1->next!=NULL)
	{
		p3=new JC;
		p3->next=NULL;
		p3->name=p1->next->name;
        p3->td=p1->next->td;
		p3->ty=p1->next->ty;
		p2->next=p3;
		p2=p2->next;
		p1=p1->next;		
	}
	return PHead;
}


void SljPZ(JC *head)//時間片輪轉法計算平均周轉時間和平均帶權周轉時間
{
	double TQ=0.0;//進程平均周轉時間
	double WQ=0.0;//進程平均帶權周轉時間
	JC *p,*q,*p1,*p2;
	q=head;
	p2=p1=p=copy(head);
 	double t=p->next->td;//系統時間
	double a=0.5;//時間片的大小，是可以調整大小的
	double count=0.0;
	while(p->next!=NULL)
	{
		p=p->next;
	}
	p->next=p1->next;
	p1=p->next;
	//p=p->next;
	while(p!=NULL)
	{

		if(p1->td>t) 
		{
			p2=p1;//保存p1上一個節點
			p1=p1->next;
		}
		if(p1->ty>0 && p1->td<=t)
		{ 
			if(p1->ty<=a)
			{
				cout<<"在時間："<<t<<"     "<<p1->name<<"運行"<<endl;  //p1固定為執行的位置
				t=t+p1->ty;
				p1->ty=0;
				cout<<"在時間："<<t<<"     "<<p1->name<<"運行完畢"<<endl;
				p1->Te=0;
			    p1->Te=t;
				q=head;
			    q=q->next;
			    while(q->name!=p1->name)
				{
				   q=q->next;
				}
			    q->Te=p1->Te;
				p2=p1;//保存p1上一個節點
				p1=p1->next;
			}
			else
			{
				cout<<"在時間："<<t<<"     "<<p1->name<<"運行"<<endl;  //p1固定為執行的位置
		        t=t+a;
		        p1->ty=p1->ty-a;
			    p2=p1;//保存p1上一個節點
		        p1=p1->next;
			}
		}
		if(p1->ty==0)
		{
			if(p2==p1)
				p=NULL;
			else
			{
				p2->next=p1->next;
			    delete p1;
			    p1=p2->next;
			}
		}
	}
	cout<<"所有進程都執行完畢!"<<endl;
	q=head;
	q=q->next;
	while(q!=NULL)
	{
		q->T=0;
		q->T=q->Te-q->td;
		count=count+q->T;
		q=q->next;
	}	
	TQ=count/n;//時間片輪轉法進程平均周轉時間
    count=0.0;
	q=head;
	q=q->next;
	while(q!=NULL)
	{
		q->W=0;
		q->W=q->T/q->ty;
		count=count+q->W;
		q=q->next;
	}
	WQ=count/n;//時間片輪轉法進程平均帶權周轉時間
	cout<<"平均周轉時間為："<<TQ<<endl;
	cout<<"平均帶權周轉時間為："<<WQ<<endl;
}	


void QdPZ(JC *head)//強占式短進程優先算法計算平均周轉時間和平均帶權周轉時間
{
	double TQ=0.0;//進程平均周轉時間
	double WQ=0.0;//進程平均帶權周轉時間
	JC *p,*q;
	q=head;
	q=q->next;
	p=copy(head);
	p=p->next;
	double count=0.0;
	double t=p->td;//系統時間
    JC *p1,*p2,*p3;
	p1=p2=p3=p;
	while(p!=NULL)
	{
		p1=p2=p3=p;
		while((p2->next!=NULL)&&(p2->next->td<=t))//選擇當前時間已提交的進程中運行時間最短的執行
		{
			if(p2->next->ty<p1->ty)
			{
				p3=p2;//保存p1上一個節點
				p1=p2->next;
			}
			p2=p2->next;	 	    
		}
		if(t<p1->td) t=p1->td;
		cout<<"時間:"<<t<<"  "<<p1->name<<"  運行!\n"; //p1固定為執行的位置      
		if(p2->next!=NULL&&(p2->next->td<(t+p1->ty)))
		{
			p1->ty=p1->ty-(p2->next->td-t);
			t=p2->next->td;
			cout<<"時間:"<<t<<"  "<<p1->name<<"暫停,剩余運行時間('"<<p1->ty<<"') "<<p2->next->name<<"就緒,此時產生中斷"<<endl;
		}
		else
		{
			p1->Te=0;
			t=t+p1->ty;
			p1->Te=t;
			cout<<"時間:"<<t<<"時刻程序"<<p1->name<<"運行完畢"<<endl;
			p1->ty=0;
			q=head;
	        q=q->next;
			while(q->name!=p1->name)
			{
				q=q->next;
			}
			q->Te=0;
			q->Te=p1->Te;
		}
		
		if(p1->ty==0)
		{
			if(p3==p1)
			    p=p1->next;
			else{
			    p3->next=p1->next;
				delete p1;}
		}
	}
	cout<<"此時所有進程都以執行完畢!"<<endl;
	q=head;
	q=q->next;	
	while(q!=NULL)
	{
		q->T=0;
		q->T=q->Te-q->td;
		count=count+q->T;
		q=q->next;
	}
	TQ=count/n;//強占式短進程優先算法進程平均周轉時間
	cout<<"平均周轉時間為："<<TQ<<endl;
	count=0.0;
	q=head;
	q=q->next;
	while(q!=NULL)
	{
		q->W=0;
		q->W=q->T/q->ty;
		count=count+q->W;
		q=q->next;
	}
	WQ=count/n;//強占式短進程優先算法進程平均帶權周轉時間
	cout<<"平均帶權周轉時間為："<<WQ<<endl;
}


void ZPrint(JC *head)
{
	JC *p;
	p=head;
	int b;
	int c=1;
	while(c==1)
	{
	cout<<"*******************************"<<endl;
	cout<<"*    選擇您要進行的操作序號   *"<<endl;
	cout<<"*1. 時間片輪轉法：            *"<<endl;
	cout<<"*2.搶占式進程優先算法:        *"<<endl;
	cout<<"*3.重新輸入進程信息:          *"<<endl;
    cout<<"*4.退出：                     *"<<endl;
	cout<<"*******************************"<<endl;
	cin>>b;
	system("cls");
	if(b!=1&&b!=2&&b!=3&&b!=4)
		cout<<"您輸入有誤，請重試"<<endl;
	else if(b==1)SljPZ(p);
	else if(b==2)QdPZ(p);
	else if(b==3)
	{
		JC *head;
	    head=NULL;
	    head=create(head);
	    print(head);
		p=head;
	}
	else {c=b;break;}
	c=1;
	}
}

int main()
{
	double count;
	JC *head;
	head=NULL;
	head=create(head);
	print(head);
	ZPrint(head);
	return 0;
}