数据结构实验,多项式计算器

数据结构中实现一元多项式简单计算：设计一个一元多项式简单的计算器。

基本要求：一元多项式简单计算器的基本功能为：（1）输入并建立多项式；（2）输出多项式；（3）两个多项式相加，建立并输出和多项式；（4）两个多项式相减，建立并输出差多项式；#include<stdio.h>#include<malloc.h>#define MAX 20 //多项式最多项数typedef struct//定义存放多项式的数组类型{float coef; //系数int exp; //指数} PolyArray[MAX];typedef struct pnode//定义单链表结点类型{float coef; //系数int exp; //指数struct pnode *next;} PolyNode;void DispPoly(PolyNode *L) //输出多项式{PolyNode *p=L->next;while (p!=NULL){printf("%gX^%d ",p->coef,p->exp);p=p->next;}printf("\n");}void CreateListR(PolyNode *&L,PolyArray a,int n) //尾插法建表{PolyNode *s,*r;int i;L=(PolyNode *)malloc(sizeof(PolyNode)); //创建头结点L->next=NULL;r=L; //r始终指向终端结点,开始时指向头结点for (i=0;i<n;i++){s=(PolyNode *)malloc(sizeof(PolyNode));//创建新结点s->coef=a[i].coef;s->exp=a[i].exp;r->next=s; //将*s插入*r之后r=s;}r->next=NULL; //终端结点next域置为NULL}void Sort(PolyNode *&head) //按exp域递减排序{PolyNode *p=head->next,*q,*r;if (p!=NULL) //若原单链表中有一个或以上的数据结点{r=p->next; //r保存*p结点后继结点的指针p->next=NULL; //构造只含一个数据结点的有序表p=r;while (p!=NULL){r=p->next; //r保存*p结点后继结点的指针q=head;while (q->next!=NULL && q->next->exp>p->exp)q=q->next; //在有序表中找插入*p的前驱结点*qp->next=q->next; //将*p插入到*q之后q->next=p;p=r;}}}void Add(PolyNode *ha,PolyNode *hb,PolyNode *&hc) //求两有序集合的并{PolyNode *pa=ha->next,*pb=hb->next,*s,*tc;float c;hc=(PolyNode *)malloc(sizeof(PolyNode)); //创建头结点tc=hc;while (pa!=NULL && pb!=NULL){if (pa->exp>pb->exp){s=(PolyNode *)malloc(sizeof(PolyNode)); //复制结点s->exp=pa->exp;s->coef=pa->coef;tc->next=s;tc=s;pa=pa->next;}else if (pa->exp<pb->exp){s=(PolyNode *)malloc(sizeof(PolyNode)); //复制结点s->exp=pb->exp;s->coef=pb->coef;tc->next=s;tc=s;pb=pb->next;}else//pa->exp=pb->exp{c=pa->coef+pb->coef;if (c!=0) //系数之和不为时创建新结点{s=(PolyNode *)malloc(sizeof(PolyNode)); //复制结点s->exp=pa->exp;s->coef=c;tc->next=s;tc=s;}pa=pa->next;pb=pb->next;}}if (pb!=NULL) pa=pb; //复制余下的结点while (pa!=NULL){s=(PolyNode *)malloc(sizeof(PolyNode)); //复制结点s->exp=pa->exp;s->coef=pa->coef;tc->next=s;tc=s;pa=pa->next;}tc->next=NULL;}void Cut(PolyNode *ha,PolyNode *hb,PolyNode *&hd) //求两有序集合的并{PolyNode *pa=ha->next,*pb=hb->next,*s,*td;float d;hd=(PolyNode *)malloc(sizeof(PolyNode)); //创建头结点td=hd;while (pa!=NULL && pb!=NULL){if (pa->exp>pb->exp){s=(PolyNode *)malloc(sizeof(PolyNode)); //复制结点s->exp=pa->exp;s->coef=pa->coef;td->next=s;td=s;pa=pa->next;}else if (pa->exp<pb->exp){s=(PolyNode *)malloc(sizeof(PolyNode)); //复制结点s->exp=pb->exp;s->coef=-(pb->coef);td->next=s;td=s;pb=pb->next;}else//pa->exp=pb->exp{d=pa->coef-pb->coef;if (d!=0) //系数之和不为时创建新结点{s=(PolyNode *)malloc(sizeof(PolyNode)); //复制结点s->exp=pa->exp;s->coef=d;td->next=s;td=s;}pa=pa->next;pb=pb->next;}}if (pb!=NULL) pa=pb; //复制余下的结点while (pa!=NULL){s=(PolyNode *)malloc(sizeof(PolyNode)); //复制结点s->exp=pa->exp;s->coef=pa->coef;td->next=s;td=s;pa=pa->next;}td->next=NULL;}void main(){PolyNode *ha,*hb,*hc,*hd,*he;PolyArray a={{1.2,0},{2.5,1},{3.2,3},{-2.5,5}};PolyArray b={{-1.2,0},{2.5,1},{3.2,3},{2.5,5},{5.4,10}};CreateListR(ha,a,4);CreateListR(hb,b,5);printf("原多项式A: ");DispPoly(ha);printf("原多项式B: ");DispPoly(hb);Sort(ha);Sort(hb);printf("有序多项式A: ");DispPoly(ha);printf("有序多项式B: ");DispPoly(hb);Add(ha,hb,hc);printf("多项式相加: ");DispPoly(hc);Cut(ha,hb,hd);printf("多项式相减: ");DispPoly(hd); }。

