数据结构上机报告

1、精选优质文档-倾情为你奉上数据结构上机题3表达式二叉树：表达式可以用表达式二叉树来表示。对于简单的四则运算，实现以下功能：1、 对于任意给出的前缀表达式（不带括号）、中缀表达式（可以带括号）、后缀表达式（不带括号），能够在计算机内部构造出一颗表达式二叉树，并且以图示显示出来（字符图货图形的形式）2、 对于构造好的内部表达式二叉树，按照用户的要求，输出相应的前缀表达式（不带括号）、中缀表达式（可以带括号，但不允许冗余括号）货后缀表达式（不带括号）。2015、5、211、 需求分析1、输入形式、输入值的范围：输入为正确的前缀、后缀、中缀表达式；2、输出形式：输出为除了输入的表达式以外的其它两种形式

2、的表达式以及所输入表达式所构建的二叉树；3、程序功能：将所输入的任意前缀、中缀、后缀表达式转换成其它两种形式的表达式，并将输入的表达式构建成二叉树的形式输出；二、概要设计1、ADT定义： 1）二叉树结点ADT： class BinaryTreeNode/二叉树结点类private: T value;/结点数据域 BinaryTreeNode<T> *leftChild; /左孩子结点 BinaryTreeNode<T> *rightChild;/右孩子结点public: BinaryTreeNode()leftChild = NULL,rightChild = NULL

3、; /构造函数（左右孩子初始化为空） BinaryTreeNode(const T&);/构造函数（结点值初始化） BinaryTreeNode(const T&,BinaryTreeNode<T> *,BinaryTreeNode<T> *);/构造函数（结点值及左右孩子均初始化） void setValue(const T&);/设置结点值 T getValue()const;/返回结点值 BinaryTreeNode<T> * getLeftChild()const;/返回左孩子结点 BinaryTreeNode<T>

4、; * getRightChild()const;/返回右孩子结点 void setLeftChild(BinaryTreeNode<T> *leftChild);/设置左孩子结点 void setRightChild(BinaryTreeNode<T> *rightChild);/设置右孩子结点 bool isLeaf()const;/判断是否为树叶; 2）表达式二叉树ADTclass ExpressionBinaryTree/表达式二叉树类private: BinaryTreeNode<string> *root;/字符串型的二叉树结点void recu

5、rsionDeleteAll(BinaryTreeNode<string> *root);/递归函数清空二叉树，释放空间 void clear() /清空函数 if(root = NULL) return; recursionDeleteAll(root); int getHeight(BinaryTreeNode<string> *root);/求树的高度 bool aIsGreaterOrEqualThanB(char a,char b);/比较a,b优先级 void printBlank(int n);/打印n个空格 void printInRightFormat

6、(string value);/按照格式打印，以便对齐 void recursionPrintPreffixE(BinaryTreeNode<string> *root);/递归调用打印前缀表达式 void recursionPrintSuffixE(BinaryTreeNode<string> *root);/递归调用打印后缀表达式 bool shouldPrintLeftBracket(const stack<BinaryTreeNode<string>*> &nodeStack ,BinaryTreeNode<string&g

7、t; *pointer,int leftOrRight);/用于输出中缀表达式时判断是否需要输出左括号public: ExpressionBinaryTree();/构造函数 ExpressionBinaryTree()clear();/析构函数 void buildBTreeByPreffixE();/以前缀表达式构建二叉树 void buildBTreeByInfixE();/以中缀表达式构建二叉树 void buildBTreeBySuffixE();/以后缀表达式构建二叉树 void printEBTree();/打印二叉树字符图 void printPreffixE()recursi

8、onPrintPreffixE(root); cout << endl;/打印前缀表达式 void printSuffixE()recursionPrintSuffixE(root); cout << endl;/打印后缀表达式 void printInfixE();/打印中缀表达式;2、 主程序流程：开始（main）ExpressionBinaryTree ebt /创建表达式二叉树的对象选择需要输入的表达式类型根据输入的表达式进行其它形式表达式的转换并构建二叉树 输出是是否继续输入 否（q） 结束3、 详细设计实现ADT定义的数据类型：stack<Binary

