JavaScript數(shù)據(jù)結(jié)構(gòu)之廣義表的定義與表示方法詳解

更新時(shí)間：2017年04月12日 11:20:34 作者：布瑞澤的童話

這篇文章主要介紹了JavaScript數(shù)據(jù)結(jié)構(gòu)之廣義表的定義與表示方法,簡單講述了廣義表的原理與相關(guān)概念,并結(jié)合實(shí)例形式分析了javascript定義與使用廣義表的相關(guān)操作技巧,需要的朋友可以參考下

本文實(shí)例講述了JavaScript數(shù)據(jù)結(jié)構(gòu)之廣義表的定義與表示方法。分享給大家供大家參考，具體如下：

廣義表是線性表的推廣，也有人稱其為列表。那么它和線性表有什么區(qū)別呢？線性表中每個(gè)成員只能是單個(gè)元素，而廣義表中的成員可以是單個(gè)元素，也可以是廣義表，分別稱為廣義表的原子和子表。下面舉幾個(gè)廣義表的例子。

A=(); B=(e); C=(a,(b,c,d)); D=((),(e),(a,(b,c,d))); E=(a,E);

由于廣義表中的數(shù)據(jù)元素可以具有不同的結(jié)構(gòu)（原子或列表），因此難以用順序存儲(chǔ)結(jié)構(gòu)表示，通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。由于列表中的元素可以是原子也可以是列表，所以需要兩種結(jié)構(gòu)的節(jié)點(diǎn)，一種是表節(jié)點(diǎn)，一種是原子節(jié)點(diǎn)。

一個(gè)表節(jié)點(diǎn)由三個(gè)域組成，標(biāo)志域、指向表頭的指針域、指向表尾的指針域。而原子節(jié)點(diǎn)只需要兩個(gè)域，標(biāo)志域和值域。如下圖：

上面講到的五個(gè)列表的存儲(chǔ)結(jié)構(gòu)如下圖：

我們用JavaScript來實(shí)現(xiàn)廣義表及其基本操作吧。

首先需要定義廣義表的存儲(chǔ)結(jié)構(gòu)：

var ATOM=0;
var LIST=1;
//廣義表的存儲(chǔ)結(jié)構(gòu)
function ListNode(){
 //標(biāo)識(shí)位
 this.tag=undefined;
 //原子結(jié)點(diǎn)的值域
 this.atom=null;
 //列表結(jié)點(diǎn)的值域
 this.ptr={
  hp:null,
  tp:null
 };
}

然后是創(chuàng)建廣義表的過程：

//創(chuàng)建廣義表
ListNode.prototype.createList=function(string){
 string=string.trim();
 //創(chuàng)建單原子廣義表
 var q;
 if(/^[\w-]+$/.test(string)){//含有單字符
  this;tag=ATOM;
  this.atom=string;
 }else{
  this.tag=LIST;
  var p =this;
  //去掉最外層括號(hào)（和）
  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為第一個(gè)逗號(hào)分隔索引
  if(i<n){
   h=sub.substr(0,i-1);//每次遍歷取出第一個(gè)結(jié)點(diǎn)，無論是原子還是列表
   sub=sub.substr(i,n-i);
  }else{//最后一組
   h=sub;
   sub='';
  }
  if(h==='()'){//空子表無表頭結(jié)點(diǎn)
   p.ptr.hp=null;
  }else{//創(chuàng)建表頭結(jié)點(diǎn)
   this.createList.call((p.ptr.hp=new ListNode()),h);
  }
  q=p;
  //創(chuàng)建表尾結(jié)點(diǎn)
  if(sub){
   p=new ListNode();
   p.tag=LIST;
   q.ptr.tp=p;
  }
  }while(sub);
  q.ptr.tp=null;
 }
};

接下就是求廣義表的深度，深度的定義為廣義表中括弧的重?cái)?shù)，是廣義表的一種量度。例如，多元多項(xiàng)式廣義表的深度為多項(xiàng)式中變元的個(gè)數(shù)。設(shè)LS=（a1,a2,a3,…,an），求LS的深度可以分解為n個(gè)之問題，每個(gè)子問題為求ai的深度。如果ai是原子，則定義其深度為0，如果ai是廣義表，則LS的深度為最大ai的深度+1?？毡硪彩菑V義表，所以深度為1。實(shí)現(xiàn)代碼如下：

//求廣義表的深度
ListNode.prototype.depth=function(){
 return getDepth(this);
}
function getDepth(list){//深度為括號(hào)的重?cái)?shù)，也可理解為左括號(hào)出現(xiàn)的個(gè)數(shù)
 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;
 }
}

最后我們創(chuàng)建測試案例：

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

node結(jié)點(diǎn)詳細(xì)如下圖：

完整代碼如下：

<!DOCTYPE html>
<html>
 <head>
  <meta charset="utf-8">
  <title></title>
 </head>
 <body>
<script type="text/javascript">
 var ATOM=0;
 var LIST=1;
 //廣義表的存儲(chǔ)結(jié)構(gòu)
 function ListNode(){
  //標(biāo)識(shí)位
  this.tag=undefined;
  //原子結(jié)點(diǎn)的值域
  this.atom=null;
  //列表結(jié)點(diǎn)的值域
  this.ptr={
   hp:null,
   tp:null
  };
 }
 //創(chuàng)建廣義表
 ListNode.prototype.createList=function(string){
  string=string.trim();
  //創(chuàng)建單原子廣義表
  var q;
  if(/^[\w-]+$/.test(string)){//含有單字符
   this.tag=ATOM;
   this.atom=string;
  }else{
   this.tag=LIST;
   var p =this;
   //去掉最外層括號(hào)（和）
   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為第一個(gè)逗號(hào)分隔索引
    if(i<n){
     h=sub.substr(0,i-1);//每次遍歷取出第一個(gè)結(jié)點(diǎn)，無論是原子還是列表
     sub=sub.substr(i,n-i);
    }else{//最后一組
     h=sub;
     sub='';
    }
    if(h==='()'){//空子表無表頭結(jié)點(diǎn)
     p.ptr.hp=null;
    }else{//創(chuàng)建表頭結(jié)點(diǎn)
     this.createList.call((p.ptr.hp=new ListNode()),h);
    }
    q=p;
    //創(chuàng)建表尾結(jié)點(diǎn)
    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){//深度為括號(hào)的重?cái)?shù)，也可理解為左括號(hào)出現(xiàn)的個(gè)數(shù)
  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>

由于廣義表的應(yīng)用多在于數(shù)學(xué)領(lǐng)域的公式推導(dǎo)和演算上，這里就不再詳解了。

這里補(bǔ)充一下廣義表的長度和深度算法：

廣義表LS=(f,(),(e),(a,(b,c,d)))的長度是多少,深度是多少

例如上表、長度為4、深度為3、為什么呢

長度的求法為最大括號(hào)中的逗號(hào)數(shù)加一、LS最大括號(hào)內(nèi)有

1. f 元素后邊有個(gè)逗號(hào)、
2.（）元素后有個(gè)逗號(hào)、
3.（e）元素后有個(gè)逗號(hào)
4. （a，（b，c，d））后邊沒有逗號(hào) ----把這個(gè)看成是一個(gè)元素

也就是三個(gè)逗號(hào) 同樣被分成四組、長度就為四了

深度的求法為上面每個(gè)元素的括號(hào)匹配數(shù)加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

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯(cuò)誤與調(diào)試技巧總結(jié)》