数据结构课程设计设计题目：一元稀疏多项式计算器专业______________________ 班级______________________ 学号______________________ 姓名______________________ 指导教师___________________2010 年12 月20 H目录一、课程题目 (1)二、需求分析 (1)三、测试数据 (2)四、概要设计 (2)五、调用关系图 (3)六、程序代码 (3)七、测试结果 (11)八、心得体会及总结 (12)数据结构课程设计一、课程题冃一元稀诡多项式计算器二、需求分析1、一元稀疏多项式简单计算器的功能是：1.1输入并建立多项式；1.2输出多项式,输出形式为整数序列:n, cl,el,c2,e2, ......................... c n, en,其中ii是多项式的项数,ci和ei分别是第i项的系数和指数，序列按指数降序排列；1.3求多项式a、b的导函数;1.4计算多项式在x处的值;1.5多项式"和b和加，建立多项认a+b；1.6多项式a和b相减,建立多项式a-b。

2、设计思路：2.1定义线性表的动态分配顺序存储结构;2.2建立多项式存储结构，定义指针*next2.3利用链表实现队列的构造.毎次输入一项的系数和指数，町以输出构造的一元多项式2.4演示程用以用户和计舜机的对话方式执行，即在计舜机终站上显示“提示信息” Z后，由川户化键盘丄输入演示程序小规运的运行•命令；报后根据相应的输入数据〔滤去输入中的4法字符）建立的多项式以及多项式相加的运行结果在屏幕上显示。

多项式显示的格式为:clx*el+c2x*e2+ — +cnx"en3、设计思路分析要解决多项式相加，必须要冇多项式，所以必须首先建立两个多项式，在这电采用链表的方式存储琏表，所以我将结点结构体定义为运川尾插法建立两条单链表，以巾•链表polyn p和polyn h分别表示两个一元多项式a和b, a+b的求和运算等同于单链表的插入问题（将单链表polyn P 中的结点插入到单链表polyn h中），因此“和多项式”中的结点无须另生成。

云南大学软件学院数据结构实验报告2010秋季学期（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）学号：姓名：专业：指导老师：实验难度A□B□ C □承担任务（难度为C时填写）指导教师评分（签名）【实验题目】实验2. 线性表及其应用【问题描述】用C或C++语言设计并实现一个一元稀疏多项式的简单计算器。

【基本要求】一元稀疏多项式简单计算器的基本功能是：1、输入并建立多项式2、输出多项式，序列按指数降序排列3、多项式A(x)和B(x)相加，并建立多项式A(x)+B(x)4、多项式A(x)和B(x)相减，并建立多项式A(x)-B(x)5、给定 x 的值，计算多项式6、多项式A(x)和B(x)相乘，建立多项式A(x)*B(x) （* 选做，作为难度B的操作）【CDIO项目要求】1、有完整的CDIO四个阶段描述2、有友好美观的操作界面3、有软件使用说明或帮助文档4、项目成员分工明确，团结协作【实现提示】一、【实验构思（Conceive）】(10%)本实验通过C语言实现了多项式加法、减法、乘法、多项式求导、多项式积分的功能。

