大整数课程设计报告

中国矿业大学银川学院数据结构课程设计报告（2011/2012学年第二学期）题目名称《大整数代数运算》系部机电动力与信息工程系专业计算机科学与技术班级10级计算机（一）班学生牛建强102100510054学生王雪琴120100510004学生李自丹120100510005完成时间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引言大整数运算在科学计算中有着很重要的位置，所谓的大整数运算,是指参与运算的数(加数,减数,因子等）范围大大超出了标准数据类型（整型，实型）能表示的范围的运算。高精度运算主要解决以下三个问题：一、加数、减数、运算结果的输入和存储运算因子超出了整型、实型能表示的范围，肯定不能直接用一个数的形式来表示。在Pascal中，能表示多个数的数据类型有两种：数组和字符串。二、运算过程（1）运算顺序：两个数靠右对齐；从低位向高位运算；先计算低位再计算高位；（2）运算规则：同一位的两个数相加再加上从低位来的进位，成为该位的和；这个和去掉向高位的进位就成为该位的值；如上例：3+8+1=12，向前一位进1，本位的值是2；可借助MOD、DIV运算完成这一步；（3）最后一位的进位：如果完成两个数的相加后，进位位值不为0，则应添加一位；（4）如果两个加数位数不一样多，则按位数多的一个进行计算；三、结果的输出按运算结果的实际位数输出四、优化：以上的方法的有明显的缺点：（1）浪费空间：一个整型变量（-32768~32767）只存放一位（0~9）；（2）浪费时间：一次加减只处理一位；需求分析1.1问题描述C/C++语言中的int类型能表示的整数范围是−231~231−1，unsignedint类型能表示的整数范围是0~231−1，即0~4294967295，所以，int和unsignedint类型都不能存储超过10位的整数。有些问题需要处理的整数远远不止10位，这种大整数用C/C++语言的基本数据类型无法直接表示。请编写算法完成两个大整数的加、减、乘和除等基本的代数运算。1.2基本要求1.大整数的长度在100位以下；2.设计存储结构表示大整数；3.设计算法实现两个大整数的加、减、乘、除等基本的代数运算；4.分析算法的时间复杂度和空间复杂度；1.3输入输出1、输入的形式和输入值的范围：因为使用的#DefineMN100声明语句定义的数组，所以程序中的数组均为100位的数组，所以输入输出的字符范围为100位；2、输出的形式：输入的形式为数字，但是中间存在字符转换，本程序输出的形式为字符型；3、程序所能达到的功能：本程序最终能达到：100位以内的两个大整数的加法、减法、乘法和除法等基本的代数运算，并能输出最终的结果；1.4小组分工程序代码部分：由于能力与时间的限制，我小组代码由牛建强负责,程序的算法由王雪琴和李自丹负责，程序整体框架小组讨论得出。报告部分：王雪琴和李自丹负责需求分析、概要设计以及总结心得部分，牛建强负责详细设计以及调试与测试部分并负责整理和打印报告。概要设计2.1设计思路主要采取三大模块：储存、判断、算法、主程序数组：实现数据元素的存储、进位等；算法：实现对数据元素的对比、运算等；主程序：结合数组和算法，通过指针等实现对数组内数据的运算和调用；2.2数据结构设计1、大整数的代数运算模块：用数组存储大整数，用字符串读入数据，即比较大的整型数组，数组元素代表大整数的一位。通过数组元素的运算模拟大整数的运算。根据计算的方便性，决定将大整数由低位到高位还是高位到低位存储到数组中，例如：乘法是由低位到高位进行运算并且可能要想高位产生进位，所以应该由低位到高位进行存储，如果从键盘输入大整数，一般用字符数组存储，这样无需对大整数进行分段输入，当然，输入到字符数组后，需要将字符转化成数字。2、主程序模块(1)声明数组变量(2)输出提示信息(3)输出提示信息(4)按要求输入数字(5)调用相应模块(6)输出结果2.3各模块之间的调用关系:本程序主要包括以下模块：(1)主函数main()(2)加法运算(3)乘法运算(4)减法运算(5)除法运算(6)进位运算(7)借位运算(8)补零运算(9)去零运算(10)按位反向存储(11)复制字符串详细设计3.1数组初始化1、用宏模块的#DefineMN100声明所使用的MN字符串数组长度大小为100，这样的使用会在后来的程序编写中使程序的编译更加的简单，减少了工作量而且能提高程序的工作效率，在本程序数组中只需要使用例如：Chara[MN]定义即可定义一个名字为a的大小为100的字符串数组；2、在数组的存储上面使用的是字符数组，这样的好处是节省内存空间，因为字符在内存中占用1位，而int型数字在内存中占2位，但是由于是空间的压缩，在电脑中根据空间换时间的道理，由于不是数字的存储，所以在存储上需要将数组的存储的数据进行倒叙的排列和转换，这就导致了运行的时候程序的运行效率会降低，但是编程的难易程度也会随之降低，在程序中使用的数组均为字符型数组，而且用的是指针指向和下标的指向方法。3、在程序中，变量的初始值大部分为空，由于软件的设计需求上面的不要求浮点求值，所以软件中除了数组以外的类型均为int整型变量。3.2算法1、总体的设计思路由于高精度的运算数字的位数较大，不能使用int或longint型变量进行运算，所以需要把所输入的数字进行拆分，然后按照一定的顺序存入数组。运算时按照低位到高位的运算顺序进行运算，但是这就需要将字符数组转换成整型数组，若存在进位，则把进位直接存入数组然后进行调用。2、字符顺序交换输入的字符是按照高位在前地位在后输入的，但是本程序的计算顺序是由低向高进行的，所以需要进行字符串内的字符交换，这个交换用的是数组下标指向完成的，这样的好处是方法简单，运行效率高。代码如下所示：intreserve(char*str){intlen=strlen(str);inti;charc;for(i=0;ilen/2;i++){c=str[i];str[i]=str[len-i-1];str[len-i-1]=c;}}3、对比输入的数字位数上可能存在不同，所以需要进行预先的判断以及预先的简单处理，如果两个字符串不一样长，返回长度的差别，如果两个字符串一样长，返回第一个不一样的字符之差，完全相同返回“0”。代码如下所示：intnumcomp(char*a,char*b){intla=strlen(a);intlb=strlen(b);if(la!=lb){return(la-lb);}else{for(lb=0;lbla;lb++){if(a[lb]-b[lb]){return(a[lb]-b[lb]);}}}return0;}4、补位由于运算中可能出现两个数组的有效运算数字位数不同，这种情况的发生，一般的情况是在有效数字前面补零。代码如下所示：intbuwei(char*num,intn){intlen=strlen(num);inti,j;if(lenn){for(i=0;i=len;i++){intt1=n-i+1;intt2=len-i;num[n-i]=num[len-i];}for(i=0;in-len;i++){num[i]='0';}}}4、进位基本的代数运算牵扯到两个数的加减乘除，所以需要进位，进位数组使用数组下标和指针，将大于‘9’的字符串转换为‘0’至‘9’的字符，并且进位‘1’。代码如下所示：intjinwei(char*num){intlen=strlen(num);reserve(num);inti;for(i=0;ilen;i++){if(num[i]'9'){num[i+1]+=(num[i]-'0')/10;num[i]=(n