数据结构程序设计作业——《一元多项式的四则运算》

数据结构07082018用链表实现多项式的四则运算——数据结构第二次上机作业班级07082姓名丁敏学号07082018上机时间2011年3月31日报告时间：2011年4月5日实验目的：熟练使用指针，熟悉链表及其操作；利用链表解决实际问题要求：能够实现任意项有理多项式的加、减、乘、除、求模以及幂运算多项式的除法注意除不尽的处理测试用例尽可能多，且说明用例的必要性用例必须包含一个自己系数为自己的学号摘要：多项式的四则运算问题是个很有趣的问题，它类似于有理数的四则运算，但又不仅仅于此.本篇课程论文重点研究了数据结构中多项式的四则运算问题。

本论文的程序是通过Microsoft Visual Studio 2010编译，来解决多项式的加、减、乘、除四则运算问题，从而达到了解数据结构的实用性及程序语言对于数学问题研究的重要性的目的。

正文：0需求分析：0.1问题描述编写程序来实现多项式的四则运算。

0.2基本要求⑴输入多项式的系数与指数，输入值为float型，输出值为float型；⑵能够完成多项式之间的四种计算方式（+、-、*、/）。

0.3函数说明typedef struct PolyNode：结构体变量，定义 int型指数和float 系数；PolyList CreatePolyList()：创建多项式列表，返回头指针；DisplayPolyList(PolyList Poly)：显示多项式；DestroyPolyList(PolyList L)：释放链表所用存储空间；MergePoly(PolyList Poly)：将多项式合并同类项；SortPoly(PolyList Poly)：将多项式按升序排列；PolyList PolyAdd(PolyList PolyA , PolyList PolyB)：多项式相加，返回和多项式链表头指针；PolyList PolySub(PolyList polyA , PolyList polyB)：多项式相减，返回差多项式链表头指针;PolyList PolyMutiply(PolyList PolyA , PolyList PolyB)：多项式相乘，结果由Poly c返回；PolyList PolyDivide(PolyList PolyA , PolyList PolyB)：多项式相除，商和余数用系数为0的结点分开。

数据结构——四则运算要进⾏⼀个表达式的计算，⼀个关键的就是括号匹配问题，现在使⽤栈进⾏实现计算表达式的值，可以作为实现⼀个简单四则运算计算器核⼼部分。

根据栈的特性（先进后出），所以决定通过把输⼊的表达式转换为后缀表达式，通过后缀表达式进⾏计算。

实现⽅法：1.⾸先定义两个栈，⼀个⽤于存放操作符，⼀个⽤于存放操作数。

1 #include<stdio.h>2 #include<string>3 #include<conio.h>4#define MAXSIZE 1005 typedef float datatype;67 typedef struct8 {9 datatype a[MAXSIZE];10int top;11 }sequence_stack;1213 typedef struct14 {15char b[MAXSIZE];16int top;17 }SeqStack;2.需要两个数组，⼀个⽤于存放输⼊的中缀表达式，⼀个⽤于存放将中缀表达式转换后的后缀表达式。

将中缀表达式转换为后缀表达式的主要代码：1int operation(char op)//判断是否为操作符2 {3switch(op)4 {5case'+':6case'-':7case'*':8case'/':return1;9default:return0;10 }11 }12int priority(char op)//判断操作符的优先级13 {14switch(op)15 {16case'#':return -1;17case'(':return0;18case'+':19case'-':return1;20case'*':21case'/':return2;22default: return -1;23 }24 }25//将中缀表达式转换为后缀表达式26void postfix(char e[],char f[],SeqStack *s,sequence_stack *s1)27 {28int i=0,j=0;29int t;30 push_SeqStack(s,'#');31while(e[i]!='#')32 {33if((e[i]>='0'&&e[i]<='9')||e[i]=='.')34 f[j++]=e[i];35else if(e[i]=='(')36 {37 push_SeqStack(s,e[i]);38 }39else if(e[i]==')')40 {41 t=s->top-1;42while(s->b[t]!='(')43 {44 f[j++]=s->b[--s->top];45 t=s->top-1;46 }47 s->top--;48 }49else if(operation(e[i]))50 {51 f[j++]=' ';52while(priority(s->b[s->top-1])>=priority(e[i]))53 f[j++]=s->b[--s->top];54 push_SeqStack(s,e[i]);55 }56 i++;57 }58while (s->top)f[j++]=s->b[--s->top];59 {}60 evalpost(f,s1);61 }3.把存放后缀表达式的数组传递给计算后表达式的函数；计算后缀表达式的值主要代码：1float readnumber(char f[],int *i)//将数字字符串转变为数2 {3float x=0.0;4int k=0;5while(f[*i]>='0'&&f[*i]<='9')6 {7 x=x*10+(f[*i]-'0');8 (*i)++;9 }10if(f[*i]=='.')11 {12 (*i)++;13while(f[*i]>='0'&&f[*i]<='9')14 {15 x=x*10+(f[*i]-'0');16 (*i)++;17 k++;18 }19 }20while(k!=0)21 {22 x=x/10.0;23 k=k-1;24 }25return (x);26 }27void evalpost(char f[],sequence_stack *s)28 {29int i=0;30float x1,x2;31while(f[i]!='#')32 {33if(f[i]>='0'&&f[i]<='9')34 {35 push_sequence_stack(s,readnumber(f,&i));36 }37else if(f[i]==' ')38 i++;39else if(f[i]=='+')40 {41 x2=s->a[--s->top];42 x1=s->a[--s->top];43 push_sequence_stack(s,x1+x2);44 i++;45 }46else if(f[i]=='-')47 {48 x2=s->a[--s->top];49 x1=s->a[--s->top];50 push_sequence_stack(s,x1-x2);51 i++;52 }53else if(f[i]=='*')54 {55 x2=s->a[--s->top];56 x1=s->a[--s->top];57 push_sequence_stack(s,x1*x2);58 i++;59 }60else if(f[i]=='/')61 {62 x2=s->a[--s->top];63 x1=s->a[--s->top];64 push_sequence_stack(s,x1/x2);65 i++;66 }67 }68 }最后，只要调⽤计算后的结果将存放在操作数栈的第⼀个位置，并将结果传递给需要显⽰的地⽅（可以放到⾃⼰的程序中显⽰结果的地⽅），显⽰出结果就没问题了。

