一元多项式相加.doc

数据结构课设计报告20122013学年第一学期课程名称 数据结构 设计题目 用单链表实现集合的操作专业班级 姓 名 学 号 指导教师 一元多项式相加1.问题描述已知A（x）=a0+a1x+a2x2+anxn 和 B（x）= b0+b1x+b2x2+bnxm ,并且在A（x）和B（x）中指数相差很多，求A（x）= A（x）+ B（x）。2.基本要求 (1)设计存储结构表示一元多项式; (2)设计算法实现一元多项式相加; (3)分析算法的时间复杂度和空间复杂度.3. 设计思想 一元多项式求和实际上是合并同类项的过程，其运算规则为：（1）若两项的指数相等，则系数相加； （2）若两项的指数不相等，则将两项加在结果中。 一元多项式由n+1个系数唯一确定，因此，可以用一个线性表 来表示，每一项的系数i隐含在其系数ai的序号里。但是，当多项式的指数很高且变化很大时，在表示多项式的线性表中就会存在很多0元素。一个较好的存储方法就是只存非0元素，但是需要在存储非0元素系数的同时存储相应的指数。这样，一个一元多项式的每一个非0项可由系数和指数唯一表示。由于两个一元多项式相加后，会改变多项式的指数和系数，因此采用顺序表不合适。采用单链表存储，则每一个非0项对应单链表中的一个节点，且单链表应按指数递增有序排列。其中： Coef是系数域，存放非0项的系数； Exp是指数域，存放非0项的指数； Next是指针域，存放指向下一个节点的指针。将两个一元多项式用两个单链表存储后，如何实现二者相加呢？设两个工作指针p和q，分别指向两个单链表的开始节点。通过对节点p的指针域和节点q的指针域进行比较进行同类项合并，则出现下列三种情况：1. 若p-exp小于q-exp，则节点p应为结果中的一个节点。2. 若p-exp大于 q-exp，则节点q应为结果中的一个节点，将q插入到第一个链表中节点p之前。3. 若p-exp等于q-exp，则节点p与节点q为同类项，将q的系数加到p的系数上。若相加结果不为0，则节点p应为结果中的一个节点，同时删除节点q；若相加结果为0；则表明结果中无此项，删除节点p和节点q。代码：#include#include#includestdio.htypedef struct float coef;/结点类型 int expn;polynomial;typedef struct LNode polynomial data;/链表类型 struct LNode *next;LNode,*Link;void createLink(Link &L,int n);void printList(Link L);void addPolyn(Link &pc,Link pa,Link pb);int locateLink(Link pa,Link e);void destroyLink(Link &L);int compareNum(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; /int k=0; L=new LNode; L-next=NULL; (L-data).expn=-1;/创建头结点 p=L; for(int i=1;i=n;i+) newp=new LNode; cout请输入第i项的系数和指数:endl; cout(newp-data).coef; cout(newp-data).expn; if(newp-data.expn0)cout您输入有误，指数不允许为负值!next=NULL; p=L; if(newp-data.coef=0)cout系数为零，重新输入!next!=NULL)&(p-next-data).expndata).expn) p=p-next; if(!locateLink( L, newp) newp-next=p-next; p-next=newp; else cout输入的该项指数与多项式中已存在的某项相同,请重新创建一个正确的多项式next; while(p!=NULL&(e-data.expn!=p-data.expn) p=p-next; if(p=NULL)return 0; else return 1; /*输出链表*/void printList(Link L) Link p; if(L=NULL|L-next=NULL) cout该一元多项式为空！next; if(p-data).coef0) if(p-data).expn=0) coutdata).coef; else if(p-data).coef=1&(p-data).expn=1) coutdata).coef=1&(p-data).expn!=1) coutxdata).expn; else if(p-data).expn=1&(p-data).coef!=1) coutdata).coefx; else coutdata).coefxdata).expn; if(p-data).coefdata).expn=0) coutdata).coef; else if(p-data.coef=-1&p-data.expn=1) coutdata.coef=-1&p-data.expn!=1) cout-xdata.expn; else if(p-data.expn=1) coutdata.coefx; else coutdata).coefxdata).expn; p=p-next; while(p!=NULL) if(p-data).coef0) if(p-data).expn=0) cout+data).coef; else if(p-data).expn=1&(p-data).coef!=1) cout+data).coefdata).expn=1&(p-data).coef=1) cout+data).coef=1&(p-data).expn!=1) cout+xdata).expn; else cout+data).coefxdata).expn; if(p-data).coefdata).expn=0) coutdata).coef; else if(p-data.coef=-1&p-data.expn=1) coutdata.coef=-1&p-data.expn!=1) cout-xdata.expn; else if(p-data.expn=1) coutdata.coefx; else coutdata).coefxdata).expn; 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.expn=p-next-data.expn; r-next=q; q-next=NULL; r=q; p=p-next; /*将两个一元多项式相加*/void addPolyn(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.expndata.expn) p-next=p1; p=p-next; p1=p1-next; else if(p1-data.expnp2-data.expn) 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; elsepd=p1;p1=p1-next;p2=p2-next;delete pd; if(p1!=NULL) p-next=p1; if(p2!=NULL)p-next=p2;/清屏函数void Clear() char a; cout请按 回车键 继续endl; a=getchar(); system(cls); /菜单函数void menuPrint() cout/t*一元多项式的简单运算*endl; cout/t/t 1创建要运算的两个一元多项式endl; cout/t/t 2将两个一元多项式相加endl; cout/t/t 3显示两个一元多项式endl; cout/t/t 4销毁所创建的二个多项式endl; cout/t/t 5退出endl; cout请输入你要进行的操作（1-5）choose; switch(choose) case 1: cout请输入你要运算的第一个一元多项式的项数:n; if(compareNum(n)=0)cout您的输入有误，请重新输入endl;Clear();break; createLink(La,n); cout请输入你要运算的第二个一元多项式的项数:n; if(compareNum(n)=0)cout您的输入有误，请重新输入endl;Clear();break; createLink(Lb,n); Clear(); break; case 2: if(La=NULL|Lb=NULL)cout您的多项式创建有误，请重新选择endl;Clear();break; addPolyn(L,La,Lb); cout相加的两个一元多项式为：endl; printList(La); printList(Lb); cout相加后的结果为：endl; printList(L); Clear(); destroyLink(L); break; case 3: if(La=NULL|Lb=NULL)cout您的多项式创建有误，请重新选择endl;Clear();break; cout第一个一元多项式为：endl; printList(La); cout第二个一元多项式为：endl; printList(Lb); Clear(); break; case 4: if(La&Lb)destroyLink(La);destroyLink(Lb);cout销毁成功！endl;Clear(); else cout多项式不存在，请重新选择endl;Clear(); break; case 5: exit(0); default: cout您的输入有误，请重新选择操作endl;Clear(); break; 运行后结果如下：相加后4.实验心得 ： 对于多项式的运算的，运算符的输出很重要，一开始多输出一个+，并且当为负数时会输出+-。还有当系数为0时的输出都没有专门考虑。 通过与同学讨论，这次用链表的来做这道题目让我收获很大