数据结构实验报告

课程设计实验报告课程设计实验报告 实验名称 实验名称 表达式类型的实现 编译环境 编译环境 硬件 PC 软件 VS2010 问题描述问题描述 一个表达式和一棵二叉树之间 存在着自然的对应关系 写一个程序 实现基于二叉 树表示的算术表达式 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 增加常数合并操作 MergeConst E 合并表达式中 E 的所有常数运算 例如 表达式 E 2 2 1 A 进行合并常数的操作后 求得 E 4 A 2 以表达式的原书写形式输入 需求分析需求分析 1 以字符序列的形式输入语法正确的中缀表示式并构造表达式 E 即要根据正确的前缀式建立 一棵二叉树 T 2 用带括弧的前缀表达式输出表达式 E 即要求在前缀遍历二叉树的时候考虑运算符的优先级 在适当的位置输出括弧 3 实现对变量 V 的赋值 V c 变量的初值为 0 那就在中缀遍历二叉树的过程中比较结点 的值是否为 V 找到 V 以后将 c 赋给 V 4 对算术表达式 E 求值 如果表达式中有变量的话 首先提示用户表达式中变量 建议先执行 操作 3 实现对变量 V 赋值 执行完后再回来执行表达式求值这一步骤 表达式求值利用递归 如果某个结点的值为运算符并且它的左右孩子结点的值为数据 那么就把 左孩子 运算符 右孩子 的结果赋给该结点 一层一层往上 最后只剩下一个根结点 此时根结点的值就是表达式 E 的值 5 构造一个新的复合表达式 E1 P E2 只要先构造表达式 E1 的二叉树和 E2 的二叉树 然后利用 P 把这两棵二叉树连接起来构成一棵新的二叉树 6 合并表达式 E 中所有常数运算 此原理类似于对表达式 E 求值 不同之处只在于该功能只对 常数合并 概要设计概要设计 1 树的抽象数据类型定义 ADT Tree 数据对象 D D 是具有相同特性的数据元素的集合 数据关系 R 若 D 为空集 则称为空树 若 D 仅含一个数据元素 则 R 为空集 否则 R H H 是如下二元关系 1 在 D 中存在唯一的称为根的数据元素 root 它在关系 H 下无前驱 2 若 D root 则存在 D root 的一个划分 D1 D2 Dm m 0 对任意 j k 1 j k m 有 Dj Dk 且对任意的 i 1 i m 唯一存在数 据元素 Xi Di 有 H 3 对应于 D root 的划分 H 有唯一的一 个划分 H1 H2 Hm m 0 对任意 j k 1 j k m 有 Dj Dk 且对 任意的 i 1 i m Hi 是 Di 上的二元关系 Di Hi 是一棵符合本定 义的树 称为根的 root 的子树 基本操作 Double Expression char exp 功能 算术表达式求值 double calculate double opnd1 char op double opnd2 功能 操作数四则运算 void push char char double ExpressionCalculateStack 功能 入栈 double pop char ExpressionCalculateStack 功能 出栈 void GetNextNotation char notation char exp 功能 读下一个运算符或操作数 char GetTypeOfNotation char notation 功能 判定是运算符或是操作数 int CompareOpPrior char op2 char op1 功能 运算符优先级别比较 BTNode ReadExpr char s int i int j 功能 读入表达式 void WriteExpr BTNode b 功能 把输入的表达式转换为相应的二叉树 并以前缀表达式的形式输出 char Seek char s int k 功能 判断是否有字母输入 void CompoundExpr char E1 char E2 char p 功能 复合表达式 void Assign char s char i char j 功能 对变量进行复制 流程图 流程图 程序清单 程序清单 头文件 头文件 MyExpression h include include include include include define MaxSize 100 typedef char ElemType typedef struct node ElemType data struct node lchild struct node rchild BTNode define MAX EXP LEN 128 表达式最大长度 define MAX NOTATION NUM 32 一个表达式中的最大算符个数 Mian 函 数 以中缀方 式输入表 达式 ReadExpr 以前缀方 式输出表 达式 WriteExpr 对式中的 变量进行 复制 Assign 查找式中 的变量 Seek 对算术 表达式 求值 是否有 变量 Y N 对变量 赋值 即执行 步骤 3 复合表达 式 常 数 合 并 123456 菜单 define MAX NOTATION LEN 20 表达式中一个算符的最大字串长度 define NULL 0 typedef struct stack 表达式计算堆栈 double OpdStack MAX NOTATION NUM 操作数堆栈 char OpStack MAX NOTATION NUM 运算符堆栈 int OpdStackTop 操作数堆栈顶指针 OpStackTop 运算符堆栈顶指针 ExpressionCalculateStack define OPND D 操作数类型标志 define OPTR R 运算符类型标志 define CONTINUE READ NEXT NOTATION C 表达式扫描标志 继续扫描 define STOP READ NEXT NOTATION S 表达式扫描标志 暂停扫描 部分子函数声明如下 主要是表达式求值函数 double Expression char exp 算术表达式求值 double calculate double opnd1 char op double opnd2 操作数四则 运算 void push char char double ExpressionCalculateStack 入栈 double pop char ExpressionCalculateStack 出栈 void GetNextNotation char notation char exp 读下一个运算符或操 作数 char GetTypeOfNotation char notation 判定是运算符或是操作 数 int CompareOpPrior char op2 char op1 运算符优先级别比较 源代码文件 源代码文件 MyExpression c include MyExpression h include stdlib h extern double Expression char oldexp extern int CompareOpPrior char op2 char op1 extern char GetTypeOfNotation char notation extern void GetNextNotation char notation char exp extern double calculate double opnd1 char op double opnd2 extern double pop char type ExpressionCalculateStack s extern void push char type char op double opnd ExpressionCalculateStack s BTNode ReadExpr char s int i int j BTNode p int k plus 0 posi if i j p BTNode malloc sizeof BTNode p data s i p lchild NULL p rchild NULL return p 以下是i j的情况 if i j for k i k j k if s k s k plus posi k if plus 0 for k i kdata s posi p lchild ReadExpr s i posi 1 p rchild ReadExpr s posi 1 j return p void WriteExpr BTNode b 把输入的表达式转换为相应的二叉树 并以前缀表达式的形 式输出 if b NULL printf c b data if b lchild NULL b rchild NULL printf WriteExpr b lchild if b rchild NULL printf WriteExpr b rchild printf char Seek char s int k 判断是否有字母输入 char a 1 0 int i for i 0 i A void Assign char s char i char j for int p 0 p strlen s 1 p if s p i s p j void CompoundExpr char E1 char E2 char p 复合表达式 char NewE MaxSize q 1 int k 0 i BTNode bt1 bt2 T if p p 复合函数为 或 是应怎样复合 for i 0 i strlen E1 i NewE i E1 i NewE strlen E1 p for k 0 k 0 s k 1 FX s k 1 s k 1 48 s k 1 48 48 for int i k i 0 for int i k i 0 for int i k i 0 for int i k i strlen s i s i s i 2 printf 常数合并后为 s s void MergeConst char s 常数合并 int i j n for i 0 i strlen s i if s i s i Conbination s i for j 0 j strlen s j if s j s j Conbination s j void main double fx 0 BTNode b int i 0 j 0 char s MaxSize yesORno value getvalue GetDigitl NULL p E1 7 E2 3 e1 e2 printf n n 表达式类型实现的使用说明 n n printf 表达式暂时还不能进行括号操作 请不要输入括号 n n printf 数字的输入只能是一位数 0 9 字母的输入a z或A Z n n printf 表达式输入时请按以下形式输入 A S D n n printf n n printf 1 输入表达式 2 输出表达式 n n printf 3 对变量赋值 4 对表达式求值 n n printf 5 复合表达式 6 常数合并 n n printf 7 返回 n n printf n n printf 请输入选择 1 7 while GetDigitl getchar 7 switch GetDigitl case 1 printf n n请以中缀表达式形式输入表达式 例如a b c d n n printf 你的输入 getchar gets s 以中缀表达式形式输入表达式 printf n printf 你输入的表达式为 s n s b ReadExpr s 0 strlen s 1 printf n请输入选择 1 7 n break case 2 printf n对应的二叉树 WriteExpr b printf n n printf n请输入选择 1 7 n break case 3 while yesORno Seek s strlen s 1 1 printf 表示式中有变量 n getchar printf 需要赋值的变量 value getchar getchar printf 变量值 getvalue getchar Assign s value getvalue b ReadExpr s 0 strlen s 1 printf n对应的二叉树 WriteExpr b printf n请输入选择 1 7 n break case 4 yesORno Seek s strlen s 1 if yesORno 1 printf 表达式中有未知变量 请选择3进行变量赋值 n else fx Expression s 表达式求值 printf n表达式的运算结果为 f n fx printf n请输入选择 1 7 n break case 5 printf 请从 中选择一个作为复合符号 n printf 你的选择是 getchar p getchar printf n printf 请输入要复合的第一个表达式 getchar gets E1 printf n printf 请输入要复合的第二个表达式 gets E2 printf n CompoundExpr E1 E2 p printf n请输入选择 1 7 n break case 6 MergeConst s printf n请输入选择 1 7 n break 一下是表达式求值函数 include MyExpression h double Expression char oldexp 表达式计算函数 输入的是表达式字符串 char notation MAX NOTATION LEN 存放当前符号扫描读入的符号 op1 op2 exp MAX EXP LEN 存放当前操作表达式 char flag CONTINUE READ NEXT NOTATION 判别是否继续扫描下去 int prior 存放算符优先级别比较结果 op2op1 1 op2 op1 0 double opnd1 opnd2 存放当前用于计算的2个操作数 ExpressionCalculateStack s 定义堆栈s s OpdStackTop s OpStackTop 0 strcpy exp oldexp 把原表达式复制给当前操作表达式 strcat exp 把 接到exp后面 原exp最后面的 0 被取消 push OPTR 0 0 初始化表达式计算堆栈 while 1 if flag CONTINUE READ NEXT NOTATION GetNextNotation notation exp else 有运算结果进操作数栈后 flag CONTINUE READ NEXT NOTATION if GetTypeOfNotation notation OPND opnd2 atof notation push OPND NULL opnd2 操作数处理 else 运算符处理 op2 notation 0 op1 char pop OPTR 运算符出栈 prior CompareOpPrior op2 op1 if prior 0 op2 0 op2 op2 opnd2 pop OPND opnd1 pop OPND opnd2 calculate opnd1 op1 opnd2 push OPND NULL opnd2 flag STOP READ NEXT NOTATION 暂停读入下一个表达式符号 使当前运算符与栈顶运算符再作一次比较 if prior 0 op2 op1 的情况处理 if op2 return pop OPND 结束运算 将运算结果从堆栈中弹出 void push char type char op double opnd ExpressionCalculateStack s if type OPND s OpdStack s OpdStackTop opnd else s OpStack s OpStackTop op double pop char type ExpressionCalculateStack s if type OPND 是操作数栈 return s OpdStack s OpdStackTop else 是运算符栈 return double s OpStack s OpStackTop double calculate double opnd1 char op double opnd2 switch op case return opnd1 opnd2 case return opnd1 opnd2 case return opnd1 opnd2 case if opnd2 0 0 return opnd1 opnd2 else return 0 0 return 0 0 void GetNextNotation char notation char exp 读入下一个完整的符号 操作数或运算符 把一个完整的操作数或运算符保存到notation static int i 0 变量i为表达式扫描的当前位置 注意其类型 int j char type lasttype GetTypeOfNotation exp i for j 0 exp i 0 j i if exp i continue notation j exp i type GetTypeOfNotation notation j if type OPTR break 第一次读到的就是 运算符 if type OPTR 由读到的不是运算符转为读到的是 运算符 lasttype type notation j NULL if notation 0 i 0 表达式扫描完毕 char GetTypeOfNotation char notation 判断一个字符是不是运算符 char opstr 运算符集 int i if notation 0 0 return NULL for i 0 opstr i 0 i if notation 0 opstr i return OPTR R 即是运算符 return OPND D 即是操作数或小数点或其它如空格等 int CompareOpPrior char op2 char op1 2个先后出现的运算符优先级别比较 按P53表3 1 定 char opstr int i j int priortable 7 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 I 1 1 1 1 I 1 1 1 1 1 1 1 I 0 for i 0 opstr i 0 i if op1 opstr i break for j 0 opstr j 0 j if op2 opstr j break return priortable i j 测试分析与用户使用步骤 测试分析与用户使用步骤 出初始界面如下 数据测试 测试结果如下 选择操作1 操作结果如下 输入你想呀输入的表达式 输入表达式后 继续选择你要执行的操作 选择2操作 此操作是将以中缀形式输入的表达式 构造成一棵树 然后以二叉树的先序遍 历的形式输入其结果 其结果如下 执行完操作2后 继续选择你要的操作 选择3操作是将表达式中的变量进行赋值 直到表达式中的所有变量都赋上确切的值位置为 止 并以所对应的二叉树的先序遍历的形式输出其结果 其执行结果如下 执行完操作3后 即可执行4的操作 对表达式求值 若表达式中有变量 没有经过执行操 作3而是直接执行操作4的话 程序会提醒用户先去执行操作3后 再回来执行操作4 其操 作结果如下 变量已赋值 变量若尚未赋值 执行完操作4后 接下来的就只有操作5没执行而已了 操作5是对用户输入的两个表达式进行复合 复合符号为 或 跟复合符号为 或 其复合的 方式不一样 其操作结果如下 以上是复合符号为 和复合符号