数据结构实系数一元多项式运算实验报告解读数据结构实系数一元多项式运算实验报告解读PAGE/NUMPAGES数据结构实系数一元多项式运算实验报告解读实系数一元多项式问题实验报告2010级计算机科学与技术（非师范）100704033鲁静2011年10月14日星期五1、需求分析实现实系数一元多项式的创建，打印以及两个一元多项式的加、减、乘运算。（1）程序所能达到的功能：a．实现一元多项式的输入；．实现一元多项式的输出；．计算两个一元多项式的和并输出结果；d．计算两个一元多项式的差并输出结果；e．计算两个一元多项式的积并输出结果；（2）输入的形式和输入值的范围：输入要求：分行输入，每行输入一项，先输入多项式的指数，再输入多项式的系数，以00为结束标志，结束一个多项式的输入。输入形式：3-120120-21-33-1-100输入值的范围：系数为int型，指数为float型。（3）输出的形式：要求：第一行输出多项式1；第二行输出多项式2；第三行输出多项式1与多项式2相加的结果多项式；第四行输出多项式1与多项式2相减的结果多项式；第五行输出多项式1与多项式2相乘的结果多项式注：多项式的每一项形如：2.0x^3,注意指数应保留一位小数；多项式按照升幂次序排列；系数为1的非零次项应略去系数，系数为0的项不能出现在结果中；指数为0的项应只输出系数；多项式的第一项系数符号为正时，不要输出“+”，其他项要输出“+”，“-”符号。输出形式：3.0+2.0x^3-x^-1-2.0x-3.0x^3-x^-1+3.0-2.0x-x^3x^-1+3.0+2.0x+5.0x^3-3.0x^-1-6.0x-2.0x^2-9.0x^3-4.0x^4-6.0x^62、概要设计抽象数据类型一元多项式的定义如下：ADTPolynomial{数据对象：D={ai|aTermSeti∈TermSet,i=1,2,,m,m≥0中的每个元素包含一个
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示系数的实数和表示指数的整数}数据关系：R1={
|ai-1,ai∈D,且ai-1中的指数值＜ai中的基本操作：指数值，i=2,,n}sort(Polyn&h);//print(Polynh);//delZeroCoef(Polyn&h);//merge(Polyn&h);//createList();//对多项式进行排序输出多项式判断系数为零的情况合并指数相同的项创建多项式addPoly(Polynh1,Polynh2);//多项式相加subPoly(Polynh1,Polynh2);//多项式相减multPoly(Polynh1,Polynh2);//多项式相乘}ADTPolynomial多项式的抽象数据类型的定义：typedefstructPolynomial//结点类型{floatcoef;intexp;////系数指数structPolynomial*next;}PolyNode,*Polyn;主程序的流程图：开始输入两个多项式h1,h2判断h1,h2系数是否为0调用print()函数，输出，合并过并排好序的h1,h2调用addPoly(h1,h2)，合并并输出调用subPoly(h1,h2),合并并输出调用multPoly(h1,h2),合并并输出结束3、详细设计伪码算法：主函数：intmain(){Polynh1=createList();//创建多项式1Polynh2=createList();//创建多项式2print(h1);//输出多项式1print(h2);//输出多项式2addPoly(h1,h2);//实现多项式1和2的相加，并输出subPoly(h1,h2);//实现多项式1和2的相减，并输出multPoly(h1,h2);//实现多项式1和2的相乘，并输出return0;}分支函数：voidsort(Polyn&h);//voidprint(Polynh);//voiddelZeroCoef(Polyn&h);//排序输出多项式判断处理系数为0的情况voidmerge(Polyn&h);//PolyncreateList();//voidaddPoly(Polynh1,Polynh2);//voidsubPoly(Polynh1,Polynh2);//合并多项式创建多项式两个多项式相加并输出两个多项式相减并输出voidmultPoly(Polynh1,Polynh2);//两个多项式相乘并输出函数的调用关系：maincreateListprintaddPolysubPolymultPolymergemergeprintmergeprintmergeprintdelZeroCoefsort4、调试分析a．调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析:在输入诸如“0,3”，“2,0”时，程序无法正常运行或总是出错.解决：对指数或系数为0的情况应单独讨论。为此，建立了delZeroCoef函数来解决问题。b．算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想:时间复杂度和空间复杂度：设两个多项式分别用m,n来表示，T()表示时间复杂度，O()表示空间复杂度，那么：sort(Polyn&h)：T(m*m),T(n*n)；O(m),O(n)。print(Polynh)：T(m),T(n)；O(1),O(1)。delZeroCoef(Polyn&h)：T(m),T(n)；O(1),O(1)。merge(Polyn&h)：T(m*m),T(n*n)；O(1),O(1)。createList()：T(m),T(n)；O(1),O(1)。addPoly(Polynh1,Polynh2)：T(m),T(n)；O(1),O(1)。subPoly(Polynh1,Polynh2)：T(m),T(n)；O(1),O(1)。multPoly(Polynh1,Polynh2)：T(m),T(n)；O(1),O(1)。改进设想：可以在原来的基础上改进程序，或者设计一些新的算法，尽量减小时间复杂度和空间复杂度。c．经验和体会:这次用链表来解决问题让我的收获很大，对链表的构建更加熟练，对链表的向前推进把握的更加准确，在调试代码，检验的时候，曾遇到很大的阻碍，但解决问题后，自己也收获了很多。通过本次实验，我发现自己分析问题不是很全面，容易忽略一些细节，以后分析问题时要仔细考虑认真分析，避免细节上的错误。在设计该算法时，由于过于依赖书本上的例子，导致很多不必要的麻烦，例如在建立链表时头指针的设立导致了之后运用到相关的指针时没能很好的移动指针出现了数据重复输出或是输出系统缺省值，不能实现算法。5、测试数据与测试结果第一组数据：输入：425303356480输出：3.0x^2+2.0x^3+2.0x^4+x^57.0x^3+7.0x^4+6.0x^5+3.0x^6+4.0x^83.0x^2+9.0x^3+9.0x^4+7.0x^5+3.0x^6+4.0x^83.0x^2-5.0x^3-5.0x^4-5.0x^5-3.0x^6-4.0x^821.0x^5+35.0x^6+46.0x^7+42.0x^8+25.0x^9+24.0x^10+11.0x^11+8.0x^12+4.0x^13Pressanykeytocontinue第二组数据：输入：64321005670输出：4.0x+5.0x^2+3.0x^3+4.0x^62.0+3.0x^5+3.0x^6+4.0x^72.0+4.0x+5.0x^2+3.0x^3+3.0x^5+7.0x^6+4.0x^7-2.0+4.0x+5.0x^2+3.0x^3-3.0x^5+x^6-4.0x^78.0x+10.0x^2+6.0x^3+20.0x^6+27.0x^7+40.0x^8+29.0x^9+12.0x^10+12.0x^11+12.0x^12+16.0x^13Pressanykeytocontinue第三组数据：输入：-21-305-40-658-6-3400输出：7.0x^-4+2.0x^-3+3.0-2.0x+9.0x^55.0x^-6+9.0-3.0x^4-6.0x^55.0x^-6+7.0x^-4+2.0x^-3+12.0-2.0x-3.0x^4+3.0x^5-5.0x^-6+7.0x^-4+2.0x^-3-6.0-2.0x+3.0x^4+15.0x^535.0x^-10+10.0x^-9+15.0x^-6-10.0x^-5+63.0x^-4+18.0x^-3+45.0x^-1+6.0-66.0x-12.0x^2-9.0x^4+69.0x^5+12.0x^6-27.0x^9-54.0x^10Pressanykeytocontinue第四组数据：输入：-9-78-2-483-100-3-430-50输出：3.0x^-9-2.0x^-4-1.02.0x^-3+1.0-4.0x^33.0x^-9-2.0x^-4+2.0x^-3-4.0x^33.0x^-9-2.0x^-4-2.0x^-3-2.0+4.0x^36.0x^-12+3.0x^-9-4.0x^-7-12.0x^-6-2.0x^-4-2.0x^-3+8.0x^-1-1.0+4.0x^3Pressanykeytocontinue第五组数据：输入：-1-110-1-1-10输出：x^-1-x0x^-1-xx^-1-x0Pressanykeytocontinue
浙公网安备 33021202002483