一元多项式运算的实现

　　自公元前两千年多年前，巴比伦人知道如何求解二次方程为开端。随着数学的发展，数学家的不断研究，新理论的创立，对多项式的研究不断深入，发展至今多项式理论现在已成为一个完善、成熟的研究领域，其理论影响到数学的各个分支，对其他学科也产生了影响。在信息与网络的时代，计算机成为了时代的标志之一，与此同时，计算机程序设计思想和其语言在时代的潮流里飞速发展。为了更好地进行科学研究，要求数据能够进行快速的运算，用计算机去使得计算速度提高就成为了必然，在此种情况下，数学的基础运算之一即一元多项式的运算成为了人们提高计算机运行速度的破解点之一，使得国内外的专家学者对它进行了深入的研究。

　　在数学领域之中，以往庞大的运算需要许多数学家通力合作奋战几天乃至数个月，但是计算机的出现使这种情况成为了历史。人们从庞大的数据计算量中解脱了出来。这就极大的促进了各个以数学为基础的学科的发展。在此基础上，为了更好地促进其他学科的发展，数学运算就必须提高速度，因此多项式在计算机上的运算和应用成为了一些数学家的研究课题。一元多项式运算的实现是多项式在计算机运算的基础，如果一元多项式在计算机上不能准确而快速实现运算，那么多项式的运算也会出现问题，影响其他学科的研究。

　　以一元多项式的运算为基础的学科大多是工程应用的领域，这些领域对社会的发展有极大的促进作用。一元多项式运算对于大型的数据处理中心必不可少，处理数据中心那庞大的数据量，就要求这个过程必须快速且准确。，一旦出错，想要使数据恢复过来需要花费大量的时间和精力，这势必会引起较大的经济损失，影响发展。

　　一元多项式运算对于科学研究来说至关重要，在物理学研究中离不开他的身影，可以说物理学是在多项式运算的基础上建立起来的，所以一元多项式运算在计算机上的实现在物理学研究计算过程中占据了很大比例，犯一点小小的错误可能使得整个实验前功尽弃；在代数领域中，数学家的主要研究方向之一就是多项式，而这些多项式经常被应用到其他领域，在这些领域中基于多项式作出各种系统软件去解决问题，在这个过程中一元多项式运算的实现成为在实现这些目标时的不可避免步骤。所以说，一元多项式运算的实现对于科学研究是基础，需要一元多项式运算在计算机上的实现。而一元多项式运算在计算机上的实现，可以帮助发展高新科技，加快各项研究的进度。

　　对于在校的计算机专业的学生来说，链表作为计算机的基础之一，在学习过程中，链表成为了计算机基础的考核点之一，这就对学生提出了更高的要求。为了能够达到这一要求，学生们需要对它能够熟练掌握并加以运用。此时一元多项式运算的实现就可以作为学生的练习题，帮助加深学生加深对链表的了解和提高使用链表的能力。

　　总而言之，一元多项式运算的实现对社会具有重要意义，尤其在科学研究和工程应用方面，可以帮助社会生产和发展，影响深远。

　　在进入信息时代后，一元多项式运算通过计算机实现得到了长足的发展，已经的到了相关领域学者的重视。在倾向不同程序设计思想，数学方法，编程语言的侧重点下，也形成了一系列的研究成果。就这一论题而言，国内早有多个学者对这一命题阐述了自己的见解。

　　郑勇林首先研究了一元多项式在数学领域中的表现形式和运算方式，深入的了解了一元多项式的数学逻辑,在此基础上对在计算机领域一元多项式的存储方式进行了研究，为一元多项式设计了一种存储结构。采用牛顿迭代法提出了多项式数值求根的算法，在此基础上构建了一元多项式运算源程序，该程序只包含了多项式运算的加法和乘法。

　　章明以数学上多项式的表示形式和乘法运算法则为出发点，设计了一种可以用于多项式乘法的数据结构类型。这种结构类型提出的目的就是为了减少算法的时间复杂度和空间复杂度，提升算法的效率。为了验证这一数据结构类型，对多项式的乘法进行了改进，为其设计算法，提出总体架构，分享了其部分核心源代码，使人们对这一研究有了一定的了解。

