Skip to main content
 首页 » 编程设计

JS实现数据结构:串-堆分配存储表示

2022年07月16日26mengfanrong

堆分配存储表示

这种存储表示的特点是,仍以一组地址连续的存储单元存放串值字符序列,但它们的存储空间是在程序执行过程中动态分配而得。

结构图:

实现:

 1 function HString(){ 
 2     this.ch = {}; 
 3     this.length = 0; 
 4   } 
 5   exports.HString = HString; 
 6   HString.prototype = { 
 7     // 1 <= position <= this.length.在串的第position个字符之前插入串tHString 
 8     strInsert: function(position, tHString){ 
 9       if(position < 1 || position > this.length + 1) 
10         throw new Error('unexpected position'); 
11  
12       if(tHString.length){ 
13         // 为插入t而腾出位置 
14         for(var i = this.length - 1, len = position - 1; i >= len; --i) 
15           this.ch[i + tHString.length] = this.ch[i]; 
16         // s.ch[position - 1..position + tHString.length - 2] = tHString.ch[0..tHString.length - 1]; 
17 //        for(i = 0, len = tHString.length - 1; i <= len; i++) 
18 //          this.ch[position - 1 + i] = tHString.ch[i]; 
19         stringCopy(this.ch, tHString.ch, position - 1, tHString.length - 1, 0); 
20  
21         this.length += tHString.length; 
22       } 
23     }, 
24     strAssign: function(chars){ 
25 //      for(var i = 0, len = chars.length; i < len; i++){ 
26 //        this.ch[i] = chars[i]; 
27 //      } 
28       stringCopy(this.ch, chars, 0, chars.length - 1, 0); 
29       this.length = chars.length; 
30     }, 
31     strLength: function(){ 
32       return this.length; 
33     }, 
34     strCompare: function(tHString){ 
35       for(var i = 0, len = this.length; i < len && i < tHString.length; i++) 
36         if(this.ch[i] !== tHString.ch[i]) return this.ch[i] - tHString.ch[i]; 
37  
38       return this.length - tHString.length; 
39     }, 
40     clearString: function(){ 
41       this.ch = {}; 
42       this.length = 0; 
43     }, 
44     concat: function(s){ 
45       var t = new HString(); 
46  
47       // t.ch[0..this.length - 1] = this.ch[0..this.length - 1] 
48       stringCopy(t.ch, this.ch, 0, this.length - 1, 0); 
49       t.length = this.length + s.length; 
50       // t.ch[this.length..t.length - 1] = s.ch[0..s.length - 1] 
51       stringCopy(t.ch, s.ch, this.length, s.length - 1, 0); 
52  
53       return t; 
54     }, 
55     substring: function(position, len){ 
56       position = ~~position || 0; 
57       len = ~~len || this.length; 
58       if(position < 0 || position > this.length - 1 || len < 0 || len > this.length - position) 
59         throw new Error('unexpected paramater'); 
60  
61       var sub = new HString(); 
62       stringCopy(sub.ch, this.ch, 0, len - 1, position); 
63       sub.length = len; 
64  
65       return sub; 
66     }, 
67     toString: function(){ 
68       var s = ''; 
69       for(var i = 0, len = this.length; i < len; i++){ 
70         s += this.ch[i]; 
71       } 
72       return s; 
73     } 
74   }; 
75  
76   function stringCopy(destination, target, destStart, length, targetStart){ 
77     destStart = destStart || 0; 
78     length = length || target.length; 
79     targetStart = targetStart || 0; 
80  
81     for(var i = 0; i <= length; i++ ){ 
82       destination[destStart + i] = target[targetStart + i]; 
83     } 
84   }

单元测试:

 1 describe('HString tests', function(){ 
 2   var s = new HString(); 
 3   var t = new HString(); 
 4  
 5   it('should assign chars', function(){ 
 6     s.strAssign('hello world!'); 
 7     expect(s + '').toBe('hello world!'); 
 8  
 9     t.strAssign('jesus '); 
10     expect(t + '').toBe('jesus '); 
11   }); 
12  
13   it('should insert string into s', function(){ 
14     s.strInsert(7, t); 
15     expect(s + '').toBe('hello jesus world!'); 
16   }); 
17  
18   it('should concat string', function(){ 
19     var ret = s.concat(t); 
20     expect(ret + '').toBe('hello jesus world!jesus '); 
21   }); 
22  
23   it('should get substring', function(){ 
24     var ret = s.substring(0); 
25     expect(ret + '').toBe('hello jesus world!'); 
26  
27     ret = s.substring(5, 13); 
28     expect(ret + '').toBe(' jesus world!'); 
29  
30     ret = s.substring(3, 8); 
31     expect(ret + '').toBe('lo jesus'); 
32   }); 
33 });

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