JS线性链表的例子:一元多项式

  1 var List = require('./complete-LinkedList'); 
  2  
  3 function Term(coef, expn) { 
  4   // 系数 
  5   this.coef = coef || null; 
  6   // 指数 
  7   this.expn = expn || null; 
  8 } 
  9  
 10 // 一元多项式 
 11 function Polynomial() { 
 12   List.call(this); 
 13 } 
 14 Polynomial.prototype = { 
 15   __proto__: List.prototype, 
 16  
 17   locateElem: function (elem, compare) { 
 18     var current = this.head; 
 19     var prev = current; 
 20     var obj; 
 21  
 22     while (current !== null) { 
 23       obj = {}; 
 24       var ret = compare(current.data, elem); 
 25       if (ret === 0) { 
 26         obj.data = current; 
 27         obj.found = true; 
 28         break; 
 29       } else if (ret > 0) { 
 30         obj.data = prev; 
 31         obj.found = false; 
 32         break; 
 33       } 
 34  
 35       prev = current; 
 36       current = current.next; 
 37     } 
 38  
 39     return obj; 
 40   }, 
 41   initList: function () { 
 42     this.head = List.makeNode(); 
 43     this.head.data = new Term(); 
 44     this.tail = this.head; 
 45   }, 
 46   cmp: function (a, b) { 
 47     if (a.expn < b.expn) { 
 48       return -1; 
 49     } else if (a.expn === b.expn) { 
 50       return 0; 
 51     } else { 
 52       return 1; 
 53     } 
 54   }, 
 55   // 输入m项的系数和指数，建立表示一元多项式的有序链表p 
 56   createPolyn: function (elems, elems2) { 
 57     var m = elems.length; 
 58     this.initList(); 
 59     var h = this.head; 
 60     var e = h.data; 
 61     e.coef = 0; 
 62     e.expn = -1; 
 63  
 64     for (var i = 0; i < m; i++) { 
 65       e.coef = +elems[i]; 
 66       e.expn = +elems2[i]; 
 67  
 68       var q = this.locateElem(e, this.cmp); 
 69       if (!q.found) { 
 70         this.insertAsFirst(e); 
 71       } 
 72  
 73       e = {}; 
 74     } 
 75   }, 
 76   // 多项式加法，a = a + b 
 77   addPolyn: function (b) { 
 78     var a = this; 
 79     // ha, hb分别指向头结点 
 80     var ha = a.head; 
 81     var hb = b.head; 
 82     // qa，qb分别指向当前结点 
 83     var qa = ha; 
 84     var qb = hb; 
 85  
 86     while (qa && qb) { 
 87       // 当前的比较元素 
 88       var elem1 = qa.data; 
 89       var elem2 = qb.data; 
 90  
 91       switch (this.cmp(elem1, elem2)) { 
 92         // 多项式a中当前结点的指数值小 
 93         case -1: 
 94           ha = qa; 
 95           qa = qa.next; 
 96           break; 
 97         // 两者的指数相等 
 98         case 0: 
 99           var sum = elem1.coef + elem2.coef; 
100           // 修改多项式a中当前结点的系数值 
101           if (sum !== 0) { 
102             qa.data.coef = sum; 
103             ha = qa; 
104  
105             // 删除多项式a中当前结点 
106           } else { 
107             a.delete(elem1); 
108           } 
109  
110           b.delFirst(); 
111           hb = b.head; 
112           qb = hb; 
113           qa = ha.next; 
114           break; 
115         // 多项式a中当前结点的指数值大 
116         case 1: 
117           a.insertAsFirst(b.delFirst().data); 
118           qb = b.head; 
119           ha = a.head; 
120           break; 
121       } 
122     } 
123  
124     if (b.head) { 
125       a.append(qb); 
126     } 
127   } 
128 }; 
129  
130 var test = new Polynomial(); 
131 test.createPolyn([-1, 2, 4], [1, 2, 3]); 
132  
133 var test2 = new Polynomial(); 
134 test2.createPolyn([1, 2, 3], [1, 2, 3]); 
135 test.addPolyn(test2); 
136 console.log(JSON.stringify(test)); 
137  
138 var test3 = new Polynomial(); 
139 test3.createPolyn([1, 5, 2], [1, 5, 2]); 
140 test.addPolyn(test3); 
141  
142 console.log(test);

 1 describe('polyn tests', function(){ 
 2   var test = new Polynomial(); 
 3   test.createPolyn([-1, 2, 4], [1, 2, 3]); 
 4   var test2 = new Polynomial(); 
 5   test2.createPolyn([1, 2, 3], [1, 2, 3]); 
 6  
 7   it('should add a new polyn', function(){ 
 8     test.addPolyn(test2); 
 9     expect(test.head.data).toEqual({coef: 7,expn: 3}); 
10     expect(test.head.next.data).toEqual({coef: 4,expn: 2}); 
11     expect(test.head.next.next).toEqual(null); 
12   }); 
13  
14   var test3 = new Polynomial(); 
15   test3.createPolyn([1, 5, 2], [1, 5, 2]); 
16   it('should add another new polyn', function(){ 
17     test.addPolyn(test2); 
18     expect(test.head.data).toEqual({coef: 1,expn: 1}); 
19     expect(test.head.next.data).toEqual({coef: 5,expn: 5}); 
20     expect(test.head.next.next.data).toEqual({coef: 6,expn: 2}); 
21     expect(test.head.next.next.next.data).toEqual({coef: 7,expn: 3}); 
22   }); 
23 });