题目长整数乘法

1、 题目: 长整数乘法班级:姓名:学号:完成日期:1：需求分析(1) 输入的形式和输入值的范围:用户从键盘输入2个任意长度的长整数，输入的时候是按4个为一段输入的,即一段一段输入的,求它们的乘积的大小，并将结果在屏幕上显示;2个长整数的输入没有大小的限制,要输入多大的数据,就可以输入多大的数据.(2) 输出的形式: 输出直接在屏幕上显示2个任意长度的长整数的乘积大小(3) 程序所能达到的功能: 对于用户输入的任意长度的2个的长整数,能够正确没有错误的显示结果,和电脑附件中的计算器的计算值要一致;能够准确无误地显示结果(4) 测试数据 如输入1000 1000 和1111 2个长整数后,显示011

2、1 1111 1111 1000的话,就是正确的结果形式; 如输入1111 1111 1111和1111 2个长整数后,结果显示0123 4444 4444 4322就不是正确结果,因为这2个长整数的积为0123 4444 4444 43212:概要设计 a：抽象数据类型的定义为了实现任意长整数的乘法，因为这种运算存在进位和位移等操作，因此选择双链表的结构体，它有一个data，left，right；考虑到data表示的数据的范围，使它只接受4个数字的整数，这样一个长整数就分为若干段，每一段为4个数字，便于进位和借位以及位移的操作,用户在输入时就是每次输入4个数字.b:主程序的流程 主程序是首先

3、调用初始化2个长整数的函数,用户4个数字一段一段地输入2个长整数,用双链表的形式和头插法的形式建立,返回2个长整数的头节点;建立完2个长整数后,就开始进行2个长整数的乘积的运算了;首先将第一个长整数的全部去乘第2个长整数的最后一段,这样得到一个长整数;接着将第一个长整数的全部去乘第2个长整数的倒数第2段,这样得到一个长整数,但是要向左位移4位; 这次得到的长整数要和上一次相加,得到一个新的长整数;接着接着将第一个长整数的全部去乘第2个长整数的倒数第3段,得到一个长整数,再和前面相加;依次进行,一直到已经到第一个长整数的全部乘于了第2个长整数的最高1段,那么乘法就结束了;这时将得到的长整数从高位

4、到低位一段一段,4个4个数字显示在屏幕上,程序就运行结束了.c:模块之间的层次(调用)关系 程序的调用关系如下:主函数调用了初始化2个长整数的函数,然后再调用了2个2个长整数的乘积的函数;2个长整数的乘积的函数调用了部分求和的函数和从表头得到表尾的函数,以及将一个长整数前后数值交换的函数以及显示一个长整数的函数.3详细设计 a：2个长整数的输入 接着采用头插法的方式，当输入一个 4个数字的整数时，就产生一个新的节点，它的值为输入的整数值，建立起它的左右指针，并用头节点指向它；为了判断一个长整数是否输入结束，定义一个结束标志，当输入正数时就继续，当输入负数时，就结束一个长整数的输入；同时用一个函

5、数得到长整数的尾节点和段数，段数在比较2个数的大小有用。 b：2个长整数的乘法先定义一个部分加法的函数，就是2个正的长整数的加法的运算；它从2个长整数的尾部开始，同时相加，接着再向左移一段，又同时相加；当2个数据的某一段同时存在时，就相加；当一个数据已经全部被相加后，另外一个数据的剩下的段就要全部复制到和中；在实行加法的时候，设置一个进位标志位，目的是为了使结果正确；当一 段的数据相加产生进位时，那么进位标志位为1；下一次一 段的数据相加就要加上这个进位标志位；而且如果2个长整数的所有的段的数据都相加完了，还要判断是否产生了进位标志位，如果有的话，就要新建一个节点，它的值就是1；2个正的长整数

