下载文档原格式
多项式的加法与乘法一、课题内容和要求给定两个多项式，用程序实现这两个多项式的相加和相乘。
（可以利用单链表法实现）例如给定多项式X+3X 2-4X 3+5X 4和多项式X 2+3X 3-4X 4。
二、需求分析整个程序中有两个大类，项结点的TERM 类和多项式的POL YNOMINAL 的类。
TERM 类用以存放项结点，POL YNOMINAL 类用以构建多项式的每一项。
而在进行多项式的加法和乘法时要进行多次的插入和删除操作，因此采用线性表的链接存储。
主要的实现函数有多项式类的输入输出函数，多项式的相加函数，多项式的相乘函数，几个友元函数。
而多项式类的构造函数和析构函数也是必不可少的。
最后加上主函数即能完成课题内容和要求。
三、概要设计先定义链表类型结点和一元多项式，然后申明各个功能函数，并编写功能函数的算法，然后定义一个主函数，用于调用各个功能函数。
其中输入输出函数由链表进行存储。
其系统结构如图所示：一元多项式的加法乘法运算一元多项式的创建 一元多项式的乘法 一元多项式的加法 一元多项式的消除一元多项式的创建流程图如下：NY（1）一元多项式的创建流程图开 始 创建一个含有n 个链表类型结点的项按降幂分别输入各项系数和指数 系数指数均小0？ 一元多项式创建成功（2）多项式相加流程图开始判断输入的p多项式系数>=0?P q指数相等时系数相加当q的系数大于p，则跳过q->exp大的项当q的系数小于p，则p的系数和指数生成新的节点插入p 进行运算开始给出两个多项式将系数相乘，指数相加将运算结果相加，并输出（3）多项式的相乘流程图四、详细设计在定义多项式类polynominal之前，首先构建一个项结点的c++类Term，用以存放系数coef和指数exp。
具体实现代码如下：class Term{ public:Term(int c,int e);Term(int c,int e,Term* nxt);Term* InsertAfter(int c,int e); //在this指针指示的结点后插入新结点private:int coef;int exp;Term *link;friend ostream &operator<<(ostream &,const Term &); //重载"<<"，输出多项式的一项friend class Polynominal;};Term::Term(int c,int e):coef(c),exp(e){ link=0;}Term::Term(int c,int e,Term *nxt):coef(c),exp(e){ link=nxt;}Term* Term::InsertAfter(int c,int e){ link=new Term(c,e,link); //为新项申请结点的存储单元，并用Term函数将return link; //c,e和this->link的值填入新结点的相应域}其中公有成员函数InsertAfter的功能是建立一个新的项结点，系数为c,指数为e，并将新结点插入调用该函数项结点及其后继结点之间。
设计程序以实现任意两个高次多项式的加法和乘法运算学生姓名：王帆指导老师：张建明摘要本课程设计主要解决任意两个高次多项式的乘法运算。
所设计的数据结构应尽可能节省存储空间，程序的运行时间应尽可能少。
从题目看出所设计的程序应能达到的功能，设计好的程序要满足以上两点。
在数据输入方面可以根据一元高次多项式的特征，从左到右开始，按每一项指数、系数的顺序输入。
这里要留意一个问题，因为要相乘的多项式项数是未知的，所以选择什么样的存储方式在本课程设计中尤为重要，这也是本程序好坏的一个评定。
程序通过调试运行，初步实现了设计目标，并且经过适当完善后，将可以应用在商业中解决实际问题。
关键词高次多项式；加法；乘法；时间复杂度；空间复杂度1 问题分析和任务定义1.1 任务定义设计程序以实现任意两个高次多项式的乘法运算。
要求：（1）所设计的数据结构应尽可能节省存储空间。
（2）程序的运行时间应尽可能少。
从题目看出所设计的程序应能达到的功能，设计好的程序要满足以上两点。
在数据输入方面可以根据一元高次多项式的特征，从左到右开始，按每一项指数、系数的顺序输入。
这里要留意一个问题，因为要相乘的多项式项数是未知的，所以选择什么样的存储方式在课程设计中尤为重要，这也是本程序好坏的一个评定。
设计算法（程序）测试用例：图1-1图1-2图1-1 为正确的输出结果，图1-2为错误的输出结果1.2要解决的问题（1）怎样实现两个多项式的乘法？（2）相乘后若有指数相同的项用什么方法合并？（3）使用什么数据结构来满足尽可能节省存储空间的要求？（4）用什么方法来输出表达式？2概要设计和数据结构的选择2.1数据结构的选择本程序选择的数据结构是单链表，原因如下：链表的定义：（1）链表是有限个具有相同数据类型的数据元素的集合，D={ai/i=1,2,…，n};ai为数据元素。
（2）数据元素之间的关系R={<ai,ai+1>/ai,ai+1∈D}。
（3）数据元素ai 在存储器中占用任意的、连续或不连续的物理存储区域。
《多项式求和》教学设计多项式求和教学设计1. 教学背景多项式求和是高中数学中的重要内容，涉及到多项式的基本性质和求和公式的应用。
学好多项式求和对于后续数学研究以及相关领域的发展具有重要意义。
2. 教学目标- 熟练掌握多项式求和的基本概念和方法；- 理解多项式求和的几何意义；- 能够灵活运用求和公式解决实际问题。
3. 教学内容与步骤3.1 了解多项式求和的概念- 复多项式的定义和运算规则；- 引入多项式求和的概念，解释求和符号的含义。
3.2 解读求和公式- 分析多项式求和的几何意义，引入求和公式的概念；- 以常数项、等差数列和等差数列求和为例，讲解求和公式的推导过程。
3.3 运用求和公式解决问题- 练运用求和公式计算常见的多项式求和问题；- 引导学生积累解题经验，掌握灵活运用求和公式解决实际问题的方法。
4. 教学方法与手段- 结合具体例子和图形解释多项式求和的几何意义；- 注重启发式教学，引导学生主动思考和发现求和公式；- 采用示例讲解和练相结合的方式，提高学生的应用能力。
5. 教学评价与反馈- 通过课堂练、小组讨论、个人作业等方式，及时评价学生对多项式求和的掌握程度；- 针对学生的不足之处，提供针对性的辅导和指导；- 鼓励学生互相交流，促进思维碰撞和知识共享。
6. 教学资源- 多项式求和的教材和参考书籍；- 多媒体课件和演示工具；- 相关的练题和作业。
7. 教学延伸- 教师可引导学生进一步研究多项式求和的应用领域，如概率统计、物理学等；- 鼓励学生自主研究，进行拓展性的实践和研究。
以上是《多项式求和》教学设计的大致内容和步骤，根据实际情况和学生的反馈，适当进行调整和补充，以提高教学效果。
题目：多项式加法多项式加法一、课题概述线性表是一种最简单、最基本，也是最常用的数据结构，其用途十分广泛，例如，用带表头结点的单链表求解一元整系数多项式加法和乘法运算。
现给两个一元整系数多项式，请求解两者之和。
输入两组数据，每一组代表一个一元整系数多项式，有多行组成，其中每一行给出多项式每一项的系数和指数，这些行按指数递减次序排序，每一组结束行为0 -1。
输出三组数据，前两组为一元整系数多项式，最后一组为两个多项式的和。
一元整系数多项式输出形式如下：（1）多项式项4x输出为4X（2）多项式项4x2输出为4X^2（3）第一项系数为正数时，加号不要输出（4）除常系数项外，项系数为1不显式输出，-1输出为-例如，4x3- x2+x-1正确输出形式为4X^3-X^2+X-1，错误输出形式为+4X^3-1X^2+1X-1二、设计与实现1、类的层次关系及核心算法分析：项节点类Trem中定义了三个私有变量，系数coef、指数exp和指向下一个项节点的指针域link。
多项式类Polynominal被声明成项节点类Trem类的友元类。
公有函数InsertAfter构造一个新的项节点，其系数为c指数为e,并将新节点插入在调用该函数的项节点及后继节点之间。
多项式类Polynominal中包含了3个公有成员函数：AddTerms，Output和PolyAdd。
AddTerms函数通过输入流in,输入多项式的各项构造一个多项式的单循环链表；Output函数将多项式按降幂方式送输出流；PolyAdd函数实现将多项式r加到指针this指示的多项式上。
AddTerms函数从输入流in按降幂输入各项（c,e）来构造多项式的单循环链表，当输入（0，-1）是构造过程结束。
Output函数遍历单循环链表将多项式按降幂方式送输出流，它调用项类Trem 上重载的“<<”操作符实现按项输出。
多项式加法，设有多项式p(x)和q(x),分别用单循环链表表示。
两个多项式相加实验报告主要实验内容：根据所学的数据结构中线性结构（线性表）的逻辑特性和物理特性及相关算法，应用于求解一个具体的实际问题----------两个多项式相加一、运行环境：visual C++二、需求分析(1)掌握线性结构的逻辑特性和物理特性(2)掌握线性结构的各种相关算法(3)掌握将算法转换成程序的方法和步骤(4)掌握采用线性结构解决实际问题。
三、概要设计1、抽象数据类型一元多项式的定义如下：ADT Polynomial { 数据对象：D＝{ a i | a i∈TermSet, i=1,2,...,m, m≥0TermSet 中的每个元素包含一个表示系数的实数和表示指数的整数 }数据关系：R1＝{ <a i-1 ,a i >|a i-1 ,a i∈D, i=2,...,n，且a i-1中的指数值＜a i中的指数值}基本操作：CreatPolyn ( &P, m )操作结果：输入 m 项的系数和指数，建立一元多项式 P。
DestroyPolyn ( &P )初始条件：一元多项式 P 已存在。
操作结果：销毁一元多项式 P。
PrintPolyn ( &P )初始条件：一元多项式 P 已存在。
操作结果：打印输出一元多项式 P。
PolynLength( P )初始条件：一元多项式 P 已存在。
操作结果：返回一元多项式 P 中的项数。
AddPolyn ( &Pa, &Pb )初始条件：一元多项式 Pa 和 Pb 已存在。
操作结果：完成多项式相加运算，即：Pa = Pa＋Pb，并销毁一元多项式 Pb。
SubtractPolyn ( &Pa, &Pb )… …} ADT Polynomial2、一元多项式的实现：typedef OrderedLinkList polynomial;// 用带表头结点的有序链表表示多项式结点的数据元素类型定义为:typedef struct { // 项的表示float coef; // 系数int expn; // 指数 term, ElemType;四、详细设计线性表的应用--多项式相加问题多项式的相加操作是线性表处理的典型例子。
8-2 两个多项式求和
两个多项式求和可以通过将它们的对应项相加来实现。
首先，我们需要确保两个多项式按照指数降序排列。
然后，我们将每对对应项相加，得到新的多项式的系数。
如果某个多项式的某一项在另一个多项式中没有对应项，那么它的系数保持不变。
最后，将新的多项式按照指数降序排列，即为所求的和多项式。
举个例子，假设我们有两个多项式：
P(x) = 3x^3 + 2x^2 + 5x + 7。
Q(x) = 2x^3 x^2 + 4x 3。
首先按照指数降序排列：
P(x) = 3x^3 + 2x^2 + 5x + 7。
Q(x) = 2x^3 x^2 + 4x 3。
然后将对应项相加：
P(x) + Q(x) = (3x^3 + 2x^2 + 5x + 7) + (2x^3 x^2 + 4x 3)。
= 3x^3 + 2x^2 + 5x + 7 + 2x^3 x^2 + 4x 3。
= 5x^3 + x^2 + 9x + 4。
因此，P(x)和Q(x)的和为5x^3 + x^2 + 9x + 4。
这就是两个多项式求和的基本步骤。
当然，在实际计算中，可能会涉及更多的项和更高的次数，但基本原理是相同的。
希望这个回答能够帮助你理解如何对两个多项式进行求和。
【2010年3月21日上机实验内容】1、编程练习1和2、逻辑量测试在此基础上，有余力可做本实验第4内容[上机题目1辅助资料]：理解所采用算法、数据结构设计、源程序解题步骤，并能调试出结果。
其关键是找出公共项表达式“term ”2005春省二级计算机试卷(15)题多项式(软件第八章第4道填空题) 66666615555514444133312211s -+-+-=[软件第八章第4道填空题程序分析]①通用公式如下，故程序为双重循环形式。
②方次库函数：书上372页“pow(x,y)”表示的x y 值，其引导的头文件是“#include <math.h>”，其数据类型为“double ”[正确运行结果]0922班林洋同学提供调试程序，经老师优化（占用内存空间小）后程序。
#include <stdio.h>void main(){ double s=1.0,t; int i,sign=1,j=10; for(i=2;i<=6;i++) { j*=10,sign=-sign; t=(j-1)*i/9; s+=sign*1.0/t; }printf("\nSum=%f\n",s); }[上机题目2辅助资料] 教科书P124程序，求π近似值+-+-=71513114π绝对误差和相对误差概念：浮点数的绝对误差是6110-+≤-i i x x根据书P372：库函数fabs()是取浮点数的绝对值，书P45，1e-6代表了数1×10-6if…else和continue、break语句。
此处while(-100)内-100逻辑值均为1π/2=1+1/3+(1/3)*(2/5)+ (1/3)*(2/5)*(3/7)+…软件第八章填空第20题以下程序通过给出的公式计算π的近似值，计算过程在所加项的值小于0.0000000001时终止。
π/6=(1/2)+((1/2)*(1/3)*(1/2)^3)+((1/2*3/4)*(1/5)(1/2)^5)+………业余时间可试用一个主函数改造软件中源程序。
计算机科学与工程学院《算法与数据结构》试验报告[二]专业班级10级计算机工程02 试验地点计算机大楼计工教研室学生学号1005080222 指导教师蔡琼学生姓名肖宇博试验时间2012-4-7试验项目算法与数据结构试验类别基础性（）设计性（）综合性（√）其它（）试验目的及要求（1）熟练掌握链表结构及有关算法的设计；（2掌握用链表表示特定形式的数据的方法，并能编写出有关运算的算法。
成绩评定表类别评分标准分值得分合计上机表现积极出勤、遵守纪律主动完成设计任务30分程序与报告程序代码规范、功能正确报告详实完整、体现收获70分备注：评阅教师：日期：年月日试验内容一、实验目的和要求1、实验目的：（1）掌握用VC++上机调试线性表的基本方法；（2）掌握顺序表的存储结构以及基本运算的实现。
2、实验内容把任意给定的两个一元多项式P(x),Q(x)输入计算机，计算它们的和并输出计算结果。
3、实验要求：用链表实现。
二、设计分析一元多项式可以用单链表表示，结点结构图示如下：coef exp next一元多项式链表的结点结构一元多项式算法伪代码如下：1. 工作指针p、q初始化；2. while（p存在且q存在）执行下列三种情形之一2.1 如果p->exp<q->exp，则指针p后移;2.2 如果p->exp>q->exp，则2.2.1 将结点q插入到结点p之前；2.2.2 指针q指向原指结点的下一个结点；2.3 如果p->exp=q->exp，则2.3.1 p->coef =p->coef+q->coef；2.3.2 如果p->coef ==0，则执行下列操作，否则，指针p后移;2.3.2.1 删除结点p；2.3.2.2 使指针p指向它原指结点的下一个结点；2.3.3 删除结点q；2.3.4 使指针q指向它原指结点的下一个结点；3. 如果q不为空，将结点q链接在第一个单链表的后面；三、源程序代码#include<stdio.h>#include<stdlib.h>#define MAXSIZE 100typedef struct pnode{float coef; //多项式系数int exp; //多项式指数struct pnode *next;}polynode;void Inipnode(polynode *&p) //初始化{p=(polynode *)malloc(sizeof(polynode));p->next=NULL;}void Creatpnode_R(polynode *&p) //尾插法建立头结点{int len=0;polynode *s,*r;p=(polynode *)malloc(sizeof(polynode));r=p;label: printf("请输入您要输入多少个多项式");printf("\n");scanf("%d",&len);if(len<=0){printf("*********************************************************** *");printf("\n");printf("\t\t输入有误! 请重新输入！");printf("\n");printf("*********************************************************** *");printf("\n");goto label;}else{for(int i=0;i<len;i++){s=(polynode *)malloc(sizeof(polynode));label2: printf("请输入第%d项的系数",i+1);scanf("%f",&(s->coef));if(s->coef==0){printf("零输入它干嘛！重新输入！");printf("\n");goto label2;}printf("请输入第%d项的指数",i+1);scanf("%d",&(s->exp));r->next=s;r=s;}r->next=NULL;}}void Dispnode(polynode *p){polynode *s=p->next;if(s==NULL) //如果所有的项都被消去{printf("您输入的多项式为F(a)=0");printf("\n");}else //如果还有多项式{printf("您输入的多项式为F(a)=");while(s!=NULL){if(s->next!=NULL) //如果数据接点不是最终的接点，就要一个加号{printf("%.1fa%d+",s->coef,s->exp);}else //如果数据接点是最终的接点，不要加号{printf("%.1fa%d",s->coef,s->exp);}s=s->next; //指向下一个接点}printf("\n");}}void Addpnode(polynode *polya,polynode *polyb,polynode *&polyc){polynode *r,*p,*q,*m;polyc=(polynode *)malloc(sizeof(polynode)); //用尾插法创建第三个链表polyc->next=NULL;r=polyc;p=polya->next; //p,q 是数据接点q=polyb->next;while(p!=NULL&&q!=NULL){if(p->exp>q->exp){r->next=p;r=p;p=p->next;}else if(p->exp<q->exp){r->next=q;r=q;q=q->next;}else if(p->exp==q->exp){m=(polynode *)malloc(sizeof(polynode));m->next=NULL;m->coef=p->coef+q->coef;m->exp=p->exp;if(m->coef!=0){r->next=m;r=m;}p=p->next;q=q->next;}}while(q!=NULL){r->next=q;q=q->next;}while(p!=NULL){r->next=p;p=p->next;}}void main(){polynode *p1;polynode *p2;polynode *p3;Inipnode(p1);Inipnode(p2);Inipnode(p3);Creatpnode_R(p1);Creatpnode_R(p2);Dispnode(p1);Dispnode(p2);printf("-------------------------------------------------");printf("\n");Addpnode(p1,p2,p3);Dispnode(p3);}四、测试用例（尽量覆盖所有分支）1.正常状态下，输入无错误后的运行程序如下：2.当输入的多项式系数如果为负或者为零时：3.当输入的多项式，有的项为零时，约去该项的情况如图：4．当所有的输入项都为零的时候：5.当两个相加的项数不一样多的时候：五、实验总结先后学习了C/C++,对编程语言基本上有一些了解，但在数据结构试验程序设计过程中还是学到了很多。
1.实验题目设计一种用单链表存储多项式的结构（每个结点存储一项的系数和指数，类型都为int），并编写一个产生多项式链表的函数和一个实现两个多项式相加的函数。
2 .实验内容顺序存储结构的实现。
先输入多项式最高项数，然后按照（系数，指数）的格式输入顺序表类型定义如下：typedef struct term{int coef;int expn;struct term *next;}term,*Polynomial;3．实验要求（1）利用C语言完成算法设计和程序设计。
（2）上机调试通过实验程序。
（3）输入数据，检验程序运行结果。
（4）给出具体的算法分析，包括时间复杂度和空间复杂度。
（5）撰写实验报告。
4.实验步骤与源程序⑴实验步骤首先分析实验内容，要实现多项式求和，必须创建两个函数，然后先建立一个多项式a和多项式b，接着输入每个多项式的系数和指数，再实现多项式a和b的求和将求出的多项式放在多项式a中，最后输出求出的多项式的结果。
⑵源代码#include<stdio.h>#include<stdlib.h>#include<string.h>#include<time.h>#include<malloc.h>/*定义存储结构，用单链表存储多项式，链表中每个结点存储多项式中的一项。
*/typedef struct term{int coef;//定义多项式系数为coefint expn;//定义多项式指数为expnstruct term *next;}term,*Polynomial;void Create_Polynomial(Polynomial *P,int n){ /*建立多项式*/int i;term *t1,*t2;(*P)=(term *)malloc(sizeof(term));(*P)->coef=0;(*P)->expn=0;(*P)->next=NULL;t1=(*P);for(i=0;i<=n;i++){ /*输入每一项的系数和指数*/ t2=(term *)malloc(sizeof(term));scanf("%d,%d",&(t2->coef),&(t2->expn));t1->next=t2;t1=t1->next;}t2->next=NULL;}void Add_Polynomial(Polynomial *a,Polynomial *b){ /*多项式a和多项式b求和，结果存放在a中。
实验2 多项式和线性方程组的求解一、实验目的求解多项式(polynomial)和线性方程组.二、实验内容与要求1. 多项式的表达方式(1)用降幂排列的多项式的系数向量表示【例1.6】对多项式p=x4+2x3－5x+6和s=x2+2x+3，用多项式的系数表示为>>p=[1,2,0,-5,6];>>s=[1,2,3];（2）由根创建多项式>>r=[1,4,8]; %已知多项式的根为（1，4，8）>>p=poly(r)p =1 -13 44 -32>>poly2sym(p)%将多项式的向量表示转变为符号形式ans =x^3-13*x^2+44*x-322. 多项式的加减乘除【例1.9】求例1.6中多项式p，s的和、差、积、商.conv(Convolution,卷积),deconv(deconvolution,去卷积,反褶积)>>p=[1,2,0,-5,6];>>s=[0,0,1,2,3];%多项式加法，向量p，s必须同维，s扩维成s=[0,0,1,2,3]基于MA TLAB的数学实验10>> p+s>>p-s %多项式减法，向量p，s必须同维>>conv(p,s) %求多项式p和s的乘积，也是向量ｐ,ｓ的卷积ans =0 0 1 4 7 1 -4 -3 18>> p=[1,2,0,-5,6];s=[1,2,3];>>[q,r]=deconv(p,s)%求多项式p除以s的商ｑ和余项ｒ，也是向量解卷积运算q =1 0 －3r =0 0 0 1 15即两多项式相除商为x2－3，余项为x+15.3. 求多项式的根compan( companion,同伴, 共事者)格式：r=roots(p) %求多项式p的根，即p(x)=0方程的解.pc=compan(p) %求多项式p的伴随矩阵.r=eig(pc) %多项式p的伴随矩阵的特征值等于多项式p的根.【例】求多项式p=x2＋2x+6的根.解一：>>p=[1,2,6];>>r=roots(p)结果为：r =-1.0000 + 2.2361i-1.0000 - 2.2361i解二：>> pc=compan(p);第一章MA TLAB软件操作实验11>> r1=eig(pc)r1 =-1.0000 + 2.2361i-1.0000 - 2.2361i即多项式p=x2+2x+6的根为一对共轭虚数.4. 多项式的微分和赋值运算der(derivation,导出,微分),val(value价值, 数值)格式：d=polyder(p)%求多项式p的一阶微分.d=polyder(p,s) %求多项式p，s乘积的一阶微分.[q,d]=polyder(p,s)%求多项式p，s商p/s的一阶微分，q为分子，d为分母.y=polyval(p,a) %计算x=a时多项式p的值.【例】求多项式p的一阶导数，求x= 1，3，5时多项式p(x)的值.解：>>p=[1,2,0,-5,6];>>d= polyder(p)结果为：d=4 6 0 -5即多项式p(x)=x4+2x3－5x+6的一阶导数为：4x3+6x2－5.>>x= 1:2:5; %x取3个值>>y=polyval(p,x) %计算对应x的多项式p的3个值结果为：y =4 126 856基于MA TLAB的数学实验125. 非齐次线性方程组求解rref( Reduced row echelon form.)格式：X=A\b %用矩阵左除法求线性方程组AX=b的解.C=[A,b] %由系数矩阵A和常数列向量b构成增广矩阵C.D= rref (C) %将C化成行最简形，则D的最后一列元素就是所求的解. 【例】求线性方程组AX=b的解，其中，A=[2,3,5;3,6,8;6,5,4]，b=[12;34;43].解一：用矩阵左除法求解.>>A=[2,3,5;3,6,8;6,5,4];>>b=[12;34;43];>>R=rank(A)>>X=A\b结果为：R =3X =0.275912.3793-5.1379注意：b是列向量，求解前先检验A是否是满秩方阵.解二：用函数rref求解.>>C=[A,b]>>D=rref(C)结果为：C =2 3 5 123 6 8 346 5 4 43D =第一章MA TLAB软件操作实验131.0000 0 0 0.27590 1.0000 0 12.37930 0 1.0000 -5.1379则D的最后一列元素就是所求的解，同解一结果相同.表1.4 数据格式命令说明。
