《数据结构课程设计大数相乘与多项式相乘》由会员分享，可在线阅读，更多相关《数据结构课程设计大数相乘与多项式相乘（17页珍藏版）》请在金锄头文库上搜索。
1、目录1、问题描述2、设计思路3、数据结构设计4、功能函数设计5、程序代码6、运行与测试7、设计心得一、大数相乘1、问题描述：输入两个相对较大的正整数，能够通过程序计算出其结果2、设计思路：首先考虑设计将两个大数按照输入顺序存入分别存入数a口同中.把这个数组中的每一位数字单独来进行乘法运算，比如我们可以 用一个数字和另外一个数组中的每一位去相乘，从而得到乘法运算中一行的数字，再将每一行数字错位相加。这就是乘法运算的过从低位 往高位依次计算，同时确定每一列的项数，确定每一位上的结果存入 数组c中.找到最高位在数组中的项ci,然后依次输出各位上的数值通过主函数来调用其它各个函数。3、数据结构设计：输
2、入阶段采用一维数组a ,b在输入阶段当大数输入时，大数a,b从高位到低位分别依次存入数组 a ,b。调用函数计算阶段采用一维数组 c在调用sum(a,b,m,n)函数 中，在计算过程中，由个位到高位依次计算各位的结果，并依次存入 数组c中。4、功能函数设计:找出每一列的所有项首先找规律，如下所示进行乘法：a0 a1 a2b0 b1 b2b2a0b2a1b2a2b1a0b1a1b1a2b0a0b0a1b0a2下标之和 01234循环时的i=4i=3i=2i=1 i =0（i的数值）即有下标之和=m+n-2-i,由此限定条件可设计循环得出每一列的所有 项。故首先解决了找出每一列所有项的问题。计算从
3、低位到高位每一位的值。显然考虑到进位的问题，故必须从低位到高位依次计算，对于每一列，第一项可以除十取余数，保留在原位，存入 c,所得商进位存入mm然后对于第二列，第一项加进位mm然后取余数存入su, 再加第二项，取余数存入c,求商存入进位mm直到该列所有项参 与运算到该列结束时，求的最终的c,和mm.依次进行后面的运算。找出反向存入结果c中的首项.因为最高位一定不为零，故可以设计程序从c399开始判断，当ci 不等于零时，即为最高项。设计主函数，依次调用如上函数。然后通过for循环5、程序代码：#include 结果在数组里顺序是反着的#include void sum(int a200,in
4、t b200,int m,int n)int mm=0;/保存进位int c400=0;/保存结果int i,j,su,tt;for(i=0;im+n;i+)su=0;for(j=0;j=n|(tt=(m-1+n-1-i-j)=0;i-)if(ci!=0)tt=i;break;else continue;for(i=tt;i=0;i-)/ printf(%d,ci);printf(n);void main()int i,m,n,c;int a200=0,b200=0;printf(*n);printf( 请输入第一个数字：n);for(i=0;(c=getchar()!=n;i+)ai=c-4
5、8;m=i;printf(n*n);printf( 请输入第二个数字：n);for(i=0;(c=getchar()!=n;i+)bi=c-48;n=i;/m,n为数字长度sum(a,b,m,n);6运行与测试:F C:USERSLJU_K XDESKTOP新建文件夹1吠数相乘bu手大数相燕exe,倩葡又重二不断三i1234S985347598542请输入第二个数字，髓果是：&777053267319807363J7875383437838Pi*ess wny Kev to concinueb7、设计心得:根据数字相乘原理，编程实现了大数相乘，虽然过程中出现了许多问题但经过与同学讨论后都顺利解
6、决。二、多项式相乘1、问题描述：能够按照指数降序排列建立多项式，能够完成两个多项式的相乘， 并将结果输出。2、设计思路：这个程序的关键是多项式的创建和排列，以及相乘时相同指数的系数 相加。由于多项式拥有指数和系数（假设基数已定），所以可以定义 一个包含指数系数的结构体，用单链表存储多项式的数据，所以结构 体包含next指针。数据插入时比较两数的指数，按照降序排序，从 表头的next开始，直至找到合适的位置，然后开始链表中数值的插 入，如果相等则直接将指数相加，如果大于就将新数据插入到当前指 向的前面，否则将新数据插入到最后。输入完数据后相乘，多项式运 算时要循环遍历整个多项式，多项式的每一组数
7、据都要和另一个多项 式整组数据相乘，直到两个多项式都遍历完结束。3、数据结构设计：对已排序且合并了同指数项的两个多项式实现乘法操作，并输出 结果；结果多项式要求以动态链表为存储结构，复用原多项式的结点空 间；输出结果多项式要求按指数升序排列，同指数的多项要合并，项 数的正负号要求显示合理。4、功能函数设计（见源代码）5、程序代码：#include #include #define TRUE 1#define FALSE 0#define N sizeof(struct quantic) /跳转页面 void welcome。printf(n*n);/创建多项式结构体struct quantic
8、int xishu;int mi;struct quantic *next;/得到一元变量char getx(void)char x;printf(n 请输入一元变量：);scanf(%c, &x);return x;/创建多项式链表struct quantic *input(void)struct quantic *p1, *p2, *head;head = p2 = (struct quantic *)malloc(N);printf(n请输入：系数 幕值(系数输入0结束)。n);p1 = (struct quantic *)malloc(N);scanf(%d %d, &p1 - xis
9、hu, &p1 - mi);while(p1 - xishu != 0)p2 - next = p1;p2 = pl；pl = (struct quantic *)malloc(N);scanf(%d %d, &p1 - xishu, &p1 - mi);p2 - next = NULL;free(p1);return head;/查找void find(char x, struct quantic *p)struct quantic *p1;int m, n, i = 0;p1 = p;printf(1.按系数查找。n);printf(2.按指数查找。n);printf(0. 退出查找。n)
10、;scanf(%d, &m);switch(m)case 1:printf(请输入索引关键字:);scanf(%d, &n);p1 = p1 - next;while(p1 != NULL)if(p1 - xishu = n)printf(%d%c(%d) , p1 - xishu, x, p1 - mi); i +;p1 = p1 -next;if(i = 0)printf(查无此数据。n);printf(n);find(x, p);break;case 2:printf(请输入索引关键字：)；scanf(%d, &n);pl = pl - next;while(p1 != NULL)if(
11、p1 - mi = n)printf(%d%c(%d) , p1 - xishu, x, p1 - mi); i +;p1 = p1 -next;if(i = 0)printf(查无此数据。n);printf(n);find(x, p);break;case 0:welcome。；/多项式相乘struct quantic *MulExp(struct quantic *exp1,struct quantic *exp2)struct quantic *head,*p1,*q,*p2,*last,pre,*p;int flag=TRUE;head=p1=*exp1;/ p1=p1-next;fo
12、r(;p1-next != NULL;p1=p1-next);p=last=p1;p1=(*exp1)-next;while(p1 != p-next)pre = *p1;flag=TRUE;p2=(*exp2)-next;while(p2)if(flag=TRUE)p1-xishu=p1-xishu*p2-xishu;p1-mi=p1-mi+p2-mi; p2=p2-next;flag=FALSE;elseq=(struct quantic *)malloc(N); q-xishu=pre.xishu*p2-xishu; q-mi=pre.mi+p2-mi;last-next=q; last=q;p2=p2-next;p1=p1-next; last-next=NULL;return head;/排序多项式struct quantic *sort(struct quantic *pol)struct quantic *head = pol;struct quantic *
