数据结构一元多项式计算

1、 课程设计报告 课程设计题目： 一元多项式计算 学生姓名： 汪世生 专 业： 软件工程 班 级： 1521822z 学 号: 201520180325 指导教师： 徐洪珍 2016年 12月 23日第1页目录(Contents):(1).课程设计任务(2).实验目的 第3页实验要求(1).主菜单运算流程图 第4页程序主流程图(1).主要功能性函数(2).过程 第5页实验过程(1).算法代码：加法，减法，乘法， 降幂算法，合并同类项算法(2) .时间复杂度：以上所有算法(3) .流程图 ： 加法，减法，乘法 第619页.算法思想(1)测试算法：减法，加法，乘法 第2022页.测试结果 第23页.

2、实验体会及心得 第24页.课程设计评分表 第2页一：实验要求1任务：（1）能够按照指数降序排列建立并输出多项式。（2）能够完成两个多项式的相加、相减，并将结果输出；在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图） 、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法； （3）除此任务要求之外；增加了一个多项式相乘的功能。 （4）测试2个多项式：1： 3*X3 +2*X2+X 2：2*X2+X2. 实验目的： （1）掌握链式存储结构方法，熟悉链表的创建。 （2）掌握链表的排序的算法。 （3）掌握链表的插入与删除的算法。 （4）设计合适的算法实现对两

3、个多项式进行相加、相减与相乘的基本运算，并对程序的健壮性进行提高；第3页开始二：程序主流程图 结束是否退出显示运算后的多项式指数相同的项数系数相加指数相同的项数系数相减两个多项式各项相乘，然后对指数相同项合并同类项减法运算乘法运算运算菜单选项创建2个多项式定义函数名称定义结构体 加法运算否否是第4页三：实验过程1 创建以下主要功能性函数 首先要创建以下各个功能性函数，同时提高程序的运算效率，减小时间的复杂度。 /typedef Ststus int;Status Create_polynomial(Linklist & L); /创建多项式的算法Status Sort(Linklist

4、 L,int n); /多项式降幂排序的算法Status Add_polynomial(Linklist L1,Linklist L2); /多项式加法的算法Status Sub_polynomial(Linklist L1,Linklist L2); /多项式减法的算法Status Mul_polynomial(Linklist L1,Linklist L2); /多项式相乘的算法Status Com_polynomial(Linklist L); /合并同类项的算法2 过程 先创建L1， L2两个多项式，调用Sort() 函数进行各项降幂排序；然后调用各个函数进行加法、减法、乘法运算,在运

5、算的时候得到的每个非零项存储在L3中，再对得到的L3进行输出到显示屏上。第5页四：算法思想1 主要算法 Mul_polynomial(Linklist L1,Linklist L2); /多项式相乘的算法 Add_polynomial(Linklist L1,Linklist L2); /多项式加法的算法 Sub_polynomial(Linklist L1,Linklist L2); /多项式减法的算法 Sort(Linklist L,int n); /多项式降幂排序的算法 Com_polynomial(Linklist L); /合并同类项的算法2一元多项式的乘法运算L1*L2=L3已知L

6、1，L2先从其中一个多项式的第一项开始分别与第二个多项式的每一项相乘，系数相乘指数相加；此算法采用嵌套while()循环，先从一个多项式的头结点p开始与第二个多项式的每一项相乘，将相乘后的各个非零数据建立新的结点插入到新的L3链表中，直到第一个多项式p=NULL的时候结束。然后对相乘后的数据进行合并同类项，也就是指数相同的项系数相加，这里的算法主要运用删除结点的算法，对指数相同的的项系数相加，然后删除后一个结点。（1） 乘法运算流程图（下页）：第6页已知两个多项式L1与L2 输出未合并同类项的相乘后的多项式调用Mul_poly()函数进行多项式相乘对相乘后的多项式调用Com_poly()函数合

