数据结构实验表达式求值、任务调度案例.doc

实验报告二 实验课名称：数据结构与程序设计实验 实验名称：表达式求值、任务调度 班级 学号 姓名 时间 一、问题描述 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;i9;i++) if(Table[0][i]==a) //纵坐标寻找 break; for(j=0;j9;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=49s=57)