广工数据结构课程设计实验报告.docxVIP

广工数据结构课程设计实验报告　数据结构课程设计实验报告　程序分析题目1：｛二叉树binaryTree｝　1、需求分析　1）输入的形式和输入值的范围输入二叉树的节点序列：Char型变量2）输出的形式树状输出二叉树；　先序遍历二叉树char型；中序遍历二叉树char型；后序遍历二叉树char型；输出叶子结点char型；输出叶子结点个数int型；输出二叉树的深度int型；　3）程序所能达到的功能(1)树状输出二叉树；(2)先序遍历二叉树；(3)中序遍历二叉树；(4)后序遍历二叉树；(5)输出叶子结点；(6)输出叶子结点个数；(7)输出二叉树的深度；(8)退出　4）测试数据：包括正确的输入及输出结果和含有错误的输入及输出结果输入：abc##de#f##g###　输出：先序遍历：abcdefg　中序遍历：cbefdga后序遍历：cfegdba叶子结点：cfg叶子结点个数：3二叉树的深度：5　2、概要设计(1)抽象数据类型的定义　typedefstructBiTNode//定义二叉树节点结构{　chardata;//数据域　structBiTNode*LChild,*RChild;//左右孩子指针域}BiTNode,*BiTree;BiTreeT;　(2)子程序的功能　(1)建立二叉树voidCreateBiTree(BiTree*bt)(2)树型打印二叉树voidTranslevelPrint(BiTreebt)(3)输出结点voidVisit(charch)　(4)先序遍历二叉树voidPreOrder(BiTreeroot)(5)中序遍历二叉树voidInOrder(BiTreeroot)(6)后序遍历二叉树voidPostOrder(BiTreeroot)(7)输出叶子结点voidPreOrderLeaf(BiTreeroot)(8)输出叶子结点的个数intLeafCount(BiTreeroot)(9)输出二叉树的深度intPostTreeDepth(BiTreeroot)(3)函数和过程的调用关系图　3、详细设计主程序:　(1)建立二叉树voidCreateBiTree(BiTree*bt)voidmain()输入二叉树的节点序列　(2)voidmainwork()根据输入信息，测算树型打印二叉树、输出结点、先序遍历二叉树、中序遍历二叉树、后序遍历二叉树、输出叶子结点、输出叶子结点的个数、输出二叉树的深度　(4)先序遍历二叉树voidPreOrder(BiTreeroot)根、左、右遍历二叉树(5)中序遍历二叉树voidInOrder(BiTreeroot)左、根、右遍历二叉树(6)后序遍历二叉树voidPostOrder(BiTreeroot)左、右、根遍历二叉树(7)输出叶子结点voidPreOrderLeaf(BiTreeroot)(8)输出叶子结点的个数intLeafCount(BiTreeroot)(9)输出二叉树的深度intPostTreeDepth(BiTreeroot)(10)退出　4、测试分析　1）调试过程中遇到的问题是如何解决的　一开始怎么输入都是“输入选择不明确，请重输”，后来就发现，空格要用“#”表示，全部输完要用更多的“#”表示已经输入完成。2）算法的时间复杂度分析时间复杂度：O3）经验和体会　经过不断地修改完善二叉树的代码，对二叉树的理解又更深了一层，相信不久就能完全掌握这一结构算法。　4）测试功能展示、树状输出二叉树　、先序遍历二叉树　、中序遍历二叉树　、后序遍历二叉树　、输出叶子节点　、输出叶子节点个数　数据结构课程设计实验报告题目：表达式求值问题　1.问题描述　表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*/3。中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀式和前缀式。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。　2.数据结构设计　本题中使用顺序栈用来存取运算符和运算数，顺序栈类的定义如下：　//顺序栈类定义　template　classSqStack　{　private:T*base;//栈底指针inttop;//栈顶intstacksize;//栈容量　};public:SqStack(intm);//构建函数~SqStack(){delete[]base;top=0;stacksize=0;}//析构函数voidPush(Tx);//入栈TPop();//出栈TGetTop();//获取栈顶元素intStackEmpty();//测栈空voidClearStack();//清空栈voidStackTop();//返回栈