数据结构课程设计n元多项式乘法.docx
- 文档编号:14501180
- 上传时间:2023-06-24
- 格式:DOCX
- 页数:24
- 大小:499.22KB
数据结构课程设计n元多项式乘法.docx
《数据结构课程设计n元多项式乘法.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计n元多项式乘法.docx(24页珍藏版)》请在冰点文库上搜索。
数据结构课程设计n元多项式乘法
数据结构课程设计报告
——N元多项式乘法
1课程设计内容
功能:
完成两个n元多项式作乘法,给出明确的等式形式。
分步实施:
1)初步完成总体设计,搭好框架,确定人机对话的界面,确定函数个数;
2)完成最低要求:
建立一个文件,实现两个一元二次多项式作乘法。
3)进一步要求:
实现三元二次多项式的乘法。
有兴趣的同学可以自己扩充系统功能。
2课程设计分析
本程序用的存储方式是单链表,单链表在C语言中是一种非常常见的结构,而在C++中的实现却又有不同,在一些地方更简单,更严密。
同时,由于C++的一些特点,使它具有C语言所不具有的“安全化”,所以本程序用C++。
有了链表特定的数据类型Mulpoly,接下来就需要建立这个链表。
这里定义了一个构造函数CreatePoly来构造链表。
首先定义一个CreatePoly型的指针变量head作为头结点,存储多项式的信息(项数),为head分配存储空间建立一个头结点并为其数据域赋值,分配存储空间用c++语言中的malloc来实现;这时输入多项式的项数num,把它赋值给head的coef域,exp域赋值为1,此时再定义一个CreatePoly型的指针变量r指向head头结点。
还要用类似的算法建立多项式的其它结点,剩余节点的插入用一个while循环来实现,while循环中的控制变量i从大于0的数n开始递增,直到到达num,此时while循环结束。
While循环的循环体由两部分组成,第一部分是为指针变量s分配存储空间和为其数据域赋值,分配存储空间同样用c++语言中的malloc来实现;第二部分是节点的指针域转换过程,将r的指针域指向新生成的结点s,相当于将生成结点依次用指针连接,然后将最后一个结点的指针域设置为NULL,具体代码如下:
MulPoly*CreatePoly(){
MulPoly*head,*r,*s;
intm,n,num,i=1;
head=(MulPoly*)malloc(sizeof(MulPoly));
cout<<"请输入多项式的项数:
"< cin>>num; head->coef=num; head->exp=1; r=head; while(i<=num)//n不为0时建立多项式链表 { s=(MulPoly*)malloc(sizeof(MulPoly)); cout<<"输入第"< "< cin>>n>>m; s->exp=m; s->coef=n; r->next=s; r=s; i++;} r->next=null; return(head); } 在处理多项式相乘的问题时,定义一个PolyMulti函数实现,需要再建立一个MulPoly型的链表存储相乘之后的链表,定义结果链表的系数等于链表P1的系数乘以链表P2的系数: (p->coef)=(p1->coef)*(p2->coef)结果链表的指数等于链表P1的指数乘以链表P2的指数: (p->exp)=(p1->exp)+(p2->exp)。 在整理之后可能出现零结点,那么就需要进行判断和删除操作同时释放零结点,这些操作是通过一个while循环来完成。 具体代码如下: while(p! =q) {s=q; q=q->next;} s->next=q->next; free(q); } 还需要定义一个输出函数,在主函数中调用输出两个多项式相乘后的结果。 程序的最终都是由主函数来实现。 在主函数中通过对一些自定义函数的调用实现具体的操作。 在此主函数调用了一个构建链表的函数CreatePoly、一个删除空结点的函数Delete和输出函数Print。 在主函数的开始需要定义三个MulPoly型指针变量,分别用来存储调用CreatePoly函数和PolyMulti函数生成的链表和结果链表。 在构建链表之前要给节点分配存储空间,s=(MulPoly*)malloc(sizeof(MulPoly));这条语句便可完成此操作。 此条语句运用了c++语言库函数中的malloc函数,这个函数的作用是在内存的动态存储区中分配一个长度为sizeof(MulPoly)的内存空间。 调用构建链表函数CreatePoly后链表Pl便构建完成。 接下来需要执行m=PolyMulti(p,q);语句,这条语句的目的是把多项式P1和P2相乘的结果多项式存储在链表m当中,然后执行Print(m);语句显示输出。 主函数的程序框架如下: intmain(){ MulPoly*p,*q,*m; p=CreatePoly(); q=CreatePoly(); m=PolyMulti(p,q); Merge_Same(m); Print(m); system("pause"); } 程序的调试是程序顺利完成中非常关键的一步。 通过程序的调试分析可以解决程序的运行错误也可以对程序的性能进行分析。 这个多项式运算问题研究的程序最重要的就是看输出的链表是否正确,是否带有空结点,合并是否完全。 决定程序成功与否的第一步是定义的PolyMulti函数操作是否正确。 如果这一步中出现错误,那么接下来的操作可以说是错上加错。 在调试的时候可以在程序中加入删除、释放空结点操作,此操作便是由Delete函数完成的,若输出的多项式没有空结点说明函数正确,可以继续向下进行。 接下来就是相乘后的合并同类项,控制此操作的关键是一个Merge_Same函数,调用Delete函数是决定成功与否的关键。 可以先在本上写出两个正确的简单的多项式,使其具有相加后出现空结点的特点,然后变换循环变量的范围,当输出吻合时则说明操作正确。 各个关键部分都已检查完毕,剩下的就是对程序的进一步细心的完善直到满足要求。 下面分析一下程序的性能。 在主函数中,首先调用的是构造单链表函数CreatePoly,在这个函数中需要通过一个for循环为每个结点分配存储空间,变换节点的next域,时间复杂度为O(n)。 接下来执行一个双重for循环,在内部的for循环中是对结点的相加、相乘操作,因为是按着指针的方向就可以对结点进行相加、相乘操作,所以每个结点的操作都需要m次,共n个结点,则需要 次操作,时间复杂度为O( )。 3思路原理 先要设置两个单链表,每个单链表中可写入一个多项式。 加法: 取第两个链表中最高项和另一链表各项比指数,若不同则放在第三个空链表里作为第一项,若相同则系数相加指数不变,放在第三个空链表里作为第一项,并且要删除两链表里此指数项。 取第两个链表中最高项和另一链表各项比指数,以此类推。 乘法: 取第一个链表第一项和第二链表的每一项相乘,系数相乘,指数相加,作为一个新链表。 取第一个链表第二项和第二链表的每一项相乘.......最后再把每个新链表做加法。 最后显示答案。 4程序简图 5算法(数据结构)描述 定义单链表的抽象数据类型: ADTLinkList{ 数据对象: D={ai|ai∈ElemSet,i=1,2,3,…,n>=0} 数据关系: R={ //----------------------线性表的单链表基本操作---------------------// LinkListInitList(void); 构造一个空的线性表 voidDestroyList(LinkList*L); 初始条件: 线性表L已存在。 操作结果: 销毁线性表L。 LinkListMakeEmpty(LinkListL)‘ 初始条件: 线性表L已存在。 操作结果: 将线性表L重置为空表。 intIsEmpty(LinkListL); 初始条件: 线性表L已存在。 操作结果: 判断线性表是否为空表。 intListLength(LinkListL); 初始条件: 线性表L已存在。 操作结果: 返回线性表L结点的个数。 LNodeIsLast(LinkListL); 初始条件: 线性表L已存在。 操作结果: 返回线性表L的最后一个结点(尾结点)。 LNodeNewLNode(ElemTypeX); 构造一个数据域为X的新结点 LNodeFindPrefious(ElemTypeX,LinkListL); 初始条件: 线性表L已存在。 操作结果: 在线性表L中寻找值为X的结点,若找到则返回该结点的前驱,否则返回NULL。 voidListDelete(LNodePre); 初始条件: 线性表L中结点P已找到。 操作结果: 删除该结点。 链表的结点结构: ┌──┬──┐ │data│next│ └──┴──┘ data域--存放结点值的数据域 next域--存放结点的直接后继的地址(位置)的指针域(链域) 此题定义系数和指数结构如下: coefexpnext //----------------------线性表的单链表存储结构---------------------// TypedefstructLnode{ ElemTypedata;//结点的数据域 StructLnode*next;//结点的指针域 }Lnode,*LinkList; //-----------------------------基本操作----------------------------// InitArray(&A,n,bound1,...,boundn) 操作结果: 若维数n和各维长度合法则构造相应数组A。 DestroyArray(&A) 初始条件: 数组A已经存在。 操作结果: 销毁数组A。 Value(A,&e,index1,...,indexn) 初始条件: A是n维数组,e为元素变量,n个下标值。 操作结果: 若各下标不超界,则e赋值为所指定的A的元素值,并返回OK。 Assign(&A,e,index1,...,indexn) 初始条件: A是n维数组,e为元素变量,n个下标值。 操作结果: 若下标不超界,则将e的值赋给A中指定下标的元素。 }ADTArray 6程序清单 6.1单链表表示 /*程序源代码: */ #include #include #include #include #definenull0 usingnamespacestd; typedefstructterm { //项的表示,多项式的项作为LinkList的数据元素 floatcoef;//系数 intexpn;//指数 structterm*next; }term; intEmpty(term*L) { if(L->next! =null) return1; return0; } term*CreatePoly() { term*head,*r,*s; intm,n,num,i=1; head=(term*)malloc(sizeof(term));//建立一个头结点 cout<<"请输入多项式的项数: "< cin>>num; head->coef=num; head->expn=1; r=head; while(i<=num)//n不为0时建立多项式链表 { s=(term*)malloc(sizeof(term));//建立一个新结点 cout<<"输入第"< "< cin>>n>>m; s->expn=m; s->coef=n; r->next=s; r=s; i++; } r->next=null; return(head); } term*PolyMulti(term*f,term*g) { term*p1,*p2,*p,*r,*head; head=(term*)malloc(sizeof(term)); head->coef=null; head->expn=null; r=head; for(p1=f->next;p1! =null;p1=p1->next) { for(p2=g->next;p2! =null;p2=p2->next) { p=(term*)malloc(sizeof(term)); (p->coef)=(p1->coef)*(p2->coef); (p->expn)=(p1->expn)+(p2->expn); r->next=p; r=p; } } r->next=null; returnhead; } voidDelete(term*L,term*p) { term*s,*q; s=L; q=L->next; while(p! =q) { s=q; q=q->next; } s->next=q->next; free(q); } voidPrint(term*L) { term*p; cout<<"两个多项式相乘的结果为: "< if(Empty(L)) { for(p=L->next;p! =null;p=p->next) cout<<"("< cout<<"\b"; } else cout<<"0"; } voidMerge_Same(term*f) { term*p,*q; for(p=f->next;p! =null;p=p->next) for(q=p->next;q! =null;q=q->next) { if(p->expn==q->expn) { (p->coef)=(p->coef)+(q->coef); Delete(f,q); } if(p->coef==0) { Delete(f,p); break; } } } term*CreatPolyn(term*P,intm) { //输入m项的系数和指数,建立表示一元多项式的有序链表P if(m<=0)returnNULL; term*h=P=(term*)malloc(sizeof(term)),*q=NULL; P->coef=0.0; inti; printf("依次输入%d个数(前一个为系数,后一个为指数)\n",m*2); for(i=1;i<=m;++i) {//依次输入m个非零项 scanf("%f%d",&P->coef,&P->expn); if(P->coef) q=P; P=P->next=(term*)malloc(sizeof(term)); } q->next=NULL; free(P); returnh; }//CreatPolyn term*selsort(term*h) { term*g,*p,*q; if(! h)returnNULL; floatf; inti,fini=1; for(g=h;g->next&&fini;g=g->next) { fini=0; for(p=h,q=h->next;q;p=p->next,q=q->next) if(p->expn { f=p->coef;i=p->expn; p->coef=q->coef;p->expn=q->expn; q->coef=f;q->expn=i; fini=1; } } for(g=h,p=g->next;p;) if(g->expn==p->expn) { g->coef+=p->coef; g->next=p->next; q=p; p=p->next; free(q); } elseif(g->next) { g=g->next; p=p->next; } returnh; } voidPrintfPoly(term*P) { term*q=P; if(! q) { putchar('0'); return; } if(q->coef! =1) { printf("%g",q->coef); if(q->expn==1)putchar('X'); elseif(q->expn)printf("X^%d",q->expn); } elseif(! q->expn)putchar('1'); elseif(q->expn==1)putchar('X'); elseprintf("X^%d",q->expn); q=q->next; while(q) { if(q->coef>0)putchar('+'); if(q->coef! =1) { printf("%g",q->coef); if(q->expn==1)putchar('X'); elseif(q->expn)printf("X^%d",q->expn); } elseif(! q->expn)putchar('1'); elseif(q->expn==1)putchar('X'); elseprintf("X^%d",q->expn); q=q->next; } } intCompare(term*a,term*b) { if(a->expn if(a->expn>b->expn)return1; return0; } term*APolyn(term*Pa,term*Pb) { //多项式加法: Pa=Pa+Pb,利用两个多项式的结点构成"和多项式"。 term*h,*qa=Pa,*qb=Pb,*p,*q; floatsum; h=p=(term*)malloc(sizeof(term)); p->next=NULL; while(qa&&qb) { //Pa和Pb均非空 switch(Compare(qa,qb)) { case-1: //多项式PA中当前结点的指数值小 p->next=qb; p=qb; qb=qb->next; break; case0: //两者的指数值相等 sum=qa->coef+qb->coef; if(sum! =0.0) { //修改多项式PA中当前结点的系数值 p->next=qa; qa->coef=sum; p=qa; qa=qa->next; } else { //删除多项式PA中当前结点 q=qa; qa=qa->next; free(q); } q=qb; qb=qb->next; free(q); break; case1: //多项式PB中当前结点的指数值小 p->next=qa; p=qa; qa=qa->next; break; }//switch }//while if(Pa)p->next=qa;//链接Pa中剩余结点 if(Pb)p->next=qb;//链接Pb中剩余结点 q=h; h=h->next; free(q); returnh; }//APolyn term*A(term*Pa,term*Pb) { intn; puts("输入第二个一元多项式的项数"); scanf("%d",&n); Pb=CreatPolyn(Pb,n); Pb=selsort(Pb); PrintfPoly(Pa); if(Pb&&Pb->coef>0)printf("+"); PrintfPoly(Pb); Pa=APolyn(Pa,Pb); printf("="); Pa=selsort(Pa); PrintfPoly(Pa); returnPa; } term*BPolyn(term*Pa,term*Pb) { //多项式减法: Pa=Pa-Pb,利用两个多项式的结点构成"差多项式"。 term*p=Pb; while(p) { p->coef*=-1; p=p->next; } returnAPolyn(Pa,Pb); }//BPolyn term*B(term*Pa,term*Pb) { intn; puts("输入第二个一元多项式的项数"); scanf("%d",&n); Pb=CreatPolyn(Pb,n); Pb=selsort(Pb); PrintfPoly(Pa); printf("-"); putchar('(');PrintfPoly(Pb);putchar(')'); Pa=BPolyn(Pa,Pb); printf("="); Pa=selsort(Pa); PrintfPoly(Pa); returnPa; } intmain() { term*M=NULL,*N=NULL; term*p,*q,*m; chars[2]; inti,n; f: puts("\n1: 加\n2: 乘\n3: 下一步"); cin>>i; switch(i) { case1: puts("一元多项式计算: \n输入第一个一元多项式的项数"); scanf("%d",&n); M=CreatPolyn(M,n); M=selsort(M); PrintfPoly(M); M=A(M,N); gotof; case2: p=CreatePoly(); q=CreatePoly(); m=PolyMulti(p,q); Merge_Same(m); Print(m); gotof; case3: break; default: puts("输入有误,请重新输入! "); } } 6.2数组表示 /*程序
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 多项式 乘法