9、TreeNode<string> *>二叉树节点字符串类型的栈；queue<BinaryTreeNode<string> *>二叉树节点类型的字符串类型队列。4、 用户使用说明根据提示输入正确的表达式（前缀表达式，中缀表达式，后缀表达式任选一）5、 测试结果运行程序：根据提示输入相应的正确表达式选择2，输入中缀表达式（12+13）*2-（15*6）/10选择1，输入前缀表达式选择3，输入后缀表达式6、 源程序#include <tchar.h>/为了兼容字符集,使用字符串宏，主要用来定义 ascii码和unicode 的标准化，使代码移植后

10、，不需要修改相应的代码，重新编译即可使用。#include <stack>/STL堆栈容器#include <sstream>/基于字符串的流,字符串流的输入输出操作 #include <queue>/STL队列容器#include <list>/STL线性列表容器 (将元素按顺序储存在链表中)#include <cmath>/包含了许多数学函数的库文件#include <iostream>using namespace std;template<class T>class BinaryTreeNode/二叉树

11、结点类private: T value;/结点数据域 BinaryTreeNode<T> *leftChild; /左孩子结点 BinaryTreeNode<T> *rightChild;/右孩子结点public: BinaryTreeNode()leftChild = NULL,rightChild = NULL; /构造函数（左右孩子初始化为空） BinaryTreeNode(const T&);/构造函数（结点值初始化） BinaryTreeNode(const T&,BinaryTreeNode<T> *,BinaryTreeNode

12、<T> *);/构造函数（结点值及左右孩子均初始化） void setValue(const T&);/设置结点值 T getValue()const;/返回结点值 BinaryTreeNode<T> * getLeftChild()const;/返回左孩子结点 BinaryTreeNode<T> * getRightChild()const;/返回右孩子结点 void setLeftChild(BinaryTreeNode<T> *leftChild);/设置左孩子结点 void setRightChild(BinaryTreeNode

13、<T> *rightChild);/设置右孩子结点 bool isLeaf()const;/判断是否为树叶;template<class T>BinaryTreeNode<T>:BinaryTreeNode(const T&V)/构造函数（结点值初始化） value = V; leftChild = rightChild = NULL;template<class T>BinaryTreeNode<T>:BinaryTreeNode(const T&V,BinaryTreeNode<T> *L,Binary

14、TreeNode *R)/构造函数（结点值及左右孩子均初始化） value = V; leftChild = L; rightChild = R;template<class T>void BinaryTreeNode<T>:setValue(const T&V)/设置结点的值 value = V;template<class T>T BinaryTreeNode<T>:getValue()const/返回结点值 return value;template<class T>BinaryTreeNode<T>* Bi

15、naryTreeNode<T>:getLeftChild()const/返回左孩子结点 return leftChild;template<class T>BinaryTreeNode<T>* BinaryTreeNode<T>:getRightChild()const/返回右孩子结点 return rightChild;template<class T>void BinaryTreeNode<T>:setLeftChild(BinaryTreeNode<T> *leftChild)/设置左孩子结点 this-

16、>leftChild = leftChild;template<class T>void BinaryTreeNode<T>:setRightChild(BinaryTreeNode<T> *rightChild)/设置右孩子结点 this->rightChild = rightChild;template<class T>bool BinaryTreeNode<T>:isLeaf()const/判断是否为树叶if(leftChild = NULL && rightChild = NULL)return t

17、rue;return false;class ExpressionBinaryTree/表达式二叉树类private: BinaryTreeNode<string> *root;/字符串型的二叉树结点void recursionDeleteAll(BinaryTreeNode<string> *root);/递归函数清空二叉树，释放空间 void clear() /清空函数 if(root = NULL) return; recursionDeleteAll(root); int getHeight(BinaryTreeNode<string> *root)

