长整数四则运算.doc

山东理工大学计算机学院课 程 设 计（数据结构）班 级计科0503班姓 名王新政学 号0512105988指导教师肖爱梅 张艳华二七 年 七 月十三日课程设计任务书及成绩评定课题名称长整数四则运算、题目的目的和要求： 设计中要求综合运用所学知识，上机解决一些与实际应用结合紧密的、规模较大的问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析、解决实际问题的能力。通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。、设计进度及完成情况日 期内 容7.2-7.4熟悉设计任务，查阅有关文献资料，确定所采用的数据结构，初步制定解决问题的方法，完成课程设计说明书内容1-3部分7.57.10选择合适的存储结构,明确解决问题的算法，上机编写并调试源程序7.117.12整体调试程序并记录调试中的问题，完成课程设计说明书第4-6部分。7.13演示设计成果，考核成绩。整理课程设计报告。、主要参考文献及资料1 严蔚敏，吴伟民主编. 数据结构（C语言版）.清华大学出版社. 2002 2 殷人昆等著. 数据结构（C+版）. 清华大学出版社. 20013 金远平著. 数据结构（C+描述）. 清华大学出版社. 2005 4 Frank M.Carrano 等著. 数据结构与+高级教程.清华大学出版社. 20045 严蔚敏,吴伟民主编. 数据结构习题集（C语言版）.清华大学出版社. 2002学科部主任_（签字）、成绩评定：设计成绩： （教师填写）指导老师： （签字）二七 年 七 月十三日目 录第一章 概述.1第二章 系统分析.2第三章 概要设计.3第四章 详细设计与源程序.4第五章 调试过程中的问题及系统测试情况.12第六章 结束语13参考文献.14第一章 概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。数据结构是一门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。本课程设计是利用栈的相关操作实现对任意长的整数进行加、减、乘、除四则运算。程序运行可以实现任意长整数的四则运算。例如：进行加法运算时：利用程序进行的长整数加法输入-23456789；-76543211；输出-100000000。输入-99999999；1000000000000输出999900000001。图1-1长整数四则运算加法进行乘法运算时：输入-123456；123456；输出输入789456；123456；输出97463079936。利用程序进行的长整数乘法图1-2长整数四则运算乘法第二章 系统分析2.1设计思想开始建立两个空的栈。一个用来存放长整数运算的运算符。另一个用来存放长整数数字字符。通过调整栈内元素的进出顺序来实现长整数的加、减、乘、除四则运算2.2主要功能 系统通过建立两个空栈Stack(so)和Stack(sd)用来存放运算符和数据。建立一个函数Getnumbersize()来获取数字字符的长度。用一个函数Transfer()来将数字字符转换成整数数据。然后利用if和else语句实现对从键盘采集来的字符利用栈的后进先出的性质进行判断和进出栈操作。从而实现任意长整数的四则运算。第三章 概要设计本设计利用栈的操作在VC+平台上实现长整数的四则运算。结构流程图见右图开始建立两个栈用来存放数字字符和操作符输出提（示语开始键盘采集判断运算的优先级是否为“（”yesno将“（”压栈“stack(so)”将数字字符转换成整数并压栈到Stack(sd)判断后面的字符是“+”、“-”yes直接压栈到Stack(so)no是乘除运算符号判断后面是否为“（”yesno将后面的连续数字字符一并转换成数值t2,sd出栈给t1,将t3=t2*t1压栈到sd*/ 对两个栈内元素依次出栈进行运算，最后得结果。结束 图3-3整数四则运算流程图第四章 详细设计与源程序1详细设计：系统建立两个空栈Stack(so)和Stack(sd)用前一个存放运算符“+”、“-”、“*”、“/”且程序规定“（”为1，“+”为2，“-”为3，“*”为4，“/”为5，“”为。后一个存放将要进行运算的操作数。当系统运行开始时输出“提示：若有负数输入请用括号括起来”和“Please input formula(format:(1+2)*1.2/4=):”。用户输入一连串的字符，开始进行键盘采集。当采集完毕时，系统开始判断运算的优先级，若为“（”则将“(”的代码1直接入到栈Stack(so)中，然后将后面的数字字符转换成整数数据入到栈Stack(sd)中。当入栈完毕再次判断数字字符后面的运算符，若是“+”、“-”则直接将2，3入栈到Stack(so)中。如果是“*”或“/”则进行 优先级判断，看“*”（“/”）后面是不是有“（”如果有则将4（5）入到栈 Stack(so)中。如果没有则将前面的整数数据出栈与“*”（“/”）后的数字字符转换成的整数数据进行运算将结果存入定义的变量 t3中然后将t3入到栈Stack(sd)中。等到读入的数据出现“=”时确定入栈完毕。然后按照栈的“后进先出”规则进行出栈逐步进行运算得最后结果。2源程序如下：#include #include #include #include #include #define M 40 /*定义堆栈*/ typedef struct double dataM; int top; Stack; /*初始化堆栈*/ InitStack(Stack *s) s-top=0; /*判断栈是否为空*/ int StEmpty(Stack *s) if(s-top=0) return 1; else return 0; /*入栈操作*/ StPush(Stack *s,double x) if(s-top=M) printf(The stack is overflow!); /此处应该用malloc函数分配一定的空间给栈 else s-top=s-top+1; s-datas-top=x; /*出栈操作*/ double StPop(Stack *s) double t; if(!StEmpty(s) t=s-datas-top; s-top=s-top-1; else printf(StPop:The stack is empty!); t=NULL; return t; /*获取栈顶元素*/ double StGetTop(Stack *s) double t; if(!StEmpty(s) t=s-datas-top; else printf(StGeTop:The stack is empty!); t=NULL; return t; /*将数字字符转换成整形*/ int ChrTransferint(char c) int n; switch(c) case 0: n=0;break; case 1: n=1;break; case 2: n=2;break; case 3: n=3;break; case 4: n=4;break; case 5: n=5;break; case 6: n=6;break; case 7: n=7;break; case 8: n=8;break; case 9: n=9;break; return n; /*获取两个操作符之间数字字符的个数,返回的是最后一个数字字符的位置*/ int GetNumsize(char str,int n1) int n2=n1; while(isdigit(strn2)|(strn2)=46)/*isdigit()判断是否数字字符*/ n2=n2+1; /为何要加1？ return n2; /数据长度加1 /*判断上个函数中获得的数字字符串中是否包含小数点，并返回它的位置，不包含，返回-1*/ int IsIncludepoint(char str,int n1,int n2) /n1初始值是0 int n3=-1; /不包含小数点 int i; for(i=n1;i=n2;i+) /n2=n2+1是该数字字符的长度 if(stri=.) n3=i; break; return n3; /*将数字字符转换成数值*/ double Transfer(char str,int n1,int n2,int n3) double data=0; int i,ct; if(n3=n1;i-) ct=ChrTransferint(stri); data=data+ct*pow(10,n2-i);/*pow(x,y)计算x的y次方的值*/ /含有小数点 else for(i=n3-1;i=n1;i-) ct=ChrTransferint(stri); data=data+ct*pow(10,n3-1-i);/*pow(x,y)计算x的y次方的值*/ for(i=n3+1;i=n2;i+) ct=ChrTransferint(stri); data=data+ct*pow(0.1,i-n3);/*pow(x,y)计算x的y次方的值*/ /含有小数点的数字字符转换成数字完成 return data; /*主程序*/ main() char strM,c; char a; int n,p1,p2,p3; /*n为字符串长度，p1,p2,p3分别为数字字符起始位置，结束位置，和小数点位置*/ double data; /*存放转换后的数值*/ int i=0; Stack *so=(Stack *)malloc(sizeof(Stack); /*存储操作符 (:1,+:2,-:3, *:4,/:5 字符),不压栈*/ Stack *sd=(Stack *)malloc(sizeof(Stack); /*存储操作数*/ InitStack(so); InitStack(sd); /该栈存放数据 printf(提示：若有负数输入请用括号括起来n); printf(Please input formula(format:(1+2)*1.2/4=):n); n=0; while(a=getchar()!=n) /用a开始记录输入的数据包括加减运算符。 strn=a; n+; while(in) c=stri; if(c=() /*c若是(直接入栈so，i+*/ StPush(so,1); i+; else if(isdigit(c) p1=i; /*c若是数字字符，一并将后面的连续数字字符转换为数值并压栈到sd,并把i设为后面的*/ p2=GetNumsize(str,p1); p3=IsIncludepoint(str,p1,p2-1); /*仅仅是用来找到第一个非数字字符的位置*/ data=Transfer(str,p1,p2-1,p3); StPush(sd,data); i=p2; else if(c=+) StPush(so,2); /*c若是+直接入栈so,i+*/ i+; else if(c=-) StPush(so,3); /*c若是-直接入栈so,i+*/ i+; else if(c=*) if(stri+1=() /*c若是*它后面的字符是否为(，若是直接将*压栈so，*/ StPush(so,4); i+; else double t1,t2,t3; /*若不是，为数字字符,将后面的连续数字字符一并转换成数值t2,sd出栈给t1,将t3=t2*t1压栈到sd*/ t1=StPop(sd); /*操作符*不压栈so*/ p1=i+1; /原先p1已经等于第一个数字字符的长度，p1+1则是下一个连续数字字符的开始。 p2=GetNumsize(str,p1); p3=IsIncludepoint(str,p1,p2-1); t2=Transfer(str,p1,p2-1,p3); t3=t1*t2; StPush(sd,t3); i=p2; else if(c=/) if(stri+1=() StPush(so,5); i+; else double t1,t2,t3; t1=StPop(sd); /*c是/同*/ p1=i+1; p2=GetNumsize(str,p1); p3=IsIncludepoint(str,p1,p2-1); t2=Transfer(str,p1,p2-1,p3); t3=t1/t2; StPush(sd,t3); i=p2; else if(c=) double t1,t2,t3; int p; while(p=StPop(so)!=1&!StEmpty(so) /*c若是),出栈so,判断是+或-,出栈sd两个操作数，进行加减运算*/ /*直到StPop=(*/ t1=StPop(sd); t2=StPop(sd); if(p=2) t3=t2+t1; StPush(sd,t3); else if(p=3) t3=t2-t1; StPush(sd,t3); if(StGetTop(so)=4) /*然后判断so栈顶是否为*或者/*/ StPop(so); t1=StPop(sd); /*为*出栈so,出栈 sd 获得2个操作数，进行乘法操作*/ t2=StPop(sd); t3=t2*t1; StPush(sd,t3); else if(StGetTop(so)=5) StPop(so); t1=StPop(sd); /*为/出栈so,出栈 sd 获得2个操作数，进行除法操作*/ t2=StPop(sd); t3=t2/t1; StPush(sd,t3); i+; else if(c=) double t1,t2,t3; /*c若是=，这是so内只有加减号，出栈so到p ，sd到t1,t2*/ int p; while(!StEmpty(so) t1=StPop(sd); t2=StPop(sd); p=StPop(so); if(p=2) t3=t2+t1; /*p=+,加法运算，并将结果t3压栈sd*/ StPush(sd,t3); else if(p=3) t3=t2-t1; StPush(sd,t3); /*p=-,减法运算，并将结果t3压栈sd*/ i+; if(!StEmpty(so)|StEmpty(sd) printf(Input error,Back!n); /*若so不为空，或者sd为空，且sd中只有一个元素,则输入的式子不对*/ else double end; int i; /*否则，sd中的那个数据就是最后计算结果，打印输出*/ end=StGetTop(sd); printf(The value of this formula:n); for(i=0;in;i+) printf(%c,stri); printf(%fn,end); 第五章 调试过程中的问题及系统测试情况1编译时出现的问题： 出现的错误一般是由粗心造成的，例如：因多重大括号而导致的大括号丢失或过多。偶尔掉落“；”等导致系统调试时出现错误。经系统提示都可找到错误出处并修改成功。当输入数据进行测试时。出现过比较重大的错误。如果输入的数为负数非常容易出现数据溢出现象，得不到正确结果，例如：-12+4按照原先的结果应该是-8。结果当运行时结果却是-16。如果输入12-4结果和预期的一样。但是如果第一个数是负数不论后面是什么样的数据和运算符总是得不到预期的结果。经过反复的数据测试最后经过思考决定在输入负数时用括号括起来这样就解决了上面所述问题。当再次输入（-12）+4时能够得到-8。输入35+（-20）也可以得到应得数据15。即使是象-99999999这样很大的整数进行相应的四则运算也可以实现准确无误。本以为问题已经全部解决。但当输入数据48-（-18）时 却又出现了问题。本应该是66，结果却是-30。即使将-18用括号括起来也无济于事。尝试另外一表达式123-（