6、的求和就完成了。再定义一个部分乘法的函数，就是1个正的长整数乘于一个4位整数，并向左位移特定的段数的运算；其实开始实现向左位移的运算，只需要建立新的节点，节点的数目为需要左移段数，并将这些节点的值设置为0；接着实现一个长整数乘于一个4位整数的运算，采用每一段都和这个4位整数的相乘的方法，当积超过10000时，那么多于高4位全为进位，参与下一次相乘时要加上它；低4位就是要新建的节点的值；和加法一样，当这个正的长整数的每一段都和这个4位整数相乘后，但还存在进位时，就要新建一个节点，它的值就是进位值；现在1个正的长整数乘于一个4位整数，并向左位移特定的段数的运算就完成了；再实现2个正的长整数的乘法的

7、运算，采用第一个长整数作为一个整体乘于第二个长整数的每一段，并向左位移的方法；例如当采用第一个长整数作为一个整体乘于第二个长整数的最后一段，就不用向左位移；但是第一个长整数作为一个整体乘于第二个长整数的倒数第二段，就用向左位移一段，就是最后一段为0，依次类推；此过程是调用部分乘法的函数实现的；我们只需要定义2个长整数的临时变量，1个是本次新产生的部分乘法的结果，1个是上次的总和；那么总和加上本次新产生的部分乘法的结果重新给总和，此操作是调用2个长整数的加法实现的；第2个数的段一直向左位移，总和也就不断扩大，当第2个数的段达到最高一段时，就完成了2个正的长整数的乘法的运算。f：补充说明 在程序中

8、，因为我们需要得到一个长整数的头部和尾部，因此定义了2个函数，一个是已知一个一长整数的头部，得到它的尾部；一个是已知一个一长整数的尾部，得到它的头部；具体实现都是利用指针的左移和右移，为空时就得到头部或尾部；在程序中，我们输入是从高位到低位输入的，而相加后的顺序就相反了，因此我们需要定义一个将一个长整数的数据前后交换的函数，新建一个一个长整数，使用头插法，将从原来一个长整数的尾部开始，向左移，一个一个给新建的长整数。4调试分析a调试过程中遇到的问题是如何解决 问题1:调试过程中发生内存错误的提示? 内存错误有非常大的原因是指针的滥用和它的空间的使用不规范情况,但最可能是指针还没有开辟空间,就已

