1、 数据结构课程设计数据结构课程设计 题目题目 算术表达式求值算术表达式求值 目录目录 一、一、 问题描述问题描述 二、二、 基本要求基本要求 三、三、 数据结构的设计数据结构的设计 四、四、 软件模块结构图软件模块结构图 五、五、 程序设计思想程序设计思想 六、六、 程序流程图程序流程图 七、七、 源程序源程序 八、八、 调试分析调试分析 九、九、 测试数据测试数据 十、十、 用户使用手册用户使用手册 十一十一、 心得体会心得体会 一：一：问题描述问题描述 从键盘上输入算术表达式，包括括号； （1） 判断表达式是否是正常表达式； （2） 计算出一般表达式（类似如 a*b+c/d-e）的值； （
2、3） 并能实现一元多项式相加。 二：基本要求二：基本要求 （1） 程序对所输入的友达式作简单的判断，如表达式有错能给出适当的提示； （2） 能处理单目运算符：十和一； （3） 已知 2 012 () n n A xaa xa xa x和 2 012 () m m B xbb xa xb x，并 且在 A(x)和 B(x)中指数相差很多，求 A(x)=A(x)+B(x)。要求设计存储结构表示 一元多项式，设计算法实现一元多项式相加。 三：数据结构的设计三：数据结构的设计 任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈 来寄存表达式的操作数和运算符。 栈是限定于紧仅在表尾进行插
3、入或删除操作的 线性表。 顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的 数据元素，同时附设指针 top 指示栈顶元素在顺序栈中的位置，base 为栈底指 针，在顺序栈中，它始终指向栈底，即 top=base 可作为栈空的标记，每当插入 新的栈顶元素时，指针 top 增 1，删除栈顶元素时，指针 top 减 1。 ADT 描述 ADT Stack 数据对象：D= i a | i aElemSet,i=1,2,，n, n0 数据对象：R1=| 1i a,Dai,i=2,，n 约定 n a端为栈顶， i a端为栈底。 基本操作： InitStack( char *base; cha
4、r *top; Stack; /* 定义整型栈 */ typedef struct int stacksize; int *base; int *top; Stack2; 六：程序流程图六：程序流程图 1. Precede(char c1,char c2) 判断运算符优先权，返回优先权高的。 算符间的优先关系如下： + - * / ( ) # + - * / ( # base=(char *)malloc(STACK_INIT_SIZE*sizeof(char); if(!s-base) return ERROR; s-top=s-base; s-stacksize=STACK_INIT_SI
5、ZE; return OK; int InitStack2(Stack2 *s) /构造操作数栈 s-base=(int *)malloc(STACK_INIT_SIZE*sizeof(int); if(!s-base) return ERROR; s-stacksize=STACK_INIT_SIZE; s-top=s-base; return OK; int In(char ch) /判断字符是否是运算符，运算符即返回 1 return(ch=+|ch=-|ch=*|ch=/|ch=(|ch=)|ch=#); int Push(Stack *s,char ch) /运算符栈插入 ch 为新
6、的栈顶元素 *s-top=ch; s-top+; return 0; int Push2(Stack2 *s,int ch)/操作数栈插入 ch 为新的栈顶元素 *s-top=ch; s-top+; return 0; char Pop(Stack *s) /删除运算符栈 s 的栈顶元素，用 p 返回其值 char p; s-top-; p=*s-top; return p; int Pop2(Stack2 *s)/删除操作数栈 s 的栈顶元素，用 p 返回其值 int p; s-top-; p=*s-top; return p; char GetTop(Stack s)/用 p 返回运算符栈 s 的栈顶元素 char p=*(s.top-1); retu
