数据结构课程设计_一元多项式的加法、减法、乘法的实现.doc

一、设计题目一元多项式的加法、减法、乘法的实现。二、主要内容设有一元多项式Am(x)和Bn(x). Am(x)=A0+A1x1+A2x2+A3x3+ +Amxm Bn(x)=B0+B1x1+B2x2+B3x3+ +Bnxn 请实现求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)×Bn(x)。 要求： 1)  首先判定多项式是否稀疏2)  采用动态存储结构实现；3)  结果M(x)中无重复阶项和无零系数项；4)  要求输出结果的升幂和降幂两种排列情况三、具体要求及应提交的材料1每个同学以自己的学号和姓名建一个文件夹，如：“。里面应包括：学生按照课程设计的具体要求所开发的所有源程序应该放到一个文件夹中、任务书和课程设计说明书的电子文档。2打印的课程设计说明书注意：在封面后夹入打印的“任务书以后再装订。四、主要技术路线提示为把多个小功能结合成一个完整的小软件，需使用“菜单设计技术可以是控制台方式下的命令行形式，假设能做成图形方式那么更好。五、进度安排共计两周时间，建议进度安排如下：选题，应该在上机实验之前完成需求分析、概要设计可分配4学时完成详细设计可分配4学时调试和分析可分配10学时。2学时的机动，可用于辩论及按教师要求修改课程设计说明书。注：只用课内上机时间一般不能完成设计任务，所以需要学生自行安排时间做补充。六、推荐参考资料(不少于3篇)1苏仕华等编著，数据结构课程设计，机械工业出版社，20072严蔚敏等编著，数据结构C语言版，清华大学出版社，20033严蔚敏等编著，数据结构题集C语言版，清华大学出版社，2003指导教师 签名日期 年 月 日系 主 任 审核日期 年 月 日摘 要 分析了matlab，mathmatic，maple等数学软件对一元多项式的计算过程，步骤后。由于这些软件比拟大功能齐全，但是实用性不强。因此，利用microsoft visual studio 6.0开发工具，编程实现了一元多项式的加法、减法、乘法的计算器系统，该系统具有一元多项式的加法、减法、乘法等功能。关键词：一元多项式; 软件; 计算 目 录 1需求分析12开发及运行平台23 概要设计34 详细设计45 调试分析86 测试结果97 结论11致 谢12参考文献13附 录161需求分析 动态链表结构下的一元多项式的加法、减法、乘法的实现。  设有一元多项式Am(x)和Bn(x).  Am(x)=A0+A1x1+A2x2+A3x3+ +Amxm  Bn(x)=B0+B1x1+B2x2+B3x3+ +Bnxn 实现求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)×Bn(x)。1输入形式和输入值范围：输入的系数为float类型，输入的幂为int类型请选择:1请输入你要运算的第一个一元多项式的项数:2请输入第1项的系数和指数:系数:1指数:1请输入第2项的系数和指数:系数:1指数:22输出形式请选择:5一元多项式A为：x+x2一元多项式B为：4x4+5x5+6x63程序所能到达的功能1) 首先判定多项式是否稀疏; 2) 采用动态存储结构实现;3) 结果M(x)中无重复阶项和无零系数项；4) 要求输出结果的升幂和降幂两种排列情况4测试数据：包括正确地输入及其输出结果和含有错误的输入及其输出结果。正确的输入：请选择:5一元多项式A为：x+x2一元多项式B为：4x4+5x5+6x6错误的输入：请输入第1项的系数和指数:系数:1指数:1请输入第2项的系数和指数:系数:2指数:1输入的该项指数与多项式中已存在的某项相同,请重新创立一个正确的多项式请输入第1项的系数和指数:2开发及运行平台Windows 7 alienware 平台上，Microsoft Visual studio 6.0 环境下开发。所以建议用户在使用时，在windows 7 平台上使用。3 概要设计数据类型的定义：struct Nodefloat coef;/结点类型，系数int exp;/指数;typedef Node polynomial;struct LNodepolynomial data;/链表类型LNode *next;typedef LNode* Link;模块调用关系如图1所示：一元多项式相乘一元多项式输出一元多项式销毁退出一元多项式创立一元多项式相加一元多项式的四那么运算一元多项式相减 图 1 一元多项式计算器模块调用图 4 详细设计 加法模块：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不为空且p2不为空)if(p1->data.exp<p2->data.exp)then： p->next=p1;p=p->next; p1=p1->next; else if(p1->data.exp>p2->data.exp) then： p->next<-p2; p<-p->next;p2<-p2->next; else <-p1->data.coef+p2->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)then：p->next=p1;endifif(p2!=NULL)then ： p->next=p2;endif减法模块，如图2所示：开始调用多项式加法函数进行运算将多项式B进行复制取多项式B的相反数 图 2 减法模块结构图void PolySubstract(Link &pc,Link pa,Link pb)Link p,pt;CopyLink(pt,pb);p<-pt;while(p不为空) (p->data).coef<- (-(p->data).coef);/被减的多项式前加"-"号 p<-p->next;PolyAdd(pc,pa,pt);/调用多项式加法运算函数DestroyLink(pt);乘法模块：如图3所示开始给出运算的两个多项式按系数相乘指数相加进行运算将运算的结果相加并输出 图 3 乘法模块结构图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不为空) 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);5 调试分析1调试过程中遇到的问题 ：独立测试各个模块的功能时发现在创立链表后和另一个进行运算后多余的存储单元没有释放而造成内存的泄漏，还有对于链表的运算时结束条件掌握不透彻导致没有按方案地去结束，比方在用For循环及While循环时没有正确地判断指针的移动与结束条件而得不到自己想要的结果。进入函数内部调试时发现有误用没有初始化的变量，还有赘余的语句扰乱了代码的健壮性。 在主函数中对各个函数的调用时没有一个清晰的思路，使程序显得很混乱，给调试造成了很大困难。 对非法操作控制的不够完善，例如缺少对越界访问及其非法数据的控制机制，使程序的平安性下降。2算法的时空分析该程序的实现是用链表实现的，所以时间复杂度和空间复杂度主要来自于链表的操作，都是O(n)。3经验和体会编写的程序不但要拿来使用，还要给别人查看，以便代码的维护。所以代码编写的风格尽量标准，清晰。变量要尽量少定义，结构夜采用简单的。另外，对指针的使用要小心，尽量在定义的时候就进行初始化，防止野指针，指针的使用涉及到内存的分配。6 测试结果判断稀疏，如图4所示： 图 4 判断多项式是否稀疏 加法运算，如图5所示: 图 5加法测试结果 减法运算，如图6所示: 图 6 减法测试结果乘法运算，如图7所示:图 7 乘法测试结果降幂升幂排序，如图8所示图8降幂升幂排序测试结果 7 结论该程序根本实现了要求的顺序结构、动态链表结构下的一元多项式的加法、减法、乘法等功能。代码较为冗余，可读性较差，可以多添加一些提示语句以及注释。在这次课程设计中我又进一步地了解了数据结构中算法的核心思想的重要性，懂得了一个程序地好坏关键在于算法是否优秀，一个好的优秀的算法可以使我们的程序更加完善，平安性更高以及有更高的效率。这次设计中我发现了自己的许多缺乏，如对指针的机制掌握的还不是很透彻，有的时候会出现指针指向错误以及空指针的错误,还有不能很好地分析自己算法地复杂度以及不能很好地使用控制机制使自己的程序流畅地运行。致 谢 感谢指导老师给我的一些重要指导以及提供的资料，感谢严蔚敏编著的数据结构等资料，让我在编写代码的过程中少走了很多弯路。参考文献1苏仕华等编著.数据结构课程设计.机械工业出版社.20072严蔚敏等编著.数据结构C语言版.清华大学出版社.20033严蔚敏等编著.数据结构题集C语言版.清华大学出版社，2003 5.陈清华 朱红主编. Visual C+课程设计案例精选与编程指导.东南大学出版社，2003.06，南京 6.刘振安等编著. C+程序设计课程设计.机械工业出版社，2004.08，北京附 录附录1 源程序清单#include<iostream>/标准输入输出流#include<conio.h>/使程序中可用键盘输入函数#include<stdlib.h>/使程序中可用系统标准输出函数#include<math.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;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; JudgeIf(L);/判断稀疏void JudgeIf(Link L)Link p;int flag=0;/判断是否为稀疏的标志p=L->next;while(p->next!=NULL)if(abs(p->next->data.exp-p->data.exp)>1)flag=1;elseflag=0; p=p->next;if(flag)cout<<"该多项式是稀疏的哈"<<endl;elsecout<<"该多项式是连续的哈"<<endl;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;elsep=L->next; 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; else if(p->data).exp=1&&(p->data).coef!=1) cout<<(p->data).coef<<"x" else cout<<(p->data).coef<<"x"<<(p->data).exp; 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; else if(p->data.exp=1) cout<<p->data.coef<<"x"/如果指数为1，那么输出系数倍xelse cout<<(p->data).coef<<"x"<<(p->data).exp; 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<<"请选择:"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; 附录2 用户使用说明双击该软件目录下的exe文件即可，或那么右击，然后翻开即可正常使用。原文已完。下文为附加文档，如不需要，下载后可以编辑删除，谢谢！施工组织设计本施工组织设计是本着“一流的质量、一流的工期、科学管理来进行编制的。编制时，我公司技术开展部、质检科以及工程部经过精心研究、合理组织、充分利用先进工艺，特制定本施工组织设计。一、 工程概况：西夏建材城生活区27#、30#住宅楼位于银川市新市区，橡胶厂对面。本工程由宁夏燕宝房地产开发开发，银川市规划建筑设计院设计。本工程耐火等级二级，屋面防水等级三级，地震防烈度为8度，设计使用年限50年。本工程建筑面积:27#m2;30# m2。室内地坪± m为准，总长27#m；30# m。总宽27#m；30# m。设计室外地坪至檐口高度18.6 00m，呈长方形布置，东西向，三个单元。本工程设计屋面为坡屋面防水采用防水涂料。外墙水泥砂浆抹面，外刷浅灰色墙漆。内墙面除卫生间200×300瓷砖，高到顶外，其余均水泥砂桨罩面，刮二遍腻子；楼梯间内墙采用50厚胶粉聚苯颗粒保温。地面除卫生间200×200防滑地砖，楼梯间50厚细石砼1：1水泥砂浆压光外，其余均采用50厚豆石砼毛地面。楼梯间单元门采用楼宇对讲门，卧室门、卫生间门采用木门，进户门采用保温防盗门。本工程窗均采用塑钢单框双玻窗，开启窗均加纱扇。本工程设计为节能型住宅，外墙均贴保温板。本工程设计为砖混结构，共六层。根底采用C30钢筋砼条形根底，