www.pudn.com > new_diaodu.rar > new_diaodu.cpp
#include
#include
#include
#include
#include
typedef struct job //job information PCB
{
double arrive_time, excute_time,start_time,finish_time;
struct job *next;
}JOB;
struct t_w // 周转时间t 与带权周转时间w
{
double t;
double w;
};
void Insert_by_arrive_time(JOB *&L,JOB *&m) //jobs will sorted by its arrive time
{
JOB *r = L;
while(r->next)
{
if(m->arrive_time >= r->next->arrive_time )
r = r->next ;
else
break;
}
if(!(r->next))
{
r->next = m;
}
else
{
m->next = r->next; //pay attention there
r->next = m;
}
}
bool Input_the_Jobs_by_Console(JOB *&L,int &job_num) //read the jobs information from the Console
{
JOB *r = L;
cout<<"Input:"<>s->arrive_time ;
if(s->arrive_time < 0.0)
{
delete s;
break;
}
cin>>s->excute_time;
s->next = NULL;
Insert_by_arrive_time(L,s);
++job_num ;
}
if(L->next)
{
JOB *p,*q;
p = L->next;
p->start_time = p->arrive_time;
p->finish_time = p->start_time + p->excute_time;
q = p->next; //pointer p is the prior pointer of q
while(q)
{
if(q->start_time <= p->finish_time)
q->start_time = p->finish_time;
else
q->start_time = q->arrive_time;
q->finish_time = q->start_time + q->excute_time;
p = p->next;
q = q->next;
}
return true;
}
else
return false;
}
bool Input_the_Jobs_by_file(JOB *&L,int &job_num) //read the job information from the file
{
ifstream tfile("input.txt"); //打开一个已经存在的文本文档(创建一个ifstream流对象)
if(!tfile)
{
cerr<<"Can't open the file of input.txt!!"<>s->arrive_time>>s->excute_time;
if(tfile.eof()) //pay attention there. if we don't do that, the file will
{ // read one more data which will do harm to the system
delete s;
break;
}
s->next = NULL;
Insert_by_arrive_time(L,s);
++job_num;
}
if(L->next)
{
JOB *p,*q;
p = L->next;
p->start_time = p->arrive_time;
p->finish_time = p->start_time + p->excute_time;
q = p->next; //pointer p is the prior pointer of q
while(q)
{
if(q->start_time <= p->finish_time)
q->start_time = p->finish_time;
else
q->start_time = q->arrive_time;
q->finish_time = q->start_time + q->excute_time;
p = p->next;
q = q->next;
}
tfile.close();
return true;
}
else
{
tfile.close();
return false;
}
}
void Short_job_first(JOB *&L,JOB *&Short) //we will use short job first
{
JOB *w = Short; // in this fuction, every time when I find the proper crunode,
// I will connect it to the new List, with the head crunode of
JOB *r = L->next; // Short. Then I will delete this crunode from the old list
r->start_time = r->arrive_time;
r->finish_time = r->start_time + r->excute_time;
double finish_time = r->finish_time;
w->next = r;
w = r;
L->next = r->next ;
r = r->next;
JOB *flag;
while(r)
{
double min_excute_time = 99999999.99;
flag = L;
while(r)
{
if(r->arrive_time <= finish_time)
{
if(r->excute_timeexcute_time;
}
r = r->next;
}
else
break;
}
if(flag==L)
{
r = L->next;
r->start_time = r->arrive_time;
r->finish_time = r->start_time + r->excute_time;
finish_time = r->finish_time ;
w->next = r;
w = w->next;
L->next = L->next->next;
r =L->next;
//t->next = r->next;
//r = t->next;
//t = r;
//r = r->next;
}
else
{
JOB *x = L; //delete the pointer of flag from the job list
while(x->next) //I want to insert it into the list of short job first
{
if(x->next == flag) //find the prior point of the pointer of flag
break;
x = x->next;
}
x->next->start_time = finish_time;
x->next->finish_time = x->next->start_time + x->next->excute_time;
finish_time = x->next->finish_time ;
w->next = x->next;
w = w->next;
x->next = x->next->next;
r = L->next;
/*r = t->next;
t = r;
r = r->next;*/
}
}
w->next = NULL;
}
void Rate_high_first(JOB *&L,JOB *&Rate) //in this function I have used the same
{ //algorithm as void Short_job_first(JOB *&L,JOB *&Short)
JOB *v = Rate;
JOB *r = L->next;
r->start_time = r->arrive_time;
r->finish_time = r->start_time + r->excute_time;
double finish_time = r->finish_time;
v->next = r;
v = r;
L->next = r->next ;
r = r->next;
JOB *flag;
while(r)
{
double High_Rate = -100.00; //init the small value
flag = L;
while(r)
{
if(r->arrive_time <= finish_time)
{ //maybe there is something wrong with the defination of wait_time
double wait_time = finish_time - r->arrive_time;
double xiang_ying = wait_time / r->excute_time;
if(xiang_ying >= High_Rate)
{
flag = r;
High_Rate = xiang_ying;
}
r = r->next;
}
else
{
break;
}
}
if(flag==L)
{
r = L->next;
L->next->start_time = L->next->arrive_time;
L->next->finish_time = L->next->start_time + L->next->excute_time;
finish_time = L->next->finish_time ;
v->next = L->next;
v = v->next;
L->next = L->next->next;
r =L->next;
//t->next = r->next;
//r = t->next;
//t = r;
//r = r->next;
}
else
{
JOB *x = L; //delete the pointer of flag from the job list
while(x->next) //I vant to insert it into the list of short job first
{
if(x->next == flag) //find the prior point of the pointer of flag
break;
x = x->next;
}
x->next->start_time = finish_time;
x->next->finish_time = x->next->start_time + x->next->excute_time;
finish_time = x->next->finish_time ;
v->next = x->next;
v = v->next;
x->next = x->next->next;
r = L->next;
/*r = t->next;
t = r;
r = r->next;*/
}
}
v->next = NULL;
}
struct t_w x[3];
void Cal_t_and_w(JOB *q,int kind)
{
JOB *r = q->next;
while(r)
{
double zhou_zhuan_time = r->finish_time - r->arrive_time;
double quan_zhou_zhuan_time = zhou_zhuan_time/r->excute_time;
x[kind].t += zhou_zhuan_time;
x[kind].w += quan_zhou_zhuan_time;
r = r->next;
}
}
void Copy(JOB *L,JOB *&New_L) //copy the list
{
JOB *r = L->next,*t = New_L;
while(r)
{
JOB *s = new JOB;
if(!s)
{
cout<<"Memory apply failed!"<arrive_time = r->arrive_time;
s->excute_time = r->excute_time;
s->next = NULL;
t->next = s;
t = s;
r = r->next;
}
}
int Best() //choose the best
{
t_w min = x[0];
int m = 0;
for(int i=1;i<3;++i)
{
if(x[i].t < min.t && x[i].w < min.w) //maybe there is some errors in my algorithm
{
m = i;
min = x[i];
}
}
return m;
}
void main()
{
JOB *L = new JOB; //Produce the head node
JOB *Short = new JOB;
JOB *Rate = new JOB;
if(!L||!Short||!Rate)
{
cout<<"Memory apply failed"<next = NULL;
Short->next = NULL;
Rate->next = NULL;
int job_num = 0;
cout<<"请输入数据读入方式：1：控制台；2：文件 ";
int choose;
cin>>choose;
bool kind;
if(choose==1)
{
cout<<"with a negative number to finish your input."<next;
JOB *Second_L = new JOB; //Copy the list which was sorted by
if(!Second_L) //arrive_time, I will use it in the function of Short_job_first()
{
cout<<"Memory apply failed"<next = NULL;
Copy(L,Second_L);
JOB *third_L = new JOB; //Copy the list which was sorted by
if(!third_L) //arrive_time, I will use it in the function of Rate_high_first()
{
cout<<"Memory apply failed"<next = NULL;
Copy(L,third_L);
for(int i=0;i<3;++i)
x[i].t = x[i].w = 0.0;
Cal_t_and_w(L,0);
Short_job_first(Second_L,Short);
Cal_t_and_w(Short,1);
Rate_high_first(third_L,Rate);
Cal_t_and_w(Rate,2);
int m = Best();
cout<<"最佳调度为：";
JOB *r;
switch(m)
{
case 0: cout<<"先来先服务。"<next; break;
case 1: cout<<"短作业优先。"<next; break;
case 2: cout<<"响应比优先。"<next; break;
default: cout<<"调度算罚出错！"<arrive_time <<'\t'<<'\t'<excute_time <<'\t'<<'\t'<start_time <<'\t'<<'\t'<finish_time <next;
}
cout<