队列应用问题，随机排队问题解答

Question

（1）编写代码实现链式队列或循环队列； （2）应用所实现的队列，设计并完成一个随机任务排队问题的求解。要求： ① 任务由任务号、任务产生时间、任务时长、任务开始处理和任务处理完成时间等信息组成； ② 任务由系统随机产生；任务产生后按产生的顺序排队等候处理。可设平均每5分钟（并非每隔5分名 钟）产生一个新任务，任务时长为1~10分钟范围内。 ③ 系统将依次处理排队等候的任务。 ④ 系统运行超过一定时间后将停止产生新任务； ⑤ 按任务处理顺序，输出处理后的任务信息。 （3）针对所选择的求解问题，编写测试程序完成设计任务的求解，并通过运行结果验证算法和程序设计 的正确性。

Answer 1

运行结果：

#define _CRT_SECURE_NO_WARNINGS

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

//定义结构体
typedef struct _datatype
{
    int id; //任务号
    int time; //任务产生的时间
    int space; //任务持续时间
    int start; //任务开始处理时间
    int end; //任务结束时间
}Task;

//定义链式结构
typedef struct _node
{
    Task task;
    struct _node* next;
}Node,*Queue;

//初始化队列（带头节点的队列）
void InitQueue(Queue* head)
{
    *head = (Queue)malloc(sizeof(Node));
    (*head)->next = NULL;
}

//判断队列是否为空
int QueueEmpty(Queue head)
{
    if (head == NULL)
        return 1;
    if (head->next == NULL)
        return 1;
    return 0;
}

//入队
void EnQueue(Queue head, Task task)
{
    Queue p, t;
    t = (Queue)malloc(sizeof(Node));
    t->task = task;
    t->next = NULL;
    //插入队列
    p = head;
    while (p->next)
        p = p->next;
    p->next = t;
}

//出队
void DeQueue(Queue head, Task* task)
{
    Queue t = 0;
    if (!QueueEmpty(head))
    {
        t = head->next;
        head->next = t->next;
        *task = t->task;
        free(t);
        t = 0;
    }
}

//显示任务信息
void ShowTask(Task t)
{
    printf("id:%d,create_time:%d,start_time:%d,time_space:%d,end_time:%d\n", t.id, t.time,t.start,t.space,t.end);
}




int main()
{
    Queue head = 0;
    Task ntask,dtask;
    int totalTime, curTime = 0, taskOrd = 0, remainTime = 0;
    int lastTime = 0;
    int flag;//决定是否生成任务
    
    srand((unsigned int)time(NULL));//生成随机数种子
    dtask.id = taskOrd;
    InitQueue(&head);//初始化队列

    scanf("%d", &totalTime);

    while (1)
    {
        if (curTime < totalTime)
        {
            flag = rand() % 2;
            if (flag && (curTime - lastTime >= 3))//平均约每5分钟生成1个任务
            {
                lastTime = curTime;
                taskOrd++;
                ntask.id = taskOrd;
                ntask.time = curTime;
                ntask.space = rand() % 10 + 1;//生成1-10的随机数
                
                EnQueue(head, ntask);
            }
            
        }
        
        if (remainTime == 0 && !QueueEmpty(head))
        {
            if (dtask.id != 0)
            {
                dtask.end = curTime;
                ShowTask(dtask);
            }
            dtask.id = 0;
            DeQueue(head, &dtask);
            dtask.start = curTime;
            remainTime = dtask.space;
        }
        else if(remainTime > 0)
        {
            remainTime--;
        }
        curTime++;

        //退出循环
        if (curTime > totalTime && remainTime == 0 && QueueEmpty(head))
            break;
        
    }

    return 0;
}