北邮数据结构上机一元多项式

《北邮数据结构上机一元多项式》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、北京邮电大学信息与通信工程学院数据结构实验报告实验名称：实验1——线性表学生姓名：班级：班内序号：学号：日期：1．实验要求实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的测试方法学习指针、模板类、异常处理的使用掌握线性表的操作实现方法培养使用线性表解决实际问题的能力实验内容：利用线性表实现一个一元多项式Polynomial;f(x)=a0+a1x+a2x2+a3x3+…+anxn提示：Polynomial的结点结构如下：structterm{floatcoef;\系数intexpn;\指数}；可以使用链表实现，也可以

2、使用顺序表实现具体要求如下：能够实现一元多项式的输入和输出能够进行一元多项式相加能够进行一元多项式相减能够计算一元多项式在x处的值能够计算一元多项式的导数（选作）能够进行一元多项式相乘（选作）编写main()函数测试算法的正确性2.程序分析由于多项式是线性结构，故选择线性表来实现，在这个程序中我采用的是单链表结构，每个结点代表一个项，多项式的每一项可以用其系数和指数唯一的表示。如果采用顺序存储，第22页北京邮电大学信息与通信工程学院那么对于结点的插入和删除的操作会比较麻烦，而且顺序表的结点个数固定，对于可能发生的情况无法很好的处理

3、，而采用链表就会简单许多，还能自由控制链表的长度。本程序完成的主要功能：1、输入和输出：需要输入的信息有多项式的项数，用来向系统动态申请内存；多项式各项的系数和指数，用来构造每个结点，形成链表。输出即是将多项式的内容向屏幕输出。2、多项式相加与相减：多项式的加减要指数相同即是同类项才能实现，所以在运算时要注意判断指数出现的各种不同的情况，分别写出计算方法。将每项运算得到的结果都插入到新的链表中，形成结果多项式。3、多项式在某点的值：由用户输入x的值，然后求出每项的值相加即可。4、多项式的求导运算：多项式的求导根据数学知识，就是将

4、每项的系数乘以指数，将指数减1即可，将每项得到的结果插入到结果多项式的链表中。5、多项式的乘法：根据输入信息八两多项式计算，并输出一个新的多项式。2.1存储结构本程序采用的存储结构是单链表结构，其定义的结点包括三部分：系数、指数以及下一个结点的地址。示意图如下：……coefnexpnnextCoef2exp2nextcoef1exp1nextnextfront2.2关键算法分析1、多项式的输入：自然语言描述：1.设置多项式的项数n；2.按照多项式的项数申请动态结构数组element*e=newelement[n]存储多项式的系数和

5、指数；3.按照指数递增的次序输入各项的系数以及指数，分别存入coef和exp；4.再将输入的系数以及指数赋给每一个结点的coef和exp域；5.利用头插法将每个结点加入链表。·伪代码：1.输入项数n；2.element*e=newelement[n];3.运用for循环，循环n次3.1element*e=newelement[n];3.2cin>>e[i].exp;3.3cin>>e[i].coef;3.4returne;4.运用头插法将结点插入链表。2、多项式的输出·自然语言描述：第22页北京邮电大学信息与通信工程学院1.获取头

6、结点；2.循环n-1次（n为多项式的项数）2.1将指针的指向后移；2.2依照多项式的各种情况，设置输出方式2.2.1系数为1且指数不为1和0，输出Xexpn+；2.2.2系数不为0且指数为0，输出（coef）+；2.2.3系数不为0且指数为1，输出（coef）X+；2.2.4系数不为0和1，指数不为0和1，输出(coef)X(expn)+；3.将指针指向移到最后一个节点。重复2.2中判断，但不输出+号。源代码如下：Node*p=GetFirst()->next;if(p==NULL){cout<<0;}while

7、(p){if(p->data.exp==0){cout<data.coef;}else{cout<data.coef<<"X"<data.exp;}p=p->next;if((p!=0)&&(p->data.coef>0)){cout<<"+";}}3、多项式的相加相减·自然语言描述：1.指针p和q分别指向a和b两个多项式的头结点的下一个节点；2.将结果多项式的项数置为0；3.只有p或q非空，进行以下循环：3.1申请一个term*型的指针d，将其next域赋为NULL；进行判断：1.3.1如果p和q均非空1

8、.3.3.1如果p和q的指数相等将d的系数赋为p、q系数之和，指数不变，将p、q指向后移；1.3.3.2如果p->expn>q->expn复制q到结果多项式（减法系数为q->coef的相反数）1.3.3.3如果p->expnexpn第22页