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

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

2、,然后依次输出各位上的数值<4>通过主函数来调用其它各个函数。3、数据结构设计：<1>输入阶段采用一维数组a ,b在输入阶段当大数输入时， 大 数a,b从高位到低位分别依次存入数组 a ,b。<2>调用函数计算阶段采用一维数组 c在调用sum(a,b,m,n)函数 中，在计算过程中，由个位到高位依次计算各位的结果，并依次存 入数组c中。4、功能函数设计：<1>找出每一列的所有项首先找规律，如下所示进行乘法：a0a1a2b0b1b2b2a0b2a1b2a2b1a0b1a1b1a2bOaOb0a1b0a2下标之和0 12i=4i=3i=2的数值）即有

3、3i=14i =0（循环时的i下标之和二m+n-2-i,由此限定条件可设计循环得出每一列的所有项。故首先解决了找出每一列所有项的问题。<2>计算从低位到高位每一位的值。显然考虑到进位的问题，故必须从低位到高位依次计算，对于每一 列，第一项可以除十取余数，保留在原位，存入c，所得商进位 存入mm。然后对于第二列，第一项加进位mm，然后取余数存入 su,再加第二项，取余数存入c,求商存入进位mm，直到该列所有 项参与运算到该列结束时，求的最终的c,和mm.依次进行后面的 运算。<3>找出反向存入结果c中的首项.因为最高位一定不为零，故可以设计程序从c399开始判断，当ci

4、不等于零时，即为最高项。<4>设计主函数，依次调用如上函数。然后通过for循环5、程序代码：#i nclude <stdio.h>#in elude <math.h>void sum(i nt a200,i nt b200,i nt m,i nt n)结果在数组里顺序是反着的int mm=O; 保存进位int c400=0; 保存结果int i,j,su,tt;for(i=0;i<m+n;i+)su=0;for(j=0;j<m;j+)if(tt=(m-1+ n-1-i-j)>=n |(tt=(m-1+ n-1-i-j)<0)con t