　　陈晓霞认为数据结构中对一元多项式运算的算法描写比较笼统,不够清晰直观,学生在学习中存在一些问题,教学效果相对较差。她为了学生更好地学习与理解，提出了在图形化用户界面之上用一种更加清晰直观地方式去实现一元多项式的运算。戴祯杰、农正、周永权为了实现多项式运算的求解，设计了一种新模型,这种新模型是基于多项式泛函网络运算的。为了验证新提出的这一算法，求解线性方程组的可以完成对网络参数的计算，实现对其的利用。通过实验证明，该方法相比传统方法有了极大的改进，在获得问题的精确解的基础上，与此同时还可以获得问题的近似解。

　　鄢盛丰、刘建波、董安葳、王琳研究认为多项式在数学里是一种最基本的表示形式,在理论和工程上有极为广泛的应用,做好多项式的运算,对实际应用有很大作用.他们提出了一种新的多项式存储结构,即系数指数数组存储法.文中对多项式的三种运算的算法在理论方面进行了推导与部分证明,最后用系数指数数组存储法给予程序实现。

　　唐骏研究认为一元多次方程简单而又实用,在工程领域中及数学求解中它都因其使用价值而占有重要地位。,他们在前人的基础上通过研究,设计了一中新的求解思路和求解方法。这种求解思路和求解方法首先要考虑到的便是其有效性，若新方法无效，则就没有研究的必要，其次便是其实用性，若新方法本身的实用性不高，则仅仅只可以在某些研究领域中得到应用，无法大规模应用则也就只是为后人提供了一些经验罢了，这就需要计算机对其两方面的能力进行验证。最后，用此方法去尝试求解虚根，对其进行一些探索。

　　张绍兵、季厌浮为了实现一元多项式加法运算他们使用单链表这一方法去研究说明并加以实现，在此过程中，涉及到了许多方面的知识，也详细描述了一元多项式在计算机中的表示。

　　徐连龙、李玲为了实现一元多项式的乘法运算对前人的方法进行总结和改进，在此基础上设计了一个程序。该程序是根据多项式的数学模型，进行数据结构的构造，对此程序进行可行性研究，分析讨论需要创建的程序主要功能模块，时期能够顺利编译，实现构建该程序的目的。在此过程中大量使用算法，在实现程序时占有重要作用，函数是构成程序的基本元素之一，有了函数后，才可以根据算法思想进行程序的编写。程序中运用的函数成为了算法思想的体现。

　　在进行了大量的文献阅读后可知，国内外学者对一元多项式运算的实现的研究整体上已经取得了极大的进展。他们通过不同的研究角度对一元多项式运算的实现进行研究，主要倾向于数学角度和数据结构的角度，研究对象主要是多项式。但是这些研究没有从总的方面对一元多项式的运算进行总结，其大多数对一元多项式运算的实现更多的是倾向于数学方法的改进，对于存储结构的改进，很少讨论其他方向的研究与改进。根据现有的情况，需要增强对一元多项式运算的实现的研究，有助于深入学习计算机。

　　本文就一元多项式的研究而言主要有以下几部分构成，从不同的角度研究了一元多项式。

　　首先就一元多项式在数学领域之中对它的定义与运算方法进行了说明分析，构建了一元多项式的数学模型；其次论述了一元多项式运算在计算机中的表示方式和存储形式；接着围绕一元多项式运算在计算机中得以实现的算法思想进行详细描画；然后展现了一元多项式运算的实现所进行的程序设计，由界面设计，加法，减法和乘法的设计构成；最后是结语，就该问题提出了做了一个总结，个人在研究中还未解决的问题，提出个人的看法与见解。

　　在这项研究中，使用文献研究法通过图书馆、互联网、电子资源数据库等查阅了大量的文献资料，明确了一元多项式在数学领域中的运算法则，基于这样去理解一元多项式在计算机上的实现方法，理清了一元多项式运算的发展脉络及研究现状，学习计算机编程语言的相关知识。通过这些方式获取大量的多项式运算等相关研究信息，为设计实现一元多项式运算提供了思路和参考。

