数据结构 一元多项式四则运算 源代码

一元多项式相加数据结构c++语言版以下是一个使用C++ 语言实现的一元多项式相加的示例代码：c复制代码#include<iostream>#include<vector>using namespace std;// 定义多项式结构体struct Polynomial {vector<int> coefficients; // 系数数组int degree; // 最高次数};// 初始化多项式void initPolynomial(Polynomial &p, int degree) {p.degree = degree;p.coefficients.resize(degree + 1);}// 多项式相加Polynomial addPolynomial(const Polynomial &p1, const Polynomial &p2) {Polynomial result;result.degree = max(p1.degree, p2.degree); // 最高次数取两个多项式的最大值result.coefficients.resize(result.degree + 1);for (int i = 0; i <= result.degree; i++) {result.coefficients[i] = p1.coefficients[i] + p2.coefficients[i]; // 系数相加}return result;}// 输出多项式void printPolynomial(const Polynomial &p) {for (int i = p.degree; i >= 0; i--) { // 从最高次到最低次输出系数和对应的次数if (p.coefficients[i] != 0) { // 如果系数不为0，则输出该次数的系数和次数cout << p.coefficients[i] << "x^" << i << " ";}}cout << endl;}int main() {Polynomial p1, p2, p3; // 定义三个多项式对象initPolynomial(p1, 3); // 初始化 p1 为最高次数为3的多项式，系数全为0initPolynomial(p2, 2); // 初始化 p2 为最高次数为2的多项式，系数全为0 p1.coefficients[3] = 2; // 设置 p1 的最高次项系数为2p1.coefficients[2] = -3; // 设置 p1 的次高次项系数为-3p2.coefficients[2] = 4; // 设置 p2 的次高次项系数为4p2.coefficients[1] = -5; // 设置 p2 的最低次项系数为-5 initPolynomial(p3, 5); // 初始化 p3 为最高次数为5的多项式，系数全为0 p3 = addPolynomial(p1, p2); // 将 p1 和 p2 相加，结果存储在 p3 中printPolynomial(p3); // 输出相加后的结果多项式return0;}。

数据结构实验报告题目一元多项式四则运算学生姓名王某某专业班级测控120X班学号U2012XXXXX1 问题描述利用已学过的数据结构来构造二个存储多项式的结构，接着把输入，加，减，乘，除运算分成四个主要的模块：实现多项式输入模块、实现加法的模块、实现减法的模块、实现乘法的模块、实现除法的模块，然后各个模块里面还要分成若干种情况来考虑并通过函数的嵌套调用来实现其功能。

最后，编写main主函数以实现对多项式输入输出以及加、减、乘、除。

2 相关函数介绍说明（1）程序定义的数据结构类型为线性表的链式存储结构类型变量：typedef struct linknode（2）程序定义的其它函数：linnode *Sort(linnode *S);//多项式按指数从大到小排序linnode *CreateList();//创建多项式Void ShowList(linnode *head) ;//显示多项式linnode *Copy(linnode *copy);//拷贝多项式（因为做减法运算时会破坏原来输入的多项式）linnode *SearchList(linnode *head,int x);//查找函数Linnode *Mulr(linnode *s,linnode *p)//用一个节点去乘与一个多项式（辅助除法运算）Linnode *AddSame(linnode *head);//和并多项式的同类项linnode *Add(linnode *head1,linnode *head2);// 加法linnode *Mul(linnode *head1,linnode *head2);// 乘法linnode *Sub(linnode *head1,linnode *head2);// 减法Void Div(linnode *head1,linnode *head2)//除法int main( )//主函数3 程序设计3.1 多项式存储的实现多项式是由若干项构成的一个数学式子，其每一项包含系数与指数。

