数据结构课程实验报告-实验5

《数据结构课程实验报告-实验5》由会员分享，可在线阅读，更多相关《数据结构课程实验报告-实验5（22页珍藏版）》请在装配图网上搜索。

1、数据结构课程实验报告- 实验 5数据结构课程实验指导书HUNANUNIVERSITY课程实习报告题目：四则运算表达式求值学生姓名康 小 雪学生学号20090810310专业班级计科三班指导老师李晓 鸿完成日期2010-10-24 2数据结构课程实验指导书 3数据结构课程实验指导书一、 需求分析1该程序可以从通过从键盘输入一个中缀表达式，判断该表达式是否合法，若合法将其转化为后缀表达式，并计算其结果，否则说明该表达式错误2 .输入的表达式包含数字和运算符及括号，之间用空格隔开3数字可以为整数和小数4运算结果保留两位小数输入输出举例输入： 21+23* （12-6）输出： 21 23 12 6 -

2、*+二、 概要设计在表达式中每个运算符应对应两个操作数，与二叉树中非叶子结点和叶子结点之间的关系刚好相同，于是，本题可采用二叉树来将中缀表达式变为后缀表达式。最后用堆栈来实现后缀表达式的计算。抽象数据类型二叉树ADT BiTree 4数据结构课程实验指导书数据对象 D：D 是具有相同特性的数据元素集合数据关系R：若 D 为空集，则 R 为空集，则称 BinaryTree为空二叉树；若 D 不为空集，否则 R=H ，H 是如下二元关系：（ 1） 在 D 中存在唯一的称为根的数据元素root ，它在关系 H 下无前驱；（2）若 D-root 空集，则存在D-root的一个划分 D1,Dr 且 D1

3、Dr=空集；（3） 若 D1空集，则 D1 中存在唯一元素x1，H, 且存在 D1shang de guanxi H1=H;ruo Dr 空集，则 Dr 中存在唯一的元素， xr ， H，且存 在 Dr 上 的 关 系 Hr H;H=,H1,Hr;（ 4） (D1,H1) 是一棵符合本定义的二叉树，称为根的左子树， (Dr ，Hr) 是一棵符合本定义的二叉树，称为根的右子树基本操作 P:InitBiTree（&T） 5数据结构课程实验指导书操作结果：构造空二叉树TDestroyBiTree （&T）初始条件：二叉树T 存在操作结果：销毁二叉树TCreateBiTree （&T，definiti

4、on）初始条件： definition给出二叉树 T 的定义操作结果：按 definition构造二叉树 TClearBiTree （&T）初始条件：二叉树T 存在操作结果：将二叉树T 清空为空树TreeBiEmpty(T)初始条件：二叉树T 存在操作结果：若二叉树 T 为空树，则返回 TRUE，否则返回 FALSETreeBiDepth （T）初始条件：二叉树T 存在操作结果：返回二叉树T 的深度Root（T）初始条件：二叉树T 存在操作结果：返回T 的根Value （T,cur_e ）初始条件：二叉树T 存在， cur_e 是 T 中的某 6数据结构课程实验指导书个结点操作结果：返回cur

5、_e 的值Assign （T, cur_e ，value ）初始条件：二叉树 T 存在， cur_e 是 T 中的某个结点操作结果：结点 cur_e 赋值为 value Parent （T,cur_e ）初始条件：而擦树 T 存在， cur_e 是 T 中的某个结点操作结果：若 cur_e 是非根结点， 则返回它的双亲，否则函数值为空LeftChild（T，cur_e ）初始条件：二叉树 T 存在， cur_e 是 T 中的某个结点操作结果：若 cur_e 是 T 的非叶子结点， 则返回它的最左孩子，否则返回空RightChild（&T,&p,i ）初始条件：二叉树 T 存在， cur_e 是

6、 T 中的某个结点操作结果：若 cur_e 有右兄弟，则返回它的右兄弟，否则函数值为空LeftSibling（T,e ） 7数据结构课程实验指导书初始条件：二叉树 T 存在， e 是 T 中的某个结点操作结果：返回 e 的左兄弟，若 e 是 T 的左孩子或无左兄弟，返回空RightSibling（T,e ）初始条件：二叉树T 存在， e 是 T 中的某个结点操作结果：返回 e 的右兄弟，若 e 是 T 的右孩子或无右兄弟，返回空InsertChild（&T,&p,I,c）初始条件：二叉树 T 存在， p 指向 T 中某个结点， 1=i=p 所指结点的度 +1，非空树 c 与 T 不相交操作结果

7、：插入 c 为 T 中 p 指结点的第 i 棵子树DeleteChild（&T,&p,i ）初始条件：树 T 存在， p 指向 T 中某个结点，1=i=0 9数据结构课程实验指导书数据关系： R1= ai 1 ，ai | ai 1，ai D,i=2, ,n 基本操作：InitStack(&S)操作结果：构造一个空栈SDestroyStack （&S ）初始条件：栈 S 已存在操作结果：栈 S 被销毁ClearStack （&S ）初始条件：栈 S 已存在操作结果：栈 S 清为空栈StackEmpty （S）初始条件：栈 S 已存在操作结果：若S 为空栈，则返回TRUE, 否则FALSEStac