　　为实现一元多项式的运算采用实验研究法通过设计数据存储方式，选取合适的算法设计思想和编程语言，完善思路，完成实验设计。为追求运算的速度，需要采取比较分析法，对几次实验的程序作出比较，进行运算速度的分析，检测出其中有问题的部分，选取最适合的一个，进行优化，从而使程序尽可能达到最优的存在。

　　在数学上,一个一元多项式（x）可以按照x的指数大小，从小到大依次排列，按照这一顺序写成：

　　（x）=

　　它由n+1个系数构成，且这些系数具有唯一确定性。因此，一元多项式的系数可以用以下方式表示，即线性表P,

　　P=（）

　　多项式的每一项的指数i都隐藏在其相对应的系数的序号里。

　　但是n不确定，在进行一元多项式的运算的时候会出现一种情况，即一元多项式的指数变得异常庞大，使一元多项式使用线性表进行顺序存储时，根据指数的大小，存储长度会发生相应的变化。当指数足够大时，为了使多项式能够被顺利存储，则需要与指数大小相同的存储空间，这会使得在存储空间变得异常庞大。所以，当进行多项式的运算时，因指数的大小无法确定，存储空间的大小也无法确定。因此，在计算过程中就会因为在线性表中存在着系数为零的情况，这时还需要对系数为零的项留下存储空间这一关系存在着一顶存储空间浪费的情况。为了避免存储空间的浪费，需要对多项式的表示方式作出一定的改进，将系数为0的项存储空间删去，只存储系数非零的项。

　　一般情况下，一元多项式可以写成下面的式子：

　　其中，是多项式中指数为的项的非零系数，并且满足这一条件，即：

　　假如设计一个线性表，在这个线性表中每个元素都与多项式一一对应。多项式的系数和其对应的指数都可以在线性表中的元素中找到，则可以表示为

　　（（）,（）,,（））

　　多项式便可以由此唯一确定。即使在最坏的情况下，n+1个系数项中每一个系数项的系数都不为零，则这个多项式在链中的表示也仅仅就是将n+1个系数和指数分别存在链表中，此时占据的空间也就是在线性表中占据的空间的二倍。但是相比较而言，存在按照指数的大小每一项都存在的多项式仅仅是少数的，这样零系数项在进行存储就可以节约大量的存储空间。

　　一元多项式在计算机中的存储方式有许多种，但在本文中根据一元多项式的表示一般使用链表来进行存储，这样相比较系数为零的项在多项式的总体中占有的比重，只存储系数非零的项，就可以节约大量的存储空间，避免浪费。为了实现减少存储空间的目的，使用链表存储过程中将多项式的系数，指数，和连接结点的指针分别存放在链表的三个数据域之中。根据这一原理可以将一元多项式的存储方式展现出来。

　　假设一个多项式由多个多项式构成，每个多项式采用如上所述的方法进行存储，则如图

　　coef expn next

　　根据上图可以看出，序数在coef数据域；指数存放在expn数据域；next域存放的就是指针。所以，由这些元素构成的数据节点链接起来的单链表就可以被用来表示一元多项式。

　　以两个多项式的加法运算为例，在进行这一数学运算时它的基本思想是，对于任意两个一元多项式中都会存在指数相同的项，各个相同指数所对应的项的系数进行相加，在进行运算时会出现两种结果，若在运算后结果不为0，是一个任意不为0的实数，则需要在结果多项式中新加入一个项，该项所对应的系数即为这两个指数相同的项所对应的多项式的系数相加的和，删去指数相同的原多项式，形成结果多项式，若结果为0，则该指数所在的两个项均要删去；对于任意两个一元多项式中所有的指数都不相等，则把所有指数相对应的项的系数按照指数的大小分别写入结果多项式中。

　　一元多项式的加法运算如果在链表中进行，则根据链表的特点可知，无需再构建一个结果多项式的链表，可以根据已有链表进行运算，新的节点也无需在已有的链表中被生成，摘取已有两个多项式的链表相对应的节点，完成多项式的运算。

