算法与数据结构设计

《算法与数据结构设计》由会员分享，可在线阅读，更多相关《算法与数据结构设计（24页珍藏版）》请在装配图网上搜索。

1、算法与数据构造设计报告（ / 年 第 二 学期）题 目： 算术体现式的求解 专 业 学 生 姓 名 班 级 学 号 指 导 教 师 指 导 单 位 日 期 年 月 日 评 分 细 则评分项优秀良好中档差遵守机房规章制度上机时的体现学习态度程序准备状况程序设计能力团队合伙精神课题功能实现状况算法设计合理性顾客界面设计报告书写认真限度内容详实限度文字体现纯熟限度回答问题精确度简 短 评 语教师签名： 年 月 日评分级别备注评分级别有五种：优秀、良好、中档、及格、不及格一、课题名称算术体现式的求解二、课题内容和规定设计规定：给定一种算术体现式，通过程序求出最后的成果。（1）从键盘输入规定解的算术体现

2、式；（2）采用栈构造进行算术体现式的求解过程；（3）可以判断算术体现式对的与否；（4）对于错误体现式给出提示；（5）对于对的的体现式给出最后的成果。三、需求分析一方面通过键盘输入体现式并将字符串入栈,然后按从左到右的循环判断体现式的格式对的与否，当体现式的+，-，/,，( )等运算符号间有两个小数点时，体现式为错误，给出错误提示并转到起始环节，然后根据给定运算顺序来做运算，有括号要先算括号里面的，计算的成果赋值到浮点型数据并输出成果。四、概要设计在此阐明每个部分的算法设计阐明（可以是描述算法的流程图），每个程序中使用的存储构造设计阐明（如果指定存储构造请写出该存储构造的定义，如果用面向对象的措

3、施，应当给出类中成员变量和成员函数原型声明）。 1.栈的建立 先建立两个不同的栈分别寄存运算符号和数字，然后初始化栈。当从键盘输入符号时，一方面判断输入的与否是括号，若是，则在括号标志位置1，再判断与否是负号，若为负，则再输入一位，并将负号标志位置1；输入字符不满足规定期，提示错误，重新输入；（1）、定义栈的抽象数据类型定义：ADT Stack数据对象： D=ai| aiDateType,i=1,2,，n，n=0数据关系： R1=| ai-1,aiD,i=2,n基本操作：InitStack(& S)（2）、栈类型 思想： 本程序中栈采用的链式存储构造，由于寄存操作符和操作数的结点类型不同样，因

4、此设计了两个结点。栈的基本操作采用了重载的措施，使两种结点类型都能使用。 （1）、寄存操作符的结点： struct node2 char data2; /寄存操作符 node2 *next2; （2）、寄存操作数的结点：struct node double data; /寄存操作数 node *next;2.数字输入当字符是数字时，若紧接该字符之后的仍然是数字，则阐明输入的为多位数，按十进制算法*10相加得到实数a入栈。3.符号输入输入符号时，根据不同的标志位，有不同的解决措施：若两运算符相连，提示错误，重新输入；当有左括号时，根据标志位判断，若未找到右括号，则提示输入错误，重新输入。4.运算

5、符号栈中运算符号op出栈，数字栈中的数字出栈并赋值给a，b，根据给定的运算优先级（括号，*，/,+，-，），在除数b不为0的条件下，调用Execute(float a,char op,float b)函数，得出成果v，压入栈中，若之前有负号（负号标志位位为1），则求其相反数v=-v，并将成果压入数字栈中，然后不断循环，直到遇到“=”停止，然后从数字栈输出成果。5、本程序涉及的三个模块（1）、主程序模块； (2)、栈模块实现栈抽象数据类型；（3）、体现式求解模块求解体现式值的抽象数据类型； 主程序模块 体现式求解模块 栈模块 三个模块之间的调用关系如上图所示。6、函数的调用关系图： 主程序s.O

6、utput() s.Put() s.Help() 退出程序五、具体设计各个算法实现的源程序（可以是一组源程序，每个功能模块采用不同的函数实现），源程序要按照写程序的规则来编写。要构造清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。源程序代码：#includeusing namespace std;#define Stack_Size 1000#define Stack_Float 1000#define TRUE 1#define FALSE 0typedef struct /建立数字栈 float elemStack_Float; int top;Stack_float;void

