数据结构实系数一元多项式运算实验报告解读

实系数一元多项式问题实验报告2010级计算机科学与技术（非师范）100704033鲁静2011年10月14日星期五1、需求分析实现实系数一元多项式的创建，打印以及两个一元多项式的加、减、乘运算。1）程序所能达到的功能：a．实现一元多项式的输入；b．实现一元多项式的输出；c．计算两个一元多项式的和并输出结果；d．计算两个一元多项式的差并输出结果；e．计算两个一元多项式的积并输出结果；a．实现一元多项式的输入；b．实现一元多项式的输出；c．计算两个一元多项式的和并输出结果；d．计算两个一元多项式的差并输出结果；e．计算两个一元多项式的积并输出结果；2）输入的形式和输入值的范围：输入要求：分行输入，每行输入一项，先输入多项式的指数，再输入多项式的系数，以00为结束标志，结束一个多项式的输入。输入形式：-12-21-33-1-100输入值的范围：系数为int型，指数为float型。（3）输出的形式：要求：第一行输出多项式1；第二行输出多项式2；第三行输出多项式1与多项式2相加的结果多项式；第四行输出多项式1与多项式2相减的结果多项式；第五行输出多项式1与多项式2相乘的结果多项式注：多项式的每一项形如：2.0x"，注意指数应保留一位小数;多项式按照升幂次序排列；系数为1的非零次项应略去系数，系数为0的项不能出现在结果中；指数为0的项应只输出系数；多项式的第一项系数符号为正时，不要输出“+”，其他项要输出“+”，“-”符号。输出形式：3.0+2.0X八3-x-1-2.0x-3.0x3

_xT+3.0-2.0x-x3x八T+3.0+2.0x+5.0x八3-3.0x八T-6.0x-2.0x八2-9.0X八3-4.0X八4-6.0X八62、概要设计抽象数据类型一元多项式的定义如下：ADTPolynomial｛数据对象：D二｛a|aGTermSet,i=l,2,…，TermSet"中的每个元素包含一个表示系数的实数和表示指数的整数｝数据关系：R1={<a,a>|数据关系：R1={<a,a>|a,i-1i i-1指数值，i=2,…,n}基本操作：sort(Polyn&h);print(Polynh);aGD,且a中的指数值Va中的i i-1 i//对多项式进行排序//输出多项式delZeroCoef(Polyn&delZeroCoef(Polyn&h);//判断系数为零的情况merge(Polyn&merge(Polyn&h);//合并指数相同的项createList();//创建多项式createList();//创建多项式//多项式相加//多项式相减//多项式相加//多项式相减//多项式相乘subPoly(Polynh1,Polynh2);multPoly(Polynh1,Polynh2);}ADTPolynomial多项式的抽象数据类型的定义：主程序的流程图主程序的流程图typedefstructPolynomial{floatcoef;intexp;structPolynomial*next;}PolyNode,*Polyn;//结点类型//系数//指数输入两个多项式hl,h2判断h1,h2系数是否为0

