一元稀疏多项式的计算

1、实验一一元稀疏多项式的计算一、实验目的通过一元稀疏多项式的表示和计算，帮助学生熟练掌握线性表的基本操作，以及用线性链表表示线性表的存储结构和操作的实现。二、实验内容实现一元稀疏多项式的如下运算：(1)两个一元稀疏多项式相加运算(2)两个一元稀疏多项式相减运算(3)两个一元稀疏多项式相乘运算三、实验原理1、一元多项式的逻辑表示一元多项式pn(x)可表示成：Pn(X)=P0+P1x+P2x2+pnxnn+1个系数可用线性表来表示：P0，P1，P2，Pn)其中每一项的指数i隐含在其系数Pi的序号中。一个一元多项式，如果其系数不为0的项相对于其多项式的次数(最大指数)而言要少得多，则称该一元多项式为一

2、元稀疏多项式。对一元稀疏多项式，若采用顺序存储结构，需n+1个元素单元存放系数。当n很大且为零的系数较多时，既浪费存储空间，又浪费运算时间。如：s(x)=1+3x10000+2x20000采用顺序存储分配需20001个元素空间，但只有3个元素有意义。若参与同数量级的加法运算，要运行2000次以上。因此，对一元多项式采用链式存储结构是必然的选择。上例的链表表示形式如图1-1所示。P-口口日-10口-63口1000口寸2口2000口H图1-1：一元稀疏多项式的链表表示示意图2、一元稀疏多项式的链式存储表示结点结构定义如下：typedefstructItemdoublecoef;intexpn;st

3、ructItem*next;Item,*Polyn;3、一元稀疏多项式运算原理设有两个稀疏多项式A和B,其运算原理如下：(1)两个多项式相加(C=A+B)的运算原则：指数相同，系数相加，若不为0，则在结果多项式中构成一新项。指数不同，则两项分别抄入结果多项式中。(2)两个多项式相减(C=AB)的运算原则：指数相同，系数相减，若不为0，则构成一新项。指数不同，对A多项式的项，直接抄入结果多项式中。对B多项式的项，系数符号变换后，再将放入结果多项式中(3)两个多项式相乘(C=AXB)的运算原则用B多项式的每一项分别去乘A多项式的每一项，并将乘得得结果放入结果多项式中。若结果多项式中有指数相同的项，

