10-9.c

数据结构的经典实现算法

#include"stdio.h"
typedef int T;
typedef struct node{
	int ID;// 作业号
	int time;// 处理时间
}jobnode;
typedef mnode{
	int ID;//机器号
	int avail;// 何时变空闲
}machinenode;
typedef struct  info{
		machinenode data;
		/* 其他数据 */
}minheap;
void LPT(T a[], int n, int m)
{// 构造一个有m 台机器的LPT 调度
	if (n <= m) {
		printf("一台机器调度一个工作\n");
		return ; 
	}
	heapsort(a,n); // 按升序排列
	// 对m 台机器及最小堆进行初始化
	minheap H[m];
	machinenode x;
	for (int i = 1; i <= m; i++) {
		x.avail = 0;
		x.ID = i;
		min_insert (H,x) ;
	}
	// 构造调度
	for (i = n; i >= 1; i--) {
		min_delete(x); // 获取第一台空闲的机器
		x.avail += a[i].time; // 新的可用时间
		min_insert (H,x) ;
}
void main()
{
	T a[10];
	LPT(a,10,9);
}