两个多项式相加

课程名称：数据结构实验名称：两个多项式相加任课教师： 专业： 班级: 学号： _ 姓 名：_ ___ 完成日期：2008年11月10日 一、实验目的： 综合理解和掌握线性表的逻辑特性和物理特性，训练综合应用求解问题的能力。 掌握一元多项式的表示和相加的原理和算法。 二、主要实验内容及要求： 使用VC++语言编写程序，根据所学的数据结构中线性结构（线性表）的逻辑特性和物理特性及相关算法，应用于求解一个具体的实际问题——两个多项式相加，编译运行程序。 三、程序说明：(算法设计思路) 先定义节点term结构、类型及其数据域和指针域；再定义用于创建一个有n个结点的链表的函数 Create(int n)；接着定义比较两个指数大小的函数cmp(polynomial &m,polynomial &n )和求两个多项式的两个系数之和的函数Sum(polynomial &m,polynomial &n)；然后定义求两个多项式相加的函数AddPolyn (polynomial &a,polynomial &b )，其调用了函数cmp(polynomial &m,polynomial &n )和函数Sum(polynomial &m,polynomial &n)；然后再定义主函数main(),调用Create(int n)创建两个要相加的多项式x和y,然后调用AddPolyn ( x,y ), 最后输出两个多项式相加后的结果。 四、实验结果与结论：（经调试正确的源程序和程序的运行结果） 编程员：lghgxu 程序源代码： #include \"stdlib.h\" #include \"stdio.h\" # define OVERFLOW -2 typedef struct term { float coef; //多项式系数 int expn; //多项式指数 struct term *next; } term, *polynomial;

1

polynomial Create(int n)//创建一个n个结点的链表，并给每//个节点数据域赋值 { term *head=NULL, *p, *q;// int i; for(i=0;inext=p; p->next=NULL; q=p; } } return(head);//返回所建链表头基地址 } int cmp (polynomial &m,polynomial &n ) //比较两个指数大小，并返回-1或0或1 { if(m->expnexpn) return -1; else if(m->expn==n->expn) return 0; else return 1; } float Sum(polynomial &m,polynomial &n) //求多项式两个系数之和 { return m->coef+n->coef; } polynomial AddPolyn (polynomial &a,polynomial &b ) //两个多项式相加 { term *ha,*hb,*Pa,*Pb,*p,*L=NULL,*k; ha=Pa=a;Pb=hb=b;

2

while(Pb&&Pb) //当一个多项式的每一项都相加完时，停止相加操作 { p=(polynomial)malloc(sizeof(term)); if(!p) { printf(\"分配内存失败!\"); exit(OVERFLOW); } p->next=NULL; switch(cmp(Pa,Pb))//根据指数大小执行相应操作 { case -1: p->coef=Pb->coef; p->expn=Pb->expn; Pb=Pb->next; free(hb); hb=Pb; break; case 0: p->coef=Sum(Pa,Pb); p->expn=Pb->expn; Pa=Pa->next; free(ha); ha=Pa; Pb=Pb->next; free(hb); hb=Pb; break; case 1: p->coef=Pa->coef; p->expn=Pa->expn; Pa=Pa->next; free(ha); ha=Pa; break; } if(!L) L=k=p; else if(p->coef!=0.0) { k->next=p; k=p; } else free(p); } if(ha)//如果多项式a还有某些项未执行相加操作， //则将其接到结果多项式后面 k->next=ha; if(hb)//如果多项式a还有某些项未执行相加操作， //则将其接到结果多项式后面

3

k->next=hb; return L;//返回结果多项式 } void main(int argc, char* argv[]) { polynomial x,y,p; int m=0,n=0; printf(\"请输入第一个多项式的项数!\\n\"); scanf(\"%d\ printf(\"请输入第一个多项式,必须是标准式,否则相加结果会出错!\\n\\n\"); x=Create(m); printf(\"请输入第二个多项式的项数!\\n\"); scanf(\"%d\ printf(\"请输入第二个多项式,必须是标准式,否则相加结果会出错!\\n\\n\"); y=Create(n); p=AddPolyn (x,y ); printf(\"两个多项式相加成功，其结果如下:\\n\"); while(p)//输出相加所得的多项式 { printf(\"%5.1f\ if(p->expn!=0) printf(\" * X(%d)\ p=p->next; if(p&&p->coef>0.0) printf(\" + \"); } printf(\"\\n\"); } 五、实验中遇到的问题及解决方法：（注：如有则写，无则可省）

4