数据结构》课程设计报告-实现对算术四则溷合运算表达式的求值以及大整数计算.doc

1、江汉大学文理学院课程设计报告课程名称： 设计题目： 系 别： 专 业： 组 别： 学生姓名: 起止日期: 年 月 日 年 月 日 指导教师: 承诺书本人郑重声明：本人所呈交的学术论文，是本人在导师指导下独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包括任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集体，均已在文中以明确的方式标明。本人完全意识到本声明的法律结果由本人承担。 学生（签名）：年 月 日数据结构课程设计报告题目：实现对算术四则混合运算表达式的求值以及大整数计算一设计目的数据结构是计算机专业的核心课程，是一门实践性很强的课程。课程设计

2、是加强学生实践能力的一个强有力手段，要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并上机调试的基本方法，还要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。二问题描述(一) 当用户输入一个合法的算术表达式后，能够返回正确的结果。能够计算的运算符包括：加、减、乘、除、括号；能够计算的操作数要求在实数范围内；对于异常表达式能给出错误提示。(二) 求两个不超过200位的非负整数的和，积和商。三调试与操作说明（一）需求分析本程序所做的工作为：能直接求出四则表达式的值，并输

3、出；可以解决因数值位数太大unsigned类型都无法表示的大数之间的运算。本程序可用于小学教师对学生作业的快速批改以及对数值位数要求较大的科学运算。此程序规定：1.程序的主要功能包括两部分：表达式求解和大整数的运算。2.表达式求解中输入的必需为一个正确的四则表达式，可以是整型也可以为浮点型，比如：3*(7-2)+5和3.154*(12+18)-23。大整数的运算中根据提示要输入两行数据位数不能大于200位。3.程序的输出：表达式求解中为一浮点型数据，大整数运算中输出的即为运算之后的结果，结果里不能有多余的前导0。（二） 概要设计1.ADT LinkStack数据元素：此链栈中的所有元素类型为字

4、符型的数字字符数据关系：栈中数据元素之间是线性关系。基本操作:（1） InitStack(LinkStack &head)操作结果：构造一个空栈head（2） IsEmpty(LinkStack head)初始条件：栈head已存在操作结果：若栈为空栈，则返回TRUE,否则FALSE（3） Push(LinkStack &head,ElementType element)初始条件：栈head已存在操作结果：插入元素element为新的栈顶元素（4） Pop(LinkStack &head,ElementType &element)初始条件：栈head已存在且非空操作结果：删除head的栈顶元素

5、，并用e返回其值（5） GetTop(LinkStack head, ElementType &element)初始条件：栈head已存在并且非空操作结果：用e返回head的栈顶元素（6） DestroyStack(LinkStack &head)初始条件：栈head已存在操作结果：栈head 被销毁ADT LinkStack2ADT LinkCharStack数据对象D：元素类型为字符型的符号字符数据关系R：基本操作：栈中数据元素之间是线性关系。（1） CInitStack(LinkCharStack &head)（2） CIsEmpty(LinkCharStack head)（3） CPu

6、sh(LinkCharStack &head,ElementType element)（4） CPop(LinkCharStack &head,ElementType &element)（5） CGetTop(LinkCharStack head, ElementType &element)（6） CDestroyStack(LinkCharStack &head)ADT LinkCharStackl 系统中子程序及功能要求：（1） add():计算两个不大于200位的大整数的和，此文件包含于头文件calculator.h中。（2） multiply()：实现两个大整数的积的运算，此文件也包含

7、于头证件calculator.h中。（3） Comop(char ch)：判断输入的字符是否为运算符（4） char Precede(char ch,char c)：比较两个运算符的优先级，ch是栈顶字符，c是表达式字符。（5） ElementType Operate(ElementType a,char ch,ElementType b)：解析表达式中的双目运算，其返回的结果即为双目运算表达式的值。（6） int error(char *str) ：错误提示函数，实现对多种非法四则表达式的判断，并给出提示，让用户更正自己的输入错误。（7） void MenuPrint()：主菜单打印函数。（

8、8） void submenu()：大整数运算功能模块的子菜单。（9） void Clear()：清屏函数。（10） ElementType EvaluateExpression(char *exp)：这是此程序的核心函数，可以综合其它子函数，实现最终的表达式求解。l 各程序模块之间的调用关系（子程序编号见上）：主函数可调用子程序1，2，7，8，9，10。子程序10可调用子程序3，4，5，6。3详细设计 表达式计算核心算法的思想及伪代码：此算法的基本思想：首先置操作数栈OPND为空栈，表达式起始符“#”为运算符的栈底元素；依次读入表达式中每个字符，若是操作数则进栈，若是运算符则和OPTR栈的栈