7、 InitStack(Stack_float*S)/初始化栈 S-top=-1;int Push(Stack_float*S,float e) /进栈 if(S-top=Stack_Float-1) return(FALSE); else S-top+; S-elemS-top=e; return(TRUE); int Pop(Stack_float*S,float*x)/出栈 if(S-top=-1) return(FALSE); else *x=S-elemS-top; S-top-; return(TRUE); int GetTop(Stack_float*S,float*x)/ 取栈顶

8、 if(S-top=-1) return(FALSE); else *x=S-elemS-top; return(TRUE); float GetTop(Stack_float S) float x; GetTop(&S,&x); return x;void ClearStack(Stack_float*S)/清空栈 if(S-top!=-1) S-top=-1;typedef struct /建立字符栈 char elemStack_Size;/存储定义 int top;Stack_char; void InitStack(Stack_char*S) S-top=-1; int Push(S

9、tack_char *S,char x) if(S-top=Stack_Size-1) return (FALSE); S-top+; S-elemS-top=x; return (TRUE);int Pop(Stack_char*S,char*x) if(S-top=-1) return(FALSE); else *x=S-elemS-top; S-top-; return(TRUE); int GetTop(Stack_char*S,char*x) if(S-top=-1) return(FALSE); else *x=S-elemS-top; return(TRUE); char Get

10、Top(Stack_char S) char x; GetTop(&S,&x); return x;void ClearStack(Stack_char*S) if(S-top!=-1) S-top=-1; char a8= +,-,*,/,(,), =,; /输入的七种字符 char p88= , ,=, , , , ,=,; /运算符之间优先权的比较 bool Ins(char ch)/判断输入的数字字符 if(ch=48&ch=57) return(TRUE); else return(FALSE); bool Inc(char ch)/判断输入的运算符 if(ch=+|ch=-|ch=

11、*|ch=/|ch=|ch=(|ch=)|ch=) return (TRUE); else return(FALSE); float GetNumber(char*ch) /数码转换 return (*ch-48);double power(double a,double b)double s=1.0;for(int i=0;ib;i+)s=s*a;return s;float Execute(float a,char op,float b) /运算关系的实行 switch(op) case+:return(a+b);break; case-:return(a-b);break; case*:

12、return(a*b);break; case/:return(a/b);break; case:return power(a,b);break; default:cout不能运算;break; return 0;char Compare(char x,char ch) /字符之间优先权比较 int i,j,k; for(i=0;i8;i+) if(x=ai) j=i; if(ch=ai) k=i; return pjk;Stack_char TA; /定义字符对象Stack_float TB; /定义数字对象float Caculator() int c; InitStack(&TA); I

