《数据结构实验报告表达式求值与任务调度》由会员分享，可在线阅读，更多相关《数据结构实验报告表达式求值与任务调度（14页珍藏版）》请在金锄头文库上搜索。
1、数据结构与程序设计实验实验报告课程名称数据结构与程序设计实验课程编号0906550/实验项目名称表达式求值、任务调度学号年级姓名专业计算机科学与技术学生所在学院计算机学院指导教师杨静实验室名称地点21B276哈尔滨工程大学 实验报告二 实验课名称：数据结构与程序设计实验 实验名称：表达式求值、任务调度班级学号姓名时间、问题描述1. 表达式求值问题表达式是数据运算的基本形式。人们的书写习惯是中缀式，女: 11+22*(7-4)/3。中缀式的计算按运算符的优先级及括号优先的原则， 相同级别从左到右进行计算。表达式还有后缀式(如: 22 7 4 - * 3 / 11 + )和前缀式(如: +11 /
2、 * 22- 7 4 3)。后缀表达式和前缀表达式中没有括旦.给计算带来方便。如后缀式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达 式形号式的 转换及不同形式的表达式计算。,2. 任务调度多用户多任务操作系统中，多个任务同时共享计算机系统资源。为了使多个任务均能够顺利执行，操作 系统要按一定的原则对它们进行调度，使它们按一定的次序进行。设只有一个CPU,现有多个任务，它们需要CPU服务的时间已知。在下列假设下，按平均等待时间最短为原则，设计算法 求出任务的执行顺序。忽略任务提交的时间差，即认为各任务同时提交。各任务不同时提交。二、数据结构设计1表达式求值：通过算符优先算法来进行
3、表达式求值，为实现算符优先算法，可以使用两个工作栈，一个称为OPTR 用以寄存运算符；另一个称为OPND,用以寄存操作数或运算结果。声明操作数栈：typedef struct NumStack任务调度：用结构体存储每个任务的任务顺序，需要时间，提交时间，开始时间，等待时间，结束时间struct taskint order, n eed, t,start,wait,e nd;T100;三、算法设计1表达式求值：Precede函数用以比较运算符的优先级，返回或char Precede(char a,char b)int i,j;char Table99=+ - I 55 5 5 5 5 5 5 J
4、 5* 5 5 5 J 55 5 5 J5/ % , ( |# =0;t-)n);return OK;则直接将它们写入后缀表达式中。2 )如果遇到的是开括号“(”，则将它们压入一个操作符栈(不需要与栈顶操作符相比较)，它表明一个新的计算层次的开始，在遇到和它匹配的闭括号“)”时，将栈中的元素弹出来并放入后缀表达式中，直到栈顶元素为“(”时，将栈顶元素“(”弹出(不需要加入后缀表达式)，表明这一层括号内的 操作处理完毕。3) 如果遇到的是操作符，则将该操作符和操作符栈顶元素比较：i) 当所遇到的操作符的优先级小于或等于栈顶元素的优先级时，则取出栈顶元素放入后缀表达式，并弹出该栈顶元素，反复执行直
5、到栈顶元素的优先级小于当前操作 符的优先级(或遇到()；/ii) 当所遇到的操作符的优先级大于栈顶元素的优先级的时则将它压入栈中。4) 重复上述步骤直到遇到中缀表达式的结束符标记 “#”，弹出栈中的所有元素并放入后缀表达式中，转换结束char postfix(char *a) n ” ；)return OK;同时提交获取每个任务所需的时间，输出按顺序执行时每个任务的序号，开始时间，等待时间和结束时间；按所需时间从小到大排序后，依次执行即为最短等待时间。int cmp(c onst void *a,c onst void *b) eed-(*(struct task *)b). need;voi
6、d sametime(i nt n) double sum,sum2;int i; for(i=0;i n;i+)=0;scan f(%d，& Ti. need);Ti.order=i+1;t=0;sum=0;printf(” 顺序执行:n);printf(”序号开始时间等待时间结束时间n);for(i=0;iT*(i nt *)b. need;void dele()int i;prin tf(%-10d%-10d%-10d%-20dnn”,Tque0.order,Tque0.start,Tque0.wait,Tque0.e nd); for(i=0;irear-1;i+)quei=quei+
7、1;rear-;int check(i nt nu m1)/int i;Tque0. need-;if(TqueO. needv=0)TqueO.e nd=t; dele(); for(i=0;ivrear;i+)|Tquei.wait+return 1;for(i=1;iT n . need)break;rec=i;for(i=rear;irec;i-)quei=quei-1;querec=n;rear+;void difftime(i nt n);printf(执行时间：”；)scanf(”d,&Ti.need);Ti.order=i+1;Ti.start=-1;Ti.e nd=-1;Ti
8、.wait=0;printf(序号开始时间等待时间结束n);que0=0;rear=1;T0.start=0;i=0;t=0;j=1;while(i n)t+;&jn )tart=-1)tart=t;for(i=0;i/vx2 t结订果达达費*4尾 式3. -3丄iQIWW r *务 grr rr r务hnkH i 要-ITT 上务.E 要-JTT-J*TT务 bh 需m nr一i 5bh 需话JTT z 务 fr sm鹘嘴对间等待时丄日皿结束时间314994TJIX-主星冃旧青一鳶、主 H円青j IX*2rii)序寻开始时间等待时间樂東2 1021Q1434164618135S2”均等待时间
9、为1-000Al输出六、实验收获与思考1 熟练掌握栈的定义及使用。2 .了解表达式求值的转换算法。设计前、后缀表达式求值算法。3 .设计操作数为多位实数，操作符为加、减、乘、除、求模的中缀表达式求值算法。 定义算数符号的 优先级。4.从理论到实践，巩固了学过的知识。七、附录（原程序）1表达式求值#in clude#in clude#in clude#defi ne STACK_INIT_SIZE 100#defi ne STACKINCREMENT 10#defi ne ERROR 0#defi ne OK 1typedef struct NumStack op=(*S).base) retur n 0; e=*(*S).top-1);return e;op=( *S).base) retur n 0;e=*(*S).top-1); return e;op+=e;return OK;op+=e;return OK;op=(*S).base) retur n 0; e=*-(*s).top; return e;op=(*S).base) retur n 0; e=*-(*S).top; return e;
