北邮数据结构实验一题目3一元多项式

《北邮数据结构实验一题目3一元多项式》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、表实现，也可以使用顺序表实现。要求：Ø能够实现一元多项式的输入和输出Ø能够进行一元多项式相加Ø能够进行一元多项式相减Ø能够计算一元多项式在x处的值Ø能够计算一元多项式的导数（选作）Ø能够进行一元多项式相乘（选作）Ø编写测试main()函数测试线性表的正确性2.程序分析第11页北京邮电大学信息与通信工程学院2.1存储结构单链表：2.2关键算法分析一、头插法构造单链表：①在堆中建立新结点：Node*s=newNode；②将a[i]写入到新结点的数据域：s->data=data[i]；③修改新结点的指针域：s->next=front-

3、>next；④修改头结点的指针域，将新结点加入到链表中：front->next=s；二、一元多项式相乘1申请三个动态数组coe1、coe2、coe3，其长度为两个多项式最高幂相乘后的幂数；2为coe1与coe2赋初为0；3分别用coe1与coe2分别储存两个多项式的系数，比如说的一个多项式指数为i的系数存在coe1[i]里面，其他没有存过系数的元素均为0（相当于将二项式延长，没有的项则系数为0）；4利用柯西乘积完成多项式相乘，用coe3储存乘积结果，即系数，并且系数不为0的项通过申请动态结构数组来储存，最后构造链表，具体代码：f

4、or(inti=0;i<=m+P.m;i++){coe3[i]=0;for(intj=0;j<=i;j++){coe3[i]+=coe1[j]*coe2[i-j];}if(coe3[i]!=0){n++;}第11页北京邮电大学信息与通信工程学院}element*e3=newelement[n];for(inti=0,j=0;i<=m+P.m;i++){if(coe3[i]!=0){e3[j].coef=coe3[i];e3[j].exp=i;j++;}}C=newPolylist(e3,n);一、一元多项式求和：第一种情况：若p

5、->data.expndata.expn，即A链表当前结点p的指数小于B链表的当前结点q的指数,则p结点保留不变,然后p指向A链表的下一个结点继续进行比较。①p_prior=p；②p=p->next；第二种情况：若p->data.expn＜q->data.expn，即A链表当前结点p的指数大于B链表的当前结点q的指数,则应将ｑ结点加入到Ａ链表ｐ结点之前，然后ｑ指向Ｂ链表的下一个结点，继续进行比较。①p_prior->next=q；②p_prior=q；③q=q->next；④p_prior->next=p；第11页北京邮

6、电大学信息与通信工程学院第三种情况：若p->data.expn＝＝q->data.expn，即A链表当前结点p的指数等于B链表的当前结点q的指数,则两结点为同类项，应将两结点的系数求和，此时又分为两种情况：（ａ）若合并的系数为０，计量同类项抵消，则删除ｐ结点；（ｂ）若合并的系数不为０，将其重新赋予ｐ结点。两结点合并后可删除ｑ结点，并且令ｐ和ｑ分别指向各自的下一个结点继续进行比较。（ａ）若合并的系数为０：①p_prior->next=p->next；②deletep；①p=p_prior->next；②Node*temp=q；③q

7、=q->next；④deletetemp；（ｂ）若合并的系数不为０：①p_prior=p；②p=p->next；③Node*temp=q；④q=q->next；①deletetemp；第四种情况：若ｐ为空且ｑ不为空，则应将ｑ结点及其后续所有结点追加到Ａ链表的最后：p_prior->next=q；第11页北京邮电大学信息与通信工程学院注：减法和加法用的是同一个函数，若是减法则将减数的多项式系数变成相反数，再进行加法运算即刻一、一元多项式求导1初始化工作指针element*p=front->next；2系数：p->coef*=p->

8、exp；3指数：p->exp-=1；4p后移；计算关键算法的时间、空间复杂度：1.头插法构造单链表：O(n)2.求和：O(n)3.求导：O(n)4.乘法：O(n^2)空间复杂度：50%3.程序运行结果1.测试主函数流程：流程图如下图所示：第11页北京邮电大学信息