⼀元多项式加法、减法、乘法实现源代码////链接程序：#include#include#include//using namespace std;#define N 1000//#define INF 65535void link();void shunxu();void Menu();typedef struct{int a[N];//记录多项式int len;//记录多项式的长度}Ploy;typedef struct //项的表⽰{ float coef; //系数int expn; //指数}term;typedef struct LNode{ term data; //term多项式值struct LNode *next;}LNode,*LinkList; //两个类型名typedef LinkList polynomail; //⽤带头结点的有序链表表⽰多项式/*⽐较指数*/int cmp(term a,term b){ if(a.expn>b.expn) return 1;if(a.expn==b.expn) return 0;if(a.expnelse exit(-2);}/*⼜⼩到⼤排列*/void arrange1(polynomail pa){ polynomail h=pa,p,q,r;if(pa==NULL) exit(-2);for(p=pa;p->next!=NULL;p=p->next); r=p;for(h=pa;h->next!=r;)//⼤的沉底{ for(p=h;p->next!=r&&p!=r;p=p->next)if(cmp(p->next->data,p->next->next->data)==1){ q=p->next->next;p->next->next=q->next;q->next=p->next;p->next=q;}r=p;//r指向参与⽐较的最后⼀个，不断向前移动} }/*由⼤到⼩排序*/void arrange2(polynomail pa){ polynomail h=pa,p,q,r;if(pa==NULL) exit(-2);for(p=pa;p->next!=NULL;p=p->next); r=p;for(h=pa;h->next!=r;)//⼩的沉底{ for(p=h;p->next!=r&&p!=r;p=p->next)if(cmp(p->next->next->data,p->next->data)==1){ q=p->next->next;p->next->next=q->next;q->next=p->next;p->next=q;}r=p;//r指向参与⽐较的最后⼀个，不断向前移动} }/*打印多项式,求项数*/int printpolyn(polynomail P){ int i;polynomail q;if(P==NULL) printf("⽆项！\n");else if(P->next==NULL) printf("Y=0\n");else{ printf("该多项式为Y=");q=P->next;i=1;if(q->data.coef!=0&&q->data.expn!=0){ printf("%.2fX^%d",q->data.coef,q->data.expn); i++; }if(q->data.expn==0&&q->data.coef!=0)printf("%.2f",q->data.coef);//打印第⼀项q=q->next;if(q==NULL){printf("\n");return 1;}while(1)//while中，打印剩下项中系数⾮零的项，{ if(q->data.coef!=0&&q->data.expn!=0){ if(q->data.coef>0) printf("+");printf("%.2fX^%d",q->data.coef,q->data.expn); i++;}if(q->data.expn==0&&q->data.coef!=0){ if(q->data.coef>0) printf("+");printf("%f",q->data.coef);}q=q->next;if(q==NULL){ printf("\n"); break; }}}return 1;}/*1、创建并初始化多项式链表*/polynomail creatpolyn(polynomail P,int m){//输⼊m项的系数和指数，建⽴表⽰⼀元多项式的有序链表P polynomail r,q,p,s,Q;int i;P=(LNode*)malloc(sizeof(LNode));r=P;for(i=0;i{s=(LNode*)malloc(sizeof(LNode));printf("请输⼊第%d项的系数和指数：",i+1);scanf("%f%d",&s->data.coef,&s->data.expn);r->next=s;r=s;}r->next=NULL;if(P->next->next!=NULL){for(q=P->next;q!=NULL/*&&q->next!=NULL*/;q=q->next)//合并同类项for(p=q->next,r=q;p!=NULL;)if(q->data.expn==p->data.expn){q->data.coef=q->data.coef+p->data.coef;r->next=p->next;Q=p;p=p->next;free(Q);}else{r=r->next;p=p->next;}}return P;}/*2、两多项式相加*/polynomail addpolyn(polynomail pa,polynomail pb) {//完成多项式相加运算，即：Pa=Pa+Pb polynomail s,newp,q,p,r;int j;p=pa->next;q=pb->next;newp=(LNode*)malloc(sizeof(LNode));r=newp;while(p&&q)//p&&q都不为空{s=(LNode*)malloc(sizeof(LNode));switch(cmp(p->data,q->data)){case -1: s->data.coef=p->data.coef;s->data.expn=p->data.expn;r->next=s;r=s;p=p->next;break;case 0: s->data.coef=p->data.coef+q->data.coef;if(s->data.coef!=0.0){s->data.expn=p->data.expn;r->next=s;r=s;}p=p->next;q=q->next;break;case 1: s->data.coef=q->data.coef;s->data.expn=q->data.expn;r->next=s;r=s;q=q->next;break;}//switch}//while p||q有⼀个跑完就跳出该循环while(p)//p没跑完{s=(LNode*)malloc(sizeof(LNode));s->data.coef=p->data.coef;s->data.expn=p->data.expn;r->next=s;r=s;p=p->next;}//p跑完跳出循环while(q)//q没跑完{s=(LNode*)malloc(sizeof(LNode));s->data.coef=q->data.coef;s->data.expn=q->data.expn;r=s;q=q->next;}//q跑完跳出循环//p&&q都跑完r->next=NULL;for(q=newp->next;q->next!=NULL;q=q->next)//合并同类项{for(p=q;p!=NULL&&p->next!=NULL;p=p->next)if(q->data.expn==p->next->data.expn){q->data.coef=q->data.coef+p->next->data.coef;r=p->next;p->next=p->next->next;free(r);}}printf("升序 1 , 降序 2\n");printf("选择排序⽅式:");scanf("%d",&j);if(j==1)arrange1(newp);elsearrange2(newp);return newp;}/*3、两多项式相减*/polynomail subpolyn(polynomail pa,polynomail pb){//完成多项式相减运算，即：Pa=Pa-Pbpolynomail s,newp,q,p,r,Q; int j;p=pa->next;q=pb->next;newp=(LNode*)malloc(sizeof(LNode));r=newp;while(p&&q){s=(LNode*)malloc(sizeof(LNode));switch(cmp(p->data,q->data)){case -1: s->data.coef=p->data.coef;s->data.expn=p->data.expn;r->next=s;r=s;p=p->next;break;case 0: s->data.coef=p->data.coef-q->data.coef;if(s->data.coef!=0.0){s->data.expn=p->data.expn;r->next=s;r=s;}p=p->next;q=q->next;break;case 1: s->data.coef=-q->data.coef;s->data.expn=q->data.expn;r->next=s;r=s;}//switch}//whilewhile(p){s=(LNode*)malloc(sizeof(LNode));s->data.coef=p->data.coef;s->data.expn=p->data.expn;r->next=s;r=s;p=p->next;}while(q){s=(LNode*)malloc(sizeof(LNode));s->data.coef=-q->data.coef;s->data.expn=q->data.expn;r->next=s;r=s;q=q->next;}r->next=NULL;if(newp->next!=NULL&&newp->next->next!=NULL)//合并同类项{for(q=newp->next;q!=NULL;q=q->next)for(p=q->next,r=q;p!=NULL;)if(q->data.expn==p->data.expn){q->data.coef=q->data.coef+p->data.coef;r->next=p->next;Q=p;p=p->next;free(Q);}else{r=r->next;p=p->next;}}printf("升序 1 , 降序 2\n");printf("选择:");scanf("%d",&j);if(j==1)arrange1(newp);elsearrange2(newp);return newp;}/*4两多项式相乘*/polynomail mulpolyn(polynomail pa,polynomail pb){//完成多项式相乘运算，即：Pa=Pa*Pbpolynomail s,newp,q,p,r;int i=20,j;newp=(LNode*)malloc(sizeof(LNode));r=newp;for(p=pa->next;p!=NULL;p=p->next)for(q=pb->next;q!=NULL;q=q->next){s=(LNode*)malloc(sizeof(LNode));s->data.coef=p->data.coef*q->data.coef;s->data.expn=p->data.expn+q->data.expn;r->next=s;r=s;}r->next=NULL;printf("升序 1 , 降序 2\n");printf("选择:");scanf("%d",&j);if(j==1)arrange1(newp);elsearrange2(newp);for(;i!=0;i--){for(q=newp->next;q->next!=NULL;q=q->next)//合并同类项for(p=q;p!=NULL&&p->next!=NULL;p=p->next)if(q->data.expn==p->next->data.expn){q->data.coef=q->data.coef+p->next->data.coef;r=p->next;p->next=p->next->next;free(r);}}return newp;}/*5、销毁已建⽴的两个多项式*/void delpolyn(polynomail pa,polynomail pb){polynomail p,q;p=pa;while(p!=NULL){q=p;p=p->next;free(q);}p=pb;while(p!=NULL){q=p;p=p->next;free(q);}printf("两个多项式已经销毁\n");}void Menulink(){printf("\n");printf(" ********⼀元多项式链式存储的基本运算********\n"); printf(" 1、创建两个⼀元多项式请按1\n");printf(" 2、两多项式相加得⼀新多项式请按2\n");printf(" 3、两多项式相减得⼀新多项式请按3\n");printf(" 4、两多项式相乘得⼀新多项式请按4\n");printf(" 5、销毁已建⽴的两个多项式请按5\n");printf(" 6、退出该⼦系统返回主菜单请按6\n");printf(" 7、退出该系统请按7\n");printf(" ********************************************\n");printf("\n");}void link() //⼀元多项式链式存储的实现{polynomail pa=NULL,pb=NULL;polynomail p,q;polynomail addp=NULL,subp=NULL,mulp=NULL; int n,m;printf("已进⼊链式存储⼀元多项式运算的⼦系统\n"); Menulink();while(1){printf("请选择你想进⾏的链式存储运算操作：\n"); scanf("%d",&n);switch(n){case 1:if(pa!=NULL){printf("已建⽴两个⼀元多项式，请选择其他操作!"); break;}printf("请输⼊第⼀个多项式：\n");printf("要输⼊⼏项：");scanf("%d",&m);while(m==0){printf("m不能为0，请重新输⼊m：");scanf("%d",&m);}pa=creatpolyn(pa,m);printpolyn(pa);printf("请输⼊第⼆个多项式：\n");printf("要输⼊⼏项：");scanf("%d",&m);while(m==0){printf("m不能为0，请重新输⼊m：");scanf("%d",&m);}pb=creatpolyn(pb,m);printpolyn(pb);break;case 2:if(pa==NULL){printf("请先创建两个⼀元多项式!\n");break;}addp=addpolyn(pa,pb);printpolyn(addp);break;case 3:if(pa==NULL){printf("请先创建两个⼀元多项式!\n");break;}subp=subpolyn(pa,pb);printpolyn(subp);break;case 4:if(pa==NULL){printf("请先创建两个⼀元多项式!\n"); break;}mulp=mulpolyn(pa,pb);printpolyn(mulp);break;case 5:if(pa==NULL){printf("请先创建两个⼀元多项式!\n"); break;}delpolyn(pa,pb);pa=pb=NULL;printf("两个⼀元多项式的销毁成功!\n"); break;case 6:if(addp!=NULL){p=addp;while(p!=NULL){q=p;p=p->next;free(q);}}if(subp!=NULL){p=subp;while(p!=NULL){q=p;p=p->next;free(q);}}printf("返回主菜单\n");Menu();break;case 7:if(addp!=NULL){p=addp;while(p!=NULL){q=p;p=p->next;free(q);}}if(subp!=NULL){p=subp;while(p!=NULL){q=p;p=p->next;free(q);}}printf("已成功退出该系统，谢谢你的使⽤！\n");exit(-2);break;}//switch}//while}//2、顺序程序：void ADD(Ploy A,Ploy B,Ploy *M)/*多项式A与多项式B相加，得到多项式M*/{int la=A.len,lb=B.len,i;M->len=la>lb?la:lb;for(i=0;i<=la&&i<=lb;i++){M->a[i]=A.a[i]+B.a[i];}while(i<=la){M->a[i]=A.a[i];i++;}while(i<=lb){M->a[i]=B.a[i];i++;}return;}void SUB(Ploy A,Ploy B,Ploy *M)/*多项式A与多项式B相减（A-B），得到多项式M*/{int la=A.len,lb=B.len,i;M->len=la>lb?la:lb;for(i=0;i<=la&&i<=lb;i++){M->a[i]=A.a[i]-B.a[i];}while(i<=la) {M->a[i]=A.a[i];i++;}while(i<=lb) {M->a[i]=0-B.a[i];i++;}return ;}void MUL(Ploy A,Ploy B,Ploy *M)/*多项式A与多项式B相乘，得到多项式M*/{int i,j;for(i=0;i<=A.len+B.len+1;i++) M->a[i]=0;for(i=0;i<=A.len;i++)for(j=0;j<=B.len;j++){M->a[i+j]+=A.a[i]*B.a[j];}M->len=A.len+B.len;return ;}void GetPloy(Ploy *A){int i,coef,ex,maxe=0;//ex指指数，maxe指最⼤指数char ch;printf("请输⼊每个项的系数及对应的指数，指数为负数时标志输⼊结束！\n");for(i=0;iA->a[i]=0;scanf("%d%d",&coef,&ex);while(ex>=0){if(ex>maxe)maxe=ex;if(A->a[ex]!=0){printf("你输⼊的项已经存在，是否更新原数据？（Y/N）"); cin>>ch;if(ch=='Y'||ch=='y'){A->a[ex]=coef;printf("更新成功，请继续输⼊！\n");}elseprintf("请继续输⼊！\n");;}elseA->a[ex]=coef;scanf("%d%d",&coef,&ex);}A->len=maxe;return ;}void PrintPloy1(Ploy A)//降序输出顺序⼀元多项式{int i;printf(" %dx^%d ",A.a[A.len],A.len);for(i=A.len-1;i>=1;i--){if(A.a[i]==0) ;else if(A.a[i]==1) printf(" + x^%d ",i);else if(A.a[i]==-1) printf(" - x^%d ",i);else{if(A.a[i]>0)printf("+ %dx^%d ",A.a[i],i);elseprintf("- %dx^%d ",-A.a[i],i);}}if(A.a[0]==0) ;else if(A.a[0]>0)printf(" + %d",A.a[0]);//打印x的0次项elseprintf(" - %d",-A.a[0]);printf("\n");return ;}void PrintPloy2(Ploy A)//升序输出顺序⼀元多项式{int i=0;while(A.a[i]==0)++i;if(i==0)printf("%d",A.a[i]);else{if(A.a[i]==1)printf("x^%d",i);else if(A.a[i]==-1)printf("-x^%d",i);elseprintf("%dx^%d",A.a[i],i);}for(++i;i<=A.len;i++){if(A.a[i]==0) ;else if(A.a[i]==1)printf(" + x^%d",i);else if(A.a[i]==-1)printf(" - x^%d",i);else if(A.a[i]>1)printf(" + %dx^%d",A.a[i],i);else if(A.a[i]<-1)printf(" - %dx^%d",-A.a[i],i);}}void Menushunxu(){printf("\n");printf(" ********⼀元多项式顺序存储的基本运算********\n");printf(" 1、更新两个多项式⼀元多项式请按1\n");printf(" 2、两多项式相加得⼀新多项式请按2\n");printf("3、两多项式相减得⼀新多项式请按3\n");printf(" 4、两多项式相乘得⼀新多项式请按4\n");printf(" 5、退出该⼦系统，返回主菜单请按5\n");printf(" 6、退出该系统请按6\n");printf(" ********************************************\n");printf("\n");return ;}void shunxu() //⼀元多项式顺序存储的实现{Ploy A,B,M;int n,m;printf("进⼊顺序存储⼀元多项式运算⼦系统\n");printf("请输⼊多项式A：\n");GetPloy(&A);printf("请输⼊多项式B：\n");GetPloy(&B);printf("输出两个⼀元多项式A、B，降幂输出请按1，升幂输出请按2！\n"); cin>>m;while(m<1&&m>m){printf("你输⼊的输出新创⼀元多项式的操作号不合法，请重新输⼊\n"); cin>>m;}switch(m){case 1:if(m==1){printf("A降=");PrintPloy1(A);printf("\n");printf("B降=");PrintPloy1(B);break;case 2:if(m==2){printf("A升=");PrintPloy1(A);printf("\n");printf("B升=");PrintPloy1(B);}break;}Menushunxu();while(1){printf("请选择你想进⾏的顺序存储运算操作：\n");cin>>n;while(n<1&&n>6){printf("输⼊的顺序操作号不对，请重新输⼊\n");cin>>n;}switch(n){case 1:if(n==1)printf("更新两个多项式：\n");printf("请输⼊多项式A：\n");GetPloy(&A);printf("请输⼊多项式B：\n");GetPloy(&B);printf("输出两个更新的⼀元多项式A、B，降幂输出请按1，升幂输出请按2！\n"); cin>>m;while(m<1&&m>2){printf("你输⼊的输出排序操作号不合法，请重新输⼊\n");cin>>m;}switch(m){case 1:if(m==1){printf("A降=");PrintPloy1(A);printf("\n");printf("B降=");PrintPloy1(B);}break;case 2:if(m==2){printf("A升=");PrintPloy1(A);printf("\n");printf("B升=");PrintPloy1(B);}break;break;case 2:if(n==2)ADD(A,B,&M);printf("降幂输出请按1，升幂输出请按2！\n");cin>>m;while(m<1&&m>2){printf("你输⼊的输出排序操作号不合法，请重新输⼊\n"); cin>>m;}switch(m){case 1:if(m==1){printf("ADD降=");PrintPloy1(M);printf("\n");}break;case 2:if(m==2){printf("ADD升=");PrintPloy2(M);printf("\n");}break;}break;case 3:if(n==3)SUB(A,B,&M);printf("降幂输出请按1，升幂输出请2！\n");cin>>m;while(m<1&&m>2){printf("你输⼊的输出排序操作号不合法，请重新输⼊\n"); cin>>m;}switch(m){case 1:if(m==1){printf("SUB降=");PrintPloy1(M);printf("\n");}break;case 2:if(m==2){printf("SUB升=");PrintPloy2(M);printf("\n");}break;}break;case 4:if(n==4)MUL(A,B,&M);printf("降幂输出请按1，升幂输出请2！\n");cin>>m;while(m<1&&m>3){printf("你输⼊输出排序操作号不合法，请重新输⼊\n"); cin>>m;}switch(m){case 1:if(m==1){printf("MUL降=");PrintPloy1(M);printf("\n");}break;case 2:if(m==2){printf("MUL升=");PrintPloy2(M);printf("\n");}break;}break;case 5:if(n==5)printf("返回主菜单\n");Menu();break;case 6:if(n==6)printf("已成功退出该系统，谢谢你的使⽤！\n");exit(-2);break;}}}void Menu(){printf("\n");printf(" ************⼀元多项式的基本运算系统************\n"); printf(" 1、⼀元多项式顺序存储的⼦系统请按1\n");printf(" 2、⼀元多项式链式存储的基本运算请按2\n"); printf(" 3、退出系统请按3\n");printf(" ************************************************\n"); printf("\n");printf("请输⼊你想进⾏的操作号：\n");int n;scanf("%d",&n);while(n!=1 && n!=2 && n!=3){printf("对不起，你的输⼊不正确，请重新输⼊！\n"); scanf("%d",&n);}switch(n){case 1:if(n==1)shunxu();break;case 2:if(n==2)link();break;case 3:if(n==3)printf("已成功退出该系统，谢谢你的使⽤！\n"); exit(-2);}}void main(){Menu();}。

