实验一一元多项式的表示和相减、相乘
一、实验目的
1.掌握链表的存储方式
2.掌握一元多项式的存储及运算。
二、实验内容
已知一元多项式P(x)和Q(x)已存在，求P(x)-Q(x)和P(x)* Q(x)并输出。
要求：
1.通过键盘随机输入两多项式P(x)和Q(x)的内容。
2.输出结果要有P(x)和Q(x)的以及它们的差P(x)-Q(x)和乘积P(x)* Q(x)。
三、实验步骤：
1.创建一元多项P(x)和Q(x)。
2.求P(x)-Q(x)，P(x)* Q(x)。
3.输出P(x)、Q(x)、P(x)-Q(x)，P(x)* Q(x)。
四、算法说明
首先，定义一元多项式的存储方式，然后从键盘输入P(x)和Q(x)对应多项式的各对系数和指数，建立相应的一元多项式
五、测试结果参考下图
多项式相减
多项式相乘
六、源代码
1.多项式的相减
# include
# include
typedef struct{
float coef; //系数
int expn; //指数
}ElemType;
typedef struct LNode{ //结点类型
ElemType data;
struct LNode *next;
}*LinkList;
void MakeNode(LinkList &s,ElemType e){ //生成结点
s=(LinkList)malloc(sizeof(LNode));
s->data=e;
}
void InsAfter(LinkList p,LinkList s){
//插入结点
s->next=p->next;
p->next=s;
}
int compare(ElemType e1,ElemType e2){
//比较
if(e1.expn>e2.expn)
return 1;
else if(e1.expn return -1; return 0; } void OrderInsert(LinkList &L,ElemType e,int(*compare)(ElemType,ElemType)){ //有序插入 LinkList p=L,q=p->next,s; while(q){ int n=compare(e,q->data); if(n<0){ MakeNode(s,e); InsAfter(p,s);break; } else if(n==0) { q->data.coef=q->data.coef+e.coef; if(q->data.coef==0){p->next=q->next;free(q);} break; } p=p->next;q=p->next; } if(q==NULL) { MakeNode(s,e); InsAfter(p,s); //最大，放在最后一个位置 } } void InitList(LinkList &L){ //初始化 L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; } void SetCurElem(LinkList &p,ElemType e){ //设置结点p->data.coef=e.coef; p->data.expn=e.expn; } void CreatePolyn(LinkList &L,int m){ InitList(L); ElemType e; e.coef=0.0; e.expn=-1; SetCurElem(L,e);//设置头结点的数据元素 printf("请输入%d对多项式的值：\n",m); for(int i=1;i<=m;i++){ scanf("%f%d",&e.coef,&e.expn); //输入值 OrderInsert(L,e,compare); } } void show(LinkList L){ //输出方法 LinkList p=L->next; if(p){ //第一个输出 printf("%.2fX^%d",p->data.coef,p->data.expn); p=p->next; } while(p){ if(p->data.coef>0) printf("+"); printf("%.2fX^%d",p->data.coef,p->data.expn); p=p->next; } printf("\n"); } void ListDestroy(LinkList &L){ //销毁 LinkList p=L,q; while(p){ q=p; p=p->next; free(q); } } void subtract(LinkList L1,LinkList L2,LinkList &L3){ //多项式相减 ElemType e; InitList(L3); e.coef=0.0; e.expn=-1; SetCurElem(L3,e);//设置头结点的数据元素 LinkList p1=L1->next,p2=L2->next,q;//r1始终指向新建链表的尾部,p1和p2表示当前结点 while(p2) { p2->data.coef=-p2->data.coef; p2=p2->next; } p2=L2->next; while(p1&&p2){ int n=compare(p1->data,p2->data); switch(n){ case -1:{OrderInsert(L3,p1->data,compare);p1=p1->next;break;} //L1中的值小，插入之 case 1:{OrderInsert(L3,p2->data,compare);p2=p2->next;break;} //L2中的值小，插入之 case 0:{ //相同 e.coef=p1->data.coef+p2->data.coef; e.expn=p1->data.expn; if(e.coef!=0){OrderInsert(L3,e,compare);} p1=p1->next;p2=p2->next; break; } } } if(p1) {OrderInsert(L3,p1->data,compare);p1=p1->next;} //添加L1 else if(p2) {OrderInsert(L3,p2->data,compare);p2=p2->next;} //添加L2 } LinkList FindThan( LinkList X, LinkList L ) { LinkList Tmp; Tmp = L; while( Tmp->next != NULL && Tmp->next->data.expn >= X->data.expn ) { Tmp = Tmp->next; } return Tmp; } int main(){ LinkList L1,L2,L3,L4; int m,n; printf("请输入多项式P(X)的项数："); scanf("%d",&m); CreatePolyn(L1,m); printf("多项式P(X)为：\n"); show(L1); printf("请输入多项式Q(X)的项数："); scanf("%d",&n); CreatePolyn(L2,n); printf("多项式Q(X)为：\n"); show(L2); subtract(L1,L2,L3); printf("多项式P(X)-Q(X)为：\n"); show(L3); return 0; } 2.多项式的相乘 # include # include typedef struct{ float coef; //系数 int expn; //指数 }ElemType; typedef struct LNode{ //结点类型 ElemType data; struct LNode *next; }*LinkList; void MakeNode(LinkList &s,ElemType e){ //生成结点 s=(LinkList)malloc(sizeof(LNode)); s->data=e; } void InsAfter(LinkList p,LinkList s){ //插入结点 s->next=p->next; p->next=s; } int compare(ElemType e1,ElemType e2){ //比较 if(e1.expn>e2.expn) return 1; else if(e1.expn return -1; return 0; void OrderInsert(LinkList &L,ElemType e,int(*compare)(ElemType,ElemType)){ //有序插入 LinkList p=L,q=p->next,s; while(q){ int n=compare(e,q->data); if(n<0){ MakeNode(s,e); InsAfter(p,s);break; } else if(n==0) { q->data.coef=q->data.coef+e.coef; if(q->data.coef==0){p->next=q->next;free(q);} break; } p=p->next;q=p->next; } if(q==NULL) { MakeNode(s,e); InsAfter(p,s); //最大，放在最后一个位置 } } void InitList(LinkList &L){ //初始化 L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; void SetCurElem(LinkList &p,ElemType e){ //设置结点p->data.coef=e.coef; p->data.expn=e.expn; } void CreatePolyn(LinkList &L,int m){ InitList(L); ElemType e; e.coef=0.0; e.expn=-1; SetCurElem(L,e);//设置头结点的数据元素 printf("请输入%d对多项式的值：\n",m); for(int i=1;i<=m;i++){ scanf("%f%d",&e.coef,&e.expn); //输入值 OrderInsert(L,e,compare); } } void show(LinkList L){ //输出方法 LinkList p=L->next; if(p){ //第一个输出 printf("%.2fX^%d",p->data.coef,p->data.expn); p=p->next; } while(p){ if(p->data.coef>0) printf("+"); printf("%.2fX^%d",p->data.coef,p->data.expn); p=p->next; } printf("\n"); } void ListDestroy(LinkList &L){ //销毁 LinkList p=L,q; while(p){ q=p; p=p->next; free(q); } } void Multiply(LinkList L1,LinkList L2,LinkList &L3){ //多项式相乘 ElemType e; InitList(L3); e.coef=0.0; e.expn=-1; SetCurElem(L3,e);//设置头结点的数据元素 LinkList p1=L1->next,p2=L2->next,q;//r1始终指向新建链表的尾部,p1和p2表示当前结点 while(p1){ p2=L2->next; while(p2){ e.coef=p1->data.coef*p2->data.coef; e.expn=p1->data.expn+p2->data.expn; OrderInsert(L3,e,compare); p2=p2->next; } p1=p1->next; } } int main(){ LinkList L1,L2,L3; int m,n; printf("请输入多项式P(X)的项数："); scanf("%d",&m); CreatePolyn(L1,m); printf("多项式P(X)为：\n"); show(L1); printf("请输入多项式Q(X)的项数："); scanf("%d",&n); CreatePolyn(L2,n); printf("多项式Q(X)为：\n"); show(L2); Multiply(L1,L2,L3); printf("多项式P(X)*Q(X)为：\n"); show(L3); return 0; } 七、分析总结 本程序从源代码开始经过多次调试，一开始创建多项式并没有遇到什么问题，但是减法开始遇到问题，好在经过调试和反复检验后问题都得以解决，在多项式相加的基础上修改，相减和相乘就容易得多。相减主要是整体把另一个多项式前加一个负号，总的运算还是和相加一样。而相乘，需要两个循环，一个多项式中的一个单项式与第二个多项式中的各个单项式相乘，再回上去第一个多项式的第二个单项式与第二个多项式中的各个单项式相乘，如此循环。全部相乘完毕之后，形成第三个多项式，还要比较各系数进行合并，这个操作在之前多项式相加中用到过，可以调用函数。相减与相乘的一个共同点是都要比较各系数进行合并，用 实验一一元多项式的表示和相减、相乘 一、实验目的 1.掌握链表的存储方式 2.掌握一元多项式的存储及运算。 二、实验内容 已知一元多项式P(x)和Q(x)已存在，求P(x)-Q(x)和P(x)* Q(x)并输出。 要求： 1.通过键盘随机输入两多项式P(x)和Q(x)的内容。 2.输出结果要有P(x)和Q(x)的以及它们的差P(x)-Q(x)和乘积P(x)* Q(x)。 三、实验步骤： 1.创建一元多项P(x)和Q(x)。 2.求P(x)-Q(x)，P(x)* Q(x)。 3.输出P(x)、Q(x)、P(x)-Q(x)，P(x)* Q(x)。 四、算法说明 首先，定义一元多项式的存储方式，然后从键盘输入P(x)和Q(x)对应多项式的各对系数和指数，建立相应的一元多项式 五、测试结果参考下图 多项式相减 多项式相乘 六、源代码 1.多项式的相减 # include void InsAfter(LinkList p,LinkList s){ //插入结点 s->next=p->next; p->next=s; } int compare(ElemType e1,ElemType e2){ //比较 if(e1.expn>e2.expn) return 1; else if(e1.expn 中国计量学院实验报告 实验课程：算法与数据结构实验名称：一元二项式班级：学号： 姓名：实验日期： 2013-5-7 一．实验题目： ①创建2个一元多项式 ②实现2个多项式相加 ③实现2个多项式相减 ④实现2个多项式相乘 ⑤实现2个多项式相除 ⑥销毁一元多项式 实验成绩：指导教师： 二．算法说明 ①存储结构：一元多项式的表示在计算机内可以用链表来表示，为了节省存储 空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。 ②加法算法 三．测试结果 四．分析与探讨 实验数据正确，部分代码过于赘余，可以精简。 五．附录：源代码#include<> #include<> #include<> typedef struct Polynomial { float coef; int expn; struct Polynomial *next; }*Polyn,Polynomial; 出多项式a和b\n\t2.多项式相加a+b\n\t3.多项式相减a-b\n"); printf("\t4.多项式相除a*b\n\t5.多项式相除a/b\n\t6.销毁多项式\n"); printf("\t7.退出 \n*********************************** ***********\n"); printf("执行:"); scanf("%d",&flag); switch(flag) { case(1): printf("多项式a：");PrintPolyn(pa); printf("多项式b：");PrintPolyn(pb);break; case(2): pc=AddPolyn(pa,pb); printf("多项式a+b：");PrintPolyn(pc); DestroyPolyn(pc);break; case(3): pd=SubtractPolyn(pa,pb); printf("多项式a-b：");PrintPolyn(pd); DestroyPolyn(pd);break; case(4): pf=MultiplyPolyn(pa,pb); printf("多项式a*b：");PrintPolyn(pf); DestroyPolyn(pf);break; case(5): DevicePolyn(pa,pb); break; case(6): DestroyPolyn(pa); DestroyPolyn(pb); printf("成功销毁2个一元二项式\n"); printf("\n接下来要执行的操作:\n1 重新创建2个一元二项式 \n2 退出程序\n"); printf("执行:"); scanf("%d",&i); if(i==1) { // Polyn pa=0,pb=0,pc,pd,pf;//定义各式的头指针，pa与pb在使用前付初值NULL printf("请输入a的项数:"); scanf("%d",&m); pa=CreatePolyn(pa,m);// 建立多项式a printf("请输入b的项 一元多项式求和——链表编程 一．实验名称：一元多项式求和——链表编程。 二．实验环境：Windows Xp ,Vc++6.0。 三．实验目的： 1.掌握一元多项式的链表式存储算法； 2.掌握链表的结构定义； 3.采用尾插法生成单链表。 四．实验内容： 1.一元多项式的表示： 一元多项式可按升幂的形式表示为 12012()n e e e n n P x p p x p x p x =++++…… 其中：i e 为第i 项的指数，i p 是指数i e 的项的系数，且 121i n e e e e <=<=<=<=<=<=……。 则多项式()n P x 可以用一个线性表P 来表示：01(,)m P p p p =, ；同理，多项式 ()n Q x 可表示为01(,,)n Q q q q =…（m 一元多项式的计算—加，减 摘要(题目)一元多项式计算 任务：能够按照指数降序排列建立并输出多项式； 能够完成两个多项式的相加、相减，并将结果输入； 目录 1.引言 2.需求分析 3.概要设计 4.详细设计 5.测试结果 6.调试分析 7.设计体会 8.结束语 一:引言: 通过C语言使用链式存储结构实现一元多项式加法、减法和乘法的运算。按指数 降序排列。 二：需求分析 建立一元多项式并按照指数降序排列输出多项式，将一元多项式输入并存储在内存中，能够完成两个多项式的加减运算并输出结果 三：概要设计 存储结构：一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。 1．单连表的抽象数据类型定义： ADT List{ 数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系：R1={ 一元多项式求和问题的研究与实现 学生姓名：指导老师： 摘要在数学上，一个一元多项式可按升幂表示为：A(x)=a0+a1x+a2x2+……+anxn，它由n+1个系数唯一确定，一元多项式求和实质上是合并同类项的过程。在实际应用中，多项式的指数可能很高且变化很大，在表示多项式的线性表中就会存在很多零元素。因此，采用单链表来存储一个一元多项式的每一个非零项的系数和指数，即每一个非零项对应单链表中的一个结点，且单链表按指数递增有序排列，就可实现两个一元多项式求和问题。程序通过调试运行，能基本达到设计要求，解决问题。 关键词数据结构；一元多项式；单链表；结点 1 引言 一个一元多项式可按升幂表示为：A(x)=a0+a1x+a2x2+……+a n x n，它由n+1个系数唯一确定。因此，可以用一个线性表(a0，a1，a2，……，an)来表示，每一项的指数i隐含在其系数ai的序号里。若有A(x)= a0+a1x+a2x2+……+a n x n和B(x)=b0+b1x+b2x2+……+b m x m，一元多项式求和也就是求A(x)=A(x)+B(x)，这实质上是合并同类项的过程。 1.1 设计目的 设计合理数据结构表示一元多项式，并设计高效算法实现两个一元多项式相加。 1.2 设计要求 本课程设计要求用C++实现两个一元多项式的求和问题，用带头结点的单链表村存储多项式。基本功能要求如下： 1．输入并建立多项式，输入形式为整数序列n，x1，y1，x2，y2，……，x n，y n。其中n是多项式的项数，x i和y i分别是第i项的系数和指数。 2．输出多项式，按指数升序排列。 3．多项式A(x)和B(x)相加，建立多项式A(x)+B(x)，输出相加的多项式，形式为类数学表达式。 2 需求分析 2.1 输入形式和输入值的范围 从键盘依次输入两个多项式的项数，系数和指数。系数为任意整数，项数和指数为大于等于0的整数。 2.2 输出形式 从屏幕输出，显示用户输入的多项式，并显示两多项式相加后的多项式和值。2.3 时间性能分析 所谓时间性能是指实现基于某种存储结构的基本操作（即算法）的时间复杂度。 一、设计题目 一元多项式的加法、减法、乘法的实现。 二、主要内容 设有一元多项式A m(x)和B n(x). A m(x)=A0+A1x1+A2x2+A3x3+… +A m x m B n(x)=B0+B1x1+B2x2+B3x3+… +B n x n 请实现求M(x)= A m(x)+B n(x)、M(x)= A m(x)-B n(x)和M(x)= A m(x)×B n(x)。要求： 1) 首先判定多项式是否稀疏 2) 采用动态存储结构实现； 3) 结果M(x)中无重复阶项和无零系数项； 4) 要求输出结果的升幂和降幂两种排列情况 三、具体要求及应提交的材料 1．每个同学以自己的学号和姓名建一个文件夹，如：“312009*********张三”。里面应包括：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）、任务书和课程设计说明书的电子文档。 2．打印的课程设计说明书（注意：在封面后夹入打印的“任务书”以后再装订）。 四、主要技术路线提示 为把多个小功能结合成一个完整的小软件，需使用“菜单设计”技术（可以是控制台方式下的命令行形式，若能做成图形方式则更好）。 五、进度安排 共计两周时间，建议进度安排如下： 选题，应该在上机实验之前完成 需求分析、概要设计可分配4学时完成 详细设计可分配4学时 调试和分析可分配10学时。 2学时的机动，可用于答辩及按教师要求修改课程设计说明书。 注：只用课内上机时间一般不能完成设计任务，所以需要学生自行安排时间做补充。 六、推荐参考资料(不少于3篇) ［1］苏仕华等编著，数据结构课程设计，机械工业出版社，2007 ［2］严蔚敏等编著，数据结构（C语言版），清华大学出版社，2003 ［3］严蔚敏等编著，数据结构题集（C语言版），清华大学出版社，2003 指导教师签名日期年月日 系主任审核日期年月日 摘要 分析了matlab，mathmatic，maple等数学软件对一元多项式的计算过程，步骤后。由于这些软件比较大功能齐全，但是实用性不强。因此，利用microsoft visual studio 6.0开发工具，编程实现了一元多项式的加法、减法、乘法的计算器系统，该系统具有一元多项式的加法、减法、乘法等功能。 关键词：一元多项式; 软件; 计算 一元多项式相加实验报告 一元多项式的相加 一实验内容 根据所学的数据结构中线性结构（线性表）的逻辑特性和物理特性及相关算法，应用于求解一个具体的实际问题----------两个多项式相加 二需求分析 1掌握线性结构的逻辑特性和物理特性。 2建立一元多项式。 3将一元多项式输入，并存储在内存中，并按照指数降序排列输出多项式。 4能够完成两个多项式的加减运算，并输出结果。 三概要设计 1 本程序所用到的抽象数据类型： typedef OrderedLinkList polynomial; // 用带表头结点的有序链表表示多项式 结点的数据元素类型定义为: typedef struct { // 项的表示 float coef; // 系数 int expn; // 指数 term, ElemType; V oid AddPolyn(polynomail&Pa,polynomail&Pb) Position GetHead() Position NextPos(LinkList L,Link p) Elem GetCurElem(Link p) int cmp(term a term b) Status SetCurElem(Link&p, ElemType e) Status DelFirst(Link h, Link &q) Status ListEmpty(LinkList L) Status Append(LinkList&L, Link S) FreeNode() 2 存储结构 一元多项式的表示在计算机内用链表来实现，同时为了节省存储空间，只存储其中非零的项，链表中的每个节点存放多项式的系数非零项。它包含三个域，分别存放多项式的系数，指数，以及指向下一个项的指针。 创建一元多项式链表，对运算中可能出现的各种情况进行分析，实现一元多项式的相加相减操作。 3 模块划分 a) 主程序；2）初始化单链表；3）建立单链表； 4）相加多项式 4 主程序流程图 四详细设计 根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项，对 《数据结构》实验报告 ——两个一元多项式相加 一、实验题目：两个一元多项式相加 二、实验内容： 根据所学的数据结构中线性结构（线性表）的逻辑特性和物理特性及相关算法，应用于求解一个具体的实际问题----------两个多项式相加 三、设计思想： （1）建立两个顺序列表，分别用来表示两个一元多项式；顺序列表奇数位，存储该多项式的系数；顺序列表的偶数位，存储该相应多项式的指数。 （2）用成员函数merg(qList 一元多项式计算(数据结构课程设计) 一、系统设计 1、算法思想 根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应指数相加（减），若其和（差）不为零，则构成“和（差）多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别写到“和（差）多项式”中去。 因为多项式指数最高项以及项数是不确定的，因此采用线性链表的存储结构便于实现一元多项式的运算。为了节省空间，我采用两个链表分别存放多项式a 和多项式b，对于最后计算所得的多项式则利用多项式a进行存储。主要用到了单链表的插入和删除操作。 (1)一元多项式加法运算 它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就应该相加；相加的和不为零的话，用头插法建立一个新的节点。P 的指数小于q的指数的话就应该复制q的节点到多项式中。P的指数大于q的指数的话，就应该复制p节点到多项式中。当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生。 (2)一元多项式的减法运算 它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就相减；相加的和不为零的话，用头插法建立一个新的节点。p的指数小于q的指数的话，就应该复制q的节点到多项式中。P的指数大于q的指数的话就应该复制p的节点到多项式中，并且建立的节点的系数为原来的相反数；当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生，并且建立的节点的系数为原来的相反数。 2、概要设计 (1)主函数流程图： （注：a代表第一个一元二次方程，b代表第二个一元二次方程） [计算机]一元多项式相加完整实验报告一元多项式的相加 一实验内容 根据所学的数据结构中线性结构(线性表)的逻辑特性和物理特性及相关算法，应用于求解一个具体的实际问题----------两个多项式相加 二需求分析 1掌握线性结构的逻辑特性和物理特性。 2建立一元多项式。 3将一元多项式输入，并存储在内存中，并按照指数降序排列输出多项式。 4能够完成两个多项式的加减运算，并输出结果。 三概要设计 1 本程序所用到的抽象数据类型: typedef OrderedLinkList polynomial; // 用带表头结点的有序链表表示多项式 结点的数据元素类型定义为: typedef struct { // 项的表示 oat flcoef; // 系数 int expn; // 指数 term, ElemType; Void AddPolyn(polynomail&Pa,polynomail&Pb) Position GetHead() Position NextPos(LinkList L,Link p) Elem GetCurElem(Link p) int cmp(term a term b) Status SetCurElem(Link&p, ElemType e) Status DelFirst(Link h, Link &q) Status ListEmpty(LinkList L) Status Append(LinkList&L, Link S) FreeNode() 2 存储结构 一元多项式的表示在计算机内用链表来实现，同时为了节省存储空间，只存储其中非零的项，链表中的每个节点存放多项式的系数非零项。它包含三个域，分别存放多项式的系数，指数，以及指向下一个项的指针。 序数coef 指数exp 指针域next 创建一元多项式链表，对运算中可能出现的各种情况进行分析，实现一元多项式的相加相减操作。 3 模块划分 a) 主程序;2)初始化单链表;3)建立单链表; 4)相加多项式 4 主程序流程图 开始 申请结点空间 输入多项式各项的系数X，指数Y 输出已输出的多项式 否 是否输入正确 合并同类项 结束 四详细设计 根据一元多项式相加的运算规则:对于两个一元多项式中所有指数相 一元多项式相加问题 # include for(i=0;i 数据结构实验报告实验一：一元多项式相加 姓名：周成 学号： 13083511 专业：软件工程 任课教师：马慧珠 2013年12 月01 日 1.实验名称： 一元多项式相加 2.实验目的: 如何使用C语言实现链表的说明、创建以及结点的插入和删除等操作。 3.实验要求： 对一元多项式能实现输入、输出，以及两个一元多项式相加及结果显示。 4.实验内容： 一元多项式的表示在计算机内用链表来实现，同时为了节省存储空间，只存储其中非零的项，链表中的每个节点存放多项式的系数非零项。它包含三个域，分别存放多项式的系数，指数，以及指向下一个项的指针。根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项，对于两个一元多项式中所有指数不相同的项，则分别复抄到“和多项式”中去。 核心算法PolyAdd是把分别由pa和pb所指的两个多项式相加，结果为pa所指的多项式。运算规则如下：相加时，首先设两个指针变量qa和qb分别从多项式的首项开始扫描，比较qa和qb所指结点指数域的值，可能出现下列三种情况之一： （1）qa->exp大于qb->exp,则qa继续向后扫描。 （2）qa->exp等于qb->exp,则将其系数相加。若相加结果不为零，将结果放入qa->coef中，并删除qb所指结点，否则同时删除qa和qb所指结点。 然后qa、qb继续向后扫描。 （3）qa->exp小于qb->exp,则将qb所指结点插入qa所指结点之前，然后qa、qb继续向后扫描。 扫描过程一直进行到qa或qb有一个为空为止，然后将有剩余结点的链表接在结果表上。所得pa指向的链表即为两个多项式之和。 5.实验程序代码及运行结果： #include"stdafx.h" #include 实验一一元多项式的表示与相加 实验目的： 1.复习并熟练掌握数据结构所使用的程序设计语言——C语言； 2.学会单步跟踪、调试自己的程序； 3.加深对线性表特别是链表知识的理解和掌握，并能够运用相关知识来解决相关的具体问题，如一元多项式相加等； 程序流程： 1.定义一元多项式链表结构体类型； 2.输入多项式项数以分配存储空间； 3.输入多项式每项的系数和指数，将其插入当前多项式链表。同时判断是否有与当前节点指数相同的项，若存在，则将两项系数相加合并。此外，若存在系数为0的项，将其存储空间释放； 4.进行多项数加法时，新建一个存储结果的链表，分别将两多项式各项依次插入结果多项式即完成多项式相加运算； 5.进行多项数加法时，将减项多项式各项系数化为相反数后进行加法操作，即完成多项式相减运算； 6.对x赋值后，将x值代入多项式进行运算得到多项式的值； 7.输出多项式。 注意：进行完一次运算以后，应该及时销毁无用多项式以释放空间以便再次应用。 算法及注释： 1）定义一元多项式链表结构体类型 typedef struct Lnode{ float cof; //定义系数 int exp; //定义指数 struct Lnode *next; //定义指针变量指向下一个节点 }Lnode ,*Linklist; //定义新的变量类型 2）建立多项式存储线性链表头结点 void makehead(Linklist &head){ head=(Linklist)malloc(sizeof(Lnode)); //建立新的节点 head->exp=-1; head->next=NULL; //指针赋空 head->cof=1; } 项目一一元多项式的计算问题 1.1设计题目与要求 1.1.1设计题目 1）一元多项式计算 任务：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输入； 基本要求：在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；本程序关键点是如何将输入的两个多项式相加、相减操作。 ①如何将输入的一元多项式按指数的降序排列 ②如何确定要输入的多项式的项数； ③如何将输入的两个一元多项式显示出来。 ④如何将输入的两个一元多项式进行相加操作。 ⑤如何将输入的两个一元多项式进行相减操作。 本程序是通过链表实现一元多项式的相加减操作。 1.1.2、任务定义 此程序需要完成如下的要求：将多项式按照指数降序排列建立并输出，将两个一元多项式进行相加、相减操作，并将结果输入。 a：输入多项式的项数并建立多项式； b：输出多项式，输出形式分别为浮点和整数序列，序列按指数升序排列； c：多项式a和b相加，建立多项式a+b； d：多项式a和b相减，建立多项式a-b。 e：多项式的输出。 1.2 数据结构的选择和概要设计： 1.2.1数据结构的选用 A:基于链表中的节点可以动态生成的特点，以及链表可以灵活的添加或删除节点的数据结构，为了实现任意多项式的加法，减法，因此选择单链表的结构体，它有一个系数，指数，下一个指针3个元属；例如，图1中的两个线性链表分别表示一元多项式 和一元多项式。从图中可见，每个结点表示多项式中的一项。 图1 多项式表的单链存储结构 B：本设计使用了以下数据结构： typedef struct node{ int xs; /*系数*/ int zs; /*指数*/ struct node * next; /*next指针*/ }Dnode,* Dnodelist; C：设计本程序需用到八个模块，用到以下八个子函数如下： 1.Dnodelist Creat_node(void) /*链表初始化*/ 2.int Insert_node(Dnodelist D,int xs,int zs) /*插入函数*/ 3.Dnodelist Creat_Dmeth(int length) /*创建多项式*/ 4.Dnodelist Addresult(Dnodelist D1,Dnodelist D2) /*多项式相加*/ 5.Dnodelist Subresult(Dnodelist D1,Dnodelist D2) /*多项式相减*/ 6.Dnodelist select(Dnodelist D1,Dnodelist D2) /*选择函数*/ 7void Show(Dnodelist D) /*显示（输出）函数*/ 8void main()主程序模块调用链一元多项式的各种基本操作模块。 1.2.2 多项式的输入 先输入多项式的项数，采用尾插法的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它； 1.2.3 两个多项式的加法 “和多项式”链表中的结点无需另生成，而应该从两个多项式的链表中摘取。其运算规则如下： 假设指针A和B分别指向多项式a和多项式b中当前进行比较的某个结点，则比较两个结点中的指数项，有下列3种情况： ①指针A所指结点的指数值<指针B所指结点的指数值，则应摘取A指针所指结点插入到“和多项式”链表中去； ②指针A所指结点的指数值>指针B所指结点的指数值，则应摘取指针A所指结点插入到“和多项式”链表中去； ③指针A所指结点的指数值=指针B所指结点的指数值，则将两个结点中的系数相加， 若和数不为零，则修改A所指结点的系数值，同时释放B所指结点；反之，从多项式A的链表中删除相应结点，并释放指针A和B所指结点。例如，由图2中的两个链表表示的多项式相加得到的“和多项式”链表如图2所示，图中的长方框表示已被释放的结点。 实验题目：一元多项式运算 班级：13级数学一班姓名：张保昌学号：2013433037 日期：2014—10—09 一、需求分析 1．问题描述； 设计一个简单的一元稀疏多项式加减及求导运算器。 2．基本要求的功能要求； （1）输入多项式时可以按任意次序输入各项的数据（输入并建立多项式A与B），不必按指数有序；在算法中实现建立按指数有序的多项式。 （2）计算多项式A与B的和，即建立多项式A+B。 （3）按照指数升序次序，输出多项式A、B、A+B。 （4）计算多项式A与B的差，即建立多项式A－B； （5）计算多项式A的导函数Aˊ。 3．测试数据。 （1）(x+3x6－8.6x11)+(6－3x6+21x9)=6+x+21x9－8.6x11 （2）(3x－3－x+4.1x2－1.2x9)＋(―3x―3－5.1x2 +7.8x12)=－x－x2－1.2x9+7.8x12 （3）(x+x3)+(―x―x3)=0 （4）(x+x2+x3)+0=x+x2+x3 （5）(x+x2+x3)—(x+x2+x3)=0 (6) (x+x2+x3)ˊ=1+2x+3x2 二、概要设计 1．本程序所用的抽象数据类型的定义； typedef struct pnode { double coef; /*系数域*/ int exp; /*指数域*/ struct pnode *next; /*指针域，*/ }polynode, *polylink; polylink insert_list(polylink h,char o); //输入多项式。 polylink order_list(polylink h); //按指数升序排列 polylink simply_list(polylink h); //初步整理（合并多项式，并删除系数为零的式子）polylink add(polylink a,polylink b); //加法运算 polylink opposite(polylink b); //将减法统归为加法 polylink derivative(polylink a); //求导函数 void list_display(polylink h,char o); //输出显示 void index(); //菜单函数 2．模块划分。 1）主函数模块。2）加法运算模块3）减法运算模块4）导数模块。 3．主模块的流程及各子模块的主要功能； 福建农林大学计算机与信息学院 课程设计报告 课程名称：数据结构 课程设计题目：一元多项式的加法减法乘法的实现姓名： 系：软件工程系 专业：软件工程专业 年级：2014 学号： 指导教师：黄思先 职称：副教授 完成起止日期：2016.6.5 - 2016.7.1 2016年07月1日 福建农林大学计算机与信息学院课程设计结果评定 目录 一、问题分析和任务定义 (1) 二、程序设计内容 (1) 三、程序调试与测试 (7) 四、实验心得 (9) 五、程序编码 (9) 一、问题分析及任务定义 顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。 【问题描述和基本要求】设有一元多项式Am(x)和Bn(x). Am(x)=A0+A1x1+A2x2+A3x3+… +Amxm Bn(x)=B0+B1x1+B2x2+B3x3+… +Bnxn 请实现求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)×Bn(x)。 要求： 1) 首先判定多项式是否稀疏 2) 分别采用顺序和动态存储结构实现； 3) 结果M(x)中无重复阶项和无零系数项； 4) 要求输出结果的升幂和降幂两种排列情况 二、课程设计的内容 2.1函数 多项式创建函数PolyNode *Creatpoly() 多项式输出函数void Prin_poly(PolyNode *h) 多项式升序排列函数void Insortup(PolyNode *h) 多项式降序排列函数void Insortdown(PolyNode *h) 多项式合并函数void UnitePoly(PolyNode *h) 多项式相乘函数PolyNode *polymuti(PolyNode *h1,PolyNode *h2) 多项式相加函数PolyNode *addition(PolyNode *ha, PolyNode *hb) 多项式相减函数PolyNode *subduction (PolyNode *ha, PolyNode *hb) 2.2设计各个模块的流程图 （1）main() 武汉理工大学华夏学院 课程设计报告书 课程名称：数据结构与算法分析 题目：用C语言实现一元多项式的加减法运算 系名：信息工程系 专业班级：物联网工程1122班 姓名：隋明超 学号： 10213312201 指导教师:司晓梅 2014年 1 月 3 日 武汉理工大学华夏学院信息工程系 课程设计任务书 课程名称：数据结构与算法分析指导教师：司晓梅班级名称：物联网1121-2 开课系、教研室：信息系计算机 一、课程设计目的与任务 《数据结构》课程设计是为训练学生的数据组织能力和提高程序设计能力而设置的增强实践能力的课程。目的：学习数据结构课程，旨在使学生学会分析研究数据对象的特性，学会数据的组织方法，以便选择合适的数据的逻辑结构和存储结构以及相应操作，把现实世界中的问题转换为计算机内部的表示和处理，这就是一个良好的程序设计技能训练的过程。提高学生的程序设计能力、掌握基本知识、基本技能，提高算法设计质量与程序设计素质的培养就是本门课程的课程设计的目的。 任务：根据题目要求，完成算法设计与程序实现，并按规定写出课程设计报告。 二、课程设计的内容与基本要求 设计题目：用C语言实现一元多项式的加减法计算 〔问题描述〕输入并建立两个多项式并输出多项式 设计一个程序：对两个多项式进行加、减法运算，建立一个新多项式并输出。 〔实现提示〕：选择单链表存储多项式 具体要完成的任务是： A. 编制完成上述问题的C语言程序、进行程序调试并能得出正确的运行结果。 B. 写出规范的课程设计报告书； 三、课程设计步骤及时间进度和场地安排 时间：本课程设计安排在第18周地点：现代教育中心 具体时间安排如下： 第一天：布置题目，确定任务、查找相关资料 第二天～第四天：功能分析，编写程序，调试程序、运行系统； 第五天上午：撰写设计报告； 第五天下午：程序验收、答辩。 四、课程设计考核及评分标准 课程设计考核将综合考虑学生的系统设计方案、运行结果、课程设计报告书的质量、态度、考勤、答辩情况等各因素。具体评分标准如下： （1）设计方案正确，具有可行性、创新性； 30分 （2）系统开发效果较好； 20分 【关键字】情况、空间、运行、继续、掌握、信心、工程、能力、结构、坚持、巩固、实现、核心、耐心 数据结构实验报告 实验一：一元多项式相加 姓名：周成 学号： 专业：软件工程 任课教师：马慧珠 2013年12 月01 日 1.实验名称： 一元多项式相加 2.实验目的: 如何使用C语言实现链表的说明、创建以及结点的插入和删除等操作。 3.实验要求： 对一元多项式能实现输入、输出，以及两个一元多项式相加及结果显示。 4.实验内容： 一元多项式的表示在计算机内用链表来实现，同时为了节省存储空间，只存储其中非零的项，链表中的每个节点存放多项式的系数非零项。它包含三个域，分别存放多项式的系数，指数，以及指向下一个项的指针。根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项，对于两个一元多项式中所有指数不相同的项，则分别复抄到“和多项式”中去。 核心算法PolyAdd是把分别由pa和pb所指的两个多项式相加，结果为pa所指的多项式。运算规则如下：相加时，首先设两个指针变量qa和qb分别从多项式的首项开始扫描，比较qa和qb所指结点指数域的值，可能出现下列三种情况之一： （1）qa->exp大于qb->exp,则qa继续向后扫描。 （2）qa->exp等于qb->exp,则将其系数相加。若相加结果不为零，将结果放入qa->coef中，并删除qb所指结点，否则同时删除qa和qb所指结点。 然后qa、qb继续向后扫描。 （3）qa->exp小于qb->exp,则将qb所指结点插入qa所指结点之前，然后qa、qb继续向后扫描。 扫描过程一直进行到qa或qb有一个为空为止，然后将有剩余结点的链表接在结果表上。所得pa指向的链表即为两个多项式之和。 5.实验程序代码及运行结果： #include"stdafx.h" #include一元多项式的相加减复习过程
一元多项式加减乘除运算
一元多项式求和
一元多项式的计算数据结构课程设计
一元多项式求和问题的研究与实现
数据结构课程设计-一元多项式的加法、减法、乘法的实现
一元多项式相加完整实验报告
两个一元多项式相加-c++版
一元多项式计算(数据结构课程设计)
[计算机]一元多项式相加完整实验报告
一元多项式相家问题
数据结构-实验一-一元多项式相加
数据结构_一元多项式的表示与相加
数据结构 一元多项式的计算
一元多项式的加减求导运算算法(数据结构算法)
一元多项式的加法减法乘法的实现
数据结构课程设计一元多项式的加减法运算
数据结构-实验一-一元多项式相加精品
相关主题
文本预览