数据结构 第3章 中缀表达式.doc

数据结构 实验报告 （第三章） 实验类型：综合性实验 班级： 学号： 姓名： 实验日期：2014年5月24日 一、表达式求值 问题描述 表达式是数据运算的基本形式。– 7 4 3）。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。 2.基本要求 从文件或键盘读入中缀表达式。 容错检验 中缀表达式变后缀表达式 中缀表达式变前缀表达式 后缀表达式求值 前缀表达式求值 任务调度 问题描述 多用户多任务操作系统中，多个任务同时共享计算机系统资源。为了使多个任务均能够顺利执行，操作系统要按一定的原则对它们进行调度，使它们按一定的次序进行。设只有一个CPU，现有多个任务，它们需要CPU服务的时间已知。在下列假设下，按平均等待时间最短为原则，设计算法求出任务的执行顺序。 忽略任务提交的时间差，即认为各任务同时提交。 各任务不同时提交。 基本要求 为任务列表设计数据结构和存储结构。 任务输入，至少包括任务编号及所需CPU的服务时间，任务数不得少于5个。 如果按提交顺序执行，求出每个任务的开始执行时间、终止时间、等待时间和所有任务的平均等待时间。 按平均等待时间最短，设计任务调度算法，输出任务的执行序列；求出每个任务的开始执行时间、终止时间、等待时间和所有任务的平均等待时间；并把结果与上一时间对比。 数据结构设计 要使任务平均等待时间最短，则应遵循所需时间最短的任务优先执行的原则， 当每次提交新的任务时，都应重新排序，找出所需时间最短的任务，则定义了以下链式存储的队列。 typedef struct node { node *next; int number; //任务编号 int time; //所需cpu的服务时间 int tijiao; //提交时间 int wait; //结点的等待时间 }sqList,*sqlistptr; typedef struct linkqueue { sqlistptr front,rear； // 队头、队尾指针 }; 算法设计 任务同时提交 依次执行 计算出每个任务开始执行时时间，并把它们相加求出总和sum，再除以总任务数n便得到平均等待时间。 按等待时间最短方式执行 先对整个队列按所需时间升序排列，再按1）方法计算。 任务不同时提交 依次执行 求出每个任务到达时间a、执行完毕时的时间b、和所需的执行时间c，则s=b-a-c就是每个任务的等待时间。每个任务等待时间的和再除以总任务数n得平均等待时间。 按等待时间最短执行 每次有新任务提交时，都要找出所需时间最短的任务并且把它放在队列第一位， 每过一秒，把第一个任务后面所有任务的等待时间都加一，当队头任务执行完后，出队，并且进入另一个队列k，反复执行上述步骤，直到队列为空，再输出队列k，把所有任务等待时间相加得sum再除以总任务数n得平均等待时间。 主要操作 // 构造一个空队列Q int initqueue(linkqueue Q) { if(!(Q.front=Q.rear=(sqlistptr)malloc(sizeof(node)))) exit(-2); Q.front-next=NULL; return 1; } int queuelength(linkqueue Q) { // 求队列的长度 int i=0; sqlistptr p; p=Q.front; while(Q.rear!=p) { i++; p=p-next; } return i; } // 若队列不空,则用e返回Q的队头元素,并返回1,否则返回0 int gethead(linkqueue Q,node e) { sqlistptr p; if(Q.front==Q.rear) return 0; p=Q.front-next; e.number=p-number; e.time=p-time; e.tijiao=p-tijiao; e.wait=p-wait; return 1; } // 插入元素e为Q的新的队尾元素 int enqueue(linkqueue Q,node e) { sqlistptr p; if(!(p=(sqlistptr)malloc(sizeof(node)))) // 存储分配失败