JS实现数据结构与算法系列:线性表的静态单链表存储结构

  1 (function(module){ 
  2   function SLinkList(data, cur, MAXSIZE) { 
  3     this[0] = {}; 
  4     this[0].data = data; 
  5     this[0].cur = cur; 
  6     this.MAXSIZE = MAXSIZE || 1000; 
  7   } 
  8   module.exports = SLinkList; 
  9   SLinkList.prototype = { 
 10     /** 
 11      * 在静态单链线性表L中查找第1个值为e的元素， 
 12      * 若找到，则返回它在L中的位序 
 13      * @param data 
 14      */ 
 15     locateElem: function (data) { 
 16       var i = this[0].cur; 
 17       while (i && this[i].data !== data) { 
 18         i = this[i].cur; 
 19       } 
 20       return i; 
 21     }, 
 22     /** 
 23      * 将一维数组中各分量链成一个备用链表 
 24      * this[0].cur为头指针 
 25      */ 
 26     initSpace: function () { 
 27       for (var i = 0; i < this.MAXSIZE - 1; ++i) { 
 28         this[i] = this[i] || {}; 
 29         this[i].cur = i + 1; 
 30       } 
 31  
 32       this[this.MAXSIZE - 1] = this[this.MAXSIZE - 1] || {}; 
 33       this[this.MAXSIZE - 1].cur = 0; 
 34     }, 
 35     /** 
 36      * 若备用链表非空，则返回分配的结点下标，反则返回0 
 37      * @returns {*} 
 38      */ 
 39     malloc: function () { 
 40       var i = this[0].cur; 
 41       if (this[0].cur) this[0].cur = this[i].cur; 
 42       return i; 
 43     }, 
 44     /** 
 45      * 将下标为k的空闲结点回收到备用链表 
 46      * @param k 
 47      */ 
 48     free: function (k) { 
 49       this[k].cur = this[0].cur; 
 50       this[0].cur = k; 
 51     }, 
 52     /** 
 53      * 在一维数组中建立表示集合(A-B)U(B-A) 
 54      * 的静态链表，s为其头指针。 
 55      * @returns {*} 
 56      */ 
 57     difference: function (arr1, arr2) { 
 58       // 初始化备用空间 
 59       this.initSpace(); 
 60       // 生成s的头结点 
 61       var s = this.malloc(); 
 62       // r指向s的当前最后结点 
 63       var r = s; 
 64       // 删除A和B的元素个数 
 65       var m = arr1.length; 
 66       var n = arr2.length; 
 67  
 68       // 建立集合A的链表 
 69       for (var j = 0; j < m; ++j) { 
 70         //分配结点 
 71         var i = this.malloc(); 
 72         // 输入A元素的值 
 73         this[i].data = arr1[j]; 
 74         // 插入到表尾 
 75         this[r].cur = i; 
 76         r = i; 
 77       } 
 78       // 尾结点的指针为空 
 79       this[r].cur = 0; 
 80  
 81       // 依次输入B的元素，若不在当前表中，则插入， 
 82       // 否则删除 
 83       for (j = 0; j < n; ++j) { 
 84         var b = arr2[j]; 
 85         var p = s; 
 86         // k指向集合中的第一个结点 
 87         var k = this[s].cur; 
 88         // 在当前表中查找 
 89         while (k !== this[r].cur && this[k].data !== b) { 
 90           p = k; 
 91           k = this[k].cur; 
 92         } 
 93         // 当前表中不存在该元素，插入在r所指结点之后，且r的位置不变 
 94         if (k === this[r].cur) { 
 95           i = this.malloc(); 
 96           this[i].data = b; 
 97           this[i].cur = this[r].cur; 
 98           this[r].cur = i; 
 99  
100           // 该元素已在表中，删除之 
101         } else { 
102           this[p].cur = this[k].cur; 
103           this.free(k); 
104           // 若删除的是r所指结点，则需修改尾指针 
105           if (r === k) r = p; 
106         } 
107       } 
108     } 
109   }; 
110  
111   var sl = new SLinkList(1, 0, 10); 
112   var ret = sl.difference([1, 2, 3], [3, 4, 5]); 
113   console.log(sl); 
114 })(this.module|| this);