数据结构实验参考格式

1、数据结构实验设计报告题目名称： 设计环境： 指导教师： 专业班级： 姓 名： 学 号： 联系电话： 电子邮件： 设计日期： 设计报告日期:指导教师评语：工程训练实习总结报告每次上课，我都会提前几分到训练基地，但我发现，老师总在我之前，并且已经画好图、检验好机床设施等待同学们的到设计成绩： 指导教师签名：算术表达式求值演示1.题目简介2需求分析2.1输入形式和输入值的范围2.2输出的形式2.3程序所能达到的功能2.4测试数据3. 设计思路及具体实现4. 调试分析5. 测试结果和分析5.1输入中缀表达式信息5.2中缀变为后缀表达式5.3后缀表达式计算过程6. 实验总结1题目算术表达式求值演示表达式

2、计算是实现程序设计语言的基本问题之一，也是栈的应 用的一个典型例子，设计一个程序，实现利用算符优先算法计算算 术表达式求值。2需求分析本演示程序用C+编写，实现利用算符优先算法计算算术表达 式求值：（1）通过键盘输入表达式字符序列，并转换为整数表达式。（2）进行输入合法性验证（3）对算术运算表达式求值（4）运算符包括乘方，开方，单目减等运算符2.1输入的形式和输入值的范围:将需要计算的中缀表达式通过键盘输入，输入形式是字符型；2.2输出的形式输入操作结束后，如同输入的表达式非法，则会显示“您输入 的表达式错误！ ”字样，如果输入是正确的，则直接进入计算过程， 首先是把中缀表达式变换为后缀表达式

3、输出，然后再显示每一步后 缀表达式运算过程，最终输出表达式计算过程。2.3程序所能达到的功能：将中缀表达式转换为后缀表达式，后缀表达式计算出最终结果， 自动退出系统服务。2.4测试数据：A .测试输入中缀表达式。在主函数中输入提示输入语句结束后， 开始输入表达式，系统自动检验输入是否正确。B. 测试中缀变后缀表达式函数In fix(Middle,Middle.le ngth (),Beh ind)，在函数中添加语句，显示“转换的后缀表达式如下：”字 样，然后循环输出数组array保存后缀表达式的字符。C. 测试后缀表达式计算函数 Suffixal(Behind,length)，添加语句实 现循

4、环输出后缀表达式计算的每一步，直到计算出最终结果。D .测试退出系统功能。输入任意键退出系统。3.设计思路及具体实现实现概要设计中定义的所有的数据类型，对每个操作给出伪码 算法。对主程序和其他模块写出伪码算法。3.1数据类型用类SeqStack来存储中缀表达式字符class SeqStackprivate:char dataMaxStackSize;/存放数据元素的数组5int top;/栈顶位置指示器public:SeqStack(void)/构造函数top=0;SeqStack(void) 析构函数void Push(c onst char& item);/入栈char Pop(v

5、oid);/出 栈char Peek(void)co nst;/读栈顶元素bool StackEmpty(void)co nst/判断堆栈是否为空retur n (top=0);int GetSize(void)co nst/读栈顶元素个数retur n top;void ClearStack(void)/清空栈top=0;3.2基本操作运算符优先级比较char Proceed(char a,char b)/ 运算符优先级比较char Result;char MidStr in g2;6Result二'v：MidStri ngO=b;MidStri ng1=0;if(a='+&

6、#39;|a='-')&&strstr("+-)#",MidStri ng)!二NULL)|(a='*'| a='/' )&&strstr("+-*/)#",MidStri ng)!=NULL)|(a='A')&&strstr("+-*/A)# ”,MidString)!=NULL)k 表开方Result二'>'else if(a='('&&b=')')|(a=&#

7、39;#'&&b=#)Result二'二：else if(a='('&&b='#')|(a=')'&&b='(')|(a=#&&b=')')Result二''retur n Result;中缀变后缀表达式函数：int In fix(stri ng& middlent n,i nt array)/ 中缀变后缀SeqStack s;char x1,x2;int j=0,z,co un t=0;s.Push('

8、#');7x1=s.Peek();while。<n)x2=middlej;if(x2>='0'&&x2<=9)z=x2-'O：j+；while (j<n&&middlej>=48&&middlejv=57)z=z*10+middlej+-'0'arrayco un t+=z;else if (x2='$')/$ 表示开方符if (j=( n-1)|middlej+1>57&&middlej+1<48)coutvv"您

