《数据结构与算法》实验报告 |
您所在的位置：网站首页 › 数据结构与算法实验项目报告 › 《数据结构与算法》实验报告 |
《数据结构与算法》实验报告
|
《数据结构》实验报告
学号： 2018329621200 机房号 10-414 姓名： 申屠志刚 日期： 2019/11/4 程序名： main.cpp 实验内容： 二叉树的遍历 一、目的和要求（需求分析）： 1、掌握二叉树的存储结构以及二叉树的建立和操作。 2、输入一串表达式后，建立二叉树，并对其进行先序、中序和后序的遍历。 （输入表达式如此形式：a+b*c-d-e/f….；以#号结束。） 3、递归实现表达式运算。
二、程序设计的基本思想，原理和算法描述： 1、输入中缀表达式； 2、中缀表达式转化后缀表达式； 3、后缀表达式转化后缀表达式树； 4、递归实现表达式运算。 三、调试和运行程序过程中产生的问题及采取的措施： 1、中缀表达式建立表达式树比较繁琐； 措施：中缀表达式先转化后缀表达式； 2、判断存在括号的情况； 措施：利用栈； 3、多位数字的情况； 措施：atof函数。 四、源程序及注释： Main.cpp /* *@Author: STZG *@Language: C++ */ #include #include #include #include #include #include using namespace std; #define MAX 100 //树结点的设计 typedef struct node { //数字和运算符 union{ char op; int data; }; struct node *lchild; struct node *rchild; }TreeNode; //树栈的设计 typedef struct { TreeNode *buf[MAX]; int n; }TreeStack; //创建空栈 TreeStack *create_empty_stack() { TreeStack *pstack; pstack = (TreeStack *)malloc(sizeof(TreeStack)); pstack->n = -1; return pstack; } //入栈 int push_stack(TreeStack *p,TreeNode *data) { p->n ++; p->buf[p->n] = data; return 0; } //出栈 TreeNode *pop_stack(TreeStack *p) { TreeNode *data; data = p->buf[p->n]; p->n --; return data; } //判断空栈 int is_empty_stack(TreeStack *p) { if(p->n == -1) { return 1; }else{ return 0; } } //后缀表达式树的创建 TreeNode *create_express_tree(char *str,TreeStack *p) { int i = 0; char dst[100]; TreeNode *current; TreeNode *left,*right; int len=strlen(str); while(str[i]) { if(str[i] == ' ') { i ++; continue; } if(isdigit(str[i])) { sscanf(str+i,"%s",dst); current = (TreeNode *)malloc(sizeof(TreeNode)); current->data = atof(dst); current->lchild = current->rchild = NULL; push_stack(p,current); while (i+1 < len && isdigit(str[i+1])){++i;} }else{ current = (TreeNode *)malloc(sizeof(TreeNode)); current->op = str[i]; right = pop_stack(p); left = pop_stack(p); current->lchild = left; current->rchild = right; push_stack(p,current); } /* printf("%s\n",str); if(current!=NULL) printf("%d or %c\n",current->data,current->data); */ i ++; } return p->buf[p->n]; } //打印结点 void print_node(TreeNode *p) { if(p->lchild == NULL && p->rchild == NULL) { printf("%d ",p->data); }else{ printf("%c ",p->op); } return; } //访问结点 int vist_node(TreeNode *p) { print_node(p); return 0; } //树的后序遍历 int PostOrder(TreeNode *p) { if(p != NULL) { PostOrder(p->lchild);//左 PostOrder(p->rchild);//右 vist_node(p);//根 } return 0; } //树的中序遍历 int InOrder(TreeNode *p) { if(p != NULL) { InOrder(p->lchild);//左 vist_node(p);//根 InOrder(p->rchild);//右 } return 0; } //树的前序遍历 int PreOrder(TreeNode *p) { if(p != NULL) { vist_node(p);//根 PreOrder(p->lchild);//左 PreOrder(p->rchild);//右 } return 0; } char stack[500]; //定义顺序栈，其中top==0表示栈为空； int top; //栈顶指针，为0表示栈为空； char output[500], input[500]; //波兰式 int outLen; int priority(char op) //判断运算符级别函数；其中* /的级别为2，+ -的级别为1； { if (op=='+' || op=='-') return 1; if (op=='*' || op=='/') return 2; else return 0; } bool isOperator(char op) //判断输入串中的字符是不是操作符，如果是返回true { return (op=='+' || op=='-' || op=='*' || op=='/'); } void rePolish(char *s,int len) //将一个中缀串转换为后缀串， { memset(output,'\0',sizeof output); //输出串 outLen = 0; for (int i=0; i < len; ++i) //1）求输入串的逆序。 { if (isdigit(s[i])) //经验见:http://blog.csdn.net/linraise/article/details/18566319#comments { output[outLen++] = s[i]; //3）假如是操作数，把它添加到输出串中。 while (i+1 < len && isdigit(s[i+1])) { output[outLen++] = s[i+1]; ++i; } output[outLen++] = ' '; //空格隔开 } if (s[i]=='(') //4）假如是闭括号，将它压栈。 { ++top; stack[top] = s[i]; } while (isOperator(s[i])) //5)如果是运算符，执行算法对应操作； { if (top==0 || stack[top]=='(' || priority(s[i]) > priority(stack[top])) //空栈||或者栈顶为)||新来的元素优先级更高 { ++top; stack[top] = s[i]; break; } else { output[outLen++] = stack[top]; output[outLen++] = ' '; --top; } } if (s[i]==')') //6）假如是开括号，栈中运算符逐个出栈并输出，直到遇到闭括号。闭括号出栈并丢弃。 { while (stack[top]!='(') { output[outLen++] = stack[top]; output[outLen++] = ' '; --top; } --top; // 此时stack[top]==')',跳过) } //7）假如输入还未完毕，跳转到步骤2。 } while (top!=0) //8）假如输入完毕，栈中剩余的所有操作符出栈并加到输出串中。 { output[outLen++] = stack[top]; output[outLen++] = ' '; --top; } } double OP(double op1,double op2,char op) { double res = 0; if (op=='+') res = op1 + op2; else if (op=='-') res = op1 - op2; else if (op=='*') res = op1 * op2; else if (op=='/') res = op1 / op2; return res; } double cSt1[200]; //波兰式的计算 double CalOrder(char *s) //波兰式需要用两个栈，逆波兰式只需要一个栈 { char dst[80]; int top1=0, i; for (i=0; s[i]; ++i) { if (s[i] && s[i] != ' ') { sscanf(s+i,"%s",dst); if (isdigit(dst[0])) { ++top1; cSt1[top1] = atof(dst); //进栈 } else { cSt1[top1-1] = OP(cSt1[top1-1], cSt1[top1], dst[0]); // memcpy(cSt1[top1-1],DstBuf,sizeof DstBuf); --top1; //操作数栈：出栈俩，进栈一 } while (s[i] && s[i] != ' ') ++i; } } return cSt1[1]; } //树的计算 double CalOrder(TreeNode *p) { if(p->lchild != NULL&&p->rchild != NULL) { return OP(CalOrder(p->lchild) ,CalOrder(p->rchild), p->op); } return p->data; } int main() { TreeNode *thead; TreeStack *pstack; int i = 0; while((input[i++] = getchar()) != '\n' && i < 100); input[i-1] = 0; printf("%s\n",input); rePolish(input, strlen(input)); output[outLen-1] = '\0'; pstack = create_empty_stack(); thead = create_express_tree(output,pstack); printf("PostOrder:: "); PostOrder(thead); printf("\n"); printf("InOrder:: "); InOrder(thead); printf("\n"); printf("PreOrder:: "); PreOrder(thead); printf("\n"); printf("CalOrder::"); printf("%f",CalOrder(output)); printf("\n"); printf("CalOrder::"); printf("%f",CalOrder(thead)); printf("\n"); return 0; }五、运行输出结果：
六、心得与体会： 1、掌握二叉树的存储结构以及二叉树的建立和操作。 2、输入一串表达式后，建立二叉树，并对其进行先序、中序和后序的遍历。 3、递归实现表达式运算。 4、理论上来讲, 一个中缀表达式是不能够转换出一个唯一的二叉树的,但是中缀算术表达式因为有运算符的优先级关系, 建立二叉树时, 需要所有的操作数都在叶子节点上, 所有的操作符都在父(根)节点上, 这个特征可以生成一个唯一的二叉树。 5、atof函数的运用。
|
【本文地址】