数据结构实验报告~表达式求值和任务调度

1、数据结构与程序设计实验实验报告课程名称实验项目名称数据结构与程序设计实验表:课程编号达式求值、任务调居0906550学号年级姓名专业计算机科学与技术学生所在学院计算机学院指导教师杨静实验室名称地点21B276哈尔滨工程大学实验报告二实验课名称：数据结构与程序设计实验实验名称：表达式求值、任务调度班级学号姓名时间 2016.04.12一、问题描述1.表达式求值问题表达式是数据运算的基本形式。人们的书写习惯是中缀式,如：11+22*(7-4)/3 。中缀式的计算按运算符的先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀式(如:22 7 4 - * 3 / 11 +）和前缀式（+11

2、/* 22- 7 4 3 )。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀式计算时按运算符出现先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。2.任务调度多用户多任务操作系统中，多个任务同时共享计算机系统资源。为了使多个任务均能够顺利执行，操作系统按一定的原则对它们进行调度，使它们按一定的次序进行。设只有一个CPU现有多个任务，它们需要CPU服务E 间已知。在下列假设下，按平均等待时间最短为原则，设计算法求出任务的执行顺序。忽略任务提交的时间差，即认为各任务同时提交。各任务不同时提交。二、数据结构设计1 .表达式求值：通过算符优先算法来进行表达式求值，为

3、实现算符优先算法，可以使用两个工作栈，一个称为 运算符；另一个称为 OPND用以寄存操作数或运算结果。声明操作数栈：typedef struct NumStack / number stackint *base;int *top;int stacksize;NumStack;声明运算符栈：typedef struct SymStack / symbol stackchar *base;char *top;int stacksize;SymStack;2 .任务调度：用结构体存储每个任务的任务顺序，需要时间，提交时间，开始时间，等待时间，结束时间struct taskint order, nee

4、d, t,start,wait,end;T100;三、算法设计1.表达式求值：Precede函数用以比较运算符的优先级，返回'>','='或'<'。char Precede(char a,char b)int i,j;char Table99='','+','-','*'"'%','(',')','#',OPTR用以三'+','>','>'

5、,'<','<','<','<','>','>',;/'-','>',':'*','>',''/','>','>',''%','>','>>''>''>>''>''

6、;>'(','<','<','<','<','<','<','=',' ', ')','>','>','>','>','>',' ','>','>', #'；<'；<'；<'；&

7、lt;'；<'；<'； ','=', 优先级表格for(i=0;i<9;i+)if(Table0i=a) break;for(j=0；j<9；j+)if(Tablej0=b) break;/纵坐标寻找横坐标寻找return Tablej叱 b Table a和操作符theta,计算操作结果并返回。Precedeoperate函数传入操作数 a, b, int Operate(int a,char theta,int b)/计算表达式值：主要是将大的表达式/转化成小的表达式进行逐步求值int c;if(theta='

8、+') c=a+b;else if(theta='-') c=a-b;else if(theta='*') c=a*b;else if(theta='%') c=a%b;else c=a/b;return c;OperatereadNum函数将字符型数字转换为int ReadNum(char s) if(s>=49&&s<=57)/int 型。将字符型的数字转化成int型数字的ASCII码所在范围/这儿决定了本程序只能计算一位数的四则运算s-=48;return s; elsereturn 0;其基本求值过程为

9、:ReadNum 求值函数result,1.首先至操作数栈为空栈，表达式起始符'#为运算符的栈底元素;2.依次读入表达式中每个字符，若是操作数则进 后做相应的操作，直至整个表达式求值完毕(即 int result(char *a,NumStack *OPND,SymStack *OPTR)char theta;OPN微，若是运算符则和 OPTRt的栈顶运算符进行比较优先OPTRt的栈顶元素和当前t入的字符均为#')/求值int b,c,i=0;IntlnitStack(OPND);CharlnitStack(OPTR);CharPush(OPTR,'#');wh

10、ile(1)if(ReadNum(ai)IntPush(OPND,ReadNum(ai+); elseif(ai='+'l|ai=T|ai='*'11ai='/'11ai='%'11ai='#'l|ai='('l|ai=')') switch(Precede(ai,CharGetTop(OPTR) case '<':CharPush(OPTR,ai+);break;case '=':CharPop(OPTR);i+;break;case '

11、;>':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(OPND);/打印输出表达式值return OK; /while /result 将中缀表达式转换为前缀表达式： 1)求输入串的逆序

12、。 2)检查输入的下一元素。3)假如是操作数，把它添加到输出串中。4)假如是闭括号，将它压栈。5)假如是运算符，则i)假如栈空，此运算符入栈。ii)假如栈顶是闭括号，此运算符入栈。iii)假如它的优先级高于或等于栈顶运算符，此运算符入栈。iv)否则，栈顶运算符出栈并添加到输出串中，重复步骤5。6)假如是开括号，栈中运算符逐个出栈并输出，直到遇到闭括号。闭括号出栈并丢弃。7)假如输入还未完毕，跳转到步骤2。8)假如输入完毕，栈中剩余的所有操作符出栈并加到输出串中。9)求输出串的逆序。char perfix(char *a) /此函数将中缀表达式转换为后缀表达式char ch, b100;int

13、j=0;SymStack r, *R;R = &r;CharlnitStack(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='*'11ch='/'11ch='%')if(*R).top=(*R).base|CharGe

14、tTop(R) = ')'|Precede(ch,CharGetTop(R)='<') CharPush(R,ch);break;elsebj+=CharPop(R);if(ch='(')while(CharGetTop(R)!=')')bj+=CharPop(R);CharPop(R);ch=a-i;/whilewhile(*R).top != (*R).base)bj+=CharPop(R);bj = '0'printf("The changed pre expression is:"

15、);int t=strlen(b)-1;for(t;t>=0;t-)打印输出前缀表达式if(bt>=1&&bt<=9) printf("%d",bt);elseprintf("%c",bt);/forprintf(".n");return OK;/prefix将中缀表达式转换为后缀表达式：算法描述：将中缀表达式转换为等价的后缀表达式的过程要使用一个栈放“(”，具体可以按照下面的方式进行。1)从左到右一次扫描中缀表达式的每一个字符，如果是数字字符和圆点".”则直接将它们写入后缀表达式中。2)如

16、果遇到的是开括号“(”，则将它们压入一个操作符栈(不需要与栈顶操作符相比较)，它表明一个新的计算次的开始，在遇到和它匹配的闭括号“)”时，将栈中的元素弹出来并放入后缀表达式中，直到栈顶元素为“(”将栈顶元素“(”弹出(不需要加入后缀表达式)，表明这一层括号内的操作处理完毕。3)如果遇到的是操作符，则将该操作符和操作符栈顶元素比较：i) 当所遇到的操作符的优先级小于或等于栈顶元素的优先级时，则取出栈顶元素放入后缀表达式，并弹出该栈顶元素，反复执行直到栈顶元素的优 先级小于当前操作符的优先级(或遇到()；ii) 当所遇到的操作符的优先级大于栈顶元素的优先级的时则将它压入栈中。4)重复上述步骤直到遇

17、到中缀表达式的结束符标记“#"，弹出栈中的所有元素并放入后缀表达式中，转换结束char postfix(char *a) /此函数将中缀表达式转换为后缀表达式char ch, b100;int i=0, j=0;SymStack r, *R;R = &r;CharInitStack(R);CharPush(R,'#');ch=ai;while(ch!='#')if(ch>=49&&ch<=57)ch-=48;bj+=ch;ch=a+i;else if(ch='(') CharPush(R,ch); c

18、h=a+i;else if(ch=')')if(CharGetTop(R)!='(') bj+=CharPop(R); elseCharPop(R);ch=a+i;else if(ch='+'|ch='-'|ch='*'11ch='/'11ch='%')if(Precede(ch,CharGetTop(R)片'<') if Top(R) < ch CharPush(R,ch);ch=a+i;else bj+=CharPop(R);/whilech=Char

19、Pop(R);while(ch!='#')bj=ch;j+；ch=CharPop(R);b昨'#'；printf("The changed expression is:");for(i=0;bi!='#'i+)/打印输出后缀表达式if(bi>=1&&bi<=9)printf("%d",bi);elseprintf("%c",bi);/forprintf(".n");return OK;postfix2.任务调度：(1) .同时提交获取每个任

20、务所需的时间，输出按顺序执行时每个任务的序号，开始时间，等待时间和结束时间；按所需时间从 到大排序后，依次执行即为最短等待时间。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;i<n;i+)/输入任务信息printf("请输入第外任务所需要的时间：",i+1);Ti.t=0;scanf("%d&qu

21、ot;,&Ti.need);Ti.order=i+1;t=0;sum=0;printf("顺序执行：n");printf("序号开始时间等待时间结束时间n");for(i=0;i<n;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);prin

22、tf("n");printf(" 平均时间最短：n");printf(" 序号开始时间等待时间结束时间n");qsort(T, n, sizeof(T0), cmp);/按最短时间排序t=0;sum2=0;for(i=0;i<n;i+)/排序后输出任务执行信息printf("%-7d",Ti.order);printf("%-7d",t);printf("%-8d",t);t+=Ti.need;printf("%-8dn",t);printf(&qu

23、ot;n");sum2+=(n-i-1)*Ti.need);printf("顺序执行等待平均时间为.3吊n",sum/n);printf("最短等待平均时间为.3lfn",sum2/n);(2) .不同时间提交int comp(const void *a,const void *b)/不同时间排序return T*(int *)a.need>T*(int *)b.need;void dele()int i;printf("%-10d%-10d%-10d%-20dnn",Tque0.order,Tque0.start,T

24、que0.wait,Tque0.en for(i=0;i<rear-1;i+)quei=quei+1;rear-;int check(int num1)int i;Tque0.need-;if(Tque0.need<=0)Tque0.end=t;dele();for(i=0;i<rear;i+)Tquei.wait+;return 1;elsefor(i=1;i<rear;i+)Tquei.wait+;return 0;/时间段移动查寻当前队列void insert(int n)int i,rec;for(i=0;i<rear;i+)if(Tquei.need&g

25、t;Tn.need)break;rec=i;for(i=rear;i>rec;i-)quei=quei-1;querec=n;rear+;void difftime(int n)/输入本来按照先后顺序int tdiff;double sum;int i,j;rear=0;sum=0;for(i=0;i<n;i+)/输入每个任务信息printf("请输入第外任务提交时刻和执行时间n",i+1,i+1);printf("提交时刻:");scanf("%d”,&Ti.t);printf("执行时间:");sca

26、nf("%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<n)t+;时间移动i+=check(tdiff);/时间移动后检查是否有完成的任务，并且就算等待时间if(t>=Tj.t&&j<n)假入在当前任务执行时间内有任务提交insert(j); /把任务插入到队列j+;qsort(que, rear, siz

27、eof(que0), comp);/按时间长短排序 if(Tque0.start=-1)给队列最前点赋起始值Tque0.start=t; for(i=0;i<n;i+)/计算出所有等待时间sum+=Ti.wait; printf("平均等待时间为 .3lfsnn",sum/n); 四、界面设计 1.表达式求值 需要输入以#结尾的中缀表达式，以提示语句的方式给出。输出注明是什么结果。 2.任务调度 需要输入任务数，任务需要执行时间，(不同时需要任务提交时间)，按平均等待时间最短为原则，输出出任的执行顺序。 五、运行测试与分析 1.表达式求值 1).输入一个以#结尾的中缀

28、表达式：入一个以，肥结尾的中播表达式. 表达式口答*4-3/9片2廿输出计算结果，后缀表达式以及前缀表达式:竺匕它以:1裳达 个忒堇表 一诲的缀耀 入表式后刖 V达的的(3) 务调度：(1) .同时提交i).输入：3 2 3 15一日.-一日、-日:日.L日、-,二1二," P 寸 m -二 m n-r 二 j要要要要要 需需需需需 5务务务务务 4 12 3 4s 堂第第第第一 人人入入人入：ii).输出:迪序执行工柞号开站时间等待时间Q3 5B结束时间358914时间最期二开播寸间等待时间00结束时闾914(2) .不同时间提交i) .输入：务提交日恻和执行时间Ba个任务提交时刻

29、和执行时间都1行时间种3旧 2露个任务提交时刻和执行时间g: I留5个任务提交日执和执行时间 9416 618&8213平均等待时间为1-0008六、实验收获与思考1.熟练掌握栈的定义及使用。2. 了解表达式求值的转换算法。设计前、后缀表达式求值算法。3.设计操作数为多位实数，操作符为加、减、乘、除、求模的中缀表达式求值算法。 定义算数符号的优先级。|小5ii) .输出:序号开始时间等待时间结束21024 .从理论到实践，巩固了学过的知识。七、附录(原程序)5 .表达式求值#include<stdio.h>#include<stdlib.h>#include&l

30、t;string.h>#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define ERROR 0#define OK 1typedef struct NumStack / number stackint *base;int *top;int stacksize;NumStack;typedef struct SymStack / symbol stackchar *base;char *top;int stacksize;SymStack;void IntInitStack(NumStack *S)S->base=(int

31、 *)malloc(STACK_INIT_SIZE*sizeof(int);if(!S->base)exit(ERROR);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;Cha

32、rInitStackint IntGetTop(NumStack *S)/取栈顶元素int e;if(*S).top=(*S).base) return 0;e=*(*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(SymSt

33、ack *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;/IntPop int CharPop(SymStack *S)char e;if(*S).top=(*S).base) return 0;e=*-(*S).top;return e;CharPopchar Precede(char a,char b)int i,j;char Table99='+','>'

34、;,'>','<','<','<','<','>','>', '-','>','>','<','<','<','<','>','>', '*','>','>','>',&#

35、39;>','>','<','>','>', '/','>','>','>','>','>','<','>','>', '%','>','>','>','>','>','&

36、lt;','>','>', -','<','<','<','=','', ')','>','>','>','>','>',' ','>','>',#;<'<'<'<'<'<'

37、; ','=',;/优先级表格for(i=0;i<9;i+)if(Table0i=a)/纵坐标寻找break; for(j=0；j<9；j+)/横坐标寻找if(Table皿0=b) break;return Tablej叱 b Table aPrecedeint Operate(int a,char theta,int b)/计算表达式值：主要是将大的表达式/转化成小的表达式进行逐步求值int c;if(theta='+') c=a+b;else if(theta='-') c=a-b;else if(theta='*

38、') c=a*b;else if(theta='%') c=a%b;else c=a/b;return c;/Operateint ReadNum(char s) if(s>=49&&s<=57) s-=48;return s; else/将字符型的数字转化成int型/数字的ASCII码所在范围这儿决定了本程序只能计算一位数的四则运算return 0; ReadNumint result(char *a,NumStack *OPND,SymStack *OPTR) /求值char theta;int b,c,i=0;IntInitStack(

39、OPND);CharInitStack(OPTR);CharPush(OPTR,'#');while(1)if(ReadNum(ai)IntPush(OPND,ReadNum(ai+);else if(ai='+'l|ai=T|ai='*'11ai='/'11ai='%'11ai='#'l|ai='('l|ai=')')switch(Precede(ai,CharGetTop(OPTR)case '<':CharPush(OPTR,ai+);br

40、eak;case '=':CharPop(OPTR);i+;break;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("表达式的结果是d.n",IntGetTop(OPND);/打印输出表达式值retur

41、n OK; /while /reslutchar postfix(char *a) /此函数将中缀表达式转换为后缀表达式char ch, b100;int i=0, j=0;SymStack r, *R;R = &r;CharInitStack(R);CharPush(R,'#');ch=ai;while(ch!='#')if(ch>=49&&ch<=57) ch-=48; bj+=ch; ch=a+i;else if(ch='(') CharPush(R,ch); ch=a+i;else if(ch='

42、;)')if(CharGetTop(R)!='(') bj+=CharPop(R);elseCharPop(R); ch=a+i;else if(ch='+'|ch='-'|ch='*'11ch='/'11ch='%') if(Precede(ch,CharGetTop(R)片'<') if Top(R) < chCharPush(R,ch);ch=a+i;elsebj+=CharPop(R);/whilech=CharPop(R);while(ch!='

43、#')bj=ch；j+；ch=CharPop(R);b昨'#'；printf("它的后缀表达式为：")；for(i=0;bi!='#'i+)/打印输出后缀表达式if(bi>=1&&bi<=9)printf("%d",bi);elseprintf("%c",bi);/forprintf(".n");return OK;postfixchar perfix(char *a) /此函数将中缀表达式转换为后缀表达式char ch, b100;int j=0

44、;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='*'11ch='/'11ch='%')if(*R).top=(*R).base|CharGetTo

45、p(R) = ')'|Precede(ch,CharGetTop(R)='<') CharPush(R,ch);break;elsebj+=CharPop(R);if(ch='(')while(CharGetTop(R)!=')') bj+=CharPop(R);CharPop(R);ch=a-i;/whilewhile(*R).top != (*R).base)bj+=CharPop(R);bj = '0'；printf("它的前缀表达式为：")；int t=strlen(b)-1;fo

46、r(t;t>=0;t-)/打印输出前缀表达式if(bt>=1&&bt<=9)printf("%d",bt);elseprintf("%c",bt);/forprintf(".n");return OK;/perfixvoid main()/主函数，使用自定义函数完成功能char a100;NumStack s1,*OPND;SymStack s2,*OPTR;OPND=&s1;OPTR=&s2;printf("请输入一个以#结尾的中缀表达式.n");printf(&

47、quot;这个表达式：”)；scanf("%s",&a);result(a,OPND,OPTR);postfix(a);perfix(a);2.任务调度1)同时提交#include <stdio.h>#include <stdlib.h>#include <string.h>int que100,rear=0,t=0;struct taskint order,need,t,start,wait,end;/任务顺序，需要时间，提交时间，开始时间，等待时间，结束时间T100;int comp(const void *a,const v

48、oid *b)/不同时间排序return T*(int *)a.need>T*(int *)b.need; void dele()int i;printf("%-10d%-10d%-10d%-20dnn",Tque0.order,Tque0.start,Tque0.wait,Tque0.enfor(i=0;i<rear-1;i+)quei=quei+1;rear-;int check(int num1)int i;Tque0.need-;if(Tque0.need<=0)Tque0.end=t;dele();for(i=0;i<rear;i+)Tqu

49、ei.wait+;return 1;elsefor(i=1;i<rear;i+)Tquei.wait+;return 0;/时间段移动查寻当前队列 void insert(int n)int i,rec;for(i=0;i<rear;i+)if(Tquei.need>Tn.need) break;rec=i;for(i=rear;i>rec;i-)quei=quei-1;querec=n;rear+;void difftime(int n)/输入本来按照先后顺序int tdiff;double sum;int i,j;rear=0;sum=0;for(i=0;i<

50、n;i+)/输入每个任务信息printf("请输入第外任务提交时刻和执行时间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;t+;时间移动 i+=check(tdiff);/ if(t>=Tj.t&&j<n)insert(j); / j+；while(i<n)时间移动后检查是否有完成的任务