两个多项式乘法的单链表与双链表的差分实现

Question

对两个多项式的乘法实现单链表和双链表的区别是什么？

特别是我试图用双链表来实现两个多项式相乘的程序。

使用这些c、c++、java、c#、vb.net语言中的任何一种算法或可行的程序都是非常好的。

我认为这可能是SO question，但这只在单链列表中。

Answer 1

下面是一个使用SLL进行乘法的JavaScript。

var x0 = {rank: 0, value: 11};
var x1 = {rank: 1, value: 5};
var x2 = {rank: 2, value: 7};
/* 11 + 5x + 7x^2 */

var SLL = {data: x0, next: {data: x1, next: {data: x2, next: null}}};

var DLL = {data: x0, prev: null, next: null};
 DLL.next = {data: x1, prev: DLL, next: null};
 DLL.next.next = {data: x2, prev: DLL.next, next: null};

function mulSLL(a, b) {
 var result = null;
 var m1 = a;
 while(m1 != null) {
  var m2 = b;
  var mr = result; //re-use pointer into result
  while(m2 != null) {
   var val = {rank: m1.data.rank + m2.data.rank, value: m1.data.value * m2.data.value};
   if(result == null) { //initial create
    result = {data: val, next: null};
   } else {
    var mrold = null;
    while(mr != null && mr.data.rank < val.rank) {
     mrold = mr;
     mr = mr.next;
    }
    if(mr != null) {
     if(mr.data.rank == val.rank) { //merge
      mr.data.value += val.value;
     } else { // insert
      var mrnext = mr.next;
      mr.next = {data: val, next: mrnext};
     }
    } else { // add
     mrold.next = {data: val, next: null};
    }
   }
   m2 = m2.next; 
  }
  m1 = m1.next;
 }
 // output result
 mr = result;
 while(mr != null) {
  console.log(' + ' + mr.data.value + 'x^' + mr.data.rank);
  mr = mr.next;
 } 
 return result;
}

mulSSL(SLL,SLL);

• 编辑*稍微清理了代码

您会注意到，大多数逻辑都是在构建结果时发生的。因为我的输入是从最低到最高的排序，所以使用DLL方法，而不是SLL，我们实际上不会获得太多的收益。我认为主要的区别是内存的数量(DLL将占用每个节点额外的一个值为“prev”的空间指针)。现在，如果输入没有按“秩”(阅读: power)排序，那么使用DLL结果将允许我们从最后插入的节点开始，并根据“秩”比较移到“prev”或“next”。

Answer 2

如果您已经使用链接列表指定了多项式。不管它是单独的还是双重的，它都不应该有任何区别。如果您正在构建另一个像这样的多项式，那么使用双链接列表可能会有一个小的优势。

但是，如果性能存在问题，则根本不使用链接列表，而是使用向量或数组。