利用了冒泡排序的算法作为排序的核心算法。

运用了高等数学中多项式的求导积分的知识。

二、【实验设计(Design)】(15%)本程序定义了抽象数据结构listnode，用于存储多项式的系数和指数并存储指向下一个listnode的指针来构成链表。

本程序包含如下*个函数：Main函数：调用input函数—>调用bubble_sort函数—>调用operplus函数—>调用oper_minus函数—>调用oper_mul函数—>调用oper_dy函数—>调用oper_jifen 函数。

Oper_plus函数：将两个链表的相应项系数相加，指数不同项不操作，存入新链表，再调用排序算法，使之为降序排列。

Oper_minus函数：将两个链表的相应项系数相减，指数不同项不操作，存入新链表，再调用排序算法，使之为降序排列。

数据结构计算器实验报告1. 引言数据结构是计算机科学的基础，它提供了一种组织和存储数据的方式，以便能够高效地访问和操作这些数据。

计算器是一种常见的应用程序，它可以执行各种数学运算。

本实验的主要目的是设计和实现一个简单的数据结构计算器，用于实现基本的四则运算功能。

2. 设计思路在设计数据结构计算器时，我们需要考虑以下几个方面的问题：2.1 数据结构选择为了实现四则运算功能，我们首先需要选择合适的数据结构来存储和操作数学表达式。

在本实验中，我们选择使用栈作为数据结构，因为栈具有后进先出的特性，非常适合处理运算符和操作数的顺序。

2.2 表达式解析在计算器中，我们需要将用户输入的数学表达式解析成运算符和操作数，以便进行计算。

为了实现表达式解析功能，我们可以使用字符串的分割和转换操作来提取运算符和操作数，并将它们存储到栈中。

2.3 运算符优先级在进行四则运算时，运算符的优先级非常重要。

我们需要确保高优先级的运算符先于低优先级的运算符进行计算。

为了实现这一功能，我们可以使用栈来存储运算符，并在遇到运算符时进行比较和计算。

2.4 计算结果输出最后，我们需要将计算结果输出给用户。

为了实现这一功能，我们可以使用一个变量来存储计算结果，并在计算完成后将结果输出到屏幕上。

3. 实现步骤基于上述设计思路，我们可以按照以下步骤来实现数据结构计算器：3.1 定义栈数据结构首先，我们需要定义一个栈数据结构来存储运算符和操作数。

栈可以使用数组或链表来实现，具体选择取决于实际需求。

3.2 解析数学表达式接下来，我们需要编写代码来解析用户输入的数学表达式。

我们可以使用字符串的分割和转换操作来提取运算符和操作数，并将它们存储到栈中。

3.3 实现运算符优先级比较和计算在解析数学表达式的过程中，我们需要实现运算符的优先级比较和计算功能。

每当遇到一个运算符时，我们可以将其与栈顶的运算符进行比较，如果栈顶的运算符优先级较高，则可以进行相应的计算。

数据结构课程设计一、课程题目一元稀疏多项式计算器二、需求分析1、一元稀疏多项式简单计算器的功能是：1.1 输入并建立多项式；1.2 输出多项式，输出形式为整数序列：n，c1,e1,c2,e2,………cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；1.3 求多项式a、b的导函数；1.4 计算多项式在x处的值；1.5多项式a和b相加，建立多项式a+b；1.6 多项式a和b相减，建立多项式a-b。

2、设计思路:2.1 定义线性表的动态分配顺序存储结构；2.2 建立多项式存储结构，定义指针*next2.3利用链表实现队列的构造。

每次输入一项的系数和指数，可以输出构造的一元多项式2.4演示程序以用户和计算机的对话方式执行，即在计算机终站上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令；最后根据相应的输入数据（滤去输入中的非法字符）建立的多项式以及多项式相加的运行结果在屏幕上显示。

多项式显示的格式为：c1x^e1+c2x^e2+…+cnx^en3、设计思路分析要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将结点结构体定义为运用尾插法建立两条单链表，以单链表polyn p和polyn h分别表示两个一元多项式a和b，a+b的求和运算等同于单链表的插入问题（将单链表polyn p中的结点插入到单链表polyn h中），因此“和多项式”中的结点无须另生成。

