c语言程序实习计划书

1、程序实习报告书起止日期： 2012 年 6月 18 日 至 2012 年 6月 29日 学 号： 2011272086 .班 级： 通 信 113 .姓 名： 李 成 元 .指导教师： 赵金胜 刑延超 .通信与电子工程学院2012年 6月 30日1 设计时间2012.06.18-2012.06.292 设计目的1、实习目的 熟练掌握和系统理解C语言的基本知识点：数据类型、程序结构、函数、数组、结构体、文件等。 学会用C语言解决实际问题的方法 掌握较大型程序设计及调试的一般步骤和方法。3设计任务综合运用C语言程序设计课程的主要知识设计一个计算器程序，利用算符优先关系，实现对算术四则混合运算表达式

2、的求值。输入的形式：算术表达式，以井号“#”结束。例如2*(3+4)#； 包含的运算符只能有'+' 、'-' 、'*' 、'/' 、'('、 ')'；输出的形式：运算结果，例如Answer is:14；程序所能达到的功能：对算术表达式求值并输出结果。4.1需求分析1、程序所能达到的功能：能够处理以字符序列的形式输入的不含变量的实数表达式，正确处理负数与小数，判断表达式是还语法正确（包含分母不能为零的情况），正确实现对算术四则混合运算表达式的求值，能够将计算中遇到的问题和结果以文件的形式予以存储。2、

3、输入的形式和输入值的范围：以字符串的形式输入表达式，以“#”结束。3、输出的形式：在计算过程中遇到的问题或最终的答案将显示在屏幕上，同时所计算的表达式的最终的结果也将保存在文件中。4、测试数据：输入“3*(7-2)#”时，输出“15.000000”，测试正确；输入“!(9-2)#”时，输出“输入错误！”，测试正确。4.2总体设计抽象数据类型定义ADT Stack数据对象：D= |ElemSet,i=1,2,，n, n0数据对象：R1=<>|,i=2,，n约定端为栈顶，端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈S。GetTop(S)初始条件：栈S已存

4、在。操作结果：用P返回S的栈顶元素。Push(&S，ch)初始条件：栈S已存在。操作结果：插入元素ch为新的栈顶元素。Pop(&S)初始条件：栈S已存在。操作结果：删除S的栈顶元素。In(ch)操作结果：判断字符是否是运算符，运算符即返回1。Precede(c1, c2) 初始条件：c1,c2为运算符。操作结果：判断运算符优先权，返回优先权高的。Operate(a,op,b)初始条件：a,b为整数，op为运算符。操作结果：a与b进行运算，op为运算符，返回其值。num(n)操作结果：返回操作数的长度。EvalExpr()初始条件：输入表达式合法。操作结果：返回表达式的最终结果。

5、ADT Stack函数模块说明为实现算符优先算法，可以使用两个工作栈。一个称做OPTR，用以寄存运算符；另一个称做OPND，用以寄存操作数或运算结果。算法的基本思想是：(1)首先置操作数栈为空栈，表达式起始符“#”为运算符栈底元素(2)依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）。4.2.3主函数流程图函数模块调用关系4.2.5运算符间的优先关系1 2+-*/()#+>>><<>>->>><

6、;<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=4.3详细设计4.3.1数据类型的定义及基本操作/= ADT Stack的表示与实现 = /- 栈的顺序存储表示 -#define STACK_INIT_SIZT 100;#define STACKINCREMENT 10typedef structSElemType *base;SElemType *top;int

