数据结构课程设计-机器调度

1、 数据结构课程设计报告 实验四：机器调度 1、 设计要求现有n件任务和无线多台的机器，任务可以在机器上得到处理。每件任务的开始时间为Si，完成时间为Fi，Sistart=start;this-end=end;bool operator (const process p1) constreturn startp1.start|(start=p1.start&endp1.end);/重载操作符;B机器类：class machine public:int end;/最后任务的结束时间int count;/该机器的任务数int* pid;/在该机器上任务的pid的数组machine()end=0;pi

2、d=0;count=0;bool operator m1.end;/重载操作符;对算法中的主要方法的描述：贪婪方法：按任务开始时间的非递减次序逐步分配任务，采用冒泡排序for(int i=0;icount;i+)for(int j=0;jcount-i-1;j+)if(!(pjpj+1)swap(pj,pj+1);建立一个机器的优先队列，队列中元素按照机器上最后任务的结束时间由早到晚排序，对于每个任务，若存在可以安排的旧机器，则将该任务分配给该机器，若不存在，则分配一个新的机器for(int i=0;ipi.start)machine *m=new machine();m-pid=new in

3、tcount;m-pidm-count=pi.pid;m-end=pi.end;m-count+;pq.push(*m);continue;machine mm=pq.top();pq.pop();mm.end=pi.end;mm.pidmm.count+=pi.pid;pq.push(mm);continue;最后，输出队列中的所有机器，并将机器中的任务输出int machine_count=0;while(!pq.empty()machine m=pq.top();cout機器+machine_count:flush;for(int i=0;im.count;i+)coutm.pidi,f

4、lush;coutendl;pq.pop();2、 分析与探讨 1、 按照任务的开始时间进行排序（冒泡）的时间复杂性为O(n2)2、机器调度时的时间复杂性为：最坏情况下O(n(n+1)/2+1)附录：源代码#include#includeusing namespace std;class processpublic:int pid;int start;int end;process()start=0;end=0;pid=0;process(int start,int end)this-start=start;this-end=end;bool operator (const process p

5、1) constreturn startp1.start|(start=p1.start&endp1.end);class machine public:int end;int count;int* pid;machine()end=0;pid=0;count=0;bool operator m1.end;inline void swap(int&a,int&b)int c=b;b=a;a=c;int main()int count=0;int start_temp=0;int end_temp=0;cout請輸入任務數和各任務的起始時間和結束時間，以空格分開count;process *p=

6、new processcount;for(int i=0;icount;i+)cout任務(i+1):(pi.start);cin(pi.end);pi.pid=i+1;coutendl;for(int i=0;icount;i+)for(int j=0;jcount-i-1;j+)if(!(pjpj+1)swap(pj,pj+1);priority_queue pq;for(int i=0;ipi.start)machine *m=new machine();m-pid=new intcount;m-pidm-count=pi.pid;m-end=pi.end;m-count+;pq.push(*m);continue;machine mm=pq.top();pq.pop();mm.end=pi.end;mm.pidmm.count+=pi.pid;pq.push(mm);continue;int machine_count=0;while(!pq.empty()machine m=pq.top(