为了实现处理，设p、q分别指向单链表polya和polyb的当前项，比较p、q结点的指数项，由此得到下列运算规则：① 若p->expn<q->expn，则结点p所指的结点应是“和多项式”中的一项，令指针p后移。

② 若p->expn=q->expn，则将两个结点中的系数相加，当和不为0时修改结点p的系数。

③ 若p->expn>q->expn，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移。

数据结构实验多项式计算器1.实验目的本次实验的目的是使用C语言实现一个多项式计算器，分析其计算性能，并对计算结果进行验证。

2.实验内容（1）多项式计算器的原理多项式计算器是指利用多项式的定义，结合多项式的加法、减法、乘法、除法等运算，实现多项式进行计算的一类计算器。

多项式定义：当n>=0时，若存在一个多项式P(x)=a(0)+(x)+a(1)(x^1)+...+a(n)(x^n)，且其中有一个a(i)!=0，则称多项式P(x)为a(0)+(x)+a(1)(x^1)+...+a(n)(x^n)。

其中a(i)称为多项式P(x)的系数，并且n+1称为多项式P(x)的次数。

多项式运算：（1）多项式加法：若存在多项式A(x)和B(x)，则A(x)+B(x)的值为：A(x)+B(x)=a(0)+(x)+a(1)(x^1)+...+a(i)(x^i)+...+a(n)(x^n)+b(0)+(x)+b(1)(x^1)+...+b(i)(x^i)+...+b(n)(x^n)=c(0)+(x)+c(1)(x^1)+. ..+c(i)(x^i)+...+c(n)(x^n)其中c(i)=(a(i)+b(i))(0<=i<=n)，即多项式A(x)+B(x)=C(x)，其中C(x)的次数=max{A(x)的次数，B(x)的次数}。

