實現單乘與雙向鏈表的差異爲兩個多項式的乘法

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

如果您使用鏈接的列表中指定的多項式。無論其單獨還是雙重聯繫都不應該有任何區別。如果您正在構建另一個這樣的多項式，那麼使用雙向鏈表可能會有一個小優點。

但是，如果性能是一個問題，根本就不使用鏈表，那麼可以使用向量或數組。