大整数计算器.docx

数据结构课程设计报告撰写要求一）纸张与页面要求1 采用国际标准 A4 型打印纸或复印纸，纵向打印。2 封页和页面按照下面模板书写（正文为：小四宋体 1.5 倍行距）。3图表及图表标题按照模板中的表示书写。二） 课设报告书的内容应包括以下各个部分： （按照以下顺序装订）1. 封页（ 见课设模版 ）2、学术诚信声明，所有学生必须本人签字，否则教师拒绝给予成绩。2.任务书 （学生教师均要签字 , 信息填写完整 ）3. 目录4. 正文一般应包括以下内容 :（1） 题目介绍和功能要求（或描述）课程设计任务的详细描述 （ 注意不能直接抄任务书 ）, 将内容做更详细的具体的分析与描述； （ 2） 系统功能模块结构图绘制系统功能结构框图及主要模块的功能说明；（ 3） 使用的数据结构的描述 : 数据结构设计及用法说明 ;（ 4） 涉及到的函数的描述 ;（ 5） 主要算法描述 （ 程序流程图 ）（6） 给出程序测试 / 运行的结果设计多组数据加以描述（包括输入数据和输出结果）（ 7） 课程设计的总结及体会（ 8） 参考文献格式要求： 1 作者，等 . 书名. 出版地：出版社，出版年5. 附录：程序清单 （ 应带有必要的注释 ）沈阳航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：大整数计算器院（系）：计算机学院专业:班级:学号:姓名:指导教师说明：结论（优秀、良好、中等、及格、不及格）作为相关教环节考核必要依据；格式不符合要求；数据不实，不予通过。报告和电子数据必须作为实验现象重复的关键依据。审查结论签名；年月日学术诚信声明本人声明：所呈交的报告（含电子版及数据文件）是我个人在导师指 导下独立进行设计工作及取得的研究结果。尽我所知，除了文中特别 加以标注或致谢中所罗列的内容以外，报告中不包含其他人己经发表 或撰写过的研究结果，也不包含其它教育机构使用过的材料。与我一 同工作的同学对本研究所做的任何贡献均己在报告中做了明确的说明 并表示了谢意。报告资料及实验数据若有不实之处，本人愿意接受本 教学环节“不及格”和“重修或重做”的评分结论并承担相关一切后 果。本人签名：日期：年月日沈阳航空航天大学课程设计任务书课程设计名称数据结构课程设计专业网络工程学生姓名李典通班级34010201学号2013040102031题目名称大整数计算器的实现起止日期2015 年 1 月 5日起至2015 年1月 16 日止课设内容和要求：内容：由于整形数据存储位数有限，因此引入串的概念，将整型数据用字符串进行存储， 利用子符串的一个子符存储大整数的一位数值， 然后根据四则运算规则对相应位依次 进行运算，同时保存进位，从而实现大整数精确的运算。要求：1以大整数形式从键盘输入操作数。2演算在求值的运算操作中，输入操作数和主要的操作的变化过程。3禾U用所学知识，设计相应的数据结构。参考资料：1 严蔚敏，吴伟民数据结构（C语言版）M.北京：清华大学出版社，20062 吕国英.算法设计与分析M.北京:清华大学出版社,20063 徐宝文 李志.C程序设计语言M.北京：机械工业出版社,2004教研室审核意见：同意教研室主任签字：指导教师（签名）2014年 12月29日学生（签名）2014年 12月31日目 录1 课程设计内容 11.1 题目介绍11.2功能要求22系统功能模块32.1主模块32.1.1系统功能结构图 32.2主要模块功能说明 33详细设计53.1 数据结构描述53.2算法流程74程序测试及总结11.4.1 测试、运行.11.参考文献13附 录（关键部分程序清单） 161课程设计内容1.1 题目介绍由于整形数据存储位数有限，因此将整型数据用字符串进行存储。在大整数 计算器分为四个大模块，分别为大整数加法运算、大整数减法运算、大整数乘法 运算、大整数除法运算函数模块。由一个主模块所调用。加法运算功能，从个位开始逐位相加，超过或达到10则进位，同时将该位计 算结果存到另一个字符串中，直至加完大整数的所有位为止。减法运算功能，首先调用库函数strcmp判断这两个大整数是否相等，如果相 等则结果为0，否则用Compare函数判断被减数和减数的大小关系，进而确定结 果为正数还是负数，然后对齐位依次进行减法，不够减则向前借位，直至求出每 一位减法之后的结果。乘法运算功能，首先让乘数的每一位都和被乘数进行乘法运算，两个乘数之 积与进位相加作为当前位乘积，求得当前位的同时获取进位值，进而实现大整数 的乘法运算。除法运算功能，类似做减法，基本思想是反复做减法，从被除数里最多能减 去多少次除数，所求得的次数就是商，剩余不够减的部分则是余数，这样便可计 算出大整数除法的商和余数。主函数，主函数是程序的入口，采用模块化设计。通过一定的入口可以进行 加法运算功能、减法运算功能、乘法运算功能、除法运算功能。12 功能要求1. 大整数加法：采用数学中列竖式的方法，从个位开始逐位相加，超过或达到10则进位，同时将该位计算结果存到另一个字符串中， 直至加完大整数的所有 位为止。2. 大整数减法：首先调用库函数判断这两个大整数是否相等，如果相等则结 果为0，否则用Compare函数判断被减数和减数的大小关系，进而确定结果为正 数还是负数，然后对齐位依次进行减法，不够减则向前借位，直至求出每一位减 法之后的结果。3. 大整数乘法：首先让乘数的每一位都和被乘数进行乘法运算，两个乘数之 积与进位相加作为当前位乘积，求得当前位的同时获取进位值，进而实现大整数 的乘法运算。4. 大整数除法：反复做减法，从被除数里最多能减去多少次除数，所求得的 次数就是商，剩余不够减的部分则是余数。5其实就是利用算法中的高精度算法进行加减乘除的实现。来实现大整数计 算器。2系统功能模块2.1 主模块2.1.1系统功能结构图设计程序实现两个大整数四则运算，输出这两个大整数的和、差、积、商及 余数，实现大整数（200位以内的整数）的加、减、乘、除运算。根据需要可以 进行如下操作：加法、减法、乘法、除法。其功能模块图如图2-1所示。2.2数据结构描述大整数计算器分为四个大模块，分别为大整数加法运算、大整数减法运算、大整数乘法运算、大整数除法运算函数模块。加法运算功能，加法运算功能是将两个字符从个位开始进行逐位相加，然后把每一位的相加结果存放到字符串中，并且输出运算结果。其流程图如图3-2所示。输入两个相加的字符，然后从个位开始逐位相加，判断两个数相加的结果是 否大于或等于十，如果是，那么向前一位进一，并将所得结果存放到另一个字符 串中，如果不是，则直接将所得结果存放到另一个字符串中。当所有结果都存入 该字符串中时，判断是否所有位都进行了加法运算，若是，输出结果，若不是， 重复上述过程，继续进行运算，直至所有位都进行了加法运算时输出结果。减法运算功能，减法运算功能是将输入的两个相减的大整数， 对齐位依次进 行减法运算，并输出结果。首先，在输入两个大整数后开始判断他们是否相等， 若相等，输出结果为零， 结束运算。若不相等，开始进行运算结果的正负判断，当被减数大于减数时，结 果为正，否则结果为负。然后，对两个大整数对齐位依次进行减法，若够减且每 一位都已减完，那么输出运算结果；若不够减，则向前借位依次进行减法运算， 直到每一位都已减完，输出结果。其功能流程图如图3-3所示。乘法运算功能，首先让乘数的每一位都和被乘数进行乘法运算，两个乘数之 积与进位相加作为当前位乘积，求得当前位的同时获取进位值，进而实现大整数 的乘法运算。除法运算功能，类似做减法，基本思想是反复做减法，从被除数里最多能减 去多少次除数，所求得的次数就是商，剩余不够减的部分则是余数，这样便可计 算出大整数除法的商和余数。主函数，主函数是程序的入口，采用模块化设计。通过一定的入口可以进行 加法运算功能、减法运算功能、乘法运算功能、除法运算功能。3算法描述3.1 数据结构描述(1)加法运算功能加法运算功能是将两个字符从个位开始进行逐位相加，然后把每一位的相加 结果存放到字符串中，并且输出运算结果。输入两个相加的字符，然后从个位开始逐位相加，判断两个数相加的结果是 否大于或等于十，如果是，那么向前一位进一，并将所得结果存放到另一个字符 串中，如果不是，则直接将所得结果存放到另一个字符串中。当所有结果都存入 该字符串中时，判断是否所有位都进行了加法运算，若是，输出结果，若不是， 重复上述过程，继续进行运算，直至所有位都进行了加法运算时输出结果。详细 代码及程序见附录中的 代码的void In tAdditi on (char*auge nd, char*addend, char *sum)整数加法 模块。流程图见图3.1加法模块减法运算功能减法运算功能是将输入的两个相减的大整数，对齐位依次进行减法运算，并 输出结果。首先，在输入两个大整数后开始判断他们是否相等，若相等，输出结果为零，结束运算。若不相等，开始进行运算结果的正负判断，当被减数大于减数时，结 果为正，否则结果为负。然后，对两个大整数对齐位依次进行减法，若够减且每 一位都已减完，那么输出运算结果；若不够减，则向前借位依次进行减法运算， 直到每一位都已减完，输出结果。详细代码及程序见附录中的代码的voidIn tSubtratio n(char *minuend, char *subtrahe nd, char *differe nce)整数减法 模块。流程图见图3.2减法模块乘法运算功能乘法运算功能是将输入的两个大整数进行乘法运算，并输出结果。首先，输入两个大整数，一个为乘数一个为被乘数，让乘数和被乘数的每一 位相乘，并将相乘后所得的结果存放到另一个字符串中，以此循环下去。然后，判断两个大整数的每一位是否乘完，若是，则将所得的i个字符串相加，并输出相加后的结果，其值为两数相乘的乘积，若不是，继续进行以上操作，直至得到两个大整数相乘的结果。详细代码及程序见附录中voidIn tMultiplicatio n(char*multiplica nd, char *multiplier, char *product)整数乘模块。流程图见图3.3乘法模块除法运算功能除法运算功能是将输入的两个大整数进行除法运算，并输出结果。输入两个数，其中一个是除数，一个是被除数。用被除数减去除数，若被除 数小于除数，则输出被除数减除数的个数作为商，剩余不够减的数则为余数，并 输出商和余数。若被除数大于除数，继续循环被除数减除数的过程，直至被除数 小于除数，输出所得结果。详细代码及程序见附录中void In tDivisio n( char*divide nd, char *divisor, char *quotie nt, char *rema in der)整数除模块。流程图见图3.4除法模块3.2算法流程1. 加法运算功能图3.1加法模块设计图2.减法功能开始V图3.2减法模块设计图3.乘法功能乘法运算功能，首先让乘数的每一位都和被乘数进行乘法运算，两个乘数之 积与进位相加作为当前位乘积，求得当前位的同时获取进位值，进而实现大整数 的乘法运算。图3.3乘法模块设计图4.除法功能除法运算功能，类似做减法，基本思想是反复做减法，从被除数里最多能减 去多少次除数，所求得的次数就是商，剩余不够减的部分则是余数，这样便可计 算出大整数除法的商和余数。图3.4除法模块设计图4程序测试及总结4.1 测试、运行1、一般而言，编写一个能运行在操作系统上的程序， 都需要一个主函数。主 函数意味着建立一个独立进程，且该进程成为了程序的入口，对其它各函数进行 调用，当然其它被调用函数也可以再去调用更多函数。主函数既是程序的入口， 又是程序的出口。先输入两个数，选择所需的运算。其功能实现图如图4-1所示图4.1主界面2、加法运算功能，采用数学中列竖式的方法，从个位（即字符串的最后一个 字符）开始逐位相加，超过或达到10则进位，同时将该位计算结果存到另一个字 符串中，直至加完大整数的所有位为止。其功能实现图如图4-2所示。3、减法运算功能，首先调用库函数strcmp判断这两个大整数是否相等，如果相等则结果为0,否则用Compare函数判断被减数和减数的大小关系，进而确 定结果为正数还是负数，然后对齐位依次进行减法，不够减则向前借位，直至求 出每一位减法之后的结果。其功能实现图如图4-3所示。图4.2加法运行图4.3减法运算3、 乘法运算功能，首先让乘数的每一位都和被乘数进行乘法运算，两个乘数 之积与进位相加作为当前位乘积，求得当前位的同时获取进位值，进而实现大整 数的乘法运算。功实现图如图4-4所示4、除法运算功能，类似做减法，基本思想是反复做减法，从被除数里最多能 减去多少次除数，所求得的次数就是商，剩余不够减的部分则是余数，这样便可计算出大整数除法的商和余数。其功能实现图如图4-5所示图4.4乘法运算实现图4.5除法运算5、按5退出计算本次计算，按任意键继续运算，按Ctrl+z退出计算器，其功能实现图如图4-6所示。图4.5结束界面图4.6 0与0运算参考文献1、谭浩强.C程序设计.北京：清华大学出版社.1999.122、滕国文.数据结构课程设计.北京：清华大学出版社.2010.093、 苏仕华等编著.数据结构课程设计.北京：机械工业出版社.2005.054、张乃笑.数据结构与算法.电子工业出版社.2004.105、徐孝凯.数据结构课程实验.清华大学出版.2002.76、 严蔚敏.数据结构（C语言版）.清华大学出版社.2006附 录（关键部分程序清单）#in clude<stdio.h>#in clude<stdlib.h>#in clude<stri ng.h>#defi ne MAX 200int Compare(c onst char *a, const char *b);void In tAdditi on( char *auge nd, char *adde nd, char *sum);void In tSubtrati on( char *minuend, char *subtrahe nd, char *differe nee);void In tMultiplicati on( char *multiplica nd, char *multiplier, char *product);void In tDivisio n(char *divide nd, char *divisor, char *quotie nt, char *rema in der);int Radix(char *toStr, char *fromStr);void FloatAdditi on( char *auge nd, char *adde nd, char *sum);void FloatSubtrati on( char *minuend, char *subtrahe nd, char *differe nee);void FloatMultiplicati on( char *multiplica nd, char *multiplier, char *product);void FloatDivisi on( char *divide nd, char *divisor, char *quotie nt, i nt precisi on);void In sert(char s, int left, int right);int IsCycle(char aMAX, i nt label);int mai n(void) int t;i nt p;char aMAX = 0;char bMAX = 0;char c3*MAX = 0;char dMAX = 0;puts("输入任意值开始计算Ctrl+z结束计算");while(sca nf("%d",&p)!=EOF)puts("请输入两个数 a， b：");scan f("%s %s", &a,& b);prin tf(”=选择运算方式=");printf("ttttn1.加法运算 n");printf("ttttn2.减法运算 n");printf("ttttn3.乘法运算 n");printf("ttttn4.除法运算 n");printf("tttttn5.退出 n");prin tf("=n");puts(a);puts(b);t=1；while(t!=5)scan f("%d", &t);if(t=1)FloatAdditio n(a, b, c);puts("两者之和：”)； puts(c);else if(t=2)FloatSubtrati on(a, b, c);puts("两者之差："); puts(c);else if (t=3)FloatMultiplicati on (a, b, c);puts("两者之积：”)； puts(c);else if(t=4)FloatDivisio n(a, b, c, MAX);puts("两者之商："); puts(c);system("pause");void FloatAdditi on( char *auge nd, char *adde nd, char *sum) 力口法char cAugMAX = 0;char cAddMAX = 0;char cSumMAX = 0;in tie nAug, le nAdd, le nSum;/分别存储三个数的小数点后的数字个数 int i, topAug, topAdd;/去掉小数点，把浮点数转化成整数后存储到新的字符串len Aug = Radix(cAug, auge nd); lenAdd = Radix(cAdd, adde nd); topAug = strle n( cAug); topAdd = strle n( cAdd);/在小数部分较短的字符串后补零，使得两个数的小数部分长度相等if (le nAug > len Add)len Sum = len Aug;for (i=le nAug-le nAdd; i>0; i-)cAddtopAdd+ = 'O'elselen Sum = len Add;for (i=le nAdd-le nAug; i>0; i-)cAugtopAug+ = '0'cAddtopAdd+ = '0' cAugtopAug+ = '0'/执行整数加法运算In tAdditio n( cAdd, cAug, cSum);i = strle n( cSum) - 1;while (le nSum > 0 && cSumi = '0')/去掉小数部分多余的零i-;len Sum-;cSumi+2 = '0'while (lenSum > 0)/在适当位置插入'.'cSumi+1 = cSumi;i-;len Sum-;cSumi+1='.'strcpy(sum, eSum);减法void FloatSubtrati on( char *minuend, char *subtrahe nd, char *differe nce) if (strcmp( minuend, subtrahe nd) = 0)strcpy(differe nee, "0");return;char cMMAX = 0;char cSMAX = 0;char cDMAX = 0;in t le nM, le nS, le nD;int i, topM, topS;lenM = Radix(cM, min ue nd); lenS = Radix(cS, subtrahe nd); topM = strle n( cM);topS = strle n(cS);if (lenM > lenS)lenD = lenM;for (i=le nM-le nS; i>0; i-) cStopS+ = '0'elselenD = lenS;for (i=le nS-le nM; i>0; i-) cMtopM+ = '0'cMtopM+ = '0' cStopS+ = '0'In tSubtratio n(cM, cS, cD);i = strle n(cD) - 1;while (le nD > 0 && cDi = '0')i-；le nD-;cDi+2 = '0：while (le nD > 0)cDi+1 = cDi;i-；le nD-;cDi+1='.'if (i = -1)cDO = 'O'cD1='.'cD2 = 'O'strcpy(differe nee, cD);乘法void FloatMultiplicati on( char *multiplica nd, char *multiplier, char *product) char cDMAX = 0;char cRMAX = 0;char cP2*MAX = 0;in t le nD, le nR, le nP;lenD = Radix(cD, multiplica nd);lenR = Radix(cR, multiplier);lenP = lenD + lenR;In tMultiplicati on (cD, cR, cP);int i = strle n(cP) - 1;while (le nP > 0 && cPi = '0')i-;len P-;cPi+2 = '0'while (le nP > 0 && i >= 0) cPi+1 = cPi;i-； len P-;cPi+1='.'if (i = -1)for (i=strle n(cP); i>0; -i) cPi+1+le nP = cPi;for (i=0; i<le nP; +i)cPi+2 = 'O'cP1='.'cP0 = '0'strcpy(product, cP);除法void FloatDivisi on( char *divide nd, char *divisor, char *quotie nt, int precisi on)/ if (Compare(divide nd, divisor) = 0)strcpy(quotie nt, "1.");return ;if (strcmp(divisor, "0.")=0 | strcmp(divisor, "0")=0)strcpy(quotie nt, "0.");return ;char cDMAX = 0;char cRMAX = 0;char cQMAX = 0;char cYMAX = 0;char tcYMAXMAX = 0;in t le nD, le nR, le nQ;int i, j, t, s, left;lenD = Radix(cD, divide nd);lenR = Radix(cR, divisor);if (lenD > lenR)lenQ = lenD - le nR;elsele nQ = 0;i = strle n( cD);for (j=0; j<le nR-le nD; j+)cDi+ = 'O'cDi = '0'In tDivisio n(cD, cR, cQ, cY);t = j = strle n( cQ);for (i=0; i<le nQ; +i,-t)if (t > 0)cQt = cQt-1;elset = 1;cQt = 'O'cQt='.'if (t = 0)for (i=j+; i>=0; -i)cQi+1 = cQi;cQ0 = 'O'+j;,"0")!=0)i = t = 0;while (i < precisi on && strcmp(cY strcpy(tcYt+, cY);left = IsCycle(tcY , t-1);if (left != t-1)/如果找到相等的余数，就结束循环Insert(cQ, j-(t-l-left), j);在字符数组s中适当位置插入符号'('if (cQj-1 = '(' && cQj = '0')/去除多余的循环节，即特殊处理可以除尽的情况cQ-j = '0：else/否则用"()”把循环节括起来cQj+1=')'cQj+2 = '0'break;/否则继续计算小数部分strcat(cY, "0");s = 0;if (Compare(cY , cR) < 0)cQj+ = 'O'elsewhile (Compare(cY , cR) >= 0)+s;IntSubtration(cY , cR, cY);cQj+ = s + 'O'+i;if (i = precisi on)cQj = '0'strcpy(quotie nt, cQ);void In sert(char s, int left, int right)int i;for (i=right; i>left; i-) /把数组元素后移，为插入符号'('腾出位置si = si-1;sleft = '('/ 插入符号'('int lsCycle(char aMAX, i nt label)int i;for (i=0; i<label; i+)如果数组中有与当前余数相同的余数，返回该余数的返 回 当 前 余数 的 位 置if (strcmp(ai, alabel) = 0) / 位置下标return i;return label; / 否 则 标课程设计总结：总结经过两周的课程设计，使我清楚地认识到了实践的重要性，不仅可以提高我 们对数据结构的认识，提高了自己的实践能力。此次课程设计，我仍感慨颇多，我们懂得了理论与实际相结合的重要性，只 有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来， 应用中得 到经验，才能真正掌握知识。在设计的过程中遇到许许多多问题，同时在设计的 过程中发现了自己的不足之处，对一些前面学过的知识理解得不够深刻， 掌握得 不够牢固，在使用高精度算法时，加减还好些，乘除就比较困难了。有写步骤需 要看参考书才能明白。这次课设，我的题目并不是很难，但我也绞尽脑汁，书都快泛滥了，我也深 刻的认识到自己的不足，好多东西都是一知半解，知识掌握的不全面，不扎实。 为今后的学习敲响警钟。总之，这次课设为我们提供了与众不同的学习方法，在书本中面对现实，为 我们将来在社会上立足提供了良好的前提。