树.docx
- 文档编号:10491972
- 上传时间:2023-05-26
- 格式:DOCX
- 页数:25
- 大小:48.80KB
树.docx
《树.docx》由会员分享,可在线阅读,更多相关《树.docx(25页珍藏版)》请在冰点文库上搜索。
树
《算法与数据结构》
实验报告
题目:
树和二叉树
班级:
计101组号:
姓名:
学号:
姓名:
学号:
姓名:
学号:
姓名:
学号:
华东理工大学
信息学院计算机系
2012年5月
一、需求分析
本实验分两小题,
(1)用二叉树表示代数表达式并输出代数表达式的前缀式和后缀式;
(2)求二叉树中从根结点到叶子节点的路径。
其中,第一小题要求编写一个程序,用二叉树来表示代数表达式,树的每个结点包括一个运算符,代数表达式由输入得到(其中只包含=,+,-,*,/和用一个字母表示的数且没有错误,并且按照先乘除后加减的原则),试编写程序输出表达式的前缀式和后缀式;第二小题要求对于1中的代数表达式二叉树,分别用递归和非递归的方法编写程序完成如下功能:
a.输出所有的叶子结点的数据项值;b.输出所有从叶子节点到根结点的路径。
输入及输出:
输入一个正确的算术表达式,长度不能超过100,依次输出其前缀表达式、后缀表达式,递归方法打印的表达式树叶节点,非递归方式打印的表达式树叶节点。
二、系统设计
1、数据结构定义。
程序中大量用到栈ADT。
本实验中的栈基于顺序表实现。
定义如下:
//顺序表ADT的定义
struct_table{
_DATATYPE*_table_head;
int_length;
int_max_length;
};
typedefstruct_table*MYSTABLE;
//栈ADT的定义
typedefstruct_table*MYSTACK;
其中_DATATYPE在ExpressionTree.h中定义,定义如下:
//_DATATYPE的定义
#ifndef_DATATYPE
#define_DATATYPENODE
#define_ERRORNULL
#endif
其中NODE表示二叉树的一个结点,定义如下:
//树结点的定义
struct_tree_node{
struct_tree_node*lchild;
struct_tree_node*rchild;
//data用于保存节点信息,类型为字符串
char*data;
};
typedefstruct_tree_node*BITREE;
typedefstruct_tree_node*NODE;
2、程序模块介绍。
mySequenceTable.h
mySequenceTable.cpp
用于定义和实现顺序表的功能。
myStack.h
myStack.cpp
用于定义和实现栈的功能。
ExpressionTree.h
ExpressionTree.cpp
用于定义二叉树节点数据结构以及一个初始化节点的函数。
core.h
core.cpp
用于定义和实现实验要求的功能函数。
main.cpp
程序主函数的入口。
3、功能函数
(1)MYSTABLEchar_to_infix(charex[]);
函数功能:
将输入的字符串分解为分散的树节点,并存储到一个顺序表中。
输入参数:
ex:
输入的字符串。
返回类型:
MYSTABLE。
(2)MYSTABLEinfix_to_postfix(MYSTABLEinfix);
函数功能:
将中缀表达式转换成后缀表达式。
输入参数:
infix:
存储中缀表达式的顺序表。
返回类型:
MYSTABLE。
(3)BITREEpostfix_to_binarytree(MYSTABLEpostfix)
函数功能:
将后缀表达式中离散的节点链接起来生成表达式树。
输入参数:
postfix:
存储后缀表达式的顺序表。
返回类型:
BITREE。
树的根节点。
(4)voidprint_prefix(BITREEnode)
函数功能:
打印前缀表达式。
输入参数:
node:
树的根节点。
返回类型:
无。
(5)voidprint_postfix(BITREEnode)
函数功能:
打印后缀表达式。
输入参数:
node:
树的根节点。
返回类型:
无。
(6)voidprint_path_with_recursion(BITREEtree)
函数功能:
递归打印每个叶节点以及从该叶节点到根节点的路径。
输入参数:
node:
树的根节点。
返回类型:
无。
(6)void_print_path_with_recursion(BITREEtree,NODEpath[],intdepth)
函数功能:
递归打印叶节点的递归入口。
输入参数:
tree:
树(子)节点;path:
保存路径的数组;depth:
节点深度。
返回类型:
无
(7)voidprint_path_without_recursion(BITREEtree)
函数功能:
非递归打印每个叶节点以及从该叶节点到根节点的路径。
输入参数:
node:
树的根节点。
返回类型:
无。
4、主函数流程图及函数调用关系图
三、调试分析
1、设计与实现
实现本实验要求的功能主要使用了实验一中计算表达式中转换中缀表达式到逆波兰式的算法。
在实验一基础上修改了相应的数据结构以适应本实验的要求(要求带字母的变量)。
然后将逆波兰式中的树节点链接成表达式树。
算法过程与实验一中计算逆波兰式的算法相同。
在转换表达式的过程中由于顺序表和栈中存放的都是指向结点的指针,编程实现相对较易。
另一方面,因为本实验不要求计算表达式的值且有字母变量的出现,相对于实验一中的数据结构,本实验中的树节点结构经过精简,将所有数据统一保存为字符型,因此无法区分运算符和操作数,也无法确定运算符的操作数个数,因此程序对检验错误表达式的能力降低。
生成表达式树之后,分别使用前序遍历和后序遍历打印前缀表达式和后缀表达式。
对于实验第二小题要求的打印叶结点及路径的问题,使用递归实现比较简单,使用一个数组保存相应深度的结点即可。
使用非递归实现需要额外使用是一个数组记录每个入栈结点的深度,在弹出栈元素的同时弹出该结点的深度。
2、算法分析
(1)转化为中缀顺序表:
遍历整个字符串,时间复杂度O(n)。
n为字符串长度。
(2)转化为后缀顺序表:
遍历整个中缀顺序表,每个运算符有一个入栈操作和出栈操作,因此时间复杂度仍为线性的,O(n)。
n为中缀顺序表元素数量。
(3)转化为表达式树:
遍历整个后缀顺序表,每个操作数有一个入栈操作和出栈操作,每个运算符有一个入栈和出栈操作,时间复杂度为O(n)。
n为后缀顺序表元素数量。
(4)打印前缀表达式:
每个节点访问一次,时间复杂度O(n)。
n为节点数。
(5)打印后缀表达式:
每个节点访问一次,时间复杂度O(n)。
n为节点数。
(6)递归打印叶节点:
每个节点访问一次,时间复杂度O(n)。
n为节点数。
(7)非递归打印叶节点:
每个节点访问一次,时间复杂度O(n)。
n为节点数。
目前没有改进设想。
3、已知Bug
由于因此无法区分运算符和操作数,也无法确定运算符的操作数个数,因此有时用户输入的表达式即使有错,依旧会打印出信息。
例如输入b*(a+*c),依旧会有输出。
解决方法是在叶节点中加入更多数据信息,详细方法参考实验一中表达式求值的数据结构。
4、经验与体会
由于树的递归定义,在关于二叉树的算法设计中,递归算法确实比非递归算法容易得多,思想也更加顺畅。
非递归算法使用一个栈或队列保存二叉树的另一个结点的算法是图论算法中BFS的基础。
四、测试结果
1、实验报告给出的数据
输入:
(-b+(b^2-4*a*c)^0.5)/(2*a)
输出:
/+-b^-^b2**4ac0.5*2a
b-b2^4a*c*-0.5^+2a*/
b:
b-+/
b:
b^-^+/
2:
2^-^+/
4:
4**-^+/
a:
a**-^+/
c:
c*-^+/
0.5:
0.5^+/
2:
2*/
a:
a*/
b:
b-+/
b:
b^-^+/
2:
2^-^+/
4:
4**-^+/
a:
a**-^+/
c:
c*-^+/
0.5:
0.5^+/
2:
2*/
a:
a*/
2、错误的表达式
输入:
(4+2)8
输出:
输入有误!
3、错误但无法发现的表达式(Bug)
输入:
(5+3)++
输出:
+++53
53+++
5:
5+++
3:
3+++
5:
5+++
3:
3+++
五、用户手册
用户只需输入表达式即可得到结果。
六、附录
程序源代码及所使用的ADT源代码。
/*表ADT*/
mySequenceTable.cpp
#include"mySequenceTable.h"
//为顺序表分配空间,将所有数据初始化为init
MYSTABLEassign(constintmaxlen,_DATATYPEinit){
MYSTABLEtemp;
if((temp=(MYSTABLE)malloc(sizeof(struct_table)))!
=NULL){
temp->_max_length=maxlen;
temp->_length=0;
if((temp->_table_head=(_DATATYPE*)malloc(sizeof(_DATATYPE)*maxlen))!
=NULL)
for(inti=0;i *(temp->_table_head+i)=init; else returnNULL; returntemp; } returnNULL; } //在表的最后插入一个数据 intadd(constMYSTABLEtable,_DATATYPEx){ returninsert(table,table->_length,x); } //判断表是否为空 intisEmpty(constMYSTABLEtable){ if(table==NULL) return-1; if(table->_length==0) return1; return0; } //判断表是否为满 intisFull(constMYSTABLEtable){ if(table==NULL) return-1; if(table->_length==table->_max_length) return1; return0; } //获取position位置的数据 _DATATYPEget(constMYSTABLEtable,intposition){ if(position>table->_length-1||position<0) return_ERROR; return*(table->_table_head+position); } //获取表长 intgetLength(constMYSTABLEtable){ if(table==NULL) return-1; returntable->_length; } //从表中删除一个数据 intremove(constMYSTABLEtable,intposition){ inti=0; if(table==NULL) return-1; if(position>table->_length-1||position<0) return0; for(i=position;i *(table->_table_head+i)=*(table->_table_head+(i+1)); table->_length--; return1; } //插入一个数据到position位置 intinsert(MYSTABLEtable,intposition,_DATATYPEdata){ inti=0; if(table==NULL) return-1; if(position>table->_length||position<0) return0; if(isFull(table)==0){ for(i=table->_length;i>position;i--) *(table->_table_head+i)=*(table->_table_head+(i-1)); *(table->_table_head+i)=data; table->_length++; }else{ MYSTABLEtemp; if((temp=(MYSTABLE)malloc(sizeof(struct_table)))==NULL) return-1; if((temp->_table_head=(_DATATYPE*)malloc(sizeof(_DATATYPE)*(table->_max_length+1)))==NULL) return-1; temp->_length=table->_max_length+1; temp->_max_length=table->_max_length+1; for(i=0;i *(temp->_table_head+i)=*(table->_table_head+i); *(temp->_table_head+i)=data; for(i++;i *(temp->_table_head+i)=*(table->_table_head+(i-1)); free(table->_table_head); free(table); table=temp; } return1; } //释放表占用的空间 intdel(constMYSTABLEtable){ free(table->_table_head); free(table); return1; } /*栈ADT*/ myStack.cpp #include"myStack.h" //初始化栈,分配空间 MYSTACKinitial(){ returnassign(100,0); } //从栈中弹出一个数据 _DATATYPEpop(MYSTACKstack){ if(stack==NULL) return_ERROR; if(isEmpty(stack)) return_ERROR; _DATATYPEdata; data=get(stack,stack->_length-1); remove(stack,stack->_length-1); returndata; } //返回栈顶的数据但不弹出 _DATATYPEpeek(MYSTACKstack){ if(stack==NULL) return_ERROR; if(isEmpty(stack)) return_ERROR; _DATATYPEdata; data=get(stack,stack->_length-1); returndata; } //向栈中压入数据 intpush(MYSTACKstack,_DATATYPEx){ returninsert(stack,stack->_length,x); } /*定义树节点*/ ExpressionTree.cpp #include"ExpressionTree.h" //分配一个新的树节点 NODEnewNode(char*data){ NODEtemp=(NODE)malloc(sizeof(struct_tree_node)); if(temp==NULL) returnNULL; temp->lchild=NULL; temp->rchild=NULL; temp->data=data; returntemp; } /*实验核心函数*/ core.cpp #include"core.h" //字符串转化为中缀顺序表 MYSTABLEchar_to_infix(charex[]){ intlength=strlen(ex); MYSTABLEinfix=assign(length,NULL); char*temp; for(inti=0;i if((ex[i]>='0'&&ex[i]<='9')||ex[i]=='.'){ //若是数字字符则查询直到遇到一个不是数字的字符 intcount=0; for(intj=i;(ex[j]>='0'&&ex[j]<='9')||ex[j]=='.';j++,count++); temp=(char*)malloc(sizeof(char)*(count+1)); for(intj=0;j temp[j]=ex[i+j]; temp[count]='\0'; add(infix,newNode(temp)); i=i+count-1; }else{ temp=(char*)malloc(sizeof(char)*2); temp[0]=ex[i];temp[1]='\0'; add(infix,newNode(temp)); } } returninfix; } //中缀表达式转化为后缀表达式 MYSTABLEinfix_to_postfix(MYSTABLEinfix){ MYSTACKstack=initial(); MYSTABLEpostfix=assign(getLength(infix),NULL); for(inti=0;i charopF,opS; opF=get(infix,i)->data[0]; if((opF>='0'&&opF<='9')||opF=='.'||(opF>='a'&&opF<='z')) //数字则直接压入后缀表达式 add(postfix,get(infix,i)); else{ if(getLength(stack)==0){ push(stack,get(infix,i)); }elseif(opF=='('){ push(stack,get(infix,i)); }elseif(opF==')'){ //遇到右括号,将栈中的数据依次弹出,直到遇到左括号 do{ opS=peek(stack)->data[0]; if(opS! ='(') add(postfix,pop(stack)); else pop(stack); }while(opS! ='('); }else{ //比较优先级,若优先级高于栈顶元素则压入栈,否则弹出 do{ opS=peek(stack)->data[0]; intspriority,fpriority; switch(opS){ //设置优先级 case'+': spriority=4;break; case'-': spriority=4;break; case'*': spriority=3;break; case'/': spriority=3;break; case'^': spriority=2;break; case'(': spriority=7;break; } switch(opF){ case'+': fpriority=4;break; case'-': fpriority=4;break; case'*': fpriority=3;break; case'/': fpriority=3;break; case'^': fpriority=2;break; case'(': spriority=7;break; } if(fpriority>=spriority) add(postfix,pop(stack)); else break; }while(getLength(stack)! =0); push(stack,get(infix,i)); } } } while(getLength(stack)! =0) add(postfix,pop(stack)); //释放括号占用的内存 for(inti=0;i NODEtemp=get(infix,i); if(temp->data[0]=='('||temp->data[0]==')'){ free(temp->data); free(temp); } } //释放栈占用的内存 del(stack); //释放掉前缀表达式占用的内存 del(infix); returnpostfix; } //生成表达式树 BITREEpostfix_to_binarytree(MYSTABLEpostfix){ MYSTACKstack=initial(); for(inti=0;i charname; name=get(postfix,i)->data[0]; if((name>='0'&&name<='9')||name=='.'||(name>='a'&&name<='z')){ push(stack,get(postfix,i)); }else{ NODEparent=get(postfix,i); NODElchild,rchild; //从栈中弹出操作数,将运算符节点的两个儿子指针指向操作数结点 if(getLength(stack)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- docx