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

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

創(chuàng)新互聯(lián)堅持“要么做到，要么別承諾”的工作理念，服務領域包括：成都做網(wǎng)站、網(wǎng)站設計、企業(yè)官網(wǎng)、英文網(wǎng)站、手機端網(wǎng)站、網(wǎng)站推廣等服務，滿足客戶于互聯(lián)網(wǎng)時代的禪城網(wǎng)站設計、移動媒體設計的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡建設合作伙伴！

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

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

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

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

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

上面講到的五個列表的存儲結構如下圖：

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

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

首先需要定義廣義表的存儲結構：

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

接下就是求廣義表的深度，深度的定義為廣義表中括弧的重數(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結點詳細如下圖：

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

完整代碼如下：

<!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
  };
 }
 //創(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);//每次遍歷取出第一個結點，無論是原子還是列表
     sub=sub.substr(i,n-i);
    }else{//最后一組
     h=sub;
     sub='';
    }
    if(h==='()'){//空子表無表頭結點
     p.ptr.hp=null;
    }else{//創(chuàng)建表頭結點
     this.createList.call((p.ptr.hp=new ListNode()),h);
    }
    q=p;
    //創(chuàng)建表尾結點
    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>

由于廣義表的應用多在于數(shù)學領域的公式推導和演算上，這里就不再詳解了。

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

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

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

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

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

更多關于JavaScript相關內容感興趣的讀者可查看本站專題：《JavaScript數(shù)據(jù)結構與算法技巧總結》、《JavaScript數(shù)學運算用法總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》、《JavaScript查找算法技巧總結》及《JavaScript錯誤與調試技巧總結》

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

本文題目：JavaScript數(shù)據(jù)結構之廣義表的定義與表示方法詳解
網(wǎng)站URL：http://m.kartarina.com/article20/jeopco.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供響應式網(wǎng)站、企業(yè)建站、搜索引擎優(yōu)化、小程序開發(fā)、網(wǎng)站導航、用戶體驗

聲明：本網(wǎng)站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經(jīng)允許不得轉載，或轉載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內容