原文:javascript实现数据结构：广义表
广义表是线性表的推广。广泛用于人工智能的表处理语言Lisp，把广义表作为基本的数据结构。
广义表一般记作：
LS = (a1, a2, ..., an)
LS是广义表的名称，n是它的长度，ai可以是单个元素，也可以是广义表，分别称为广义表LS的原子和子表。习惯上，用大写字母表示广义表的名称，小写字母表示原子。当广义表LS非空时，称第一个元素a1为LS的表头，称其余元素组成的表(a2, a3, ..., an)是LS的表尾。
下面列举一些广义表的例子：
1.A = () ---- A是一个空表，它的长度为0。
2.B = (e) ---- 列表B只有一个原子e，B的长度为1。
3.C = (a, (b, c, d)) ---- 列表C的长度为2，两个元素分别为原子a和子表(b, c, d)。
4.D = (A, B, C) ---- 列表D的长度为3,3个元素都是列表。显示，将子表的值代入后，则有D = ((), (e), (a, (b, c, d)))。
5.E = (a, E) ---- 这是一个递归的表，它的长度为2.E相当于一个无限的列表E = (a, (a, (a, ...)))。
下图为列表的图形表示：
从定义和例子可推出三个结论：
1）列表的元素可以是子表，而子表的元素还可以是子表。由此，列表是一个多层次的结构，可以用图形象地表示。
2）列表可为其它列表所共享。列表A，B和C为D的子表，则在D中可以不必列出子表的值。
3）列表可以是一个递归的表，即列表也可以是其本身的一个子表。例如列表E。
然后我们根据结论可知：
任何一个非空列表其表头可能是原子，也可能是列表，而其表尾必定为列表。
由于广义表中的数据元素可以具有不同的结构（或是原子，或是列表），因此难以用顺序存储结构表示，通常采用链式存储结构，每个数据元素可用一个结点表示。
下面是两种稍微不同的存储结构表示：
1 var ATOM = 0;
2 var LIST = 1;
3
4 // 广义表的头尾链表存储表示
5 function GLNode() {
6 // 公共部分，用于区分原子结点和表结点
7 this.tag = undefined;
8
9 // atom是原子结点的值域
10 this.atom = null;
11 // ptr是表结点的指针域
12 this.ptr = {
13 // ptr.hp和ptr.tp分别指向表头和表尾
14 hp: null,
15 tp: null
16 };
17 }
18
19 // 广义表的扩展线性链表存储表示
20 function GLNode2() {
21 // 公共部分，用于区分原子结点和表结点
22 this.tag = undefined;
23
24 // 原子结点的值域
25 this.atom = null;
26 // 表结点的表头指针
27 this.hp = null;
28
29 // 相当于线性链表的next，指向下一个元素结点
30 this.tp = null;
31 }
下列分别为两个存储结构的示例图：
1.GLNode
2.GLNode2
两种存储结构没有大的区别，可根据自己的习惯选择。
广义表的递归算法
我们知道递归定义的归纳项是用来描述如何实现从当前状态到终结状态的转化。
由于递归函数的设计用的是归纳思维的方法，则在设计递归函数时，应注意：
（1）首先应书写函数的首部和规格说明，严格定义函数的功能和接口（递归调用的界面），对求精函数中所得的和原问题性质相同的字问题，只要接口一致，便可进行递归调用。
（2）对函数中的每一个递归调用都看成只是一个简单的操作，只要接口一致，必能实现规格说明中定义的功能，切忌想得太深太远。
求广义表的深度
广义表的深度定义为广义表中括弧的重数，是广义表的一种量度。
设非空广义表为:
LS = (a1, a2, ..., an)
其中ai(i = 1, 2, ..., n)或为原子或为LS的子表，则求LS的深度可分解为n个子问题，每个子问题为求ai的深度，若ai是原子，则由定义其深度为零，若ai是广义表，则递归处理，而LS的深度为各ai(i = 1, 2, ..., n)的深度最大值加1.空表也是广义表，且深度为1.
广义表的深度DEPTH(LS)的递归定义为：
基本项： DEPTH(LS) = 1 当LS为空表时
DEPTH(LS) = 0 当LS为原子时
归纳项： DEPTH(LS) = 1 + MAX{DEPTH(ai)} 1 <= i <= n
下面为采用头尾链表存储结构，求广义表的深度的代码：
1 // 采用头尾链表存储结构，求广义表的深度
2 GLNode.prototype.depth = function () {
3 return getDepth(this);
4 };
5
6 function getDepth(gList) {
7 if (!gList) return 1;
8 else if (gList.tag === ATOM) return 0;
9
10 var m = getDepth(gList.ptr.hp) + 1;
11 var n = getDepth(gList.ptr.tp);
12
13 return m > n ? m : n;
14 }
然后下面是广义表基本操作的代码（都是涉及到递归算法设计）：
1 // 复制广义表
2 GLNode.prototype.copyList = function (gList) {
3 gList.tag = this.tag;
4
5 if (this.tag === ATOM) {
6 gList.atom = this.atom;
7 } else {
8 if (this.ptr.hp) {
9 gList.ptr.hp = new GLNode();
10 this.copyList.call(this.ptr.hp, gList.ptr.hp);
11 }
12 if (this.ptr.tp) {
13 gList.ptr.tp = new GLNode();
14 this.copyList.call(this.ptr.tp, gList.ptr.tp);
15 }
16 }
17 };
18
19 function isWord(str){
20 return /^[\w-]+$/.test(str);
21 }
22
23 // 采用头尾链表存储结构，由广义表的书写形式串创建广义表
24 GLNode.prototype.createGList = function (string) {
25 string = string.trim();
26
27 // 创建单原子广义表
28 var q;
29 if (isWord(string)) {
30 this.tag = ATOM;
31 this.atom = string;
32 } else {
33 this.tag = LIST;
34 var p = this;
35
36 // 脱外层括号
37 var sub = string.substr(1, string.length - 2);
38
39 do {
40 var hsub;
41 var n = sub.length;
42 var i = 0;
43 var k = 0;
44 var ch;
45
46 do {
47 ch = sub[i++];
48 if (ch == '(') ++k;
49 else if (ch == ')') --k;
50 } while (i < n && (ch != ',' || k != 0));
51
52 // i为第一个逗号分隔索引
53 if (i < n) {
54 hsub = sub.substr(0, i - 1);
55 sub = sub.substr(i, n - i);
56
57 // 最后一组
58 } else {
59 hsub = sub;
60 sub = '';
61 }
62
63 if(hsub === '()')
64 p.ptr.hp = null;
65 else
66 // 创建表头结点
67 this.createGList.call((p.ptr.hp = new GLNode()), hsub);
68
69 q = p;
70
71 // 创建表尾结点
72 if (sub) {
73 p = new GLNode();
74 p.tag = LIST;
75 q.ptr.tp = p;
76 }
77 } while (sub);
78
79 q.ptr.tp = null;
80 }
81 };
82
83 var node = new GLNode();
84 node.createGList('((), (ea), (sa, (bd, ce, dh)))');
85 console.log(node.depth());
86
87 GLNode.equal = function equal(gList1, gList2) {
88 // 空表时相等的
89 if (!gList1 && !gList2) return true;
90 if (gList1.tag === ATOM && gList2.tag === ATOM && gList1.atom === gList2.atom) return true;
91
92 if (gList1.tag === LIST && gList2.tag === LIST) {
93 // 表头表尾都相等
94 if (equal(gList1.ptr.hp, gList2.ptr.hp) && equal(gList1.ptr.tp, gList2.ptr.tp)) return true;
95 }
96
97 return false;
98 };
99
100 // 递归逆转广义表
101 GLNode.prototype.reverse = function reverse() {
102 var ptr = [];
103 // 当A不为原子且表尾非空时才需逆转
104 if (this.tag === LIST && this.ptr.tp) {
105 for (var i = 0, p = this; p; p = p.ptr.tp, i++) {
106 // 逆转各子表
107 if (p.ptr.hp) reverse.call(p.ptr.hp);
108
109 ptr[i] = p.ptr.hp;
110 }
111
112 // 重新按逆序排列各子表的顺序
113 for (p = this; p; p = p.ptr.tp)
114 p.ptr.hp = ptr[--i];
115 }
116 };
117
118 var global = Function('return this')();
119 GLNode.prototype.toString = function () {
120 var str = '';
121 if (this == global) str = '()';
122 else if (this.tag === ATOM) str = this.atom; // 原子
123 else {
124 str += '(';
125
126 for (var p = this; p; p = p.ptr.tp) {
127 str += this.toString.call(p.ptr.hp);
128 if (p.ptr.tp) str += ', ';
129 }
130 str += ')';
131 }
132
133 return str;
134 };
135
136 // 按层序输出广义表
137 // 层序遍历的问题，一般都是借助队列来完成的，每次从队头
138 // 取出一个元素的同时把它下一层的孩子插入队尾，这是层序遍历的基本思想
139 GLNode.prototype.orderPrint = function(){
140 var queue = [];
141 for(var p = this; p; p = p.ptr.tp) queue.push(p);
142
143 while(queue.length){
144 var r = queue.shift();
145 if(r.tag === ATOM) console.log(r.atom);
146 else {
147 for(r = r.ptr.hp; r; r = r.ptr.tp)
148 queue.push(r);
149 }
150 }
151 };
152
153 // 使用链队列
154 var Queue = require('../Queue/Queue.js').Queue;
155 GLNode.prototype.orderPrint2 = function(){
156 var queue = new Queue();
157
158 for(var p = this; p; p = p.ptr.tp) queue.enQueue(p);
159
160 while(queue.size){
161 var r = queue.deQueue();
162 if(r.tag === ATOM) console.log(r.atom);
163 else {
164 for(r = r.ptr.hp; r; r = r.ptr.tp)
165 queue.enQueue(r);
166 }
167 }
168 };
169
170 console.log(node + '');
171 node.reverse();
172 console.log(node + '');
173
174 var node2 = new GLNode();
175 node.copyList(node2);
176 console.log(GLNode.equal(node, node2));
177
178 console.log(node + '');
179 console.time('A');
180 node.orderPrint();
181 console.timeEnd('A');
182
183 console.log('------------------------------------');
184 console.time('B');
185 node.orderPrint2();
186 console.timeEnd('B');
广义表的运用：
m元多项式表示
如果用线性表来表示,则每个数据元素需要m+1个数据项，以存储一个系数和m个指数值，这将产生两个问题。
一是无论多项式中各项的变元数是多是少，若都按m个变元分配存储空间，则将造成浪费；反之，若按各项实际的变元数分配存储空间，就会造成结点的大小不匀，给操作带来不便。二是对m值不同的多项式，线性表中的结点大小也不同，这同样引起存储管理的不便。
故不适于用线性表表示。
例如三元多项式：
P(x, y, z) = x(10)y(3)z(2) + 2x(6)y(3)z(2) + 3x(5)y(2)z(2) + x(4)y(4)z + 2yz + 15
如若改写为：
P(x, y, z) = ((x(10) + 2x(6))y(3) + 3x(5)y(2))z(2) + ((x(4) + 6x(3))y(4) + 2y)z + 15
用广义表表示：
P = z((A, 2), (B, 1), (15, 0))
A = y((C, 3), (D, 2))
B = y((E, 4), (F, 1))
C = x((1, 10), (2, 6))
D = x((3, 5))
E = x((1, 4), (6, 3))
F = x((2, 0))
下面为用广义表描述m元多项式的存储结构：
1 function MPNode() {
2 // 区分原子结点和表结点
3 this.tag = undefined;
4 // 指数域
5 this.exp = 0;
6
7 // 系数域
8 this.coef = 0;
9 // 表结点的表头指针
10 this.hp = null;
11
12 // 相当于线性表的next，指向下一个元素结点
13 this.tp = null;
14 }
篇幅有限，就没有做其他操作，以后有空再补回吧。
所有代码：
1 /**
2 * 广义表
3 *
4 * 广义表是线性表的推广。广泛用于人工智能的表处理语言Lisp，把广义表作为基本的数据结构。
5 * 广义表一般记作：
6 * LS = (a1, a2, ..., an)
7 * LS是广义表的名称，n是它的长度，ai可以是单个元素，也可以是广义表，分别称为广义表LS的原子和子表。习惯上，用大写字母表示广义表的名称，小写字母表示原子。当广义表LS非空时，称第一个元素a1为LS的表头，称其余元素组成的表(a2, a3, ..., an)是LS的表尾。
8 *
9 * 下面列举一些广义表的例子：
10 * 1.A = () ---- A是一个空表，它的长度为0。
11 * 2.B = (e) ---- 列表B只有一个原子e，B的长度为1。
12 * 3.C = (a, (b, c, d)) ---- 列表C的长度为2，两个元素分别为原子a和子表(b, c, d)。
13 * 4.D = (A, B, C) ---- 列表D的长度为3,3个元素都是列表。显示，将子表的值代入后，则有D = ((), (e), (a, (b, c, d)))。
14 * 5.E = (a, E) ---- 这是一个递归的表，它的长度为2.E相当于一个无限的列表E = (a, (a, (a, ...)))。
15 *
16 * 1）列表的元素可以是子表，而子表的元素还可以是子表。由此，列表是一个多层次的结构，可以用图形象地表示。
17 * 2)列表可为其它列表所共享。列表A，B和C为D的子表，则在D中可以不必列出子表的值。
18 * 3）列表可以是一个递归的表，即列表也可以是其本身的一个子表。例如列表E。
19 *
20 * 任何一个非空列表其表头可能是原子，也可能是列表，而其表尾必定为列表。
21 *
22 */
23
24 var ATOM = 0;
25 var LIST = 1;
26
27 // 广义表的头尾链表存储表示
28 function GLNode() {
29 // 公共部分，用于区分原子结点和表结点
30 this.tag = undefined;
31
32 // atom是原子结点的值域
33 this.atom = null;
34 // ptr是表结点的指针域
35 this.ptr = {
36 // ptr.hp和ptr.tp分别指向表头和表尾
37 hp: null,
38 tp: null
39 };
40 }
41
42 // 广义表的扩展线性链表存储表示
43 function GLNode2() {
44 // 公共部分，用于区分原子结点和表结点
45 this.tag = undefined;
46
47 // 原子结点的值域
48 this.atom = null;
49 // 表结点的表头指针
50 this.hp = null;
51
52 // 相当于线性链表的next，指向下一个元素结点
53 this.tp = null;
54 }
55
56
57 /*
58 广义表的递归算法
59
60 递归定义的归纳项描述了如何实现从当前状态到终结状态的转化。
61
62 由于递归函数的设计用的是归纳思维的方法，则在设计递归函数时，应注意：
63 （1）首先应书写函数的首部和规格说明，严格定义函数的功能和接口（递归调用的界面），对求精函数中所得的和原问题性质相同的字问题，只要接口一致，便可进行递归调用。
64 （2）对函数中的每一个递归调用都看成只是一个简单的操作，只要接口一致，必能实现规格说明中定义的功能，切忌想得太深太远。
65 */
66
67 /*
68 求广义表的深度
69
70 广义表的深度定义为广义表中括弧的重数，是广义表的一种量度。
71 设非空广义表为:
72 LS = (a1, a2, ..., an)
73
74 其中ai(i = 1, 2, ..., n)或为原子或为LS的子表，则求LS的深度可分解为n个子问题，每个子问题为求ai的深度，若ai是原子，则由定义其深度为零，若ai是广义表，则递归处理，而LS的深度为各ai(i = 1, 2, ..., n)的深度最大值加1.空表也是广义表，且深度为1.
75
76 广义表的深度DEPTH(LS)的递归定义为：
77 基本项： DEPTH(LS) = 1 当LS为空表时
78 DEPTH(LS) = 0 当LS为原子时
79 归纳项： DEPTH(LS) = 1 + MAX{DEPTH(ai)} 1 <= i <= n
80 */
81
82 // 采用头尾链表存储结构，求广义表的深度
83 GLNode.prototype.depth = function () {
84 return getDepth(this);
85 };
86
87 function getDepth(gList) {
88 if (!gList) return 1;
89 else if (gList.tag === ATOM) return 0;
90
91 var m = getDepth(gList.ptr.hp) + 1;
92 var n = getDepth(gList.ptr.tp);
93
94 return m > n ? m : n;
95 }
96
97 // 复制广义表
98 GLNode.prototype.copyList = function (gList) {
99 gList.tag = this.tag;
100
101 if (this.tag === ATOM) {
102 gList.atom = this.atom;
103 } else {
104 if (this.ptr.hp) {
105 gList.ptr.hp = new GLNode();
106 this.copyList.call(this.ptr.hp, gList.ptr.hp);
107 }
108 if (this.ptr.tp) {
109 gList.ptr.tp = new GLNode();
110 this.copyList.call(this.ptr.tp, gList.ptr.tp);
111 }
112 }
113 };
114
115 function isWord(str){
116 return /^[\w-]+$/.test(str);
117 }
118
119 // 采用头尾链表存储结构，由广义表的书写形式串创建广义表
120 GLNode.prototype.createGList = function (string) {
121 string = string.trim();
122
123 // 创建单原子广义表
124 var q;
125 if (isWord(string)) {
126 this.tag = ATOM;
127 this.atom = string;
128 } else {
129 this.tag = LIST;
130 var p = this;
131
132 // 脱外层括号
133 var sub = string.substr(1, string.length - 2);
134
135 do {
136 var hsub;
137 var n = sub.length;
138 var i = 0;
139 var k = 0;
140 var ch;
141
142 do {
143 ch = sub[i++];
144 if (ch == '(') ++k;
145 else if (ch == ')') --k;
146 } while (i < n && (ch != ',' || k != 0));
147
148 // i为第一个逗号分隔索引
149 if (i < n) {
150 hsub = sub.substr(0, i - 1);
151 sub = sub.substr(i, n - i);
152
153 // 最后一组
154 } else {
155 hsub = sub;
156 sub = '';
157 }
158
159 if(hsub === '()')
160 p.ptr.hp = null;
161 else
162 // 创建表头结点
163 this.createGList.call((p.ptr.hp = new GLNode()), hsub);
164
165 q = p;
166
167 // 创建表尾结点
168 if (sub) {
169 p = new GLNode();
170 p.tag = LIST;
171 q.ptr.tp = p;
172 }
173 } while (sub);
174
175 q.ptr.tp = null;
176 }
177 };
178
179 var node = new GLNode();
180 node.createGList('((), (ea), (sa, (bd, ce, dh)))');
181 console.log(node.depth());
182
183 GLNode.equal = function equal(gList1, gList2) {
184 // 空表时相等的
185 if (!gList1 && !gList2) return true;
186 if (gList1.tag === ATOM && gList2.tag === ATOM && gList1.atom === gList2.atom) return true;
187
188 if (gList1.tag === LIST && gList2.tag === LIST) {
189 // 表头表尾都相等
190 if (equal(gList1.ptr.hp, gList2.ptr.hp) && equal(gList1.ptr.tp, gList2.ptr.tp)) return true;
191 }
192
193 return false;
194 };
195
196 // 递归逆转广义表
197 GLNode.prototype.reverse = function reverse() {
198 var ptr = [];
199 // 当A不为原子且表尾非空时才需逆转
200 if (this.tag === LIST && this.ptr.tp) {
201 for (var i = 0, p = this; p; p = p.ptr.tp, i++) {
202 // 逆转各子表
203 if (p.ptr.hp) reverse.call(p.ptr.hp);
204
205 ptr[i] = p.ptr.hp;
206 }
207
208 // 重新按逆序排列各子表的顺序
209 for (p = this; p; p = p.ptr.tp)
210 p.ptr.hp = ptr[--i];
211 }
212 };
213
214 var global = Function('return this')();
215 GLNode.prototype.toString = function () {
216 var str = '';
217 if (this == global) str = '()';
218 else if (this.tag === ATOM) str = this.atom; // 原子
219 else {
220 str += '(';
221
222 for (var p = this; p; p = p.ptr.tp) {
223 str += this.toString.call(p.ptr.hp);
224 if (p.ptr.tp) str += ', ';
225 }
226 str += ')';
227 }
228
229 return str;
230 };
231
232 // 按层序输出广义表
233 // 层序遍历的问题，一般都是借助队列来完成的，每次从队头
234 // 取出一个元素的同时把它下一层的孩子插入队尾，这是层序遍历的基本思想
235 GLNode.prototype.orderPrint = function(){
236 var queue = [];
237 for(var p = this; p; p = p.ptr.tp) queue.push(p);
238
239 while(queue.length){
240 var r = queue.shift();
241 if(r.tag === ATOM) console.log(r.atom);
242 else {
243 for(r = r.ptr.hp; r; r = r.ptr.tp)
244 queue.push(r);
245 }
246 }
247 };
248
249 // 使用链队列
250 var Queue = require('../Queue/Queue.js').Queue;
251 GLNode.prototype.orderPrint2 = function(){
252 var queue = new Queue();
253
254 for(var p = this; p; p = p.ptr.tp) queue.enQueue(p);
255
256 while(queue.size){
257 var r = queue.deQueue();
258 if(r.tag === ATOM) console.log(r.atom);
259 else {
260 for(r = r.ptr.hp; r; r = r.ptr.tp)
261 queue.enQueue(r);
262 }
263 }
264 };
265
266 console.log(node + '');
267 node.reverse();
268 console.log(node + '');
269
270 var node2 = new GLNode();
271 node.copyList(node2);
272 console.log(GLNode.equal(node, node2));
273
274 console.log(node + '');
275 console.time('A');
276 node.orderPrint();
277 console.timeEnd('A');
278
279 console.log('------------------------------------');
280 console.time('B');
281 node.orderPrint2();
282 console.timeEnd('B');
283
284 /*
285 m元多项式表示
286
287 如果用线性表来表示,则每个数据元素需要m+1个数据项，以存储一个系数和m个指数值，这将产生两个问题。
288 一是无论多项式中各项的变元数是多是少，若都按m个变元分配存储空间，则将造成浪费；反之，若按各项实际的变元数分配存储空间，就会造成结点的大小不匀，给操作带来不便。二是对m值不同的多项式，线性表中的结点大小也不同，这同样引起存储管理的不便。
289 故不适于用线性表表示。
290
291 例如三元多项式：
292 P(x, y, z) = x(10)y(3)z(2) + 2x(6)y(3)z(2) + 3x(5)y(2)z(2) + x(4)y(4)z + 2yz + 15
293
294 如若改写为：
295 P(x, y, z) = ((x(10) + 2x(6))y(3) + 3x(5)y(2))z(2) + ((x(4) + 6x(3))y(4) + 2y)z + 15
296
297 用广义表表示：
298 P = z((A, 2), (B, 1), (15, 0))
299 A = y((C, 3), (D, 2))
300 B = y((E, 4), (F, 1))
301 C = x((1, 10), (2, 6))
302 D = x((3, 5))
303 E = x((1, 4), (6, 3))
304 F = x((2, 0))
305
306
307 */
308
309 function MPNode() {
310 // 区分原子结点和表结点
311 this.tag = undefined;
312 // 指数域
313 this.exp = 0;
314
315 // 系数域
316 this.coef = 0;
317 // 表结点的表头指针
318 this.hp = null;
319
320 // 相当于线性表的next，指向下一个元素结点
321 this.tp = null;
322 }
View Code
时间： 2024-02-25 09:00:50