#数据结构 队列-简单任务调度

Question

现有N个任务等处理，完成每个任务需要的时间分别为T1，T2，...（设为整数），处理任务的机器共有2台，要求将这些任务顺序分配给这两台机器处理，分配的原则是当前哪台机器处理任务的时间短就分配给哪台机器（如果当前两台机器处理完成任务的时间相同，则分配给第1台机器），要求按被处理完时间的先后顺序输出对应的任务号。
提示：设置两个队列，第一个队列存储分配给第一台机器的任务号，第二个队列存储分配给第二台机器的任务号。
函数initQueue完成队列初始化；queueEmpty判断队列是否为空；enQueue实现入队操作；deQueue实现出队操作；getHead获取队头元素；createJobs实现任务执行时间的输入，并将任务加入到相应的队列；dealJobs实现根据任务完成时间出队列，并输出任务编号
#include
#include

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 队列存储空间初始分配量 */

typedef int Status;
//构建任务数据类型
typedef struct {
int id;//任务编号
int starttime;//任务开始时间
int runtime;//任务运行时间
} QElemType;

/*循环队列的顺序存储结构
采用少用一个元素的方法实现，
即队列空间为 MAXSIZE,则有MAXSIZE-1个元素时则认为队列满。
/
typedef struct {
QElemType data[MAXSIZE];
int front; / 头指针 /
int rear; / 尾指针，若队列不空，指向队列尾元素的下一个位置 */
} SqQueue;

Status initQueue(SqQueue &Q);
Status queueEmpty(SqQueue Q);
void enQueue(SqQueue &Q,QElemType e);
Status deQueue(SqQueue &Q,QElemType &e);
QElemType getHead(SqQueue Q);
void createJobs(SqQueue &A,SqQueue &B,int jobsNum);
void dealJobs(SqQueue &A,SqQueue &B);

int main(void) {
int jobsNum; //任务数目
SqQueue A,B;
initQueue(A);
initQueue(B);
scanf("%d", &jobsNum);
createJobs(A,B,jobsNum);
dealJobs(A,B);
return 0;
}

/* 初始化一个空队列Q，头尾指针初始设置 */
Status initQueue(SqQueue &Q) {
Q.front = 0;
Q.rear = 0;
return OK;
}

/* 若队列Q为空队列,则返回TRUE,否则返回FALSE */
Status queueEmpty(SqQueue Q) {
if(Q.front == Q.rear)
return TRUE;
return FALSE;
}

/*只提交以下代码*/
void enQueue(SqQueue &Q,QElemType e) {

}

Status deQueue(SqQueue &Q,QElemType &e) {

}

QElemType getHead(SqQueue Q) {

}

void createJobs(SqQueue &A,SqQueue &B,int jobsNum) {

}

void dealJobs(SqQueue &A,SqQueue &B) {

}
输入
第1行输入一个整数，表示有n个任务
第2行输入n个整数，表示每个任务需要处理的时间
输出
按处理完成的先后顺序输出对应的任务编号（如果两台机器同时完成当前任务，则先显示机器1的任务号）
样例输入
4
10 30 15
样例输出
1 3 2 4

Answer 1

1. #include <stdio.h>
   #include <stdlib.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 队列存储空间初始分配量 */

typedef int Status;
//构建任务数据类型
typedef struct {
int id;//任务编号
int starttime;//任务开始时间
int runtime;//任务运行时间
} QElemType;

/*循环队列的顺序存储结构
采用少用一个元素的方法实现，
即队列空间为 MAXSIZE,则有MAXSIZE-1个元素时则认为队列满。
/
typedef struct {
QElemType data[MAXSIZE];
int front; / 头指针 /
int rear; / 尾指针，若队列不空，指向队列尾元素的下一个位置 */
} SqQueue;

Status initQueue(SqQueue &Q);
Status queueEmpty(SqQueue Q);
void enQueue(SqQueue &Q,QElemType e);
Status deQueue(SqQueue &Q,QElemType &e);
QElemType getHead(SqQueue Q);
void createJobs(SqQueue &A,SqQueue &B,int jobsNum);
void dealJobs(SqQueue &A,SqQueue &B);

int main(void) {
int jobsNum; //任务数目
SqQueue A,B;
initQueue(A);
initQueue(B);
scanf("%d", &jobsNum);
createJobs(A,B,jobsNum);
dealJobs(A,B);
return 0;
}

/* 初始化一个空队列Q，头尾指针初始设置 */
Status initQueue(SqQueue &Q) {
Q.front = 0;
Q.rear = 0;
return OK;
}

/* 若队列Q为空队列,则返回TRUE,否则返回FALSE */
Status queueEmpty(SqQueue Q) {
if(Q.front == Q.rear)
return TRUE;
return FALSE;
}

/只提交以下代码/
void enQueue(SqQueue &Q,QElemType e) {
Q.data[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXSIZE;
}

Status deQueue(SqQueue &Q,QElemType &e) {
if(Q.front==Q.rear)
return ERROR;
e=Q.data[Q.front];
Q.front=(Q.front+1)%MAXSIZE;
return OK;
}

QElemType getHead(SqQueue Q) {
return Q.data[Q.front];
}

void createJobs(SqQueue &A,SqQueue &B,int jobsNum) {
int fa=0,fb=0;//分别记录队列A和B的任务完成时间
int t;
QElemType job;
for(int i = 1; i <= jobsNum; i++)
{
scanf("%d", &t);
job.id=i;
job.runtime=t;
if(fa<=fb)
{
enQueue(A,job);
fa++;
}
else
{
enQueue(B,job);
fb++;
}
}
}

void dealJobs(SqQueue &A,SqQueue &B) {
QElemType temp; //若两个队列都不为空
while(!queueEmpty(A) && !queueEmpty(B)) {
if(getHead(A).runtime<=getHead(B).runtime)
{
deQueue(A,temp);
printf("%d ",temp.id);
}
else
{
deQueue(B,temp);
printf("%d ",temp.id);
}
}
while(!queueEmpty(A)) {
deQueue(A,temp);
printf("%d ",temp.id);
}

while(!queueEmpty(B)) {
    deQueue(B,temp);
        printf("%d ",temp.id);
}

}