JavaScript数据结构之广义表的定义与表示方法详解

2019-11-19 16:50:55

字体：大中小

来源：转载

供稿：网友

本文实例讲述了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;//广义表的存储结构function ListNode(){ //标识位 this.tag=undefined; //原子结点的值域 this.atom=null; //列表结点的值域 this.ptr={  hp:null,  tp:null };}

然后是创建广义表的过程：

//创建广义表ListNode.prototype.createList=function(string){ string=string.trim(); //创建单原子广义表 var q; if(/^[/w-]+$/.test(string)){//含有单字符  this;tag=ATOM;  this.atom=string; }else{  this.tag=LIST;  var p =this;  //去掉最外层括号（和）  var sub=string.substr(1,string.length-2);  do{  var h,   i=0,   k=0,   n=sub.length,   ch;  do{   ch=sub[i++];   if(ch=='('){   ++k;   }else if(ch==')'){   --k;   }  }while(i<n&&(ch!=','||k!=0));  //i为第一个逗号分隔索引  if(i<n){   h=sub.substr(0,i-1);//每次遍历取出第一个结点，无论是原子还是列表   sub=sub.substr(i,n-i);  }else{//最后一组   h=sub;   sub='';  }  if(h==='()'){//空子表无表头结点   p.ptr.hp=null;  }else{//创建表头结点   this.createList.call((p.ptr.hp=new ListNode()),h);  }  q=p;  //创建表尾结点  if(sub){   p=new ListNode();   p.tag=LIST;   q.ptr.tp=p;  }  }while(sub);  q.ptr.tp=null; }};

接下就是求广义表的深度，深度的定义为广义表中括弧的重数，是广义表的一种量度。例如，多元多项式广义表的深度为多项式中变元的个数。设LS=（a1,a2,a3,…,an），求LS的深度可以分解为n个之问题，每个子问题为求ai的深度。如果ai是原子，则定义其深度为0，如果ai是广义表，则LS的深度为最大ai的深度+1。空表也是广义表，所以深度为1。实现代码如下：

//求广义表的深度ListNode.prototype.depth=function(){ return getDepth(this);}function 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);  return m>n?m:n; }}

最后我们创建测试案例：

var node=new ListNode();node.createList('((),(a),(b,(c,d,e)))');alert(node.depth());//5

node结点详细如下图：

完整代码如下：

<!DOCTYPE html><html> <head>  <meta charset="utf-8">  <title></title> </head> <body><script type="text/javascript"> var ATOM=0; var LIST=1; //广义表的存储结构 function ListNode(){  //标识位  this.tag=undefined;  //原子结点的值域  this.atom=null;  //列表结点的值域  this.ptr={   hp:null,   tp:null  }; } //创建广义表 ListNode.prototype.createList=function(string){  string=string.trim();  //创建单原子广义表  var q;  if(/^[/w-]+$/.test(string)){//含有单字符   this.tag=ATOM;   this.atom=string;  }else{   this.tag=LIST;   var p =this;   //去掉最外层括号（和）   var sub=string.substr(1,string.length-2);   do{    var h,     i=0,     k=0,     n=sub.length,     ch;    do{     ch=sub[i++];     if(ch=='('){      ++k;     }else if(ch==')'){      --k;     }    }while(i<n&&(ch!=','||k!=0));    //i为第一个逗号分隔索引    if(i<n){     h=sub.substr(0,i-1);//每次遍历取出第一个结点，无论是原子还是列表     sub=sub.substr(i,n-i);    }else{//最后一组     h=sub;     sub='';    }    if(h==='()'){//空子表无表头结点     p.ptr.hp=null;    }else{//创建表头结点     this.createList.call((p.ptr.hp=new ListNode()),h);    }    q=p;    //创建表尾结点    if(sub){     p=new ListNode();     p.tag=LIST;     q.ptr.tp=p;    }   }while(sub);   q.ptr.tp=null;  } }; //求广义表的深度 ListNode.prototype.depth=function(){  return getDepth(this); } function 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);   return m>n?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、为什么呢

长度的求法为最大括号中的逗号数加一、LS最大括号内有

1. f 元素后边有个逗号、
2.（）元素后有个逗号、
3.（e）元素后有个逗号
4. （a，（b，c，d））后边没有逗号 ----把这个看成是一个元素

也就是三个逗号同样被分成四组、长度就为四了

深度的求法为上面每个元素的括号匹配数加1

1. f元素的深度为0+1=1
2. （）元素深度为1+1=2
3. （e）元素深度为1+1=2
4 . （a，（b，c，d））元素的深度为2+1=3

所以深度为3

综上所诉、长度为4、深度为3

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