18、;/求树的高度 bool aIsGreaterOrEqualThanB(char a,char b);/比较a,b优先级 void printBlank(int n);/打印n个空格 void printInRightFormat(string value);/按照格式打印，以便对齐 void recursionPrintPreffixE(BinaryTreeNode<string> *root);/递归调用打印前缀表达式 void recursionPrintSuffixE(BinaryTreeNode<string> *root);/递归调用打印后缀表达式 bool

19、 shouldPrintLeftBracket(const stack<BinaryTreeNode<string>*> &nodeStack ,BinaryTreeNode<string> *pointer,int leftOrRight);/用于输出中缀表达式时判断是否需要输出左括号public: ExpressionBinaryTree();/构造函数 ExpressionBinaryTree()clear();/析构函数 void buildBTreeByPreffixE();/以前缀表达式构建二叉树 void buildBTreeByInf

20、ixE();/以中缀表达式构建二叉树 void buildBTreeBySuffixE();/以后缀表达式构建二叉树 void printEBTree();/打印二叉树字符图 void printPreffixE()recursionPrintPreffixE(root); cout << endl;/打印前缀表达式 void printSuffixE()recursionPrintSuffixE(root); cout << endl;/打印后缀表达式 void printInfixE();/打印中缀表达式; static const int LEFT;/为左子结点