一元多项式计算(数据结构课程设计)一、系统设计1、算法思想根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应指数相加（减），若其和（差）不为零，则构成“和（差）多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别写到“和（差）多项式”中去。

因为多项式指数最高项以及项数是不确定的，因此采用线性链表的存储结构便于实现一元多项式的运算。

为了节省空间，我采用两个链表分别存放多项式a 和多项式b，对于最后计算所得的多项式则利用多项式a进行存储。

主要用到了单链表的插入和删除操作。

(1)一元多项式加法运算它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就应该相加；相加的和不为零的话，用头插法建立一个新的节点。

P 的指数小于q的指数的话就应该复制q的节点到多项式中。

P的指数大于q的指数的话，就应该复制p节点到多项式中。

当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。

当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生。

(2)一元多项式的减法运算它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就相减；相加的和不为零的话，用头插法建立一个新的节点。

p的指数小于q的指数的话，就应该复制q的节点到多项式中。

P的指数大于q的指数的话就应该复制p的节点到多项式中，并且建立的节点的系数为原来的相反数；当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。

当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生，并且建立的节点的系数为原来的相反数。

2、概要设计(1)主函数流程图：（注：a代表第一个一元二次方程，b代表第二个一元二次方程）(2)一元多项式计算算法用类C语言表示：Typedef struct00{ //项的表示，多项式的项作为LinkList的数据元素Float coef；//细数Int expn；//指数}term，ElemType；//两个类型名：term用于本ADT，ElemType为LinkList的数据对象名Typedef LinkList polynomial：//用带表头的节点的有序链表表示多项式//基本操作的函数原型说明Void CreatePolyn（polynomail&P）；//输入n的系数和指数，建立表示一元多项式的有序链表P 销毁一元多项式P Void DestroyPolyn（polynomailP）；销毁一元多项式PvoidPrintPoly（polynomail P）；//打印输入一元多项式PIntPolynLength（polynnomail P);//返回一元多项式P中的项数void CreatPolyn（polynomail&Pa.polunomail&Pb);//完成多项式相加运算，即:Pa=Pa+Pb,并贤惠一元多项式Pb voidSubtractPolyn（polunomail&Papolunomail&Pb）；//完成多项式相减运算，即：Pa=Pa-Pb，并销毁一元多项式Pb//基本操作的算法描述Int cmp(tem a，temp b）；//依a的指数值<（或=）（或>b的住数值，分别返回-1、0和+1Void CreatePolyn（polynomail&P,int m){//输入m项的系数和指数，建立表示一元多项式的有序链表PInitList（P）；h=GetHead（P）；E.coef=0.0； e.expn=-1；S erCurElem（h，e）；//设置头结点的数据元素For （i=1；i<=m；++i）{ //依次输入m个非零项Scanf（e.coef，e.epn）；If（！LocateElem（P，e，q，（*cmp）（）））{//当前链表中不存在该指数项If(MakeNode（s，e））InsFirst（q，s）；//生成节点并插入链表}}}//CreatPolun二、详细设计1、算法实现(1)输入一元多项式函数：void shuchu(pnode *head){pnode *p;int one_time=1;p=head;while(p!=NULL) /*如果不为空*/{if(one_time==1){if(p->zhishu==0) /*如果指数为0的话，直接输出系数*/printf("%5.2f",p->xishu); /*如果系数是正的话前面就要加+号*/else if(p->xishu==1||p->xishu==-1)printf("X^%d",p->zhishu); /*如果系数是1的话就直接输出+x*//*如果系数是-1的话就直接输出-x号*/else if(p->xishu>0) /*如果系数是大于0的话就输出+系数x^指数的形式*/ printf("%5.2fX^%d",p->xishu,p->zhishu);else if(p->xishu<0) /*如果系数是小于0的话就输出系数x^指数的形式*/ printf("%5.2fX^%d",p->xishu,p->zhishu);one_time=0;}else{if(p->zhishu==0) /*如果指数为0的话，直接输出系数*/{if(p->xishu>0)printf("+%5.2f",p->xishu); /*如果系数是正的话前面就要加+号*/}else if(p->xishu==1) /*如果系数是1的话就直接输出+x号*/printf("+X^%d",p->zhishu);else if(p->xishu==-1) /*如果系数是-1的话就直接输出-x号*/printf("X^%d",p->zhishu);else if(p->xishu>0) /*如果系数是大于0的话就输出+系数x^指数的形式*/ printf("+%5.2fX^%d",p->xishu,p->zhishu);else if(p->xishu<0) /*如果系数是小于0的话就输出系数x^指数的形式*/printf("%5.2fX^%d",p->xishu,p->zhishu);}p=p->next; /*指向下一个指针*/}printf("\n");}(2)加法函数/*两个多项式的加法运算*/pnode * add(pnode *heada,pnode *headb){pnode *headc,*p,*q,*s,*r; /*headc为头指针，r,s为临时指针，p指向第1个多项式并向右移动，q指向第2个多项式并向右移动*/float x; /*x为系数的求和*/p=heada; /*指向第一个多项式的头*/q=headb; /*指向第二个多项式的头*/headc=(pnode *)malloc(sizeof(pnode)); /*开辟空间*/r=headc;while(p!=NULL&&q!=NULL) /*2个多项式的某一项都不为空时*/{if(p->zhishu==q->zhishu) /*指数相等的话*/{x=p->xishu+q->xishu; /*系数就应该相加*/if(x!=0) /*相加的和不为0的话*/{s=(pnode *)malloc(sizeof(pnode)); /*用头插法建立一个新的节点*/s->xishu=x;s->zhishu=p->zhishu;r->next=s;r=s;}q=q->next;p=p->next; /*2个多项式都向右移*/}else if(p->zhishu<q->zhishu) /*p的系数小于q的系数的话，就应该复制q节点到多项式中*/{s=(pnode *)malloc(sizeof(pnode));s->xishu=q->xishu;s->zhishu=q->zhishu;r->next=s;r=s;q=q->next; /*q向右移动*/}else/*p的系数大于q的系数的话，就应该复制p节点到多项式中*/{s=(pnode *)malloc(sizeof(pnode));s->xishu=p->xishu;s->zhishu=p->zhishu;r->next=s;r=s;p=p->next; /*p向右移动*/}}/*当第2个多项式空，第1个数不为空时，将第一个数剩下的全用新节点产生*/ while(p!=NULL){s=(pnode *)malloc(sizeof(pnode));s->xishu=p->xishu;s->zhishu=p->zhishu;r->next=s;r=s;p=p->next;}/*当第1个多项式空，第1个数不为空时，将第2个数剩下的全用新节点产生*/ while(q!=NULL){s=(pnode *)malloc(sizeof(pnode));s->xishu=q->xishu;s->zhishu=q->zhishu;r->next=s;r=s;q=q->next;}r->next=NULL; /*最后指向空*/headc=headc->next; /*第一个头没有用到*/return headc; /*返回头接点*/}(3)减法函数/*两个多项式的加法运算*/pnode * add(pnode *heada,pnode *headb){pnode *headc,*p,*q,*s,*r; /*headc为头指针，r,s为临时指针，p指向第1个多项式并向右移动，q指向第2个多项式并向右移动*/float x; /*x为系数的求和*/p=heada; /*指向第一个多项式的头*/q=headb; /*指向第二个多项式的头*/headc=(pnode *)malloc(sizeof(pnode)); /*开辟空间*/r=headc;while(p!=NULL&&q!=NULL) /*2个多项式的某一项都不为空时*/{if(p->zhishu==q->zhishu) /*指数相等的话*/{x=p->xishu+q->xishu; /*系数就应该相加*/if(x!=0) /*相加的和不为0的话*/{s=(pnode *)malloc(sizeof(pnode)); /*用头插法建立一个新的节点*/s->xishu=x;s->zhishu=p->zhishu;r->next=s;r=s;}q=q->next;p=p->next; /*2个多项式都向右移*/}else if(p->zhishu<q->zhishu) /*p的系数小于q的系数的话，就应该复制q节点到多项式中*/{s=(pnode *)malloc(sizeof(pnode));s->xishu=q->xishu;s->zhishu=q->zhishu;r->next=s;r=s;q=q->next; /*q向右移动*/}else/*p的系数大于q的系数的话，就应该复制p节点到多项式中*/{s=(pnode *)malloc(sizeof(pnode));s->xishu=p->xishu;s->zhishu=p->zhishu;r->next=s;r=s;p=p->next; /*p向右移动*/}}/*当第2个多项式空，第1个数不为空时，将第一个数剩下的全用新节点产生*/ while(p!=NULL){s=(pnode *)malloc(sizeof(pnode));s->xishu=p->xishu;s->zhishu=p->zhishu;r->next=s;r=s;p=p->next;}/*当第1个多项式空，第1个数不为空时，将第2个数剩下的全用新节点产生*/ while(q!=NULL){s=(pnode *)malloc(sizeof(pnode));s->xishu=q->xishu;s->zhishu=q->zhishu;r->next=s;r=s;q=q->next;}r->next=NULL; /*最后指向空*/headc=headc->next; /*第一个头没有用到*/return headc; /*返回头接点*/}2、程序代码/*一元多项式计算*//*程序功能：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输出；*//*提示：输入完一元多项式之后，输入“0 0”结束本一元多项式的输入*//*注意：系数只精确到百分位，最大系数只能为999.99,指数为整数.如果需要输入更大的系数，可以对程序中5.2%f进行相应的修改*/#include<stdio.h>#include<malloc.h>#include<stdlib.h>#include<conio.h>/*建立结构体*/typedef struct pnode{float xishu; /*系数*/int zhishu; /*指数*/struct pnode *next; /*下一个指针*/}pnode;/*用头插法生成一个多项式，系数和指数输入0时退出输入*/pnode * creat()int m;float n;pnode *head,*rear,*s; /*head为头指针，rear和s为临时指针*/ head=(pnode *)malloc(sizeof(pnode));rear=head; /*指向头*/scanf("%f",&n); /*系数*/scanf("%d",&m); /*输入指数*/while(n!=0) /*输入0退出*/{s=(pnode *)malloc(sizeof(pnode));s->xishu=n;s->zhishu=m;s->next=NULL;rear->next=s; /*头插法*/rear=s;scanf("%f",&n); /*输入系数*/scanf("%d",&m); /*输入指数*/}head=head->next; /*第一个头没有用到*/return head;}/*调整多项式*/void tiaozhen(pnode *head){pnode *p,*q,*t;float temp;p=head;while(p!=NULL){q=p;t=q->next;while(t!=NULL){if(t->zhishu>q->zhishu)q=t;t=t->next;}temp=p->xishu;p->xishu=q->xishu;q->xishu=temp;temp=p->zhishu;p->zhishu=q->zhishu;q->zhishu=temp;p=p->next;}/*显示一个多项式*/void shuchu(pnode *head){pnode *p;int one_time=1;p=head;while(p!=NULL) /*如果不为空*/{if(one_time==1){if(p->zhishu==0) /*如果指数为0的话，直接输出系数*/printf("%5.2f",p->xishu); /*如果系数是正的话前面就要加+号*/else if(p->xishu==1||p->xishu==-1)printf("X^%d",p->zhishu); /*如果系数是1的话就直接输出+x*//*如果系数是-1的话就直接输出-x号*/else if(p->xishu>0) /*如果系数是大于0的话就输出+系数x^指数的形式*/ printf("%5.2fX^%d",p->xishu,p->zhishu);else if(p->xishu<0) /*如果系数是小于0的话就输出系数x^指数的形式*/ printf("%5.2fX^%d",p->xishu,p->zhishu);one_time=0;}else{if(p->zhishu==0) /*如果指数为0的话，直接输出系数*/{if(p->xishu>0)printf("+%5.2f",p->xishu); /*如果系数是正的话前面就要加+号*/}else if(p->xishu==1) /*如果系数是1的话就直接输出+x号*/printf("+X^%d",p->zhishu);else if(p->xishu==-1) /*如果系数是-1的话就直接输出-x号*/printf("X^%d",p->zhishu);else if(p->xishu>0) /*如果系数是大于0的话就输出+系数x^指数的形式*/ printf("+%5.2fX^%d",p->xishu,p->zhishu);else if(p->xishu<0) /*如果系数是小于0的话就输出系数x^指数的形式*/ printf("%5.2fX^%d",p->xishu,p->zhishu);}p=p->next; /*指向下一个指针*/}printf("\n");/*两个多项式的加法运算*/pnode * add(pnode *heada,pnode *headb){pnode *headc,*p,*q,*s,*r; /*headc为头指针，r,s为临时指针，p指向第1个多项式并向右移动，q指向第2个多项式并向右移动*/float x; /*x为系数的求和*/p=heada; /*指向第一个多项式的头*/q=headb; /*指向第二个多项式的头*/headc=(pnode *)malloc(sizeof(pnode)); /*开辟空间*/r=headc;while(p!=NULL&&q!=NULL) /*2个多项式的某一项都不为空时*/{if(p->zhishu==q->zhishu) /*指数相等的话*/{x=p->xishu+q->xishu; /*系数就应该相加*/if(x!=0) /*相加的和不为0的话*/{s=(pnode *)malloc(sizeof(pnode)); /*用头插法建立一个新的节点*/s->xishu=x;s->zhishu=p->zhishu;r->next=s;r=s;}q=q->next;p=p->next; /*2个多项式都向右移*/}else if(p->zhishu<q->zhishu) /*p的系数小于q的系数的话，就应该复制q节点到多项式中*/{s=(pnode *)malloc(sizeof(pnode));s->xishu=q->xishu;s->zhishu=q->zhishu;r->next=s;r=s;q=q->next; /*q向右移动*/}else/*p的系数大于q的系数的话，就应该复制p节点到多项式中*/{s=(pnode *)malloc(sizeof(pnode));s->xishu=p->xishu;s->zhishu=p->zhishu;r->next=s;r=s;p=p->next; /*p向右移动*/}}/*当第2个多项式空，第1个数不为空时，将第一个数剩下的全用新节点产生*/ while(p!=NULL){s=(pnode *)malloc(sizeof(pnode));s->xishu=p->xishu;s->zhishu=p->zhishu;r->next=s;r=s;p=p->next;}/*当第1个多项式空，第1个数不为空时，将第2个数剩下的全用新节点产生*/ while(q!=NULL){s=(pnode *)malloc(sizeof(pnode));s->xishu=q->xishu;s->zhishu=q->zhishu;r->next=s;r=s;q=q->next;}r->next=NULL; /*最后指向空*/headc=headc->next; /*第一个头没有用到*/return headc; /*返回头接点*/}/*两个多项式的减法运算*/pnode * sub(pnode *heada,pnode *headb){pnode *headc,*p,*q,*s,*r;float x; /*x为系数相减*/p=heada; /*指向第一个多项式的头*/q=headb; /*指向第二个多项式的头*/headc=(pnode *)malloc(sizeof(pnode)); /*开辟空间*/r=headc;while(p!=NULL&&q!=NULL) /*两个多项式的某一项都不为空时*/{if(p->zhishu==q->zhishu) /*指数相等的话*/{x=p->xishu-q->xishu; /*系数相减*/if(x!=0) /*相减的差不为0的话*/{s=(pnode *)malloc(sizeof(pnode)); /*用头插法建立一个新的节点*/s->xishu=x;s->zhishu=p->zhishu;r->next=s;r=s;}q=q->next;p=p->next; /*2个多项式都向右移*/}else if(p->zhishu<q->zhishu) /*p的系数小于q的系数的话*/{s=(pnode *)malloc(sizeof(pnode));s->xishu=-q->xishu; /*建立的节点的系数为原来的相反数*/s->zhishu=q->zhishu;r->next=s;r=s;q=q->next;}else{s=(pnode *)malloc(sizeof(pnode));s->xishu=p->xishu;s->zhishu=p->zhishu;r->next=s;r=s;p=p->next; /*p向右移动*/}}while(p!=NULL) /*当第2个多项式空，第1个数不为空时，将第一个数剩下的全用新节点产生*/{s=(pnode *)malloc(sizeof(pnode));s->xishu=p->xishu;s->zhishu=p->zhishu;r->next=s;r=s;p=p->next;}while(q!=NULL) /*当第1个多项式空，第1个数不为空时，将第2个数剩下的全用新节点产生*/{s=(pnode *)malloc(sizeof(pnode));s->xishu=-q->xishu; /*建立的节点的系数为原来的相反数*/ s->zhishu=q->zhishu;r->next=s;r=s;q=q->next;}r->next=NULL; /*最后指向空*/headc=headc->next; /*第一个头没有用到*/return headc; /*返回头接点*/}void add_main(){pnode * a,*b,*c;printf("\n输入第一个一元多项式:\n系数指数\n");a=creat();tiaozhen(a);printf("\n输入第二个一元多项式:\n系数指数\n");b=creat();tiaozhen(b);c=add(a,b);printf("第一个一元多项式如下:");shuchu(a);printf("第二个一元多项式如下:");shuchu(b);printf("两式相加如下:");shuchu(c);}void sub_main(){pnode * a,*b,*c;printf("\n输入第一个一元多项式:\n系数指数\n");a=creat();tiaozhen(a);printf("\n输入第二个一元多项式:\n系数指数\n");b=creat();tiaozhen(b);c=sub(a,b);printf("第一个一元多项式如下:");shuchu(a);printf("第二个一元多项式如下:");shuchu(b);printf("两式相减如下:");shuchu(c);}void open(){printf("\n****************************************************\n");printf(" 功能项: * 1 两个一元多项式相加;2 两个一元多项式相减;0 退出*\n");printf("****************************************************\n\n请选择操作: ");}void main(){int choose;open();while(choose!=0){scanf("%d",&choose);getchar();switch(choose){case 0:return;case 1:printf("\n 两个一元多项式相加\n");add_main();choose=-1;open();break;case 2:printf("\n 两个一元多项式相减\n");sub_main();choose=-1;open();break;default:printf("没有该选项!请重新选择操作!\n\n");open();}}}三、测试方案及结果1、测试方案在Visual C++ 6.0环境中调试运行。

C++开放项目实验报告题目：一元符号多项式四则运算姓名：指导老师：学号：班级：一、内容总结1.功能要求用所学C++知识编程实现两个一元符号多项式的加法，减法和乘法运算。

2.算法概要设计①结点插入函数void Insert (PNode *temp);②多项式的创建函数void CreatPoly();③赋值运算符的重载Polynomail& operator = (const Polynomail &p1);④一元符号多项式的加法Polynomail& operator + (const Polynomail &p);⑤一元符号多项式的减法Polynomail& operator - (Polynomail &p);⑥一元符号多项式的乘法Polynomail& operator * (const Polynomail &p);3.应用技巧①利用Insert（）插入函数规范多项式的输入问题，进行同类项的合并和不同类项间的排序问题，使得到有序的链表，方便后续的运算②对赋值、加、减和乘运算符进行重载，赋予其新的意义，进行多项式间的四则运算。

③发现函数间联系，可以减少代码的长度。

巧妙利用Insert()函数和加运算符重载函数，方便乘法和减法等代码编写。

二、实验成果1.输入要求按提示一次输入多项式各项的系数和指数，建立多项式。

如下所示: 系数，指数：1,2系数，指数：3,4系数，指数：0 4（以输入系数为零的项结束创建）创建结果为：1x^2+3x^4进行加法运算2根据自己的需要选择输入功能序号进行运算，如选择数字2.输出样例总体上各项是按照输入的方法进行输出，如果指数为零只输出系数，如果系数为零，那么该项不输出，如果系数为负数，那么两项间“+”变“-”。

以上述输入为例创建的结果为：1x^2+3x^4。

如果另一个多项式为：-1-2x^6，那么加法运算后的结果为：-1+1x^2+3x^4-2x^6：主要代码展示 3.//**** c++开放实验项目****//一元符号多项式的四则运算#include <iostream>using namespace std;struct PNode{PNode(double c=0,int e=-1){ coef=c; expn=e; next=NULL;}double coef;int expn;PNode *next;};class Polynomial{public:Polynomial(){poly=new PNode;}Polynomial(Polynomial &p);void Print();~Polynomial();void Insert (PNode *temp);void CreatPoly();Polynomial& operator = (const Polynomial &p);Polynomial& operator + (const Polynomial &p);Polynomial& operator - (Polynomial &p);Polynomial& operator * (const Polynomial &p);private:PNode *poly;};//析构函数Polynomial::~Polynomial(){PNode *pt=poly->next;while (pt){poly->next=pt->next;delete pt;pt=poly->next;}delete poly;poly=NULL;}//赋值运算符的重载Polynomial& Polynomial::operator = (const Polynomial &p){ this->~Polynomial();poly=new PNode;PNode *pt=poly,*qt=p.poly->next;while(qt){PNode *s=new PNode(qt->coef,qt->expn);pt->next=s;pt=s;qt=qt->next;}return *this;}//复制构造函数Polynomial::Polynomial(Polynomial &p){poly=new PNode;*this=p;}//遍历void Polynomial::Print(){if(poly->next==NULL){cout<<empty!\n;return;}PNode *pt=poly->next;if(pt){if(pt->expn==0){cout<<pt->coef;}else {潣瑵?瑰?潣晥?硜属?瑰?硥湰※}pt=pt->next;}while (pt){if(pt->expn==0){cout<<pt->coef;}else {if(pt->coef<0){潣瑵?瑰?潣晥?硜属?瑰?硥湰※}else {潣瑵???瀼?挾敯?尼幸?瀼?放灸?}}pt=pt->next;}cout<<endl;}//结点插入函数void Polynomial::Insert (PNode *temp){ if(poly->next==NULL){poly->next=temp;return;}PNode *pt=poly;PNode *qt=pt->next;while(qt&&qt->expn<temp->expn){ pt=qt;qt=pt->next;}if(qt==NULL||qt->expn>temp->expn){ temp->next=qt;pt->next=temp;}else {qt->coef+=temp->coef;if(qt->coef==0){pt->next=qt->next;delete qt;}}}//多项式的构建函数void Polynomial::CreatPoly(){double c;int e;潣瑵?系数，指数：;cin>>c>>e;while (c){PNode *p=new PNode(c,e);Insert(p);潣瑵?系数，指数：;cin>>c>>e;}}//多项式的加法Polynomial& Polynomial::operator + (const Polynomial &q){ Polynomial *PC=new Polynomial;PNode *ta=poly->next,*tb=q.poly->next, *tc=PC->poly; while(ta&&tb){int a=ta->expn;int b=tb->expn;int t=a>b?1:(b>a?-1:0);switch(t){case -1:{PNode *s=new PNode(ta->coef,ta->expn);tc->next=s;tc=s;ta=ta->next;break;}case 0:{double sum=ta->coef+tb->coef;if(sum==0){ta=ta->next;tb=tb->next;}else {PNode *s=new PNode(sum,ta->expn);tc->next=s;tc=s;ta=ta->next;tb=tb->next;}break;}case 1:{PNode *s=new PNode(tb->coef,tb->expn);tc->next=s;tc=tc->next;tb=tb->next;break;}} //switch} //whilewhile (ta){PNode *s=new PNode(ta->coef,ta->expn);tc->next=s;tc=s;ta=ta->next;}while (tb){PNode *s=new PNode(tb->coef,tb->expn);tc->next=s;tc=s;tb=tb->next;}return *PC;}//多项式的减法Polynomial& Polynomial::operator - (Polynomial &p){//复制取反相加Polynomial P(p),*PC=new Polynomial;PNode *pt=P.poly->next;while(pt){pt->coef=-pt->coef;pt=pt->next;}*PC=*this+P;return *PC;}//多项式的乘法Polynomial& Polynomial:: operator * (const Polynomial &p){ Polynomial *PC=new Polynomial;PNode *pt=poly->next,*qt;for(;pt;pt=pt->next){for(qt=p.poly->next;qt;qt=qt->next){PNode *s=new PNode(pt->coef*qt->coef,pt->expn+qt->expn);PC->Insert(s);}}return *PC;}//主函数int main(){Polynomial PA,PB,PC;int index;cout<< //------一元符号多项式的表示及运算------// <<endl;潣瑵?本函数的功能列表：<<endl;cout<<.多项式的加法:<<endl;cout<<.多项式的减法:<<endl;cout<<.多项式的乘法:<<endl;cout<<.选择重建多项式:<<endl;cout<<_x0005_.结束运算\n<<endl;潣瑵?依次输入PA各项系数和指数(以输入系数0项结束)，建立多项式：<<endl;PA.CreatPoly();PA.Print();潣瑵?依次输入PB各项系数和指数(以输入系数0项结束)，建立多项式：<<endl;PB.CreatPoly();PB.Print();cout<<\请输入功能序号进行多项式的运算：;cin>>index;while(index){switch(index){case 1:{PC=PA+PB;cout<<PC=PA+PB:;PC.Print();break;}case 2:{PC=PA-PB;cout<<PC=PA-PB:;PC.Print();break;}case 3:{PC=PA*PB;cout<<PC=PA*PB:;PC.Print();break;}case 4:{int flag;潣瑵?输入0修改多项式PA,其他数字保留多项式PA:;cin>>flag;if(!flag){PA.CreatPoly();PA.Print();}潣瑵?输入0修改多项式PB,其他数字保留多项式PB:;cin>>flag;if(!flag){PB.CreatPoly();PB.Print();}break;}case 5:{潣瑵?运算结束<<endl;return 0;}}//switchcout<<\是否需要继续，请再次输入选择：;cin>>index;}//whilereturn 0;}4.项目结果展示实践体会三、在此次的C++开放项目试验中，我承担了用C++实现一元符号多项式的四则运算，将所学C++知识运用实战编程中去，并及时进行知识的查缺补漏，帮助我更好的掌握了C++这门语言。

长沙学院课程设计说明书题目一元多项式计算问题系(部)计算机科学与技术系专业(班级)12软件4班姓名谢仲蛟学号2012022411指导教师邱建雄起止日期2013.12.9～2013.12.20课程设计任务书课程名称：数据结构与算法设计题目：一元多项式计算问题已知技术参数和设计要求：问题描述：设计一个稀疏多项式简单计算器基本要求：(1)输入并分别建立多项式A和B(2)输入输出多项式，输出形式为整数序列：n,c1,e1,c2,e2……，其中n是多项式的项数，ci和ei 是第i项的系数和指数，序列按指数降序排列(3)完成两个多项式的相加、相减，并将结果输出；测试数据：(1) A+B A= 3x14-8x8+6x2+2 B=2x10+4x8+-6x2(2) A-B A=11x14+3x10+2x8+10x6+5 B=2x14+3x8+5x6+7(3) A+B A=x3+x1 B=-x3-x1(4) A+B A=0 B=x7+x5+x3+x1(5) A-B A=100x100+50x50+20x20+x B=10x100+10x50+10x20+x选作内容：（1）.多项式在x=1时的运算结果（2）求多项式A和B的乘积设计工作量：40课时工作计划：指导教师签名：日期：教研室主任签名：日期：系主任签名：日期：长沙学院课程设计鉴定表摘要本次课程设计是在《数据结构》基础上设计以C语言来实现的，它的目的是帮助同学更深入的了解《数据结构》这门课程并熟练运用C语言，使同学达到熟练掌握的程度。

课程设计一个稀疏多项式简单计算器。

其基本要求有六：其一，输入建立两个多项式；其二,输出多项式，输出形式为整数序列：n，c1,e1,c2,e2……,其中n是多项式的项数，ci和ei是第i项的系数和指数，序列按指数的降序序列排列；其三，多项式排序，多项式按指数的降序序列排列；其四，多项式相加，指数相同系数相加，指数不同则把此项加进去；其五，多项式相减，指数相同系数相加，指数不同则把此项取反再加进去；其六，返回多项式的项数。

数据结构一元多项式的运算数据结构一元多项式的运算1、引言1.1 研究背景1.2 研究目的2、一元多项式的定义2.1 一元多项式的概念2.2 一元多项式的表示方法2.3 一元多项式的次数和系数2.4 一元多项式的零多项式和常数项2.5 一元多项式的加法运算2.6 一元多项式的减法运算2.7 一元多项式的乘法运算3、一元多项式的特殊运算3.1 一元多项式的乘方运算3.2 一元多项式的取余运算3.3 一元多项式的求导运算3.4 一元多项式的积分运算3.5 一元多项式的复合运算4、一元多项式的应用4.1 一元多项式在数学中的应用4.2 一元多项式在计算机科学中的应用4.3 一元多项式在工程领域中的应用5、实例分析5.1 实例一：一元多项式的相加减5.2 实例二：一元多项式的乘法运算5.3 实例三：一元多项式的特殊运算应用6、结论附件：附件一：一元多项式的代码实现示例法律名词及注释：1.一元多项式: 指仅有一个未知数的多项式。

2.多项式的次数: 多项式中各项最高次幂的次数。

3.多项式的系数: 多项式中各项中未知数的系数。

4.零多项式: 所有系数均为0的多项式。

5.常数项: 多项式中次数为0的项，即常数项。

6.多项式的加法运算: 将两个多项式相同次项的系数相加。

7.多项式的减法运算: 将两个多项式相同次项的系数相减。

8.多项式的乘法运算: 将两个多项式的各项相乘，并根据指数相加合并同类项。

9.多项式的乘方运算: 将一个多项式自乘n次。

10.多项式的取余运算: 两个多项式相除后的余数部分。

11.多项式的求导运算: 对多项式中的每一项进行求导操作。

12.多项式的积分运算: 对多项式中的每一项进行积分操作。

13.多项式的复合运算: 将一个多项式代入另一个多项式中进行运算。

c语言数据结构实现——一元多项式的基本运算在C语言中，一元多项式的表示与运算是常见的数据结构操作之一。

一元多项式由一系列具有相同变量的单项式组成，每个单项式由系数和指数组成。

本文将介绍如何使用C语言实现一元多项式的基本运算，包括多项式的创建、求和、差、乘积等操作。

首先，我们需要定义一个结构体来表示单项式。

每个单项式由一个系数和一个指数组成，我们可以将其定义如下：```cstruct term{float coefficient; // 系数int exponent; // 指数};typedef struct term Term;```接下来，我们可以定义一个结构体来表示一元多项式。

一元多项式由一系列单项式组成，可以使用一个动态数组来存储这些单项式。

```cstruct polynomial{Term* terms; // 单项式数组int num_terms; // 单项式数量};typedef struct polynomial Polynomial;```现在，我们可以开始实现一元多项式的基本运算了。

1. 创建一元多项式要创建一元多项式，我们需要输入每个单项式的系数和指数。

我们可以使用动态内存分配来创建一个适应输入的单项式数组。

```cPolynomial create_polynomial(){Polynomial poly;printf("请输入多项式的项数：");scanf("%d", &poly.num_terms);poly.terms = (Term*)malloc(poly.num_terms * sizeof(Term));for(int i = 0; i < poly.num_terms; i++){printf("请输入第%d个单项式的系数和指数：", i+1);scanf("%f %d", &poly.terms[i].coefficient, &poly.terms[i].exponent);}return poly;}```2. 求两个一元多项式的和两个一元多项式的和等于对应指数相同的单项式系数相加的结果。

教学单位学生学号数据结构课程设计报告书题目一元多项式四则运算学生姓名专业名称指导教师目录1 问题描述.................................................... -2 -2 功能描述.................................................... - 2 -2.1课题要求 (2)2.2软件格式规定 (2)3 设计........................................................ - 2 -3.1相关函数介绍说明 (2)3.2主程序的流程基函数调用说明 (3)4 程序设计.................................................... -5 -4.1多项式存储的实现 (5)4.2加减乘除算法 (5)4.2.1加法运算的实现................................................... - 5 - 4.2.2减法运算的实现................................................... - 6 - 4.2.3乘法运算的实现................................................... - 7 - 4.2.4除法运算的实现................................................... - 7 - 4.3函数调用关系图 (8)5 运行测试.................................................... - 9 -6 设计小结................................................... - 12 -参考文献..................................................... - 12 -谢辞....................................................... - 13 -附录：程序清单............................................... - 14 -1 问题描述1.1首先是确定结构化程序设计的流程图，利用已学过的数据结构来构造二个存储多项式的结构，接着把输入，加，减，乘，除运算分成四个主要的模块：实现多项式输入模块、实现加法的模块、实现减法的模块、实现乘法的模块、实现除法的模块，然后各个模块里面还要分成若干种情况来考虑并通过函数的嵌套调用来实现其功能。

一、设计题目一元多项式的加法、减法、乘法的实现。

二、主要内容设有一元多项式A m(x)和B n(x).A m(x)=A0+A1x1+A2x2+A3x3+… +A m x mB 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等数学软件对一元多项式的计算过程，步骤后。

由于这些软件比较大功能齐全，但是实用性不强。