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

数据结构与程序设计实验

实 验 报 告

课程名称 实验项目名称学号姓名数据结构与程序设计实验 课程编号 0906550 计算机学院表达式求值、任务调度 年级专业 计算机科学与技术 学生所在学院 指导教师21B276 杨静 实验室名称地点

哈尔滨工程大学

实验报告二 实验课名称：数据结构与程序设计实验 实验名称：表达式求值、任务调度 班级 学号 姓名 时间 2016.04.12 一、问题描述 1. 表达式求值问题 表达式是数据运算的基本形式。人们的书写习惯是中缀式， 如：11+22*(7-4)/3。中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀式（如：22 7 4 - * 3 / 11 +）和前缀式（如：+11 / * 22 – 7 4 3）。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。 2. 任务调度 多用户多任务操作系统中，多个任务同时共享计算机系统资源。为了使多个任务均能够顺利执行，操作系统要按一定的原则对它们进行调度，使它们按一定的次序进行。设只有一个CPU，现有多个任务，它们需要CPU 服务的时间已知。在下列假设下，按平均等待时间最短为原则，设计算法求出任务的执行顺序。 忽略任务提交的时间差，即认为各任务同时提交。 各任务不同时提交。 二、数据结构设计 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. 任务调度： 用结构体存储每个任务的任务顺序，需要时间，提交时间，开始时间，等待时间，结束时间 struct task{ int order, need, t,start,wait,end; }T[100]; 三、算法设计 1.表达式求值： Precede函数用以比较运算符的优先级，返回’>’，’=’ 或 ’<’。 char Precede(char a,char b){ int i,j; char Table[9][9]={ {' ','+','-','*','/','%','(',')','#'}, {'+','>','>','<','<','<','<','>','>'}, {'-','>','>','<','<','<','<','>','>'}, {'*','>','>','>','>','>','<','>','>'}, {'/','>','>','>','>','>','<','>','>'}, {'%','>','>','>','>','>','<','>','>'}, {'(','<','<','<','<','<','<','=',' '}, {')','>','>','>','>','>',' ','>','>'}, {'#','<','<','<','<','<','<',' ','='}, }; //优先级表格 for(i=0;i<9;i++) if(Table[0][i]==a) //纵坐标寻找 break; for(j=0;j<9;j++) //横坐标寻找 if(Table[j][0]==b) break; return Table[j][i]; // b Table a }//Precede operate函数传入操作数a, b, 和操作符theta, 计算操作结果并返回。 int Operate(int a,char theta,int b){ //计算表达式值：主要是将大的表达式 //转化成小的表达式进行逐步求值 int c; if(theta=='+') 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; }//Operate readNum函数将字符型数字转换为int型。 int ReadNum(char s){ //将字符型的数字转化成int型 if(s>=49&&s<=57) //数字的ASCII码所在范围 { //这儿决定了本程序只能计算一位数的四则运算 s-=48; return s; } else return 0; }//ReadNum 求值函数result, 其基本求值过程为： 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(a[i])) IntPush(OPND,ReadNum(a[i++])); else if(a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/'||a[i]=='%'||a[i]=='#'||a[i]=='('||a[i]==')') { switch(Precede(a[i],CharGetTop(OPTR))) { case '<':CharPush(OPTR,a[i++]);break; 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(a[i]=='#'&&CharGetTop(OPTR)=='#') { printf(\ //打印输出表达式值 return OK; } }//while }//result 将中缀表达式转换为前缀表达式： 1）求输入串的逆序。 2）检查输入的下一元素。 3）假如是操作数，把它添加到输出串中。 4）假如是闭括号，将它压栈。 5）假如是运算符，则 i)假如栈空，此运算符入栈。 ii)假如栈顶是闭括号，此运算符入栈。 iii)假如它的优先级高于或等于栈顶运算符，此运算符入栈。 iv)否则，栈顶运算符出栈并添加到输出串中，重复步骤5。 6）假如是开括号，栈中运算符逐个出栈并输出，直到遇到闭括号。闭括号出栈并丢弃。 7）假如输入还未完毕，跳转到步骤2。 8）假如输入完毕，栈中剩余的所有操作符出栈并加到输出串中。 9）求输出串的逆序。 char perfix(char *a){ //此函数将中缀表达式转换为后缀表达式 char ch, b[100]; int j=0; SymStack r, *R; R = &r; CharInitStack(R); //CharPush(R,'#'); int i = strlen(a)-2; ch=a[i]; while(i>=0) { if(ch>=49&&ch<=57) { ch-=48; b[j++]=ch; } if(ch==')') { CharPush(R,ch); } while(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='%') { if((*R).top==(*R).base||CharGetTop(R) == ')'||Precede(ch,CharGetTop(R))=='<'){ CharPush(R,ch); break; }else{ b[j++]=CharPop(R); } } if(ch=='(') { while(CharGetTop(R)!=')') b[j++]=CharPop(R); CharPop(R); } ch=a[--i]; }//while while((*R).top != (*R).base) { b[j++]=CharPop(R);

} b[j] = '\\0'; printf(\ int t=strlen(b)-1; for(t;t>=0;t--) //打印输出前缀表达式 { if(b[t]>=1&&b[t]<=9) printf(\ else printf(\ }//for printf(\ return OK; }//prefix 将中缀表达式转换为后缀表达式： 算法描述： 将中缀表达式转换为等价的后缀表达式的过程要使用一个栈放“（”，具体可以按照下面的方式进行。 1）从左到右一次扫描中缀表达式的每一个字符，如果是数字字符和圆点“.”则直接将它们写入后缀表达式中。 2）如果遇到的是开括号“（”，则将它们压入一个操作符栈（不需要与栈顶操作符相比较），它表明一个新的计算层次的开始，在遇到和它匹配的闭括号“）”时，将栈中的元素弹出来并放入后缀表达式中，直到栈顶元素为“(”时，将栈顶元素“（”弹出（不需要加入后缀表达式），表明这一层括号内的操作处理完毕。 3）如果遇到的是操作符，则将该操作符和操作符栈顶元素比较： i)当所遇到的操作符的优先级小于或等于栈顶元素的优先级时，则取 出栈顶元素放入后缀表达式，并弹出该栈顶元素，反复执行直到栈顶元素的优 先级小于当前操作符的优先级（或遇到‘（’）； ii)当所遇到的操作符的优先级大于栈顶元素的优先级的时则将它压入 栈中。 4）重复上述步骤直到遇到中缀表达式的结束符标记“#”，弹出栈中的所有元素并放入后缀表达式中，转换结束 char postfix(char *a){ //此函数将中缀表达式转换为后缀表达式 char ch, b[100]; int i=0, j=0; SymStack r, *R; R = &r; CharInitStack(R); CharPush(R,'#'); ch=a[i]; while(ch!='#') { if(ch>=49&&ch<=57){ ch-=48; b[j++]=ch; ch=a[++i]; }else if(ch=='('){ CharPush(R,ch); ch=a[++i]; }else if(ch==')'){ if(CharGetTop(R)!='('){ b[j++]=CharPop(R); }else{ CharPop(R); ch=a[++i]; } }else if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='%'){ if(Precede(ch,CharGetTop(R))=='<'){ // if Top(R) < ch CharPush(R,ch); ch=a[++i]; }else b[j++]=CharPop(R); } }//while ch=CharPop(R); while(ch!='#') { b[j]=ch; j++; ch=CharPop(R); } b[j]='#'; printf(\ for(i=0;b[i]!='#';i++) //打印输出后缀表达式 { if(b[i]>=1&&b[i]<=9) printf(\ else printf(\ }//for printf(\ return OK; }//postfix 2．任务调度： (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;iT[*(int *)b].need; } void dele(){ int i; printf(\ for(i=0;iT[n].need) break; } rec=i; for(i=rear;i>rec;i--) que[i]=que[i-1]; que[rec]=n; rear++; } void difftime(int n){//输入本来按照先后顺序 int tdiff; double sum; int i,j; rear=0;sum=0; for(i=0;i=T[j].t&&j

ii).输出: (2). 不同时间提交 i).输入: ii).输出: 六、实验收获与思考 1．熟练掌握栈的定义及使用。 2．了解表达式求值的转换算法。设计前、后缀表达式求值算法。 3．设计操作数为多位实数，操作符为加、减、乘、除、求模的中缀表达式求值算法。 定义算数符号的优先级。 4. 从理论到实践，巩固了学过的知识。 七、附录（原程序） 1.表达式求值 #include #include #include #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define ERROR 0 #define OK 1 typedef 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(ERROR); S->top=S->base; S->stacksize=STACK_INIT_SIZE; }//IntInitStack void 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; }//CharInitStack int IntGetTop(NumStack *S){ //取栈顶元素 int e; if((*S).top==(*S).base) return 0; e=*((*S).top-1); return e; }//IntGetTop char CharGetTop(SymStack *S){ //取栈顶元素 char e; if((*S).top==(*S).base) return 0; e=*((*S).top-1); return e; }//IntGetTop int IntPush(NumStack *S,int e){ *(*S).top++=e; return OK; }//IntPush int CharPush(SymStack *S,char e){ *(*S).top++=e; return OK; }//CharPush int 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; }//CharPop char Precede(char a,char b){ int i,j; char Table[9][9]={ {' ','+','-','*','/','%','(',')','#'}, {'+','>','>','<','<','<','<','>','>'}, {'-','>','>','<','<','<','<','>','>'}, {'*','>','>','>','>','>','<','>','>'}, {'/','>','>','>','>','>','<','>','>'}, {'%','>','>','>','>','>','<','>','>'}, {'(','<','<','<','<','<','<','=',' '}, {')','>','>','>','>','>',' ','>','>'}, {'#','<','<','<','<','<','<',' ','='}, }; //优先级表格 for(i=0;i<9;i++) if(Table[0][i]==a) //纵坐标寻找 break; for(j=0;j<9;j++) //横坐标寻找 if(Table[j][0]==b) break; return Table[j][i]; // b Table a }//Precede int Operate(int a,char theta,int b){ //计算表达式值：主要是将大的表达式 //转化成小的表达式进行逐步求值 int c; if(theta=='+') 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; }//Operate int ReadNum(char s){ //将字符型的数字转化成int型 if(s>=49&&s<=57) //数字的ASCII码所在范围 { //这儿决定了本程序只能计算一位数的四则运算 s-=48; return s; } else return 0; }//ReadNum 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(a[i])) IntPush(OPND,ReadNum(a[i++])); else if(a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/'||a[i]=='%'||a[i]=='#'||a[i]=='('||a[i]==')') { switch(Precede(a[i],CharGetTop(OPTR))) { case '<':CharPush(OPTR,a[i++]);break; 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(a[i]=='#'&&CharGetTop(OPTR)=='#') { printf(\表达式的结果是%d.\\n\ //打印输出表达式值 return OK; } }//while }//reslut char postfix(char *a){ //此函数将中缀表达式转换为后缀表达式 char ch, b[100]; int i=0, j=0; SymStack r, *R; R = &r; CharInitStack(R); CharPush(R,'#'); ch=a[i]; while(ch!='#')