7、并同类项其他运算输出合并同类项后的相乘后的多项式退出？否是退出？否是结束（2）乘法运算算法的代码：其时间复杂度为: T(n)=O(L1*L2)，L1与L2分别为两项多项式的项数。 Status Mul_polynomial(Linklist L1,Linklist L2) /多项式相乘int a=0,n=0; /a是一个哨兵，n用于统计相乘后的项数Linklist p1,p2,p; Linklist L3; /L3用于存储相乘后的多项式L3=(Linklist)malloc(sizeof(LNode);L3->next=NULL;第7页p1=L1;p1=p1->next;p2=L2

8、;p2=p2->next;while(p1!=NULL)while(p2!=NULL)n+; p=(Linklist)malloc(sizeof(LNode);p->coef=p1->coef*p2->coef;p->expn=p1->expn+p2->expn;p->next=L3->next;L3->next=p;p2=p2->next;p1=p1->next;p2=L2->next;Sort(L3,n); /对相乘后的多项式调用Sort()降幂函数cout<<"两多项式相乘为(未合并同类项

9、)"Show_polynomial(L3); /对相乘后的多项式输出Com_polynomial(L3,n); /调用Com_poly()函数合并同类项cout<<"两多项式相乘 (合并同类项后)显示如下:n"L3=L3->next;while(L3) /对相乘后的多项式输出if(L3->coef!=0)if(L3->coef)>0 && a!=0)第8页cout<<" + "cout<<L3->coef<<"*X"<<

10、L3->expn;elsecout<<" "<<L3->coef<<"*X"<<L3->expn;L3=L3->next;a+;cout<<endl;return OK;3 一元多项式加法运算 L1+L2=L3 它从两个多项式的头部开始，两个多项式L1，L2的某一项都不为空时，如果指数相等的话，系数就应该相加；相加的和不为零的话，用头插法建立一个新的节点插入到L3中。p1的指数小于p2的指数的话就应该复制p2的节点到L3中。P1的指数大于p2的指数的话，就应该复p1节点到

11、L3中。当L2多项式空，L1多项式不为空时，将L1剩余项插入到L3中。当L1多项式空，第L2多项式不为空时，将L2剩余项插入到L3中。（1）加法运算流程图（后页）：第9页已知两个多项式L1与L2调用Add_poly()函数进行相加 输出相加后的多项式其他运算是否退出是否退出否否是是结束 （2）加法运算算法代码:其时间复杂度 T(n)=O(L1+L2) ，L1与L2各为两个多项式的项数。Status Add_polynomial(Linklist L1,Linklist L2) /多项式的加法L1+L2int a=0,n=0;Linklist p,p1,p2,pd;Linklist L3; /用

12、于存储相加后的多项式p1=L1->next;p2=L2->next;L3=(Linklist)malloc(sizeof(LNode); L3->next=NULL;while(p1!=NULL && p2!=NULL)第10页if(p1->expn<p2->expn) /L2项中指数大于L1项中指数，插入L2项n+; p=(Linklist)malloc(sizeof(LNode);p->coef=p2->coef;p->expn=p2->expn;p->next=L3->next;L3->next

13、=p;p2=p2->next;else if(p1->expn>p2->expn) /L1项中指数大于L2项中指数，插入L1项n+; p=(Linklist)malloc(sizeof(LNode);p->coef=p1->coef;p->expn=p1->expn;p->next=L3->next;L3->next=p;p1=p1->next;else /L2项中指数等于L1项中指数，系数相加pd=(Linklist)malloc(sizeof(LNode);pd->coef=p1->coef+p2->

14、coef;pd->expn=p1->expn;if(pd->coef!=0)n+;p=(Linklist)malloc(sizeof(LNode);第11页p->coef=pd->coef;p->expn=pd->expn; p->next=L3->next;L3->next=p;p1=p1->next;p2=p2->next;elsep1=p1->next;p2=p2->next;delete pd;while(p1!=NULL) /插入L1剩余项p=(Linklist)malloc(sizeof(LNode

15、);p->coef=p1->coef;p->expn=p1->expn;p->next=L3->next; L3->next=p;p1=p1->next;if(p2!=NULL) /插入L1剩余项p=(Linklist)malloc(sizeof(LNode);p->coef=p2->coef;p->expn=p2->expn;p->next=L3->next;第12页 L3->next=p;p2=p2->next;cout<<"相加后多项式为:"L3=L3->

16、next; while(L3)if(L3->coef)>0 && a!=0)cout<<" + "cout<<L3->coef<<"*X"<<L3->expn;elsecout<<" "<<L3->coef<<"*X"<<L3->expn;L3=L3->next;a+;cout<<endl;return OK; 4一元多项式的减法运算L1-L2=L3

17、它从两个多项式的头部开始，两个多项式L1，L2的某一项都不为空时，如果指数相等的话，系数就应该相减；相减的值不为零的话，用头插法建立一个新的节点插入到L3中。p1的指数小于p2的指数的话就应该复制p2的节点到L3中，并且该项系数取相反数。P1的指数大于p2的指数的话，就应该复p1第13页节点到L3中。当L2多项式空，L1多项式不为空时，将L1剩余项插入到L3中。当L1多项式空，第L2多项式不为空时，将L2剩余项插入到L3中，并把所有项系数取相反数。已知两个多项式L1与L2（1）减法运算流程图：调用Sub-poly()函数进行相减 其他运算输出相减后的多项式是否退出否否是否退出 是是 结束（2）

18、减法运算算法代码：其时间复杂度为 T(n)=O(L1+L2) ，L1与L2各为两个多项式的项数。Status Sub_polynomial(Linklist L1,Linklist L2) /多项式的减法L1-L2 int a=0,n=0; /a是一个哨兵，n用于统计项数Linklist p,p1,p2,pd;第14页p1=L1->next;p2=L2->next;L3=(Linklist)malloc(sizeof(LNode); /用于存储相减后的多项式L3->next=NULL;while(p1!=NULL && p2!=NULL)if(p1->e

19、xpn<p2->expn) /L2项中指数大于L1项中指数，插入L2项 ，且系数取相反数 n+;p=(Linklist)malloc(sizeof(LNode);p->coef=-(p2->coef);p->expn=p2->expn;p->next=L3->next;L3->next=p;p2=p2->next;else if(p1->expn>p2->expn) /L1项中指数大于L2项中指数，插入L1项 n+;p=(Linklist)malloc(sizeof(LNode);p->coef=p1->

20、coef;p->expn=p1->expn;p->next=L3->next;L3->next=p;p1=p1->next;else /L2项中指数等于L1项中指数，系数相加第15页pd=(Linklist)malloc(sizeof(LNode);pd->coef=p1->coef-p2->coef;pd->expn=p1->expn;if(pd->coef!=0)n+;p=(Linklist)malloc(sizeof(LNode);p=pd; p->next=L3->next; L3->next=p

21、;p1=p1->next;p2=p2->next;elsep1=p1->next;p2=p2->next;delete pd;while(p1!=NULL) /L1非空，插入剩余项p=(Linklist)malloc(sizeof(LNode);p->coef=p1->coef;p->expn=p1->expn;p->next=L3->next;L3->next=p;p1=p1->next;第16页while(p2!=NULL) /L2非空，插入剩余项，且系数取相反数p=(Linklist)malloc(sizeof(LN

22、ode);p->coef= -(p2->coef);p->expn=p2->expn;p->next=L3->next;L3->next=p;p2=p2->next;cout<<"相减后多项式为:"L3=L3->next; while(L3)if(L3->coef)>0 && a!=0)cout<<" + "cout<<L3->coef<<"*X"<<L3->expn;elsecou

23、t<<" "<<L3->coef<<"*X"<<L3->expn;L3=L3->next;a+;cout<<endl;return OK;第17页5. 对各个多项式进行降幂排序的算法 时间复杂度为: T(n)=O(n*n) ,n为多项式L的项数。Status Sort(Linklist L,int n) /多项式降幂的算法int a;float b;Linklist p;p=L;p=p->next;for(i=1;i<n;i+)for(j=i;j<n;j+)

24、if(p->expn)<(p->next->expn)a=p->expn; /交换指数p->expn=p->next->expn; p->next->expn=a;b=p->coef; /交换系数p->coef=p->next->coef;p->next->coef=b;p=p->next;p=L->next;return OK;第18页6. 合并同类项算法 注意:这个算法只进行一次合并同类项，需要在这个函数外加一个for循环，最 大次数为这个多项式的项数。 时间复杂度为: T(n)=O

25、(n*n)，n为多项式L的项数 Status Com_polynomial(Linklist L,int n) /对多项式进行合并同类项Linklist p;int i;for(i=0;i<n;i+) /最多有n项相同，n为项数p=L;p=p->next;while(p->next) if(p->expn=p->next->expn) /若指数相同，则系数相加，删除后一项p->coef=p->coef+p->next->coef; p->next=p->next->next;p=p->next;elsep=p->next;return OK; 第19页五：测试结果1 创建多项式；用户从键盘输入项数，然后输入每个项的系数与指数创建两个多项式 L1: 3*X3+2*X2+X L2: 2*X2+X2 显示这两个多项式