# include <iostream>
# include <iomanip>
using namespace std;
typedef struct Job //作业
{
int ID;
int time;
}Job;
typedef struct JobNode //作业链表的节点
{
int ID;
int time;
JobNode *next;
}JobNode,*pJobNode;
typedef struct Header //链表的表头
{
int s; //处理机上的时间；
JobNode *next;
}Header,pHeader;
int main()
{
void QuickSort(Job *job,int left,int right); //将job时间排序
void outSort(Job *job,int n); //输出排序
void display(Header *M,int m); //输出每个每台机器处理的工作序号数
int SelectMin(Header *M,int m); //分配作业时选取机器函数；
void solve(Header *head,Job*job,int n,int m); //作业分配函数；
int m,n;
cout<<"\t\t《多机调度问题的算法研究》\n";
cout<<"请输入机器台数m:";
cin>>m;
Header *head=new Header [m]; //动态构建数组结构体，用于记录机器的作业时间；
cout<<"请输入作业个数n:";
cin>>n;
Job *job=new Job [n]; //动态构建作业的数组结构体；
cout<<"\n请按序号输入每个作业调度所需时间：";
for(int i=0;i<n;i++)
{
cin>>job[i].time;
job[i].ID=i;
}
QuickSort(job,0,n-1); //作业排序
outSort(job,n); //输出排序
solve(head,job,n,m); //作业分配
display(head,m); //输出分配
cout<<endl<<endl;
return 0;
}
int SelectMin(Header* M,int m) //选择s最小的机器序号k;
{
int k=0;
for(int i=1;i<m;i++)
{
if(M[i].s<M[k].s)
k=i; //k记录S最小的序号；
}
return k;
}
void QuickSort(Job *job,int left,int right) //从大到小排序
{
int middle=0,i=left,j=right;
Job itemp;
middle=job[(left+right)/2].time;
do
{
while((job[i].time>middle)&&(i<right))
i++;
while((job[j].time<middle)&&(j>left))
j--;
if(i<=j)
{
itemp=job[j];
job[j]=job[i];
job[i]=itemp;
i++;
j--;
}
}while(i<=j);
if(left<j)
QuickSort(job,left,j);
if(right>i)
QuickSort(job,i,right);
}
void display(Header *M,int m) //作业分配输出函数；
{
JobNode *p;
for(int i=0;i<m;i++)
{
cout<<"\n第"<<i+1<<"台机器上处理的工作序号：";
if(M[i].next==0)
continue;
p=M[i].next;
do{
cout<<p->ID+1<<' ';
p=p->next;
}while(p!=0);
}
}
void outSort(Job *job,int n) //作业时间由大到小排序后输出函数；
{
cout<<"\n按工作时间由大到小为:\n时间：\t";
for(int i=0;i<n;i++)
cout<<setw(4)<<job[i].time;
cout<<"\n序号：\t";
for( i=0;i<n;i++)
cout<<setw(4)<<job[i].ID+1;
}
void solve(Header *head,Job*job,int n,int m) //作业分配函数；
{
int k;
for(int i=0;i<m&&i<n;i++)
{
JobNode *jobnode=new JobNode;
jobnode->time=job[i].time;
jobnode->ID=job[i].ID;
jobnode->next=0;
head[i].s=jobnode->time;
head[i].next=jobnode;
}
if(i<=m) //n<m的情况续处理；
{
for(i;i<m;i++)
{
head[i].s=0;
head[i].next=0;
}
}
if(n>m)
{
for(i;i<n;i++)
{
JobNode *p;
JobNode *jobnode=new JobNode;
jobnode->time=job[i].time;
jobnode->ID=job[i].ID;
jobnode->next=0;
k=SelectMin(head,m);
p=head[k].next;
head[k].s+=jobnode->time;
while(p->next!=0)
p=p->next;
p->next=jobnode;
}
}
}