　　根据这一方法，两个多项式运用链表进行加法运算的规则如下：若存两个在多项式A和B用链表表示，使用指针a和指针b分别指向多项式A和多项式B链表中的任意一个节点，对这两个节点所对应的指数项进行比较，则有3种情况可能会出现，分别是：第一种情况指针a所指向的节点所对应的项的指数<指针b所指向的节点所对应的项的指数，在此种情况下，选择指针b所指向的结点把它插入到结果多项式所存在的链表之中，成为结果多项式所在链表的一部分；第二种情况指针a所指向的节点所对应的项的指数>指针b所指向的节点所对应的项的指数，在此种情况下，选择指针b所指向的结点把它插入到结果多项式所存在的链表之中，成为结果多项式所在链表的一部分;第三种情况是指针a所指向的节点所对应的项的指数=指针b所指向的节点所对应的项的指数，则指针a所指向的结点所对应的系数应该加上指针b所指向的结点所对应的系数，得到一个新的系数，指数则不变，如果这个新的系数不等于0，是一个任意不为零的实数，则将指针a所指向的结点对应的系数修改为这个新的系数，与此同时删去指针b所指向的节点；与此相反，如果新的系数等于0，则在结果多项式中指针a和指针b所指向的结点在其各自所指向的结点中没有存在的必要，应该将这两个结点从其所对应的多项式链表中删除，并且在原有的链表中将指针a和指针b所指向的节点解放出来，进入下一步的运算之中。

　　以两个多项式的减法运算为例，在进行这一数学运算时它的基本思想是，对于任意两个一元多项式中都会存在指数相同的项,各个相同指数所对应的项的系数进行相减在进行运算时会出现两种情况，若在运算后结果不为0，，是一个任意不为0的实数，则需要在结果多项式中新加入一个项，该项所对应的系数即为指数所对应的系数相减的差，成为结果多项式的一部分，若结果为0，则该指数所在的两个项均要删去；对于任意两个一元多项式中所有指数都不相等，需要进行进一步的操作把被减数的指数所对应的项复制到结果多项式中，将减数的指数所对应的项取负号后的项复制到结果多项式中。

　　在链表中进行一元多项式的减法运算，则根据链表的特点可知，在构建的链表中，无需再构建一个结果多项式的链表，可以根据已有链表进行运算，新的节点也无需在已有的链表中被生成，摘取已有两个多项式的链表相对应的节点，加以处理完成多项式的运算。

　　根据这一方法，两个多项式运用链表进行减法运算的规则如下：假设两个多项式A和B，多项式A为被减数，多项式B为减数，多项式A和多项式B在其各自所在链表中的指针分别为指针a和指针b,指针a和指针b分别指向两个多项式链表中的任意一个节点，对这两个节点的指数项进行比较，则有3种情况可能会出现，分别是：第一种情况指针a所指向的节点所对应的项的指数<指针b所指向的节点所对应的项的指数，在此种情况下，选择指针b所指向的结点把它插入到结果多项式所存在的链表之中，成为结果多项式所在链表的一部分；第二种情况指针a所指向的节点所对应的项的指数>指针b所指向的节点所对应的项的指数，在此种情况下，选择指针b所指向的结点把它插入到结果多项式所存在的链表之中，成为结果多项式所在链表的一部分;第三种情况指针a所指向的节点所对应的项的指数和指针b所指向的节点所对应的项的指数指数相等，则指针a所指向的结点所对应的系数应该减去上指针b所指向的结点所对应的系数，得到一个新的系数，指数则不变，如果这个新的系数不等于0，是一个任意不为零的实数，则将指针a所指向的结点对应的系数修改为这个新的系数，与此同时删去指针b所指向的节点；与此相反，如果新的系数等于0，则在结果多项式中指针a和指针b所指向的结点在其各自所指向的结点中没有存在的必要，应该将这两个结点从其所对应的多项式链表中删除，并且在原有的链表中将指针a和指针b所指向的节点解放出来，进入下一步的运算之中。

　　以两个多项式的乘法运算为例，在进行这一数学运算时它的基本思想是，首先将多项式按照升序进行排列，取第一个多项式的第一项分别与第二个多项式的每一项相乘，在每个项相乘时，系数相乘，指数相加，得到结果多项式的一组项；然后第一个多项式的第二项分别于第二个多项式的每一项相乘，重复上述操作，直到第一个多项式的每一项都与第二个多项式的每一项相乘。在完成相乘的过程后，对得到的结果多项式进行整理，按照升序排列，其指数相同的项，系数相加，得到该指数新的由系数相加后的项，原来指数相同的项则删去，则得到便是结果多项式。[胡军，马勇，万林.经历活动探究发展运算能力——以多项式乘以多项式教学为例[J].中学数学.2014,7.8-12.]