3、详细设计伪码算法：主函数：intmain(){;//创建多项式1;//创建多项式1;//创建多项式2//输出多项式1//输出多项式2//实现多项式1和2的相加，并输出//实现多项式1和2的相减，并输出//实现多项式1和2的相乘，并输出Polynh2=createList()print(h1);print(h2);addPoly(h1,h2);subPoly(h1,h2);multPoly(h1,h2);return0;}分支函数：voidsort(Polyn&h); //排序voidprint(Polynh); //输出多项式voiddelZeroCoef(Polyn&h);//判断处理系数为0的情况voidmerge(Polyn&h); //合并多项式PolyncreateList(); //创建多项式voidaddPoly(Polynhl,Polynh2);//两个多项式相加并输出voidsubPoly(Polynhl,Polynh2);//两个多项式相减并输出voidmultPoly(Polynh1,Polynh2);//两个多项式相乘并输出函数的调用关系：4、调试分析a.调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析:在输入诸如“0,3”，“2,0”时，程序无法正常运行或总是出错.解决：对指数或系数为0的情况应单独讨论。为此，建立了delZeroCoef函数来解决问题。b・算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想:时间复杂度和空间复杂度：设两个多项式分别用m,n来表示，T()表示时间复杂度，0()表示空间复杂度，那么：sort(Polyn&h)：T(m*m),T(n*n)；0(m),0(n)。print(Polynh)：T(m),T(n)；0(1),0(1)。delZeroCoef(Polyn&h)：T(m),T(n)；0(1),0(1)。merge(Polyn&h)：T(m*m),T(n*n)；0(1),0(1)。createList()：T(m),T(n)；0(1),0(1)。addPoly(Polynh1,Polynh2)：T(m),T(n)；0(1),0(1)。subPoly(Polynh1,Polynh2)：T(m),T(n)；0(1),0(1)。multPoly(Polynh1,Polynh2)：T(m),T(n)；0(1),0(1)。改进设想：可以在原来的基础上改进程序，或者设计一些新的算法，尽量减小时间复杂度和空间复杂度。c・经验和体会：这次用链表来解决问题让我的收获很大，对链表的构建更加熟练，对链表的向前推进把握的更加准确，在调试代码，检验的时候，曾遇到很大的阻碍，但解决问题后，自己也收获了很多。通过本次实验，我发现自己分析问题不是很全面，容易忽略一些细节，以后分析问题时要仔细考虑认真分析，避免细节上的错误。在设计该算法时，由于过于依赖书本上的例子，导致很多不必要的麻烦，例如在建立链表时头指针的设立导致了之后运用到相关的指针时没能很好的移动指针出现了数据重复输出或是输出系统缺省值，不能实现算法。5、测试数据与测试结果第一组数据：输入：42530033564800输出：3.0x“2+2.0x"3+2.0x“4+x“57.0x“3+7.0x"4+6.0x“5+3.0x飞+4.0x"83.0x“2+9.0x"3+9.0x“4+7.0x“5+3.0x飞+4.0x"83.0x“2—5.0x"3—5.0x“4—5.0x“5—3.0x飞—4.0x"821.0x“5+35.0x飞+46.0x“7+42.0x"8+25.0x"9+24.0x"10+11.0x"ll+8.0x"12+4.0x"13Pressanykeytocontinue第二组数据输入：604321000536700输出：4.0x+5.0x"2+3.0x“3+4.0x飞2.0+3.0x“5+3.0x飞+4.0x“72.0+4.0x+5.0x"2+3.0x“3+3.0x“5+7.0x飞+4.0x“7—2.0+4.0x+5.0x“2+3.0x“3—3.0x“5+x飞—4.0x“78.0x+10.0x“2+6.0x“3+20.0x飞+27.0x“7+40.0x"8+29.0x”9+12.0x"10+12.0x"ll+12.0x「2+16.0x「3Pressanykeytocontinue第三组数据：输入：—21—30957—400—6508—6—349000输出：7.0x-4+2.0x-3+3.0-2.0x+9.0x55.0x—6+9.0—3.0x4—6.0x55.0x—6+7.0x—4+2.0x—3+12.0—2.0x—3.0x4+3.0x5—5.0x—6+7.0x—4+2.0x—3—6.0—2.0x+3.0x4+15.0x535.0x—10+10.0x—9+15.0x—6—10.0x—5+63.0x—4+18.0x—3+45.0x—1+6.0—66.0xT2.0x2—9.0x4+69.0x5+12.0x6—27.0x9—54.0x10Pressanykeytocontinue第四组数据：输入：3-9-78-2-47803-10002-3-43100-500输出：3.0x"-9-2.0x"-4-1.02.0x-3+1.0-4.0x33.0x“-9-2.0x“-4+2.0x"-3-4.0x“33.0x-9-2.