1、数据结构实验报告表达式求值与任务调度数据结构与程序设计实验实 验 报 告课程名称数据结构与程序设计实验课程编号0906550实验项目名称表达式求值、任务调度学号年级姓名专业计算机科学与技术学生所在学院计算机学院指导教师杨静实验室名称地点21B276哈尔滨工程大学实验报告二实验课名称：数据结构与程序设计实验实验名称：表达式求值、任务调度班级 学号 姓名时间 2016.04.12一、问题描述1. 表达式求值问题表达式是数据运算的基本形式。人们的书写习惯是中缀式， 如：11+22*(7-4)/3。中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀式（如：22 7
2、4 - * 3 / 11 +）和前缀式（如：+11 / * 22 7 4 3）。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。2. 任务调度多用户多任务操作系统中，多个任务同时共享计算机系统资源。为了使多个任务均能够顺利执行，操作系统要按一定的原则对它们进行调度，使它们按一定的次序进行。设只有一个CPU，现有多个任务，它们需要CPU 服务的时间已知。在下列假设下，按平均等待时间最短为原则，设计算法求出任务的执行顺序。忽略任务提交的时间差，即认为各任务同时提交。各任务不同时提交。二、数据结
3、构设计1. 表达式求值：通过算符优先算法来进行表达式求值，为实现算符优先算法，可以使用两个工作栈，一个称为OPTR，用以寄存运算符；另一个称为OPND，用以寄存操作数或运算结果。声明操作数栈：typedef struct NumStack / number stack int *base; int *top; int stacksize; NumStack;声明运算符栈：typedef struct SymStack / symbol stack char *base; char *top; int stacksize; SymStack;2. 任务调度：用结构体存储每个任务的任务顺序，需要时
4、间，提交时间，开始时间，等待时间，结束时间struct task int order, need, t,start,wait,end; T100;三、算法设计1.表达式求值：Precede函数用以比较运算符的优先级，返回，= 或 , -, *, /, %, (, , #, ,=, ; /优先级表格 for(i=0;i9;i+) if(Table0i=a) /纵坐标寻找 break; for(j=0;j=49&s=57) /数字的ASCII码所在范围 /这儿决定了本程序只能计算一位数的四则运算 s-=48; return s; else return 0;/ReadNum求值函数result,
5、其基本求值过程为：1.首先至操作数栈为空栈，表达式起始符#为运算符的栈底元素；2.依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符进行比较优先权后做相应的操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为#）int result(char *a,NumStack *OPND,SymStack *OPTR) /求值 char theta; int b,c,i=0; IntInitStack(OPND); CharInitStack(OPTR); CharPush(OPTR,#); while(1) if(ReadNum(ai) Int
6、Push(OPND,ReadNum(ai+); else if(ai=+|ai=-|ai=*|ai=/|ai=%|ai=#|ai=(|ai=) switch(Precede(ai,CharGetTop(OPTR) case :theta=CharPop(OPTR); /栈顶元素优先权高 c=IntPop(OPND); b=IntPop(OPND); IntPush(OPND,Operate(b,theta,c); break; /switch /else if if(ai=#&CharGetTop(OPTR)=#) printf(The result is %d.n,IntGetTop(OPN
7、D); /打印输出表达式值 return OK; /while/result将中缀表达式转换为前缀表达式：1）求输入串的逆序。2）检查输入的下一元素。3）假如是操作数，把它添加到输出串中。4）假如是闭括号，将它压栈。5）假如是运算符，则i)假如栈空，此运算符入栈。ii)假如栈顶是闭括号，此运算符入栈。iii)假如它的优先级高于或等于栈顶运算符，此运算符入栈。iv)否则，栈顶运算符出栈并添加到输出串中，重复步骤5。6）假如是开括号，栈中运算符逐个出栈并输出，直到遇到闭括号。闭括号出栈并丢弃。7）假如输入还未完毕，跳转到步骤2。8）假如输入完毕，栈中剩余的所有操作符出栈并加到输出串中。9）求输出串
8、的逆序。char perfix(char *a) /此函数将中缀表达式转换为后缀表达式 char ch, b100; int j=0; SymStack r, *R; R = &r; CharInitStack(R); /CharPush(R,#); int i = strlen(a)-2; ch=ai; while(i=0) if(ch=49&ch=57) ch-=48; bj+=ch; if(ch=) CharPush(R,ch); while(ch=+|ch=-|ch=*|ch=/|ch=%) if(*R).top=(*R).base|CharGetTop(R) = )|Precede(
9、ch,CharGetTop(R)=0;t-) /打印输出前缀表达式 if(bt=1&bt=49&ch=57) ch-=48; bj+=ch; ch=a+i; else if(ch=() CharPush(R,ch); ch=a+i; else if(ch=) if(CharGetTop(R)!=() bj+=CharPop(R); else CharPop(R); ch=a+i; else if(ch=+|ch=-|ch=*|ch=/|ch=%) if(Precede(ch,CharGetTop(R)=) / if Top(R) =1&bi=9) printf(%d,bi); else pri
10、ntf(%c,bi); /for printf(.n); return OK;/postfix2任务调度：(1). 同时提交获取每个任务所需的时间，输出按顺序执行时每个任务的序号，开始时间，等待时间和结束时间；按所需时间从小到大排序后，依次执行即为最短等待时间。int cmp(const void *a,const void *b) /相同时间排序, 从小到大 return (*(struct task *)a).need-(*(struct task *)b).need;void sametime(int n) double sum,sum2; int i; for(i=0;in;i+)/输
11、入任务信息 printf(请输入第%d个任务所需要的时间: ,i+1); Ti.t=0; scanf(%d,&Ti.need); Ti.order=i+1; t=0;sum=0; printf(顺序执行:n); printf(序号 开始时间 等待时间 结束时间n); for(i=0;in;i+)/顺序执行任务，输出执行信息 printf(%-7d,i+1); printf(%-7d,t); printf(%-8d,t); t+=Ti.need; printf(%-8d,t); printf(n); sum+=(n-i-1)*Ti.need); printf(n); printf(平均时间最短:
12、n); printf(序号 开始时间 等待时间 结束时间n); qsort(T, n, sizeof(T0), cmp);/按最短时间排序 t=0;sum2=0; for(i=0;iT*(int *)b.need;void dele() int i; printf(%-10d%-10d%-10d%-20dnn,Tque0.order,Tque0.start,Tque0.wait,Tque0.end); for(i=0;irear-1;i+) quei=quei+1; rear-;int check(int num1) int i; Tque0.need-; if(Tque0.need=0) T
13、que0.end=t; dele(); for(i=0;irear;i+) Tquei.wait+; return 1; else for(i=1;irear;i+) Tquei.wait+; return 0; /时间段移动查寻当前队列 void insert(int n) int i,rec; for(i=0;iTn.need) break; rec=i; for(i=rear;irec;i-) quei=quei-1; querec=n; rear+;void difftime(int n)/输入本来按照先后顺序 int tdiff; double sum; int i,j; rear=
14、0;sum=0; for(i=0;in;i+)/输入每个任务信息 printf(请输入第%d个任务提交时刻和执行时间n,i+1,i+1); printf(提交时刻: ); scanf(%d,&Ti.t); printf(执行时间: ); scanf(%d,&Ti.need); Ti.order=i+1; Ti.start=-1;Ti.end=-1;Ti.wait=0; printf(序号 开始时间 等待时间 结束n); que0=0;rear=1;T0.start=0; i=0;t=0;j=1; while(i=Tj.t&jn)/假入在当前任务执行时间内有任务提交 insert(j); /把任
15、务插入到队列 j+; qsort(que, rear, sizeof(que0), comp);/按时间长短排序 if(Tque0.start=-1)/给队列最前点赋起始值 Tque0.start=t; for(i=0;in;i+)/计算出所有等待时间 sum+=Ti.wait; printf(平均等待时间为 %.3lfsnn,sum/n);四、界面设计1.表达式求值需要输入以#结尾的中缀表达式，以提示语句的方式给出。输出注明是什么结果。2.任务调度需要输入任务数，任务需要执行时间，（不同时需要任务提交时间），按平均等待时间最短为原则，输出出任务的执行顺序。五、运行测试与分析1.表达式求值1)
16、.输入一个以#结尾的中缀表达式：2).输出计算结果，后缀表达式以及前缀表达式：3.任务调度：(1). 同时提交i).输入:ii).输出:(2). 不同时间提交i).输入:ii).输出:六、实验收获与思考1熟练掌握栈的定义及使用。2了解表达式求值的转换算法。设计前、后缀表达式求值算法。3设计操作数为多位实数，操作符为加、减、乘、除、求模的中缀表达式求值算法。定义算数符号的优先级。4. 从理论到实践，巩固了学过的知识。七、附录（原程序）1.表达式求值#include #include #include#define STACK_INIT_SIZE 100#define STACKINCREMENT
17、 10#define ERROR 0#define OK 1typedef struct NumStack / number stack int *base; int *top; int stacksize;NumStack;typedef struct SymStack / symbol stack char *base; char *top; int stacksize;SymStack;void IntInitStack(NumStack *S) S-base=(int *)malloc(STACK_INIT_SIZE*sizeof(int); if(!S-base) exit(ERRO
18、R); S-top=S-base; S-stacksize=STACK_INIT_SIZE;/IntInitStackvoid CharInitStack(SymStack *S) S-base=(char *)malloc(STACK_INIT_SIZE*sizeof(char); if(!S-base) exit(ERROR); S-top=S-base; S-stacksize=STACK_INIT_SIZE;/CharInitStackint IntGetTop(NumStack *S) /取栈顶元素 int e; if(*S).top=(*S).base) return 0; e=*
19、(*S).top-1); return e;/IntGetTopchar CharGetTop(SymStack *S) /取栈顶元素 char e; if(*S).top=(*S).base) return 0; e=*(*S).top-1); return e;/IntGetTopint IntPush(NumStack *S,int e) *(*S).top+=e; return OK;/IntPushint CharPush(SymStack *S,char e) *(*S).top+=e; return OK;/CharPushint IntPop(NumStack *S) int e; if(*S).top=(*S).base) return 0; e=*-(*S).top; return e;/IntPopint CharPop(SymStack *S) char e; if(*S).top=(*S).base) return 0; e=*-(*S).top
