数据结构 任务调度 实验报告_数据结构图的实验报告
数据结构 任务调度 实验报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构图的实验报告”。
实验报告
实验名称：表达式求值 任务调度 实验类型：综合性实验 班级：
学号：
姓名：
实验日期：2014.5.28
表达式求值 1.问题描述
表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*(7-4)/3。中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀式（如：22 7 4-* 3 / 11 +）和前缀式（如：+ 11 / * 22 – 7 4 3）。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。2.数据结构设计
建立栈，算数表达式的计算往往是通过栈来实现的，所以建立结构体，如下 typedef struct{ float *base;//栈底指针
float *top;//栈顶指针
int stacksize;}SqStack_f;//实数栈
typedef struct{ char *base;char *top;int stacksize;}SqStack_c;//字符栈
3.算法设计
void Translate(char *s1)
//中缀转后缀
{ char s2[80];SqStack_c Optr;int i=0,j=0;char t;InitStack_c(&Optr);
//初始化一个运算符栈
Push_c(&Optr,'(');while(s1[i]!='#'){
if(s1[i]>='0' && s1[i]
{
s2[j++]=s1[i];
if((s1[i+1]'9')&& s1[i+1]!='.')
s2[j++]=' ';
//将完整的字符型数字存入 然后存入空格
}
else
switch(s1[i])
{
case'(':Push_c(&Optr,s1[i]);break;
//遇到左括号 将其压栈
case')':Pop_c(&Optr,&t);
//遇到右括号时
将栈内运算符弹出并压入数组s2 直到遇到左括号
while(t!='(')
{
s2[j++]=t;
Pop_c(&Optr,&t);
}
break;
default:while(GetTop_c(&Optr,&t),precede(t,s1[i]))//与栈顶元素比较 若栈顶元素级别高 则进行以下循环
{
Pop_c(&Optr,&t);
s2[j++]=t;
//弹出栈顶元素 并存入数组s2
}
Push_c(&Optr,s1[i]);
//将当前遇到运算符压栈
}
i++;} Pop_c(&Optr,&t);while(t!='('){
s2[j++]=t;
Pop_c(&Optr,&t);} for(i=0;i
s1[i]=s2[i];s1[i]='#';s1[i+1]=' ';}
void Calculate(SqStack_f *s,char *s2)
//计算表达式的值
{ float m,x,y,z;
int p,i=0,j=0;while(s2[i]!='#'){ if(s2[i]>='0' && s2[i]
m=0;
while(s2[i]!=' ' && s2[i]!='.')
m=m*10+(float)(s2[i++]-'0');
if(s2[i]=='.')
{
j=0;i++;
while(s2[i]!=' ')
{
m=m*10+(float)(s2[i++]-'0');
j++;
}
while(j>0)
{
m/=10;
j--;
}
}
i++;
Push_f(s,m);
GetTop_f(s,&m);} else {
Pop_f(s,&x);
Pop_f(s,&y);
switch(s2[i])
{
case '+':z=y+x;Push_f(s,z);break;
case '-':z=y-x;Push_f(s,z);break;
case '*':z=y*x;Push_f(s,z);break;
case '/':if(x==0)
{
printf(“表达式出错，除数为‘0’，无意义n”);
exit(1);
}
else
{
z=y/x;
Push_f(s,z);
break;
}
case '%':if(x==0||(int)x!=x||(int)y!=y)
{
printf(“表达式出错n”);
exit(1);
}
else
{
p=(int)y%(int)x;
Push_f(s,p);
break;
}
}
i++;} } }
int precede(char Top_char,char s1_char)
//比较运算符的优先级
{ int i,pre[2];char op[2];op[0]=Top_char;op[1]=s1_char;for(i=0;i
switch(op[i])
{
case'(':case')':pre[i]=0;break;
case'+':case'-':pre[i]=1;break;
case'*':case'/':case’%’:pre[i]=2;break;
} if(pre[0]>=pre[1])
//栈顶元素top char>=s1 char就返回1
return 1;else
return 0;}
void convert(char *s,char *output)
//中缀转前缀
{
int j=0;int top=0;
char stack[50];strcpy(output,“”);
for(int i=strlen(s)-1;i>=0;)
{
if((s[i]>=48&&s[i]
output[j++]=s[i];
if(s[i]==')')
{
top++;
stack[top]=s[i];
}
while(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/'||s[i]=='%')
{
output[j++]=' ';
if(top==0||stack[top]==')'||precede(s[i],stack[top]))
{
top++;
stack[top]=s[i];
break;
}
else
{
output[j++]=stack[top];
top--;
}
}
if(s[i]=='(')
{
while(stack[top]!=')')
{
output[j++]=stack[top];
top--;
}
top--;
}
i--;
}
while(top!=0)
{
output[j++]=stack[top];
top--;
}
}
4.界面设计
printf(“请输入算术表达式，结束前请输入#号！n”);
5.运行、测试与分析
6、实验收获与思考
1．熟练掌握栈的定义及使用。
2．了解表达式求值的转换算法。设计前、后缀表达式求值算法。
3．设计操作数为多位实数，操作符为加、减、乘、除、求模的中缀表达式求值算法。定义算数符号的优先级。
7、源代码
#include #include #include #include #include #define TTACK_INIT_SIZE 100 #define STACKINCREMENT 10
typedef struct{ float *base;float *top;int stacksize;}SqStack_f;//实数栈
typedef struct{ char *base;char *top;int stacksize;}SqStack_c;//字符栈
void InitStack_f(SqStack_f *s){ s->base=(float *)malloc(TTACK_INIT_SIZE*sizeof(float));if(!s->base)
exit(1);s->top=s->base;s->stacksize=TTACK_INIT_SIZE;} void InitStack_c(SqStack_c *s){ s->base=(char *)malloc(TTACK_INIT_SIZE*sizeof(char));if(!s->base)
exit(1);s->top=s->base;s->stacksize=TTACK_INIT_SIZE;} void GetTop_f(SqStack_f *s,float *e){ if(s->top==s->base){
printf(“ERROR!n”);
exit(1);} *e=*(s->top-1);} void GetTop_c(SqStack_c *s,char *e){ if(s->top==s->base){
printf(“ERROR!n”);
exit(1);} *e=*(s->top-1);} void Push_f(SqStack_f *s,float e){ if(s->top-s->base>=s->stacksize){
s->base=(float *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(float));
if(!s->base)
{
printf(“OVERFLOW!n”);
exit(1);
}
s->top=s->base+s->stacksize;
s->stacksize+=STACKINCREMENT;} *s->top++=e;} void Push_c(SqStack_c *s,char e){ if(s->top-s->base>=s->stacksize){
s->base=(char *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(char));
if(!s->base)
{
printf(“OVERFLOW!n”);
exit(1);
}
s->top=s->base+s->stacksize;
s->stacksize+=STACKINCREMENT;} *s->top++=e;} void Pop_f(SqStack_f *s,float *e){ if(s->top==s->base)
exit(1);*e=*--s->top;} void Pop_c(SqStack_c *s,char *e){ if(s->top==s->base)
exit(1);*e=*--s->top;} int precede(char Top_char,char s1_char)
//比较运算符的优先级
{ int i,pre[2];char op[2];op[0]=Top_char;op[1]=s1_char;for(i=0;i
switch(op[i])
{
case'(':case')':pre[i]=0;break;
case'+':case'-':pre[i]=1;break;
case'*':case'/':case'%':pre[i]=2;break;
} if(pre[0]>=pre[1])
//栈顶元素top char>=s1 char就返回1
return 1;else
return 0;} void Translate(char *s1)
//中缀转后缀
{ char s2[80];SqStack_c Optr;int i=0,j=0;char t;InitStack_c(&Optr);
//初始化一个运算符栈
Push_c(&Optr,'(');while(s1[i]!='#'){
if(s1[i]>='0' && s1[i]
{
s2[j++]=s1[i];
if((s1[i+1]'9')&& s1[i+1]!='.')
s2[j++]=' ';
//将完整的字符型数字存入 然后存入空格
}
else
switch(s1[i])
{
case'(':Push_c(&Optr,s1[i]);break;
//遇到左括号 将其压栈
case')':Pop_c(&Optr,&t);
//遇到右括号时
将栈内运算符弹出并压入数组s2 直到遇到左括号
while(t!='(')
{
s2[j++]=t;
Pop_c(&Optr,&t);
}
break;
default:while(GetTop_c(&Optr,&t),precede(t,s1[i]))//与栈顶元素比较 若栈顶元素级别高 则进行以下循环
{
Pop_c(&Optr,&t);
s2[j++]=t;
//弹出栈顶元素 并存入数组s2
}
Push_c(&Optr,s1[i]);
//将当前遇到运算符压栈
}
i++;} Pop_c(&Optr,&t);while(t!='('){
s2[j++]=t;
Pop_c(&Optr,&t);} for(i=0;i
s1[i]=s2[i];s1[i]='#';s1[i+1]=' ';} void Calculate(SqStack_f *s,char *s2)
//计算表达式的值
{ float m,x,y,z;int p,i=0,j=0;while(s2[i]!='#'){
if(s2[i]>='0' && s2[i]
{
m=0;
while(s2[i]!=' ' && s2[i]!='.')
m=m*10+(float)(s2[i++]-'0');
if(s2[i]=='.')
{
j=0;i++;
while(s2[i]!=' ')
{
m=m*10+(float)(s2[i++]-'0');
j++;
}
while(j>0)
{
m/=10;
j--;
}
}
i++;
Push_f(s,m);
GetTop_f(s,&m);
}
else
{
Pop_f(s,&x);
Pop_f(s,&y);
switch(s2[i])
{
case '+':z=y+x;Push_f(s,z);break;
case '-':z=y-x;Push_f(s,z);break;
case '*':z=y*x;Push_f(s,z);break;
case '/':if(x==0)
{
printf(“表达式出错，除数为‘0’，无意义n”);
exit(1);
}
else
{
z=y/x;
Push_f(s,z);
break;
}
case '%':if(x==0||(int)x!=x||(int)y!=y)
{
printf(“表达式出错n”);
exit(1);
}
else
{
p=(int)y%(int)x;
Push_f(s,p);
break;
}
}
i++;} } } void result(SqStack_f *s){ float v;GetTop_f(s,&v);printf(“The final result is:%gn”,v);}
void convert(char *s,char *output)
//中缀转前缀
{
int j=0;int top=0;
char stack[50];strcpy(output,“”);
for(int i=strlen(s)-1;i>=0;)
{
if((s[i]>=48&&s[i]
output[j++]=s[i];
if(s[i]==')')
{
top++;
stack[top]=s[i];
}
while(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/'||s[i]=='%')
{
output[j++]=' ';
if(top==0||stack[top]==')'||precede(s[i],stack[top]))
{
top++;
stack[top]=s[i];
break;
}
else
{
output[j++]=stack[top];
top--;
}
}
if(s[i]=='(')
{
while(stack[top]!=')')
{
output[j++]=stack[top];
top--;
}
top--;
}
i--;
}
while(top!=0)
{
output[j++]=stack[top];
top--;
}
}
int main(){
int i;SqStack_f stack;char str[80];char output[80];
printf(“请输入算术表达式，结束前请输入#号！n”);
gets(str);
InitStack_f(&stack);
printf(“前缀表达式为：n”);
convert(str,output);
for(i=strlen(output)-1;i>=0;i--)
printf(“%c”,output[i]);
printf(“n”);
Translate(str);
printf(“后缀表达式为：n”);
puts(str);
Calculate(&stack,str);
result(&stack);}
任务调度 1.问题描述
多用户多任务操作系统中，多个任务同时共享计算机系统资源。为了使多个任务均能够顺利执行，操作系统要按一定的原则对它们进行调度，使它们按一定的次序进行。设只有一个CPU，现有多个任务，它们需要CPU服务的时间已知。在下列假设下，按平均等待时间最短为原则，设计算法求出任务的执行顺序。
忽略任务提交的时间差，即认为各任务同时提交。 各任务不同时提交。2.数据结构设计
struct task { }T[100];int order,ne,t,sta,wa,end;//任务顺序，需要时间，提交时间，开始时间，等待时间，结束时间
3.算法设计 同时
int cmp(const void *a,const void *b)
//相同时间排序
{ return(*(struct task *)a).ne>(*(struct task *)b).ne;}
void sametime(int n){ double sum,sum2;int i;for(i=0;i
{
printf(“请输入第%d个任务所需要的时间n”,i+1);
T[i].t=0;
scanf(“%d”,&T[i].ne);
T[i].order=i+1;} t=0;sum=0;printf(“序号 开始时间 等待时间
结束时间n”);for(i=0;i
{
printf(“%-7d”,i+1);
printf(“%-7d”,t);
printf(“%-8d”,t);
t+=T[i].ne;
printf(“%-8d”,t);
printf(“n”);
sum+=((n-i-1)*T[i].ne);} printf(“n”);printf(“序号 开始时间 等待时间
结束时间n”);qsort(T,n,sizeof(T[0]),cmp);//按最短时间排序
t=0;sum2=0;for(i=0;i
{
printf(“%-7d”,T[i].order);
printf(“%-7d”,t);
printf(“%-8d”,t);
t+=T[i].ne;
printf(“%-8dn”,t);
printf(“n”);
sum2+=((n-i-1)*T[i].ne);} printf(“顺序执行等待平均时间为
%.3lfn”,sum/n);} printf(“最短等待平均时间为
%.3lfn”,sum2/n);不同时
int comp(const void *a,const void *b)//不同时间排序
{ return T[*(int *)a].ne>T[*(int *)b].ne;}
void dele(){ int i;printf(“%-10d%-10d%-10d%-20dnn”,T[que[0]].order,T[que[0]].sta,T[que[0]].wa,T[que[0]].end);for(i=0;i
que[i]=que[i+1];rear--;}
int check(int num1){ int i;T[que[0]].ne--;if(T[que[0]].ne
T[que[0]].end=t;
dele();
for(i=0;i
T[que[i]].wa++;
return 1;} else {
for(i=1;i
T[que[i]].wa++;
return 0;} }//时间段移动查寻当前队列
void insert(int n){ int i,rec;for(i=0;i
if(T[que[i]].ne>T[n].ne)
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
{
printf(“请输入第%d个任务提交时刻和第%d个任务执行时间n”,i+1,i+1);
scanf(“%d%d”,&T[i].t,&T[i].ne);
T[i].order=i+1;
T[i].sta=-1;T[i].end=-1;T[i].wa=0;} printf(“序号
开始时间
等待时间
结束n”);que[0]=0;rear=1;T[0].sta=0;i=0;t=0;j=1;while(i
t++;//时间移动
i+=check(tdiff);//时间移动后检查是否有完成的任务，并且就算等待时间
if(t>=T[j].t&&j
{
insert(j);//把任务插入到队列
j++;
qsort(que,rear,sizeof(que[0]),comp);//按时间长短排序
}
if(T[que[0]].sta==-1)//给队列最前点赋起始值
T[que[0]].sta=t;} for(i=0;i
sum+=T[i].wa;printf(“平均等待时间为 %.3lfsnn”,sum/n);
} 4.界面设计
printf(“请输入任务数n”);
5.运行、测试与分析
同时
不同时
6.实验收获及思考
写出一个程序不仅仅是算法的考究，更是细节的较量。
从理论到实践，我学到很多很多的东西。不仅巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的内容。
7、源代码
同时
#include #include #include int que[100],rear=0,t=0;struct task { int order,ne,t,sta,wa,end;//任务顺序，需要时间，提交时间，开始时间，等待时间，结束时间
}T[100];int cmp(const void *a,const void *b)
//相同时间排序
{ return(*(struct task *)a).ne>(*(struct task *)b).ne;} void sametime(int n){ double sum,sum2;int i;for(i=0;i
printf(“请输入第%d个任务所需要的时间n”,i+1);
T[i].t=0;
scanf(“%d”,&T[i].ne);
T[i].order=i+1;} t=0;sum=0;printf(“序号 开始时间 等待时间
结束时间n”);for(i=0;i
{
printf(“%-7d”,i+1);
printf(“%-7d”,t);
printf(“%-8d”,t);
t+=T[i].ne;
printf(“%-8d”,t);
printf(“n”);
sum+=((n-i-1)*T[i].ne);} printf(“n”);printf(“序号 开始时间 等待时间
结束时间n”);qsort(T,n,sizeof(T[0]),cmp);//按最短时间排序
t=0;sum2=0;for(i=0;i
{
printf(“%-7d”,T[i].order);
printf(“%-7d”,t);
printf(“%-8d”,t);
t+=T[i].ne;
printf(“%-8dn”,t);
printf(“n”);
sum2+=((n-i-1)*T[i].ne);} printf(“顺序执行等待平均时间为
%.3lfn”,sum/n);printf(“最短等待平均时间为
%.3lfn”,sum2/n);} int main(){ int n;printf(“请输入任务数:n”);while(scanf(“%d”,&n)!=EOF){
if(n
{
printf(“输入错误,程序结束”);
break;
}
sametime(n);} system(“pause”);return 0;}
不同时
#include #include #include int que[100],rear=0,t=0;struct task { int order,ne,t,sta,wa,end;//任务顺序，需要时间，提交时间，开始时间，等待时间，结束时间
}T[100];int comp(const void *a,const void *b)//不同时间排序
{ return T[*(int *)a].ne>T[*(int *)b].ne;} void dele(){ int i;printf(“%-10d%-10d%-10d%-20dnn”,T[que[0]].order,T[que[0]].sta,T[que[0]].wa,T[que[0]].end);for(i=0;i
que[i]=que[i+1];rear--;} int check(int num1){ int i;T[que[0]].ne--;if(T[que[0]].ne
T[que[0]].end=t;
dele();
for(i=0;i
T[que[i]].wa++;
return 1;} else {
for(i=1;i
T[que[i]].wa++;
return 0;} }//时间段移动查寻当前队列
void insert(int n){ int i,rec;for(i=0;i
if(T[que[i]].ne>T[n].ne)
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
{
printf(“请输入第%d个任务提交时刻和第%d个任务执行时间n”,i+1,i+1);
scanf(“%d%d”,&T[i].t,&T[i].ne);
T[i].order=i+1;
T[i].sta=-1;T[i].end=-1;T[i].wa=0;} printf(“序号
开始时间
等待时间
结束n”);que[0]=0;rear=1;T[0].sta=0;i=0;t=0;j=1;while(i
t++;//时间移动
i+=check(tdiff);//时间移动后检查是否有完成的任务，并且就算等待时间
if(t>=T[j].t&&j
{
insert(j);//把任务插入到队列
j++;
qsort(que,rear,sizeof(que[0]),comp);//按时间长短排序
}
if(T[que[0]].sta==-1)//给队列最前点赋起始值
T[que[0]].sta=t;} for(i=0;i
sum+=T[i].wa;printf(“平均等待时间为 %.3lfsnn”,sum/n);
} int main(){ int n;printf(“请输入任务数n”);while(scanf(“%d”,&n)!=EOF){
if(n
{
printf(“输入错误,程序结束”);
break;
}
difftime(n);} system(“pause”);return 0;}