4、则应把它们合并为一项。1、约定使用带头结点的链表表示一元稀疏多项式。用线性链表表示的一元稀疏多项式中，各结点按指数的升序排列。每个多项式都独立存在，即参与运算的两个多项式的数据不能因运算而受到破坏，加、减、乘运算的结果应相互不受影响。因此，对于每种情况都必须单独建立一个链表进行表示。(4)每一种重复性的操作都要进行确认，以免破坏原有操作的结果。如需要输入A多项式，而A多项式已经存在，这时通过“确认”后再确定是否真正需要输入。2、基本功能(1)多项式的输入(2)两个一元稀疏多项式相加运算：P(x)+Q(x(3)两个一元稀疏多项式相减运算：P(x)-Q(x)(4)两个一元稀疏多项式相乘运算：P(x

5、)XQ(x)(5)多项式打印3、辅助功能(1)菜单选择：将上述功能通过“菜单”形式罗列出来，通过菜单选择进行交互式控制程序运行。(2)插入结点位置查找：确定将一个新结点插入到多项式链表结构中的位置，以保证链表中结点按指数升序排列。(3)交互选择：当出现重复性操作时，提供交互式选择方式，以确定其重复操作是否进行。(4)撤消多项式：释放表示多项式链表中所有结点的存储空间。(5)多项式项插入：将表示多项式中一项的结点插入到链表中给定的位置。(6)判多项式非空：判断某个多项式是否存在。(7)判断两个多项式的当前运算项的关系(指数大于，等于，小于)4、程序结构本程序可以由13个函数组成，其中主函数1个，

6、基本功能函数5个，辅助功能函数7个。函数间的调用关系图1-2所示。图1-2：程序结构示意图5、程序函数(1)主函数：main功能：通过菜单选择控制对系统功能的操作(2)菜单选择函数：menu函数格式：intmenu(void)函数功能：构造功能菜单，并选择下一步要操作的功能。函数参数：无参数。函数返回值：111中的一个序号。可供选择的功能如下：1-createP(x)表示生成P多项式2-createQ(x)表示生成Q多项式3-p(x)+Q(x)表示两多项式相加4-P(x)-Q(x)表示两多项式相减5-p(x)*Q(x)表示两多项式相乘6-printP(x)7-printQ(x)6-printP

7、(x)7-printQ(x)8-printP(x)+Q(x)9-printP(x)-Q(x)10-printP(x)*Q(x)11Quit表示打印Q多项式表示打印两多项式相加的结果表示打印两多项式相减的结果表示打印两多项式相乘的结果表示退出系统，结束程序的运行在运行过程中，输入其中一个序号，即表示下一步执行后面的功能。如输入3，表示执行P(x)+(x)额运算。(3)输入多项式函数：input函数格式：PolynInput(void)函数参数：无参数函数功能：输入多项式各项的系数和指数，生成一个多项式链表。函数返回值：指向一个多项式链表的头指针(4)两多项式相加函数：AddPolyn函数格式Po

8、lynAddPolyn(Polynh1,Polynh2)函数功能：实现两个多项式hl和h2相加。函数参数：Polynhl指向第一个多项式链表的头指针Polynh2指向第二个多项式链表的头指针函数返回值：指向相加后的结果链表的头指针(5)两多项式相减函数：SubtractPolyn函数格式PolynSubtractPolyn(Polynh1,Polynh2)函数功能：实现两个多项式hl和h2相减。函数参数：Polynhl指向第一个多项式链表的头指针Polynh2指向第二个多项式链表的头指针函数返回值：指向相减后的结果链表的头指针(6)两多项式相乘函数：MultPolyn函数格式PolynMult

9、Polyn(Polynh1,Polynh2)函数功能：实现两个多项式hl和h2相乘。函数参数：Polynhl指向第一个多项式链表的头指针Polynh2指向第二个多项式链表的头指针函数返回值：指向相乘后的结果链表的头指针(7)显示多项式函数：Output函数格式：voidOutput(Polynh,char*title)函数功能：输出多项式的完整表示。如：P(x)=1.00+2.50 xA3-3.5xA9函数参数：Polynh一要输出的多项式链表的头指针char*title一字符串，提示要输出一个什么样的多项式，如“P(x)”。函数返回值：无返回值。判断选择函数：Select函数格式：intSe

10、lect(char*str)函数功能：根据str提示的内容判断是执行指定的操作，还是不执行。输入“Y”则表示执行，若输入收”表示不执行。如当P(x)多项式已经产生后，若再选择产生P(x)，这是提示：P(x)isnotEmpty,CreateP(x)again?InputYorN:若输入“丫”则表示重新产生多项式P(x)，若输入“N”表示维持原多项式不变。函数参数：char*str将要确定的内容。函数返回值：1表示执行指定的操作0表示不执行指定的操作(9)插入位置定位函数：InsertLocate函数格式：intInsertLocate(Polynh,intexpn,Item*p)函数功能：确定

11、新结点的插入位置。其插入位置的确定是保证多项式链表按指数递增排列的关键。函数参数：Polynh一要查找的多项式链表的头指针intexpn一新插入项的指数值。Itemp插入位置的前驱结点指针，由该函数的调用而被确定的内容。新结点一定插入到该结点的后面。函数返回值：-1一若指数expn值在某两个结点之间，则返回一1,参数p带回的值为指数值小于expn的结点指针。0若指数expn值等于某结点的指数值，则返回0,参数p带回的值为指数值等于expn的结点指针。1一若指数expn值大于最后一个结点的指数值，则返回1,参数p带回最后一个结点的指针(10)结点插入函数：insert函数格式：voidinser

12、t(Item*pre,Item*p)函数功能：在指定结点pre后插入一个新结点p。函数参数：Item*pre被插入结点的前驱结点Item*p一要插入的新结点函数返回值：无(11)撤消链表函数：Destroy函数格式：voidDestroy(Polynh)函数功能：释放链表所占用的存储空间函数参数：Polynh一被撤消的链表的头指针函数返回值：无(12)判链表非空函数：PolynNotEmpty函数格式：intPolynNotEmpty(Polynh,char*p)函数功能：判断链表是否非空，即代表了一个真正的多项式。函数参数：Polynh一多项式链表的头指针char*p多项式名函数返回值：0链

13、表为空1链表不为空(13)比较多项式两项关系函数：ItemComp函数格式：intItemComp(ItemxItemy)函数功能：根据两个多项式项的指数判断它们的关系。函数参数：Itemx表示多项式项的变量Itemy表示多项式项的变量函数返回值：-1x项的指数小于y项的指数0 x项的指数等于y项的指数1x项的指数大于y项的指数五、部分算法描述两个多项式相加运算的算法参见教科书的描述。两个多项式相减运算算法与多项式相加运算的算法结构一致，只是把Q(x)多项式的结点作为独立的一项时，其系数应改变其正/负号。这里只对两个多项式相乘运算的算法加以描述。两个多项式相乘运算的基本原理是：用Q(x)多项式

14、的每一项分别去乘P(x)多项式的每一项，并将乘得得结果放入结果多项式中。若结果多项式中有指数相同的项，则应把它们合并为一项。这实际上是运用加法运算来实现乘法运算，实现时有两种不同的方法把每次计算的结果与原来的中间结果进行相加。【算法1】基本思想：把Q(x)多项式的每一项分别去乘P(x)多项式的每一项所得到的每一个结果(一个结点)插入到结果多项式中，若结果多项式中无相同指数的项，则生成一个新结点插入；若有相同指数的项，则系数相加。算法如图1-3所示。图1-3两个多项式相乘算法1描述【算法2】基本思想：把Q(x)多项式的每一项分别去乘P(x)多项式得到一个新的多项式，然后把新多项式与结果多项式相加

15、。算法如图3所示。图1-4两个多项式相乘算法2描述七、思考题修改一元多项式相加运算的函数，实现：两个有序表合并为一个有序表。假设具有整数值的集合用有序的线性链表表示，实现求两个集合的联合运算，要求结果集合中不能有两个值相同的元素。八、部分函数代码【说明】：为了使学生掌握复杂程序设计的基本方法和程序的结构，下面给出了几乎所有的辅助函数的程序代码，学生只需要完成稀疏多项式的加、减、乘运算的程序代码编写工作。希望学生通过下面程序代码的阅读、编码、测试和运算，掌握一个完整程序的基本结构和设计一个程序的基本方法。#include#include#includetypedefstructItemdoubl

16、ecoef;intexpn;structItem*next;Item,*Polyn;#defineCreateItem(p)p=(Item*)malloc(sizeof(Item);#defineDeleteItem(p)free(void*)p);/*判断选择函数*/intSelect(char*str)charch;printf(%sn,str);printf(InputYorN:);doch=getch();while(ch!=Y&ch!=y&ch!=N&ch!=n);printf(n);if(ch=Y|ch=y)return(1);elsereturn(0);/*插入位置定位函数*/*

17、插入位置定位函数*/intInsertLocate(Polynh,intexpn,Item*p)Item*pre,*q;pre=h;q=h-next;while(q&q-expnnext;if(!q)*p=pre;return(1);elseif(q-expn=expn)*p=q;return(0);else*p=pre;return(-1);/*插入结点函数*/*插入结点函数*/voidinsert(Item*pre,Item*p)p-next=pre-next;pre-next=p;/*输入多项式*/*输入多项式*/PolynInput(void)doublecoef;intexpn,fl

18、ag;Item*h,*p,*q,*pp;Createltem(h);/产生头结点h-next=NULL;printf(inputcoefandexpn(ifend,expn=-1)n);while(1)scanf(%lf%d,&coef,&expn);/输入多项式的系数和指数if(expn=-1)break;/若指数为1，表示输入结束if(InsertLocate(h,expn,&pp)/返回值非0表示插入新结点CreateItem(p);p-coef=coef;p-expn=expn;insert(pp,p);elseif(Select(hasthesameexpn,Replaceolder

19、value?)pp-coef=coef;/指数相同，替换系数returnh;/*撤消多项式*/*撤消多项式*/voidDestroy(Polynh)Item*p=h,*q;while(p!=NULL)q=p;p=p-next;DeleteItem(q);/*输出多项式*/*输出多项式*/voidOutput(Polynh,char*title)intflag=1;Item*p=h-next;printf(%s=,title);while(p)if(flag)/表示是否是多项式的第一项flag=0;if(p-expn=0)printf(%.2lf,p-coef);elseprintf(%.21f

20、xA%d,p-coef,p-expn);elseif(p-coef0)printf(+);if(p-expn=0)printf(%.2lf,p-coef);elseprintf(%.2lfxA%d,p-coef,p-expn);p=p-next;printf(n);/*判断两个多项式项的关系*/*判断两个多项式项的关系*/intItemComp(Itemx,Itemy)if(x.expnnext,*pb=h2-next,*s,*s0;doublecoef;CreateItem(head);蟹一种：/*CreateItem(s);s=head-next;while(!pa)s=pb;pb=pb-

21、next;s=s-next;DeleteItem(pb);While(!pb)S=pa;Pa=pa-next;S=s-next;DeleteItem(pa);While(pa&pb)While(Itemcomp(pa,pb)=-1)S=pa;Pa=pa-next;S=s-next;While(Itemcomp(pa,pb)=0)s-coef=pa-coef+pb-coef;if(s-coef!=0.0)CreateItem(s0);S0-coef=s-coef;ElseDeleteItem(pa);DeleteItem(pb);s-expn=pa-expn|s-expn=pb-expn;pa=

22、pa-next;pb=pb-next;s=s-next;While(Itemcomp(pa,pb)=1)S=pb;Pb=pb-next;S=s-next;DeleteItem(pa);DeleteItem(pb);*/第二种：CreateItem(s);S=pa;CreateItem(s0);S0=pb;While(!s)Head-next=s;s=s-next;While(!s0)Head-next=s0;S0=s0-next;While(s&s0)Switch(ItemComp(s-expn,s0-expn)Case-1:Head-next=s;S=s-next;Break;Case0:H

23、ead-next-coef=s-coef+s0-coef;If(head-next-coef!=0)Head-next-expn=s-expn+s0-expn;ElseDeleteItem(s);DeleteItem(s0);S=s-next;S0=s0-next;Break;Case1:Head-next=s0;S0=s0-next;Break;*/last-next=NULL;returnhead;*/*/PolynSubtractPolyn(Polynh1,Polynh2)intflag;Item*head,*last,*pa=h1-next,*pb=h2-next,*s,*s0;dou

24、blecoef;CreateItem(head);last=head;if(!pa)head-next-coef=-(pb-coef);head-next-expn=pb-expn;pb=pb-next;If(!pb)Head-next=pa;Pa=pa-next;If(pa&pb)Switch(ItemComp(pa,pb)Case-1:Head-next=pa;Pa=pa-next;Break;Case0:Head-next-coef=pa-coef-pb-coef;If(head-next-coef!=0)Head-next-expn=pa-expn|head-next-expn=pb-

25、expn;ElseDeleteItem(pa);DeleteItem(pb);Pa=pa-next;Pb=pb-next;Pb=pb-next;Break;Case1:Head-next-coef=-(pb-coef);Head-next-expn=pb-expn;Pb=pb-next;Break;If(PolynNotEmpty(h2,*pb)Append(pa,pb);DeleteItem(pb);last-next=NULL;returnhead;/*两多项式多项式相乘*/*两多项式多项式相乘*/PolynMultPolyn(Polynh1,Polynh2)/两个多项式相乘intitem

26、,expn;Item*head,*pa,*pb=h2-next,*s,*pp;doublecoef;CreateItem(head);head-next=NULL;实现两个多项式相乘运算的代码（由学生独立完成）returnhead;/*菜单选择*/*菜单选择*/intmenu(void)intnum;clrscr();printf(%20c1-createP(x)n,);printf(%20c2-createQ(x)n,);printf(%20c3-p(x)+Q(x)n,);printf(%20c4-P(x)-Q(x)n,);printf(%20c5-p(x)*Q(x)n,);printf(%

27、20c6-printP(x)n,);printf(%20c7-printQ(x)n,);printf(%20c8-printP(x)+Q(x)n,);printf(%20c9-printP(x)-Q(x)n,);printf(%20c10-printP(x)*Q(x)n,);printf(%20c11-Quitn,);printf(pleaseselect1,2,3,4,5,6,7,8,9,10,11:);doscanf(%d,&num);while(num11);return(num);/*判断多项式是否存在*/*判断多项式是否存在*/intPolynNotEmpty(Polynh,char

28、*p)if(h=NULL)printf(%sisnotexist!n,p);getchar();return(0);elsereturn(1);/*主函数*/*主函数*/voidmain()intnum;Polynh1=NULL;/p(x)Polynh2=NULL;/Q(x)Polynh3=NULL;/P(x)+Q(x)Polynh4=NULL;/P(x)-Q(x)Polynh5=NULL;/P(x)*Q(x)while(1)num=menu();getchar();switch(num)/输入第一个多项式，若多项式存在，首先撤消然后再输入if(h1!=NULL)if(Select(P(x)isnotEmpty,CreateP(x)again?)Destroy(h1);h1=Input();elseh1=Input();break;/输入第二个多项式，若多项式存在，首先撤消然后再输入if(h2!=NULL)if(Select(Q(x)isnotEmpty,CreateQ(x)again?)Destroy(h2);h2=Input();elseh2=Input();break;/两多项式相加if