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

Question

实现两个多项式相乘的单链表和双链表有什么区别。

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

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

我想这可能是什么问题，但这只是在Singly Linked List中。。

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"的额外指针空间。现在，如果输入没有按"秩"(读作：幂(排序，那么使用DLL结果将允许我们从最后插入的节点开始，并根据"秩"比较移动到"preve"或"next"。

Answer 2

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

但是，如果性能是一个问题，则根本不会使用链表，而是使用向量或数组。