9、顶运算符比较优先权作相应操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）此算法的伪代码：ElementType EvaluateExpression(char *exp)定义两个字符变量c和ch,c代表输入表达式中的字符，ch代表栈顶运算符;定义字符指针 *p,*q,*temp;temp指向运算符后面的一个字符double i=0,a=0,b=0;将传入的实参赋给p,q;定义一个运算符栈 OPTR;定义一个操作数栈 OPND;调用函数InitStack()初始化栈OPND; 调用函数InitCharStack()初始化栈OPNR ;调用函数CPush(OPTR,

10、#)将#压入运算符栈;c=*p;temp=p;p+;if(第一个字符就为-)c=*p;temp=p;p+;while(栈不为空或表达式没有结束)/进入最外层循环if(不是运算符)/则解析数字字符串然后进操作数栈整数部分m=0;小数部分n=0;while(没有遇到小数点并且为数字字符) 解析整数部分m if(遇到小数点) 解析小数部分c=*p;将p指针移到第一个出现的字符;将q指针指向小数的最后一位;while(p指针不指向.)将p指向的字符转为小数np-;p=q;p+;if(运算符为-并且运算符前一个为（或者为表达式的开始)调用Push(OPND,-(m+n)将m+n的相反数入栈;else 调

11、用Push(OPND,m+n)将m+n入栈;数字进栈结束else/是运算符时则进栈OPTRif(运算符为-&运算符前一个为（)c=*p;temp=p;p+;else调用函数CGetTop(OPTR,ch)得到OPTR的栈顶元素; switch(调用函数Precede(ch,c)判断栈顶元素与接收的字符的优生级别)case 栈顶运算符优先权低:调用函数CPush(OPTR,c)将c入运算符栈;接收下一个字符;case 栈顶运算符优先权高：运算符出栈得到ch;数字栈连续出栈两次得到a,b ;调用Operate(a,ch,b)并将结果入栈到数字栈;break;case 优生权相等：脱括号并接收下一个

12、字符;调用CPop(OPTR,ch)脱括号;接收下一个字符;default:接收下一个字符;退出switch循环/else1/else2/退出最外层while循环调用函数GetTop(OPND,i)得到栈顶元素i;将两个栈消毁;返回I;EvaluateExpression函数结束 实现大整数相加的add()函数的伪代码：void add()输入两个要运算的大整数分别存在长度为MAX_LEN+10的字符串数组szline1和szline2中;循环计数变量 i,j;调用库函数memeset()将地址an1开始的sizeof(an1)字节内容置成0;调用库函数memeset()将地址an2开始的si

13、zeof(an2)字节内容置成0;将szline1中存储的字符串形式的整数转换到an1中去将szline1中存储的字符串形式的整数转换到an1中去for(i=0;i=0;i-)如果 没有标记第一次出现过了0那么 输出an1i;否则 如果 an1i为0 则 输出an1i;标记已经出现过0; 实现大整数相加的add()函数的伪代码：void multiply()输入两个要运算的大整数分别存在长度为MAX_LEN+10的字符串数组szline1和szline2中;循环计数变量 i,j;调用库函数memeset()将地址an1开始的sizeof(an1)字节内容置成0;调用库函数memeset()将地

14、址an2开始的sizeof(an2)字节内容置成0;调用库函数memeset()将地址aresult开始的sizeof(aresult)字节内容置成0。将szline1中存储的字符串形式的整数转换到an1中去将szline1中存储的字符串形式的整数转换到an1中去for(i=0;inlen2;i+)每一都用an1的一位，去和an2各位相乘/从an1的个位开始for(j=0;jnlen1;j+)用选定的an1的那一位，去乘an2的各位aresulti+j+=an2i*an1j;两数第i,j位相乘，累加到结果的第i+j位下面的循环统一处理进位问题for(i=0;i=10)aresulti+1+=a

15、resulti/10;aresulti%=10;输出结果和上一函数一样4测试分析按照附录中的测试数据，得出如下测试、分析结果：（1） 表达式求解功能当我们输入表格中两个正确的四则表达式时程序能准确地求得其值：完全支持浮点数，正负数的运算;而当我们输入第三组错误的表达式时，程序能做出正确判断，提醒用给用户输入一个正确的表达式。其数据测试的情况见截图：表达式一运算结果由表一知结果正确。表达式二运算结果由表一知结果正确。表达式三运算出错情况（2） 大整数加法功能输入两组不大于200位的大整数，能准确计算出结果 其截图如下图所示：选择功能b（3） 大整数乘法功能其测试截图如：第二组数据结果正确。5使用

16、说明1 运行程序，首先出现主菜单。主菜单包括四个选项：选项a：表达式求解，选择该项可进行四则表达式的求解；选项b：大整数运算，选择该项可进行不大于200位的大整数的加法和乘法运算（目前只支持加，乘）；选项c：清屏；选项d：退出程序，选择该项将退出程序。2 大整数运算界面包括4个选项：选项1：两个大整数相加；选项2：两个大整数相乘；选项3：返回上一级菜单，可返回主界面。选项4：直接退出本程序。6附录（一）：测试数据组别表达式正确值112+（9-8）*7-（-6*5）4923.14*（67.305-65.305）+3.149.42312-（3-6*7）8-4无（表一）加法乘法整数112121212

17、12121212121212121212121212121212121212121212121212121212121212121212整数1111111111111111111111111111111111111111111111111111111111111111111111111111111整数24545454545454545454545454545454545454545454545454545454545454545454545454545整数2222222222222222222222222222222222222222222222222222222222222222222222

18、2222222结果5757575757575757575757575757575757575757575757575757575757575757575757575757结果2469135802469135802469135802469135802469135802469135802469135802469135802468641975308641975308641975308641975308641975308641975308641975308641975308642（表二）7附录（二）：C语言实现（源代码）源程序文件名清单：LinkStack.h/链栈的实现 数字栈LinkCharSta

19、ck.h/链栈的实现 符号栈Calculator.h/主要实现大整数的加，乘运算Calculator.cpp/主程序LinkStack.h头文件/这个栈是用来存储数字符的#include#define ERROR 0#define OK 1#defineTRUE 1#define FALSE 0typedef double ElementType;typedef int Status;typedef struct node ElementType data; struct node *next;StackNode, *LinkStack;void InitStack(LinkStack &he

20、ad) head=(LinkStack)malloc(sizeof(StackNode); head-next=NULL;Status IsEmpty(LinkStack head)if(head-next=NULL)return TRUE;else return ERROR;Status Push(LinkStack &head,ElementType element)/入栈LinkStack p;p=(LinkStack)malloc(sizeof(StackNode);if(p= NULL) return FALSE;p-data=element;p-next=head-next;hea

21、d-next=p;return OK;Status Pop(LinkStack &head,ElementType &element)/出栈if(IsEmpty(head)return FALSE;LinkStack temp=head-next; element=temp-data;head-next=temp-next;free(temp);return OK;int GetTop(LinkStack head, ElementType &element)if(head-next=NULL)return ERROR; element =head-next-data;return OK;St

22、atus DestroyStack(LinkStack &head) LinkStack q; while(head) q=head-next; free(head); head=q; return TRUE;LinkStack_Char.h头文件/这个栈是用来存储符号字符的#include #define TRUE 1#define FALSE 0#define NULL 0typedef char ElemType;typedef int Status;typedef struct node1ElemType data;struct node1 *next;StackCharNode,*L

23、inkCharStack;void CInitCharStack(LinkCharStack &head)head=(LinkCharStack)malloc(sizeof(StackCharNode);head-next=NULL;int CIsEmpty(LinkCharStack head)return (head-next=NULL)?TRUE:FALSE;int CPush(LinkCharStack &head,ElemType element)LinkCharStack temp=(LinkCharStack)malloc(sizeof(StackCharNode);if(!te

24、mp)return ERROR;temp-data=element;temp-next=head-next;head-next=temp;return TRUE;int CPop(LinkCharStack &head,ElemType &element)if(CIsEmpty(head)return FALSE;StackCharNode *temp=head-next;element=temp-data;head-next=temp-next;free(temp);return TRUE;int CGetTop(LinkCharStack head,ElemType &element)if

25、(head-next!=NULL)element=head-next-data;return TRUE;element=#;return FALSE;Status CDestroyStack(LinkCharStack &head)LinkCharStack q;while(head)q=head-next;free(head);head=q;return TRUE;calculator.h头文件/*calculator.h头文件*/#include#include#define MAX_LEN 200unsigned int an1MAX_LEN+10;unsigned int an2MAX

26、_LEN+10;unsigned int aresultMAX_LEN*2+10;char szline1MAX_LEN+10;char szline2MAX_LEN+10;void add()printf(请输入两个要运算的大整数:n);scanf(%s,szline1);scanf(%s,szline2);int i,j;memset(an1,0,sizeof(an1);/库函数memeset将地址an1开始的sizeof(an1)字节内容置成memset(an2,0,sizeof(an2);/下面将szline1中存储的字符串形式的整数转换到an1中去/an10对应于个位int nlen

27、1=strlen(szline1);j=0;for(i=nlen1-1;i=0;i-)an1j+=szline1i-0;int nlen2=strlen(szline2);j=0;for(i=nlen2-1;i=0;i-)an2j+=szline2i-0;for(i=0;i=10)/看是否要进位an1i-=10;an1i+1+;/进位printf(计算的结果为：n);bool bstartoutput=false;for(i=MAX_LEN;i=0;i-)if(bstartoutput)printf(%d,an1i);else if(an1i)printf(%d,an1i);bstartout

28、put=true;void multiply()printf(请输入两个要运算的大整数:n);scanf(%s,szline1);scanf(%s,szline2);int i,j;memset(an1,0,sizeof(an1);/库函数memeset将地址an1开始的sizeof(an1)字节内容置成memset(an2,0,sizeof(an2);memset(aresult,0,sizeof(aresult);/下面将szline1中存储的字符串形式的整数转换到an1中去/an10对应于个位int nlen1=strlen(szline1);j=0;for(i=nlen1-1;i=0;

29、i-)an1j+=szline1i-0;int nlen2=strlen(szline2);j=0;for(i=nlen2-1;i=0;i-)an2j+=szline2i-0;/以下为进行计算for(i=0;inlen2;i+)/每一都用an1的一位，去和an2各位相乘/从an1的个位开始for(j=0;jnlen1;j+)/用选定的an1的那一位，去乘an2的各位aresulti+j+=an2i*an1j;/两数第i,j位相乘，累加到结果的第i+j位/下面的循环统一处理进位问题for(i=0;i=10)aresulti+1+=aresulti/10;aresulti%=10;printf(计

30、算的结果为：n);bool bstartoutput=false;for(i=MAX_LEN*2;i=0;i-)if(bstartoutput)printf(%d,aresulti);else if(aresulti)printf(%d,aresulti);bstartoutput=true;Calculator.cpp# include # include # include # include LinkStack.h# include LinkCharStack.h# include calculator.h# define STACK_INIT_SIZE 30# define STACK

31、INCREAMENT 10# define NUMBER 30/判断ch是否为运算符int Comop(char ch)switch(ch)case +:case -:case *:case /:case (:case ):case #:return 1;default:return 0;/Comop/比较两个运算符的优先级char Precede(char ch,char c)/ch是栈顶字符,c 是表达式字符switch(ch)case +:case -:if(c=+|c=-|c=)|c=#)return ;if(c=*|c=/|c=()return ;if(c=()return ;cas

32、e (:if(c=+|c=-|c=*|c=/|c=()return ;if(c=()return ;if(c=#)return ;case #:if(c=+|c=-|c=*|c=/|c=()return =0&stri+1=0&stri57) |(stri=/ & stri+1=0) |(int(stri)31 & int(stri)=0&c=0&c=9)p+;c=*p;q=p;p-;while(*p!=.)n=n/10+(*p-48)/10.0;p-;p=q;p+;if(*(temp-2)=(&*(temp-1)=-|temp-1=exp)Push(OPND,-(m+n);else Push

33、(OPND,m+n);/*数字进栈结束*else/是运算符时则进栈OPTRif(c=-&*(p-2)=()c=*p;temp=p;p+;else/else1CGetTop(OPTR,ch);switch(Precede(ch,c)case :/栈顶运算符优先权高CPop(OPTR,ch);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,ch,b);break;case =:/脱括号并接收下一个字符CPop(OPTR,ch);c=*p;temp=p;p+;break;default:c=*p;temp=p;p+;/switch/else1/else2/退出最外层循环GetTop(OPND,i);DestroyStack(OPND);C