数据结构课程设计一元多项式的四则运算.doc

一元多项式的四则运算 学生姓名： 指导老师： 摘 要 本课程设计主要解决一元多项式的运算问题，通过链表的使用，实现对一元多项式的构建、录入、存储、打印、以及之间的运算。在本课程设计中，程序设计语言为C+语言，程序运行平台为Windows/98/2000/XP，程序采用了链表存储方法以及结构化和模块化的设计方法，通过调试运行，可以进行多项式的加、减、乘运算，勉强实现了设计目标，并且经过适当完善后，将可应用到实际中解决某些问题。关键词 程序设计； C+ ；一元多项式；运算 1 引 言一般来说，我们只知道数学上的一元多项式的运算，这一般都是用笔来进行运算的，然而此课程设计将一元多项式的运算用电脑来进行，只需要将多项式输入，然后就可以出结果，速度快，省去了认为计算的环节，在现实中带来不少方便。1.1 课题背景一元多项式的运算，虽然无法直接在除数学外的其他领域作出贡献，但是在数学上，它可以为人们解决一些自己动笔动手很难解决的问题，比如说那些很长很长的多项式，用笔算可能要算半天，但是用该程序，只需短短的几秒钟，所以它给人们带来了不少方便，同时相信它也能间接地为其他领域做出贡献。1.2 课程设计目的个人觉得，该数据结构课程设计一方面可以让自己更加熟悉那些些常用的数据结构，掌握数据结构内在的逻辑关系，以及它们在计算机中的存储表示，和对它们实行的各种运算；另一方面，可以让自己对于整体和局部，以及结构化和模块化编程有一个更深层次的了解。作为网络工程的学生，虽然之前有过一次语言课程设计，但是深知自己编程能力尚为欠缺，所以这一次数据结构课程设计是对我的编程能力和组织能力的又一次考验。 1.3课程设计内容本课程设计是用链表实现一元多项式的存储及运算，其中包括多项式系数及指数的录入（即一元多项式的录入），以及储存、一元多项式的显示、一元多项式之间的加、减、乘法运算。2 设计思路与方案2.1设计思路该系统使用+语言进行开发和实现，程序中的各个功能分别由不同的的函数实现，然后在main函数中调用实现。其设计思路基于结构化的程序设计和链表的存储等，应用了高级语言程序设计中的基本控制结构，如循环和选择等。2.2设计方案 先定义链表类型结点和一元多项式，然后申明个功能函数并分别编写这些功能函数的算法，然后定义一个菜单函数Menu()，最后在main()函数中分别调用这些函数，其中输入的数据则由链表进行储存。其系统结构图如图2-1所示：一元多项式相乘一元多项式输出一元多项式销毁退出一元多项式创建一元多项式相加一元多项式的四则运算一元多项式相减图2-1 一元多项式的四则运算3 详细实现3.1一元多项式创建操作流程图如下图所示：开始创建一个含n个链表类型结点的项分别输入各项的系数和指数判断是否系数不为0且指数大于0重新输入一元多项式创建成功 N Y图3-1 一元多项式的创建流程图3.2 一元多项式相加先判断多项式的系数与项数之间大小关系，流程图如下所示：开始运算时系数想加删除该项判断所输入的多项式系数是否为0判断输入的两个多项式指数是否相等输入的第1个多项式为B判断输入的多项式1,2指数是否e1>e2输入的第2个多项式为B进行运算YNY NY N N N图3-2一元多项式相加流程图3.3一元多项式相减相减即取第二个的相反数，然后进行加法运算，操作流程图如下图所示：开始调用多项式加法函数进行运算将多项式B进行复制取多项式B的相反数 图3-3一元多项式相减流程图3.4一元多项式相乘操作流程图如下图所示：开始给出运算的两个多项式按系数相乘指数相加进行运算将运算的结果相加并输出图3-4一元多项式相乘流程图3.5一元多项式输出先判断录入的两个多项式是否有空项，如果两个多项式都不是空的，那么顺序输出多项式A和多项式B，否则多项式创建不成功，提示重新输入。操作流程图如下图所示：输出多项式B输出多项式A开始判断所输入的两个多项式是否有空的多项式创建有误，重新输入 YN图3-5一元多项式输出流程图3.6一元多项式销毁先判断存储多项式的链表类型结点是否都不为空结点，若有空结点，则提示重新选择，否则，按顺序销毁多项式A,B。操作流程图如下图所示：销毁存储多项式B的结点销毁存储多项式A的结点开始判断存储多项式的链表类型结点是否都不为空多项式不存在，重新选择NY图3-6一元多项式销毁流程图3.7退出本过程较为简单，用exit(0)强制终止程序，返回状态码0表示正常结束。其操作流程图如下图所示：开始强制终止程序提示退出图3-6一元多项式退出流程图4 运行环境与结果4.1运行环境在本课程设计中，系统开发平台为WindowsXP,程序设计语言为 C+，程序的运行环境为Visual C+ 6.0。4.2运行结果（1） 在程序开始运行时，会出现一个编号1-7的菜单并提示选择，如下图所示：图4-1 最初运行界面（2）选择1，创建两个一元多项式，按顺序操作，录入两个一元多项式，结果如下图所示：图4-2 一元多项式创建（3） 选择2，将两个一元多项式相加，操作后结果如下图所示：图4-3一元多项式相加（4）选择3将两个一元多项式相减，操作后结果如下图所示：图4-4一元多项式相减（5） 选择4将两个一元多项式相乘，操作后结果如下图所示：图4-5 一元多项式相乘（6）选择5显示两个一元多项式，操作后结果如下图所示：图4-6一元多项式输出（7） 选择6，销毁所创建的两个多项式，操作后结果如下图所示：图4-7一元多项式销毁（8）选择7，退出程序，操作后结果如下图所示：图4-8退出程序5 结束语由于课程设计只有短短的两周时间，再加上原本自己编程能力并非突出，所以连这个简单的一元多项式的四则运算都令我大伤脑筋，尽管这样，还是没能完善，虽然我到处查资料，试图改写除法算法，也曾自己仿写一个除法的算法，不过都没能成功，所以说到四则运算，其实，我还只能算勉勉强强完成了三则运算，不过虽说这样，我也从中学到不少东西，我深刻认识到编程中结构化和模块化的重要性，当然也注意到很多细节问题是平时编小程序时经常疏忽的，如局部变量，外部变量等的定义与使用。虽然这次课程设计并非做的好，但我知道这也只不过是另一次尝试，一次考验。而且通过这次课程设计，我深知在做一件比较专业的事情的时候，没有其专业知识时绝对不可能把它做好的，也许并非这个一元多项式的四则运算难，而是自己的编程知识缺乏了点，所以一直在想我该先做什么，后来，我就去查阅了一些资料，就把目标锁定在要实现的功能上，从简单到容易，所以就构思了一下整体结构，然后开始找资料，写程序。但不管怎样，我受益还是颇多的，起码让我认识到自身编程知识还是有些欠缺的，所以我以后会踏踏实实的走好每一步。参考文献1苏运霖 数据结构与算法 中南工业大学出版社 ， 20022 Shaffer 数据结构与算法分析(C+版) 电子工业出版社 ， 19993严蔚敏，吴伟民数据结构(C语言版)清华大学出版社，20054清华大学数据结构(C语言)讲义.道客巴巴，5数据结构课程设计一元多项式的运算百度知道，附录：源程序代码/ 程序功能：一元多项式的四则运算/ 程序作者：阳超/ 最后修改日期：2011-03-02#include<iostream>/标准输入输出流#include<conio.h>/使程序中可用键盘输入函数#include<stdlib.h>/使程序中可用系统标准输出函数using namespace std;/命名空间std内定义的所有标识符均有效struct Nodefloat coef;/结点类型，系数int exp;/指数;typedef Node polynomial;struct LNodepolynomial data;/链表类型LNode *next;typedef LNode* Link;/*申明各功能函数*/ void CreateLink(Link &L,int n);void PrintList(Link L);void PolyAdd(Link &pc,Link pa,Link pb);void PolySubstract(Link &pc,Link pa,Link pb);void CopyLink(Link &pc,Link pa);void PolyMultiply(Link &pc,Link pa,Link pb);int JudgeIfExpSame(Link pa,Link e);void DestroyLink(Link &L);int CompareIfNum(int i);/*销毁链表类型结点*/void DestroyLink(Link &L)/Link p;p=L->next;while(p) L->next=p->next; delete p; p=L->next;delete L;L=NULL;/*创建含有n个链表类型结点的项，即创建一个n项多项式*/void CreateLink(Link &L,int n)if(L!=NULL) DestroyLink(L);Link p,newp;L=new LNode;L->next=NULL;(L->data).exp=-1;/创建头结点p=L;for(int i=1;i<=n;i+) newp=new LNode; cout<<"请输入第"<<i<<"项的系数和指数:"<<endl; cout<<"系数:" cin>>(newp->data).coef; cout<<"指数:" cin>>(newp->data).exp; if(newp->data.exp<0) cout<<"您输入有误，指数不允许为负值!"<<endl; delete newp; i-; continue; newp->next=NULL; p=L; if(newp->data.coef=0) cout<<"系数为零，重新输入!"<<endl; delete newp; i-; continue; while(p->next!=NULL)&&(p->next->data).exp<(newp->data).exp) p=p->next; /p指向指数最小的那一个 if(!JudgeIfExpSame( L, newp) newp->next=p->next; p->next=newp; else cout<<"输入的该项指数与多项式中已存在的某项相同,请重新创建一个正确的多项式"<<endl; delete newp; DestroyLink(L); CreateLink(L,n); /创建多项式没有成功，递归调用重新创建 break; /*判断指数是否与多项式中已存在的某项相同*/int JudgeIfExpSame(Link L,Link e)Link p;p=L->next;while(p!=NULL&&(e->data.exp!=p->data.exp) p=p->next;if(p=NULL)return 0;else return 1;/*输出链表*/void PrintList(Link L)Link p;if(L=NULL|L->next=NULL) cout<<"该一元多项式为空！"<<endl;else p=L->next; /项的系数大于0的5种情况 if(p->data).coef>0) if(p->data).exp=0) cout<<(p->data).coef;/如果指数为0则直接输出系数 else if(p->data).coef=1&&(p->data).exp=1) cout<<"x"/如果系数和指数均为1，则输出x else if(p->data).coef=1&&(p->data).exp!=1) cout<<"x"<<(p->data).exp;/如果系数为1，指数不为1，则输出x的指数次方 else if(p->data).exp=1&&(p->data).coef!=1) cout<<(p->data).coef<<"x"/如果系数不为1，指数为1，则输出系数倍xelse cout<<(p->data).coef<<"x"<<(p->data).exp;/如果系数和指数都不为1，则输出系数乘以x的指数次方 /项的系数小于0的5种情况 if(p->data).coef<0) if(p->data).exp=0) cout<<(p->data).coef;/如果指数为0，则直接输出系数 else if(p->data.coef=-1&&p->data.exp=1) cout<<"-x"/如果系数为-1，指数为1，则输出-x else if(p->data.coef=-1&&p->data.exp!=1) cout<<"-x"<<p->data.exp;/如果系数为-1，指数不为1，则输出x的指数次方的相反数 else if(p->data.exp=1) cout<<p->data.coef<<"x"/如果指数为1，则输出系数倍xelse cout<<(p->data).coef<<"x"<<(p->data).exp; /如果指数不为1，系数不为-1，则输出系数倍x的指数次方 p=p->next; while(p!=NULL) if(p->data).coef>0)/系数大于0时输出情况 if(p->data).exp=0) cout<<"+"<<(p->data).coef; else if(p->data).exp=1&&(p->data).coef!=1) cout<<"+"<<(p->data).coef<<"x" else if(p->data).exp=1&&(p->data).coef=1) cout<<"+"<<"x" else if(p->data).coef=1&&(p->data).exp!=1) cout<<"+"<<"x"<<(p->data).exp; else cout<<"+"<<(p->data).coef<<"x"<<(p->data).exp; if(p->data).coef<0)/系数小于0时输出情况 if(p->data).exp=0) cout<<(p->data).coef; else if(p->data.coef=-1&&p->data.exp=1) cout<<"-x" else if(p->data.coef=-1&&p->data.exp!=1) cout<<"-x"<<p->data.exp; else if(p->data.exp=1) cout<<p->data.coef<<"x" else cout<<(p->data).coef<<"x"<<(p->data).exp; p=p->next; cout<<endl;/*把一个链表的内容复制给另一个链表*/void CopyLink(Link &pc,Link pa)Link p,q,r;pc=new LNode;pc->next=NULL;r=pc;p=pa;while(p->next!=NULL) q=new LNode; q->data.coef=p->next->data.coef; q->data.exp=p->next->data.exp; r->next=q; q->next=NULL; r=q; p=p->next;/*将两个一元多项式相加*/void PolyAdd(Link &pc,Link pa,Link pb) Link p1,p2,p,pd;CopyLink(p1,pa);CopyLink(p2,pb);pc=new LNode;pc->next=NULL;p=pc;p1=p1->next;p2=p2->next;while(p1!=NULL&&p2!=NULL) if(p1->data.exp<p2->data.exp) p->next=p1; p=p->next; p1=p1->next; else if(p1->data.exp>p2->data.exp) p->next=p2; p=p->next; p2=p2->next; else p1->data.coef=p1->data.coef+p2->data.coef;/如果指数相同，运算时系数想加 if(p1->data.coef!=0) p->next=p1; p=p->next; p1=p1->next; p2=p2->next; else pd=p1; p1=p1->next; p2=p2->next; delete pd;/如果系数为0，则删除该项 if(p1!=NULL) p->next=p1;if(p2!=NULL) p->next=p2;/*将两个多项式相减*/void PolySubstract(Link &pc,Link pa,Link pb)Link p,pt;CopyLink(pt,pb);p=pt;while(p!=NULL) (p->data).coef=(-(p->data).coef);/被减的多项式前加“-”号 p=p->next;PolyAdd(pc,pa,pt);/调用多项式加法运算函数DestroyLink(pt);/清屏函数void Clear()system("pause");system("cls");/让用户重新选择/*将两个一元多项式相乘*/void PolyMultiply(Link &pc,Link pa,Link pb)Link p1,p2,p,pd,newp,t;pc=new LNode;pc->next=NULL;p1=pa->next;p2=pb->next;while(p1!=NULL) pd=new LNode; pd->next=NULL; p=new LNode; p->next=NULL; t=p; while(p2) newp=new LNode; newp->next=NULL; newp->data.coef=p1->data.coef*p2->data.coef;/系数相乘 newp->data.exp=p1->data.exp+p2->data.exp;/指数相加 t->next=newp; t=t->next; p2=p2->next; PolyAdd(pd,pc,p); CopyLink(pc,pd); p1=p1->next; p2=pb->next; DestroyLink(p); DestroyLink(pd);/菜单函数void Menu()cout<<""<<endl;cout<<endl;cout<<"=一元多项式的四则运算="<<endl;cout<<"tttttttt "<<endl;cout<<"1 创建要运算的两个一元多项式tt "<<endl;cout<<"2 将两个一元多项式相加ttt "<<endl;cout<<"3 将两个一元多项式相减ttt "<<endl;cout<<"4 将两个一元多项式相乘ttt "<<endl;cout<<"5 显示两个一元多项式ttt "<<endl;cout<<"6 销毁所创建的二个多项式tt "<<endl;cout<<"7 退出ttttt "<<endl;cout<<"tttttttt "<<endl;cout<<"请选择:"/判断输入的整数是不是为1到7的数字int CompareIfNum(int i)if(i>0&&i<8) return 0;else return 1;/返回1时出错，因为菜单中只有17void main()int n;Link L,La=NULL,Lb=NULL;/La,Lb分别为创建的两个多项式int choose;while(1) Menu(); /调用菜单函数 cin>>choose; switch(choose) case 1: cout<<"请输入你要运算的第一个一元多项式的项数:"<<endl; cin>>n; if(CompareIfNum(n)=1) cout<<"您的输入有误，请重新输入"<<endl; Clear(); break; CreateLink(La,n); cout<<"请输入你要运算的第二个一元多项式的项数:"<<endl; cin>>n; if(CompareIfNum(n)=1) cout<<"您的输入有误，请重新输入"<<endl; Clear(); break; CreateLink(Lb,n); Clear(); break; case 2: if(La=NULL|Lb=NULL) cout<<"您的多项式创建有误，请重新选择"<<endl; Clear(); break; PolyAdd(L,La,Lb);cout<<""<<endl; cout<<"设相加的两个一元多项式为和则："<<endl; cout<<""<<endl; cout<<"A的多项式为：" PrintList(La);cout<<""<<endl; cout<<"B的多项式为：" PrintList(Lb); cout<<""<<endl; cout<<"相加后的结果为：" PrintList(L);cout<<""<<endl; Clear(); DestroyLink(L); break; case 3: if(La=NULL|Lb=NULL) cout<<"您的多项式创建有误，请重新选择"<<endl; Clear(); break; PolySubstract(L,La,Lb); cout<<"设相减的两个一元多项式为和则："<<endl;cout<<""<<endl;cout<<"A的多项式为：" PrintList(La);cout<<""<<endl;cout<<"B的多项式为：" PrintList(Lb);cout<<""<<endl; cout<<"相减后的结果为：" PrintList(L);cout<<""<<endl; Clear(); DestroyLink(L);break; case 4: if(La=NULL|Lb=NULL) cout<<"您的多项式创建有误，请重新选择"<<endl; Clear(); break; PolyMultiply(L,La,Lb); cout<<"设相乘的两个一元多项式为和则："<<endl;cout<<""<<endl;cout<<"A的多项式为：" PrintList(La);cout<<""<<endl;cout<<"B的多项式为：" PrintList(Lb);cout<<""<<endl; cout<<"相乘后的结果为："PrintList(L);DestroyLink(L);cout<<""<<endl; Clear();break; case 5: if(La=NULL|Lb=NULL) cout<<"您的多项式创建有误，请重新选择"<<endl; Clear(); break; cout<<"一元多项式A为："<<endl; PrintList(La);cout<<""<<endl; cout<<"一元多项式B为："<<endl; PrintList(Lb);cout<<""<<endl; Clear();break; case 6: if(La&&Lb) DestroyLink(La); DestroyLink(Lb); cout<<"多项式销毁成功！"<<endl; Clear(); else cout<<"多项式不存在，请重新选择"<<endl; Clear(); break; case 7: exit(0); /exit(0)强制终止程序，返回状态码0表示正常结束 default: cout<<"您的输入有误，请重新选择操作"<<endl; Clear(); break;