2つの多項式の乗算のSingly対Doublyリンクリストの相違点

Question

2つの多項式の乗算のための単一リンクリストまたは2重リンクリストの相違点を教えてください。

特に、二重リンクリストを使用して2つの多項式を掛けるプログラムを実装しようとしています。

アルゴリズムや、あなたの非常にいいだろうこれら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); 

• 編集*あなたがロジックのほとんどが結果を構築起こることに気づくでしょうコードビット

をクリーンアップ。 私の入力は最低のランクから最高のものにソートされているので、SLLの代わりにDLLアプローチを使用してもほとんど得られません。私は主な違いはメモリの量だと思う（DLLは、各ノードのために余分なポインタの価値 'prev'を取るだろう。）入力が 'ランク'（読み込み：電力）で並べ替えられなかったならば、最終的に挿入されたノードから始めて、 'rank'比較に基づいて 'prev'または 'next'に移動させます。

Answer 2

リンクされたリストを使用して多項式を指定した場合。それは単なるものであろうと二重であっても違いはありません。このような別の多項式を構築している場合は、二重リンクリストを使用すると小さな利点があります。

しかし、パフォーマンスが問題であった場合、リンクされたリストはまったく使用されません。ベクターまたは配列を使用します。