讲解在线视频

本节，我们来学习线性表的一个应用

多项式

这里给出了一个多项式

它一共有n+1项

包含n+1个系数，n+1个指数

如何在内存当中，来存储这个多项式呢

先采用第一种方式：顺序存储

我们为数组划分了长度为

max+1的

容量，并且用数组元素的下标作为每一项的指数

然后，把每一项的系数

赋值到相应的下标处，就可以了

比如，我们这里存放了一个具有3个项的多项式

3+x^2-14x^101

我们只需要将3、1、-14

也就是这3项的系数，填充到下标为0、2、101的这3个元素位置上，就可以了

因为，这3项它们的指数，实际上是0、2、101

在这种方式下

用下标对应指数，结构非常的清晰

而且，它的大部分操作的时间复杂度都是O(1)

比如查找

因为，我们采用的是顺序存储

直接通过随机存取，就能找到相应的下标

这个下标，实际上就对应着项的指数

所以，找每一项很快，是O(1)；插入、删除也是类似的

因为，现在

每一项都存放了

尤其是那些不存在的项

系数为0的项

我们也存了，比如，x^3项

x^3项

虽然不存在

这是因为它的系数为0

那么，下标为3的这个元素

它实际上是0

它也存了

所以，无论是插入也好

删除也好

我们都只是修改一个元素的系数值

修改一个元素就可以了

不像之前讲的，以顺序存储的线性表那样，要移动元素

所以

插入、删除的时间复杂度都是O(1)

那么，两个多项式相加呢

它的时间复杂度是多少呢

通过分析

我们可以发现

如果这两个多项式，它们的最大项的系数不一样

比如，一个是101

一个是50

那么，我们只需要以最大项指数

最大的那个多项式，也就是以这里的101为基准，一共循环102次

然后，把两个数组相应的系数进行相加

就可以了

所以

两个多项式相加

在以顺序方式存储的时候

它的时间复杂度，是看两个多项式

最后一项的指数，谁大

那么，它就作为时间复杂度

这种存储方式

对于稀疏多项式，实际上会浪费非常多的空间

比如，假设每一个系数占c个字节

那么，整个多项式

所占的存储空间

至少是c(n+1)

也就是说

我们划分的

数组容量，最少必须是102

对于这个多项式来说

之所以+1

因为，还有一个下标为0的项

也就是常数项

所以，对于这个多项式

采用顺序存储，它最少占用的存储单元是c(101+1)

也就是c(n+1)

这里的n，表示的就是最后一项

它的指数。那么，最大占用空间呢

假如，max比n要大

那就是c(max+1)

稀疏多项式

比如，这个多项式，它明明只有3项

但是，它却至少要占用102*c这么多个字节

所以，非常浪费存储空间

我们来改进

我们现在把它改成链式存储，链式存储

有多少项，我们就分配多少项的结点

每一个结点有3个信息

分别是系数、指数、当前结点的下一项

比如，存放这个多项式，它对应的链表就有3个结点

我们附设了一个头结点

头结点的结构

跟这个结构是一致的

现在，它占用的存储空间就是按需分配的

一共要占用多少呢

是恒等于

链表当中结点的个数+1的

因为，有一个头结点

这个n(items)，是表示稀疏多项式当中有多少项

因为有一个头结点，所以要+1，每一项，假设系数占c个字节、指数占e个字节、指针占p个字节

那就是乘上c+e+p

当然

在大多数情况下

c、e、p它们的量级都是一样的

顶多是2、4、8这样的区分

所以，我们认为，e和p跟c都是相等的

那么，这个式子就等于

3(n(items)+1)c

即使是这样，3(n(items)+1)也是远远小于n+1的

因为，n到了101

而n(items)

只有3

所以，比前面讲的顺序存储要节约空间

它的查找时间复杂度

因为是链式存储

要遍历整个链表

所以，它的时间复杂度是O(n)；插入、删除也是一样的

因为，都需要找第i-1个元素

