Различия, реализующие Сингли против двусвязного списка для Умножения двух полиномов - PullRequest
Новая
       5

Различия, реализующие Сингли против двусвязного списка для Умножения двух полиномов

1 голос
/ 15 сентября 2011

В чем различия, реализующие односвязный список или двусвязный список для умножения двух полиномов.

И особенно я пытаюсь реализовать программу для умножения двух полиномов, используя двусвязный список.

Алгоритм или работающая программа, использующая любой из этих языков c, c++, java, c#, vb.net, была бы очень милой с вашей стороны.

Я думаю, что это могло бы быть ТАК вопрос , но это только в Единственном связанном списке ..

Ответы [ 2 ]

2 голосов
/ 15 сентября 2011

Вот JavaScript для умножения с использованием SLL. 

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 будетпозвольте нам начать с последнего вставленного узла и перейти к «предыдущий» или «следующий» на основе сравнения «ранг».

0 голосов
/ 15 сентября 2011

Если вы указали многочлен, используя связанный список. Это не должно иметь никакого значения, независимо от того, однозначно или двукратно оно связано. Если вы строите другой многочлен, подобный этому, использование двусвязного списка может иметь небольшое преимущество.

Однако, если бы производительность была проблемой, вы бы вообще не использовали связанный список, вы бы использовали вектор или массив.

...