大整数课程设计报告

1、中国矿业大学银川学院数据结构课程设计报告（2011/2012学年第二学期）题目名称 大整数代数运算 系 部 机电动力与信息工程系 专 业 计算机科学与技术 班 级 10级计算机（一）班 学 生 牛建强 4 学 生 王雪琴 4 学 生 李自丹 5 完成时间 2011年 6 月 指导老师 王居平 目 录引言31.1问题描述41.2基本要求41.3输入输出41.4小组分工4概要设计42.1设计思路42.2数据结构设计52.3各模块之间的调用关系:5详细设计53.1 数组初始化53.2 算法63.3 主程序15调试与测试17总结心得17附录：源程序清单及运行结果19参考文献30引言 大整数运算在科学计

2、算中有着很重要的位置，所谓的大整数运算,是指参与运算的数(加数,减数,因子等）范围大大超出了标准数据类型（整型，实型）能表示的范围的运算。高精度运算主要解决以下三个问题：一、加数、减数、运算结果的输入和存储运算因子超出了整型、实型能表示的范围，肯定不能直接用一个数的形式来表示。在Pascal中，能表示多个数的数据类型有两种：数组和字符串。二、运算过程（1）运算顺序：两个数靠右对齐；从低位向高位运算；先计算低位再计算高位；（2）运算规则：同一位的两个数相加再加上从低位来的进位，成为该位的和；这个和去掉向高位的进位就成为该位的值；如上例：3+8+1=12，向前一位进1，本位的值是2；可借助MOD、

3、DIV运算完成这一步；（3）最后一位的进位：如果完成两个数的相加后，进位位值不为0，则应添加一位；（4）如果两个加数位数不一样多，则按位数多的一个进行计算；三、结果的输出按运算结果的实际位数输出四、优化：以上的方法的有明显的缺点：（1）浪费空间：一个整型变量（-3276832767）只存放一位（09）；（2）浪费时间：一次加减只处理一位；需求分析1.1问题描述C/C+语言中的int类型能表示的整数范围是-231231-1，unsigned int类型能表示的整数范围是0231-1，即04 294 967 295，所以，int 和unsigned int类型都不能存储超过10位的整数。有些问题需

4、要处理的整数远远不止10 位，这种大整数用C/C+语言的基本数据类型无法直接表示。请编写算法完成两个大整数的加、减、乘和除等基本的代数运算。1.2基本要求1. 大整数的长度在100位以下；2. 设计存储结构表示大整数；3. 设计算法实现两个大整数的加、减、乘、除等基本的代数运算；4. 分析算法的时间复杂度和空间复杂度；1.3输入输出1、输入的形式和输入值的范围：因为使用的#Define MN 100声明语句定义的数组，所以程序中的数组均为100位的数组，所以输入输出的字符范围为100位；2、输出的形式：输入的形式为数字，但是中间存在字符转换，本程序输出的形式为字符型；3、程序所能达到的功能：本

5、程序最终能达到：100位以内的两个大整数的加法、减法、乘法和除法等基本的代数运算，并能输出最终的结果；1.4小组分工程序代码部分：由于能力与时间的限制，我小组代码由牛建强负责,程序的算法由王雪琴和李自丹负责，程序整体框架小组讨论得出。报告部分：王雪琴和李自丹负责需求分析、概要设计以及总结心得部分，牛建强负责详细设计以及调试与测试部分并负责整理和打印报告。概要设计2.1设计思路主要采取三大模块：储存、判断、算法、主程序数组：实现数据元素的存储、进位等；算法：实现对数据元素的对比、运算等； 主程序：结合数组和算法，通过指针等实现对数组内数据的运算和调用；2.2数据结构设计1、大整数的代数运算模块：

6、用数组存储大整数，用字符串读入数据，即比较大的整型数组，数组元素代表大整数的一位。通过数组元素的运算模拟大整数的运算。根据计算的方便性，决定将大整数由低位到高位还是高位到低位存储到数组中，例如：乘法是由低位到高位进行运算并且可能要想高位产生进位，所以应该由低位到高位进行存储，如果从键盘输入大整数，一般用字符数组存储，这样无需对大整数进行分段输入，当然，输入到字符数组后，需要将字符转化成数字。2、主程序模块(1) 声明数组变量(2) 输出提示信息(3) 输出提示信息(4) 按要求输入数字(5) 调用相应模块(6) 输出结果2.3各模块之间的调用关系:本程序主要包括以下模块：(1)主函数main(

7、)(2)加法运算(3)乘法运算(4)减法运算(5)除法运算(6)进位运算(7)借位运算(8)补零运算(9)去零运算(10)按位反向存储(11)复制字符串详细设计 3.1 数组初始化1、用宏模块的#Define MN 100声明所使用的MN字符串数组长度大小为100，这样的使用会在后来的程序编写中使程序的编译更加的简单，减少了工作量而且能提高程序的工作效率，在本程序数组中只需要使用 例如：Char a MN定义即可定义一个名字为a的大小为100的字符串数组；2、在数组的存储上面使用的是字符数组，这样的好处是节省内存空间，因为字符在内存中占用1位，而int型数字在内存中占2位，但是由于是空间的压缩

8、，在电脑中根据空间换时间的道理，由于不是数字的存储，所以在存储上需要将数组的存储的数据进行倒叙的排列和转换，这就导致了运行的时候程序的运行效率会降低，但是编程的难易程度也会随之降低，在程序中使用的数组均为字符型数组，而且用的是指针指向和下标的指向方法。3、在程序中，变量的初始值大部分为空，由于软件的设计需求上面的不要求浮点求值，所以软件中除了数组以外的类型均为int整型变量。3.2 算法1、总体的设计思路由于高精度的运算数字的位数较大，不能使用int或long int型变量进行运算，所以需要把所输入的数字进行拆分，然后按照一定的顺序存入数组。运算时按照低位到高位的运算顺序进行运算，但是这就需要

9、将字符数组转换成整型数组，若存在进位，则把进位直接存入数组然后进行调用。2、字符顺序交换输入的字符是按照高位在前地位在后输入的，但是本程序的计算顺序是由低向高进行的，所以需要进行字符串内的字符交换，这个交换用的是数组下标指向完成的，这样的好处是方法简单，运行效率高。代码如下所示：int reserve(char *str)int len=strlen(str);int i;char c;for (i=0;ilen/2;i+)c=stri;stri=strlen-i-1;strlen-i-1=c;3、对比输入的数字位数上可能存在不同，所以需要进行预先的判断以及预先的简单处理，如果两个字符串不一样

10、长，返回长度的差别，如果两个字符串一样长，返回第一个不一样的字符之差，完全相同返回“0”。代码如下所示：int numcomp(char *a,char *b)int la=strlen(a);int lb=strlen(b);if (la!=lb)return (la-lb);else for (lb=0;lbla;lb+)if (alb-blb)return (alb-blb);return 0;4、补位由于运算中可能出现两个数组的有效运算数字位数不同，这种情况的发生，一般的情况是在有效数字前面补零。代码如下所示：int buwei(char *num,int n)int len=strl

11、en(num);int i,j;if (lenn)for (i=0;i=len;i+)int t1=n-i+1;int t2=len-i;numn-i=numlen-i;for (i=0;in-len;i+)numi=0;4、进位基本的代数运算牵扯到两个数的加减乘除，所以需要进位，进位数组使用数组下标和指针，将大于9的字符串转换为0至9的字符，并且进位1。代码如下所示：int jinwei(char * num)int len=strlen(num);reserve(num);int i;for (i=0;i9)numi+1+=(numi-0)/10;numi=(numi-0)%10+0;if

12、 (numlen)numlen+=0;numlen+1=0;reserve(num);if (num09)jinwei(num);return len;5、借位计算数组在低位不够计算的时候需要进行借位计算的方法，以保证每个字符都是大于0的。代码如下所示：int jiewei(char *num)int len=strlen(num);while (len-)if (numlen0)numlen+=10;numlen-1-;6、除零运算在计算不同位数两组数字代数运算的时候需要将两组数字数位少的一组前面补零，但是输出的时候需要将符串中多余的0字符去掉代码如下所示：int quling (char

13、* num)int i,j;int len=strlen(num);for (i=0;ilen;i+)if (numi=0)if (i=(len-1)strcpy(num,0);return 0;continue;for (j=0;i0)subla-=0;for (i=lb-1;i=0;i-)if (ai+lab=bi)subla-=ai+lab-bi+0; else subla-=10+0-bi+ai+lab;ai+lab-1-;for (i=0;ilab;i+)subi=ai;jiewei(sub);quling (sub);10、除法除法运算的方式类似于乘法，但是不同的是将加法换成了加法

14、利用循环体进行减法运算，大数除法进行分解，然后利用numsdiv函数再转换为减法进行最终计算最后得到整数部分和余数部分。代码如下所示：int numsdiv(char *a,char *b,char *div,char *remain)if (numcomp(a,b)=0)count+;strcpy(t,a);numsub(t,b,a);strcpy(remain,a);div0=count;div1=0;int numdiv(char *a,char *b,char *div,char * remain)int comp=numcomp(a,b);if (comp=0)strcpy(div,

15、1);strcpy(remain,0);return 1;else if (comp0)strcpy(div,0);strcpy(remain,b);return 2;else strcpy(div,);int count;int lb=strlen(b);int la=strlen(a);int lab=la-lb;char tMN;char t23;char t3MN;int i;for (i=0;i=0)numsdiv(t,b,t2,t3);strcat(div,t2);buwei(t3,lb);strcpy3(a+i,t3,lb);if (i0)ai-1=0;elsestrcat(di

16、v,0);quling(a);strcpy(remain,a);quling(div);3.3 主程序通过调用之前的变量而直接控制和链接输入输出。代码如下所示：int printjieshao()cout本程序可进行大整数的四则运算。但运算不包含负数。n; cout即只能大数减小数，大数除以小数，除法可求出商和余数n;cout输入两个数，大数在前，小数在后，输出分四行，分别为和差积商。n; cout请按要求输入正确的数字:;int main ()int n;int i,j;char aMN;char bMN;char cMN;char dMN;char t1MN;char t2MN;print

17、jieshao();while (1)scanf (%s%s,a,b);if (numcomp(a,b)0)printf (n必须大数在前，小数在后。请重新输入！n);else break;strcpy(t1,a);strcpy(t2,b);numadd(t1,t2,c);cout%s+%s=%snn,a,b,c; strcpy(t1,a);strcpy(t2,b);numsub(t1,t2,c);cout%s-%s=%snn,a,b,c;strcpy(t1,a);strcpy(t2,b);nummul(t1,t2,c);cout%s*%s=%snn,a,b,c; strcpy(t1,a);s

18、trcpy(t2,b);numdiv(t1,t2,c,d);cout%s%s=%s-%snn,a,b,c,d; return 0;调试与测试调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析：遇到的问题：（1）算法问题首先是对实现大整数的代数运算时应当如何实现遇到了困难，具体解析见解题思路。（2）数组的存储问题然后是对数据存储和转换问题的解决，即数字被输入进内存后应当怎样储存，怎样的转化格式去运算，这个问题最初参考过使用栈的方式但是事实证明只需要在最后转换格式就行了。总结心得经我团队经过数天的共同努力，完成了数据结构中的一道经典例题“大整数的代数运算”（也可叫高精度代数运算），解

19、决问题的过程是艰难的，但是通过解决问题，我们发现了自己在计算机方面动手能力不足的问题，这次课程设计同时也是对自己编程和算法的检验，很庆幸的是我们可以顺利的完成，我们的成功也离不开老师和同学们的帮助，在这里我代表团队感谢这期间给我们帮助的人。巩固书本上的知识，对书上的知识能更透彻地了解。通过自己设计程序积累调试数据结构经验，培养了我们编程能力。巩固我们所学的数据结构知识，消化课堂所讲解的内容。对所学课程及其知识的一种整理，将原本在我们脑中比较混乱的课程设计重新梳理。通过课程设计我们更好的掌握了大整数代数运算的整体思路，这也为今后学习结构和算法提供了宝贵的经验，同时也成了此类问题的解决模式样板。相

20、对于以前，我们能够独立的完成简单的程序设计以及完成一份较为满意的程序设计报告。通过这次课程设计，达到了我们增强巩固数据结构知识的目的，使知识全面化，系统化。数据结构在计算机学科的学习中，是一门比较重要的环节，这次的巩固与加深提高了我们的实际工作能力，培养科学作风，为学习后续课程和今后系统开发奠定基础。课程设计更注重的是综合训练，做到学以致用。培养了分析问题与解决问题的能力。一个星期前的茫然，现在已经烟消云散了。回顾过去一段时间里，我们小组整天通过查资料，在了解了“大整数代数运算”的核心思想后，经过团队的分析和思考，一天时间我们就得到了整体的框架和细节方面的思路，而后经过数天的努力，我们团队终于

21、完成了“大整数代数运算”这个问题的课程设计，这次课程设计是踏入程序世界的第一步，对于本次课程设计，我们学到了一个道理“学计算机，理论是一部分，但是更重要的是实践，只有实践才能检验我们所学的理论，才能去应用。”附录：源程序清单及运行结果 下面的是本程序的完整代码和运行代码的截图#define MN 100#include #include using namespace std;int reserve(char *str)int len=strlen(str);int i;char c;for (i=0;ilen/2;i+)c=stri;stri=strlen-i-1;strlen-i-1=c;

22、int numcomp(char *a,char *b)int la=strlen(a);int lb=strlen(b);if (la!=lb)return (la-lb);else for (lb=0;lbla;lb+)if (alb-blb)return (alb-blb);return 0;int jinwei(char * num)int len=strlen(num);reserve(num);int i;for (i=0;i9)numi+1+=(numi-0)/10;numi=(numi-0)%10+0;if (numlen)numlen+=0;numlen+1=0;reserv

23、e(num);if (num09)jinwei(num);return len;int jiewei(char *num)int len=strlen(num);while (len-)if (numlen0)numlen+=10;numlen-1-;int quling (char * num)int i,j;int len=strlen(num);for (i=0;ilen;i+)if (numi=0)if (i=(len-1)strcpy(num,0);return 0;continue;for (j=0;i0)subla-=0;for (i=lb-1;i=0;i-)if (ai+lab

24、=bi)subla-=ai+lab-bi+0;else subla-=10+0-bi+ai+lab;ai+lab-1-;for (i=0;ilab;i+)subi=ai;jiewei(sub);quling (sub);int strcpy3(char *a,char *b,int n)while (n-)an=bn;int strcpy2(char *a,char *b,int n)an=0;while (n-)an=bn;int numsdiv(char *a,char *b,char *div,char *remain)if (numcomp(a,b)=0)count+;strcpy(t

25、,a);numsub(t,b,a);strcpy(remain,a);div0=count;div1=0;int buwei(char *num,int n)int len=strlen(num);int i,j;if (lenn)for (i=0;i=len;i+)int t1=n-i+1;int t2=len-i;numn-i=numlen-i;for (i=0;in-len;i+)numi=0;int numdiv(char *a,char *b,char *div,char * remain)int comp=numcomp(a,b);if (comp=0)strcpy(div,1);strcpy(remain,0);return 1;else if (comp0)strcpy(div,0);strcpy(remain,b);return 2;else strcpy(div,);int count;int lb=strlen(b);int la=strlen(a);int lab=la-lb;char tMN;char t23;char t3MN;int i;for (i=0;i=0)numsdiv(t,b,t2,t3);strcat(div,t2);buwei(t3,lb);strcpy3(a+i,t3,lb);if (i0)ai-1=0;elsestrcat(di