javascript实现数据结构: 串的块链存储表示
2020-11-17 00:59
标签：des com class blog http div code img style java size 和线性表的链式存储结构相类似，也可采用链式方式存储串值。由于串结构的特殊性--结构中的每个数据元素是一个字符，则用链表存储串值时，存在一个“结点大小”的问题，即每个结点可以存放一个字符，也可以存放多个字符。 下面是结点大小为4（即每个结点存放4个字符）的链表: head --> (a) --> (b) --> (c) --> ... --> (i) 当结点大小大于1时，由于串长不一定是结点大小的整倍数，则链表中的最后一个结点不一定全被串值占满，此时通常补上“#”或其它非串值字符。 为了便于进行串的操作，当以链表存储串值时，除头指针外还可附设一个尾指针指示链表中的最后一个结点，并给出当前串的长度，称如此定义的串存储结构为块链结构。 由于一般情况下，对串进行操作时，只需要从头向尾顺序扫描即可，则对串值不必建立双向链表。设尾指针的目的是为了便于进行连接操作，但应注意连接时需处理第一个串尾的无效字符。 在链式存储方式中，结点大小的选择和顺序存储方式的格式选择一样都很重要，它直接影响到串处理的效率。如果串很长，这要求我们考虑串值的存储密度： 存储密度 = 串值所占的存储位 / 实际分配的存储位 串值的链式存储结构对某些串操作，如连接操作等有一定方便之处，但总的来说不如另外两种存储结构灵活，它占用存储量大且操作复杂。 结构图： 实现代码： 单元测试代码： javascript实现数据结构: 串的块链存储表示,搜素材,soscw.com javascript实现数据结构: 串的块链存储表示 标签：des com class blog http div code img style java size 原文地址：http://www.cnblogs.com/webFrontDev/p/3695163.html
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 ) {
30 current.ch[i % this.chunkSize] = chars[i];
31 if (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 this.length - 1 || 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 ) {
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 ) {
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 ) {
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 ) {
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 });
下一篇：java关键字