c - 如何用链表实现O(M^2N)的两个多项式的乘法？

Question

这是“C 中的数据结构和算法分析”练习 3.7 中的练习。 假设在链表中实现了两个多项式。一个有 M 项。另一个有 N 项。练习要求我在 O(M^2N) 中实现两个多项式的乘法(假设 M 是较小的那个)。如何解决？

Answer 1

我可以给你想法。

假设多项式是 1+x+x^3 和 1+x^2。

使用(1,1)--->(1,1)--->(1,3)创建链表P

创建另一个链表 Q (1,1)--->(1,2) 其中 (a,b) 表示 x^b 的系数。

现在对于 P 中的每个节点，将它与 Q 中的每个节点相乘。

如何？我们将创建一个节点 res with (x,y) where

x= P->coeff * Q->coeff.

和y=P->exp+Q->exp。

将这个新节点添加到将包含答案的多项式中。

---

在插入 answer 多项式时，您必须记住两件事 -

i) Keep a sorted list (sorted against the exp)(increasing maybe as I have takem increasing here--you can take decreasing also).

ii) Get the correct position in case you add new node and if a node with same exp value exists add the coeff only and delete the node that you are about to insert.

好的!现在打印多项式。

复杂性分析。