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

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'指针，现在如果输入不是按'rank'排序（读：power），那么使用DLL结果会允许我们从最后插入的节点开始，并根据'等级'比较移动到'prev'或'next'。

Answer 2

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

但是，如果性能是一个问题，根本就不使用链表，那么可以使用向量或数组。