5、i nue;elsesu=su+aj*bm-1+ n-1-i-j; su=su+mm;ci=su%10;mm=su/10;prin tf("n*n");printf("结果是：n");for(i=399;i>=0;i-)找首位if(ci!=O)tt=i;break;else con ti nue;for(i=tt;i>=0;i-) 输出prin tf("%d",ci);prin tf("n");void mai n()int i,m, n,c;int a200=0,b200=0;printf("

6、;f*n");printf（"请输入第一个数字：n"）;for(i=0;(c=getchar()!='n'i+)ai=c-48;m=i;prin tf("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、问题描述：<1&g

7、t;能够按照指数降序排列建立多项式，能够完成两个多项式的相 乘，并将结果输出。2、设计思路：这个程序的关键是多项式的创建和排列，以及相乘时相同指数的系 数相加。由于多项式拥有指数和系数 （假设基数已定），所以可以 定义一个包含指数系数的结构体，用单链表存储多项式的数据，所 以结构体包含next指针。数据插入时比较两数的指数，按照降序排 序，从表头的next开始，直至找到合适的位置，然后开始链表中数 值的插入，如果相等则直接将指数相加，如果大于就将新数据插入 到当前指向的前面，否则将新数据插入到最后。输入完数据后相 乘，多项式运算时要循环遍历整个多项式，多项式的每一组数据都 要和另一个多项式整组

8、数据相乘，直到两个多项式都遍历完结束。3、数据结构设计：<1>对已排序且合并了同指数项的两个多项式实现乘法操作，并输出结果；<2>结果多项式要求以动态链表为存储结构，复用原多项式的结点空间；<3>输出结果多项式要求按指数升序排列，同指数的多项要合并，项数的正负号要求显示合理。4、功能函数设计(见源代码)5、程序代码：#i nclude <stdio.h>#i nclude <stdlib.h>#defi ne TRUE 1#defi ne FALSE 0#defi ne N sizeof(struct qua ntic)/跳转页面 v

9、oid welcome()prin tf("n*n");/创建多项式结构体struct qua nticint xishu;int mi;struct qua ntic *n ext;；/得到一元变量char getx(void)char x;printf("n 请输入一元变量：")；sca nf("%c", &x);return x;/创建多项式链表struct qua ntic *in put(void)struct qua ntic *p1, *p2, *head;head = p2 = (struct qua ntic

10、 *)malloc(N);printf("n 请输入：系数 幕值(系数输入0结束)。n");p1 = (struct qua ntic *)malloc(N);sca nf("%d %d", & p1 -> xishu, & p1 -> mi);while(p1 -> xishu != 0)p2 -> n ext = p1;p2 = pl；pl = (struct qua ntic *)malloc(N); scanf("%d %d", & pl -> xishu, & p

11、l -> mi);p2 -> next = NULL;free(p1);retur n head;/查找void fin d(char x, struct qua ntic *p)struct qua ntic *p1;int m, n, i = 0;p1 = p;printf("1.按系数查找。n");printf("2.按指数查找。n");printf("0.退出查找。n");sca nf("%d", &m);switch(m)case 1:printf("请输入索引关键字：&qu

12、ot;)；sca nf("%d", &n);pl = pl -> n ext;while(p1 != NULL)if(p1 -> xishu = n)prin tf("%d%c(%d)", p1 -> xishu, x, p1 -> mi);i +;p1 = p1 ->n ext;if(i = 0)printf("查无此数据。n");prin tf("n");fin d(x, p);break;case 2:printf("请输入索引关键字:");sea n

13、f("%d", &n);pl = pl -> n ext;while(p1 != NULL)if(p1 -> mi = n)prin tf("%d%c(%d)", p1 -> xishu, x, p1 -> mi);i +;p1 = p1 ->n ext;if(i = 0)printf("查无此数据。n");prin tf("n");fin d(x, p);break;ease 0:welcome。；/多项式相乘struct qua ntic *MulExp(struct qu

14、a ntic *exp1,struct qua ntic *exp2) struct qua ntic *head,*p1,*q,*p2,*last,pre,*p;int flag=TRUE;head=p1=*exp1;/p1=p1- >n ext;for(;p1-> next != NULL;p 仁p1-> next);p=last=p1;p1=(*exp1)->n ext;while(p1 != p->n ext)pre = *p1;flag=TRUE;p2=(*exp2)-> next;while(p2)if(flag=TRUE)p1->xish

15、u=p1->xishu*p2->xishu;p1->mi=p1->mi+p2->mi;p2=p2->n ext;flag=FALSE;elseq=(struct qua ntic *)malloc(N);q->xishu=pre.xishu*p2->xishu;q->mi=pre.mi+p2->mi;last- >n ext=q;last=q;p2=p2->n ext;p1=p1- >n ext;last- >n ext=NULL;retur n head;/排序多项式struct qua ntic *sort

16、(struct qua ntic *pol)struct qua ntic *head = pol;struct qua ntic *p,*q;struct qua ntic *r,*t;if(head-> next = NULL)printf("请输入有效信息。n");elsep = head->n ext;q = p->n ext;p->n ext = NULL;p = q;while(p!=NULL)r = head;q = r->n ext;while(q != NULL&& q->mi < p->mi

17、)r = q;q = q->n ext;t=p->n ext;p->n ext=r- >n ext;r->n ext=p;P=t； return(head);/合并多项式struct qua ntic *comb in e(struct qua ntic *head)struct qua ntic *p1,*p2;pl = head ->n ext;while(p1 -> next != NULL )if(p1 -> next -> mi = p1 -> mi)p2 = p1 ->n ext;p1 -> xishu = p

18、1 -> xishu + p2 -> xishu;p1 -> n ext = p1 -> n ext ->n ext;free(p2);elsep1 = pl -> n ext;return(head);/输出多项式void output(char x, struct qua ntic *p)p = p -> n ext;while(p != NULL)if(p -> xishu <0 && p != NULL)prin tf("b b");prin tf("%d%c(%d)+", p -> xishu, x, p -> mi); p = p ->n ext;prin tf("b ");prin tf("n"); mai n()char x;struct qua ntic *p, *q, *l, *s, *k, *a, *b, *c