搜索
北京邮电大学信息与通信工程学院第1页数据结构实验报告实验名称：实验一——多项式的实现学生姓名：班级：班内序号：学号：日期：2011年10月29日1．实验要求实验目的：1.熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法2.学习指针、模板类、异常处理的使用3.掌握线性表的操作的实现方法4.学习使用线性表解决实际问题的能力实验内容：利用线性表实现一个一元多项式Polynomialf(x)=a0+a1x+a2x2+a3x3+…+anxn要求：1．能够实现一元多项式的输入和输出2．能够进行一元多项式相加3．能够进行一元多项式相减4．能够计算一元多项式在x处的值5．能够计算一元多项式的导数（选作）6．能够进行一元多项式相乘（选作）7．编写测试main()函数测试线性表的正确性2.程序分析由于多项式是线性结构，故选择线性表来实现，在这个程序中我采用的是单链表结构，每个结点代表一个项，多项式的每一项可以用其系数和指数唯一的表示。如果采用顺序存储，那么对于结点的插入和删除的操作会比较麻烦，而且顺序表的结点个数固定，对于可能发生的情况无法很好的处理，而采用链表就会简单许多，还能自由控制链表的长度。两个多项式要进行多次的计算，为了保护原始的数据，方便进行以后的计算，故选择把结果存储在一个新建的链表里。本程序完成的主要功能：1.输入和输出：需要输入的信息有多项式的项数，用来向系统动态申请内存；多项式北京邮电大学信息与通信工程学院第2页各项的系数和指数，用来构造每个结点，形成链表。输出即是将多项式的内容向屏幕输出。2.多项式相加与相减：多项式的加减要指数相同即是同类项才能实现，所以在运算时要注意判断指数出现的各种不同的情况，分别写出计算方法。将每项运算得到的结果都插入到新的链表中，形成结果多项式。3.多项式的求导运算：多项式的求导根据数学知识，就是将每项的系数乘以指数，将指数减1即可，将每项得到的结果插入到结果多项式的链表中。4.多项式在某点的值：由用户输入x的值，然后求出每项的值相加即可。2.1存储结构本程序采用的存储结构是单链表结构，其定义的结点包括三部分：系数、指数以及下一个结点的地址。示意图如下：2.2关键算法分析1.输入多项式·自然语言描述：1.设置多项式的项数n；2.按照多项式的项数申请动态数组coef[]和expn[]存储多项式的系数和指数；3.按照指数递增的次序输入各项的系数以及指数，分别存入coef和expn；4.再将输入的系数以及指数赋给每一个结点的coef和expn域；5.利用头插法将每个结点加入链表。·伪代码：1.输入项数n；2.float*coef1=newfloat[n1];int*expn1=newint[n1];3.运用for循环，循环n次3.1term*s=newterm;3.2s-coef=coef[i];3.3s-expn=expn[i];3.4r-next=s;3.5r=s;4.运用头插法将结点插入链表。时间复杂度：空间复杂度：2.输出多项式·自然语言描述：1.获取头结点；2.循环n-1次（n为多项式的项数）2.1将指针的指向后移；2.2依照多项式的各种情况，设置输出方式2.2.1系数为1且指数不为1和0，输出x^expn+；2.2.2系数不为0且指数为0，输出（coef）+；2.2.3系数不为0且指数为1，输出（coef）x+；nextcoef1expn1nextcoef1expn1nextcoef1expn1next……北京邮电大学信息与通信工程学院第3页2.2.4系数不为0和1，指数不为0和1，输出(coef)x^(expn)+；3.将指针指向移到最后一个节点。重复2.2中判断，但不输出+号。·伪代码描述：1.term*m=front;2.for(inti=0;in-1;i++)2.1m=m-next;2.2if(m-coef==1&&(m-expn!=1&&m-expn!=0))coutx^m-expn+;2.3elseif(m-coef==1&&m-expn==0)coutm-coef+;2.4elseif(m-coef!=1&&m-expn==0)coutm-coef+;2.5elseif(m-coef!=0&&m-expn==1)coutm-coefx+;2.6elseif(m-coef==1&&m-expn==1)coutx+;2.7elseif(m-coef==0)cout+;2.8elsecoutm-coefx^m-expn+;3.m=m-next;3.1if(m-coef==1&&(m-expn!=1&&m-expn!=0))coutx^m-expn;3.2elseif(m-coef==1&&m-expn==0)coutm-coef;3.3elseif(m-coef!=1&&m-expn==0)coutm-coef;3.4elseif(m-coef!=1&&m-expn==1)coutm-coefx;3.5elseif(m-coef==1&&m-expn==1)coutx;3.6elseif(m-coef==0)cout;3.7elsecoutm-coefx^m-expn;时间复杂度：O(n)空间复杂度：S(1)3.多项式的相加相减·自然语言描述：1.指针p和q分别指向a和b两个多项式的头结点的下一个节点；2.将结果多项式的项数置为0；3.只有p或q非空，进行以下循环：3.1申请一个term*型的指针d，将其next域赋为NULL；进行判断：3.3.1如果p和q均非空北京邮电大学信息与通信工程学院第4页3.3.3.1如果p和q的指数相等将d的系数赋为p、q系数之和，指数不变，将p、q指向后移；3.3.3.2如果p-expnq-expn复制q到结果多项式（减法系数为q-coef的相反数）3.3.3.3如果p-expnq-expn复制p到结果多项式3.3.3.4判断后将项数++，插入新节点d；3.3.2如果q为空，p仍存在，逐项将p复制到结果多项式。每进行一次，项数++，p后移。3.3.3如果p为空，q仍存在，逐项将q复制到结果多项式（减法将系数变为原来的相反数）。每进行一次，项数++，q后移。3.2返回结果多项式的项数·伪代码描述：1.工作指针p、q初始化：term*p=front-next;term*q=b.front-next;2.intnAdd=0;//加法intnMinus=0;//减法3.while(p||q)3.1term*d=newterm;d-next=NULL;3.3.1if(p&&q)3.3.3.1if(p-expn==q-expn)d-coef=p-coef+q-coef;d-expn=p-expn;p=p-next;q=q-next;//加法d-coef=p-coef-q-coef;d-expn=p-expn;p=p-next;q=q-next;//减法3.3.3.2p-expnq-expnd-coef=q-coef;d-expn=q-expn;q=q-next;//加法d-coef=-q-coef;d-expn=q-expn;q=q-next;//减法3.3.3.3p-expnq-expnd-coef=p-coef;d-expn=p-expn;p=p-next;//加法d-coef=p-coef;d-expn=p-expn;p=p-next;//减法3.3.3.4nAdd++;add.Insert(d);//加法nMinus++;min.Insert(d);//减法3.3.2while(p)term*d=newterm;d-coef=p-coef;d-expn=p-expn;d-next=NULL;nAdd++;add.Insert(d);p=p-next;//加法term*d=newterm;d-coef=(p-coef);d-expn=p-expn;d-next=NULL;nMinus++;min.Insert(d);p=p-next;//减法3.3.3while(q)北京邮电大学信息与通信工程学院第5页term*d=newterm;d-coef=q-coef;d-expn=q-expn;d-next=NULL;nAdd++;add.Insert(d);q=q-next;//加法term*d=newterm;d-coef=0-(q-coef);d-expn=q-expn;d-next=NULL;nMinus++;min.Insert(d);q=q-next;//减法3.2returnnAdd;returnnMinus;时间复杂度：O(n)空间复杂度：O(2)4.求值·自然语言描述：1.将工作指针指向多项式的第一项；2.将结果result置为0；3.指针不为空，即进行循环：3.1result+=s-coef*(pow(x,s-expn));3.2s=s-next;4．返回result；·伪代码描述：1.term*s=front-next;2.floatresult=0;3.while(s)3.1result+=s-coef*(pow(x,s-expn));3.2s=s-next;4.returnresult;时间复杂度：O(n)空间复杂度：S(1)5.求导数·自然语言描述：1.将指针指到多项式的第一项的结点：term*p=a.front-next;2.循环n次2.1每项求导的系数为：p-coef*p-expn;指数为：p-expn-1;2.2将新结点插入新链表；2.3指针p后移。·伪代码描述：1.term*p=a.front-next;2.for(inti=0;in;i++)2.1term*s=newterm;2.2if(p-expn)2.2.1s-coef=(p-coef)*(p-expn);2.2.2s-expn=p-expn-1;2.2.3p=p-next;2.2.4de.Insert(s);2.3else北京邮电大学信息与通信工程学院第6页2.3.1s-coef=0;2.3.2s-expn=0;2.3.3p=p-next;2.3.4de.Insert(s);时间复杂度：O(n)空间复杂度：S(1)3.程序运行结果1.测试主函数流程：开始设置多项式A的项数设置多项式B的项数按照A的项数动态申请coef1[]和expn1[]按照B的项数动态申请coef2和expn2[]输出A输出B进行A-B的运算进行A+B的运算输出相减的结果minus输出相加的结果add11进行对A求导数的运算输出求导的结果de输入x的取值计算A在x处的取值并输出结束北京邮电大学信息与通信工程学院第7页测试条件：问题规模n的数量级为1A多项式每项的系数和指数分别为：1,02,13,2B多项式每项的系数和指数分别为：2,22,34,5X的值为：2运行出来的结果是：测试结论：通过测试，本程序具有的功能有：多项式的建立、多项式的输入与输出、多项式的相加及相减，多项式求导以及多项式求值。4.总结1.调试时出现的问题及解决的方法①输出多项式的时候有些问题，但经过查看是由于输出时没有将各种情况考虑全面的结果。②相加相减操作：在刚开始的时候，只考虑了p、q指针均非空的情况，计算的结果就出现了问题，但逐项的运算后，会出现一个还非空但另一个已经遍历完毕的情况，故后又设计让非空的链表继续进行运算，解决了问题。③在插入结点的时候出现了一些问题，经查看是尾插法运用地并不熟练，后运用头插法将结点插入链表中，编完程序后，又仔细学习了尾插法的操作。2.心得体会通过