8、kLength （S）初始条件：栈 S 已存在操作结果：返回S 元素的个数，即栈的长度GeTop（S,&e）初始条件：栈 S 已存在且非空操作结果：用 e 返回 S 的栈顶元素Push（&S ，e）初始条件：栈 S 已存在10数据结构课程实验指导书操作结果：插入元素 e 为新的栈顶元素Pop（&S,&e ）初始条件：栈 S 已存在且非空操作结果：删除 S 的栈顶元素，并返回 e StackTraverse（S,visit() ）初始条件：栈 S 已存在且非空操作结果：从栈底到栈顶依次对 S 的每个元素调用函数 visit() ，一旦 visit() 失败，则操作失败ADT Stack算法的基本

9、思想以(A+B)*(C-D/E) 这样一个表达式为列求它的后缀表达式按照优先级加上括号，得到： (A+B)*(C-(D/E)然后从最外层括号开始，依次转化成二叉树1、根是 * ，左子树 (A+B) ，右子树 (C-(D/E)2、右子树的根 -，右子树的左子树C，右子树的右子树 (D/E)3、(A+B)的根 +，左子树 A ，右子树 B4、(D/E) 的根 /，左子树 D，右子树 E可以画出表达式对应的 2 叉树，操作数作为叶子节点，操作符作为非叶子节点 , 如图所示。*+-11ABC/数据结构课程实验指导书再逆序遍历二叉树可得逆波兰表达式为：AB+CDE/-*利用堆栈的方法计算后缀表达式的值程

10、序的流程程序由三个模块组成：（ 1）输入模块：在主函数中输入中缀表达式（ 2）转换模块：将中缀表达式转换为后缀表达式，并打印（ 3）计算模块：生成的后缀表达式用于计算，打印最后结果三、详细设计物理数据类型二叉树12数据结构课程实验指导书#define Max_TREE_SIZE 100Typedef TElemType SqBiTreeMAX_TREE_SIZE;SqBiTree bt;堆栈#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OK 1#define TRUE 1#define FALSE 0#define

11、ERROR 0#define OVERFLOW -2typedef float SElemtype;typedef int Status;算法的具体步骤/基本操作的函数原型/二叉树的存储结构表示Typedef struct BiTNodeTElemType data;Srtuct BiTNode *lchild,*rchild;13数据结构课程实验指导书BiTNode,*BiTree;/基本操作的函数原型说明Status CreatBiTree(BiTree &T)/按先序次序插入二叉树中结点的值（一个字符）/构造二叉链表表示二叉树TStatus PreOrderTraverse （BiTre

12、eT,Status (*Visit)(TELemType e) ）/采用二叉链表的存储结构，Visit 是对结点操作的应用函数/先序遍历二叉树，对每个结点调用且仅调用一次 Visit 函数/一旦 Visit 函数失败则操作失败Status InOrderTraverse （ BiTreeT,Status(*Visit)(TELemType e) ）/采用二叉链表的存储结构，Visit 是对结点操作的应用函数/中序遍历二叉树，对每个结点调用且仅调用一次 Visit 函数/一旦 Visit 函数失败则操作失败Status PostOrderTraverse （BiTreeT,Status (* V

13、isit)(TELemType e) ）14数据结构课程实验指导书/采用二叉链表的存储结构， Visit 是对结点操作的应用函数/后序遍历二叉树，对每个结点调用且仅调用一次 Visit 函数/一旦 Visit 函数失败则操作失败/堆栈的存储结构表示typedef structSElemtype * base;SElemtype * top;int stacksize; SqStack;Status InitStack(SqStack &S)S.base = (SElemtype *)malloc(STACK_INIT_SIZE*sizeof(SElemtype );if (! S.base)

14、exit(OVERFLOW); S.top = S.base;S.stacksize = STACK_INIT_SIZE; return OK;15数据结构课程实验指导书int StackLength(SqStack S)/获得堆栈元素的个数/填空return S.top-S.base;Status Push(SqStack &S, SElemtype e)/入栈/填空S.top+;*(S.top)=e;return true;Status Pop(SqStack &S, SElemtype &e)/出栈16数据结构课程实验指导书/填空if(S.topS.base) return false ;e=*(S.top);S.top-;return true;算法的时空分析遍历所有的结点上限是 O(n), 故此算法的增长率上限为 O(n)输入和输出的格式请输入中缀表达式： /输出/等待输入/输出后缀表达式后缀表达式：/输出结果运算结果为：四、调试分析略。五、测试结果六、用户使用说明（可选）17数据结构课程实验指导书七、实验心得（可选）略。七、附录（可选）Gcd.c 主程序18