13、nitStack(&TB); Push(&TA,=); coutendl; cout请输入一种体现式串（以=结束）endl; cout-endl; char ch; int w=0,q=0,y=0,z=0,m=0; /w=0表达无负号输入，q=0表达无数字输入，y=0表达有字符输入，z=0表达无括号输入，m=0表达无负括号标记 float n=0,v,a,b; char op; ch=getchar(); if(!Ins(ch) if(ch=() z=1; else if(ch=-) w=1;ch=getchar();/记录输入负号 else coutendl; cout您输入的体现式有误【(

14、1)体现式不能以运算符（除取反外）开头】，请重新输入!endl; cout-endl; fflush(stdin); /清理缓存 ClearStack(&TA); Caculator(); exit(1); while(ch!=|GetTop(TA)!=) if(Ins(ch) n=n*10+GetNumber(&ch); q=1;/记录输入数字 y=0;/记录输入字符 ch=getchar(); if(Inc(ch) if(ch=() z=1; if(w=1) if(q=0) if(z=1) Push(&TA,ch); z=0; m=2;/记录负的左括号 ch=getchar(); cont

15、inue; else if(ch=-) w=0;ch=getchar(); /* else coutendl; cout您输入的体现式有误【(2)体现式中有不符合规定的运算】，请重新输入!endl; cout-endl; fflush(stdin); ClearStack(&TA); Caculator(); exit(1); */ else coutwwendl;n=-n;w=0; if(m=2)n=-n;m-;coutmmendl; /体现式中有负号和括号时的运算 if(q=1) Push(&TB,n); n=0; q=0; if(y=1) if(GetTop(TA)=(&ch=-) w=

16、1;ch=getchar(); else if(ch=() z=1; else coutendl; cout您输入的体现式有误【(2)体现式中有运算符位置错误】，请重新输入!endl; cout-endl; fflush(stdin); ClearStack(&TA); ClearStack(&TB); Caculator(); exit(1); if(y=0|z=1) switch(Compare(GetTop(TA),ch) case: Pop(&TA,&op); /目前输入运算符的优先级不不小于字符栈顶运算符/优先级，将栈顶运算符出栈 Pop(&TB,&b); /并且将数字栈的a,b出栈

17、进行运算 Pop(&TB,&a); if(op=/&b=0) coutendl; cout您输入的体现式有误（分子不能为0），请重新输入!endl; cout-endl; fflush(stdin); ClearStack(&TA); ClearStack(&TB); Caculator(); exit(1); v=Execute(a,op,b); if(m=1)v=-v;m=0; Push(&TB,v); /将运算成果压进数字栈 break; case=: Pop(&TA,&op); ch=getchar(); break; case$: coutendl; cout括号不匹配，请重新输入!

18、endl; cout-endl; fflush(stdin); ClearStack(&TA); ClearStack(&TB); Caculator(); exit(1); if(!Inc(ch)&!Ins(ch) coutendl; cout您输入的体现式有误（不能浮现非法字符），请重新输入!endl; cout-endl; fflush(stdin); ClearStack(&TA); ClearStack(&TB); Caculator(); exit(1); v=GetTop(TB); cout-endl; cout计算成果为：endl; coutvendl; cout-endl;

19、system(pause); cout-endl; cout请选择:endl;cout1.进入系统endl;cout2.退出系统endl;cout-c;switch(c)case 1: fflush(stdin); ClearStack(&TA); ClearStack(&TB); Caculator(); break;case 2: return 0;default: couterrorendl;break;return 0;int main()int c;cout-endl;coutendl;cout-欢迎使用算术体现式求解系统!-endl;coutendl;cout-endl;cout1

20、.进入系统endl;cout2.退出系统endl;cout-c;switch(c)case 1: fflush(stdin); ClearStack(&TA); ClearStack(&TB); Caculator(); break;case 2: return 0;default: couterrorendl;break; return 0; 六、测试数据及其成果分析测试数据，应准备多组测试数据，对测试输出的成果进行分析。测试1测试2测试3测试4测试5测试6测试7七、调试过程中的问题每个模块设计和调试时存在问题的思考（问题有哪些？如何解决问题？），以及算法的改善设想。本次设计的程序运用了两个

21、栈，占用的内存比一种栈的要大，因此此程序可以改用一种栈的设计思想，将中缀体现式转化为后缀体现式进行求解。中缀转化为后缀体现式的算法如下所示：Void InfixToPostfix()seqStack s(SIZE); char ch,y; s.Push(#); while(cinch,ch!=#) if(isdigit(ch)|isalpha(ch) coutch; else if(ch=) for(s.Top(y),s.Pop();y!=(;s.Top(y),s.Pop() couty; else for(s.Top(y),s.Pop();icp(ch)=isp(y);s.Top(),s.P

22、op() couty; s.Push(y); s,Push(ch); while(!s.IsEmpty() s.Top(y); s.Pop(); if(y!=#) couty; coutendl;八、程序设计总结总结可以涉及：程序设计过程的收获、遇到的问题，遇到问题解决问题过程的思考、程序调试能力的思考，对该课程组织和考核方式的建议等。通过一周多时间的奋斗，这次数据构造的课程设计终于做完了。通过这次课程设计使我在挫折中学到了诸多的东西。在编程前，我都是进行了一下分析，考虑在整个程序中需要什么函数，对每个函数我都进行了研究，并且参照了课本和资料。在编完整个程序后，进行调试，发现了诸多的错误，我通过无多次的改善，修改错误，总算使其能进行对的的运营。通过本次的课程设计，我们深深体会到数据构造的重要性。理解典型数据构造的性质是非常有用的，她往往是编写程序的核心。与此同步，我逐渐提高了自己的程序设计和调试能力，我发目前面对较难解决的编程问题时，可以先分割成许多小的部分，然后再整合起来，整合的过程是十分重要的；此外，清晰的思路和理性的措施是解决问题的核心。相信在越来越多的尝试之后，自己会不断进步和提高。在此我要感谢王教师在数据构造及课程设计中对我的指引和协助。