#include<iostream>
using namespace std;
	struct Node{
		Node *pNext;
		char name;
		int starttime;
		int ytime;       //運行時間
		int level;//進程的優先級
	};
      
 Node*Add(Node*pHead){
int mark=1;
	cout<<"請輸入進程隊列!";
	while(mark==1)
	{
		Node *p,*q;
		p=new Node;
		cout<<"\n添加進程:\n"<<"  進程名:";
		cin>>p->name;
		cout<<"提交時間:";
		cin>>p->starttime;
		cout<<"運行時間:";
		cin>>p->ytime;
		cout<<"  優先級:";
		cin>>p->level;
		p->pNext=NULL;
		if(pHead==NULL)
			pHead=p;
		else
		{
			q=pHead;
			while(q)
			{
				if((q->pNext!=NULL)&&(p->starttime>=q->pNext->starttime))
					q=q->pNext;
				else
					break;
			}
			if(q==pHead&&q->starttime>p->starttime)
			{
				pHead=p;
			    p->pNext=q;
			}
			else
			{	
				p->pNext=q->pNext;
				q->pNext=p;
			}

		}
        cout<<"繼續添加(YES-1，No-0):";
		cin>>mark;
	}
	return pHead;
	}
void compare(Node*pHead){
	Node *p=pHead;
	Node *flag=NULL;
	Node *q=NULL;
	int time;
	Node *p1=p;

//測試
	Node *s=pHead;
	cout<<"生成的進程鏈表如下：\n";
	while(s)
	{
		cout<<"["<<s->name<<","<<s->starttime<<","<<s->ytime<<","<<s->level<<"]\n";
		s=s->pNext;
	}



	int m;
	cout<<"請選擇算法：0-優先級調度算法；1-最高響應比優先算法"<<endl;
	cin>>m;
	if(m==1){                        //最高響應比算法
		double j=0,i=0;
		time=p->starttime;
		while(pHead)
		{
			q=pHead;
			if(time<p->starttime)
				time=p->starttime;
			flag=pHead;
			while(q&&q->starttime<=time)
			{
				if((time-q->starttime)/(q->ytime)>(time-flag->starttime)/(flag->ytime)){
					flag=q;
					j=(time-flag->starttime)/flag->ytime;
				}
				q=q->pNext;
			}
		cout<<"進程名為："<<flag->name<<endl;
		cout<<"進程開始時間為："<<time<<endl;
		cout<<"進程運行時間為："<<flag->ytime<<endl;
		cout<<"進程的優先級為："<<flag->level<<endl;
		i+=(time-flag->starttime+flag->ytime);
		time+=flag->ytime;
		
		if(flag==pHead)
			pHead=pHead->pNext;
		else{
			p1=pHead;
			while(p1->pNext!=flag)
				p1=p1->pNext;
			p1->pNext=flag->pNext;
			delete flag;
			}
		}
		cout<<"周轉時間："<<i<<endl;
	}
	else                               //優先級調度算法
	{
		time=p->starttime;
		double n=0;
		while(pHead)
		{
			q=pHead;
			if(time<p->starttime)
				time=p->starttime;
			flag=pHead;
			while(q&&q->starttime<=time)
			{
				if(q->level>flag->level)
					flag=q;
				q=q->pNext;
			}
		cout<<"進程名為："<<flag->name<<endl;
		cout<<"進程開始時間為："<<time<<endl;
		cout<<"進程運行時間為："<<flag->ytime<<endl;
		cout<<"進程的優先級為："<<flag->level<<endl;
		n+=(time-flag->starttime+flag->ytime);
		time+=flag->ytime;
		if(flag==pHead)
			pHead=pHead->pNext;
		else{
		p1=pHead;
		while(p1->pNext!=flag)
			p1=p1->pNext;
		p1->pNext=flag->pNext;
		delete flag;
		}



	}
			cout<<"周轉時間："<<n<<endl;
}
	}
int main(){
	int i=0;
	Node*pHead=NULL;                              
	
	pHead=Add(pHead);
	
	compare(pHead);
	return 0;
}