表达式求值问题、任务调度第三章实验报告

数据结构实验报告实验名称：表达式求值问题、任务调度实验类型：综合性实验班级：20102111学号：2010211102姓名：李晓彬实验日期：20121.问题描述（1）表达式求值问题表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*(7-4)/3。中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀式（如：2274-*3/11+）和前缀式（如：+11/*22–743）。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。（2）任务调度多用户多任务操作系统中，多个任务同时共享计算机系统资源。为了使多个任务均能够顺利执行，操作系统要按一定的原则对它们进行调度，使它们按一定的次序进行。设只有一个CPU，现有多个任务，它们需要CPU服务的时间已知。在下列假设下，按平均等待时间最短为原则，设计算法求出任务的执行顺序。2.数据结构设计（1）表达式求值问题typedefstructnode{charname[10];/*进程标识符*/intprio;/*进程优先数*/intround;/*进程时间轮转时间片*/intcputime;/*进程占用CPU时间*/intneedtime;/*进程到完成还要的时间*/intcount;/*计数器*/charstate;/*进程的状态*/structnode*next;/*链指针*/}PCB;（2）任务调度typedefstructnode{charname[10];/*进程标识符*/intprio;/*进程优先数*/intround;/*进程时间轮转时间片*/intcputime;/*进程占用CPU时间*/intneedtime;/*进程到完成还要的时间*/intcount;/*计数器*/charstate;/*进程的状态*/structnode*next;/*链指针*/}PCB;3.算法设计（1）表达式求值问题1、算数表达式的计算往往是通过栈来实现的。2、读入或扫描表达式的同时，完成运算符和操作数的识别处理。3、识别操作数时，注意将其字符序列转换成整数或实数形式进行存储。4、可以将表达式转换成一棵二叉树，通过先序、中序、后序遍历得到前缀、中缀、后缀表达式。（2）任务调度1、为使各任务平均等待时间最短，如果忽略任务提交的时间差，调度时应该按短任务优先进行调度，即：按照各任务需要CPU服务时间的长短，确定执行顺序，短的在前，长的在后。2、根据上一问题的分析，需要根据任务列表，按任务的CPU服务时间进行排序。3、如果考虑任务提交的时间差，应该按“最短剩余时间”优先进行调度。调度发生在每次任务提交时，从未完成任务中选择需要CPU时间最短的任务。4.界面设计程序开始时出现提示汉字：5.运行、测试与分析1）输入字符串：2）输出结果：6、源代码：1）后缀表达式求值：#includestdio.h#includestdlib.h#includestring.htypedefstructnode{charname[10];/*进程标识符*/intprio;/*进程优先数*/intround;/*进程时间轮转时间片*/intcputime;/*进程占用CPU时间*/intneedtime;/*进程到完成还要的时间*/intcount;/*计数器*/charstate;/*进程的状态*/structnode*next;/*链指针*/}PCB;PCB*finish,*ready,*tail,*run;/*队列指针*/intN;/*进程数*//*将就绪队列中的第一个进程投入运行*/firstin(){run=ready;/*就绪队列头指针赋值给运行头指针*/run-state='R';/*进程状态变为运行态*/ready=ready-next;/*就绪对列头指针后移到下一进程*/}/*标题输出函数*/voidprt1(chara){if(toupper(a)=='P')/*优先数法*/printf(namecputimeneedtimeprioritystate\n);elseprintf(namecputimeneedtimecountroundstate\n);}/*进程PCB输出*/voidprt2(chara,PCB*q){if(toupper(a)=='P')/*优先数法的输出*/printf(%-10s%-10d%-10d%-10d%c\n,q-name,q-cputime,q-needtime,q-prio,q-state);else/*轮转法的输出*/printf(%-10s%-10d%-10d%-10d%-10d%-c\n,q-name,q-cputime,q-needtime,q-count,q-round,q-state);}/*输出函数*/voidprt(charalgo){PCB*p;prt1(algo);/*输出标题*/if(run!=NULL)/*如果运行指针不空*/prt2(algo,run);/*输出当前正在运行的PCB*/p=ready;/*输出就绪队列PCB*/while(p!=NULL){prt2(algo,p);p=p-next;}p=finish;/*输出完成队列的PCB*/while(p!=NULL){prt2(algo,p);p=p-next;}getch();/*压任意键继续*/}/*优先数的插入算法*/insert1(PCB*q){PCB*p1,*s,*r;intb;s=q;/*待插入的PCB指针*/p1=ready;/*就绪队列头指针*/r=p1;/*r做p1的前驱指针*/b=1;while((p1!=NULL)&&b)/*根据优先数确定插入位置*/if(p1-prio=s-prio){r=p1;p1=p1-next;}elseb=0;if(r!=p1)/*如果条件成立说明插入在r与p1之间*/{r-next=s;s-next=p1;}else{s-next=p1;/*否则插入在就绪队列的头*/ready=s;}}/*轮转法插入函数*/insert2(PCB*p2){tail-next=p2;/*将新的PCB插入在当前就绪队列的尾*/tail=p2;p2-next=NULL;}/*优先数创建初始PCB信息*/voidcreate1(charalg){PCB*p;inti,time;charna[10];ready=NULL;/*就绪队列头指针*/finish=NULL;/*完成队列头指针*/run=NULL;/*运行队列指针*/printf(Enternameandtimeofprocess\n);/*输入进程标识和所需时间创建PCB*/for(i=1;i=N;i++){p=malloc(sizeof(PCB));scanf(%s,na);scanf(%d,&time);strcpy(p-name,na);p-cputime=0;p-needtime=time;p-state='w';p-prio=50-time;if(ready!=NULL)/*就绪队列不空调用插入函数插入*/insert1(p);else{p-next=ready;/*创建就绪队列的第一个PCB*/ready=p;}}clrscr();printf(outputofpriority:\n);printf(************************************************\n);prt(alg);/*输出进程PCB信息*/run=ready;/*将就绪队列的第一个进程投入运行*/ready=ready-next;run-state='R';}/*轮转法创建进程PCB*/voidcreate2(charalg){PCB*p;inti,time;charna[10];ready=NULL;finish=NULL;run=NULL;printf(Enternameandtimeofroundprocess\n);for(i=1;i=N;i++){p=malloc(sizeof(PCB));scanf(%s,na);scanf(%d,&time);strcpy(p-name,na);p-cputime=0;p-needtime=time;p-count=0;/*计数器*/p-state='w';p-round=2;/*时间片*/if(ready!=NULL)insert2(p);else{p-next=ready;ready=p;tail=p;}}clrscr();printf(outputofround\n);printf(************************************************\n);prt(alg);/*输出进程PCB信息*/run=ready;/*将就绪队列的第一个进程投入运行*/ready=ready-next;run-state='R';}/*优先数调度算法*/priority(charalg){while(run!=NULL)/*当运行队列不空时，有进程正在运行*/{run-cputime=run-cputime+1;run-needtime=run-needtime-1;run-prio=run-prio-3;/*每运行一次优先数降低3个单位*/if(run-needtime==0)/*如所需时间为0将其插入完成队列*/{run-next=finish;finish=run;run-state='F';/*置状态为完成态*/run=NULL;/*运行队列头指针为空*/if(ready!=NULL)/*如就绪队列不空*/firstin();/*将就绪对列的第一个进程投入运行*/}else/*没有运行完同时优先数不是最大，则将其变为就绪态插入到就绪队列*/if((ready!=NULL)&&(run-prioready-prio)){run-state='W';insert1(run);firstin();/*将就绪队列的第一个进程投入运行*/}prt(alg);/*输出进程PCB信息*/}}/*时间片轮转法*/roundrun(charalg){while(run!=NULL){run-cputime=run-cputime+1;run-needtime=run-needtime-1;run-count=run-count+1;if(run-needtime==0)/*运行完将其变为完成态，插入完成队列*/{run-next=finish;finish=run;run-state='F';run=NULL;if(ready!=NULL)firstin();/*就绪对列不空，将第一个进程投入运行*/}elseif(run-count==run-round)/*如果时间片到*/{run-count=0;/*计数器置0*/if(ready!=NULL)/*如就绪队列不空*/{run-state='W';/*将进程插入到就绪队列中等待轮转*/insert2(run);firstin();/*将就绪对列的第一个进程投入运行*/}}prt(alg);/*输出进程信息*/}}/*主函数*/main(){charalgo;/*算法标记*/clrscr();printf(typethealgorithm:P/R(priority/roundrobin)\n);scanf(%c,&algo);/*输入字符确定算法*/printf(Enterprocessnumber\n);scanf(%d,&N);/*输入进程数*/if(algo=='P'||algo=='p'){create1(algo);/*优先数法*/priority(algo);}el