豆丁数据结构实系数一元多项式运算实验报告.doc
实系数一元多项式问题实验报告2021级计算机科学与技术非师范100704033鲁静2021年10月14日星期五1、需求分析实现实系数一元多项式的创立，打印以及两个一元多项式的加、减、乘运算。1程序所能到达的功能： a实现一元多项式的输入； b实现一元多项式的输出； c计算两个一元多项式的和并输出结果；d计算两个一元多项式的差并输出结果；e计算两个一元多项式的积并输出结果；2输入的形式和输入值的范围：输入要求：分行输入，每行输入一项，先输入多项式的指数，再输入多项式的系数，以0 0为结束标志，结束一个多项式的输入。输入形式：2 3-1 23 01 20 0-2 1-3 3-1 -10 0输入值的范围：系数为int型，指数为float型。3输出的形式：要求：第一行输出多项式1； 第二行输出多项式2；第三行输出多项式1与多项式2相加的结果多项式；第四行输出多项式1与多项式2相减的结果多项式；第五行输出多项式1与多项式2相乘的结果多项式注： 多项式的每一项形如：2.0x3,注意指数应保存一位小数；多项式按照升幂次序排列； 系数为1的非零次项应略去系数，系数为0的项不能出现在结果中； 指数为0的项应只输出系数； 多项式的第一项系数符号为正时，不要输出“+，其他项要输出“+，“-符号。输出形式：3.0+2.0x3-x-1-2.0x-3.0x3-x-1+3.0-2.0x-x3x-1+3.0+2.0x+5.0x3-3.0x-1-6.0x-2.0x2-9.0x3-4.0x4-6.0x62、概要设计抽象数据类型一元多项式的定义如下：ADT Polynomial 数据对象：D=ai| ai TermSet,i=1,2,m,m0TermSet 中的每个元素包含一个表示系数的实数和表示指数的整数 数据关系：R1=< ai-1,ai >| ai-1 , ai D,且ai-1 中的指数值ai 中的指数值，i=2,n 根本操作：sort(Polyn & h); /对多项式进行排序print(Polyn h); /输出多项式delZeroCoef(Polyn & h); /判断系数为零的情况merge(Polyn & h); /合并指数相同的项createList(); /创立多项式addPoly(Polyn h1,Polyn h2); /多项式相加subPoly(Polyn h1,Polyn h2); /多项式相减multPoly(Polyn h1,Polyn h2); /多项式相乘 ADT Polynomial多项式的抽象数据类型的定义： typedef struct Polynomial /结点类型float coef; /系数int exp; /指数struct Polynomial * next;PolyNode,*Polyn;判断h1,h2系数是否为0输入两个多项式h1,h2开始主程序的流程图：调用multPoly(h1,h2),合并并输出调用subPoly(h1,h2),合并并输出调用addPoly(h1,h2)，合并并输出结束调用print()函数，输出，合并过并排好序的h1,h23、详细设计伪码算法： 主函数： int main() Polyn h1=createList();/创立多项式1 Polyn h2=createList();/创立多项式2 print(h1); /输出多项式1 print(h2); /输出多项式2 addPoly(h1,h2); /实现多项式1和2的相加，并输出 subPoly(h1,h2); /实现多项式1和2的相减，并输出 multPoly(h1,h2); /实现多项式1和2的相乘，并输出 return 0; 分支函数： void sort(Polyn & h); /排序 void print(Polyn h); /输出多项式 void delZeroCoef(Polyn & h);/判断处理系数为0的情况 void merge(Polyn & h); /合并多项式 Polyn createList(); /创立多项式 void addPoly(Polyn h1,Polyn h2);/两个多项式相加并输出 void subPoly(Polyn h1,Polyn h2);/两个多项式相减并输出 void multPoly(Polyn h1,Polyn h2);/两个多项式相乘并输出函数的调用关系：mainmultPolycreateListsubPolyprintaddPolyprintmergeprintmergeprintmergemergesortdelZeroCoef4、 调试分析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(Polyn h)：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(Polyn h1,Polyn h2)：T(m),T(n)；O(1),O(1)。 subPoly(Polyn h1,Polyn h2)：T(m),T(n)；O(1),O(1)。 multPoly(Polyn h1,Polyn h2)：T(m),T(n)；O(1),O(1)。 改良设想： 可以在原来的根底上改良程序，或者设计一些新的算法，尽量减小时间复杂度和空间复杂度。c经验和体会: 1.这次用链表来解决问题让我的收获很大，对链表的构建更加熟练，对链表的向前推进把握的更加准确，在调试代码，检验的时候，曾遇到很大的阻碍，但解决问题后，自己也收获了很多。 2.通过本次实验，我发现自己分析问题不是很全面，容易忽略一些细节，以后分析问题时要仔细考虑认真分析，防止细节上的错误。 3.在设计该算法时，由于过于依赖书本上的例子，导致很多不必要的麻烦，例如在建立链表时头指针的设立导致了之后运用到相关的指针时没能很好的移动指针出现了数据重复输出或是输出系统缺省值，不能实现算法。5、 测试数据与测试结果第一组数据：输入：2 43 21 52 30 05 32 36 53 67 44 80 0输出：3.0x2+2.0x3+2.0x4+x57.0x3+7.0x4+6.0x5+3.0x6+4.0x83.0x2+9.0x3+9.0x4+7.0x5+3.0x6+4.0x83.0x2-5.0x3-5.0x4-5.0x5-3.0x6-4.0x821.0x5+35.0x6+46.0x7+42.0x8+25.0x9+24.0x10+11.0x11+8.0x12+4.0x13Press any key to continue第二组数据：输入：4 60 43 35 24 10 02 03 53 64 70 0输出：4.0x+5.0x2+3.0x3+4.0x62.0+3.0x5+3.0x6+4.0x72.0+4.0x+5.0x2+3.0x3+3.0x5+7.0x6+4.0x7-2.0+4.0x+5.0x2+3.0x3-3.0x5+x6-4.0x78.0x+10.0x2+6.0x3+20.0x6+27.0x7+40.0x8+29.0x9+12.0x10+12.0x11+12.0x12+16.0x13Press any key to continue第三组数据：输入：-2 12 -33 09 57 -40 0-6 50 85 -6-3 49 00 0输出：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.0x-12.0x2-9.0x4+69.0x5+12.0x6-27.0x9-54.0x10Press any key to continue第四组数据：输入：3 -9-7 8-2 -47 80 3-1 00 02 -3-4 31 00 -50 0输出：3.0x-9-2.0x-4-1.02.0x-3+1.0-4.0x33.0x-9-2.0x-4+2.0x-3-4.0x33.0x-9-2.0x-4-2.0x-3-2.0+4.0x36.0x-12+3.0x-9-4.0x-7-12.0x-6-2.0x-4-2.0x-3+8.0x-1-1.0+4.0x3Press any key to continue第五组数据：输入：1 -1-1 10 01 -1-1 -10 0输出：x-1-x0x-1-xx-1-x0Press any key to continue
