数据结构大实验1报告---副本

目录1.摘要2.关键字3.概述3.1问题的定义3.2算法输入3.3算法输出3.4研究的目的与意义4.数据结构与算法设计4.1数据结构的逻辑结构设计4.2数据存储结构设计4.3算法的基本思想和流程图5.实验及测试5.1开始菜单5.2中缀转后缀5.3后缀计算5.4中缀计算5.5括号匹配5.6零的处理3.7其他运算符6.结论与展望7.参考文献8.附录（代码）1.摘要问题表达式求值是程序设计语言编译中的一个最基本问题。人们在书写表达式时通常采用将运算符放在两个操作数中间的“中缀”表示形式，称为中缀表达式。但是这种表达式形式对计算机处理来说是不太适合的。在计算机领域，经常将算术表达式表示成“后缀”表表达式求值是程序设计语言编译中的一个最基本问题。人们在书写表达式时通常采用将运算符放在两个操作数中间的“中缀”表示形式，称为中缀表达式。但是这种表达式形式对计算机处理来说是不太适合的。在计算机领域，经常将算术表达式表示成“后缀”表示形式，称为后缀表达式。如:中缀表达式3+2*(7-5)对应的后缀表达式为3275-*+。2.关键字栈，队列，中缀表达式，后缀表达式3．概述：3.1问题的定义：实现中缀表达式到后缀表达式的转换，并实现中缀表达式和后缀表达式的计算。3.2算法输入：一个算数表达式，由数字，运算符，括号组成，数字范围0~9的正整数，运算符包含加减乘除，开方和取余。3.3算法输出：表达式中缀到后缀的转换和最终运算的结果。3.4研究的目的与意义：加深了我对栈和队列的理解，实现的简单的运算功能。4.数据结构与算法设计4.1数据结构的逻辑结构设计：算数表达式由操作数，运算符和括号组成。我们用队列寄存表达式的操作数，用栈来寄存运算符和左括号。栈是“先进后出”的线性表，链栈存储结构是一条链表，他有一根始终指向栈顶的指针s，当s=NULL时栈就为空，当插入新节点时s就会指向新插入的节点，删除栈顶元素时，s会指向下一个节点。4.2数据存储结构设计：输入的表达式会先存储进链表中再利用函数对栈和队列进行操作。/*定义字符类型的链表*/typedefstructlnode{chardata;structlnode*next;}lnode,*linklist;/*定义字符类型的栈*/typedefstructstack{chardata;structstack*next;}stack,*linkstack;/*定义字符类型的队*/typedefstructqnode{chardata;structqnode*next;}qnode,*queueptr;typedefstruct{queueptrfront;queueptrrear;}linkqueue;4.3算法的基本思想和流程图（1）优先级判断函数：getprecedence(chare)判断运算符的优先级，返回每个运算符对应的数值。运算符之间的关系：+（加）=-（减）*（乘）=/（除）=%（取余）^（次方）=!（开方）（2）中缀转为后缀：算法基本思想：顺序扫描中缀表达式，当读到数字时，直接将其送至输出队列中；当读到运算符时，将栈中所有优先级高于或等于该运算符的运算符弹出，送至输出队列中，再将当前运算符入栈；当读入左括号时，将其入运算符栈；当读到右括号时，将栈中从栈顶到靠近栈顶的第一个左括号之间的所有运算符全部依次弹出，送至输出队列中，再删除栈中的左括号。流程图：YNYNNYYNYNYNY开始push(s,'#')while(p!=NULL)p-data是0~9的数字吗？数字入队p-data是左括号吗？p-data是右括号吗？栈顶是左括号吗？p-data是运算符吗？左括号入栈数据入栈将栈中从栈顶到靠近栈顶的第一个左括号(“伪栈底”）之间的所有运算符全部依次弹出，送至输出队列中，再删除栈中的左括号将栈中所有优先级高于或等于该运算符的运算符弹出，送至输出队列中，再将当前运算符入栈栈顶是#吗？c=pop(s);enqueue(q,c);元素出队并输出结束表格解释：中缀表达式到后缀表达式的转换过程示例转换步骤中缀表达式的读入运算符栈后缀表达式初始1+2*（3-1+2）-3##空1+2*（3-1+2）-3##122*（3-1+2）-3##+13*（3-1+2）-3##+124（3-1+2）-3##+*1253-1+2）-3##+*（126-1+2）-3##+*（12371+2）-3##+*（-1238+2）-3##+*（-123192）-3##+*（+1231-10）-3##+*（[phone]##+*1231-2+123##-1231-2+*+13##-1231-2+*+314空1231-2+*+3-（3）后缀表达式的计算：算法基本思想：利用栈（操作数和运算结果栈）计算后缀表达式。顺序扫描后缀表达式，当读到数字时，将其送至栈中；当读到运算符θ时，将栈顶字符弹出，将其转换成对应的数值并赋给变量y，再将次栈顶字符弹出，将其转换成对应的数值，并赋给变量x，之后计算xθy，将运算结果转换成对应的数字字符送入栈中。表格解释：表1-2后缀表达式计算过程示例计算步骤后缀表达式的读入运算符栈初始1231-2+*+3-空1231-2+*+3-1231-2+*+3-1231-2+*+3-1234-2+*+3-123152+*+3-1226+*+3-12227*+3-1248+3-1893-910-9311空6流程图：NYNYNY（3）中缀表达式就计算：开始while(p!=NULL)是数字吗？是空格吗？是运算符吗？将字符减去48再存入栈中执行相应的运算再将结果入栈跳过空格输出栈中元素也就是结果结束算法基本思想：将中缀表达式通过中缀到后缀的转化函数转成后缀表达式并利用后缀表达式的求值函数来计算。流程图：5．实现及测试：(1)开始菜单(2)中缀表达式转换成后缀表达式将输入的中缀表达式转换成后缀表达式开始利用后缀表达式的计算函数求值结束(3)后缀表达式的计算例子：23+4*5-(4)中缀表达式的计算例子：（2+3）*4-5(5)括号匹配检测(6)除法零的处理(7)其他运算符n次幂运算开平方运算取余运算6.结论与展望时间复杂度上中缀表达式转后缀O(n),后缀表达式计算O(n^2)，这个实验加深了我对栈和队列的理解，让我感受到了数据结构的强大作用，增加了我的学习热情。这个程序的不足之处有很多，没有实现可视化也没有实现小数之间的运算，程序的操作界面过于简陋，我已经尽力而为了，在今后的学习中我会努力学习这些知识，让自己的编程水平更上一层楼！7.参考文献:《数据结构与算法》严蔚敏著百度文库8.附录#includeiostream#includestdlib.h#includecstdlib#includemath.h#includewindows.husingnamespacestd;typedefstructstack//链栈的定义{chardata;structstack*next;}stack,*linkstack;typedefstructlnode//队的定义{chardata;structlnode*next;}lnode,*linklist;voidinitstack(linkstack&s)//初始化栈{s=NULL;}voidpush(linkstack&s,charc)//入栈{linkstackp;p=newstack;p-data=c;p-next=s;s=p;}charpop(linkstack&s)//出栈{charc;if(s==NULL){cout栈为空endl;exit(0);}linkstackp;c=s-data;p=s;s=s-next;deletep;returnc;}chargettop(linkstack&s)//取栈顶{if(s!=NULL){returns-data;}}typedefstructqnode//链队的定义{chardata;structqnode*next;}qnode,*queueptr;typedefstruct{queueptrfront;queueptrrear;}linkqueue;voidinitqueue(linkqueue&q)//初始化队{q.front=q.rear=newqnode;q.front-next=NULL;}voidenqueue(linkqueue&q,chare)//入队{queueptrp;p=newqnode;p-data=e;p-next=NULL;q.rear-next=p;q.rear=p;}voiddequeue(linkqueueq)//出队并输出出队的值{qnode*p;p=q.front-next;while(p!=NULL){coutp-data;p=p-next;}}voidcreate(linklist&l)//输入函数并建立链表{linklistp,r;l=newlnode;r=l;chara;cout请输入表达式并以#结尾endl;cina;while(a!='#'){p=newlnode;p-data=a;r-next=p;r=p;cina;}r-next=NULL;}voidjudge(linklist&l)//判断函数，判断括号的匹配{linkstacks;initstack(s);linklistp;p=l-next;charc;while(p!=NULL){if(p-data=='('){c=p-data;push(s,c);}elseif(p-data==')'&&s!=NULL){pop(s);}elseif(p-data==')'&&s==NULL){cout匹配失败,右括号多了endl;exit(0);}p=p-next;}if(s==NULL)cout括号匹配成功endl;elsecout匹配失败，左括号多了endl;}intgetprecedence(chare)//得到操作符的优先级{switch(e){case'#':return0;case'+':return1;case'-':return1;case'*':return2;case'/':return2;case'%':return2;case'^':return3;case'!':return3;}}voidinqueue(linkqueue&q)//将后缀表达式入队，用来传给计算函数{qnode*p;charx;cout请输入后缀表达式（以#结束输入）:endl;cinx;while(x!='#'){p=newqnode;p-data=x;p-next=NULL;q.rear-next=p;q.rear=p;cinx;}}linkqueuechange(linklist&l,linkstack&s,linkqueueq)//中缀表达式转换成后缀表达式{initqueue(q);initstack(s);linklistp;p=l-next;chara,b,c;push(s,'#');//先把#压入栈作为一个标志while(p!=NULL){if((p-data)='0'&&(p-data)='9')//碰到数字入队{enqueue(q,p-data);}elseif(p-data=='(')//碰到左括号入栈{push(s,p-data);}elseif(p-data==')')//碰到右括号就出栈一直到栈顶为左括号再将左括号出栈{while(gettop(s)!='('){a=pop(s);enqueue(q,a);}pop(s);//删除左括号}elseif(gettop(s)=='(')//碰到做括号入栈{push(s,p-data);}elseif(p-data=='+'||p-data=='-'||p-data=='*'||p-