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

1、目录1、 问题描述2、 设计思路3、 数据结构设计4、 功能函数设计5、 程序代码6、 运行与测试7、 设计心得一、大数相乘1、问题描述：输入两个相对较大的正整数，能够通过程序计算出其结果2、设计思路：首先考虑设计将两个大数按照输入顺序存入分别存入数a ,b 中.把这个数组中的每一位数字单独来进行乘法运算，比如我们可以用一个数字和另外一个数组中的每一位去相乘，从而得到乘法运算中一行的数字，再将每一行数字错位相加。这就是乘法运算的过从低位往高位依次计算，同时确定每一列的项数，确定每一位上的结果存入数组c 中.找到最高位在数组中的项ci,然后依次输出各位上的数值通过主函数来调用其它各个函数。3、数

2、据结构设计：输入阶段采用一维数组a ,b 在输入阶段当大数输入时，大数a,b从高位到低位分别依次存入数组a ,b 。调用函数计算阶段采用一维数组c 在调用sum(a,b,m,n)函数中，在计算过程中，由个位到高位依次计算各位的结果，并依次存入数组c 中。4、功能函数设计：找出每一列的所有项首先找规律，如下所示 进行乘法:a0 a1 a2b0 b1 b2b2a0 b2a1 b2a2b1a0b1a1 b1a2b0a0b0a1b0a2下标之和01 2 3 4 i=4 i=3 i=2 i=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(i

4、nt a200,int 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);

5、for(i=0;(c=getchar()!=n;i+)ai=c-48;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运行与测试：7、设计心得：根据数字相乘原理，编程实现了大数相乘，虽然过程中出现了许多问题但经过与同学讨论后都顺利解决。二、多项式相乘1、问题描述：能够按照指数降序排列建立多项式，能够完成两个多项式的相乘，并将结果输出。2、设计思路：这个程序的关键是多项式的创建和排列，以及相乘时相同指数的系数相加。由于多项式拥有指数和系数（假设基数已定

6、），所以可以定义一个包含指数系数的结构体，用单链表存储多项式的数据，所以结构体包含next指针。数据插入时比较两数的指数，按照降序排序，从表头的next开始，直至找到合适的位置，然后开始链表中数值的插入，如果相等则直接将指数相加，如果大于就将新数据插入到当前指向的前面，否则将新数据插入到最后。输入完数据后相乘，多项式运算时要循环遍历整个多项式，多项式的每一组数据都要和另一个多项式整组数据相乘，直到两个多项式都遍历完结束。3、数据结构设计：对已排序且合并了同指数项的两个多项式实现乘法操作，并输出结果；结果多项式要求以动态链表为存储结构，复用原多项式的结点空间；输出结果多项式要求按指数升序排列，同

7、指数的多项要合并，项数的正负号要求显示合理。4、 功能函数设计（见源代码）5、 程序代码：#include #include #define TRUE 1#define FALSE 0#define N sizeof(struct quantic)/跳转页面void welcome()printf(n*n);/创建多项式结构体struct quanticint xishu;int mi;struct quantic *next;/得到一元变量char getx(void)char x;printf(n请输入一元变量：);scanf(%c, &x);return x;/创建多项式链表struct

8、 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 - xishu, &p1 - mi);while(p1 - xishu != 0)p2 - next = p1;p2 = p1;p1 = (struct quantic *)malloc(N);scanf(%d %d, &p1 - xishu, &p1 -

9、 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);scanf(%d, &m);switch(m)case 1:printf(请输入索引关键字:);scanf(%d, &n);p1 = p1 - next;while(p1 != NULL)if(p1 - xishu = n)printf(%d%c

10、(%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);p1 = p1 - next;while(p1 != NULL)if(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;cas

11、e 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;for(;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

12、=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

13、 quantic *p,*q;struct quantic *r,*t;if(head-next = NULL)printf(请输入有效信息。n);elsep = head-next;q = p-next;p-next = NULL;p = q;while(p!=NULL)r = head;q = r-next;while(q != NULL& q-mi mi)r = q;q = q-next; t=p-next; p-next=r-next; r-next=p; p=t;return(head);/合并多项式struct quantic *combine(struct quantic *he

14、ad)struct quantic *p1,*p2;p1 = head -next;while(p1 - next != NULL )if(p1 - next - mi = p1 - mi)p2 = p1 -next;p1 - xishu = p1 - xishu + p2 - xishu;p1 - next = p1 - next -next;free(p2);elsep1 = p1 - next;return(head);/输出多项式void output(char x, struct quantic *p)p = p - next;while(p != NULL)if(p - xishu

15、 xishu, x, p - mi);p = p -next;printf(b );printf(n);main()char x;struct quantic *p, *q, *l, *s, *k, *a, *b, *c, *d;/欢迎界面开始welcome();/输入一元未知量x = getx();/输入两个多项式并输出printf(n请输入第一个多项式:n);p = input();output(x, p);printf(n请输入第二个多项式:n);l = input();output(x, l);/查找相应节点find(x, p);find(x, l);/对队列进行排序、合并，然后输出q = s