《一元多项式的运算》由会员分享，可在线阅读，更多相关《一元多项式的运算（20页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计实 验 报 告专业班级： 学 号： 姓 名： 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 次多项式，同样可以用一个线性表 Q
2、来表示：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(L
3、inkList &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 p
5、b-data.expn)pc-next=pa;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;/插入链表剩
6、余部分free(Lb);/释放 Lb 的头结点(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-
7、next;printf(n);源程序代码：#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 类型的结点的指
8、针类型/结点的查找定位int LocateNode(LinkList 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*)mallo
9、c(sizeof(ListNode);s-data.coef=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,
10、(p-data.coef0? +: ),p-data.coef,p-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
11、-next=pa;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);/释放
12、 Lb 的头结点/主控函数void main()LinkList La,Lb,Lc;int n;printf(输入第一个多项式的项数:);scanf(%d,printf(输入第一个多项式的每一项的系数,指数:n);CreatPolyn(La,n);printf(第一个多项式为:);printList(La);printf(输入第二个多项式的项数:);scanf(%d,printf(输入第二个多项式的每一项的系数,指数:);CreatPolyn(Lb,n);printf(第二个多项式为:);printList(Lb);AddPolyn(La,Lb,Lc);printf(n 相加后的和多项式为 :
13、);printList(Lc);5、调试分析此一元多项式的运算程序，只能实现一元多项式的加、减法，不能实现一元多项式的乘法，而且若想计数多个多项式的和或者差的话，必须退出界面重新开始计算。在补充程序里面，解决了程序没有的选择功能表的功能，及其多项式的乘法运算。6. 测试结果输入多项式的项数，并且显示多项式及其两个多项式的和：补充程序：多项式运算程序具有以下基本功能：1界面输出，提示如何输入数据。要求先输入多项式的项数。2创建多项式。接收输入的数据，并保存到链表中。3显示程序的功能表，允许使用者选择运算类型。4显示已经创建好的多项式。5实现加法运算。6实现减法运算。7实现乘法运算。8清除内存内容
14、，销毁创建的链表，退出程序。该程序实现了多项式的创建、多项式的加法、减法、乘法运算以及多项式的清除。源程序代码：#include#include/*以下函数实现链表的定义*/*该函数的功能:在计算机内要表示一个多项式，至少以下数据信息-系数信息、指数信息和指向下一个单项式的指针。通过指针，我们就可以把多个单项式连接起来，形式一个多项式.*/typedef struct Polynomialfloat coef; /系数int expn; /指数struct Polynomial *next; /指向下一个结点*Polyn,Polynomial; /Polyn 为结点指针类型/*以下函数用来实现
15、链表的顺序排列和合并相同的项 */*该函数的功能:实现链表的顺序排列和合并相同的项。将新的节点 p 插入到现有链表的后面，并确保多项式的指数 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;fr
