毕业设计-多项式的设计报告数据结构课程设计.doc

目 录1.多项式的设计报告.2 a概要设计 .2 b详细设计 .3 c调试分析 .8 数据结果 .8 时间复杂度分析 10 问题和解决方法 10 源程序代码展示102.二叉树的设计报告.18 a概要设计 .18 b详细设计 .19 c调试分析 .21 数据结果 .21 时间复杂度分析 22 问题和解决方法 23 源程序代码展示233.课程设计总结26一 多项式的设计报告a 概要设计 1. 将该存储结构定义为链式结构的线性表存储结构的定义：struct Nodefloat coef;/结点类型int exp;typedef Node polynomial;struct LNodepolynomial data;/链表类型LNode *next;typedef LNode* Link;2创建函数流程图开 始 分 配 空 间第i个的系数ceof第i个的指数expexp0？否是错误，重新输入JudgeIfExpSame=1？ 否是错误，重新输入1=i注释：JudgeIfExpSame函数是判断输入的指数是否与多项式中已存在的某项的指数相同3.主程序流程图:4.多项式加法的算法分析将链表pa，pb分别复制到新建链表p1，p2中，再新建链表pc，然后分别依次对p1，p2链表中结点中的指数进行比较，将指数小的结点的值先赋值给pc中的结点，两个指数相同时，将系数相加后一起赋值给pc中的结点，最后将p1或者p2中多余的结点直接赋值给pc链表，pc链表就是通过加法后的多项式5.多项式减法的算法分析新建链表pt，将pb中的结点值赋给pt，然后将pt中所有结点的系数乘上（-1）后，再将pt和pa相加就得到相减后的多项式。6.多项式乘法的算法分析同样将链表pa，pb中的结点赋值给p1，p2，然后依次将p1中的每个结点的值分别与p2中每个结点的值相乘后赋值给pc，就得到相乘后的多项式。b 详细设计一 创建多项式的源程序void CreateLink(Link &L,int n)if(L!=NULL) /首先判断是已经存在多项式，如果存在则销毁DestroyLink(L);Link p,newp;L=new LNode;L-next=NULL;/分配结点空间，new相当于malloc函数(L-data).exp=-1; /创建头结点p=L;for(int i=1;i=n;i+)newp=new LNode;cout请输入第i项的系数和指数:endl;cout(newp-data).coef;cout(newp-data).exp;if(newp-data.exp0)cout您输入有误，指数不允许为负值!next=NULL;p=L;if(newp-data.coef=0)cout系数为零，重新输入!next!=NULL)&(p-next-data).expdata).exp) p=p-next; /p指向指数最小的那一个if(!JudgeIfExpSame( L, newp)newp-next=p-next;p-next=newp;else cout输入的该项指数与多项式中已存在的某项相同,请重新创建一个正确的多项式next=NULL;p=pc; /创建新链表pc来存储相加后的值p1=p1-next;p2=p2-next;while(p1!=NULL&p2!=NULL)if(p1-data.expdata.exp) /将指数小的结点的值赋给pc链表中的结点p-next=p1;p=p-next;p1=p1-next;else if(p1-data.expp2-data.exp)p-next=p2;p=p-next;p2=p2-next;else /当指数相等时，将系数相加后再把指数和系数赋给pcp1-data.coef=p1-data.coef+p2-data.coef; if(p1-data.coef!=0) /当相加后的系数不等于0，直接赋给pcp-next=p1;p=p-next;p1=p1-next;p2=p2-next;else /当相加后的系数等于0时不存储在pc中，将p1，p2分别指向下一个结点进行相加算法pd=p1;p1=p1-next;p2=p2-next;delete pd;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; /将链表pb赋给链表ptwhile(p!=NULL) (p-data).coef=(-(p-data).coef);p=p-next; /将pt中的系数都乘以（-1） PolyAdd(pc,pa,pt); /再将pt与pa相加，就得到相减的结果DestroyLink(pt);四多项式相乘模块的源程序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) /用循环的方式将p1的每个结点分别与p2中的每个结点相乘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); /再将相加的结果放到链表pc中去p1=p1-next;p2=pb-next;DestroyLink(p);DestroyLink(pd);五主函数源程序void main()/主函数int n;Link L,La=NULL,Lb=NULL;/La,Lb分别为创建的两个多项式int choose;Menu(); /调用菜单函数while(1) cinchoose;switch(choose)case 1:cout请输入需要运算的第一个一元多项式的项数:n;if(CompareIfNum(n)=1)cout输入有误，请重新输入ntttt请选择:;break;CreateLink(La,n); /创建链表Lacout请输入需要运算的第二个一元多项式的项数:n;if(CompareIfNum(n)=1)cout输入有误，请重新输入ntttt请选择:;break;CreateLink(Lb,n);coutntttt请继续选择:;break; /创建链表Lbcase 2:if(La=NULL|Lb=NULL)cout多项式不存在，请重新输入ntttt请选择:;break; /如果多项式为空则重新输入PolyAdd(L,La,Lb);coutendl; /将多项式相加cout待相加的两个一元多项式为：endl;coutendl;coutA的多项式为：;PrintList(La);coutendl;coutB的多项式为：;PrintList(Lb);coutendl; cout相加后的结果为：;PrintList(L);DestroyLink(L);coutntttt请继续选择:;break;case 3:if(La=NULL|Lb=NULL)cout多项式不存在，请重新输入ntttt请选择:;break;PolySubstract(L,La,Lb); /将多项式相减cout相减的两个一元多项式为：endl;coutendl;coutA的多项式为：;PrintList(La);coutendl;coutB的多项式为：;PrintList(Lb);coutendl;cout相减后的结果为：;PrintList(L);coutntttt请继续选择:;DestroyLink(L);break; case 4:if(La=NULL|Lb=NULL)cout多项式不存在，请重新输入ntttt请选择:;break;PolyMultiply(L,La,Lb); /将多项式相乘cout相乘的两个一元多项式为：endl;coutendl;coutA的多项式为：;PrintList(La);coutendl;coutB的多项式为：;PrintList(Lb);coutendl;cout相乘后的结果为：;PrintList(L);DestroyLink(L);coutntttt请继续选择:;break;case 5:if(La=NULL|Lb=NULL)cout多项式不存在，请重新输入ntttt请选择:;break;cout一元多项式A为：endl;PrintList(La);coutendl; /将多项式La输出cout一元多项式B为：endl;PrintList(Lb); /将多项式Lb输出coutntttt请继续选择:;break;case 6:if(La&Lb)DestroyLink(La);DestroyLink(Lb);cout多项式销毁成功！endl;couttttt请继续选择:;else cout多项式不存在，请重新输入ntttt请选择:;break;case 7:exit(0); /exit(0)强制终止程序，返回状态码0表示正常结束default:cout输入错误，请重新选择操作ntttt请选择:;break;c 调试分析1.数据结果 *一元多项式的运算* * * * 新建多项式 * * 加法运算 * * 减法运算 * * 相乘运算 * * 输出 * * 清空 * * 退出 * * * * 请选择:9输入错误，请重新选择操作 请选择:4多项式不存在，请重新输入 请选择:1请输入需要运算的第一个一元多项式的项数:46项数太大，请重新输入 请选择:1请输入需要运算的第一个一元多项式的项数:5请输入第1项的系数和指数:系数:34指数:5请输入第2项的系数和指数:系数:47指数:2请输入第3项的系数和指数:系数:48指数:1请输入第4项的系数和指数:系数:49指数:3请输入第5项的系数和指数:系数:28指数:4请输入需要运算的第二个一元多项式的项数:4请输入第1项的系数和指数:系数:33指数:5请输入第2项的系数和指数:系数:39指数:1请输入第3项的系数和指数:系数:29指数:3请输入第4项的系数和指数:系数:88指数:2 请继续选择:2待相加的两个一元多项式为：A的多项式为：48x+47x2+49x3+28x4+34x5B的多项式为：39x+88x2+29x3+33x5相加后的结果为：87x+135x2+78x3+28x4+67x5 请继续选择:3相减的两个一元多项式为：A的多项式为：48x+47x2+49x3+28x4+34x5B的多项式为：39x+88x2+29x3+33x5相减后的结果为：9x-41x2+20x3+28x4+x5 请继续选择:4相乘的两个一元多项式为：A的多项式为：48x+47x2+49x3+28x4+34x5B的多项式为：39x+88x2+29x3+33x5相乘后的结果为：1872x2+6057x3+7439x4+6767x5+6795x6+5355x7+2603x8+924x9+1122x10 请继续选择:5一元多项式A为：48x+47x2+49x3+28x4+34x5一元多项式B为：39x+88x2+29x3+33x5 请继续选择:6多项式销毁成功！ 请继续选择:7Press any key to continue2时间复杂度分析创建函数的复杂度为o（n），复制链表时为o（n），设链表a为n1个节点，链表b为n2个节点，加法运算时因为有复制过程所以如果是不理想状态复杂度为o（2（n1+ n2），减法运算时因为先将链表b复制然后又将其改成-pb，然后将-pb与pa相加，故复杂度为o（2（n1+ 2n2），乘法时复杂度为o（n1*n2）3.问题和解决方法1.开始没有想到将链表复制，而是直接在链表上进行的操作，但是却因此改变了链表的值而影响了后面的操作使结果不如人意。解决方法是从网上看了一个程序后，重新分配空间后将其链表复制到其上，才达到效果，不影响原来多项式的数值。2.系数的表示方法，开始运行的时候，不是很到位，比如说当系数为1或-1时，可以省略1，还有指数1和0次方的表示比较特殊。所以解决的时候必须分别分情况讨论。但是又增加了程序的空间复杂度。还有一些其他细小的问题一般都会有的，只需注意一下，也比较容易改正。3.在课设过程中有遇到这样一个问题，就是对一个操作完成以后它不会进行下一个操作，分析之后发现switch语句中用到break，而没有循环故不进行下个选项直接跳出switch到主函数中去了，加入一个while以后就可以正常进行。4.改进改进的话就是需要尽量减少空间复杂度和时间复杂度。源程序代码展示#include#include#includeusing namespace std;struct Nodefloat coef;/结点类型int exp;typedef Node polynomial;struct LNodepolynomial data;/链表类型LNode *next;typedef LNode* Link;void DestroyLink(Link &L)/销毁链表函数Link p;p=L-next;while(p) L-next=p-next;delete p;p=L-next;delete L;L=NULL;/*判断指数是否与多项式中已存在的某项相同*/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;/用头插入法创建含有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(newp-data).coef;cout(newp-data).exp;if(newp-data.exp0)cout您输入有误，指数不允许为负值!next=NULL;p=L;if(newp-data.coef=0)cout系数为零，重新输入!next!=NULL)&(p-next-data).expdata).exp) p=p-next; /p指向指数最小的那一个if(!JudgeIfExpSame( L, newp)newp-next=p-next;p-next=newp;else cout输入的该项指数与多项式中已存在的某项相同,请重新创建一个正确的多项式next=NULL) cout该一元多项式为空！next;/项的系数大于0的5种情况if(p-data).coef0) if(p-data).exp=0)coutdata).coef;else if(p-data).coef=1&(p-data).exp=1)coutdata).coef=1&(p-data).exp!=1)coutxdata).exp;else if(p-data).exp=1&(p-data).coef!=1)coutdata).coefx;else coutdata).coefxdata).exp;/项的系数小于0的5种情况if(p-data).coefdata).exp=0)coutdata).coef;else if(p-data.coef=-1&p-data.exp=1)coutdata.coef=-1&p-data.exp!=1)cout-xdata.exp;else if(p-data.exp=1)coutdata.coefx;else coutdata).coefxdata).exp;p=p-next;while(p!=NULL)if(p-data).coef0)if(p-data).exp=0) cout+data).coef;else if(p-data).exp=1&(p-data).coef!=1) cout+data).coefdata).exp=1&(p-data).coef=1)cout+data).coef=1&(p-data).exp!=1)cout+xdata).exp;else cout+data).coefxdata).exp;if(p-data).coefdata).exp=0)coutdata).coef;else if(p-data.coef=-1&p-data.exp=1)coutdata.coef=-1&p-data.exp!=1)cout-xdata.exp;else if(p-data.exp=1)coutdata.coefx;else coutdata).coefxdata).exp;p=p-next;coutnext=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.expdata.exp)p-next=p1;p=p-next;p1=p1-next;else if(p1-data.expp2-data.exp)p-next=p2;p=p-next;p2=p2-next;elsep1-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;elsepd=p1;p1=p1-next;p2=p2-next;delete pd;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 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()coutendlendl;coutt*一元多项式的运算*endl;coutt*ttttttt *endl; coutt*ttt 新建多项式 ttt *endl; coutt*ttt 加法运算ttt * endl; coutt*ttt 减法运算ttt *endl; coutt*ttt 相乘运算ttt *endl; coutt*ttt 输出ttt * endl; coutt*ttt 清空ttt * endl; coutt*ttt 退出ttt *endl; coutt*ttttttt *endl; coutt*endl;cout0&ichoose;switch(choose)case 1:cout请输入需要运算的第一个一元多项式的项数:n;if(CompareIfNum(n)=1)cout输入有误，请重新输入ntttt请选择:;break;CreateLink(La,n);cout请输入需要运算的第二个一元多项式的项数:n;if(CompareIfNum(n)=1)cout输入有误，请重新输入ntttt请选择:;break;CreateLink(Lb,n);coutntttt请继续选择:;break; case 2:if(La=NULL|Lb=NULL)cout多项式不存在，请重新输入ntttt请选择:;break;PolyAdd(L,La,Lb);coutendl;cout待相加的两个一元多项式为：endl;coutendl;coutA的多项式为：;PrintList(La);coutendl;coutB的多项式为：;PrintList(Lb);coutendl; cout相加后的结果为：;PrintList(L);DestroyLink(L);coutntttt请继续选择:;break;case 3:if(La=NULL|Lb=NULL)cout多项式不存在，请重新输入ntttt请选择:;break;PolySubstract(L,La,Lb);cout相减的两个一元多项式为：endl;coutendl;coutA的多项式为：;PrintList(La);coutendl;coutB的多项式为：;PrintList(Lb);coutendl;cout相减后的结果为：;PrintList(L);coutntttt请继续选择:;Destr