7、stacksize;SqStack;/- 基本操作的算法描述 -Status InitStack(SqStack &S)S.base = (SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemType);if(!S.base) exit (OVERFLOW);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;Status GetTop(SqStack S, SElemType &e)if(S.top = S.base) return ERROR;e = * (S.top-

8、1);return OK;Status Push(SqStack &S,SElemType e)if(S.top-S.base>=S.stacksize) S.base=(SElemType*)realloc(S.base,(S.StackSize+STACKINCREMENT)*sizeof (SElemType); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize += STACKINCREMENT;*S.top+ =e;return OK;Status Pop(SqStack &S,S

9、ElemType &e)if(S.top = S.base) return ERROR;e = * -S.top;return OK;OperandType EvaluateExpession()InitStack(OPTR); Push(OPTR,#);InitStack(OPND); c = getchar();while(c!#|GetTop(OPTR)!=#) if(!In(c,OP)Push(OPND,c); c = getchar();) else switch(Precede(GetTop(OPTR),c) case<:Push(OPTR,c); c = getch

10、ar(); break; case=:Pop(OPTR,x); c = getchar(); break; case>:Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b); break; 4.3.2函数调用关系4.3.3主要模块的算法描述void main()SqStack_T OPTR;SqStack_N OPND;float a,b,i; char theta,c,x;InitStack_T(&OPTR);Push_T(&OPTR,#);InitStack_N(&OPN

11、D);printf(“请输入表达式关以#结尾：n”);c=getchar();if(c=35|(c>=40&&c<=43)|c=45|(c>=47&&c<=57)while(c!=#|GetTop_T(&OPTR)!=#) if(c>=48&&c<=57) i=(float)c-48; Push_N(&OPND,i); c=getchar(); else switch(Precede(GetTop_T(&OPND),c) case<:Push_T(&OPTR,c);c=ge

12、tchar();break; case=:x=Pop_T(&OPTR);c=getchar();break; case>:theat=Pop_T(&OPTR);b=Pop_N(&OPND);a=Pop_N(&OPND);Push_N(&OPND,Operate(a,theta,b);break; printf(“结果是%fn”,GetTop_N(&OPND);else printf(“输入错误！n”);4.4测试与分析测试加法测试，输入正确，输出正确，测试正确：乘法测试，输入正确，输出正确，测试正确：输入表达式正确，输出正确，测试正确：输入

13、表达式错误，能正确判断，测试正确：4.4.2分析内容包括：1、调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析:遇到的问题：调试过程中遇到了输入非法字符不输出“错误！”的情况。解决的办法：查ASCII码表得知运算符+,-,*,/,(,),#和运算数0,1,2,3,4,5,6,7,8,9相应的ASCII值。在主程序中加入了判断语句，判断输入的是否为运算符或运算数。如果是，则进行正常运算；如果不是，则返回错误。2、算法的时间复杂度和空间复杂度的分析：中缀表达式运算时间主要用在字符串扫描和算符优先权的比较上。把#看作运算符，操作数与运算符个数相同，最坏情况下优先级比较是n/2次，即运

14、算顺序完全是逆序的，每个字符扫描一遍是O(n)的，所以整个算法复杂度是O(n2)的。算法中用到两个栈，分别为O(n/2)，其算法空间复杂度是O(n)。4.5附录源程序#include "stdio.h"#include "stdlib.h"#define OK 1#define ERROR 0#define OVERFLOW 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef structchar *base;char *top;int stacksize;SqStack_T;type

15、def structfloat *base;float *top;int stacksize;SqStack_N;void InitStack_T(SqStack_T *S)(*S).base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);if(!(*S).base) exit(OVERFLOW);(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;void InitStack_N(SqStack_N *S)(*S).base=(float *)malloc(STACK_INIT_SIZE*sizeof(

16、float);if(!(*S).base) exit(OVERFLOW);(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;char GetTop_T(SqStack_T *S)char e;if(*S).top=(*S).base) return ERROR;e=*(*S).top-1);return e;float GetTop_N(SqStack_N *S)float e;if(*S).top=(*S).base) return ERROR;e=*(*S).top-1);return e;char Push_T(SqStack_T *S,

17、char e)if(*S).top-(*S).base>=(*S).stacksize)(*S).base=(char*)realloc(*S).base,(*S).stacksize+STACKINCREMENT)*sizeof(char);if(!(*S).base) exit(OVERFLOW);(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;*(*S).top)+=e;return OK;float Push_N(SqStack_N *S,float e)if(*S).top-(*S).base&g

18、t;=(*S).stacksize)(*S).base=(float*)realloc(*S).base,(*S).stacksize+STACKINCREMENT)*sizeof(float);if(!(*S).base) exit(OVERFLOW);(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;*(*S).top)+=e;return OK;char Pop_T(SqStack_T *S)char e;if(*S).top=(*S).base) return ERROR;e=*(-(*S).top);re

19、turn e;float Pop_N(SqStack_N *S)float e;if(*S).top=(*S).base) return ERROR;e=*(-(*S).top);return e;char m7="+-*/()#"char n77=">><<<>>",">><<<>>",">>>><>>",">>>><>>",&

20、quot;<<<<<= ",">>>> >>","<<<<< ="char Precede(char a,char b)int i=0,j=0;while(mi!=a)i+;while(mj!=b)j+;return(nij);float Operate(float a,char theta,float b)float r;switch(theta)case'+':r=a+b;break;case'-':r=a-b;b

21、reak;case'*':r=a*b;break;case'/':if(b!=0)r=a/b;else printf("输入错误!");break;return r;void main()SqStack_T OPTR;SqStack_N OPND;float a,b,i;char theta,c,x;InitStack_T(&OPTR);Push_T(&OPTR,'#');InitStack_N(&OPND);printf("请输入表达式并以'#'结尾:n");c=getchar();if(c=35|(c>=40&&c<=43)|c=45|(c>=47&&c<=57)while(c!='#'|GetTop_T(&OPTR)!='#')if(c>=48&&c<=57)i=(float)c-48;Push_N(&OPND,i);c=getchar();elseswitch(Precede(GetTop_T(&OPTR),c)case'<':Push_T(&OPTR,c);c