9、经指向了一个实际存在的数;查找代码,果然发现,head在使用中没有开辟空间,.但后面语句有给它赋值的情况,因此添加代码head=(dnode*)malloc(sizeof(dnode);再次调试时没有发生一样的错误;问题2:结果显示的时候本应该按从高位到低位输出,结果从从低位到高位输出? 我们定义的部分和的加法是从长整数的尾部开始的，即先从小的开始加起,再加大的;但是我们还是采用的是头插法的方法,因此头节点其实是和的最小值,依次类推,那么当我们按从头到尾节点输出时,就是从低到高输出了;因此我们输出的时候可以先从头节点写一个函数得到尾节点,再从尾节点,从右到左的形式输出结果,即从尾到头的形式输出

10、结果;因此我定义了一个从头节点得到尾节点的函数,再从尾到头的形式输出结果,这次输出结果没有错误;问题3:结果显示的时候本总出现一个为-858993460的节点? 有可能是定义了一个节点, 没有被赋值,因此产生的情况; 查找代码,果然发现s=(dnode*)malloc(sizeof(dnode);p->right=s;s->left=p;缺少了s的赋值的代码,添加 s->data=inc后,运行没有错误b算法的时空分析 时间复杂度:由于2个长整数的乘法是用第一个长整数的全部乘于了第2个长整数的每一段然后想加得到的,因此它实际上就是2重循环的作用,假设2个数的段数分别为n1和n

11、2,那么算法的时间复杂度为n1和n2的乘积;空间复杂度: 空间复杂度是和2个长整数的段数成正比, 2个长整数的段数越多,那么需要开辟的空间越多,求和需要的长整数的开辟的空间也越多c经验和体会在写程序中要规范书写，这样便于检查错误的出现所在的地方；写代码要前后照应，前面的变量和函数在后面使用时可能要对应，如果不注意，可能发生错误；当出现错误时，要大胆猜测各种出错的可能的原因，一种一种排除，一种一种尝试，问题可能解决。定义了指针就需要开辟空间,否则会出错;同时指针开辟的空间单元要初始一定的值, 否则会出现不需要的数据;5用户使用说明 本程序使用简单,运行程序后出现了input the first

12、data,input negative data exit的提示,告诉用户输入第一个长整数,4个数字一段输入,要想结束输入直接输入一个负数就可以结束了;如需要输入1011 1011时;input the first data,input negative data exit10111011-1接着出现input the second data,input negative data exit的提示,告诉用户输入第2个长整数,4个数字一段输入,要想结束输入直接输入一个负数就可以结束了;如需要输入1011 1011时;input the second data,input negative dat

13、a exit10111011-10102 2325 4344 2121输入完以后,程序直接显示运行结果,按回车就退出程序.6测试结果7附录#include<stdio.h>#include<malloc.h>typedef struct linknodeint data;/*节点的值*/struct linknode *left,*right;/*左指针和右指针*/dnode;dnode *r1,*r2,*r3,*head1,*head2,*head3;dnode *head_temp,*rear_temp;/*head1为第1个数的头指针，r1为 为第1个的尾指针*/

14、*head2为第2个数的头指针，r2为 为第2个的尾指针*/*head3为结果的头指针，r3为结果的尾指针*/*head_temp为临时数的头指针，rear_temp为临时数的尾指针*/*产生一个长整数*/dnode* creat()dnode *head,*p,*s;/*head为头指针，p和s为临时指针*/int x,cycle=1;/*x为输入的数据，cycle为是否继续输入的标志*/head=(dnode*)malloc(sizeof(dnode);p=head;/*指向头*/while(cycle)scanf("%d",&x);/*输入数据*/if(x&g

15、t;=0)/*输入正数才有效*/s=(dnode*)malloc(sizeof(dnode);s->data=x;p->right=s;s->left=p;p=s;/*采用的是头插法*/else cycle=0;/*输入负数就退出*/head=head->right;/*第一个头没有用到*/head->left=NULL;p->right=NULL;return head;dnode *rear(dnode *head)/*根据一个数的头节点，得到尾节点，并得到这个数的段数*/dnode *p;p=head;while(p->right)/*向右移*/

16、 p=p->right;return p;void input_and_init()/*初始化2个数据的大小*/*符号变为对应的0或1*/printf("input the first data,input negative data exitn"); head1=creat(); /*产生第一个数，得到它的头指针*/ r1=rear(head1); /*得到第一个数的尾指针和*/*符号变为对应的0或1*/ printf("input the second data,input negative data exitn"); head2=creat(

17、); /*产生第2个数，得到它的头指针*/ r2=rear(head2); /*得到第一个数的尾指针和段数*/*打印一个数*/void print(int data)if(data>=1000)/*含有4个数字*/ printf("%d",data);else if(data>=100)/*含有3个数字，补1个零*/ printf("0%d",data);else if(data>=10)/*含有2个数字，补2个零*/ printf("00%d",data);else/*含有1个数字，补3个零*/ printf(&q

18、uot;000%d",data);/*显示一个结果的长整数，从后向前移*/void display(dnode *rear)dnode *p; p=rear;while(p)print(p->data); printf(" "); p=p->left; /*向左移*/printf("n");dnode *find_sum2(dnode *r1,dnode *r2)/*得到2个正数的和*/dnode *head,*p,*s,*p1,*p2;/*head为头指针，p,s为临时指针，p1指向第1个数并向左移动，p2指向第2个数并并向左移动

19、*/ int inc=0,sum=0,f1=0,f2=0;/*inc为进位，sum为和，f1为第一个数是否结束，f2为第一个数是否结束*/head=(dnode*)malloc(sizeof(dnode);p=head;/*开辟空间*/p1=r1;/*指向第一个数的尾*/p2=r2;/*指向第二个数的尾*/while(p1!=NULL&&p2!=NULL)/*2个数的某一段都不为空时 */sum=p1->data+p2->data+inc;/*和为2个数之和加进位*/inc=0;/* 进位回0*/if(sum>=10000)/*当超过2位数的大小时，和减去10

20、000，并进位*/sum=sum-10000;inc=1;/*用头插法建立一个新的节点*/s=(dnode*)malloc(sizeof(dnode);s->data=sum;p->right=s;s->left=p;p=s;/*2个数都向左移*/p1=p1->left;p2=p2->left;if(p1=NULL&&p2=NULL)if(inc=1)/*当2个数据都完了，但是存在进位时，新建一个节点，值就是进位*/s=(dnode*)malloc(sizeof(dnode); s->data=1;p->right=s;s->le

21、ft=p;p=s;while(p1!=NULL)/*当第2个数空，第1个数不为空时，将第一个数剩下的全用新节点产生*/f1=1;s=(dnode*)malloc(sizeof(dnode);sum=p1->data+inc;inc=0;if(sum>=10000)sum=sum-10000;inc=1;s->data=sum;p->right=s;s->left=p;p=s;/*第1个数都向左移*/p1=p1->left;/*当第1个数据完了，但是存在进位时，新建一个节点，值就是进位*/if(f1=1&&inc=1&&!p1)

22、s=(dnode*)malloc(sizeof(dnode);s->data=1;p->right=s;s->left=p;p=s;/*当第1个数空，第2个数不为空时，将第一个数剩下的全用新节点产生*/while(p2!=NULL)f2=1;s=(dnode*)malloc(sizeof(dnode);sum=p2->data+inc;inc=0;if(sum>=10000)sum=sum-10000;inc=1;s->data=sum;p->right=s;s->left=p;p=s;p2=p2->left;/*第2个数都向左移*/*当第

23、2个数据完了，但是存在进位时，新建一个节点，值就是进位*/if(f2=1&&inc=1)s=(dnode*)malloc(sizeof(dnode);s->data=1;p->right=s;s->left=p;p=s;head=head->right;head->left=NULL;p->right=NULL;return head;/*返回头节点*/dnode * find_sub_mult(dnode * r1,int data ,int i)/*将r1指向的数全乘于data，并向左位移i段*/dnode *head,*p,*s,*rr

24、;/*head为头指针，p,s为临时指针，rr为尾指针*/int k,inc=0;/*k为循环用的，inc为进位*/long sum=0; /*求和*/rr=r1;head=(dnode*)malloc(sizeof(dnode);p=head;/*开辟空间*/*先将需要位移的段数全用0补齐*/if(i!=0)for(k=1;k<=i;k+)s=(dnode*)malloc(sizeof(dnode);s->data=0;p->right=s;s->left=p;p=s;while(rr!=NULL)/* 当rr没有到头时*/s=(dnode*)malloc(sizeo

25、f(dnode);sum=rr->data*data+inc;if(sum>10000)inc=sum/10000;/*得到和的高4位*/s->data=sum-inc*10000;/*值为低4位的值*/ elses->data=sum;/*直接给值*/inc=0;p->right=s;s->left=p;p=s;/*左移*/rr=rr->left;if(inc!=0)/*如果还有进位，就需要新建一个节点*/s=(dnode*)malloc(sizeof(dnode);s->data=inc;p->right=s;s->left=p;

26、p=s;head=head->right;head->left=NULL;p->right=NULL;/*返回头指针*/return head;/*由一个数的尾指针得到头指针*/dnode * return_head(dnode *rear)dnode *p;p=rear;while(p->left)p=p->left;return p;/*由一个数的头指针得到尾指针*/dnode * return_rear(dnode *head)dnode *p;p=head;while(p->right)p=p->right;return p;/*将一个数的数据前后交换*/dnode * tansfer_rear2(dnode *rear_temp)dnode *h