#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<conio.h>

typedef struct qnode
{  int artime,dotime;
   char data;
   struct qnode *next;
}qnode,*queueptr;
typedef struct
{
queueptr front;
queueptr rear;
}linkqueue;
void initqueue(linkqueue &Q)
{
    Q.front=(queueptr)malloc(sizeof(qnode));
    Q.rear=Q.front;
    if(Q.front)  Q.front->next=NULL;
}
void enqueue(linkqueue &Q,char e,int a,int k)
//e为进程名，a到达时间，k执行时间
{
    queueptr p;
    p=(queueptr)malloc(sizeof(qnode));
    if(p)
    { p->data=e;
    p->artime=a;
    p->dotime=k;
    p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
    }
}
void  creatqueue(linkqueue &Q)
{ 

    char ch;
    int a,i;
    i=0;
    printf("请输入进程名及服务时间，以P结束");
    scanf("%c%d",&ch,&a);
    while(ch!='P'){
        i++;
         enqueue(Q,ch,i,a);
        printf("请输入下一个进程成名及服务时间:");
        scanf("%c%d",&ch,&a);
    }
    
}
void  dooperator(linkqueue Q)
{  queueptr  p;
int a[50];
    int i,j;
    i=0;
    p=Q.front;
    while(p)
    {
    Q.front=p->next;
    if(p->dotime--){ 
        i++;
        a[i]=p->data;
        enqueue(Q,p->data,p->artime,p->dotime);
        free(p);}
        else
        {i++;
        a[i]=p->data;
        printf("进程%c的到达时间为%d，服务时间为%d，结束时间为%d",p->data,
            p->artime,p->dotime,i);
        free(p);
            printf("/n");}
        p=Q.front;
    }
        printf("整个进程的执行顺序为：/n");
        for(j=1;j<i;j++)
            printf("%c",a[i]);
        printf("整个进程所需要的时间为:%d",i);
}

 int main()
{
    linkqueue Q;
        initqueue(Q);
  creatqueue(Q);
    dooperator(Q);
  return 0;
 }
注：《数据结构》课程设计任务书

二.    题目：
1、    模拟操作系统中的进程调度
在多任务的操作系统（OS, Operating System）中，同一时间内存在多个程序（作业）同时执行，每个程序都以一个进程（process）来执行。但在计算机中通常只有一个处理机（CPU），为了保证所有程序都能执行，将所有待执行的作业插入进程队列（process queue），然后采用特定的进程调度算法进行调度。
1）（必做）时间片轮转算法
操作系统中仅设置一个进程队列，记录所有待执行的作业。调度算法每次从队列中取出一个进程执行1个时间片（time slice），若进程执行完毕则退出内存。否则，将剩余时间片数减1后，重新插入作业队列末尾等待再次调度。新的进程到达时，插入队列尾。
提示：
每个进程在输入时，需描述下面的特征：
      进程名（可用字符串或用整数简单表示）
      到达时间（可用整数表示，以时间片为单位）
      所需执行时间（整数，以时间片为单位）
2）（选做）多级反馈队列调度算法
为了快速响应短作业，同时可以执行长时间的作业，可以采用下面的调度算法。
（1）OS设置有多个就绪队列（用Qi, i=1,2, ... ,n表示），用于存放等待处理的进程，每个队列的优先权（priority）各不相同，从第一个到最后一个依次降低；
（2）各个队列中进程执行的时间片大小各不相同，优先级越高的队列时间片越小，各个队列的时间片可按下面的规定：每一个队列时间片都比前一个队列时间片长1倍；
（3）当一个进程进入内存后，先放入第一队列Q1末尾，按先来先响应的原则排队等待处理。该进程执行时若在规定的时间片内完成，则处理完毕，可撤离系统，若第一个时间片结束时尚未完成，则该进程转入第二队列Q2的末尾排队等待处理，依次下去，直至转到最后一个队列中。
（4）仅当第i个队列Qi为空，才能调度第i+1队列Q(i+1)中的进程运行。如果第i队列中某进程正在执行，又有新进程进入第1—i-1中任何队列，则此时正在运行的进程放回第i队列末尾，运行新进程。
提示：多级反馈队列调度算法中的每个调度队列需说明：
     队列编号
     优先权（可用整数表示）
     时间片
三、    要求：
1、    以字符序列的形式从终端输入语法正确的，不含变量的整数表达式，利用算符的优先关系，实现算术四则运算，最终给出表达式结果。
2、    进程不少于5个；最终要给出每个进程执行的起止时间、进程的执行顺序和整个服务所需的总的时间；队列的存储方式可采用循环队列、链队列。
选作部分要求：队列不少于4个。
四、    测试数据：
1、9-（2+4*7）/5+3       
2、
进程名    A    B    C    D    E
到达时间    0    1    2    3    4
服务时间    4    3    4    2    4
五.    完成结果要求：  
课程设计报告需写明：学号、班级、组别、同组成员、课程名、起止日期
上交的成果的内容必须由以下三个部分组成，缺一不可
1．    上交源程序：学生按照课程设计的具体要求所开发的所有源程序。源程序要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。（应该放到一个文件夹中）；
2．    上交程序的说明文件：（保存在.txt中）在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名；
3．    课程设计报告：即实验报告，按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成：
a)    需求分析：在该部分中叙述，每个模块的功能要求
b)概要设计　　在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义）。
c）详细设计　各个算法实现的源程序，略写，只给出重要部分。
d）调试分析：　测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。
可以提交至教师邮箱或在机房通过局域网提交。具体格式见附录
六.    参考资料：课本 第三章

附录：
《数据结构》课程设计报告
（一）    问题描述及分析：
    根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？ 
（二）    数据结构描述：
      对问题描述中涉及的操作对象定义相应的数据类型
（三）    主要算法流程描述：
按照以数据结构为中心的原则划分模块，定义主程序模块和各个主要模块的算法，逻辑设计
的结果应写出每个基本操作的功能说明和模块之间的调用关系 
（四）    使用说明：
如何运行，如何输入测试数据，会出现的输出结果等，给出实例。
（五）    调试分析说明：
调试过程中遇到的主要问题有哪些？如何解决的。有何结论？
（六）    特色及改进设想；
（七）    附录：
（1）    列出所有文件名清单并说明；
（2）参考资料列表（书名、网址）；