溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

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

發(fā)布時間：2020-10-26 00:25:07 來源：腳本之家 閱讀：397 作者：布瑞澤的童話 欄目：web開發(fā)

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

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

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

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

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

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

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

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

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

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

var ATOM=0;
var LIST=1;
//廣義表的存儲結(jié)構(gòu)
function ListNode(){
 //標識位
 this.tag=undefined;
 //原子結(jié)點的值域
 this.atom=null;
 //列表結(jié)點的值域
 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;
  //去掉最外層括號（和）
  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);//每次遍歷取出第一個結(jié)點，無論是原子還是列表
   sub=sub.substr(i,n-i);
  }else{//最后一組
   h=sub;
   sub='';
  }
  if(h==='()'){//空子表無表頭結(jié)點
   p.ptr.hp=null;
  }else{//創(chuàng)建表頭結(jié)點
   this.createList.call((p.ptr.hp=new ListNode()),h);
  }
  q=p;
  //創(chuàng)建表尾結(jié)點
  if(sub){
   p=new ListNode();
   p.tag=LIST;
   q.ptr.tp=p;
  }
  }while(sub);
  q.ptr.tp=null;
 }
};

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

//求廣義表的深度
ListNode.prototype.depth=function(){
 return getDepth(this);
}
function getDepth(list){//深度為括號的重數(shù)，也可理解為左括號出現(xiàn)的個數(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é)點詳細如下圖：

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

完整代碼如下：

<!DOCTYPE html>
<html>
 <head>
  <meta charset="utf-8">
  <title></title>
 </head>
 <body>
<script type="text/javascript">
 var ATOM=0;
 var LIST=1;
 //廣義表的存儲結(jié)構(gòu)
 function ListNode(){
  //標識位
  this.tag=undefined;
  //原子結(jié)點的值域
  this.atom=null;
  //列表結(jié)點的值域
  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;
   //去掉最外層括號（和）
   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);//每次遍歷取出第一個結(jié)點，無論是原子還是列表
     sub=sub.substr(i,n-i);
    }else{//最后一組
     h=sub;
     sub='';
    }
    if(h==='()'){//空子表無表頭結(jié)點
     p.ptr.hp=null;
    }else{//創(chuàng)建表頭結(jié)點
     this.createList.call((p.ptr.hp=new ListNode()),h);
    }
    q=p;
    //創(chuàng)建表尾結(jié)點
    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){//深度為括號的重數(shù)，也可理解為左括號出現(xiàn)的個數(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ù)學領(lǐng)域的公式推導(dǎo)和演算上，這里就不再詳解了。

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

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

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

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

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

也就是三個逗號 同樣被分成四組、長度就為四了

深度的求法為上面每個元素的括號匹配數(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ù)學運算用法總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯誤與調(diào)試技巧總結(jié)》

希望本文所述對大家JavaScript程序設(shè)計有所幫助。

向AI問一下細節(jié)

免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手