{ if(ch>=49&&ch<=57){ ch-=48; b[j++]=ch; ch=a[++i]; }else if(ch=='('){ CharPush(R,ch); ch=a[++i]; }else if(ch==')'){ if(CharGetTop(R)!='('){ b[j++]=CharPop(R); }else{ CharPop(R); ch=a[++i]; } }else if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='%'){ if(Precede(ch,CharGetTop(R))=='<'){ // if Top(R) < ch CharPush(R,ch); ch=a[++i]; }else b[j++]=CharPop(R); } }//while ch=CharPop(R); while(ch!='#') { b[j]=ch; j++; ch=CharPop(R); } b[j]='#'; printf(\它的后缀表达式为: \ for(i=0;b[i]!='#';i++) //打印输出后缀表达式 { if(b[i]>=1&&b[i]<=9) printf(\ else printf(\ }//for printf(\ return OK; }//postfix char perfix(char *a){ //此函数将中缀表达式转换为后缀表达式 char ch, b[100]; int j=0; SymStack r, *R; R = &r; CharInitStack(R); //CharPush(R,'#'); int i = strlen(a)-2; ch=a[i]; while(i>=0) { if(ch>=49&&ch<=57) { ch-=48; b[j++]=ch; } if(ch==')') { CharPush(R,ch); } while(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='%') { if((*R).top==(*R).base||CharGetTop(R) == ')'||Precede(ch,CharGetTop(R))=='<'){ CharPush(R,ch); break; }else{ b[j++]=CharPop(R); } } if(ch=='(') { while(CharGetTop(R)!=')') b[j++]=CharPop(R); CharPop(R); } ch=a[--i]; }//while while((*R).top != (*R).base) { b[j++]=CharPop(R); } b[j] = '\\0'; printf(\它的前缀表达式为: \ int t=strlen(b)-1; for(t;t>=0;t--) //打印输出前缀表达式 { if(b[t]>=1&&b[t]<=9) printf(\ else printf(\ }//for printf(\ return OK; }//perfix void main(){ //主函数，使用自定义函数完成功能 char a[100]; NumStack s1,*OPND; SymStack s2,*OPTR; OPND=&s1; OPTR=&s2; printf(\请输入一个以'#'结尾的中缀表达式.\\n\ printf(\这个表达式:\ scanf(\ result(a,OPND,OPTR); postfix(a); perfix(a); } 2.任务调度 1)同时提交 #include #include #include int que[100],rear=0,t=0; struct task{ int order,need,t,start,wait,end;//任务顺序，需要时间，提交时间，开始时间，等待时间，结束时间 }T[100]; int comp(const void *a,const void *b){//不同时间排序 return T[*(int *)a].need>T[*(int *)b].need; } void dele(){ int i; printf(\ for(i=0;iT[n].need) break; } rec=i; for(i=rear;i>rec;i--) que[i]=que[i-1]; que[rec]=n; rear++; } void difftime(int n){//输入本来按照先后顺序 int tdiff; double sum; int i,j; rear=0;sum=0; for(i=0;i=T[j].t&&j #include #include int que[100],rear=0,t=0; struct task{ int order, need, t, start, wait, end;//任务顺序，需要时间，提交时间，开始时间，等待时间，结束时间 }T[100];

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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构实验报告-表达式求值与任务调度在线全文阅读。