一元多项式的运算(16页).doc

-一元多项式的运算-第 16 页数据结构课程设计实 验 报 告专业班级： 学 号： 姓 名： 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来表示：Q=(qm,q(m-1)，.，q1，q0)不是一般性，假设吗吗m<n，则两个多想是相加的结果：Rn(X)= Pn(X)+ Qm(X) 很显然，可以对P,Q和R采用顺序存储结构，使得多项式相加的算法定义和实现简单化。然而，在通常的应用中，多项式的次数可能变化很大而且很高，使得顺序存储结构的最大长度很难确定。特别是在处理项数少且次数特别高的情况下，对内存空间的浪费是相当大的。因此，一般情况下，都采用链式存储结构来处理多项式的运算，使得两个线性链表分别表示一元多项式Pn(X)和Qm(X)，每个结点表示多项式中的一项。通过分析多项式的特征，不难看出多项式是由单项式构成的，而每个单项式都具有系数和指数，当系数为0时，该项就是去了意义，在计算机内要表示一个多项式，至少具有以下数据信息：系数信息、指数信息和指向下一个单项式的指针。通过指针，我们就可以把多个单项式连接起来，形成一个多项式。2、任务要求系数定义的是float型，范围是3.4*10-383.4*1038;指数定义的是int型，范围是-2147483648+2147483647；输入多项式系数及指数，系统会自动将系数转化为浮点型。功能：（1）提示输入数据。要求先输入多项式的项数。（2）创建多项式。接收输入的数据，并保存到链表中。（3）显示已经创建好的多项式。（4）实现加、减法运算。（5）.退出程序3、概要设计(1)链表结点的类型定义(2)建立有序链表void CreatPolyn(LinkList &L,int n)(3)多项式链表的相加void AddPolyn(LinkList La,LinkList Lb,LinkList &Lc)(4)多项式链表的输出void printList(LinkList L)4、详细设计(1)链表结点的类型定义 typedef struct /在struct前使用关键字typedef，表示是声明新类型float coef; /系数int expn; /指数DataType; /DataType是新类型typedef struct node /单链表的存储DataType data; /数据域struct node *next; /指向下一个结点ListNode,*LinkList; /ListNode是结点的新类型，LinkList是指向ListNode类型的结点的指针类型(2)建立有序链表 要实现多项式的加法运算，首先要建立多项式的存储结构，每一个一元多项式的存储结构就是一个有序单链表。有序链表的基本操作定义与线性链表有两处不同，一个是结点的查找定位操作LocateNode有所不同，二是结点的插入操作InsertNode不同，这两个操作算法分别如下：/结点的查找定位int LocateNode(LinkList L,DataType e,int &q)ListNode *p=L->next;q=0;/记录结点位置序号while(p&&e.expn<p->data.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(LinkList &L,DataType e,int q)ListNode *s,*p;int i=0;p=L;while(p->next && i<q)p=p->next;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时，将不再提示用户继续输入多项式的系数和指数。建立一个一元多项式的单链表的具体算法如下：/多项式链表的建立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;i<=n;i+)scanf("%f,%d",&e.coef,&e.expn);if(!LocateNode(pa,e,q) /当前链表中不存在该指数项InsertNode(pa,e,q); /调用InsertNode函数插入结点L=pa;(3)多项式链表的相加 根据一元多项式相加的运算规则：对于一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别复制到“和多项式”中相应的位置。根据以上运算规则，其实现算法思路如下：假设pc为指向“和多项式链表”当前尾结点的指针，指针pa和pb分别指向两个多项式中当前进行比较的某个结点，则比较两个结点中的指数项值，有下面三种情况：1.若指针pa所指结点的指数值大于指针pb所指结点的指数值，则取pa指针所指向的结点插入到pc指针所指结点之后，分别修改指针pa和pc，使之指向链表的下一个结点；2.若指针pa所指结点的指数值小于指针pb所指结点的指数值，则取pb指针所指向的结点插入到pc指针所指结点之后，分别修改指针pb和pc，使之指向链表的下一个结点；3.若指针pa所指结点的指数值等于指针pb所指结点的指数值，则将两结点中的系数相加，如果其和数不为零，则修改pa指针所指结点中的系数值，将其结点插入到pc指针所指结点之后，分别修改pa、pb和pc，使之指向各自链表的下一个结点，同时删除并释放指针pb原先指向各自链表的下一个结点；如果和数为零，保存pa和pb所指向的结点，修改pa和pb指针使之指向各自链表的下一个结点，然后释放保存的两个结点。再比较指针pa和pb指向节点中的指数项值，分3种情况进行处理.这样的操作一直继续到pa或pb等于NULL为止。最后将未结束的链表后面剩余的节点连接到pc指针所指向结点之后。上述多项式的相加过程和两个有序链表合并的过程类似，不同之处仅在于多项式的比较多了相等比较后的操作。因此，多项式相加的过程完全可以利用线性链表的基本操作来实现。具体实现多项式相加的算法如下：/多项式链表的相加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;else if(pa->data.expn < pb->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的头结点(4) 多项式链表的输出void printList(LinkList L)函数功能：显示多项式链表。在输出项中使用了条件表达式，当系数项为正数时，在系数前输出一个“+”号，否则输出一个空格，而负数的负号还照常输出，使得输出结果尽量与原多项式的表示形式类似。因此，输出多项式链表的算法实现如下：/多项式链表的输出void printList(LinkList L)ListNode *p;p=L->next;while(p)printf("%c %fx %d",(p->data.coef>0? '+':' '),p->data.coef,p->data.expn);p=p->next;printf("n");源程序代码：#include <stdio.h>#include <stdlib.h>#include <math.h>/多项式链表结点类型定义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(LinkList L,DataType e,int &q)ListNode *p=L->next;q=0;/记录结点位置序号while(p&&e.expn<p->data.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 && i<q)p=p->next;i+;s=(ListNode*)malloc(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;i<=n;i+)scanf("%f,%d",&e.coef,&e.expn);if(!LocateNode(pa,e,q) /当前链表中不存在该指数项InsertNode(pa,e,q); /调用InsertNode函数插入结点L=pa;/多项式链表的输出void printList(LinkList L)ListNode *p;p=L->next;while(p)printf("%c %fx %d",(p->data.coef>0? '+':' '),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->next=pa;pc=pa;pa=pa->next;xpn)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的头结点/主控函数void main()LinkList La,Lb,Lc;int n;printf("输入第一个多项式的项数:");scanf("%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、调试分析此一元多项式的运算程序，只能实现一元多项式的加、减法，不能实现一元多项式的乘法，而且若想计数多个多项式的和或者差的话，必须退出界面重新开始计算。在补充程序里面，解决了程序没有的选择功能表的功能，及其多项式的乘法运算。6. 测试结果输入多项式的项数，并且显示多项式及其两个多项式的和：补充程序：多项式运算程序具有以下基本功能：1界面输出，提示如何输入数据。要求先输入多项式的项数。2创建多项式。接收输入的数据，并保存到链表中。3显示程序的功能表，允许使用者选择运算类型。4显示已经创建好的多项式。5实现加法运算。6实现减法运算。7实现乘法运算。8清除内存内容，销毁创建的链表，退出程序。该程序实现了多项式的创建、多项式的加法、减法、乘法运算以及多项式的清除。源程序代码：#include<stdio.h>#include<malloc.h>/*以下函数实现链表的定义*/*该函数的功能:在计算机内要表示一个多项式，至少以下数据信息-系数信息、指数信息和指向下一个单项式的指针。通过指针，我们就可以把多个单项式连接起来，形式一个多项式.*/typedef struct Polynomialfloat coef; /系数int expn; /指数struct Polynomial *next; /指向下一个结点*Polyn,Polynomial; /Polyn为结点指针类型/*以下函数用来实现链表的顺序排列和合并相同的项 */*该函数的功能:实现链表的顺序排列和合并相同的项。将新的节点p插入到现有链表的后面，并确保多项式的指数expn是升序。将p节点插入到head所指向的链表。在该函数的操作中，要注意指针是如何移动的。*/void Insert(Polyn p,Polyn h)if(p->coef=0)free(p); /系数为0的话释放结点else /如果系数不为0Polyn q1,q2;q1=h;q2=h->next;while(q2&&p->expn<q2->expn) /查找插入位置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(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计数，当i<m时，for语句反复提示用户输入该多项式的每一项的指数和系数，并保存。当i=m时，输入完毕，该链表也创建完毕。Polyn p; /定义一个p链表p=head=(Polyn)malloc(sizeof(struct Polynomial);head->next=NULL;for(i=0;i<m;i+)/使用for语句，控制输入多项式的每一项。当创建的链表长度为m时，将不再提示用户继续输入多项式的系数和指数。p=(Polyn)malloc(sizeof(struct Polynomial);/建立新结点以接收数据,用到分配空间的函数malloc()为新建链表分配空间printf("请输入第%d项的系数与指数:",i+1);scanf("%f %d",&p->coef,&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;/*以下函数实现显示输出多项式* */*该函数的功能:显示多项式链表。在该函数中较复杂的是如何控制链表的输出,尤其是第一项的输出，同时还有符号的控制。在输出第一项时要判断是不是常数项,若是,则不要输出字符x。*/void PrintPolyn(Polyn P) Polyn q=P->next; int flag=1;/项数计数器,flag=1表示为第一项if(!q) /若多项式为空,输出0putchar('0'); printf("n");return;while (q)if(q->coef>0&&flag!=1)/系数大于0且不是第一项putchar('+'); if(q->coef!=1&&q->coef!=-1)/系数非1或-1的普通情况printf("%g",q->coef); if(q->expn=1) putchar('X');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/*在下面的辅助乘法和加法运算*/*该函数功能：判断两个多项式在同一指数下是否有其中一个为系数为0。用来辅助加法和乘法运算。*/int compare(Polyn a,Polyn b)/a、b两个多项式if(a&&b)/a、b多项式均非空if(!b|a->expn>b->expn) /a的指数大于b的指数return 1;else if(!a|a->expn<b->expn) /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相加，并将计算结果存储于新建立的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(sizeof(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多项式不会实现相加运算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)/求解并建立多项式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)/求解并建立多项式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函数以合并指数相同的项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;/定义各式的头指针，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.计算多项式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);continue;if(flag=4)pf=MultiplyPolyn(pa,pb);printf("多项式a*b：");PrintPolyn(pf);DestroyPolyn(pf);continue;if(flag=5)break;if(flag<1|flag>5) printf("Error!n");continue;/forDestroyPolyn(pa);DestroyPolyn(pb);return 0;7、收获体会通过这次课程设计练习，使我更深刻地理解了对链表的操作，加深了对数据结构的理解和认识。由于自己的知识水平有限，在完成课程设计的过程作查阅了相关资料，学习别人的算法，进行认真的分析，在学习别人的算法的过程中，发现自己的不足并加以改正。计算多项式的加、减、乘法运算，需要用到链表的储存，还要使用到指针等知识，对我以前学到的知识能够进行复习，认识体会到自己的不足之处，在以后的学习中，能够注重于算法的学习。认识到算法在程序设计中的重要性，一个完整的程序总是由若干个函数构成的，这些相应的函数体现了算法的基本思想。 经过这次课程设计，我深刻认识到自己在以前的学习数据结构的过程中，还有许多的不足，需要自己以后更加努力学习数据结构，让自己在以后的其他专业课的学习中，不会因为自己没学好数据结构而掉队。在这个寒假里面，学习自己没有好好学到的数据结构的知识。输入第一、二个多项式的项的系数及其指数，再选择要进行的5种操作：