Skip to main content
 首页 » 编程设计

JS实现数据结构:广义表

2022年07月16日29zhoujg

 广义表是线性表的推广。广泛用于人工智能的表处理语言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 }

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