　　一元多项式的乘法运算如果在链表中进行，则根据链表的特点可知，无需再构建一个结果多项式的链表，可以根据已有链表进行运算，新的节点也无需在已有的链表中被生成，摘取已有两个多项式的链表相对应的节点，完成多项式的运算。

　　根据这一方法，两个多项式运用链表进行乘法运算的规则如下：假设两个一元多项式分别为多项式A和多项式B，在其各自所在链表中的指针分别为指针a和指针b,指针a和指针b根据它们所在的链表按照其对应的多项式指向一元多项式A和一元多项式B中的任意一个节点，在进行乘法运算时，首先选定指针a所指向的节点保持不变，然后将指针b所指向的一元多项式B的每一个节点都与指针a所指向的节点的系数相乘，指数项相加，得到的每一个结果插入到新构建的结果多项式的链表之中；指针a再次选定一个新的节点后保持不变，重复上述操作，直到指针a将多项式的每一个节点全部选定后并完成运算。此时得到的结果多项式存在着一些问题，即在结果多项式的链表之中，指数有可能相同，这就存在着对存储空间的浪费，占用了一些不必要的空间。为了避免这一情况，则需要对多项式进行整理。多项式的整理过程主要包括多项式的同类项合并和排序。首先要在结果多项式的链表中选取任意一个节点，取出该节点所对应的指数，然后将该链表中除选定的节点以外的每一个节点所对应的指数与取出的节点相比较，在比较的过程中，只选取两个指数相等的节点所对应的系数进行相加，得到的系数和替换已选定的指数所对应的节点相应的系数，将除选定的节点的另一指数所对应的节点删除，然后继续比较，若还存在指数相同的节点，则重复上述操作，直到每一个节点都比较完成，然后再次选定另一个节点，重复上述操作，直到每一个节点所对应的指数都选定过，得到的便是结果多项式的链表。

　　对于一元多项式的运算，在此过程可能会进行复合运算，此时就需要设计一个界面对需要进行的运算进行选择。设计如下：

　　首先要设计一个主界面进行对运算方式的选择，可以选择加法，减法，乘法三种选择，在选择过后即要开始进行正式的运算，运算过程主要是对程序的的各个部分即主函数进行调用，在进行函数调用后进入到指针数组中，指针数组有存在与多项式的链表中，在明白这一点之后开始运算，这个过程第一步是在程序中根据设计思想申请节点空间，完成之后将多项式各项的系数x,指数y，按照顺序输入，实现多项式的输入，然后把已输入的多项式用程序输出，检验是否正确，如果不是则重新开始，反之则合并同类项，进入到正式的程序中。

　　根据进行一元多项式的加法运算的步骤,首先定义存储结果所在的空链表r，判断第一个多项式的空链表P是否为空链表，若P为空链表,则将空链表P的各项按照顺序依次存入空链表r中，对存储多项式的和的链表r进行输出,合并同类项后结束运算，输出结果多项式，若P不为空链表，则继续判断第二个多项式的空链表Q是否为空链表，若Q为空链表,则将空链表Q的各项按照顺序依次存入空链表r中，对存储多项式的和的链表r进行输出,合并指数相同的项，然后结束运算，输出结果多项式；若Q不为空链表，则对两个多项式进行运算，即指数相等的项的系数进行相加，然后存入空链表r中，返回到判断存储第一个多项式的空链表P是否为空链表，重复上述操作，直到链表P和链表Q都不为空链表后，下一步是对存储多项式的和的链表r进行输出，合并指数相同的项，然后结束运算，输出结果多项式。

　　根据一元多项式的减法运算的步骤,首先定义存储结果所在的空链表r，判断第一个多项式的空链表P是否为空链表，若P为空链表,则将空链表P的各项按照顺序依次存入空链表r中，对存储多项式的和的链表r进行输出,合并同类项后结束运算，输出结果多项式，若P不为空链表，则继续判断第二个多项式的空链表Q是否为空链表，若Q为空链表,则将空链表Q的各项取负号后按照顺序依次存入空链表r中，对存储多项式的和的链表r进行输出,合并同类项后结束运算，输出结果多项式，若Q不为空链表，则同一指数的项的系数进行相减，然后存入空链表r中，返回到判断存储第一个多项式的空链表P是否为空链表，重复上述操作，直到链表P和Q都不为空链表后，下一步则是对存储多项式的和的链表r进行输出，合并指数相同的项，然后结束运算，输出结果多项式。