所以，时间复杂度都是O(n)。那么，相加呢

两个以链式存储的多项式

它们相加的时间复杂度是多少呢

现在，我们就来看相加的算法

我们这里给出了两个具体的多项式

在相加的时候

我们用第三个链表C，来存放这两个链表相加的结果

具体的算法

是：每次将A和B当中，具有较小指数的项

插到C的尾端

注意，是A和B当中，具有较小指数的项

每次都是将较小指数的项，插入到C的末尾

现在，我们来看算法的实现

将两个以链式存储的多项式A和B相加

结果存放到第三个链表C当中

在进入循环之前

我们先用两个指针pa和pb

分别指向两个链表的第一个结点

然后，创建一个

空的链表，用来存放结果

while循环条件有两个

分别是pa!=NULL和

pb!=NULL

也就是说

两个链表，都有剩余的结点未被处理完

我们才继续执行这个循环

循环体是：如果pa指向的项，它的指数小于

pb指向的项，我们插入pa指向的项

同时，pa后移

反之

如果是pa指向的项的指数

要大于pb指向的项

这时候，我们插入pb

因为，刚才说了，始终是插入pa和pb当中，指数较小的那一项

现在，pa指向的是0，pb指向的是4，毫无疑问

应该插入pa指向的、指数为0的这一项

插入的是pa

所以，pa后移，重复刚才的过程，pa和pb继续比较

现在，pb指向的是4，pa指向的是6

那应该插入pb指向的项

pb后移

现在，pa和pb指向的项的指数都是6

并且，它们的系数之和为0

这两项相加之后，实际上是不需要插入任何项的

于是

pa和pb

都后移

现在，pa指向8

小于pb指向的10，继续

168
pa后移

pb指向10，要小一些

继续往后插

我们插入的是pb

那么，pb后移

现在，pa指向的和pb指向的都是14

而且，它们的系数之和是不等于0的

于是，我们就要将它们的系数相加

作为新的项的系数

指数呢

任取一个

现在，pa后移，pa变成了空

pb再后移

这个while循环就结束了

因为，我们始终是在二者都不等于空的情况下，才继续执行

那怎么办呢

现在

pb还有元素未被插入

这是因为，如果pa的最后一项已经处理完了，那pb剩下的项

它们的指数，肯定都是大于最后一项的指数14的

所以，只需要将未被处理完的那些结点，全部插入到C的最后，就可以了

这里应该是这个指针

还有4、18

未被插入。循环结束之后

我们只需要将剩下的所有结点，插入到C的最后，就可以了

这里，我用了一个C语言的选择运算符

如果pa不等于空

注意，pa等价于pa!=NULL

我们就将pa中剩余的结点，赋值给remain

如果pa等于空

我们就将

pb剩余结点的那个指针，赋值给remain

然后，将remain及其后续项，插入到C的末端

这个需要做循环

因为，我们是用第三个链表来存放两个链表相加之和

这个算法

它的时间复杂度是多少呢

通过刚才的分析

我们可以发现，在处理

这些结点的时候

实际上，这个循环一共执行了多少次呢

一共执行了8次

因为，你始终要处理这8个结点

所以，是两倍的nA

我们这里假设，nA是小于nB的

nA就是A的项数

nB就是B的项数

剩下B当中，还有多少个结点未被插入呢

应该是nB-nA

最后，就是nA+nB

也就是两个表的项数之和

当然，这个算法我们可以改进一下

我们不一定要用第三个链表来存放最后的结果

我们可以复用原来的链表

比如，我们将相加之后的结果

赋值给A，也就是说，用A

这个链表来存放最后的结果

最后可能是这样的：第一项之后

然后到第二项，第二项之后

然后到第三项

这样下去

总之

从A这个头指针出发

我们能找到最后的结果

这是原地相加

只需要把刚才修改指针的

赋值语句，稍微修改一下即可

本章的内容就到此结束

下一章，我们将进入栈和队列

同学们，加油！