一元多项式的运算.doc

《一元多项式的运算.doc》由会员分享，可在线阅读，更多相关《一元多项式的运算.doc（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-作者xxxx-日期xxxx一元多项式的运算【精品文档】数据结构课程设计实 验 报 告专业班级： 学 号： 姓 名： 2011年1月1日题目：一元多项式的运算1、 题目描述一元多项式的运算在此题中实现加、减法的运算，而多项式的减法可以通过加法来实现（只需在减法运算时系数前加负号）。在数学上，一个一元n次多项式Pn(X)可按降序写成： Pn(X)= PnXn+ P(n-1)X(n-1)+.+ P1X+P0它由n+1个系数惟一确定，因此，在计算机里它可以用一个线性表P来表示： P=(Pn，P(n-1)，.，P1，P0)每一项的指数i隐含在其系数Pi的序号里。假设Qm(X)是一元m次多项式，同样可以

2、用一个线性表Q来表示：Q=(qm,q(m-1)，.，q1，q0)不是一般性，假设吗吗mnext;q=0;/记录结点位置序号while(p&e.expndata.expn)p=p-next;q+;if(p=NULL|e.expn!=p-data.expn)return 0;else return 1;void InsertNode(LinkList &L,DataType e,int q)函数功能：将新的节点p插入到现有链表的后面，并确保多项式的指数expn是升序。将s节点插入到e所指向的链表。在该函数的操作中，要注意指针是如何移动的。/有序链表结点的插入void InsertNode(Link

3、List &L,DataType e,int q)ListNode *s,*p;int i=0;p=L;while(p-next & inext;i+;/查找插入位置s=(ListNode*)malloc(sizeof(ListNode);s-data.coef=e.coef;s-data.expn=e.expn;s-next=p-next;p-next=s;有了上述两个“结点的查找定位算法”和“有序链表结点的插入算法”，int n保存的多项式的项数，使用for语句，控制输入多项式的每一项。当创建的链表长度为n时，将不再提示用户继续输入多项式的系数和指数。建立一个一元多项式的单链表的具体算法如

4、下：/多项式链表的建立void CreatPolyn(LinkList &L,int n)LinkList pa; /定义一个头指针为pa链表int i,q; /i用来计输入的项数，q指结点的位置序号DataType e; /插入的值epa=(ListNode*)malloc(sizeof(ListNode); /生成链表头结点pa-next=NULL;for(i=1;inext;pb=Lb-next; /pa和pb分别指向两个链表的开始结点Lc=pc=La; /用La的头结点作为Lc的头结点while (pa&pb)if(pa-data.expn pb-data.expn)pc-next=p

5、a;pc=pa;pa=pa-next;else if(pa-data.expn data.expn)pc-next=pb;pc=pb;pb=pb-next; else sum=pa-data.coef+pb-data.coef;if(fabs(sum)0) /系数和不为零pa-data.coef=sum;pc-next=pa;pc=pa;pa=pa-next;s=pb;pb=pb-next;free(s);elses=pa;pa=pa-next;free(s);s=pb;pb=pb-next;free(s);pc-next=pa?pa:pb;/插入链表剩余部分 free(Lb);/释放Lb的头

6、结点(4) 多项式链表的输出void printList(LinkList L)函数功能：显示多项式链表。在输出项中使用了条件表达式，当系数项为正数时，在系数前输出一个“+”号，否则输出一个空格，而负数的负号还照常输出，使得输出结果尽量与原多项式的表示形式类似。因此，输出多项式链表的算法实现如下：/多项式链表的输出void printList(LinkList L)ListNode *p;p=L-next;while(p)printf(%c %fx %d,(p-data.coef0? +: ),p-data.coef,p-data.expn);p=p-next;printf(n);源程序代码：

7、#include #include #include /多项式链表结点类型定义typedef struct /在struct前使用关键字typedef，表示是声明新类型float coef; /系数int expn; /指数DataType; /DataType是新类型typedef struct node /单链表的存储DataType data; /数据域struct node *next; /指向下一个结点ListNode,*LinkList; /ListNode是结点的新类型，LinkList是指向ListNode类型的结点的指针类型/结点的查找定位int LocateNode(Lin

8、kList L,DataType e,int &q)ListNode *p=L-next;q=0;/记录结点位置序号while(p&e.expndata.expn)p=p-next;q+;if(p=NULL|e.expn!=p-data.expn)return 0;else return 1;/有序链表结点的插入void InsertNode(LinkList &L,DataType e,int q)ListNode *s,*p;int i=0;p=L;while(p-next & inext;i+;s=(ListNode*)malloc(sizeof(ListNode);s-data.coe

9、f=e.coef;s-data.expn=e.expn;s-next=p-next;p-next=s;/多项式链表的建立void CreatPolyn(LinkList &L,int n)LinkList pa; /定义一个头指针为pa链表int i,q; /i用来计输入的项数，q指结点的位置序号DataType e; /插入的值epa=(ListNode*)malloc(sizeof(ListNode); /生成链表头结点pa-next=NULL;for(i=1;inext;while(p)printf(%c %fx %d,(p-data.coef0? +: ),p-data.coef,p-

10、data.expn);p=p-next;printf(n);/多项式链表的相加void AddPolyn(LinkList La,LinkList Lb,LinkList &Lc) /两个有序链表La和Lb表示的多项式相加ListNode *pa,*pb,*pc,*s;float sum;pa=La-next;pb=Lb-next;/pa和pb分别指向两个链表的开始结点Lc=pc=La;/用La的头结点作为Lc的头结点while (pa&pb)if(pa-data.expn pb-data.expn)pc-next=pa;pc=pa;pa=pa-next;xpn)pc-next=pb;pc=p

11、b;pb=pb-next; else sum=pa-data.coef+pb-data.coef;if(fabs(sum)0)/系数和不为零pa-data.coef=sum;pc-next=pa;pc=pa;pa=pa-next;s=pb;pb=pb-next;free(s);elses=pa;pa=pa-next;free(s);s=pb;pb=pb-next;free(s);pc-next=pa?pa:pb;/插入链表剩余部分 free(Lb);/释放Lb的头结点/主控函数void main()LinkList La,Lb,Lc;int n;printf(输入第一个多项式的项数:);sca

12、nf(%d,&n);printf(输入第一个多项式的每一项的系数,指数:n);CreatPolyn(La,n);printf(第一个多项式为:);printList(La);printf(输入第二个多项式的项数:);scanf(%d,&n);printf(输入第二个多项式的每一项的系数,指数:);CreatPolyn(Lb,n);printf(第二个多项式为:); printList(Lb);AddPolyn(La,Lb,Lc);printf(n相加后的和多项式为:);printList(Lc);5、调试分析此一元多项式的运算程序，只能实现一元多项式的加、减法，不能实现一元多项式的乘法，而且若

13、想计数多个多项式的和或者差的话，必须退出界面重新开始计算。在补充程序里面，解决了程序没有的选择功能表的功能，及其多项式的乘法运算。6. 测试结果输入多项式的项数，并且显示多项式及其两个多项式的和：补充程序：多项式运算程序具有以下基本功能：1界面输出，提示如何输入数据。要求先输入多项式的项数。2创建多项式。接收输入的数据，并保存到链表中。3显示程序的功能表，允许使用者选择运算类型。4显示已经创建好的多项式。5实现加法运算。6实现减法运算。7实现乘法运算。8清除内存内容，销毁创建的链表，退出程序。该程序实现了多项式的创建、多项式的加法、减法、乘法运算以及多项式的清除。源程序代码：#include#

14、include/*以下函数实现链表的定义*/*该函数的功能:在计算机内要表示一个多项式，至少以下数据信息-系数信息、指数信息和指向下一个单项式的指针。通过指针，我们就可以把多个单项式连接起来，形式一个多项式.*/typedef struct Polynomialfloat coef; /系数int expn; /指数struct Polynomial *next; /指向下一个结点*Polyn,Polynomial; /Polyn为结点指针类型/*以下函数用来实现链表的顺序排列和合并相同的项 */*该函数的功能:实现链表的顺序排列和合并相同的项。将新的节点p插入到现有链表的后面，并确保多项式的

15、指数expn是升序。将p节点插入到head所指向的链表。在该函数的操作中，要注意指针是如何移动的。*/void Insert(Polyn p,Polyn h) if(p-coef=0)free(p); /系数为0的话释放结点else /如果系数不为0 Polyn q1,q2;q1=h;q2=h-next;while(q2&p-expnexpn) /查找插入位置 q1=q2;q2=q2-next;if(q2&p-expn=q2-expn) /将指数相同相合并 q2-coef+=p-coef;free(p);if(!q2-coef) /系数为0的话释放结点 q1-next=q2-next;free

16、(q2);else /指数为新时将结点插入 p-next=q2;q1-next=p;/Insert/*以下函数实现建立一个多项式*/*该函数功能:创建新的多项式链表。int m保存的多项式的项数，使用for语句，控制输入多项式的每一项。当创建的链表长度为m时，将不再提示用户继续输入多项式的系数和指数。*/Polyn CreatePolyn(Polyn head,int m)/建立一个头指针为head、项数为m的一元多项式,int m是保存的多项式的项数 /在主程序初始时，先输入的多项式中的项数m、n 在这里为m。主程序中的pa、pb在此为headint i;/定义int i计数，当inext=

17、NULL;for(i=0;icoef,&p-expn);Insert(p,head); /调用Insert函数插入结点return head;/CreatePolyn/*以下函数实现多项式的销毁*/*该函数的功能:销毁掉创建的两个链表，释放内存。以辅助退出程序*/void DestroyPolyn(Polyn p)/销毁多项式pPolyn q1,q2;q1=p-next;q2=q1-next;while(q1-next)free(q1);q1=q2; /指针后移q2=q2-next;/*以下函数实现显示输出多项式* */*该函数的功能:显示多项式链表。在该函数中较复杂的是如何控制链表的输出,尤

18、其是第一项的输出，同时还有符号的控制。在输出第一项时要判断是不是常数项,若是,则不要输出字符x。*/void PrintPolyn(Polyn P) Polyn q=P-next; int flag=1;/项数计数器,flag=1表示为第一项if(!q) /若多项式为空,输出0 putchar(0); printf(n);return; while (q)if(q-coef0&flag!=1)/系数大于0且不是第一项putchar(+); if(q-coef!=1&q-coef!=-1)/系数非1或-1的普通情况printf(%g,q-coef); if(q-expn=1) putchar(X

19、);else if(q-expn) printf(X%d,q-expn);elseif(q-coef=1)if(!q-expn) putchar(1); else if(q-expn=1) putchar(X); else printf(X%d,q-expn);if(q-coef=-1)if(!q-expn) printf(-1); else if(q-expn=1) printf(-X); elseprintf(-X%d,q-expn);q=q-next; flag+;/whileprintf(n);/PrintPolyn/*在下面的辅助乘法和加法运算*/*该函数功能：判断两个多项式在同一指

20、数下是否有其中一个为系数为0。用来辅助加法和乘法运算。*/int compare(Polyn a,Polyn b)/a、b两个多项式if(a&b)/a、b多项式均非空if(!b|a-expnb-expn) /a的指数大于b的指数return 1;else if(!a|a-expnexpn) /a的指数小于b的指数return -1;else /a的指数等于b的指数return 0;else if(!a&b) return -1;/a多项式已空，但b多项式非空else return 1;/b多项式已空，但a多项式非空/compare/*以下函数实现加法*/*该函数功能:实现两个多项式pa、pb相

21、加，并将计算结果存储于新建立的pc中，它的原理是将指数相同的单项式相加，系数相加后为0，则pa、pb的指针都后移。在加法计算中要求pa与pb的幂次序都是升序，否则可能得到错误的结果。*/Polyn AddPolyn(Polyn pa,Polyn pb)/求解并建立多项式a+b，返回其头指针Polyn qa=pa-next;Polyn qb=pb-next;Polyn headc,hc,qc;hc=(Polyn)malloc(sizeof(struct Polynomial);/建立头结点hc-next=NULL;headc=hc;while(qa|qb)qc=(Polyn)malloc(siz

22、eof(struct Polynomial);/malloc()函数为其分配内存空间switch(compare(qa,qb)case 1: /a的指数大于b的指数，a、b多项式不会实现相加运算qc-coef=qa-coef;qc-expn=qa-expn;qa=qa-next;break;case 0: /a的指数等于b的指数，系数和为a、b多项式的系数相加之和，指数即为其两者相同的指数 qc-coef=qa-coef+qb-coef;qc-expn=qa-expn;qa=qa-next;qb=qb-next;break; case -1: /a的指数小于b的指数，a、b多项式不会实现相加运

23、算qc-coef=qb-coef;qc-expn=qb-expn;qb=qb-next;break; /switchif(qc-coef!=0)qc-next=hc-next;hc-next=qc;hc=qc;else free(qc);/当相加系数为0时，释放该结点/whilereturn headc;/AddPolyn/*以下函数实现减法*/*该函数功能:实现两个多项式pa、pb相减，其原理根加法类似，将指数相同的系数相减。与加法不同的是在送在减法中，创建了新的链表来存放结果，并返回该链表的头指针。*/Polyn SubtractPolyn(Polyn pa,Polyn pb)/求解并建立

24、多项式a+b，返回其头指针Polyn h=pb;Polyn p=pb-next;Polyn pd;while(p) /将pb的系数取反p-coef*=-1;p=p-next;pd=AddPolyn(pa,h);for(p=h-next;p;p=p-next) /恢复pb的系数p-coef*=-1;return pd;/SubtractPolyn/*以下函数实现乘法*/*该函数功能:实现两个多项式相乘，A(X) * B(x) 。计算时运用单项式与多项式相乘的法则，然后再次运用单项式与多项式相乘的法则。*/Polyn MultiplyPolyn(Polyn pa,Polyn pb)/求解并建立多项

25、式a*b，返回其头指针(该函数实现乘法)Polyn hf,pf;Polyn qa=pa-next;Polyn qb=pb-next;hf=(Polyn)malloc(sizeof(struct Polynomial);/建立头结点hf-next=NULL;for(;qa;qa=qa-next)for(qb=pb-next;qb;qb=qb-next) pf=(Polyn)malloc(sizeof(struct Polynomial);pf-coef=qa-coef*qb-coef;pf-expn=qa-expn+qb-expn;Insert(pf,hf);/调用Insert函数以合并指数相同

26、的项return hf;/MultiplyPolyn/*主函数实现显示与功能选择*/*该函数功能:main函数用来实现提示使用者输入、显示功能列表、调用其他运算函数实现运算功能。在main（）函数中，定义m、n用来保存两个多项式的项数，pa、pb、pc、pd、pf定义程序所需链表的头指针。在程序开始要求输入两个多项式的项数，随后根据项数创建两个链表以保存多项式，再显示出功能列表后通过if语句来实现功能的选择，从而对整个程序流程进行控制。*/int main()int m,n,flag=0;/m、n为分别为a、b两个多项式的项数Polyn pa=0,pb=0,pc,pd,pf;/定义各式的头指针

27、，pa与pb在使用前付初值NULL/pc头指针所在的多项式用在加法中作为结果，pd用在加法中，pf乘法中printf(*欢迎使用一元多项式运算程序*n);printf(请输入第一个多项式a的项数:);scanf(%d,&m);pa=CreatePolyn(pa,m); /建立第一个多项式aprintf(请输入第二个多项式b的项数:);scanf(%d,&n);pb=CreatePolyn(pb,n); /建立第二个多项式b/输出菜单printf(*n);printf(请选择您要进行的操作：nt1.输出多项式a和bnt2.建立多项式a+bnt3.建立多项式a-bn);printf(t4.计算多项

28、式a*b的值nt5.退出n);for(;flag=0)printf(n);scanf(%d,&flag);if(flag=1)printf(多项式a：);PrintPolyn(pa);printf(多项式b：);PrintPolyn(pb);continue;if(flag=2)pc=AddPolyn(pa,pb);printf(多项式a+b：);PrintPolyn(pc);DestroyPolyn(pc);continue;if(flag=3)pd=SubtractPolyn(pa,pb);printf(多项式a-b：);PrintPolyn(pd);DestroyPolyn(pd);co

29、ntinue;if(flag=4)pf=MultiplyPolyn(pa,pb);printf(多项式a*b：);PrintPolyn(pf);DestroyPolyn(pf);continue;if(flag=5)break;if(flag5) printf(Error!n);continue;/forDestroyPolyn(pa);DestroyPolyn(pb);return 0;7、收获体会通过这次课程设计练习，使我更深刻地理解了对链表的操作，加深了对数据结构的理解和认识。由于自己的知识水平有限，在完成课程设计的过程作查阅了相关资料，学习别人的算法，进行认真的分析，在学习别人的算法的过程中，发现自己的不足并加以改正。计算多项式的加、减、乘法运算，需要用到链表的储存，还要使用到指针等知识，对我以前学到的知识能够进行复习，认识体会到自己的不足之处，在以后的学习中，能够注重于算法的学习。认识到算法在程序设计中的重要性，一个完整的程序总是由若干个函数构成