Skip to main content
 首页 » 编程设计

JS实现数据结构:串的块链存储表示

2022年07月16日29zhengyun_ustc

和线性表的链式存储结构相类似,也可采用链式方式存储串值。由于串结构的特殊性--结构中的每个数据元素是一个字符,则用链表存储串值时,存在一个“结点大小”的问题,即每个结点可以存放一个字符,也可以存放多个字符。

下面是结点大小为4(即每个结点存放4个字符)的链表:

head --> (a) --> (b) --> (c) --> ... --> (i)

当结点大小大于1时,由于串长不一定是结点大小的整倍数,则链表中的最后一个结点不一定全被串值占满,此时通常补上“#”或其它非串值字符。

为了便于进行串的操作,当以链表存储串值时,除头指针外还可附设一个尾指针指示链表中的最后一个结点,并给出当前串的长度,称如此定义的串存储结构为块链结构。

由于一般情况下,对串进行操作时,只需要从头向尾顺序扫描即可,则对串值不必建立双向链表。设尾指针的目的是为了便于进行连接操作,但应注意连接时需处理第一个串尾的无效字符。

在链式存储方式中,结点大小的选择和顺序存储方式的格式选择一样都很重要,它直接影响到串处理的效率。如果串很长,这要求我们考虑串值的存储密度:

存储密度 = 串值所占的存储位 / 实际分配的存储位

串值的链式存储结构对某些串操作,如连接操作等有一定方便之处,但总的来说不如另外两种存储结构灵活,它占用存储量大且操作复杂。

结构图:

