一元多项式相加数据结构实验

-.z.中南大学"数据构造与算法"课程实验实验报告题目实验一线性表的操作学生姓名谭淇蔚学生**3901130721专业班级软件工程1307班完成日期2014年3月31日星期一实验一线性表的操作〔一元多项式相加〕1.需求分析我们使用计算机处理的对象之间通常存在着的是一种最简单的线性关系，这类数学模型可称为线性的数据构造。而数据存储构造有两种：顺序存储构造和链式存储构造。线性表是最常用且最简单的一种数据构造。所以我们做的是实验一-----------线性表的操作。实验的目的是掌握线性表的根本操作，插入、删除、查找，以及线性表合并等运算在顺序存储构造和链接存储构造上的运算以及熟练运用掌握的线性表的操作，实现一元n次多项式的加法运算。学习实现一元n次多项式的加法是符号多项式的操作，是表处理的典型用例，需要注意的是：顺序存储构造指的是用数组方法，使用数组方法实现时，在插入和删除的方面，数组不如链表灵活，方法复杂，删除其中一个需要将其后的数组元素改变位置，使其数组保持原有的顺序构造，在查找方面较链表简单，只需要知道其下标就可以知道。链接存储构造指的是用链表方法,值得注意的是，删除和插入较为灵活，不需要变动大多数元素，但是查找过程相对于数组这种顺序存储构造来说较为复杂，耗时巨大。我们要学习的是通过对两种方法根本操作的掌握来做到实现一元n次多项式的相加减。我们程序的任务是：能进展简单的线性表操作〔插入、删除、查找〕以及线性表合并等运算。能通过这些根本操作实现一元多项式相加。明确规定：输入的形式：按照提示〔比方："请您输入第一个构造体数组的项数〔不超过50项〕：〞、"请您输入第二个构造体数组的项数〔不超过50项〕：〞、"请输入第n项的系数〞、"请输入第n项的指数〞等等〕，先输入多项式的项数，之后顺次输入每一项的系数与指数。输入值的范围：项数没有要求，但不能过于巨大；系数取为float型数据，指数取为int型数据，输出的形式：按照提示〔比方："您输入的第一个多项式为：〞、"您输入的第二个多项式为：〞等等〕，会输出原输入的多项式和经过排序和合并之后的降幂型多项式。同时，系数会以保存小数点后两位数字的形式输出；假设指数输入时为小数，则输出时会自动截取其整数局部。程序所能到达的功能：程序可以对输入的序列紊乱的多项式进展加工，使之按照降幂排列，之后对两多项式进展加法运算〔包括系数为负的加法〕，最后输出最终的多项式。测试数正确数据：输入：2**^3+2**^6+2**^7+2**^8+2**^10和-3**^10+4**^8+2**^7+3**^5+3**^3输出：7.00**^2+8.00**^1+2.00错误数据：输入：-8**^1.5+4**^2和3**^2+12**^1.6输出：7.00**^2+4.00**^12．概要设计〔1〕链接存储构造：structnode{floatcoef;inte*po;structnode*ne*t;}chainLink;函数主体局部，利用头指针进展链表操作，利用display进展打印出屏幕，利用order函数对其进展降幂排序，当两个多项式已经创立完毕时，利用add函数进展两个多项式相加。〔2〕顺序存储构造抽象数据类型为构造体数组：structpoly{floatcoef;inte*p;};函数主体局部，会引用指针进展参数传递，在函数主体局部定义了3个构造体数组同时定义其所对应的指针，利用用户输入，利用print函数将其打印出来，再用sort函数将其降序排列，做完两个构造体数组后，接着利用add函数将两个多项式相加。3．详细设计〔1〕链接存储构造：构造体定义：structnode{ intcoef;//系数 inte*p;//指数 structnode*ne*t;//指针域}chainLink;//创立chainLink的node结点对象〔值得注意的是，与顺序存储构造不同的是，内部还定义了指针域〕功能函数介绍：structnode*create()//定义建立多项式函数，并返回链表头指针{structnode*h=NULL,*q,*p;//定义构造体头指针h，标记指针p和q，p是创造新节点的标记指针，q是链接链表的指针；inti=1,N;//定义多项式的项数N及标记数i cout<<"请输入多项式的项数：\n"; cin>>N; p=0;//指针初始化；q=0;//本地指针初始化；for(;i<=N;i++) { p=(structnode*)malloc(sizeof(chainLink));//为一个新节点分配空间cout<<"请输入第"<<i<<"项的系数：\n"; cin>>(*p).coef; cout<<"请输入第"<<i<<"项的指数:\n"; cin>>(*p).e*p; if(i==1){h=p;q=p;}//建立头节点else { q->ne*t=p; q=p; } } q->ne*t=NULL;//p,q都成为新链表的尾指针；p->ne*t=NULL; returnh;}PS：值得注意的是，我在里面P，q指针均使其值为0，是让其为空指针，对其进展初始化，在visualstudio2013版中，如果不进展初始化，会被报错。打印函数display:voiddisplay(structnode*h){ structnode*p;//定义标记指针，输出链表p=h; while(p!=NULL) { if(p->coef==0) { structnode*d; d=h; while(d->ne*t!=p) { d=d->ne*t; } d->ne*t=p->ne*t; p=p->ne*t;//删去系数为0的节点； }else { if(p->coef<0)//系数为负时应加上括号,让式子容易看清； {if(p->e*p==0)cout<<(*p).coef<<"+"; elsecout<<"("<<(*p).coef<<")"<<"**^"<<(*p).e*p<<"+"; } else { if(p->e*p==0)cout<<(*p).coef<<"+"; elseif(p->e*p!=0&&p->e*p!=1) { cout<<(*p).coef<<"**^"<<(*p).e*p<<"+"; } elsecout<<(*p).coef<<"**+"; } p=p->ne*t; } } cout<<"\b\b\n";}PS:打印函数display中，值得注意的是系数为负时，应该加括号。其次，当指数为1时，没必要写成*^1这种形式。系数为0的项也应该删去，这里我定义一个d指针，用来找到系数为0的项前一个结点的指针，然后进展删除该系数为0的节点的操作，其实和教师上课中的处理差不多，都是使用一个指针保护原有指针，用while循环找到系数为0的项的前驱，以便进展删除节点操作。排序函数order：structnode*order(structnode*h)//定义排序函数，并返回整理后的链表的头指针{structnode*p,*q,*t,*h1,*h2;//定义三个构造体标记指针和两个头指针h1=h;//建立一个新的链表，头指针为h，指向原链表的第一个节点，之后将原链表中的节点一个一个的插入此链表，进展排序h2=h1->ne*t;//将原来的链表建立成待排序链表h1->ne*t=NULL;//截断第一个原链表中的节点while(h2!=NULL) { q=h1; p=q->ne*t; t=h2;//从待排序链表中选出一个节点准备插入到新链表中h2=h2->ne*t;//移动待排序链表的头指针，便于进展下一次挑选t->ne*t=NULL; if(t->e*p>q->e*p)//应插入头指针之前的情况 {t->ne*t=q; h1=t; continue; } if(p==NULL&&t->e*p<=q->e*p)q->ne*t=t;//应插入表尾的情况while(p!=NULL) { if(t->e*p>p->e*p) { q->ne*t=t; t->ne*t=p; break; } else { q=q->ne*t; p=p->ne*t; } } if(p==NULL)q->ne*t=t; } returnh1;//新链表即为按降幂顺序排好的链表，返回其头指针}Order函数其实是利用了3个头指针，具体操作看代码即可，其实很容易懂。相加函数add：structnode*add(structnode*h1,structnode*h2)//定义加法函数，并返回结果的链表的头指针{structnode*p,*q,*head,*r;//定义构造体头指针head和标记指针p,q,r p=h1; q=h2; head=(structnode*)malloc(sizeof(chainLink));//为结果多项式分配头指针if(p->e*p>=q->e*p){head=h1;p=p->ne*t;} else { if(p->e*p<q->e*p){head=h2;q=q->ne*t;} else{p->coef=p->coef+q->coef;head=p;p=p->ne*t;q=q->ne*t;} } r=head; while(p!=NULL&&q!=NULL) { if(p->e*p>q->e*p){r->ne*t=p;p=p->ne*t;} else { if(p->e*p<q->e*p){r->ne*t=q;q=q->ne*t;} else{p->coef=p->coef+q->coef;r->ne*t=p;p=p->ne*t;q=q->ne*t;} } r=r->ne*t; } if(p==NULL&&q==NULL)r->ne*t=NULL; else { if(p==NULL)r->ne*t=q; if(q==NULL)r->ne*t=p; } returnhead;}add函数大局部其实和教师PPT思路差不多。比拟两个多项式中指数大小，然后分别对其余两个进展操作。〔2〕顺序存储构造构造体定义：structpoly{ floatcoef; inte*p;};//构造体数组定义主函数构造体数组的创立以及导引指针的创立：polyp[50],*po=p;polyp1[50],*po1=p1;polyp2[100],*po2=p2;//定义三个构造体数组，用于存放多项式,定义三个指针变量；print函数以及参数调用代码：voidprint(structpoly*s[],intn){ for(inti=0;i<n;i++) { if(i==n-1)cout<<(*s)[i].coef<<"**^"<<(*s)[i].e*p; else cout<<(*s)[i].coef<<"**^"<<(*s)[i].e*p<<"+"; }}//输出数组主函数中调用print函数的具体形式：print(&po,n1);sort函数的代码：voidsort(structpoly*s[],intn){ inti,temp1,j;//定义数组中的循环标记数据i与j，和整型标记temp1 floattemp2;//定义单精度型标记temp2 for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) { if((*s)[j].e*p>(*s)[i].e*p) { temp1=(*s)[j].e*p; (*s)[j].e*p=(*s)[i].e*p; (*s)[i].e*p=temp1; temp2=(*s)[j].coef; (*s)[j].coef=(*s)[i].coef; (*s)[i].coef=temp2; } } for(i=0;i<n-1;i++) { if((*s)[i].e*p==(*s)[i+1].e*p) { (*s)[i+1].coef=(*s)[i].coef+(*s)[i+1].coef; if(i==n-2) { (*s)[i].coef=(*s)[i+1].coef; (*s)[i+1].coef=0; } else { for(j=i;j<n;j++) { (*s)[j].coef=(*s)[j+1].coef; (*s)[j].e*p=(*s)[j+1].e*p; } (*s)[j].coef=0; i--; } } }}事实上sort函数是采用逆冒泡法排序，让指数局部大的排在前面，与选择排序不同，选择排序是相邻的交换，直到最小的排在前面为止。Sort函数在主函数中的调用：sort(&po,n1);add函数的代码：voidadd(structpoly*s[],structpoly*s1[],structpoly*s2[],intn1,intn2){ inti=0,j=0,p,m;//定义数组中的循环标记数据i,j,p,m for(p=0;;p++) { if((*s)[i].e*p==(*s1)[j].e*p) { (*s2)[p].coef=(*s)[i].coef+(*s1)[j].coef; (*s2)[p].e*p=(*s)[i].e*p; i++; j++; } else { if((*s)[i].e*p>(*s1)[j].e*p) { (*s2)[p].coef=(*s)[i].coef; (*s2)[p].e*p=(*s)[i].e*p; i++; } else { (*s2)[p].coef=(*s1)[j].coef; (*s2)[p].e*p=(*s1)[j].e*p; j++; } } if(i==n1||j==n2) { p++; break; } } if(i==n1) for(;j<n2;j++) { (*s2)[p].coef=(*s1)[j].coef; (*s2)[p].e*p=(*s1)[j].e*p; p++; } else for(;i<n1;i++) { (*s2)[p].coef=(*s)[i].coef; (*s2)[p].e*p=(*s)[i].e*p; p++; } for(m=0;m<p;m++) { if((*s2)[m].coef<0) { if((*s2)[m].e*p==0)cout<<(*s2)[m].coef<<"+"; elsecout<<(*s2)[m].coef<<"**^"<<(*s2)[m].e*p<<"+"; } elseif((*s2)[m].coef>0) { if((*s2)[m].e*p==0)cout<<(*s2)[m].coef<<"+"; else//printf("%.2f**^%d+",d*s2[m].coef,d*s2[m].e*p); cout<<(*s2)[m].coef<<"**^"<<(*s2)[m].e*p<<"+"; } } cout<<"\b\b\n";}add函数在主函数中的调用：add(&po,&po1,&po2,n1,n2);4．调试分析〔1〕链接存储构造：设计过程，注意指针保护，如果一步不小心，容易造成头指针消失，所以需要指针来保护头指针，至于其他方面倒是没有什么问题。总的来说，代码长度170，算不上特别多，该有的功能也考虑到了。〔2〕顺序存储构造在设计过程中，发现如果不采用指针参数传递构造体数组，而是对单个多项式进展单个功能操作，即对于每一个多项式都会用同功能的函数，只不过不同名称来实现，这样造成代码冗长，我试过写出了286行的代码，但visualstudio2013无法编译如此冗长的代码，所以我决定使用指针导向进展优化，优化后的代码行数是162行，少了100多行，实现功能也比之前多了一些。虽然没法像我第一次写那286行的代码可以实现动态创立构造体数组，但我认为，这162行的代码的构造体数组50个大小，理应足够计算，如果要更大，建议修改代码中创立构造体数组大小的尺寸。总体来说，还算不错，知识经过一个寒假忘得七零八落，感觉我还没有完全掌握这类知识，等有时间重新将自己进展优化，也希望教师给予指导。5．用户使用说明〔1〕链接存储构造：按照提示一步步来即可；举例：请输入第一个多项式：请输入多项式的项数：3请输入第一项的系数：2请输入第一项的指数：2请输入第二项的系数：3请输入第二项的指数：5请输入第三项的系数：3请输入第三项的指数：1类似如上操作，到时大局部会在屏幕显示。〔2〕顺序存储构造按照提示一步步来即可；举例：请您输入第一个构造体数组的项数〔不超过50项〕：2请您输入第二个构造体数组的项数〔不超过50项〕：2现在是输入第一个多项式请输入第1项系数：2请输入第1项指数：2请输入第2项系数：3请输入第2项指数：3现在是输入第二个多项式：请输入第1项系数：3请输入第1项指数：3请输入第2项系数：4请输入第2项指数：4接着屏幕便会显示出来。6．测试结果〔1〕链接存储构造：〔2〕顺序存储构造7．附录〔1〕链接存储构造：#include<iostream>usingnamespacestd;structnode{ intcoef;//系数 inte*p;//指数 structnode*ne*t;//指针域}chainLink;//创立chainLink的node结点对象structnode*create()//定义建立多项式函数，并返回链表头指针{structnode*h=NULL,*q,*p;//定义构造体头指针h，标记指针p和q，p是创造新节点的标记指针，q是链接链表的指针；inti=1,N;//定义多项式的项数N及标记数i cout<<"请输入多项式的项数：\n"; cin>>N; p=0;//指针初始化；q=0;//本地指针初始化；for(;i<=N;i++) { p=(structnode*)malloc(sizeof(chainLink));//为一个新节点分配空间cout<<"请输入第"<<i<<"项的系数：\n"; cin>>(*p).coef; cout<<"请输入第"<<i<<"项的指数:\n"; cin>>(*p).e*p; if(i==1){h=p;q=p;}//建立头节点else { q->ne*t=p; q=p; } } q->ne*t=NULL;//p,q都成为新链表的尾指针；p->ne*t=NULL; returnh;}voiddisplay(structnode*h){ structnode*p;//定义标记指针，输出链表p=h; while(p!=NULL) { if(p->coef==0) { structnode*d; d=h; while(d->ne*t!=p) { d=d->ne*t; } d->ne*t=p->ne*t; p=p->ne*t;//删去系数为0的节点； }else { if(p->coef<0)//系数为负时应加上括号,让式子容易看清； {if(p->e*p==0)cout<<(*p).coef<<"+"; elsecout<<"("<<(*p).coef<<")"<<"**^"<<(*p).e*p<<"+"; } else { if(p->e*p==0)cout<<(*p).coef<<"+"; elseif(p->e*p!=0&&p->e*p!=1) { cout<<(*p).coef<<"**^"<<(*p).e*p<<"+"; } elsecout<<(*p).coef<<"**+"; } p=p->ne*t; } } cout<<"\b\b\n";}structnode*order(structnode*h)//定义排序函数，并返回整理后的链表的头指针{structnode*p,*q,*t,*h1,*h2;//定义三个构造体标记指针和两个头指针h1=h;//建立一个新的链表，头指针为h，指向原链表的第一个节点，之后将原链表中的节点一个一个的插入此链表，进展排序h2=h1->ne*t;//将原来的链表建立成待排序链表h1->ne*t=NULL;//截断第一个原链表中的节点while(h2!=NULL) { q=h1; p=q->ne*t; t=h2;//从待排序链表中选出一个节点准备插入到新链表中h2=h2->ne*t;//移动待排序链表的头指针，便于进展下一次挑选t->ne*t=NULL; if(t->e*p>q->e*p)//应插入头指针之前的情况 {t->ne*t=q; h1=t; continue; } if(p==NULL&&t->e*p<=q->e*p)q->ne*t=t;//应插入表尾的情况while(p!=NULL) { if(t->e*p>p->e*p) { q->ne*t=t; t->ne*t=p; break; } else { q=q->ne*t; p=p->ne*t; } } if(p==NULL)q->ne*t=t; } returnh1;//新链表即为按降幂顺序排好的链表，返回其头指针}structnode*add(structnode*h1,structnode*h2)//定义加法函数，并返回结果的链表的头指针{structnode*p,*q,*head,*r;//定义构造体头指针head和标记指针p,q,r p=h1; q=h2; head=(structnode*)malloc(sizeof(chainLink));//为结果多项式分配头指针if(p->e*p>=q->e*p){head=h1;p=p->ne*t;} else { if(p->e*p<q->e*p){head=h2;q=q->ne*t;} else{p->coef=p->coef+q->coef;head=p;p=p->ne*t;q=q->ne*t;} } r=head; while(p!=NULL&&q!=NULL) { if(p->e*p>q->e*p){r->ne*t=p;p=p->ne*t;} else { if(p->e*p<q->e*p){r->ne*t=q;q=q->ne*t;} else{p->coef=p->coef+q->coef;r->ne*t=p;p=p->ne*t;q=q->ne*t;} } r=r->ne*t; } if(p==NULL&&q==NULL)r->ne*t=NULL; else { if(p==NULL)r->ne*t=q; if(q==NULL)r->ne*t=p; } returnhead;}intmain(){ structnode*h1,*h2,*h3;//定义3个头指针；cout<<"\n请输入第一个多项式：\n"; h1=create();//创造第一个线性链表；cout<<"\n您输入的第一个多项式为：\n"; display(h1);//把多项式显示出来；h1=order(h1); cout<<"\n降幂排列后的第一个多项式为：\n"; display(h1); cout<<"\n"; cout<<"\n请输入第二个多项式：\n"; h2=create();//创造第二个线性链表；cout<<"\n您输入的第二个多项式为：\n"; display(h2);//把多项式显示出来；h2=order(h2); cout<<"\n降幂排列后的第二个多项式为：\n"; display(h2); cout<<"\n"; h3=add(h1,h2);//利用加函数将多项式相加；cout<<"\n第一个多项式和第二个多项式相加后：\n"; display(h3); system("pause"); return0;}〔2〕顺序存储构造#include<iostream>usingnamespacestd;structpoly{ floatcoef; inte*p;};//构造体数组定义voiddefStruct(structpoly*s[],intn){ inti=0; for(;i<n;i++) { cout<<"请输入第"<<i+1<<"项的系数：\n"; cin>>(*s)[i].coef; cout<<"请输入第"<<i+1<<"项的指数：\n"; cin>>(*s)[i].e*p; }//初始化顺序构造体数组}voidprint(structpoly*s[],intn){ for(inti=0;i<n;i++) { if(i==n-1)cout<<(*s)[i].coef<<"**^"<<(*s)[i].e*p; else cout<<(*s)[i].coef<<"**^"<<(*s)[i].e*p<<"+"; }}//输出数组voidsort(structpoly*s[],intn){ inti,temp1,j;//定义数组中的循环标记数据i与j，和整型标记temp1 floattemp2;//定义单精度型标记temp2 for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) { if((*s)[j].e*p>(*s)[i].e*p) { temp1=(*s)[j].e*p; (*s)[j].e*p=(*s)[i].e*p; (*s)[i].e*p=temp1; temp2=(*s)[j].coef; (*s)[j].coef=(*s)[i].coef; (*s)[i].coef=temp2; } } for(i=0;i<n-1;i++) { if((*s)[i].e*p==(*s)[i+1].e*p) { (*s)[i+1].coef=(*s)[i].coef+(*s)[i+1].coef; if(i==n-2) { (*s)[i].coef=(*s)[i+1].coef; (*s)[i+1].coef=0; } else { for(j=i;j<n;j++) { (*s)[j].coef=(*s)[j+1].coef; (*s)[j].e*p=(*s)[j+1].e*p; } (*s)[j].coef=0; i--; } } }}voidadd(structpoly*s[],structpoly*s1[],structpoly*s2[],intn1,intn2){ inti=0,j=0,p,m;//定义数组中的循环标记数据i,j,p,m for(p=0;;p++) { if((*s)[i].e*p==(*s1)[j].e*p) { (*s2)[p].coef=(*s)[i].coef+(*s1)[j].coef; (*s2)[p].e*p=(*s)[i].e*