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

目录问题描述…………………设计思绪…………………数据结构设计……………功能函数设计……………程序代码…………………运营与测试………………设计心得…………………一、大数相乘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 1234i=4i=3i=2i=1i=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>voidsum(inta[200],intb[200],intm,intn)//结果在数组里顺序是反着的{ intmm=0;//保存进位 intc[400]={0};//保存结果 inti,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) 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; } elsecontinue; } for(i=tt;i>=0;i--)//输出 printf("%d",c[i]); printf("\n");}voidmain(){ inti,m,n,c; inta[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=getchar())!='\n';i++) b[i]=c-48; n=i;//m,n为数字长度 sum(a,b,m,n);}6运营与测试：7、设计心得：根据数字相乘原理，编程实现了大数相乘，虽然过程中出现了许多问题但通过与同学讨论后都顺利解决。二、多项式相乘1、问题描述：<1>可以按照指数降序排列建立多项式，可以完毕两个多项式的相乘，并将结果输出。2、设计思绪：这个程序的关键是多项式的创建和排列，以及相乘时相同指数的系数相加。由于多项式拥有指数和系数（假设基数已定），所以可以定义一个包含指数系数的结构体，用单链表存储多项式的数据，所以结构体包含next指针。数据插入时比较两数的指数，按照降序排序，从表头的next开始，直至找到合适的位置，然后开始链表中数值的插入，假如相等则直接将指数相加，假如大于就将新数据插入到当前指向的前面，否则将新数据插入到最后。输入完数据后相乘，多项式运算时要循环遍历整个多项式，多项式的每一组数据都要和另一个多项式整组数据相乘，直到两个多项式都遍历完结束。3、数据结构设计：<1>对已排序且合并了同指数项的两个多项式实现乘法操作，并输出结果；<2>结果多项式规定以动态链表为存储结构，复用原多项式的结点空间；<3>输出结果多项式规定按指数升序排列，同指数的多项要合并，项数的正负号规定显示合理。功能函数设计（见源代码）程序代码：#include<stdio.h>#include<stdlib.h>#defineTRUE1#defineFALSE0#defineNsizeof(structquantic)//跳转页面voidwelcome(){ printf("\n*******************************\n");}//创建多项式结构体structquantic{ intxishu; intmi; structquantic*next;};//得到一元变量chargetx(void){ charx; printf("\n请输入一元变量："); scanf("%c",&x); returnx;}//创建多项式链表structquantic*input(void){ structquantic*p1,*p2,*head; head=p2=(structquantic*)malloc(N); printf("\n请输入：系数幂值(系数输入0结束)。\n"); p1=(structquantic*)malloc(N); scanf("%d%d",&p1->xishu,&p1->mi); while(p1->xishu!=0) { p2->next=p1; p2=p1; p1=(structquantic*)malloc(N); scanf("%d%d",&p1->xishu,&p1->mi); } p2->next=NULL; free(p1); returnhead;}//查找voidfind(charx,structquantic*p){ structquantic*p1; intm,n,i=0; p1=p; printf("1.按系数查找。\n"); printf("2.按指数查找。\n"); printf("0.退出查找。\n"); scanf("%d",&m); switch(m) { case1: 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; case2: 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; case0: welcome(); }}//多项式相乘structquantic*MulExp(structquantic**exp1,structquantic**exp2){ structquantic*head,*p1,*q,*p2,*last,pre,*p; intflag=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==TRUE) { p1->xishu=p1->xishu*p2->xishu; p1->mi=p1->mi+p2->mi; p2=p2->next; flag=FALSE; } else { q=(structquantic*)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; } returnhead;}//排序多项式structquantic*sort(structquantic*pol){ structquantic*head=pol; structquantic*p,*q; structquantic*r,*t; if(head->next==NULL) printf("请输入有效信息。\n"); else { p=head->next; q=p->next; p->next=NULL; p=q; } while(p!=NULL) { r=head; q=r->next; while(q!=NULL&&q->mi<p->mi) { r=q; q=q->next; }t=p->next; p->next=r->next; r->next=p; p=t; } return(head);}//合并多项式structquantic*combine(structquantic*head){ structquantic*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); } else {p1=p1->next;} } return(head);}//输出多项式voidoutput(charx,structquantic*p){ p=p->next; while(p!=NULL) { if(p->xishu<0&&p!=NULL) printf("\b\b"); pri