9、输入的表达式错误！"<<e ndl;exit(0);8j + + ；z=middlej+-'O'while (j<n&&middlej>=48&&middlejv=57)z=z*10+middlej+-'0'arrayco un t+二sqrt(z);elseif(x2!='+'&& x2!='-'&&x2!='*'&&x2!='/'&&x2!='A'&a

10、mp;&x2!='('&&x2!=')')cout«"您输入的表达式错误！"<<e ndl;exit(0);elseif(Proceed(x1,x2)='v')s.Push(x2);x1=x2;9else if(Proceed(x1,x2)='>')if (x1!='+'&& x1!='-'&&x1!='*'&&x1!='/'&&x1

11、!='A')coutvv"您输入的表达式错误！"<<e ndl;exit(0);arrayco un t=in t(x1);flagco un t+二true;s.Pop();x1=s.Peek();while(Proceed(x1,x2)='>')if (x2!='+'&&x2!='-'&&x2!='*'&&x2!='/'&& x2!='A') coutvv"您输入的表达

12、式错误！"<<e ndl;exit(0);arrayco un t=in t(x1);10flagco un t+二true;s.Pop();x1=s.Peek();if (Proceed(x1,x2)='')"<<e ndl;coutvv"您输入的表达式错误!exit(0);else if (Proceed(x1,x2)='=')s.Pop();x1=s.Peek();elses.Push(x2);x1=x2;11else if(Proceed(x1,x2)='=')s.Pop();x1=s

13、.Peek();elsecoutvv"您输入的表达式错误!exit(0);j+；x2=#;while (1)if (Proceed(x1,x2)='=')"<<e ndl;/清空栈break;if (Proceed(x1,x2)='>')12if (x1!='+')&&(x1!='-')&&(x1!='*')&&(x1!='/')&&(x1!='“)coutvv"您输入的表达式错误

14、！"<<e ndl;exit(O);arrayco un t二in t(x1);flagco un t+二true;s.Pop();if (s.StackEmpty()coutvv"您输入的表达式错误！"<<e ndl;exit(0);x1=s.Peek();elsecoutvv"您输入的表达式错误！"<<e ndl;exit(0);int i,k=0;k表示操作符的个数for (i=0;i<co un t;i+)k+;if(k*2+1)!=cou nt)/运算符不比运算数少1,则非法coutvv&qu

15、ot;您输入的表达式错误!"<<e ndl;exit(O);if (co un t>=0)coutvv"转换的后缀表达式如下:I!<<e ndl;for (i=0;i<co un t;i+)cout<<char(arrayi)vv""elsecout<<arrayi<<" ”；cout«e ndl;retur n count;后缀表达式的运算后缀表达式的void Suffixal(int s,int t)运算while (t>1)int j=0;while

16、(j+2<t&&! flagj+2)j+;if (j+2>=t)break;switch (char(sj+2)case '+':sj=sj+sj+1;break;case '-':sj=sj-sj+1;break;case '*':sj=sj*sj+1;break;case '/':sj=sj/sj+1;break;case 'A':sj=pow(sj,sj+1);break;for (i nt i=j+1;i<t-2;i+)si=si+2;flagi=flagi+2;t=t-2

17、;for (i=0;i<t;i+)if (flagi)cout<<char(si)<<""elsecout<<sivv" ”；cout«e ndl;3.3主函数功能伪代码：int mai n()stri ng Middle;接收中缀表达试int Behi nd1000; /此数组用来接收中缀所变得整形后缀表达式 coutvv"请输入需要计算的中缀表达式(加、减、乘、除、乘方、开方分别用+、-、*、/、八、$表示)"<<endl;ci n>> Middle;int len

18、 gth=I nfix(Middle,Middle.le ngth (),Behi nd);if(le ngth>1)Suffixal(Behi nd,le ngth);/ 后缀运算return 0;4. 调试分析开始设计时，使用数组存储中缀表达式，其中有一些麻烦，后17来发现用顺序堆栈存储会更显得方便，所以改用顺序堆栈。在存储 中缀表达式过程中，需要先把字符数字改为数学数字。其中，还有 要把运算符号改为数字形式，最终有其还原。5. 测试结果和分析5.1输入中缀表达式信息直接输入需要转换和计算的中缀表达式，接着系统自动对算术 表达式进行合法性验证。如果错误，就显示出错语句提示，并退出 程序。5.2中缀变为后缀表达式如果上一步验证算术表达式合法，就进入中缀转换为后缀函数，并输出转换后的后缀表达式。5.3后缀表达式计算过程输出玩后缀表达式后，紧接着进入