实现代码:

  1 function Chunk(chunkSize) { 
  2         this.chunkSize = chunkSize || 4; 
  3         this.ch = []; 
  4         for (var i = 0; i < this.chunkSize; i++) { 
  5             this.ch[i] = '#'; 
  6         } 
  7         // type: Chunk 
  8         this.next = null; 
  9     } 
 10  
 11     exports.LString = LString; 
 12     function LString(chunkSize) { 
 13         // type Chunk 
 14         this.head = null; 
 15         // type: chunk 
 16         this.tail = null; 
 17         // 串的当前长度 
 18         this.length = 0; 
 19         this.chunkSize = chunkSize || 4; 
 20     } 
 21  
 22     LString.prototype = { 
 23         // 将字符串转换成LString类型 
 24         strAssign: function (chars) { 
 25             this.head = this.tail = new Chunk(this.chunkSize); 
 26             this.length = chars.length; 
 27  
 28             var current = this.head; 
 29             for (var i = 0, len = chars.length; i < len; i++) { 
 30                 current.ch[i % this.chunkSize] = chars[i]; 
 31                 if (i + 1 < len && (i + 1) % this.chunkSize === 0) { 
 32                     current.next = new Chunk(); 
 33                     current = current.next; 
 34                 } 
 35             } 
 36  
 37             this.tail = current; 
 38         }, 
 39         // 字符串对比 
 40         // TODO 是否去掉chunkSize的对比 
 41         strCompare: function (tLString) { 
 42             var current = this.head; 
 43             var curT = tLString.head; 
 44  
 45             if (this.length !== tLString.length) return false; 
 46  
 47             while (current) { 
 48                 for (var i = 0; i < this.chunkSize; i++) { 
 49                     if (current.ch[i] !== curT.ch[i]) return false; 
 50                 } 
 51  
 52                 current = current.next; 
 53                 curT = curT.next; 
 54             } 
 55  
 56             return true; 
 57         }, 
 58         clearString: function () { 
 59             this.head = this.tail = null; 
 60             this.length = 0; 
 61         }, 
 62         concat: function (tLSting) { 
 63             if (!tLSting.length) return; 
 64  
 65             var ret = new LString(this.chunkSize); 
 66  
 67             if (this.head === null) { 
 68                 copyString(ret, tLSting); 
 69             } else { 
 70                 ret.head = ret.tail = new Chunk(this.chunkSize); 
 71                 copyString(ret, this); 
 72  
 73                 var index = ret.tail.ch.indexOf('#'); 
 74                 if (index === -1) { 
 75                     copyString(ret, tLSting); 
 76                 } else { 
 77                     copyString(ret, tLSting, ret.tail, tLSting.head, index); 
 78                 } 
 79             } 
 80  
 81             return ret; 
 82         }, 
 83         substring: function (pos, len) { 
 84             pos = ~~pos || 0; 
 85             len = ~~len || this.length; 
 86             if (pos < 0 || pos > this.length - 1 || len < 0 || len > this.length - pos) 
 87                 throw new Error('unexpected parameter'); 
 88  
 89             var sub = new LString(this.chunkSize); 
 90             var current = findPosChunk(this, pos); 
 91             var curS = sub.head = new Chunk(this.chunkSize); 
 92             var i = 0; 
 93             sub.length = len; 
 94  
 95             outerloop: while (current) { 
 96                 for (var j = 0, size = this.chunkSize; j < size; j++) { 
 97                     if (i === len) { 
 98                         break outerloop; 
 99                     } else { 
100                         curS.ch[j] = current.ch[(i + pos) % this.chunkSize]; 
101                         i++; 
102                         if ((i + pos) % this.chunkSize === 0) { 
103                             current = current.next; 
104                         } 
105                         if (i % this.chunkSize === 0 && (current.ch[i] || current.next)) { 
106                             curS.next = new Chunk(this.chunkSize); 
107                             curS = curS.next; 
108                         } 
109                     } 
110                 } 
111             } 
112  
113             return sub; 
114         }, 
115         toString: function () { 
116             var current = this.head; 
117  
118             if (current === null) return ''; 
119  
120             var str = ''; 
121             while (current) { 
122                 for (var i = 0, len = this.chunkSize; i < len; i++) { 
123                     var ch = current.ch[i]; 
124                     if (ch === '#') { 
125                         return str; 
126                     } else { 
127                         str += current.ch[i]; 
128                     } 
129                 } 
130                 current = current.next; 
131             } 
132  
133             return str; 
134         } 
135     }; 
136  
137     function findPosChunk(lString, pos) { 
138         var current = lString.head; 
139         while (current) { 
140             for (var i = 0, len = lString.chunkSize; i < len; i++) { 
141                 if (pos-- === 0) return current; 
142             } 
143             current = current.next; 
144         } 
145     } 
146  
147     function copyString(destination, target, curD, currT, offset) { 
148         offset = offset || 0; 
149         currT = currT || target.head; 
150         curD = curD || destination.head; 
151         var k = 0; 
152  
153         while (currT) { 
154             for (var i = 0, len = target.chunkSize; i < len; i++, k++) { 
155                 var j = k % curD.chunkSize + offset; 
156                 curD.ch[j % curD.chunkSize] = currT.ch[i]; 
157  
158                 if ((j + 1) % curD.chunkSize === 0 && (currT.ch[i + 1] || currT.next)) { 
159                     curD.next = new Chunk(destination.chunkSize); 
160                     curD = curD.next; 
161                 } 
162             } 
163  
164             currT = currT.next; 
165         } 
166  
167         destination.tail = curD; 
168         destination.length += target.length; 
169     } 
170  
171     var a = new LString(); 
172     var b = new LString(); 
173     var c = new LString(); 
174  
175     a.strAssign('abcdefg'); 
176     console.log(a + ''); 
177     b.strAssign('hijklmno'); 
178     console.log(b + ''); 
179     c.strAssign('abcdefg'); 
180     console.log(a.strCompare(b)); 
181     console.log(a.strCompare(c)); 
182     var t = a.concat(b); 
183     console.log(t + ''); 
184     t = t.substring(2, 5); 
185     console.log(t + '');

单元测试代码:

 1 describe('LString tests', function(){ 
 2     var a = new LString(5); 
 3     var b = new LString(4); 
 4     var c = new LString(5); 
 5     var t; 
 6  
 7     it('should assign string', function(){ 
 8         a.strAssign('abcdefg'); 
 9         expect(a + '').toBe('abcdefg'); 
10  
11         b.strAssign('hijklmno'); 
12         expect(b + '').toBe('hijklmno'); 
13  
14         c.strAssign('abcdefg'); 
15         expect(c + '').toBe('abcdefg'); 
16     }); 
17  
18     it('should compare', function(){ 
19         expect(a.strCompare(b)).toBe(false); 
20         expect(a.strCompare(c)).toBe(true); 
21     }); 
22  
23     it('should concat', function(){ 
24         t = a.concat(b); 
25         expect(t + '').toBe('abcdefghijklmno'); 
26     }); 
27  
28     it('should substring', function(){ 
29         t = t.substring(2, 5); 
30         expect(t + '').toBe('cdefg'); 
31     }); 
32 });

本文参考链接:https://www.cnblogs.com/webFrontDev/p/3695163.html