数据结构课程设计报告题目设计一个一元多项式计算器班级20090201学生姓名学号2009031327专业电类强化班指导教师提交日期 2011/1/4南京航空航天大学金城学院目录一、题目要求及内容二、函数模块及功能三、技术要点四、源代码五、举例六、调试心得一．题目要求及内容1.题目：设计一个一元多项式计算器○1．用带头结点的单链表存储多项式Typedef struct lnode{Float coef;Int expn;Struct lnode *next;} lnode,*linklist;Typedef linklist polynominal;○2．输入时，构成的多项式链表按指数项大小递增有序排列○3．输出格式要求如：3x^2+6x^8+7x^12-9x^15○1．输入并且建立一元多项式○2．输出多项式○3．多项式相加a+b○4．多项式相减a-b○5．多项式相乘a*b二．函数模块及功能1 ．void Insert( linklist p,linklist h)；链表插入void Insert( linklist p,linklist h){if(p->coef==0) free(p);//系数为0的话释放结点else{linklist q1,q2;q1=h;q2=h->next;while(q2&&p->expn>q2->expn) {//查找插入位置q1=q2;q2=q2->next;}if(q2&&p->expn==q2->expn) {//将指数相同相合并q2->coef+=p->coef;free(p);if(!q2->coef) {//系数为0的话释放结点q1->next=q2->next;free(q2);}}else{//指数为新时将结点插入p->next=q2;q1->next=p;}}}2．linklist Createlinklist(linklist head)；创建链表linklist Createlinklist(linklist head) {//建立一个头指针为head的一元多项式linklist p;float a;int b;p=head=(linklist)malloc(sizeof(struct lnode));p->next=NULL;scanf("%f %d",&a,&b);while(a!=0 || b!=0){ //当输入为0 0时停止输入p=(linklist)malloc(sizeof(struct lnode));p->coef=a;p->expn=b;Insert(p,head); //调用Insert函数插入结点scanf("%f %d",&a,&b);}return head;}3．void Destroylinklist(linklist p)；销毁链表void Destroylinklist(linklist p){ //销毁多项式linklistlinklist q1,q2;q1=p->next;q2=q1->next;while(q2){free(q1);q1=q2;q2=q2->next;}}4．void Printlinklist(linklist P)；打印链表void Printlinklist(linklist P){linklist q=P->next;int flag=1;//项数计数器if(!q){ //若多项式为空，输出0putchar('0');printf("\n");return;}while(q){if(q->coef>0&&flag!=1) putchar('+'); //系数大于0且不是第一项if(q->coef!=1&&q->coef!=-1){//系数非1或-1的普通情况printf("%g",q->coef);if(q->expn==1) putchar('X');else if(q->expn) printf("X^%d",q->expn);}else{if(q->coef==1){if(!q->expn) putchar('1');else if(q->expn==1) putchar('X');else printf("X^%d",q->expn);}if(q->coef==-1){if(!q->expn) printf("-1");else if(q->expn==1) printf("-X");else printf("-X^%d",q->expn);}}q=q->next;flag++;}printf("\n");}5．int compare(linklist a,linklist b)；链表非空判断int compare(linklist a,linklist b){if(a&&b){if(!b||a->expn>b->expn) return -1;else if(!a||a->expn<b->expn) return 1;else return 0;}else if(!a&&b) return -1;//a多项式已空，但b多项式非空else return 1;//b多项式已空，但a多项式非空}6．linklist Addlinklist(linklist pa,linklist pb)；链表合并—多项式相加linklist Addlinklist(linklist pa,linklist pb){//求解并建立多项式a+b，返回其头指针linklist qa=pa->next;linklist qb=pb->next;linklist headc,hc,qc;hc=(linklist)malloc(sizeof(struct lnode));//建立头结点hc->next=NULL;headc=hc;while(qa||qb){qc=(linklist)malloc(sizeof(struct lnode));switch(compare(qa,qb)){case 1:{qc->coef=qa->coef;qc->expn=qa->expn;qa=qa->next;break;}case 0:{qc->coef=qa->coef+qb->coef;qc->expn=qa->expn;qa=qa->next;qb=qb->next;break;}case -1:{qc->coef=qb->coef;qc->expn=qb->expn;qb=qb->next;break;}}if(qc->coef!=0){qc->next=hc->next;hc->next=qc;hc=qc;}else free(qc);//当相加系数为0时，释放该结点}return headc;}7．linklist Subtractlinklist(linklist pa,linklist pb)；链表合并—多项式相减linklist Subtractlinklist(linklist pa,linklist pb){//求解并建立多项式a-b，返回其头指针linklist h=pb;linklist p=pb->next;linklist pd;while(p){ //将pb的系数取反p->coef*=-1;p=p->next;}pd=Addlinklist(pa,h);for(p=h->next;p;p=p->next) //恢复pb的系数p->coef*=-1;return pd;}8．linklist Multiplylinklist(linklist pa,linklist pb)；多项式相乘linklist Multiplylinklist(linklist pa,linklist pb){ //求解并建立多项式a*b，返回其头指针linklist hf,pf;linklist qa=pa->next;linklist qb=pb->next;hf=(linklist)malloc(sizeof(struct lnode));//建立头结点hf->next=NULL;for(;qa;qa=qa->next){for(qb=pb->next;qb;qb=qb->next){pf=(linklist)malloc(sizeof(struct lnode));pf->coef=qa->coef*qb->coef;pf->expn=qa->expn+qb->expn;Insert(pf,hf);//调用Insert函数以合并指数相同的项}}return hf;}9．int Valuelinklist(linklist head,int x)；多项式带值函数int Valuelinklist(linklist head,int x){//输入x值，计算并返回多项式的值linklist p;int i;int sum=0;int t;for(p=head->next;p;p=p->next){t=1;for(i=p->expn;i!=0;){if(i<0){t/=x;i++;}//指数小于0，进行除法else{t*=x;i--;}//指数大于0，进行乘法}sum+=int(p->coef)*t;}return sum;}10．void main（）；主函数void main(){int s,x;char flag;linklist pa=0,pb=0,pc;printf(" 欢迎使用多项式操作程序\n\n");//输出菜单printf(" *******************************************************\n"); printf(" * 一元多项式操作程序*\n"); printf(" * *\n"); printf(" * *\n"); printf(" * 1:输入多项式a 2:输入多项式b *\n"); printf(" * *\n"); printf(" * *\n"); printf(" * a:输出多项式a b:输出多项式b *\n");printf(" * *\n"); printf(" * *\n"); printf(" * c:代入x的值计算a d:代入x的值计算b *\n"); printf(" * *\n"); printf(" * *\n"); printf(" * +:输出a+b -:输出a-b *\n"); printf(" * *\n"); printf(" * *\n"); printf(" * *:输出a*b q:退出程序*\n"); printf(" * *\n"); printf(" *******************************************************\n");printf("\n 请选择操作：");while(s){scanf(" %c",&flag);//空格符号一定要注意switch(flag){case '1':{printf("请输入多项式a各项系数和指数（系数，指数）输入0 0为结束:");pa=Createlinklist(pa);//建立多项式aprintf(" \n");printf("请继续操作: ");break;}case '2':{p rintf("请输入多项式b各项系数和指数（系数，指数）输入0 0为结束: ");pb=Createlinklist(pb);//建立多项式bprintf(" \n");printf("请继续操作: ");break;}case'a':{printf("\n 多项式a=");Printlinklist(pa);break;}case'b':{printf("\n 多项式b=");Printlinklist(pb);break;}case'c':{printf("输入x的值：x=");scanf("%d",&x);printf("\n x=%d时，a=%d\n",x,Valuelinklist(pa,x));break;}case'd':{printf("输入x的值：x=");scanf("%d",&x);printf("\n x=%d时，b=%d\n",x,Valuelinklist(pb,x));break;}case'+':{pc=Addlinklist(pa,pb);printf("\n a+b=");Printlinklist(pc);break;}case'-':{pc=Subtractlinklist(pa,pb);printf("\n a-b=");Printlinklist(pc);break;}case'*':{pc=Multiplylinklist(pa,pb);printf("\n a*b=");Printlinklist(pc);break;}case'q':{printf("\n 感谢使用此程序！\n");Destroylinklist(pa);Destroylinklist(pb);s=0;break;}default:printf("\n 操作错误，请重新选择! \n");}}}三．技术要点这两个链表的交叉合并运算主要用到的是链表的基本操作，定义节点，将链表的创建（输入0 0为结束）、链表的交叉组合、链表内容升序排列、销毁链表、多项式的插入、多项式相加、多项式相减、多项式相乘、以及带值计算多项式等算法写成独立函数，通过主函数调用。

一元多项式的计算代码：#include<iostream.h>#include <stdlib.h>#include <math.h>typedef struct Polynomial{float coe; //系数float exp;//指数struct Polynomial *next;}*Polyn,Polynomial;Polyn ma,mb;void Insert(Polyn p,Polyn h){if(p->coe==0) delete p;else{Polyn q1,q2;q1=h;q2=h->next;while(q2&&p->exp<q2->exp){q1=q2;q2=q2->next;}if(q2&&p->exp==q2->exp){q2->coe+=p->coe;delete p;if(!q2->coe){q1->next=q2->next;delete q2;}}else{p->next=q2;q1->next=p;}}}Polyn CreatePolyn(Polyn head,int m) {int i;Polyn p;p=head=new Polynomial;head->next=NULL;for(i=0;i<m;i++){p=new Polynomial;;cout<<"请输入第"<<i+1<<"项的系数:";cin>>p->coe;cout<<" 指数:";cin>>p->exp;Insert(p,head);}return head;}void DestroyPolyn(Polyn p){Polyn t;while(p!=NULL){t=p;p=p->next;delete t;}}void PrintPolyn(Polyn Pm){Polyn qa=Pm->next;int flag=1;if(!qa){cout<<"0";cout<<endl;return;}while (qa){if(qa->coe>0&&flag!=1) cout<<"+";if(qa->coe!=1&&qa->coe!=-1){cout<<qa->coe;if(qa->exp==1) cout<<"X";else if(qa->exp) cout<<"X^"<<qa->exp;}else{if(qa->coe==1){if(!qa->exp) cout<<"1";else if(qa->exp==1) cout<<"X";else cout<<"X^"<<qa->exp;}if(qa->coe==-1){if(!qa->exp) cout<<"-1";else if(qa->exp==1) cout<<"-X";else cout<<"-X^"<<qa->exp;}}qa=qa->next;flag++;}cout<<endl;}int compare(Polyn a,Polyn b){if(a&&b){if(!b||a->exp>b->exp) return 1;else if(!a||a->exp<b->exp) return -1;else return 0;}else if(!a&&b) return -1;else return 1;}Polyn AddPolyn(Polyn pa,Polyn pb){Polyn qa=pa->next;Polyn qb=pb->next;Polyn headc,hc,qc;hc=new Polynomial;hc->next=NULL;headc=hc;while(qa||qb){qc=new Polynomial;switch(compare(qa,qb)){case 1:{qc->coe=qa->coe;qc->exp=qa->exp;qa=qa->next;break;}case 0:{qc->coe=qa->coe+qb->coe;qc->exp=qa->exp;qa=qa->next;qb=qb->next;break;}case -1:{qc->coe=qb->coe;qc->exp=qb->exp;qb=qb->next;break;}}if(qc->coe!=0){qc->next=hc->next;hc->next=qc;hc=qc;}else delete qc;}return headc;}Polyn SubtractPolyn(Polyn pa,Polyn pb){Polyn h=pb;Polyn p=pb->next;Polyn pd;while(p){p->coe*=-1;p=p->next;pd=AddPolyn(pa,h);for(p=h->next;p;p=p->next)p->coe*=-1;return pd;}Polyn MultiplyPolyn(Polyn pa,Polyn pb){Polyn hf,pf;//Polyn qa=pa->next; //新建一个结点作为pa的后继结点Polyn qb=pb->next; //新建一个结点作为pb的后继结点hf=new Polynomial;hf->next=NULL;while(qa)//使用while循环，使得多项式的每项得以运算{qb=pb->next;while(qb){pf=new Polynomial;pf->coe=qa->coe*qb->coe;pf->exp=qa->exp+qb->exp;Insert(pf,hf);//调用插入函数，将新的结点插入到新建链表中，并合并同类项qb=qb->next;}qa=qa->next;}return hf;//返回所得链表的头指针}void DevicePolyn(Polyn pa,Polyn pb){Polyn quotient,remainder,temp1,temp2;Polyn qa=pa->next;Polyn qb=pb->next;quotient=new Polynomial; //建立头结点,存储商quotient->next=NULL;remainder=new Polynomial; //建立头结点，存储余数remainder->next=NULL;temp1=new Polynomial;temp1->next=NULL;temp2=new Polynomial;temp2->next=NULL;temp1=AddPolyn(temp1,pa);while(qa!=NULL&&qa->exp>=qb->exp)temp2->next=new Polynomial;temp2->next->coe=(qa->coe)/(qb->coe);temp2->next->exp=(qa->exp)-(qb->exp);Insert(temp2->next,quotient);pa=SubtractPolyn(pa,MultiplyPolyn(pb,temp2));qa=pa->next;temp2->next=NULL;}remainder=SubtractPolyn(temp1,MultiplyPolyn(quotient,pb));pb=temp1;cout<<endl<<"shang"<<endl;//printf("\t商：");PrintPolyn(quotient);cout<<"yushu"<<endl;//printf("\t余数：");PrintPolyn(remainder);}float ValuePolyn(Polyn head,float x){Polyn p;p=head->next;float result=0;while(p!=NULL){result+=(p->coe)*(float)pow(x,p->exp);p=p->next;}return result;}void desktop(){system("cls");cout<<endl<<endl<<endl<<" 一元多项式的计算"<<endl;cout<<"**********************************************"<<endl;cout<<" ** 1.输出多项式a和 b **"<<endl;cout<<" ** 2.建立多项式a+b **"<<endl;cout<<" ** 3.建立多项式a-b **"<<endl;cout<<" ** 4.建立多项式a*b **"<<endl;cout<<" ** 5.建立多项式a/b**"<<endl;cout<<" ** 6.计算多项式a的值**"<<endl;cout<<" ** 7.退出**"<<endl;cout<<"**********************************************"<<endl<<endl;cout<<" 执行操作:";}void input(){int m,n;//Polyn pa,pb;cout<<"请输入多项式a的项数:";cin>>m;ma=CreatePolyn(ma,m);cout<<endl;cout<<"请输入多项式b的项数:";cin>>n;mb=CreatePolyn(mb,n);}void main(){//int m,n;float x,result;char key;//Polyn pa,pb;cout<<endl<<endl<<endl<<endl<<" 欢迎您的使用！"<<endl;cout<<" 系统正在初始化数据，请稍后..."<<endl;_sleep(3*1000);system("cls");while(key){desktop();cin>>key;switch (key){case'1':input();cout<<"多项式a：";PrintPolyn(ma);cout<<"多项式b：";PrintPolyn(mb);break;case'2':input();//pc=AddPolyn(pa,pb);cout<<"多项式a：";PrintPolyn(ma);cout<<"多项式b：";PrintPolyn(mb);cout<<"多项式a+b：";PrintPolyn(AddPolyn(ma,mb));//DestroyPolyn(pc);break;case'3':input();//pd=SubtractPolyn(pa,pb);cout<<"多项式a：";PrintPolyn(ma);cout<<"多项式b：";PrintPolyn(mb);cout<<"多项式a-b：";PrintPolyn(SubtractPolyn(ma,mb));//DestroyPolyn(pd);break;case'4':input();//pd=SubtractPolyn(pa,pb);cout<<"多项式a：";PrintPolyn(ma);cout<<"多项式b：";PrintPolyn(mb);cout<<"多项式a*b：";PrintPolyn(MultiplyPolyn(ma,mb));//DestroyPolyn(pd);break;case'5':input();//pd=SubtractPolyn(pa,pb);cout<<"多项式a：";PrintPolyn(ma);cout<<"多项式b：";PrintPolyn(mb);cout<<"多项式a/b：";DevicePolyn(ma,mb);//DestroyPolyn(pd);break;case'6':input();cout<<"多项式a：";PrintPolyn(ma);cout<<"输入x的值：x=";cin>>x;result=ValuePolyn(ma,x);cout<<"多项式a的值:"<<result<<endl;break;case'7':DestroyPolyn(ma);DestroyPolyn(mb);exit(0);break;default:cout<<"Error!!!"<<endl;}cout<<endl<<endl;system("pause");}}。

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^63.主要代码展示：//**** 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 {cout<<pt->coef<<"x^"<<pt->expn;}pt=pt->next;}while (pt){if(pt->expn==0){cout<<pt->coef;}else {if(pt->coef<0){cout<<pt->coef<<"x^"<<pt->expn;}else {cout<<"+"<<pt->coef<<"x^"<<pt->expn;}}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;cout<<"系数，指数：";cin>>c>>e;while (c){PNode *p=new PNode(c,e);Insert(p);cout<<"系数，指数：";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; cout<<"本函数的功能列表："<<endl;cout<<"1.多项式的加法:"<<endl;cout<<"2.多项式的减法:"<<endl;cout<<"3.多项式的乘法:"<<endl;cout<<"4.选择重建多项式:"<<endl;cout<<"5.结束运算\n"<<endl;cout<<"依次输入PA各项系数和指数(以输入系数0项结束)，建立多项式："<<endl;PA.CreatPoly();PA.Print();cout<<"依次输入PB各项系数和指数(以输入系数0项结束)，建立多项式："<<endl;PB.CreatPoly();PB.Print();cout<<"\n请输入功能序号进行多项式的运算：";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;cout<<"输入0修改多项式PA,其他数字保留多项式PA:";cin>>flag;if(!flag){PA.CreatPoly();PA.Print();}cout<<"输入0修改多项式PB,其他数字保留多项式PB:";cin>>flag;if(!flag){PB.CreatPoly();PB.Print();}break;}case 5:{cout<<"运算结束"<<endl;return 0;}}//switchcout<<"\n是否需要继续，请再次输入选择：";cin>>index;}//whilereturn 0;}4.项目结果展示三、实践体会在此次的C++开放项目试验中，我承担了用C++实现一元符号多项式的四则运算，将所学C++知识运用实战编程中去，并及时进行知识的查缺补漏，帮助我更好的掌握了C++这门语言。

一元多项式的四则运算学生姓名：指导老师：摘要本课程设计主要解决一元多项式的运算问题，通过链表的使用，实现对一元多项式的构建、录入、存储、打印、以及之间的运算。

在本课程设计中，程序设计语言为C++语言，程序运行平台为Windows/98/2000/XP，程序采用了链表存储方法以及结构化和模块化的设计方法，通过调试运行，可以进行多项式的加、减、乘运算，勉强实现了设计目标，并且经过适当完善后，将可应用到实际中解决某些问题。

关键词程序设计； C++ ；一元多项式；运算1 引言一般来说，我们只知道数学上的一元多项式的运算，这一般都是用笔来进行运算的，然而此课程设计将一元多项式的运算用电脑来进行，只需要将多项式输入，然后就可以出结果，速度快，省去了认为计算的环节，在现实中带来不少方便。

1.1 课题背景一元多项式的运算，虽然无法直接在除数学外的其他领域作出贡献，但是在数学上，它可以为人们解决一些自己动笔动手很难解决的问题，比如说那些很长很长的多项式，用笔算可能要算半天，但是用该程序，只需短短的几秒钟，所以它给人们带来了不少方便，同时相信它也能间接地为其他领域做出贡献。

1.2 课程设计目的个人觉得，该数据结构课程设计一方面可以让自己更加熟悉那些些常用的数据结构，掌握数据结构内在的逻辑关系，以及它们在计算机中的存储表示，和对它们实行的各种运算；另一方面，可以让自己对于整体和局部，以及结构化和模块化编程有一个更深层次的了解。

作为网络工程的学生，虽然之前有过一次Ｃ语言课程设计，但是深知自己编程能力尚为欠缺，所以这一次数据结构课程设计是对我的编程能力和组织能力的又一次考验。

1.3课程设计内容本课程设计是用链表实现一元多项式的存储及运算，其中包括多项式系数及指数的录入（即一元多项式的录入），以及储存、一元多项式的显示、一元多项式之间的加、减、乘法运算。

2 设计思路与方案2.1设计思路该系统使用Ｃ++语言进行开发和实现，程序中的各个功能分别由不同的的函数实现，然后在main函数中调用实现。