一、需求分析【课程设计要求】
问题的描述】
一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现基于二叉树表示的算术表达式expression的操作。
基本要求】一】【必做部分】
一、需求分析【课程设计要求】
问题的描述】
一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现基于二叉树表示的算术表达式expression的操作。
基本要求】一】【必做部分】
假设算术表达式expression内可以含有变量（a-z）,常量（0-9）和二元运算符乘幂））。实现以下操作：
（1）readexpr(e)――以字符序列的形式输入语法正确的前缀表达式并构造表达式e。
（2）writeexpr(e)――用带括号的中缀表达式输出表达式e。
（3）assign(v，c)――实现对变量v的赋值（v=c），变量的初值为0。
（4）value(e)――对算术表达式e求值。
（5）compoundexpr(p,e1,e2)――构造一个新的复合表达式（e1）p（e2）。
二】【选做部分】
1）以表达式的原书写形式输入，支持大于0的正整数常量；
2）增加常数合并操作mergeconst(e)——合并表达式e中所有常数运算。例如，对表达式e=(2+3-a)*(b+3*4)进行合并常数的操作后，求得e=(5-a)*(b+12)
3)增加对求偏导数的运算diff（e，v）——求表达式e对v的导数。
4)在表达式内增加对三角函数等初等函数的操作。
测试数据】1)分别输入0；a;-91;+a*bc;+*5x2*8x;++3^*2^x2x6并输出。
2）每当输入一个表达式后，对其中的变量赋值，然后对表达式求值。
二 、【整体算法思想】
一个表达式和一棵二叉树之间存在一一对应的关系。本程序我主要用前缀表达式建树，中序遍历并适当加括号实现中缀输出。具体操作即对树的程序进行处理，再输出。
三、【概要设计】
1、数据类型的声明：
在这个课程设计中，采用了链表二叉树的存储结构，以及两个顺序栈的辅助存储结构。
*头文件以及存储结构*/
#include<>
#include<>
#include<>
#include<>
#define true 1
#define false 0
#define ok 1
#define error 0
#define overflow 0
typedef int status;
2、表达式的抽象数据类型定义。
adt expression
基本操作：status input_expr(&string,flag)
操作结果：以字符序列的形式输入语法正确的前缀表达式，保存到字符串string； 参数flag表示输出的提示信息是什么，输入成功返回ok，否则，返回error。
void judge_value(&e,&string,i)
初始条件：树e存在，表达式的前缀字符串string存在；
操作结果：判断字符string[i]，如果是'0'-'9'常量之间，二叉树结点e存为整型；否则，存为字符型。
status readexpr(&e,&exprstring)
初始条件：表达式的前缀形式字符串exprstring存在；
操作结果：以正确的前缀表示式exprstring并构造表达式e，构造成功，返回ok，否则返回error。
status pri_compare(c1,c2)
初始条件：c1和c2是字符；
操作结果：如果两个字符是运算符，比较两个运算符的优先级，c1比c2优先，返回ok，否则返回error。
void writeexpr(&e)
初始条件：表达式e存在；
操作条件：用带括弧的中缀表达式输入表达式e。
void assign(&e,v,c,&flag)
初始条件：表达式e存在，flag为标志是否有赋值过；
操作结果：实现对表达式e中的所有变量v的赋值(v=c)。
long operate(opr1,opr,opr2)
初始条件：操作数opr1和操作数opr2以及操作运算符opr;
操作结果：运算符运算求值，参数opr1,opr2为常量，opr为运算符，根据不同的运算符，实现不同的运算，返回运算结果。
status check(e)
初始条件：表达式e存在；
操作结果：检查表达式e是否还存在没有赋值的变量，以便求算数表达式e的值。
long value(e)
初始条件：表达式e存在；
操作结果：对算术表达式求值，返回求到的结果。
void compoundexpr(p,&e1,e2)
初始条件：表达式e1和e2存在；
操作条件：构造一个新的复合表达式(e1)p(e2)。
status read_inorder_expr(&string,&pre_expr)
操作结果：以表达式的原书写形式输入，表达式的原书写形式字符串string变为字符串pre_expr，后调用reversal_string()函数反转得到前缀表达式pre_expr。得到正确的前缀表达式返回ok，否则，返回error。
void mergeconst(&e)
操作结果：常数合并操作，合并表达式e中所有常数运算。
adt expression
3、整体设计。
在这个课程设计中，有两个源**文件：和。
在文件中，包含了各个存储结构的声明和辅助存储结构的两个栈的基本操作；在文件中，是实现课程设计要求的各个函数。
一》文件的整体结构。
1、各个存储结构的声明；
2、两个除了栈名和栈存储的元素不一样的顺序栈的基本操作。其基本操作如下：
对于栈sqstack:
status initstack(sqstack *s) /构造一个空栈s */
status stackempty(sqstack s) /若栈s为空栈，则返回true，否则返回false */
status push(sqstack *s,selemtype e) /插入元素e为新的栈顶元素 */
status pop(sqstack *s,selemtype *e) /若栈不空，则删除s的栈顶元素，用e返回其值，并返回ok；否则返回error */
status gettop(sqstack s,selemtype *e) /若栈不空，则用e返回s的栈顶元素，并返回ok；否则返回error */
对于栈sqstack1:
status initstack1(sqstack1 *s) /构造一个空栈s */
status stackempty1(sqstack1 s) /若栈s为空栈，则返回true，否则返回false */
status push1(sqstack1 *s,selemtype1 e) /插入元素e为新的栈顶元素 */
status pop1(sqstack1 *s,selemtype1 *e) /若栈不空，则删除s的栈顶元素，用e返回其值，并返回ok；否则返回error */
status gettop1(sqstack1 s,selemtype1 *e) /若栈不空，则用e返回s的栈顶元素，并返回ok；否则返回error */
顺序栈的基本操作的算法见程序清单。
二》文件的整体结构。
1、主程序模块的整体流程。
可以从主菜单函数可以明了的了解的程序的整体流程，主菜单函数menu()如下：
char menu()
char choice;
printf("
printf(" 1 >>输入正确的前缀表达式");
printf(" 2 >>带括弧的中缀表示式输出");
printf(" 3 >>对变量进行赋值");
数据结构课程设计报告
东莞理工学院城市学院。题目 二叉排序树 专业 计算机科学与技术 本 年级 2010级计算机科学与技术专业 1 班。个人姓名 何振江。指导教师 张娟老师 时间 2010至2011第二学期第18周 地点 实验楼615机房 东莞理工学院城市学院计算机与信息科学系制。2011年 6月。实习报告的内容。一 问...
数据结构课程设计报告
设计一个校园导游程序，为来访的客人提供信息查询服务。1 设计学校的校园平面图。选取若干个有代表性的景点抽象成一个无向带权图 无向网 以图中顶点表示校内各景点，边上的权值表示两景点之间的距离。2 存放景点代号 名称 简介等信息供用户查询。3 为来访客人提供图中任意景点相关信息的查询。4 为来访客人提供...
数据结构课程设计报告
河北科技大学。课程设计报告。学生姓名学号。专业班级。课程名称数据结构。学年学期 2 012 2 013学年第 2 学期指导教师 黄春茹。2 0 13年 6 月。课程设计成绩评定表。一 数据结构课程设计目标。二 问题描述。三 需求分析。四 概要设计。五 详细设计。六 软件说明书 给出软件如何使用，使用...