本文阐述了JavaScript数据结构的广义表的定义和表示。分享给大家参考，如下：

广义表是线性表的扩展，有人称之为列表。那么它和线性表有什么区别呢？线性表中的每个成员只能是单个元素，而广义表中的成员可以是单个元素，也可以是广义表，称为广义表的原子和子表。这里有一些通用表格的例子。

a=()；b=(e)；C=(a，(b，c，d))；D=(()、(e)、(a)、(b、c、d)))；E=(a，E)；

由于广义表中的数据元素可以有不同的结构(原子或列表)，很难用顺序存储结构来表示，通常采用链式存储结构。因为列表中的元素可以是原子，也可以是列表，所以需要两种节点，一种是表节点，一种是原子节点。

表格节点由三个字段组成，包括标志字段、指向页眉的指针字段和指向页脚的指针字段。原子节点只需要两个域，一个标志域和一个值域。下图：

上述五个列表的存储结构如下：

让我们用JavaScript来实现广义表及其基本操作。

首先，我们需要定义通用表的存储结构：

var ATOM=0；var LIST=1；//广义表函数ListNode()的内存结构{ //标识位this.tag=undefined//原子节点的值字段为this.atom=null//列表节点的值字段是this.ptr={hp:null，TP : null }；}然后是创建通用表的过程：

//创建通用表list node . prototype . create list=function(string){ string=string . trim()；//创建单原子广义表var q；If (/[ w-] $/。test(string)){//包含单个字符thistag=ATOMthis.atom=string} else { this.tag=LISTvar p=这个；//删除最外面的括号(和)var sub=string.substr (1，string . length-2)；do{ var h，i=0，k=0，n=子长，ch；do { ch=sub[I]；if(ch=='('){ k；} else if(ch==')'){-k；} }while(in(ch！='，' ||k！=0));//i是第一个逗号分隔的索引if(in){ h=substr(0，I-1)；//每次遍历都取出第一个节点，无论是atom还是list sub=sub substr(I，n-I)；}else{//最后一组h=subsub=} if(h==='()'){//空子表没有头节点p . ptr . HP=null；}else{//创建头节点this . create list . call((p . ptr . HP=newlistnode())，h)；} q=p；//创建页脚节点if(sub){ p=new ListNode()；p.tag=LISTq . ptr . TP=p；} } while(sub)；q . ptr . TP=null；}};下一步是找到广义表的深度，它被定义为广义表中括号的多重性，是广义表的度量。比如多元多项式广义表的深度就是多项式中变量的个数。设LS=(a1，a2，a3，…，an)，LS的深度可以分解成n个问题，每个子问题就是ai的深度。如果ai是原子，它的深度定义为0，如果ai是广义表，LS的深度就是最大ai 1的深度。空表也是广义表，因此深度为1。实现代码如下：

//求广义表list node . prototype . depth=function(){ return get depth(this)；}函数getDepth(list){//深度就是括号的多重性，也可以理解为左括号的个数if(！list){ return 1；} else if(list . tag===ATOM){ return 0；} else { var m=GetDepth(list . ptr . HP)1；var n=GetDepth(list . ptr . TP)；返回mn？m:n}}最后，我们创建一个测试用例：

var node=new ListNode()；node.createList('(()，(a)、(b)、(c、d、e)))')；alert(node . depth())；//5节点详情如下：

完整的代码如下：

！DOCTYPE html html head meta charset=' utf-8 ' title/title/head body script type=' text/JavaScript ' var ATOM=0；var LIST=1；//广义表函数ListNode()的内存结构{ //标识位this.tag=undefined//原子节点的值字段是this.atom=null//列表节点的值字段是this.ptr={hp:null，TP : null }；}//创建通用表list node . prototype . create list=function(string){ string=string . trim()；//创建单原子广义表var q；If (/[ w-] $/。test(string)){//包含单个字符this.tag=ATOMthis.atom=string} else { this.tag=LISTvar p=这个；//删除最外面的括号(和)var sub=string.substr (1，string . length-2)；do{ var h，i=0，k=0，n=子长，ch；do { ch=sub[I]；if(ch=='('){ k；} else if(ch==')'){-k；} }while(in(ch！='，' ||k！=0));//i是第一个逗号分隔的索引if(in){ h=substr(0，I-1)；//每次遍历都取出第一个节点，无论是atom还是list sub=sub substr(I，n-I)；}else{//最后一组h=subsub=} if(h==='()'){//空子表没有头节点p . ptr . HP=null；}else{//创建头节点this . create list . call((p . ptr . HP=newlistnode())，h)；} q=p；//创建页脚节点if(sub){ p=new ListNode()；p.tag=LISTq . ptr . TP=p；} } while(sub)；q . ptr . TP=null；} };//求广义表list node . prototype . depth=function(){ return get depth(this)；}函数getDepth(list){//深度就是括号的多重性，也可以理解为左括号的个数if(！list){ return 1；} else if(list . tag===ATOM){ return 0；} else { var m=GetDepth(list . ptr . HP)1；var n=GetDepth(list . ptr . TP)；返回mn？m:n} } var node=new ListNode()；node.createList('(()，(a)、(b)、(c、d、e)))')；alert(node . depth())；//5/script /body/html由于广义表的应用主要在于数学领域的公式推导和计算，这里不再详细说明。

这里，添加广义表的长度和深度算法：

广义表LS=(f，()，(e)，(a，(b，c，d))的长度和深度是多少？

例如，在上表中，长度为4，深度为3。为什么

长度是通过在最大括号中的逗号数量上加1来计算的，有

1.f元素后有一个逗号，2。()元素后有一个逗号，3。(e)元素后有一个逗号，4。(a，(b，c，d)后面没有逗号-把这个作为一个元素

也就是说，三个逗号也分为四组，长度为四

深度是通过将1加到上面每个元素的匹配括号数上来计算的

1.f元素的深度为0.1=12。()元素深度为1.1=23。(e)元素深度为1.1=24。(a，(b，c，d))元素深度为2.1=3

所以深度是3

总而言之，长度是4，深度是3

更多对JavaScript相关内容感兴趣的读者可以查看本网站专题：《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》、《JavaScript错误与调试技巧总结》、0103010。

希望本文对JavaScript编程有所帮助。