一元多项式计算.doc

数据结构课内实验实验报告实验1 一元多项式计算1 问题描述： 能够按照指数降序排列建立并输出多项式； 完成两个多项式的相加、相减和相乘,并将结果输出.参考教材P42页上的例2-4定义抽象数据类型,实现多项式的创建、相加、相减、相乘、打印等函数.可以采用链表或数组任意一种结构表示多项式.2 设计思想数学模型的选择在数学上,一个一元多项式Pn<x>可按升幂写成：Pn<x>=a 0+a1 x+a2 x2 +an xn-1 .它由n+1个系数惟一确定,因此,在计算机里,它可用一个线性表P来表示：Pn=<a0,a1,a2,an>每一项的指数i隐含在其系数ai的序号里. 多项式的乘法规则：多次运用单项式与多项式相乘的法则得到的计算时<a+b><m+n>,先把<m+n>看成一个单项式,<a+b> 是一个多项式,运用单项式与多项式相乘的法则,得到<a+b><m+n>=a<m+n>+b<m+n>,然后再次运用单项式与多项式相乘的法则.3 数据结构定义typedef struct Polynomiafloat coef;int expn;struct Polynomial *next;*Polyn,Polynomial;4 系统功能模块介绍系统主要分为:<1 >pare<><2 >insert<><3 >createpolyn<><4 >printpolyn<><5 >addpolyn<><6 >subtractpolyn<><7 >mulpolyn<><8> main<>5 程序清单打印清单# include "stdio.h"# include "malloc.h"typedef struct Polynomialfloat coef;int expn;struct Polynomial *next;*Polyn,Polynomial;/int pare<Polyn a,Polyn b> if<a&&b> if<!b|a->expn>b->expn> return 1; else if<!a|a->expn<b->expn>return -1; else return 0; else if<!a&&b>return -1;/a多项式已空,但b多项式非空elsereturn 1;/b多项式已空,但a多项式非空/pare /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->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 /Polyn CreatePolyn<Polyn head> Polyn p; /定义一个p链表p=head=<Polyn>malloc<sizeof<struct Polynomial>> head->next=NULL; p=<Polyn>malloc<sizeof<struct Polynomial>>/建立新结点以接收数据scanf<"%f %d",&p->coef,&p->expn> while<p->coef!=-100> Insert<p,head> /调用Insert函数插入结点p=<Polyn>malloc<sizeof<struct Polynomial>> /建立新结点以接收数据scanf<"%f%d",&p->coef,&p->expn> printf<"建立成功!nn">return head; /CreatePolyn /void PrintPolyn<Polyn P> Polyn q=P->next; int flag=1; /项数计数器if<!q> /若多项式为空,输出0 putchar<'0'> printf<"n"> return; while <q> if<q->coef>0&&flag!=1> putchar<'+'> /系数大于0且不是第一项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> else if<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"> else printf<"-X%d",q->expn> q=q->next; flag+; /while printf<"n"> /PrintPolyn /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>> switch<pare<qa,qb>> case 1: qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; / 当a->expn > b->expn时,将a这个节点放进新的多项式hc中break; case 0: qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; / 当a->expn=b->expn时,先把系数相加,指数不变,在将这个节点放进新的多项式hc中 case -1: qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break; / 当a->expn < b->expn时,将b这个节点放进新的多项式hc中 /switch if<qc->coef!=0> qc->next=hc->next; hc->next=qc; hc=qc; else free<qc> /当相加系数为0时,释放该结点 /while return headc; /AddPolyn /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 /Polyn MulPolyn<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; /MulPolyn /int main<> Polyn pa=0,pb=0,pc,pd,pf;/定义各式的头指针,pa与pb在使用前付初值NULL /pc头指针所在的多项式用在加法中作为结果,pd用在加法中,pf乘法中int i=1; /菜单变量printf<"建立第一个多项式,输入-100结束:n">pa=CreatePolyn<pa> /建立第一个多项式a printf<"n">printf<"建立第二个多项式,输入-100结束:n">pb=CreatePolyn<pb>printf<"n"> /建立第二个多项式b printf<"多项式A<x>="> /多项式aPrintPolyn<pa>printf<"多项式B<x>="> /多项式bPrintPolyn<pb>while<i!=0>printf<"=n">printf<" 选择计算公式:n">printf<" 1:A<x>+B<x>n">printf<" 2:A<x>-B<x>n">printf<" 3:A<x>*B<x>n">printf<" 0:退出程序!n">printf<"=n">scanf<"%d",&i>switch <i> case 1 : pc=AddPolyn<pa,pb> printf<"多项式A<x>+B<x>="> /多项式a+b PrintPolyn<pc> break; case 2 : pd=SubtractPolyn<pa,pb> printf<"多项式A<x>-B<x>="> /多项式a-b PrintPolyn<pd>break; case 3 :pf=MulPolyn<pa,pb> printf<"多项式A<x>*B<x>="> /多项式a*b PrintPolyn<pf>break;default : return 0; 6 运行与调试分析运行结构截图和调试小结<1>对于多项式的运算的,运算符的输出很重要,一开始多输出一个+,并且当为负数时会输出+-.还有当系数为0时的输出都没有专门考虑.和周围的同学交流一下算法,相互探讨了出现的问题,和解决的方法.讨论中改掉很多不足.使代码更加完善.<2>通过本次试验,我发现自己分析问题不是很全面,忽略掉一些细节.以后分析问题时要仔细考虑,认真分析,避免在细节上犯错误.<3>通过这次实验,我发现自己编程能力相当欠缺,尤其是用链表实现.自己以后要勤加练习.8 / 8