Skip to main content
 首页 » 编程设计

JS实现数据结构:串-定长顺序存储表示以及kmp算法实现

2022年07月16日24xxx_UU

串(string)(或字符串)是由零个或多个字符组成的有限序列。串中字符的数目称为串的长度。零个字符的串称为空串(null string),它的长度为零。

串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。

只有当两个串的长度相等,并且各个对应位置的字符都相等时才相等。

串有3种机内表示方法:
* 1.定长顺序存储表示
* 2.堆分配存储表示
* 3.串的块链存储表示

定长顺序存储表示:

类似于线性表的顺序存储结构,用一组地址连续的存储单元存储串值得字符序列。在串的定长顺序存储结构中,按照预定义的大小,为每个定义的串变量分配一个固定长度的存储区,则可用定长数组来描述。

以下标为0的数组分量存放串的实际长度:

结构图:

实现:

  1 function SString() { 
  2         this.MAXSTRLEN = 10; 
  3     } 
  4  
  5     exports.SString = SString; 
  6     SString.prototype = { 
  7         constructor: SString, 
  8         // 返回由s1和s2连接而成的新串 
  9         concat: function (s2) { 
 10             var t = new SString(); 
 11             // 未截断 
 12             if (this[0] + s2[0] <= this.MAXSTRLEN) { 
 13                 copyStr2T(this); 
 14                 copyStr2T(s2, this[0]); 
 15                 t[0] = this[0] + s2[0]; 
 16  
 17                 // 截断 
 18             } else if (this[0] < this.MAXSTRLEN) { 
 19                 copyStr2T(this); 
 20                 copyStr2T(s2, this[0], this.MAXSTRLEN - this[0]); 
 21                 t[0] = this.MAXSTRLEN; 
 22  
 23                 // 截断(仅取s1) 
 24             } else { 
 25                 copyStr2T(this, 0, this.MAXSTRLEN); 
 26                 t[0] = this[0] = this.MAXSTRLEN; 
 27             } 
 28  
 29             return t; 
 30  
 31             function copyStr2T(str, start, end) { 
 32                 start = start || 0; 
 33                 for (var i = 1, len = end || str[0]; i <= len; i++) { 
 34                     t[start + i] = str[i]; 
 35                 } 
 36             } 
 37         }, 
 38         substring: function (position, len) { 
 39             position = ~~position || 0; 
 40             len = ~~len || this[0]; 
 41             if (position < 0 || position > this[0] - 1 || len < 0 || len > this[0] - position) 
 42                 throw new Error('unexpected parameter'); 
 43  
 44             var sub = new SString(); 
 45             for (var i = 1; i <= len; i++) { 
 46                 sub[i] = this[position + i - 1]; 
 47             } 
 48             sub[0] = len; 
 49  
 50             return sub; 
 51         }, 
 52         toString: function () { 
 53             var str = ''; 
 54             for (var i = 1; this[i]; i++) { 
 55                 str += this[i]; 
 56             } 
 57             return str; 
 58         }, 
 59         // 返回子串sstring在主串中的第position个字符之后的位置 
 60         index: function (sstring, position) { 
 61             var i = position || 0; 
 62             var j = 1; 
 63  
 64             while (i <= this[0] && j <= sstring[0]) { 
 65                 if (this[i] === sstring[j]) { 
 66                     i++; 
 67                     j++; 
 68                 } else { 
 69                     i = i - j + 2; 
 70                     j = 1; 
 71                 } 
 72             } 
 73  
 74             return j > sstring[0] ? i - sstring[0] : -1; 
 75         }, 
 76         kmpIndex: function (sstring, position) { 
 77             var i = position || 0; 
 78             var j = 1; 
 79             var next = getNext(sstring); 
 80  
 81             while (i <= this[0] && j <= sstring[0]) { 
 82                 if (j === 0 || this[i] === sstring[j]) { 
 83                     ++i; 
 84                     ++j; 
 85                 } else { 
 86                     j = next[j]; 
 87                 } 
 88             } 
 89  
 90             return j > sstring[0] ? i - sstring[0] : -1; 
 91         } 
 92     }; 
 93  
 94     function getNext(sstring) { 
 95         var i = 1; 
 96         var next = {1: 0}; 
 97         var j = 0; 
 98  
 99         while (i < sstring[0]) { 
100             if (j === 0 || sstring[i] === sstring[j]) { 
101                 if(sstring[++i] !== sstring[++j]){ 
102                     next[i] = j; 
103                 } else { 
104                     next[i] = next[j]; 
105                 } 
106 //                next[++i] = ++j; 
107             } else { 
108                 j = next[j]; 
109             } 
110         } 
111  
112         return next; 
113     } 
114  
115     var a = new SString(); 
116     var b = new SString(); 
117     for (var i = 0; i < 4; i++) { 
118         a[i + 1] = i + ''; 
119         b[i + 1] = i + ''; 
120     } 
121     a[0] = b[0] = 4; 
122     var t = a.concat(b); 
123     console.log(t + '');       // 01230123 
124  
125     var d = new SString(); 
126     var str = 'acabaabaabcacaabc'; 
127     for(i = 0; i < str.length; i++){ 
128         d[i + 1] = str[i]; 
129     } 
130     d[0] = str.length; 
131  
132     var c = new SString(); 
133     str = 'abaabc'; 
134     for(i = 0; i < str.length; i++){ 
135         c[i + 1] = str[i]; 
136     } 
137     c[0] = str.length; 
138  
139     console.log(d.index(c)); 
140     console.log(d.kmpIndex(c));

单元测试代码:

 1 describe('SString tests', function(){ 
 2   var a = new SString(); 
 3   var b = new SString(); 
 4  
 5   it('should concat without break strings', function(){ 
 6     for(var i = 0; i < 4; i++){ 
 7       a[i + 1] = i + ''; 
 8       b[i + 1] = i + ''; 
 9     } 
10     a[0] = b[0] = 4; 
11  
12     var t = a.concat(b); 
13     console.log(a); 
14     console.log(b); 
15     expect(t[0]).toBe(8); 
16     expect(t + '').toBe('01230123'); 
17   }); 
18  
19   it('should break strings of b', function(){ 
20     for(var i = 0; i < 7; i++){ 
21       b[i + 1] = i + ''; 
22     } 
23     b[0] = 7; 
24  
25     var t = a.concat(b); 
26     console.log(a); 
27     console.log(b); 
28     expect(t[0]).toBe(10); 
29     expect(t + '').toBe('0123012345'); 
30   }); 
31  
32   it('should break strings of a', function(){ 
33     for(var i = 4; i < 10; i++){ 
34       a[i + 1] = i + ''; 
35     } 
36     a[0] = 10; 
37  
38     var t = a.concat(b); 
39     console.log(a); 
40     console.log(b); 
41     expect(t[0]).toBe(10); 
42     expect(t + '').toBe('0123456789'); 
43   }); 
44  
45   it('should get substring', function(){ 
46     console.log(a); 
47     var t = a.substring(1, 10); 
48     expect(t + '').toBe('0123456789'); 
49  
50     t = a.substring(3, 5); 
51     expect(t + '').toBe('23456'); 
52   }); 
53 });

在顺序存储结构中,实现串操作的原操作为“字符串序列的复制”,操作时间复杂度基于复制的字符串序列的长度。
另一操作特点是,如果在操作中出现串值序列的长度超过MAXSTRLEN时,约定用截尾法处理,这种情况不仅在求连接串时可能发生,在串的其他操作中,如插入,置换等也可能发生,克服这个弊病唯有不限定串长的最大长度,即动态分配串值的存储空间。


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