用数组实现多项式的加法

本文主要是介绍用数组实现多项式的加法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

学习C语言的同学相信都会遇到这个题目，在数据结构课上他是一个非常经典题目，通常来说人们都是用链表的知识来实现的，今天给大家介绍一个用数组实现的方法。

先来看题目

用链表表示多项式，并实现多项式的加法运算

输入格式:

输入在第一行给出第一个多项式POLYA的系数和指数，并以0,0 结束第一个多项式的输入；在第二行出第一个多项式POLYB的系数和指数，并以0,0 结束第一个多项式的输入。

输出格式:

对每一组输入，在一行中输出POLYA+POLYB和多项式的系数和指数。

输入样例:

5,0 2,1 1,6 8,15 0,0
-2,1 3,6 4,8 0,0

结尾无空行

输出样例:

5,0 4,6 4,8 8,15 

结尾无空行

我们先来分析一下用数组实现的可行性，实现输入有两个多项式，每个多项式包括了两部分：系数和指数。多项式加法就是把指数相同的项的系数相加，输出的时候，系数为零的就不用输出了。很明显我们要做的是比较第一个多项式的系数和第二个多项式的系数，然后把系数相同的进行相加。两个内容：比较、相加。理论上数组是可以实现这个功能的。

现在具体说一下算法

首先用户会按照一定的规则输入两个多项式，那么我们就先把他们分别存放在两个数组中，我们还可以从a[1]存起，把a[0]空出来，这样子后面会方便一点，当然从0开始存也是可以的。第二个多项式也是一样的，我们把他存放在数组b中。因为输入是先输入系数，再输入指数，所以我们直接把系数存在奇数下标，指数存在偶数下标（从0开始存的朋友这里就刚好相反）。下面所有的数组情况是一样的，奇数下标里面存系数，偶数下标里面存指数。

接下来我们对指数进行比较，在把指数相同的 系数加起来，把加起来的结果存到另一个数组c中。我们的指数存在了偶数下标里面，所以我们只需要比较偶数项就可以了，系数相加的时候就加奇数下标。因为多项式的加法是不会改变我们的系数的，所以我们直接把a的系数赋值给c即可。再把刚刚合并了的项的系数变成0，避免后面重复合并。进行比较的时候，我们只需要用两个for循环进行冒泡比较即可实现。

因为合并的时候，c数组我们是直接使用了比较过程中的下标，这时候c数组里面合并好的内容其实是分散的，我们要把他发到一起来，这也是为了方便后面的输出操作 。我们可以直接遍历数组c，把数组c里面不等于0的拿到一个新的数组d中就可以了。这个非常容易实现。

再下来我们要干的就是对d进行排序，为什么呢？因为题目说了，按照指数升序进行输出，所以我们先对数组d进行排序。 同样的，这里只需要比较偶数下标就可以了。注意这里我们要比较的是指数，对指数进行升序排序，但是排序的时候一定一定要记得，系数也要跟着指数进行排序，不然就全乱套了结果就不对了。 

比较完排好序，接下来就是输出了。到了这里想必大家都知道要怎么输出了，这里不细说了

我们按照上面题目的测试样例输入测试一下

很好，结果正确。

输出正确之后是不是就结束了呢？并没有。我做的那个题目中有两个测试题，第一个测试输入的多项式指数是升序的，第二个测试输入的多项式指数是乱序的 。

很显然第一个测试题通过了，第二个没有通过，原因我也不是很清楚，读者们知道原因的话欢迎评论区讨论。

有问题那就得解决是不是，既然你输入的时候是乱序的，那我给你排序不就完了么，排序我们在行啊，那么这个排序又在哪一步进行呢？这个留给读者思考，我们评论区见。

想直接要CV代码的请看下一个博客

这篇关于用数组实现多项式的加法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！