（2）多项式减法：若存在多项式A(x)和B(x)，则A(x)-B(x)的值为：A(x)-B(x)=a(0)+(x)+a(1)(x^1)+...+a(i)(x^i)+...+a(n)(x^n)-b(0)+(x)-b(1)(x^1)-...-b(i)(x^i)-...-b(n)(x^n)=c(0)+(x)+c(1)(x^1)+...+c(i)(x^i)+...+c(n)(x^n)其中c(i)=(a(i)-b(i))(0<=i<=n)，即多项式A(x)-x)=C(x)，其中C(x)的次数=max{A(x)的次数。

数据结构实验报告——一元稀疏多项式计算器安子烨PB12203079实验目的实现一元多项式的简单运算功能，掌握线性表的知识，提高编程能力。

功能清单1.一元多项式创建2.显示一元多项式3.复制一元多项式4.多项式加法5.多项式减法6.修改一元多项式7.删除一元多项式8.销毁记录实验设计该多项式计算器以菜单驱动的形式实现上述各运算功能。

最多可支持十条记录，分别用指针数组引导存储于十个不同的位置。

以下为程序的部分源代码。

#include<stdio.h>#include<math.h>#include<stdlib.h>typedef struct LinkList{double coef;int expn;LinkList *next;}LNode;void CreatPolyn(LinkList **h)//创建多项式{LinkList *q=NULL, *w=NULL, *p=NULL;double m=0; int n=0;(*h)=(LinkList *)malloc(sizeof(LinkList));(*h)->coef=0; (*h)->expn=0; (*h)->next=NULL;printf("请输入X的系数和指数,当系数为零时结束创建\n");scanf("%lf%d",&m,&n);while(m!=0){q=(LinkList *)malloc(sizeof(LinkList));q->coef=m; q->expn=n; q->next=NULL;if((*h)->next==NULL){if(q->expn==(*h)->expn) (*h)->coef+=q->coef;else if((*h)->expn>q->expn) {q->next=(*h); *h=q; } else (*h)->next=q;}else{for(w=(*h);w->next!=NULL;w=w->next){if(q->expn==w->expn){w->coef+=q->coef;break;}else if((w->expn>q->expn)&&(w==*h)){q->next=(*h);(*h)=q;break;}else if((w->expn<q->expn)&&(w->next->expn>q->expn)){q->next=w->next;w->next=q;break;}}if(w->next==NULL){if(w->expn==q->expn) w->coef+=q->coef;else if(w->expn<q->expn) w->next=q;}}printf("请输入X的系数和指数,当系数为零时结束创建\n");scanf("%lf%d",&m,&n);}}void PrintPolyn(LinkList *p, int i)//打印多项式{printf("第%d个多项式是:",i);while(p!=NULL){if((p->coef)>0) printf("+%lf*X^%d",p->coef,p->expn);else if((p->coef)<0) printf("%lf*X^%d",p->coef,p->expn); p=p->next;}printf("\n");}void CopyPolyn(LinkList **M, LinkList **N)//多项式复制{LinkList *p=NULL, *q=NULL, *w=NULL;(*N)=(LinkList *)malloc(sizeof(LinkList));(*N)->coef=(*M)->coef; (*N)->expn=(*M)->expn; (*N)->next=NULL;for(w=(*N),p=(*M)->next;p!=NULL;p=p->next){q=(LinkList *)malloc(sizeof(LinkList));q->coef=p->coef; q->expn=p->expn; q->next=p->next;w->next=q; w=w->next;}}void AddPolyn(LinkList *M, LinkList *N, LinkList **X)//多项式加法{LinkList *p=NULL, *q=NULL, *w=NULL, *z=NULL;(*X)=(LinkList *)malloc(sizeof(LinkList));(*X)->coef=0; (*X)->expn=0; (*X)->next=NULL;for(p=M,q=N,w=(*X);(p!=NULL)&&(q!=NULL);){z=(LinkList *)malloc(sizeof(LinkList));if(p->expn<q->expn){z->coef=p->coef; z->expn=p->expn; z->next=NULL;p=p->next; w->next=z; w=w->next;}else if(p->expn>q->expn){z->coef=q->coef; z->expn=q->expn; z->next=NULL;q=q->next; w->next=z; w=w->next;}else if(p->expn==q->expn){z->coef=p->coef+q->coef; z->expn=p->expn; z->next=NULL;p=p->next; q=q->next; w->next=z; w=w->next;}}if(p==NULL){for(;q!=NULL;){z=(LinkList *)malloc(sizeof(LinkList));z->coef=q->coef; z->expn=q->expn; z->next=NULL;q=q->next; w->next=z; w=w->next;}}else if(q==NULL){for(;p!=NULL;){z=(LinkList *)malloc(sizeof(LinkList));z->coef=p->coef; z->expn=p->expn; z->next=NULL;p=p->next; w->next=z; w=w->next;}}for(w=(*X);w!=NULL;w=w->next){printf("%lf %d\n",w->coef,w->expn);}}void SubtractPolyn(LinkList *M, LinkList *N, LinkList **X)//多项式减法{LinkList *p=NULL, *q=NULL, *w=NULL, *z=NULL;(*X)=(LinkList *)malloc(sizeof(LinkList));(*X)->coef=0; (*X)->expn=0; (*X)->next=NULL;for(p=M,q=N,w=(*X);(p!=NULL)&&(q!=NULL);){z=(LinkList *)malloc(sizeof(LinkList));if(p->expn<q->expn){z->coef=p->coef; z->expn=p->expn; z->next=NULL;p=p->next; w->next=z; w=w->next;}else if(p->expn>q->expn){z->coef=-q->coef; z->expn=q->expn; z->next=NULL;q=q->next; w->next=z; w=w->next;}else if(p->expn==q->expn){z->coef=p->coef-q->coef; z->expn=p->expn; z->next=NULL;p=p->next; q=q->next; w->next=z; w=w->next;}}if(p==NULL){for(;q!=NULL;){z=(LinkList *)malloc(sizeof(LinkList));z->coef=-q->coef; z->expn=q->expn; z->next=NULL;q=q->next; w->next=z; w=w->next;}}else if(q==NULL){for(;p!=NULL;){z=(LinkList *)malloc(sizeof(LinkList));z->coef=p->coef; z->expn=p->expn; z->next=NULL;p=p->next; w->next=z; w=w->next;}}/*for(w=(*X);w!=NULL;w=w->next){printf("%lf %d\n",w->coef,w->expn);}*/}void ValuePolyn(LinkList *h, double x)//多项式求值{double sum=0, a=0;while(h!=NULL){a=pow(x,h->expn);sum=sum+(h->coef)*a;h=h->next;}printf("所求多项式的值为%lf\n",sum);}void DeletePolyn(LinkList **h){LinkList *p=(*h)->next; (*h)=NULL;while(p!=NULL){free(*h);(*h)=p;p=p->next;}}void RevisePolyn(LinkList **h, int i){int n=0;int choose=0;double m=0;LinkList *q=NULL, *w=NULL;PrintPolyn((*h),i);printf("请输入你想执行的操作代号（添加：1；修改：2；删除：3）\n");scanf("%d",&choose);switch(choose){case 1:{printf("输入你想要添加项的系数和次数\n");scanf("%lf%d",&m,&n);q=(LinkList *)malloc(sizeof(LinkList));q->coef=m; q->expn=n; q->next=NULL;for(w=(*h);w->next!=NULL;w=w->next){if((w->expn>q->expn)&&(w==*h)){q->next=(*h);(*h)=q;break;}else if((w->expn<q->expn)&&(w->next->expn>q->expn)) {q->next=w->next;w->next=q;break;}}if(w->expn<n) w->next=q;break;}case 2:{printf("输入你想要修改项的系数和次数\n");scanf("%lf%d",&m,&n);for(w=(*h);w!=NULL;w=w->next){if(w->expn==n) w->coef=m;}printf("未找到该项。

数据结构课程设计系别电子信息系专业计算机科学与技术班级学号4090113姓名王健指导教师党群成绩2011年7 月14 日目录一、课程题目 (1)二、需求分析 (1)三、测试数据 (2)四、概要设计 (2)五、调用关系图 (3)六、程序代码 (3)七、心得体会及总结 (12)数据结构课程设计一、课程题目一元稀疏多项式计算器二、需求分析1、一元稀疏多项式简单计算器的功能是：1.1 输入并建立多项式；1.2 输出多项式，输出形式为整数序列：n，c1,e1,c2,e2,………cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；1.3 求多项式a、b的导函数；1.4 计算多项式在x处的值；1.5多项式a和b相加，建立多项式a+b；1.6 多项式a和b相减，建立多项式a-b。

2、设计思路:2.1 定义线性表的动态分配顺序存储结构；2.2 建立多项式存储结构，定义指针*next2.3利用链表实现队列的构造。

每次输入一项的系数和指数，可以输出构造的一元多项式2.4演示程序以用户和计算机的对话方式执行，即在计算机终站上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令；最后根据相应的输入数据（滤去输入中的非法字符）建立的多项式以及多项式相加的运行结果在屏幕上显示。

多项式显示的格式为：c1x^e1+c2x^e2+…+cnx^en3、设计思路分析要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将结点结构体定义为运用尾插法建立两条单链表，以单链表polyn p和polyn h分别表示两个一元多项式a和b，a+b的求和运算等同于单链表的插入问题（将单链表polyn p中的结点插入到单链表polyn h中），因此“和多项式”中的结点无须另生成。

为了实现处理，设p、q分别指向单链表polya和polyb的当前项，比较p、q结点的指数项，由此得到下列运算规则：① 若p->expn<q->expn，则结点p所指的结点应是“和多项式”中的一项，令指针p后移。

数据结构实习报告班级 XXXXXX学生姓名 XXXXXX学号 *******XXXX指导教师 XXXXXX日期 2012年11月10日报告简介：整篇实习报告主要分为三部分：实习一，实习二以及实习困惑。

其中每个实习报告涉及6个部分：需求分析，设计，调试分析，用户手册，测试结果，源程序清单。

具体报告内容如下：实习一：一元稀疏多项式运算器的设计1、需求分析【问题描述】设计一个一元稀疏多项式简单计算器。

【基本要求】（1）输入并建立两个多项式；（2）多项式a与b相加，建立和多项式c；（3）多项式a与b相减，建立和多项式d；（4）输出多项式a,b,c,d。

输出格式：比如多项式a为：A(x)=c1xe1+ c2xe2+…+ cmxem，其中，ci和ei分别为第i项的系数和指数，且各项按指数的升幂排列，即0≤e1＜e2＜…＜em。

2、设计（1）设计思想存储结构：以带头结点的单链表存储多项式。

算法主要思想：●首先定义单链表中每个结点的结构体类型，设计能够生成多项式链表的函数，这个函数的功能是可以根据给定的多项式来创建存储它的单链表。

●然后需要设计两个多项式相加的函数与两个多项式相减的函数。

●要检验多项式的运算结果以及初始的多项式链表正确与否，需要将其打印输出，故还需要设计打印输出函数。

●主函数的设计：依次调用多项式链表生成的函数、多项式相加减的函数，最后将结果打印输出。

（2）概要设计整个算法需要设计五个函数，分别是：多项式链表生成的函数、两个多项式相加的函数、两个多项式相减的函数、打印输出的函数以及主函数。

在设计各个函数之前，要定义单链表结点的结构体类型。

每个结点应该包括指数code、系数exp和指向下一个结点的指针next。

多项式链表生成的函数：函数的返回值应该为定义的结构体类型，不需要设置参数。

函数内部，需要有多项式指数和系数的输入，直至输入的系数为零时结束，将每一对输入的指数和系数保存到新结点中，并将结点插入到链表中。

#include<stdio.h>#include<malloc.h>#include<math.h>#include<stdlib.h>typedef struct{float coef;int expn;}term,ElemType;typedef struct LNode{ElemType data;struct LNode *next;}*Link;typedef struct{Link head,tail;int len;}LinkList;/*====================链表-ADT====================*/ void MakeNode(Link &p,ElemType e){p=(Link)malloc(sizeof(struct LNode));if(!p) exit(1);p->data=e;p->next=NULL;}//MakeNodevoid InitList(LinkList &L){L.head=L.tail=(Link)malloc(sizeof(LNode));if(!L.head) exit(1);L.head->next=NULL;L.len=0;}//InitListvoid DestroyList(LinkList &L){Link p,q;p=L.head->next;while(p){q=p->next;free(p);p=q;}L.head->next=NULL;L.tail=L.head;L.len=0;}//DestroyListvoid InsLast(LinkList &L,Link s){L.tail->next=s;L.tail=s;L.len++;L.tail->next=NULL;}//InsLastvoid Append(LinkList &L,Link s){Link q;int m;if(!s) exit(1);L.tail->next=s;q=s;m=1;while(q->next){m++;q=q->next;}L.len+=m;L.tail=q;}//Append/*====================多项式-ADT====================*/ void CreatPolyn(LinkList &L){term e;Link s;scanf("%f,%d",&e.coef,&e.expn);while(e.coef){MakeNode(s,e);InsLast(L,s);scanf("%f,%d",&e.coef,&e.expn);}L.tail->next=NULL;}//CreatPolynint Judge(int n){if(n>19||n<0){printf("存储位置选择错误!请重新选择0-19.\n");return 1;}elsereturn 0;}//Judgevoid PrintPolyn(LinkList L){Link p;p=L.head->next;if(!p)printf("NULL\n");else {printf("y=");if(p->data.coef>0){if(p->data.expn==0)printf("%f",p->data.coef);elseprintf("%fx^%d",p->data.coef,p->data.expn);p=p->next;}else{if(p->data.expn==0)printf("%f",p->data.coef);elseprintf("%fx^%d",p->data.coef,p->data.expn);p=p->next;}while(p){if(p->data.coef>0){if(p->data.expn==0)printf("+%f",p->data.coef);elseprintf("+%fx^%d",p->data.coef,p->data.expn);p=p->next;}else{if(p->data.expn==0)printf("%f",p->data.coef);elseprintf("%fx^%d",p->data.coef,p->data.expn);if(p->next)p=p->next;}}printf("\n");}}//PrintPolynvoid PrintAll(LinkList S[]){int i;for(i=0;i<20;i++){printf("%d.",i);PrintPolyn(S[i]);}}//PrintAllvoid CopyPolyn(LinkList L,LinkList &S){term e;Link s,p;p=L.head->next;while(p){e.coef=p->data.coef;e.expn=p->data.expn;MakeNode(s,e);InsLast(S,s);p=p->next;}S.tail->next=NULL;}//CopyPolynint AddPolyn(LinkList &L,LinkList P,LinkList Q){ Link a,b,c;term e;a=P.head->next;b=Q.head->next;while((a!=NULL)&&(b!=NULL)){if(a->data.expn<b->data.expn){e.coef=a->data.coef;e.expn=a->data.expn;MakeNode(c,e);InsLast(L,c);a=a->next;}else if(a->data.expn>b->data.expn){e.coef=b->data.coef;e.expn=b->data.expn;MakeNode(c,e);InsLast(L,c);b=b->next;}else if((a->data.coef+b->data.coef)!=0){e.coef=a->data.coef+b->data.coef;e.expn=a->data.expn;MakeNode(c,e);InsLast(L,c);a=a->next;b=b->next;}else if((a->data.coef+b->data.coef)==0){a=a->next;b=b->next;}}if(!a&&!b){L.tail->next=NULL;return 0;}if(!b){while(a){e.coef=a->data.coef;e.expn=a->data.expn;MakeNode(c,e);InsLast(L,c);a=a->next;}}if(!a){while(b){e.coef=b->data.coef;e.expn=b->data.expn;MakeNode(c,e);InsLast(L,c);b=b->next;}}return 0;}//AddPolynvoid SubtractPolyn(LinkList &L,LinkList P,LinkList Q){ Link p;p=Q.head->next;while(p){p->data.coef=0-p->data.coef;p=p->next;}AddPolyn(L,P,Q);p=Q.head->next;while(p){p->data.coef=0-p->data.coef;p=p->next;}}//SubtractPolyndouble ResultPolyn(LinkList L,float x){Link p;double y=0;p=L.head->next;while(p){y+=(pow(x,p->data.expn)*p->data.coef);p=p->next;}return y;}//ResultPolynvoid MultiplyPolyn(LinkList &L,LinkList P,LinkList Q){ Link l,p,q;LinkList E,F;InitList(E);InitList(F);int i,j;term e;p=P.head->next;q=Q.head->next;for(i=0;i<Q.len;i++){for(j=0;j<P.len;j++){e.coef=p->data.coef*q->data.coef;e.expn=p->data.expn+q->data.expn;MakeNode(l,e);InsLast(E,l);p=p->next;}AddPolyn(L,E,F);DestroyList(E);DestroyList(F);CopyPolyn(L,F);if(i!=Q.len-1)DestroyList(L);q=q->next;p=P.head->next;}}//MultiplyPolynvoid Polyn_NFang(LinkList &L,LinkList P,int n){ int i;LinkList E;InitList(E);CopyPolyn(P,E);for(i=0;i<n;i++){MultiplyPolyn(L,E,P);DestroyList(E);CopyPolyn(L,E);if(i!=n-1)DestroyList(L);}}//Polyn_NFangvoid Polyn_NDao(LinkList &L,LinkList P,int n){ Link p,q;int i,j;CopyPolyn(P,L);for(i=0;i<n;i++){p=L.head->next;q=L.head;for(j=0;j<L.len;j++){if(p->data.expn==0){q->next=p->next;free(p);p=q->next;L.len--;}p->data.coef=p->data.coef*p->data.expn;p->data.expn=p->data.expn-1;p=p->next;q=q->next;}}}//Polyn_NDaoint Polyn_Ji(LinkList &L,LinkList P){Link p;int i;CopyPolyn(P,L);p=L.head->next;for(i=0;i<L.len;i++){if(p->data.expn==-1){printf("对不起，本程序不能实现对-1次方的积分.请重新选择.\n");DestroyList(L);return 0;}elsep=p->next;}for(i=0;i<L.len;i++){p->data.coef=p->data.coef/(p->data.expn+1);++p->data.expn;p=p->next;}return 0;}//Polyn_Jidouble Polyn_Ding(LinkList L,float a,float b){double m,n;double e=0;LinkList P;InitList(P);Polyn_Ji(P,L);m=ResultPolyn(P,a);n=ResultPolyn(P,b);e=n-m;return e;}//Polyn_Ding/*====================main====================*/void main(){int n,m,i,a,b,c;float x,e,f;double d;LinkList S[20];for(i=0;i<20;i++)InitList(S[i]);printf("说明：共有二十个多项式备用位置:0~19。