数据结构表达式求值实验报告 (2).docVIP

1 淮 海 工 学 院 计算机工程学院 课程设计报告 设计名称 设计名称 数据结构课程设计 选题名称 选题名称 通讯录管理系统 姓姓 名 名 谢猛男 学学 号 号 2012122681 专业班级 专业班级 网络工程 网络 122 系系 院 院 计算机工计算机工程学院程学院 设计时间 设计时间 2013 12 23 2013 1 3 设计地点 设计地点 软件工程实验室 教室软件工程实验室 教室 2 指导教师评语 签名 签名 年年 月月 日日 目录目录 1 前前言言 设计表达式求值 设计到栈的应用 设计表达式求值 设计到栈的应用 2 概要设计概要设计 2 12 1 数据结构设计数据结构设计 2 22 2 算法设计算法设计 2 32 3 ADTADT 描述描述 2 42 4 功能模块分析功能模块分析 3 详细设计详细设计 3 13 1 数据存储结构设计数据存储结构设计 3 23 2 主要算法流程图 或算法代码 主要算法流程图 或算法代码 4 软件测试软件测试 成绩 成绩 3 5 5 总结总结 附 录 1 前 言 在现实生活中 我们在好多方面需要用到计算 列如计算器的应用 网络上的计算 都要 应用到计算 所以表达式求值就比较重要 表达式求值 涉及到操作数和运算符 即需要 设两个栈 分别用来存储操作数和运算符 另外还涉及运算符的优先级别 所以通过优先 级别表来达到计算 的效果 2 2 概要设计 概要设计 2 1 数据结构设计 任何一个表达式都是由操作符 运算符和界限符组成的 我们分别用顺序栈来寄存表 达式的操作数和运算符 栈是限定于紧仅在表尾进行插入或删除操作的线性表 顺序栈的 存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素 同时附设指针 top 指示栈顶元素在顺序栈中的位置 base 为栈底指针 在顺序栈中 它始终指向栈底 即 top base 可作为栈空的标记 每当插入新的栈顶元素时 指针 top 增 1 删除栈顶元素 时 指针 top 减 1 代码中设立两个栈 用来存储操作数和运算符 2 2 算法设计 为了实现算符优先算法 可以使用两个工作栈 一个称为 OPTR 用以寄存运算符 另 一个称做 OPND 用以寄存操作数或运算结果 1 首先置操作数栈为空栈 表达式起始符 为运算符栈的栈底元素 2 依次读入表达式 若是操作符即进 OPND 栈 若是运算符则和 OPTR 栈的栈顶运算符 比较优先权后作相应的操作 直至整个表达式求值完毕 即 OPTR 栈的栈顶元素和当前读入 的字符均为 2 3 ADT 描述 ADT Stack 4 数据对象 D ElemSet i 1 2 n n 0 i a i a 数据对象 R1 i 2 n 1 ii aa 1 i aDai 约定端为栈顶 端为栈底 n a i a 基本操作 InitStack char base char top Stack 定义整型栈 typedef struct int stacksize int base int top Stack2 3 2 主要算法流程图 或算法代码 1 Precede char c1 char c2 判断运算符优先权 返回优先权高的 6 算符间的优先关系如下 用一维数组存储 49 种情况 switch c1 i 为下面 array 的横标 case i 0 break case i 1 break case i 2 break case i 3 break case i 4 break case i 5 break case i 6 break switch c2 j 为下面 array 的纵标 case j 0 break case j 1 break case j 2 break case j 3 break case j 4 break case j 5 break case j 6 break return array 7 i j 返回运算符 array 7 i j 为对应的 c1 c2 优先关系 7 2 int EvalExpr 主要操作函数 算法概要流程图 利用该算法对算术表达式 3 7 2 求值操作过程如下 步骤OPTR 栈OPND 栈输入字符主要操作 1 3 7 2 Push OPND 3 2 3 7 2 Push OPTR 3 3 7 2 Push OPNR 4 37 2 Push OPND 7 5 3 7 2 Push OPNR 6 3 72 Push OPND 2 7 3 7 2 Operate 7 2 8 3 5 Pop OPTR 9 3 5 Operate 3 5 10 15 Return GetTop2 OPND 表 2 算法代码如下 int EvalExpr 主要操作函数 c ptr while c GetTop OPTR if In c 不是运算符即进栈 if In ptr 1 ptr ptr 1 Char c 表达式首字符 C GetTop OPTR ln c 进操作数栈 c ptr ReturnGetTop2 OPND Case 操作数栈头 2 个数进 行运算 8 m atoi ptr 取字符串前面的数字段 n num m Push2 将操作数入栈 ptr ptr n c ptr else switch Precede GetTop OPTR c case 退栈并将运算结果入栈 theta Pop b Pop2 a Pop2 Push2 break 4 4 软件测试 软件测试 1 运行成功后界面 9 2 输入正确的表达式后 3 更改表达式 输入有 2 位数的整数调试 10 5 5 总结总结 这次课程设计让我认识到数据结构在编程中的重要性 栈和队列的应用不仅实用 在编程 的过程中为我们解决了不少问题 方便了不少 利用了栈先进后出的特点 表达式求值的 优先级别问题也是通过网上搜集 找到了优先级别表 利用数组的方法 返回优先级别高 的数组 总之很顺利 代码是较为复杂 不过思路倒是蛮清晰的 最后 感谢老师在这次课程设计的悉心指导 祝老师身体健康 工作顺利 最后 感谢老师在这次课程设计的悉心指导 祝老师身体健康 工作顺利 附附 录录 程序源代码 include include include define NULL 0 define OK 1 define ERROR 1 define STACK INIT SIZE 100 define STACKINCREMENT 20 定义字符类型栈 typedef struct int stacksize char base char top Stack 定义整型栈 11 typedef struct int stacksize int base int top Stack2 全局变量 Stack OPTR 定义运算符栈 Stack2 OPND 定义操作数栈 char expr 255 存放表达式串 char ptr expr 指针指向表达式串 int InitStack Stack s 构造运算符栈 s base char malloc STACK INIT SIZE sizeof char if s base return ERROR s top s base s stacksize STACK INIT SIZE return OK int InitStack2 Stack2 s 构造操作数栈 s base int malloc STACK INIT SIZE sizeof int 12 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 为新的栈顶元素 s top ch s top return 0 int Push2 Stack2 s int ch 操作数栈插入 ch 为新的栈顶元素 s top ch s top return 0 13 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 return p int GetTop2 Stack2 s 用 p 返回操作数栈 s 的栈顶元素 int p s top 1 14 return p 判断运算符优先权 返回优先权高的 char Precede char c1 char c2 int i 0 j 0 static char array 49 switch c1 i 为下面 array 的横标 case i 0 break case i 1 break case i 2 break case i 3 break 15 case i 4 break case i 5 break case i 6 break switch c2 j 为下面 array 的纵标 case j 0 break case j 1 break case j 2 break case j 3 break case j 4 break case j 5 break case j 6 break return array 7 i j 返回运算符 操作函数 int Operate int a char op int b switch op 16 case return a b case return a b case return a b case return a b return 0 int num int n 返回操作数的长度 char p 10 itoa n p 10 把整型转换成字符串型 n strlen p return n int EvalExpr 主要操作函数 char c theta x int n m int a b c ptr 指向字符串的指针 while c GetTop OPTR 当前栈底元素不为 栈首元素也不为 17 if In c 判断是否为运算符 if In ptr 1 ptr ptr 1 m atoi ptr 取字符串前面的数字段 n num m Push2 将数字段压入操作数栈 ptr ptr n c ptr else swit