数据结构课程设计报告一元多项式加减乘除

数学与计算机学院课程设计说明书课程名称:数据结构课程设计课程代码:8404181题目:一元多项式运算的实现年级/专业/班:2009-计科-3学生姓名:学号:开始时间:2011年06月13日完成时间:2011年06月21日课程设计成绩：学习态度及平时成绩〔30〕技术水平与实际能力〔20〕创新〔5〕说明书撰写质量〔45〕总分〔100〕指导教师签名：年月日目录TOC\o"1-2"\h\z1引言 11.1问题的提出 11.2国内外研究的现状 11.3任务与分析 12程序的主要功能 22.1一元多项式创立 22.2一元多项式的加法 22.3一元多项式的减法 22.4一元多项式的乘法 22.5一元多项式项的指数比拟 22.6一元多项式运算结果升降排序 22.7一元多项式的输出 32.8一元多项式的销毁 33程序运行平台 44总体设计 55程序类的说明 66模块分析 76.1创立模块 86.2一元多项式的加法 106.3一元多项式相减 126.4一元多项式相乘 156.5一元多项式输出结果按项的指数排序 176.6一元多项式运算系统实现 217系统测试 328结论 38摘要随着计算机的普及，对数学中一元多项式的研究也逐渐普及，计算机程序员通过对其结构的分析，针对其特殊的结构，利用不同的计算机设计语言编程利用计算机系统实现了对一元多项式的一系列操作。本课程设计中主要利用C、C++语言编写程序实现了稀疏一元多项式的简单运算系统，该系统具有一元多项式顺序和动态两种存储结构，实现了一元多项式的加法、减法、乘法运算等功能。关键词：计算机;一元多项式;C；C++;顺序存储；动态存储1引言1.1问题的提出随着计算机的不断开展，计算机的线性表的应用越来越广泛，如今线性表在计算器程序上的应用已达非常成熟的阶段。但作为计算机领域的初学者要如何利用数据结构的知识完成线性表在一元多项式运算中的简单运用？一元多项式的表示在计算机内可以用顺序来表示，借助元素在存储相对位置来表示数据元素之间的关系，顺序表中每两个相邻位置表示一元多项式的一个项的系数、指数。创立一个一元多项式顺序表，对一元多项式的运算中会出现的各种情况进行分析，实现一元多项式的相加、相减、相乘操作。一元多项式的表示在计算机内也可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创立一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减、相乘操作。1.2国内外研究的现状顺序存储和链式存储实现简单的计算运算是计算机实现的最简单最低的根本功能，顺序存储和链式存储是计算各种功能的根底，随着计算机的研究不断开展，现在国内外的研究都到达非常稳定和成熟的程度。1.3任务与分析本课题主要的目的是分别采用顺序和动态存储结构实现一元多项式的加法、减法和乘法。并将操作结果分别按升序和降序输出。2程序的主要功能2.1一元多项式创立建立一元多项式的顺序表和链式表，按程序提示输入每个项数据结束创立。借助元素在存储器中的相对位置来表示数据元素之间的关系，顺序表中第i个位置表示一元多项式的第i项的系数为第i个位置存放的内容，指数为i-1。创立一个一元多项式顺序表，对一元多项式的运算中会出现的各种情况进行分析，实现一元多项式的相加、相减、相乘操作。用链表来表示只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个term项结构和指向下一个节点的指针域，term又包括系数和指数两个域分别存放该项的系数、。创立一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减、相乘操作。2.2一元多项式的加法对于两个一元多项式中所有指数相同的项，对应系数相加，假设其和不为零，那么构成“和多项式”中的一项；对于两个一元多项式中所有指数不相同的项，那么分别复抄到和多项式中去。2.3一元多项式的减法对于两个一元多项式中所有指数相同的项，对应系数相减，假设其差不为零，那么构成“和多项式”中的一项；对于两个一元多项式中所有指数不相同的项，将其按减法规那么复抄到差多项式中去。2.4一元多项式的乘法将乘法运算分解为一系列的加法运算利用两个一元多项式相加的算法实现。2.5一元多项式项的指数比拟比拟相邻两项的指数的大小。按升序排列时，前面项的指数大于后面项的指数就交换其项的位置。按降序序排列时，后面项的指数大于前面项的指数就交换其项的位置。2.6一元多项式运算结果升降排序一元多项式运算结果选择调用降序或升序排序函数。2.7一元多项式的输出将选择的运算操作结果输出。2.8一元多项式的销毁销毁已建立的两个多项式，释放空间。3程序运行平台VC++6.0。编译，链接，执行。WindowsXP。4总体设计主主函数创立多项式多项式加法多项式减法多项式乘法多项式升降序多项式输出5程序类的说明〔1〕Ploy结构声明typedefstruct//顺序表结构声明{inta[N];//记录多项式intlen;//记录多项式的长度}Ploy;〔2〕term结构声明typedefstruct//项的表示{floatcoef;//系数intexpn;//指数}term;〔3〕LNode结构声明typedefstructLNode{termdata;//term多项式值structLNode*next;}LNode,*LinkList;//两个类型名typedefLinkListpolynomail;//用带头结点的有序链表表示多项式6模块分析整个流程图如下图：图16.1创立模块6.1.1、链式存储结构的一元多项式的创立程序源代码：polynomailcreatpolyn(polynomailP,intm){ //输入m项的系数和指数，建立表示一元多项式的有序链表P polynomailr,q,p,s,Q; inti;P=(LNode*)malloc(sizeof(LNode));r=P; for(i=0;i<m;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; } } returnP;} 6.1.2、顺序存储结构一元多项式的创立程序源代码：voidGetPloy(Ploy*A){ inti,coef,ex,maxe=0;charch;printf("请输入每个项的系数及对应的指数，指数为负数时标志输入结束！\n");for(i=0;i<N;i++) A->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"); } else printf("请继续输入！\n");; } else A->a[ex]=coef; scanf("%d%d",&coef,&ex); }A->len=maxe;return;}6.2一元多项式的加法6.2.1链式存储两多项式相加程序源代码：polynomailaddpolyn(polynomailpa,polynomailpb){ //完成多项式相加运算，即：Pa=Pa+Pb polynomails,newp,q,p,r; intj; 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; case0: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; case1:s->data.coef=q->data.coef;s->data.expn=q->data.expn;r->next=s; r=s;q=q->next;break; }//switch }//while6.2.2顺序存储的多项式相加程序源代码：voidADD(PloyA,PloyB,Ploy*M)/*多项式A与多项式B相加，得到多项式M*/{ intla=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;}6.3一元多项式相减6.3.1链式存储的多项式相减程序源代码：/*3、两多项式相减*/polynomailsubpolyn(polynomailpa,polynomailpb){ //完成多项式相减运算，即：Pa=Pa-Pb polynomails,newp,q,p,r,Q;intj;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;case0: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; case1:s->data.coef=-q->data.coef; s->data.expn=q->data.expn;r->next=s; r=s; q=q->next; }//switch }//while while(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);else arrange2(newp);returnnewp;}6.3.2顺序存储的多项式相减程序源代码：voidSUB(PloyA,PloyB,Ploy*M)/*多项式A与多项式B相减〔A-B〕，得到多项式M*/{intla=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;}6.4一元多项式相乘6.4.1链式存储的多项式相乘程序源代码：polynomailmulpolyn(polynomailpa,polynomailpb){ //完成多项式相乘运算，即：Pa=Pa*Pb polynomails,newp,q,p,r;inti=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);else arrange2(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); } } returnnewp;}6.4.2顺序存储多项式相乘程序源代码：voidMUL(PloyA,PloyB,Ploy*M)/*多项式A与多项式B相乘，得到多项式M*/{ inti,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;}6.5一元多项式输出结果按项的指数排序6.5.1链式由小到大排序图6.6.1链式升序流程图voidarrange1(polynomailpa){polynomailh=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指向参与比拟的最后一个，不断向前移动}}6.5.2链式由大到小排序图6.6.2链式降序流程图程序源代码：voidarrange2(polynomailpa){polynomailh=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指向参与比拟的最后一个，不断向前移动6.5.3顺序由大到小排序程序源代码：voidPrintPloy1(PloyA)//降序输出顺序一元多项式{ inti;printf("%dx^%d",A.a[A.len],A.len);for(i=A.len-1;i>=1;i--){ if(A.a[i]==0); elseif(A.a[i]==1)printf("+x^%d",i); elseif(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); elseif(A.a[0]>0) printf("+%d",A.a[0]);//打印x的0次项 else printf("-%d",-A.a[0]); printf("\n");return;}6.5.4顺序由小到大排序程序源代码：voidPrintPloy2(PloyA)//升序输出顺序一元多项式{ inti=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); elseif(A.a[i]==-1) printf("-x^%d",i);else printf("%dx^%d",A.a[i],i); } for(++i;i<=A.len;i++){ if(A.a[i]==0);elseif(A.a[i]==1) printf("+x^%d",i);elseif(A.a[i]==-1) printf("-x^%d",i);elseif(A.a[i]>1)printf("+%dx^%d",A.a[i],i);elseif(A.a[i]<-1)printf("-%dx^%d",-A.a[i],i); }}6.6一元多项式运算系统实现6.6.1主菜单系统程序源代码：voidMenu(){ printf("\n"); printf("************一元多项式的根本运算系统************\n");printf("1、一元多项式顺序存储的子系统请按1\n");printf("2、一元多项式链式存储的根本运算请按2\n");printf("3、退出系统请按3\n");printf("************************************************\n"); printf("\n");printf("请输入你想进行的操作号：\n"); intn; scanf("%d",&n); while(n!=1&&n!=2&&n!=3) { printf("对不起，你的输入不正确，请重新输入！\n"); scanf("%d",&n); } switch(n) { case1: if(n==1) shunxu(); break; case2: if(n==2) link(); break; case3: if(n==3) printf("已成功退出该系统，谢谢你的使用！\n"); exit(-2); }}6.6.2顺序子系统程序源代码：voidMenushunxu(){ 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;}voidshunxu()//一元多项式顺序存储的实现{ PloyA,B,M;intn,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) { case1: if(m==1) { printf("A降="); PrintPloy1(A); printf("\n"); printf("B降="); PrintPloy1(B); } break; case2: 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) { case1: 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) { case1: if(m==1) { printf("A降="); PrintPloy1(A); printf("\n"); printf("B降="); PrintPloy1(B); } break; case2: if(m==2) { printf("A升="); PrintPloy1(A); printf("\n"); printf("B升="); PrintPloy1(B); } break; } break; case2: if(n==2) ADD(A,B,&M);printf("降幂输出请按1，升幂输出请按2！\n");cin>>m; while(m<1&&m>2) { printf("你输入的输出排序操作号不合法，请重新输入\n"); cin>>m; } switch(m) { case1: if(m==1) { printf("ADD降="); PrintPloy1(M); printf("\n"); } break; case2: if(m==2) { printf("ADD升="); PrintPloy2(M); printf("\n"); } break; } break; case3: if(n==3) SUB(A,B,&M); printf("降幂输出请按1，升幂输出请2！\n"); cin>>m; while(m<1&&m>2) { printf("你输入的输出排序操作号不合法，请重新输入\n"); cin>>m; } switch(m) { case1: if(m==1) { printf("SUB降="); PrintPloy1(M); printf("\n"); } break; case2: if(m==2) { printf("SUB升="); PrintPloy2(M); printf("\n"); } break; } break; case4: if(n==4) MUL(A,B,&M); printf("降幂输出请按1，升幂输出请2！\n"); cin>>m; while(m<1&&m>3) { printf("你输入输出排序操作号不合法，请重新输入\n"); cin>>m; } switch(m) { case1: if(m==1) { printf("MUL降="); PrintPloy1(M); printf("\n"); } break; case2: if(m==2) { printf("MUL升="); PrintPloy2(M); printf("\n"); } break; } break; case5: if(n==5) printf("返回主菜单\n"); Menu(); break; case6: if(n==6) printf("已成功退出该系统，谢谢你的使用！\n"); exit(-2); break;}}}6.6.3链式子系统程序源代码：voidMenulink(){ 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");}voidlink()//一元多项式链式存储的实现{ polynomailpa=NULL,pb=NULL; polynomailp,q; polynomailaddp=NULL,subp=NULL,mulp=NULL; intn,m; printf("已进入链式存储一元多项式运算的子系统\n"); Menulink(); while(1) { printf("请选择你想进行的链式存储运算操作：\n");scanf("%d",&n);switch(n) { case1: 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; case2: if(pa==NULL) { printf("请先创立两个一元多项式!\n"); break; } addp=addpolyn(pa,pb); printpolyn(addp); break; case3: if(pa==NULL) { printf("请先创立两个一元多项式!\n"); break; } subp=subpolyn(pa,pb); printpolyn(subp); break; case4: if(pa==NULL) { printf("请先创立两个一元多项式!\n"); break; } mulp=mulpolyn(pa,pb); printpolyn(mulp); break; case5: if(pa==NULL) { printf("请先创立两个一元多项式!\n"); break; } delpolyn(pa,pb); pa=pb=NULL; printf("两个一元多项式的销毁成功!\n"); break; case6: 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; case7: if(addp!=NULL) { p=addp; while(p!=NULL) { q=p; p=p->next;