　　根据一元多项式的乘法运算的步骤，首先定义存储结果所在的空链表，再建立n个元素的单链表，将在单链表中插入两个多项式的系数和指数，在两个多项式中随机选定一个多项式中的指数，找到与其相对应的系数，将之与另一个多项式中的每一项系数相乘，指数相加，得到多项式的一组项，接着选定多项式中的其他项，重复上述操作，将在过程中产生的所有的项相加的结果，即为结果多项式。对于这一结果多项式还需进行处理，合并同类项，按照指数的大小依次输出,便会得到最终结果。

　　在本文对一元多项式在数学领域的定义与运算进行了说明分析，叙述了一元多项式运算在计算机领域中的表示和存储方式，围绕一元多项式运算在计算机中得以实现的算法思想进行详细描述，展现了一元多项式运算的程序设计结构。但是一些问题依然存在。在本文中只涉及了一元多项式的简单运算，即加法，减法，乘法，但还有一部分没有涉及到，例如在数学领域经常被用到，即除法和因式分解。以我目前浅薄的学术水平，这两者的研究对我是一个极大的挑战，无法在短时间内完成，需要一个长期积累的过程。本文仅仅是将所涉及到运算用一种较为简单直白的语言进行了描述，便于初学者的学习。

　　[1]陈晓霞.图形化用户界面的一元多项式运算[J].计算机时代.2008.11:70-71

　　[2]戴祯杰,农正,周永权.多项式泛函网络运算模型及应用[J].计算机工程与应用.2005,21:49-51+73

　　[3]丁夏畦，王振.Hermite多项式的乘积运算[J].系统科学与数学.2009，11:1434-1436

　　[4]方文波.多元多项式的存贮结构及四则运算的实现[J].纺织高校基础科学学报.2003,3:257-260

　　[5]冯俊.数据结构[M].北京：中国人民大学出版社.2014:68-72

　　[6]胡军，马勇，万林.经历活动探究发展运算能力——以多项式乘以多项式教学为例[J].中学数学.2014,7：8-12.

　　[7]乔川.多项式运算的实现[J].珠海教育学报.2003,03:64-66+91

　　[8]唐骏.一元多次方程求解新方法的验证与探索[D].南京大学.2015

　　[9]唐在良.矩阵形式下的一元多项式的可约性研究[J].绵阳师范学院学报.2011,11:1-7

　　[10]徐连龙,李玲.数据结构一元多项式的实现[J].科学咨询(科技•管理).2011,07:70-71

　　[11]鄢盛丰,刘建波,董安葳,王琳.多项式运算算法实现方式的改进[M].第27届中国控制与决策会议论文集.2015:2387-2390

　　[12]严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，2009:39-43

　　[13]殷人昆，陶永雷，谢若阳，盛绚华.数据结构（用面向对象方法与C++描述）[M].北京：清华大学出版社，1997:85-87

　　[14]于丽妮,岳贵鑫.MATLAB在多项式计算中的应用[J].辽宁省交通高等专科学校学报.2006,04:42-44

　　[15]章明.多项式乘法的算法设计与实现[J].电脑知识与技术(学术交流).2007,19:199-201+240

　　[16]张绍兵,季厌浮.浅析一元多项式相加问题在计算机中的实现[J].鸡西大学学报.2003,03:55-56

　　[17]郑勇林.一元n次多项式的计算机数值计算方法[J].四川教育学院学报.2003,03:59-62

　　[18]Ogunye,A.B.,Penlidis,A.,Reilly,P.M..Polynomial matrices for the design of multivariable control systems using symbolic computation[J].System Theory.1996:540-544

　　[19]V.N.Chubarikov.On Complete Rational Arithmetic Sums of Polynomial Values[J].Proceedings of the Steklov Institute of Mathematics.2017