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

堆分配存储表示

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

 

结构图:

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

实现:

javascript实现数据结构:串--堆分配存储表示
 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   }
javascript实现数据结构:串--堆分配存储表示

单元测试:

javascript实现数据结构:串--堆分配存储表示
 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 });
View Code

 

javascript实现数据结构:串--堆分配存储表示,布布扣,bubuko.com

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

上一篇:VC++中,CTime 与CString转换


下一篇:oracle两列相同的去重