数据结构课程设计大数相乘与多项式相乘.docVIP

目录 问题描述………………………………………………… 设计思路………………………………………………… 数据结构设计…………………………………………… 功能函数设计…………………………………………… 程序代码………………………………………………… 运行与测试……………………………………………… 设计心得………………………………………………… 一、大数相乘 1、问题描述： 1输入两个相对较大的正整数，能够通过程序计算出其结果 2、设计思路： 1首先考虑设计将两个大数按照输入顺序存入分别存入数a[ ],b[ ]中. 2把这个数组中的每一位数字单独来进行乘法运算，比如我们可以用一个数字和另外一个数组中的每一位去相乘，从而得到乘法运算中一行的数字，再将每一行数字错位相加。这就是乘法运算的过从低位往高位依次计算，同时确定每一列的项数，确定每一位上的结果存入数组c[ ]中. 3找到最高位在数组中的项c[i],然后依次输出各位上的数值 4通过主函数来调用其它各个函数。 3、数据结构设计： 1输入阶段采用一维数组a[ ],b[ ]在输入阶段当大数输入时， 大数a,b从高位到低位分别依次存入数组a[ ],b[ ]。 2调用函数计算阶段采用一维数组c[ ]在调用sum(a,b,m,n)函数中，在计算过程中，由个位到高位依次计算各位的结果，并依次存入数组c[ ]中。 4、功能函数设计： 1找出每一列的所有项 首先找规律，如下所示 进行乘法: a[0] a[1] a[2] b[0] b[1] b[2] b[2]a[0] b[2]a[1] b[2]a[2] b[1]a[0] b[1]a[1] b[1]a[2] b[0]a[0] b[0]a[1] b[0]a[2] 下标之和 0 1 2 3 4 i=4 i=3 i=2 i=1 i =0(循环时的i的数值) 即有 下标之和=m+n-2-i,由此限定条件可设计循环得出每一列的所有项。 故首先解决了找出每一列所有项的问题。 2计算从低位到高位每一位的值。 显然考虑到进位的问题，故必须从低位到高位依次计算，对于每一列 ，第一项可以除十取余数，保留在原位，存入c[ ] ，所得商进位存入mm。然后对于第二列，第一项加进位mm，然后取余数存入su,再加第二项，取余数存入c[ ],求商存入进位mm，直到该列所有项参与运算到该列结束时，求的最终的c[ ],和mm. 依次进行后面的运算。 3找出反向存入结果c[ ]中的首项. 因为最高位一定不为零，故可以设计程序从c[399]开始判断，当c[i]不等于零时，即为最高项。 4设计主函数，依次调用如上函数。然后通过for循环 5、程序代码： #include stdio.h #include math.h void sum(int a[200],int b[200],int m,int n)//结果在数组里顺序是反着的 { int mm=0;//保存进位 int c[400]={0};//保存结果 int i,j,su,tt; for(i=0;im+n;i++) { su=0; for(j=0;jm;j++) { if((tt=(m-1+n-1-i-j))=n||(tt=(m-1+n-1-i-j))0) continue; else su=su+a[j]*b[m-1+n-1-i-j]; } su=su+mm; c[i]=su%10; mm=su/10; } printf(\n***************************\n); printf(结果是：\n); for(i=399;i=0;i--)//找首位 { if(c[i]!=0) { tt=i;break; } else continue; } for(i=tt;i=0;i--)//输出 printf(%d,c[i]); printf(\n); } void main() { int i,m,n,c; int a[200]={0},b[200]={0}; printf(***************************\n); printf(请输入第一个数字：\n); for(i=0;(c=getchar())!=\n;i++) a[i]=c-48; m=i; printf(\n***************************\n); printf(请输入第二个数字：\n); for(i=0;(c=