21、static const int RIGHT;/为右子结点ExpressionBinaryTree:ExpressionBinaryTree()root=NULL;void ExpressionBinaryTree:recursionDeleteAll(BinaryTreeNode<string> *root)/递归清空二叉树 if(root->getLeftChild() != NULL) recursionDeleteAll(root->getLeftChild(); if(root->getRightChild() != NULL) recursionDel

22、eteAll(root->getRightChild(); delete root;int ExpressionBinaryTree:getHeight(BinaryTreeNode<string> *root)/求树的高度 if(root = NULL) return 0; int left = getHeight(root->getLeftChild(); int right = getHeight(root->getRightChild(); return left > right ? left+1 : right+1;bool ExpressionB

23、inaryTree:aIsGreaterOrEqualThanB(char a,char b)/比较a,b的优先级 switch (a) case '*': case '/': return true; case '+': case '-': if(b = '*' | b = '/') return false; return true; case '(': return false; return false;void ExpressionBinaryTree:printBlank

24、(int n) for(int i = 0;i < n;+i) cout << " "void ExpressionBinaryTree:printInRightFormat(string value)/按照格式打印，以便对齐 switch (value.length() case 1:/如果就1个字符，则在两端打印空格，以便对齐 cout << " " cout << value << " " break; case 2:/如果2个字符，则在其后补一个空格，以便对齐 cout &

25、lt;< value << " " break; case 3: cout << value;/如果3个字符，则不用补空格 break; void ExpressionBinaryTree:recursionPrintPreffixE(BinaryTreeNode<string> * root)/递归调用打印前缀表达式 if(root = NULL) return; cout << root->getValue() << " " recursionPrintPreffixE(root

26、->getLeftChild(); recursionPrintPreffixE(root->getRightChild();void ExpressionBinaryTree:recursionPrintSuffixE(BinaryTreeNode<string> * root)/递归调用打印后缀表达式 if(root = NULL) return; recursionPrintSuffixE(root->getLeftChild(); recursionPrintSuffixE(root->getRightChild(); cout << r

27、oot->getValue() << " "bool ExpressionBinaryTree:shouldPrintLeftBracket(const stack<BinaryTreeNode<string> *> &nodeStack ,BinaryTreeNode<string> *pointer ,int leftOrRight)/是否应该添加左括号 if(nodeStack.empty() | pointer = NULL) return false; char a = nodeStack.top()-

28、>getValue().c_str()0;/a b 为栈中父子关系的两个结点值的首字母(为了区分是数字还是操作符) char b = pointer->getValue().c_str()0; if(b >= '0' && b <= '9')/如果是数字，则不用打括号 return false; if(leftOrRight = LEFT)/如果pointer是左结点 switch (a) case '*': case '/': if(b = '*' | b = '/

29、') return false; return true; case '+': case '-': return false; return false; else if(leftOrRight = RIGHT)/如果pointer是右结点 switch (a) case '*': case '/': return true; case '+': case '-': if(b = '+' | b = '-') return true; return false

30、; return false;void ExpressionBinaryTree:buildBTreeByPreffixE() clear(); root = new BinaryTreeNode<string>(); char c; cout << "请输入前缀表达式（以=结尾）：" cin >> c; stack<BinaryTreeNode<string> *> parentStack;/用于保存存放父结点 BinaryTreeNode<string> *pointer = root;/用于指向下

31、一个保存数据的结点 string blankStr = "" double tempDouble = 0; string tempStr;/用于输入流，将浮点数转换成字符串 while(c != '=') switch (c) case '+': case '-': case '*': case '/': pointer->setValue(c+blankStr);/设置当前结点的值 pointer->setLeftChild(new BinaryTreeNode<string

32、>();/生成左结点 parentStack.push(pointer); pointer = pointer->getLeftChild(); break; default: cin.putback(c); cin >> tempDouble; stringstream sss; sss << tempDouble; sss >> tempStr; pointer->setValue(tempStr); pointer = parentStack.top(); while(pointer->getRightChild()!=NULL

33、) parentStack.pop();/找到按前序遍历的下一个结点 if(parentStack.empty() break; pointer = parentStack.top(); if(parentStack.empty()/如果此时栈空则表明表达式已经构建完成 break; pointer->setRightChild(new BinaryTreeNode<string>();/找到了按前序遍历的下一个结点位置并生成结点 pointer = pointer->getRightChild(); break; cin >> c; void Expres

34、sionBinaryTree:buildBTreeByInfixE()/构造中缀表达式二叉树 clear(); root = new BinaryTreeNode<string>(); char c; cout << "请输入中缀表达式（以=结尾）：" ; cin >> c; stack<BinaryTreeNode<string> *> opd;/操作数栈 /为了方便统一管理，操作数和操作符全部定义为string类型 stack<string> opt;/操作符栈 double tempDouble

35、= 0; string tempStr;/用于输入流，将浮点数转换成字符串 string blankStr = "" while(c != '=') switch (c) case '+': case '-': case '*': case '/': while(!opt.empty() && aIsGreaterOrEqualThanB(opt.top().c_str()0,c)/如果栈顶操作符优先级高于读入操作符优先级，则表名应该先计算栈顶操作符 BinaryTreeNode

36、<string> *secondOpd = opd.top(); opd.pop(); BinaryTreeNode<string> *firstOpd = opd.top(); opd.pop();/从操作数栈取出两个操作数 opd.push(new BinaryTreeNode<string>(opt.top(),firstOpd,secondOpd);/将操作数和操作符组成一个新结点存入栈中 opt.pop(); opt.push(c + blankStr);/将读入操作符入栈 break; case '(': opt.push(c +

37、 blankStr);/遇到左括号直接入栈 break; case ')': while(!opd.empty() && opt.top().c_str()0 != '(')/为了防止冗赘括号，但未检测括号不匹配 BinaryTreeNode<string> *secondOpd = opd.top(); opd.pop(); BinaryTreeNode<string> *firstOpd = opd.top(); opd.pop();/从操作数栈取出两个操作数 opd.push(new BinaryTreeNode&l

38、t;string>(opt.top(),firstOpd,secondOpd);/将操作数和操作符组成一个新结点存入栈中 opt.pop(); opt.pop();/将左括号出栈 break; default:/如果是操作数，直接包装成结点入栈 cin.putback(c); cin >> tempDouble; stringstream sss; sss << tempDouble; sss >> tempStr; opd.push(new BinaryTreeNode<string>(tempStr); break; cin >&

39、gt; c; while(!opt.empty() && aIsGreaterOrEqualThanB(opt.top().c_str()0,c)/如果栈顶操作符优先级高于读入操作符优先级，则表名应该先计算栈顶操作符 BinaryTreeNode<string> *secondOpd = opd.top(); opd.pop(); BinaryTreeNode<string> *firstOpd = opd.top(); opd.pop();/从操作数栈取出两个操作数 opd.push(new BinaryTreeNode<string>(o

40、pt.top(),firstOpd,secondOpd);/将操作数和操作符组成一个新结点存入栈中 opt.pop(); root = opd.top();/此时操作数栈中唯一元素即为根元素 opd.pop();void ExpressionBinaryTree:buildBTreeBySuffixE() clear(); char c; cout << "请输入后缀表达式（以=结尾）" ; cin >> c; stack<BinaryTreeNode<string> *> opdStack;/抽象意义上为操作数栈，但实际为操

41、作数和操作符构成的结点栈 double tempDouble = 0; string tempStr;/用于输入流，将浮点数转换成字符串 string blankStr = "" while(c != '=') switch (c) case '+': case '-': case '*': case '/': BinaryTreeNode<string> *secondOpd = opdStack.top(); opdStack.pop(); BinaryTreeNode<s

42、tring> *firstOpd = opdStack.top(); opdStack.pop(); opdStack.push(new BinaryTreeNode<string>(c+blankStr,firstOpd,secondOpd); break; default: cin.putback(c); cin >> tempDouble; stringstream sss; sss << tempDouble; sss >> tempStr; opdStack.push(new BinaryTreeNode<string>

43、;(tempStr); break; cin >> c; root = opdStack.top();/此时操作数栈中唯一元素即为根元素 opdStack.pop();void ExpressionBinaryTree:printEBTree() int height = getHeight(root); int headIndentation;/行首缩进空格数 int InIndentation;/行中单位数据间隔空格数 queue<BinaryTreeNode<string> *> nodeQueue;/结点队列 nodeQueue.push(root)

44、;/将根结点入队列以便第一次操作 BinaryTreeNode<string> *pointer; for(int i = 1;i <= height;+i) headIndentation = (int)2*pow(2.0,double(height)-i)-2;/根据层数获得行首缩进空格数 printBlank(headIndentation); InIndentation = (int)2*pow(2.0,double(height)-i+1)-3;/根据高度和层数计算行中单位数据间隔空格数 for(int j = 0;j < pow(2.0,double(i)-

45、1)&&!nodeQueue.empty();+j)/遍历第i层结点 pointer = nodeQueue.front(); if(pointer = NULL)/如果是空，则直接输行中单位数据间隔空格数+3个空格(数据占3位，无数据则用空格补全) printBlank(InIndentation+3); nodeQueue.pop(); nodeQueue.push(NULL); nodeQueue.push(NULL);/向队列内加入两个空子树，当作占位符，以便在无结点的地方输出空格 else printInRightFormat(pointer->getValue

46、(); printBlank(InIndentation); nodeQueue.pop(); nodeQueue.push(pointer->getLeftChild();/左右子树入队列 nodeQueue.push(pointer->getRightChild(); cout << endl; void ExpressionBinaryTree:printInfixE() stack<BinaryTreeNode<string> *> nodeStack;/结点栈，遍历使用 BinaryTreeNode<string> *poi

47、nter = root; list<BinaryTreeNode<string> *> nodeList;/用于记录在哪些元素被输出之后要输出反括号 while(!nodeStack.empty() | pointer != NULL) while(pointer != NULL)/一直向左子结点走，找到左子结点时，经过的结点已全部入栈 if(shouldPrintLeftBracket(nodeStack,pointer,LEFT)/如果应该添加左括号,为左子结点的情况下 BinaryTreeNode<string> * temp = pointer-&g

48、t;getRightChild();/找到应该在输出哪个结点后输出右括号 while(temp->getRightChild() != NULL) temp = temp->getRightChild(); nodeList.push_back(temp);/将该位置放入序列中，供查询使用 cout << "(" nodeStack.push(pointer); pointer = pointer->getLeftChild(); cout << nodeStack.top()->getValue();/输出结点 list<BinaryTreeNode<s